实验一单链表
一、实验目的
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 "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int 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", &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 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 ) {
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 kList p,s;
p=L;
int j=0;
while(p&&j{ 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-> next&&jp=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(choice!=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("\n---------------------------------------------------------------------------- \n");
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 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 %d\n",e);
