实验二_单链表的实现及测试.doc

上海电力学院计算机软件技术实验实验报告 实验题目： 单链表的实现及测试院系： 自动化工程学院 专业年级： 自动化2013级 学生姓名： 晁文涛 学号20131529实验二 单链表的基本算法一 实验目的：通过上机编程掌握1生成单链表的基本算法；2 在单链表上的插入、删除运算。二 实验要求：1. 给出程序设计的基本思想、原理和算法描述。2. 画出程序流程图；根据数据结构有关知识编出算法程序； 3. 源程序给出注释；4. 保存和打印出程序的运行结果，并结合程序进行分析。三 实验内容：1. 编写函数实现单链表的基本运算： (1) 单链表的生成反向建立链表（头插法）思想：首先生成头结点，形成一个空链表，然后在表中逐一读入新的结点，反复执行下列步骤：使用malloc函数开辟新结点的存储单元；将读入数据存放到新结点的数据域中；将新结点插入到当前链表的表头上，直到读入结束标志为止。流程图为：具体算法如下：NODE *creatlink1()/头插法NODE *head,*s;int x;head=(NODE*)malloc(sizeof(NODE);/生成头结点head-next=NULL;scanf(%d,&x);/读入第一个结点值while(x!=0)s=(NODE*)malloc(sizeof(NODE);s-data=x;s-next=head-next;head-next=s;/将新节点插入到表头上scanf(%d,&x);return head;正向建立单链表（尾插法）思想：首先生成头结点，依次读入线性表的元素，从前往后依次将元素插入到当前链表的最后一个结点之后。流程图为：具体算法为：NODE *creatlink2()/尾插法NODE *head,*p,*s;int num;head=(NODE*)malloc(sizeof(NODE);/生成头结点scanf(%d,&num);/读入第一个结点值p=head;/头指针等于尾指针while (num!=0)/输入0作为结束符s=(NODE*)malloc(sizeof(NODE);/生成新节点s-data=num;/新结点上填入输入值p-next=s; /新结点*s插入到尾结点*p之后p=s;/尾指针指向新的表尾scanf(%d,&num); /读入下一个结点值p-next=NULL;/将尾结点的指针置空return head;/返回单链表表头指针（2）单链表的插入思想：首先要搜索单链表以找到指定插入结点的前趋结点p；然后改变链接，即只要是将待插入结点的指针域内容赋予p结点的指针域即可。流程图为：具体算法为：NODE *get(NODE *head,int i) /查找第i个元素的位置NODE *p;int counter=1;p=head-next;while(p!=NULL)&(counternext;counter+;if(p!=NULL)&(counter=i)/找到，1=in或idata=x;s-next=p-next;p-next=s;void insert(NODE *head,int i,int x)/在i个位置插入xNODE *p;int j=i-1;p=get(head,j);/调用查找函数找到i-1的结点位置if(p=NULL)printf(error);else insertafter(p,x);/调用insertafter函数(2) 单链表的删除思想：首先要搜索单链表以找到指定删除结点的前趋结点p；然后改变链接，即只要是将待删除结点的指针域内容赋予p结点的指针域即可。流程图为：具体算法为：void delete(NODE *head,int i) /删除第i个位置的元素NODE *p,*s;int j=0;p=head;while(p-next!=NULL)&(jnext;j+;if(p-next=NULL)|(ji-1)printf(i值不合法 n);elses=p-next;/修改p-next，使指向s-nextp-next=s-next;/删除s结点free(s);2. 编写主函数测试单链表的各种基本运算：(1) 生成一个至少包含有5个元素的单链表,元素值由计算机输入(2) 在表中的第5个位置上插入元素”7”(3) 删除表中的第6个元素(4) 显示(1)(3)每一步的操作结果源程序为：#include #include typedef int datatype;typedef struct node datatype data; struct node *next;NODE;NODE *creatlink1()/头插法NODE *head,*s;int x;head=(NODE*)malloc(sizeof(NODE);/生成头结点head-next=NULL;scanf(%d,&x);/读入第一个结点值while(x!=0)s=(NODE*)malloc(sizeof(NODE);s-data=x;s-next=head-next;head-next=s;/将新节点插入到表头上scanf(%d,&x);return head;NODE *creatlink2()/尾插法NODE *head,*p,*s;int num;head=(NODE*)malloc(sizeof(NODE);/生成头结点scanf(%d,&num);/读入第一个结点值p=head;/头指针等于尾指针while (num!=0)/输入0作为结束符s=(NODE*)malloc(sizeof(NODE);/生成新节点s-data=num;/新结点上填入输入值p-next=s;/新结点*s插入到尾结点*p之后p=s;/尾指针指向新的表尾scanf(%d,&num); /读入下一个结点值p-next=NULL;/将尾结点的指针置空return head;/返回单链表表头指针NODE *get(NODE *head,int i) /查找第i个元素的位置NODE *p;int counter=1;p=head-next;while(p!=NULL)&(counternext;counter+;if(p!=NULL)&(counter=i)/找到，1=in或inext!=NULL)&(jnext;j+;if(p-next=NULL)|(ji-1)printf(i值不合法 n);elses=p-next;/修改p-next，使指向s-nextp-next=s-next;/删除s结点free(s);void insertafter(NODE *p,int x)NODE *s;s=(NODE*)malloc(sizeof(NODE);/修改i-1结点的尾指针s-data=x;s-next=p-next;p-next=s;void insert(NODE *head,int i,int x)/在i个位置插入xNODE *p;int j=i-1;p=get(head,j);/调用查找函数找到i-1的结点位置if(p=NULL)printf(error);else insertafter(p,x);/调用insertafter函数void print(NODE *head)/输出函数int x; NODE *p; p=head;printf(n);p=p-next; while(p) x=p-data; printf(%4d,x); p=p-next; main() NODE *head; printf(Please enter the link of elements:n);/head=creatlink1();/头插法 head=creatlink2();/尾插法 printf(The first step of is :n); print(head); printf(n); insert(head,5,7);/调用插入函数 printf(The second step of is :n); print(head); printf(n); delete(head,6);/调