数据结构单链表

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

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

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

4、nt Status;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(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&

5、quot;, &n);prin tf("Please in put a group of values of the list:n"); for(i=1;i<=n; i+) p= (Lnode *)malloc(sizeof(L no de);scanf("%d", &p->data);p-> next=NULL;tail->n ext=p;tail=p;printf("A list has bee n created successfully!' n");/以下是输出单链表void O

6、utputList_L(L in kList L)Lin kList p = L->n ext;if(p=NULL)prin tf("n No list'n");return;prin tf("The list is:n ” );while (p ) prin tf("%4d",p->data);p = p_>n ext;prin tf("n");/在第 i 个元素之前插入一个元素Status List In sert_L(L in kList L, int i, ElemType e) Lin k

7、List p,s;p=L;int j=0;while(p&&j<i-1) p=p->n ext; +j; if(!p|j>i-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-> ne

8、xt&&j<i-1)p=p->n ext;+j;if(!(p-> next)|j>i-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(cho

9、ice!=0) prin tf("n menu n");prin tf(" 1 insert a elem ");printf(" 2 delete 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) brea

10、k;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 has bee n don e!n");OutputList_L(L);else prin tf("The in sert ing pos is error! please do

11、 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);else prin tf("The pos what you want to d

12、elete 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 表，然后依次扫描L

13、a 和 Lb 中的元素，比较当前元素的值，将较小者链到*pc 之后，如此重复直到La 或 Lb 结束为止，再将另一个链表余下的内容链到 pc 所指的结点之后。#i nclude "stdio.h"#in clude "stdlib.h"typedef 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

14、 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(i=1;i<=n; i+)p= (Lnode *)malloc(sizeof(L no de);seanf("%d

15、", &p->data);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 list'n"); return;prin tf("The list is:n ” );while (p ) pri

16、n 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->data<=pb->data)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