实验二 单链表基本操作的实现Word文件下载.docx

1、#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType; Link head,tail; int len;Position MakeNode_L（Link &p,ElemType e） /创建结点 p=（Link）malloc（sizeof（LNode）; if（!p） return ERROR; p-data=e;next=NULL; return p;void FreeNode_L（Link &q） /释放结点 free（q）;Status InitList_L（LinkList &L）

2、 /初始化L为一个带头结点的空链表,头尾指针指向头结点，表长赋 ElemType e; e=-1;/实际应用中此初始化语句需要修改MakeNode_L（L.head,e）return ERROR;/开辟头结点 L.tail=L.head;L.len=0; return OK;/InitList_LStatus DestroyList_L（LinkList &L）/销毁链表L Link p; while（p=L.head-next）/依次释放有序链表中第一个元素至最后一个元素所占用空间; L.head-next=p-next; free（p）; free（L.head）; L.head=NULL

3、;L.tail=NULL; coutendl while（p） q=p- p=q; L.len=0;Status InsFirst_L（LinkList &L,Link s） /在首元素前插入一个结点 s-next=L.head-L.head-next） L.tail=s; L.head-next=s; L.len+;Status DelFirst_L（LinkList &L,Link h,Link &q） /删除首结点 h=L.head; q=L.head- if（q） h-next=q- q- if（!h- L.tail=h; L.len-; return OK; else return

4、ERROR;Status Append_L（LinkList &L,Link s） /将两个链表跟一个字符串连接起来 Link q;next=q=s; L.tail- while（q- q=q- L.tail=q;Position Remove_L（LinkList &L,Link &q） /删除尾结点 p=L.head;next） coutnext!=L.tail） p=p- q=L.tail; L.tail=p; return q;Status InsBefore_L（LinkList &p,Link s） /在p指向的结点前插入一个结点 q=L.head; if（p=L.head） co

5、ut=p） q=q- s-next=p;Status InsAfter_L（LinkList &p,Link s） /在p指向的结点后插入一个结点 if（p=L.tail） L.tail=s;Status SetCurElem_L（Link &p,ElemType e） /改变p指向的结点的内容ElemType GetCurElem_L（Link p） /获取p指向的结点的内容 return p-data;int ListLength_L（LinkList L） /获取单链表的长度值 return L.len;Status ListEmpty_L（LinkList L） /判断单链表是否为空，

6、是返回，否返回 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的前驱 if（p=L.head-next） return NULL;Position NextPos_L（LinkList L,Link p） /获取p的后继p-Status Lo

7、catePos_L（LinkList L,int i,Link &p） /查找p在单链表中的位置i int j; if（i1） return ERROR; for（j=1;jStatus compare（ElemType x,ElemType y） /比较函数 if（x=y） return 1; return 0;Status LocateElem_L（LinkList L,ElemType e,Link &p） /返回跟e相同的值，没有的话返回空指针 int i=0; do i+; while（p&!compare（p-data,e）; if（p） couti visit（p-data）;S

8、tatus ListInsert_L（LinkList &L,int i,ElemType e） /在第i个位置后插入一个元素 Link p,s; s=（Link）malloc（sizeof（LNode）;Status ListDelete_L（LinkList &L,int i） /删除第i个元素的结点 if（iL.len） return ERROR;i-1;next- L.len-;Status MergeList_L（LinkList La,LinkList Lb,LinkList &Lc） /将两个字符串连接起来 Link p,q,t; p=La.head- q=Lb.head- wh

9、ile（p&q） if（p-datadata） MakeNode_L（t,p- InsFirst_L（Lc,t）; else MakeNode_L（t,q- while（p） MakeNode_L（t,p- InsFirst_L（Lc,t）; while（q） MakeNode_L（t,q-【测试数据及实验结果】int main（） LinkList la,lb,lc; Link p,q,s,k,t; InitList_L（la）; InitList_L（lb）; InitList_L（lc）;建立一个有个数据的顺序表La，各节点值依次为：,4,6,8,10,12，.,38,40- for（i

10、nt i=20;i=1;i-） MakeNode_L（p,2*i）; InsFirst_L（la,p）; q=la.head-setw（3）删除，节点- ListDelete_L（la,8）; ListDelete_L（la,30）;表长为：la.len将La和Lb合并为线性表Lc MergeList_L（la,lb,lc）;输出La，Lb，Lc的以及各表的表长 coutq=lc.tail;while（q）coutq=PriorPos_L（lc,q）;清空线性表La，Lb；输出La，Lb的表长lb.lenlc.len ClearList_L（la）; ClearList_L（lb）; retu

11、rn 0;【实验小结】举例说明求解什么样的问题用顺序存储，什么样的问题用链式存储较好？答:使用顺序存储结构的情况: （1）空间利用率较高； （2）存取某个元素速度快； （3）插入元素和删除元素存在元素移动,速度慢,耗时； （4）有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现溢出问题.当元素个数远少于预先分配的空间时,空间浪费巨大。在存取元素频繁,但删除或插入操作较少的情况宜用顺序表。例如建立一个班学生的资料，一般学生人数变动较少，而对资料的调用较多，股宜用顺序表。使用链式存储结构的情况： （1）占用额外的空间以存储指针（浪费空间）； （2）存取某个元素速度慢； （3）插入元素和删除元素速度快； （4）没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关。【源代码说明】1文件名：.cpp2操作说明：只需使用visual c+6.0软件将其打开，点击运行即可！