实验二单链表基本操作的实现

实验二 单链表基本操作的实现【实验课程名称】数据结构【实验项目名称】单链表基本操作的实现【实验目的】1 理解单链表的存储结构及基本操作的定义；2掌握单链表存储基本操作；3学会设计实验数据验证程序。【实验仪器及环境】计算机，window xp操作系统，VC+6.0【实验内容及步骤】1 单链表顺序存储基本操作存储结构定义：typedef struct LNode /结点类型 ElemType data; struct LNode *next;*Link,*Position;typedef struct /链表类型Link head,tail;int len;LinkList;实现的基本操作：#include#include#include#includeusing namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct LNode /结点类型ElemType data;struct LNode *next;*Link,*Position;typedef struct /链表类型Link head,tail;int len;LinkList;Position MakeNode_L(Link &p,ElemType e) /创建结点p=(Link)malloc(sizeof(LNode);if(!p) return ERROR;p-data=e;p-next=NULL;return p;void FreeNode_L(Link &q) /释放结点free(q);Status InitList_L(LinkList &L)/初始化L为一个带头结点的空链表,头尾指针指向头结点，表长赋ElemType e;e=-1;/实际应用中此初始化语句需要修改if(!MakeNode_L(L.head,e)return ERROR;/开辟头结点L.tail=L.head;L.len=0;return OK;/InitList_LStatus DestroyList_L(LinkList &L)/销毁链表LLink p;while(p=L.head-next)/依次释放有序链表中第一个元素至最后一个元素所占用空间;L.head-next=p-next;free(p);free(L.head);L.head=NULL;L.tail=NULL;L.len=0;coutendlThe list has been destroyed!next;while(p)q=p-next;free(p);p=q;L.tail=L.head;L.len=0;return OK;Status InsFirst_L(LinkList &L,Link s) /在首元素前插入一个结点s-next=L.head-next;if(!L.head-next)L.tail=s;L.head-next=s;L.len+;return OK;Status DelFirst_L(LinkList &L,Link h,Link &q) /删除首结点h=L.head;q=L.head-next;if(q)h-next=q-next;q-next=NULL;if(!h-next)L.tail=h;L.len-;return OK;elsereturn ERROR;Status Append_L(LinkList &L,Link s) /将两个链表跟一个字符串连接起来Link q;if(!L.head-next)L.head-next=q=s;elseL.tail-next=q=s;while(q-next)q=q-next;L.tail=q;return OK;Position Remove_L(LinkList &L,Link &q) /删除尾结点Link p;p=L.head;if(!L.head-next) coutThe LinkList is empty!next!=L.tail)p=p-next;q=L.tail;L.tail=p;L.tail-next=NULL;L.len-;return q;Status InsBefore_L(LinkList &L,Link &p,Link s) /在p指向的结点前插入一个结点Link q;q=L.head;if(p=L.head) cout 不能在这个地方插入元素!next!=p)q=q-next;s-next=p;q-next=s;L.len+;return OK;Status InsAfter_L(LinkList &L,Link &p,Link s) /在p指向的结点后插入一个结点if(p=L.tail) L.tail=s;s-next=p-next;p-next=s;L.len+;return OK;Status SetCurElem_L(Link &p,ElemType e) /改变p指向的结点的内容p-data=e;return OK;ElemType GetCurElem_L(Link p) /获取p指向的结点的内容return p-data;int ListLength_L(LinkList L) /获取单链表的长度值return L.len;Status ListEmpty_L(LinkList L) /判断单链表是否为空，是返回，否返回if(L.head=L.tail) return TRUE;else return FALSE;Position GetHead_L(LinkList L) /获取头指针的地址return L.head;Position GetLast_L(LinkList L) /获取尾指针的地址return L.tail;Position PriorPos_L(LinkList L,Link p) /获取p的前驱Link q;q=L.head;if(p=L.head-next) return NULL;elsewhile(q-next!=p)q=q-next;return q;Position NextPos_L(LinkList L,Link p) /获取p的后继if(!p-next) return NULL;return p-next;Status LocatePos_L(LinkList L,int i,Link &p) /查找p在单链表中的位置iint j;if(inext;for(j=1;jnext;if(!p) return ERROR;return OK;Status compare(ElemType x,ElemType y) /比较函数if(x=y)return 1;elsereturn 0;Status LocateElem_L(LinkList L,ElemType e,Link &p) /返回跟e相同的值，没有的话返回空指针int i=0;p=L.head;doi+;p=p-next;while(p&!compare(p-data,e);if(p)coutiendl;elsecoutIt is not in here!next;while(p-next)visit(p-data);p=p-next;return OK;Status ListInsert_L(LinkList &L,int i,ElemType e) /在第i个位置后插入一个元素int j;Link p,s;s=(Link)malloc(sizeof(LNode);p=L.head-next;for(j=1;jnext;s-data=e;s-next=p-next;p-next=s;L.len+;return OK;Status ListDelete_L(LinkList &L,int i) /删除第i个元素的结点if(iL.len) return ERROR;int j;Link p;p=L.head-next;for(j=1;jnext;p-next=p-next-next;L.len-;return OK;Status MergeList_L(LinkList La,LinkList Lb,LinkList &Lc) /将两个字符串连接起来Link p,q,t;p=La.head-next;q=Lb.head-next;while(p&q)if(p-datadata)MakeNode_L(t,p-data);InsFirst_L(Lc,t);p=p-next;elseMakeNode_L(t,q-data);InsFirst_L(Lc,t);q=q-next;while(p)MakeNode_L(t,p-data);InsFirst_L(Lc,t);p=p-next;while(q)MakeNode_L(t,q-data);InsFirst_L(Lc,t);q=q-next;return OK;【测试数据及实验结果】int main()LinkList la,lb,lc;Link p,q,s,k,t;InitList_L(la);InitList_L(lb);InitList_L(lc);cout建立一个有个数据的顺序表La，各节点值依次为：,4,6,8,10,12，.,38,40endl;cout-=1;i-)MakeNode_L(p,2*i);InsFirst_L(la,p);q=la.head-next;while(q)coutsetw(3)data;q=q-next;coutendl;coutendl删除，节点endl;cout-next;while(q)coutsetw(3)data;q=q-next;coutendl;cout-endl;cout表长为：la.lenendl;cout-endl;cout 在第五个结点后插入一个结点endl;cout-next;while(q)coutsetw(3)data;q=q-next;coutendl;cout-endl;cout分别查找值为,45的元素endl;cout-endl;LocateElem_L(la,28,s);LocateElem_L(la,45,s);cout-endl; cout建立线性表Lb，各结点值依次为：endl; cout3,8,13,18,23,28,33,38,43,48,53,58,63,68,73,78endl;cout-=0;i-)MakeNode_L(p,i*10+8);InsFirst_L(lb,p);MakeNode_L(p,i*10+3);InsFirst_L(lb,p);q=lb.head-next;while(q)coutsetw(3)data;q=q-next;coutendl;cout-endl;cout将La和Lb合并为线性表Lcendl;cout-next;cout-endl;cout输出La，Lb，Lc的以及各表的表长endl;cout-endl;while(q)coutsetw(3)data;q=q-next;coutnext;while(q)coutsetw(3)data;q=q-next;coutendl;q=lc.tail;while(q)coutsetw(3)data;q=PriorPos_L(lc,q);coutendl; cout-endl;cout清空线性表La，Lb；输出La，Lb的表长endl;cout-endl;coutla.lenendllb.lenendllc.lenendl;ClearList_L(la);coutla.lenendl;ClearList_L(lb);coutlb.lenendl;return 0;【实验小结】举例说明求解什么样的问题用顺序存储，什么样的问题用链式存储较好？答:使用顺序存储结构的情况: (1)空间利用率较高； (2)存取某个元素速度快； (3)插入元素和删除元素存在元素移动,速度慢,耗时； (4)有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现溢出问题.当元素个数远少于预先分配的空间时,空间浪费巨大。在存取元素频繁,但删除或插入操作较少的情况宜用顺序表。例如建立一个班学生的资料，一般学生人数变动较少，而对资料的调用较多，股宜用顺序表。使用链式存储结构的情况： (1)占用额外的空间以存储指针(浪费空间)； (2)存取某个元素速度慢； (3)插入元素和删除元素速度快； (4)没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关。【源代码说明】1 文件名：.cpp2 操作说明：只需使用visual c+6.0软件将其打开，点击运行即可！- 11 -