算法数据结构 单链表的实现+操作 以及和顺序表的对比
浏览数：23 /
时间：2015年06月08日
顺序表和单链表的优缺点对比：
顺序表的优点，无需为表示表中元素之间的逻辑关系而增加额外的存储空间；
可以快速的存取表中的任意位置的元素。
顺序表的缺点，插入后删除操作需要移动大量元素；
当线性表长度不稳定时，存储空间难确定，容易造成存储空间碎片。
对于单链表
链式存储即元素存储的内存单元可以是不连续，分散的。对于元素间如何来维护他们的关系（即逻辑结构，每个元素的前驱和后继。）
即用到一个指针域来存储他和前驱或是后继直接的关系。
如上面的是一个单链表的指针结构，即每个元素中存储了他的后继元素的内存空间地址。
应用场景选择
由上图可以简单的知道数据的常见的操作，增，删，改，查时。
对于数据操作偏向于查和改时，顺序存储的速度是非常快的，而链表的话，则必须从头节点开始遍历查找。
但是涉及到插入或是删除元素时，顺序存储每次操作为了维护顺序，必须移动元素，而对于链表来说，只需新增一个存储单元后，对其中几个指针域中指针的指向做下改变就行。
tips1. 但是我们要注意的是， 表的插入和删除操作其实有两部分组成：遍历找到第i个元素，然后删除或插入。那其实顺序表这步的时间复杂度为 O（1），
而单链表的时间复杂度为O（n），虽然后面的话顺序表需要将i后面的元素都往后移动一位，话费的时间相对来说就是O(n),而单链表无需移动元素，
时间就为O（1）。看上去其实貌似扯平啊，这样单链表相对于线性表的顺序存储结构来说没什么大的优势。但是如果在第i点插入k个元素时，
那么相对于链表来说只要第一遍历查找到了第i个元素后，之后的操作基本是是O（1），而顺序的操作的话，是每次都要移动n-i个元素，O（n），
效果就出来了。
tips2.而对于顺序表，如果我们的插入和删除操作，在不考虑存储空间额分配这个死角的话（即存储空间可以动态的申请，不考虑溢出），
都是在对最后的一个元素进行操作，那不是也很好，即删除和插入都是在表尾进行，那么就不用移动大量元素了。
代码实现：
#ifndef _LIST_H
#define _LIST_H
#include<iostream>
#include<assert.h>//断言
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
#include<iostream>
using namespace std;
#define ElemType int
typedef struct Node
{
ElemType data;
struct Node *next;
}Node, *PNode;
typedef PNode List;
/*-------------------------函数声明------------------------*/
void menu();//菜单
void InitList(List *list);//初始化函数
bool CreateList(List *list, int count);//创建函数
bool isEmpty(List *list);//判断空
bool push_front(List *list, ElemType x);//头插
int push_back(List *list, ElemType x);//尾插
bool pop_front(List *list);//头删
bool pop_back(List *list);//尾删
Node* find(List *list, ElemType x);//查询 返回输入序号的指针
int LocatePos(List *list, ElemType x);//查询 获取输入序号的值
void Length(List *list);//长度
bool delete_pos(List *list, ElemType pos);//位置删除
bool delete_val(List *list, ElemType x);//值删
bool modify(List *list, int pos, ElemType x);//修改某位置的值域
bool DestroyList(List *list);//摧毁
void ShowList(List list);//显示
bool insert_pos(List *list, int pos, ElemType x);//位置插入
bool insert_val(List *list, ElemType x);//值 插入（有序前提）
bool sort(List *list);//排序
Node* resver(List *list);//逆置
void reverse_2(List *list);//逆置
Node* next(List *list, ElemType key);//返回输入位置的后继节点
Node* prio(List *list, ElemType key);//返回输入位置的前驱节点
Node* Pfind(List *list, size_t pos);//返回对应位置的指针
#endif
#include"List.h"
/*-----------------函数实现部分----------------------*/
void menu()
{
cout << " " << endl;
cout << "**********************************" << endl;
cout << "* [100] CreateList *" << endl;
cout << "* [0] quit_system [1] push_back *" << endl;
cout << "* [2] push_front [3] show_list *" << endl;
cout << "* [4] pop_back [5] pop_front *" << endl;
cout << "* [6] insert_pos *" << endl;
cout << "* [8] delete_pos [9] delete_val *" << endl;
cout << "* [10] find [11] LocatePos *" << endl;
cout << "* [12] modify [13] destroy *" << endl;
cout << "* [14] sort [15] resver *" << endl;
cout << "* [16] length [17] next *" << endl;
cout << "* [18] prio *" << endl;
cout << "**********************************" << endl;
cout << "plese chose:>";
}
/*-----------初始化单链表———————————————*/
void InitList(List *list)
{
*list = (Node *)malloc(sizeof(Node));
(*list)->next = NULL;
(*list)->data = 0;
}
/*---------头节点的方式创建单链表---------------------*/
//???????
bool CreateList(List *list,int count) //Node * *list
{
Node *p = *list;
ElemType x = 0;
for (int i = 1; i <= count; ++i)
{
cin >> x;
p = p->next = (Node *)malloc(sizeof(Node));
p->data = x;
p->next = NULL;
(*list)->data++;
}
return false;
}
/*----判断空--------*/
bool isEmpty(List *list)
{
return (NULL == (*list)->next);
}
/*-----------------尾插————————————*/
int push_back(List *list, ElemType x)
{
if (isEmpty(list))
return 0;
Node* cur = (*list)->next;
while (cur->next != NULL)
{
cur = cur->next;
}
Node *p = (Node *)malloc(sizeof(Node));
if (p == NULL)
return 0;
p->data = x;
cur->next = p;
p->next = NULL;
(*list)->data++;
}
/*-----------------头插————————————*/
bool push_front(List *list, ElemType x)
{
Node *p = (Node *)malloc(sizeof(Node));
if (p == NULL)
return false;
p->data = x;
p->next = (*list)->next;
(*list)->next = p;
(*list)->data++;
}
/*------显示--------------*/
void ShowList(List list)
{
Node *p = list->next;
while (p != NULL)
{
cout << p->data << "-->";
p = p->next;
}
cout << "Nul" << endl;
}
/*-----------------尾删————————————*/
bool pop_back(List *list)
{
if (isEmpty(list))
return false;
Node* cur = (*list);
while (cur->next != NULL && cur->next->next != NULL)
{
cur = cur->next;
}
free(cur->next);
cur->next = NULL;
(*list)->data--;
return true;
}
/*-----------------头删————————————*/
bool pop_front(List *list)
{
if (isEmpty(list))
return false;
Node *p = (*list)->next;
(*list)->next = p->next;
free(p);
p = NULL;
(*list)->data--;
}
/*-------------------按位置插入--------------*/
bool insert_pos(List *list, int pos, ElemType x)
{
Node *p = Pfind(list, pos - 1);//寻找第i-1个结点
if (p == NULL)//i<1或i>n+1时插入位置i有错
{
cout << "ERROR POS" << endl;
}
Node* s = (Node *)malloc(sizeof(Node));
s->data = x;
s->next = p->next;
p->next = s;
return false;
}
/*--------位置删除---------------*/
bool delete_pos(List *list, ElemType pos)
{
int count = 1;
Node* cur = NULL;
Node* pre = *list;
while (pre->next != NULL && pre->next->next != NULL && count < pos)//找到前驱
{
pre = pre->next;
count++;
}
if (count != pos)
{
cout << "ERROE pos" << endl;
return false;
}
cur = pre->next;
pre->next = cur->next;
free(cur);
cur = NULL;
(*list)->data--;
return true;
}
/*----------按值删除-------------*/
bool delete_val(List *list, ElemType x)
{
Node* pre = *list;
Node* cur = NULL;
while (pre->next != NULL && pre->next->next != NULL)//找到前驱
{
if (x == pre->next->data)
{
cur = pre->next;
pre->next = cur->next;
free(cur);
cur = NULL;
return true;
}
pre = pre->next;
}
(*list)->data--;
return true;
}
/*----------------查询 返回指针————————————*/
Node* find(List *list, ElemType x)
{
Node *p = (*list)->next;
while (p)
{
if (p->data != x)
p = p->next;
else
break;
}
return p;
}
/*----------输入序号 返回指针——————*/
Node* Pfind(List *list, size_t pos)
{
size_t count = 1;
Node *p = (*list)->next;
while (count < pos)
{
p = p->next;
count++;
}
if (count != pos)
return NULL;
return p;
}
/*-----------------查询 返回序号————————————*/
int LocatePos(List *list, ElemType x)
{
Node* cur = (*list)->next;
int count = 0;
while (cur)
{
count++;
if (x == cur->data)
return count; //返回是第几个元素
cur = cur->next;
}
return 0;
}
/*--------------修改---------------*/
bool modify(List *list,int pos, ElemType x)
{
int count = 1;
if (pos < 0 || pos >(*list)->data)
return false;
Node* cur = (*list)->next;
while (cur != NULL && cur->next != NULL)
{
if (count == pos)
{
cur->data = x;
return true;
}
cur = cur->next;
count++;
}
return false;
}
/*-------销毁-------------*/
bool DestroyList(List *list)
{
Node *p = (*list);
Node *q = NULL;
while (p)
{
q = p->next;
free(p);
p = q;
}
(*list)->next = NULL;
cout << "the List was destroyed !" << endl;
cout << "After destroy ,any operation is invalid!" << endl;
cout << "Please quit_system!" << endl;
return true;
}
/*----------排序--------------*/
bool sort(List *list)
{
if (isEmpty(list))
return false;
Node* p = NULL;
Node* q = NULL;
for (p = (*list)->next; p != NULL; p = p->next)
{
for (q = p->next; q != NULL; q = q->next)
{
if (p->data > q->data)
{
p->data = p->data ^ q->data;
q->data = p->data ^ q->data;
p->data = p->data ^ q->data;
}
}
}
return true;
}
/*-------逆置-----------*/
Node* resver(List *list)
{
Node *p = (*list)->next;
Node *q = NULL;
Node *r = NULL;
while (p)
{
q = p->next;
p->next = r;
r = p;
p = q;
}
return r;
}
void reverse_2(List *list)
{
Node *p, *q;
p = (*list)->next; //P指向链表第一个元素
(*list)->next = NULL; //断开头结点与链表
while (p != NULL)
{
q = p;
p = p->next;
q->next = (*list)->next; //相当于前插法构建新的链表，和原来的相反
(*list)->next = q;
}
}
/*----------------返回长度————————————*/
void Length(List *list)
{
cout << "the length of list is:>" << (*list)->data << endl;
}
/*-----------------返回后继————————————*/
Node* next(List *list, ElemType key) //输入节点序号返回其后继节点
{
Node* cur = (*list)->next;
int count = 1;
if (isEmpty(list) || key < 0 || key > (*list)->data)
return false;
while (count < key)
{
cur = cur->next;
count++;
}
if (count == key)
{
cur = cur->next;
return cur;
}
else
{
cout << "ERROE" << endl;
return false;
}
}
/*-----------------返回前驱————————————*/
Node* prio(List *list, ElemType key)
{
Node* pre = (*list);
Node* cur = (*list)->next;
int count = 1;
if (isEmpty(list) || key < 1 || key > (*list)->data)
return false;
while (count < key)
{
pre = pre->next;
cur = cur->next;
count++;
}
if (count == key)
{
return pre;
}
else
{
cout << "ERROE" << endl;
return false;
}
}
#include"List.h"
int main(void)
{
List mylist;
InitList( &mylist);
ElemType item;
int pos = 0;
int select = 1;
int length = 0;
while (select)
{
menu();
cin >> select;
switch (select)
{
case 100:
cout << "please input the length:>" ;
cin >> length;
cout << "please input the data:>" ;
CreateList(&mylist, length);
break;
case 1:
cout << "please enter data:>";
cin >> item;
push_back(&mylist, item);
break;
case 2:
cout << "please enter data:>";
cin >> item;
push_front(&mylist, item);
break;
case 3:
ShowList(mylist);
break;
case 4:
pop_back(&mylist);
break;
case 5:
pop_front(&mylist);
break;
case 6:
cout << "please enter position:>";
cin >> pos;
cout << "please enter insert data:>";
cin >> item;
insert_pos(&mylist, pos, item);
break;
case 8:
cout << "please enter position:>";
cin >> pos;
delete_pos(&mylist, pos);
break;
case 9:
cout << "please enter delete data:>";
cin >> item;
delete_val(&mylist, item);
break;
case 10:
cout << "please enter data:>";
cin >> item;
cout << "the piont of pos is:>" << find(&mylist, item) << endl;
break;
case 11:
cout << "please enter data:>";
cin >> item;
cout << "the number of pos is>" << LocatePos(&mylist, item)<< endl;
break;
case 12:
cout << "please enter position:>";
cin >> pos;
cout << "please enter the modify data:>";
cin >> item;
modify(&mylist, pos, item);
break;
case 13:
DestroyList(&mylist);
break;
case 14:
sort(&mylist);
cout << "the changes of SeqList will be incremental ! " << endl;
ShowList(mylist);
break;
case 15:
(mylist)->next = resver(&mylist);
cout << "the changes of List will be resver ! " << endl;
ShowList(mylist);
reverse_2(&mylist);
cout << "the changes of List will be resver ! " << endl;
ShowList(mylist);
break;
case 16:
Length(&mylist);
break;
case 17:
cout << "please enter position:>";
cin >> pos;
if (pos <= 0 || pos >= (mylist)->data)//保证输入位置正确
{
cout << "ERROR POS" << endl;
break;
}
cout << "the NextPosData is:>" << next(&mylist, pos)->data;
break;
case 18:
cout << "please enter position:>";
cin >> pos;
if (pos <= 1 || pos > (mylist)->data)//保证输入位置正确
{
cout << "ERROR POS" << endl;
break;
}
cout << "the PrePosData is:>" << prio(&mylist, pos)->data;
break;
}
}
return 0;
}郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
