实验一单链表
一、实验目的
1、掌握用Vc++上机调试程序的基本方法；
2、掌握单链表的建立、插入、删除以及相关操作。 二、实验内容
1、单链表的插入算法； 2、单链表的删除算法；
3、两个有序单链表合并成一个有序单链表的算法。 三、实验要求
1、学生用C++/C完成算法设计和程序设计并上机调试通过； 2、撰写实验报告，提供实验测试数据和实验结果；
3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度， 并简要给出算法设计小结和心得。 四、实验准备
1、复习C 语言中指针的用法，特别是结构体的指针的用法； 2、了解单链表的概念，单链表的定义方法；
3、掌握线性表在链式存储结构上实现基本操作：查找、插入、删除的算法； 在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要注意以 下内容：
在实现查找的时候，首先要判断该单链表是否为空，其次要判断查找后的结果 (查到时输出查到的数据，未查到时给出错误提示)。
在实现插入的时候，由于是链式存储，它可以随机产生和回收存储空间，所以 它不要判断线性表是否为满，但仍需判断要插入的位置是否合法，其次要注意插 入的时候语句的顺序不可颠倒，否则出错。
在实现删除的时候，首先要判断线性表是否为空，为空则不能删除；其次在删 除后要回收空间。 五、实验步骤
1、编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素
5
(1)通过键盘读取元素建立单链表；
(2)指定一个位置，在此位置之前插入一个新元素； (3)指定一个位置，删除此位置元素。
2、两个有序单链表合并成一个有序单链表的算法。 (1)通过键盘读取元素建立2 个有序单链表； (2)将二两个有序单链表合并成一个有序单链表； (3)输出合并后的单链表。 六、实验参考代码
1、编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素
#include \#include \#define OK 1 #define ERROR 0 typedefintElemType;
typedefint Status; typedefstructLnode { ElemType data; structLnode *next; }Lnode,*LinkList; //以下是建立单链表
voidCreatList_L(LinkList&head) { LinkList tail, p; intn,i;
p=(Lnode *)malloc(sizeof(Lnode)); head=tail=p;
head->next=NULL;
printf(\scanf(\
printf(\for(i=1;i<=n;i++){
p= (Lnode *)malloc(sizeof(Lnode)); scanf(\p->next=NULL; tail->next=p; tail=p; }
printf(\}
//以下是输出单链表
voidOutputList_L(LinkList L){ LinkList p = L->next; if(p==NULL){
printf(\return; }
printf(\while (p ) {
printf(\p = p->next; }
printf(\}
//在第i个元素之前插入一个元素
Status ListInsert_L(LinkList L, inti, ElemType e) { LinkListp,s; p=L; int j=0;
while(p&&j { p=p->next; ++j; } if(!p||j>i-1) return ERROR; s=(LinkList)malloc(sizeof(Lnode)); s->data=e;s->next=p->next; p->next=s; return OK; } // 删除第i个元素 Status ListDelete_L(LinkList L, inti, ElemType&e) { LinkListp,q; p=L; int j=0; while(p->next&&j if(!(p->next)||j>i-1) return ERROR; q=p->next;p->next=q->next; e=q->data;free(q); return OK; } void main() { LinkList L; intchoice,i; ElemType e; choice=1; printf(\CreatList_L(L); OutputList_L(L); while(choice!=0) { printf(\ printf(\printf(\printf(\printf(\ printf(\printf(\scanf(\if(choice==0) break; else if(choice==1) { printf(\scanf(\if(ListInsert_L(L,i,e)){ printf(\OutputList_L(L);}