数据结构单链表

实验一 单链表一、实验目的1、掌握用Vc++上机调试程序的基本方法；2、掌握单链表的建立、插入、删除以及相关操作。二、实验内容1、单链表的插入算法；2、单链表的删除算法；3、两个有序单链表合并成一个有序单链表的算法。三、实验要求1、学生用C++/C完成算法设计和程序设计并上机调试通过；2、撰写实验报告，提供实验测试数据和实验结果；3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、实验准备1、复习C语言中指针的用法，特别是结构体的指针的用法；2、了解单链表的概念，单链表的定义方法；3、掌握线性表在链式存储结构上实现基本操作：查找、插入、删除的算法；在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要注意以下内容：在实现查找的时候，首先要判断该单链表是否为空，其次要判断查找后的结果(查到时输出查到的数据，未查到时给出错误提示)。在实现插入的时候，由于是链式存储，它可以随机产生和回收存储空间，所以它不要判断线性表是否为满，但仍需判断要插入的位置是否合法，其次要注意插入的时候语句的顺序不可颠倒，否则出错。在实现删除的时候，首先要判断线性表是否为空，为空则不能删除；其次在删除后要回收空间。五、实验步骤、编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素5通过键盘读取元素建立单链表；指定一个位置，在此位置之前插入一个新元素；指定一个位置，删除此位置元素。2、两个有序单链表合并成一个有序单链表的算法。通过键盘读取元素建立2个有序单链表；将二两个有序单链表合并成一个有序单链表；输出合并后的单链表。六、实验参考代码 1、编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素 #include"stdio.h"#include"stdlib.h"#defineOK1#defineERROR0typedefintElemType;typedefintStatus;typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;//以下是建立单链表voidCreatList_L(LinkList&head){LinkListtail,p;intn,i;p=(Lnode*)malloc(sizeof(Lnode));head=tail=p;head->next=NULL;printf("Pleaseinputlengthtocreatalist:\n");scanf("%d",&n);printf("Pleaseinputagroupofvaluesofthelist:\n");for(i=1;i<=n;i++){p=(Lnode*)malloc(sizeof(Lnode));scanf("%d",&p->data);p->next=NULL;tail->next=p;tail=p;}printf("Alisthasbeencreatedsuccessfully!'n");}//以下是输出单链表voidOutputList_L(LinkListL){LinkListp=L->next;if(p==NULL){printf("\nNolist'n");return;}printf("Thelistis:\n ”);while(p){printf("%4d",p->data);p=p_>next;}printf("\n");}//在第i个元素之前插入一个元素StatusListInsert_L(LinkListL,inti,ElemTypee){LinkListp,s;p=L;intj=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(Lnode));s->data=e;s->next=p->next;欢迎下载 2p_>next=s;returnOK;}//删除第i个元素StatusListDelete_L(LinkListL,inti,ElemType&e){LinkListp,q;p=L;intj=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;q=p->next;p->next=q_>next;e=q_>data;free(q);returnOK;}voidmain(){LinkListL;intchoice,i;ElemTypee;choice=1;printf("Weshouldcreatealistfirst!");CreatList_L(L);OutputList_L(L);while(choice!=0){printf("\nmenu\n");printf("1insertaelem");printf("2deleteaelem");printf("3outputalist");printf(”4exit");printf("\n----------------------------------------------------------------------------\n");printf("pleasechoice(1,2,3,4)");scanf("%d",&choice);if(choice==0)break;elseif(choice==1){printf("Pleaseinputaposandavaluewhatyouwanttoinsert:\n；”)scanf("%d%d",&i,&e);if(ListInsert_L(L,i,e)){printf("Theinsertingactionhasbeendone!\n");OutputList_L(L);}elseprintf("Theinsertingposiserror!pleasedoagain!\n");}elseif(choice==2){printf("Pleaseinputaposwhatyouwanttodelete:\n");scanf("%d",&i);if(ListDelete_L(L,i,e)){printf("Thedeletingactionhasbeendone,thedeletedvalueis%d\n",e);欢迎下载 3OutputList_L(L);}elseprintf("Theposwhatyouwanttodeleteiserror!pleasedoagain!\n；”)}elseif(choice==3){OutputList_L(L);}elseif(choice!=0)printf("choiceerror\n");}}2、两个有序单链表合并成一个有序单链表的算法。实现提示：程序需要3个指针：pa,pb,pc,其中pa, pb分别指向La表、Lb表的首结点，用 pa遍历La表，pb遍历Lb表，pc指向合并后的新表的最后一个结点 (即尾结点)， pc的初值指向La表的头8结点。合并的思想是：先建立好两个链表 La表和Lb表，然后依次扫描 La和Lb中的元素，比较当前元素的值，将较小者链到 *pc之后，如此重复直到 La或Lb结束为止，再将另一个链表余下的内容链到pc所指的结点之后。#include"stdio.h"#include"stdlib.h"typedefintElemType;typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;//以下是建立单链表voidCreatList_L(LinkList&head){LinkListtail,p;intn,i;p=(Lnode*)malloc(sizeof(Lnode));head=tail=p;head->next=NULL;printf("Pleaseinputlengthtocreatalist:\n");scanf("%d",&n);printf("Pleaseinputagroupofvaluesofthelist:\n");for(i=1;i<=n;i++){p=(Lnode*)malloc(sizeof(Lnode));seanf("%d",&p->data);p->next=NULL;tail->next=p;tail=p;}欢迎下载 4printf("Alisthasbeencreatedsuccessfully!'n");}//以下是输出单链表voidOutputList_L(LinkListL){LinkListp=L->next;if(p==NULL){printf("\nNolist'n");return;}printf("Thelistis:\n ”);while(p){printf("%4d",p->data);p=p_>next;}printf("\n");}//以下将La和Lb表合并为Lc表voidMergeList(LinkList&Lc,LinkList&La,LinkList&Lb){LinkListpa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;free(Lb);}//以下是主程序voidmain(){LinkListLa,Lb,Lc;printf("Weshouldcreatetwoincrementalandorderlylistsfirst!\n");printf("pleasecreataincrementalandorder