数据结构单链表

1、实验一 单链表一、实验目的1、掌握用Vc+上机调试程序的基本方法；2、掌握单链表的建立、插入、删除以及相关操作。二、 实验内容1、单链表的插入算法；2、单链表的删除算法；3、两个有序单链表合并成一个有序单链表的算法。三、实验要求1、学生用C+/C完成算法设计和程序设计并上机调试通过；2、撰写实验报告，提供实验测试数据和实验结果；3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度， 并简要给出算法设计小结和心得。四、实验准备1、复习 C 语言中指针的用法，特别是结构体的指针的用法；2、了解单链表的概念，单链表的定义方法；3、掌握线性表在链式存储结构上实现基本操作：查找、插入、删

2、除的算法； 在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要注意以 下内容： 在实现查找的时候，首先要判断该单链表是否为空，其次要判断查找后的结果 ( 查到时输出查到的数据，未查到时给出错误提示 ) 。在实现插入的时候，由于是链式存储，它可以随机产生和回收存储空间，所以 它不要判断线性表是否为满， 但仍需判断要插入的位置是否合法， 其次要注意插 入的时候语句的顺序不可颠倒，否则出错。在实现删除的时候，首先要判断线性表是否为空，为空则不能删除；其次在删 除后要回收空间。五、实验步骤1 、编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素5(1) 通过键盘读取元素建立单链表

3、；(2) 指定一个位置，在此位置之前插入一个新元素；(3) 指定一个位置，删除此位置元素。2、两个有序单链表合并成一个有序单链表的算法。(1) 通过键盘读取元素建立 2 个有序单链表；(2) 将二两个有序单链表合并成一个有序单链表；(3) 输出合并后的单链表。六、实验参考代码 1、编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素 #include stdio.h#include stdlib.h#define OK 1#define ERROR 0typedef int ElemType;typedef int Status;typedef struct Lnode ElemTyp

4、e data;struct Lnode *n ext;Lno de,*Li nkList;/以下是建立单链表void CreatList_L(Li nkList &head) Lin kList tail, p;int n,i;p=(L node *)malloc(sizeof(L no de);head=tail=p;head- next=NULL;prin tf(Please in put len gth to creat a list:n);sca nf(%d, &n);prin tf(Please in put a group of values of the list:n); for

5、(i=1;idata);p- next=NULL;tail-n ext=p;tail=p;printf(A list has bee n created successfully! n);/以下是输出单链表void OutputList_L(L in kList L)Lin kList p = L-n ext;if(p=NULL)prin tf(n No listn);return;prin tf(The list is:n ”);while (p ) prin tf(%4d,p-data);p = p_n ext;prin tf(n);/在第i个元素之前插入一个元素Status List I

6、n sert_L(L in kList L, int i, ElemType e) Lin kList p,s;p=L;int j=0;while(p&jn ext; +j; if(!p|ji-1) return ERROR;s=(Li nkList)malloc(sizeof(L no de);s-data=e;s-n ext=p-n ext;p_n ext=s;return OK;/删除第i个元素Status ListDelete_L(LinkList L, int i, ElemType &e) Lin kList p,q;p=L;int j=0;while(p- next&jn ext

7、;+j;if(!(p- next)|ji-1) return ERROR;q=p-n ext;p-n ext=q _n ext;e=q_data;free(q);return OK;void mai n() Lin kList L;int choice,i;ElemType e;choice=1;prin tf(We should create a list first!);CreatList_L(L);OutputList_L(L); while(choice!=0) prin tf(n menu n);prin tf( 1 insert a elem );printf( 2 delete

8、a elem );printf( 3 output a list);printf(” 4 exit );printf(nn);prin tf(please choice ( 1,2, 3, 4);sca nf(%d,&choice);if(choice=0) break;else if(choice=1) prin tf(Please in put a pos and a value what you want to in sert: n ”)； scanf(%d%d, &i,&e);if(List In sert_L(L,i,e)prin tf(The in sert ing acti on

9、 has bee n don e!n);OutputList_L(L);else prin tf(The in sert ing pos is error! please do aga in !n);else if (choice=2)prin tf(Please in put a pos what you want to delete:n);sca nf(%d, & i);if(ListDelete_L(L,i,e)printf(The deleting action has been done, the deleted value is %dn,e);OutputList_L(L);els

10、e prin tf(The pos what you want to delete is error! please do aga in!n ”)；else if (choice=3)OutputList_L(L); else if(choice!=0)prin tf(choice errorn);2、两个有序单链表合并成一个有序单链表的算法。实现提示：程序需要3个指针：pa,pb,pc,其中pa, pb分别指向La表、Lb表的首结点，用pa遍历La 表，pb遍历Lb表，pc指向合并后的新表的最后一个结点(即尾结点)，pc的初值指向La表的头8结点。合并的思想是：先建立好两个链表La表和Lb表

11、，然后依次扫描La和Lb中的元素，比较当前元素的值，将较小者链到*pc之后，如此重复直到La或Lb结束为止，再将另一个链表余下的内容链到pc所指的结点之后。#i nclude stdio.h#in clude stdlib.htypedef int ElemType;typedef struct Lnode ElemType data;struct Lnode *n ext;Lno de,*Li nkList;/以下是建立单链表void CreatList_L(Li nkList &head) Lin kList tail, p;int n,i;p=(L node *)malloc(sizeo

12、f(L no de);head=tail=p;head- next=NULL;prin tf(Please in put len gth to creat a list:n);sca nf(%d, &n);prin tf(Please in put a group of values of the list:n);for(i=1;idata);p- next=NULL;tail-n ext=p;tail=p;printf(A list has bee n created successfully! n);/以下是输出单链表void OutputList_L(L in kList L)Lin k

13、List p = L-n ext;if(p=NULL)prin tf(n No listn);return;prin tf(The list is:n ”);while (p ) prin tf(%4d,p-data);p = p_n ext;prin tf(n);/以下将La和Lb表合并为Lc表void MergeList(LinkList &Lc, LinkList &La, LinkList &Lb) Lin kList pa, pb, pc;pa=La-n ext; pb=Lb-n ext;Lc=pc=La;while (pa&pb)if (pa-datadata)pc-n ext=pa;pc=pa;pa=pa-n ext;else pc- n ext=pb;pc=pb;pb=pb-n ext;pc-n ext=pa?pa:pb;free(Lb);/以下是主程序void mai n() Lin kList La,Lb,Lc;prin tf(We should create two in creme ntal and orderly lists first!n);prin tf(please creat a in creme ntal and orderly list An