线性表操作实验报告(共14页)

1、精选优质文档-倾情为你奉上忻州师范学院计算机科学与技术系实 验 报 告（第六组）组长：梁启超组员：晋丹丹 张艳华马军 刘雪梅孙钰林 刘涛忻州师范学院计算机科学与技术系实验报告实验名称 线性表的操作 专业班级 计本1504班 姓名 梁启超 学号 6 指导教师 成绩 日期 2016/9/26 组员分工 晋丹丹（头插法构造单链表），张艳华（尾插法构造单链表;） 马军（遍历单链表;）刘雪梅（按位序查找单链表;）孙钰林（按值查找 单链表;） 刘涛（向单链表中插入元素;） 一、实验目的熟练掌握线性表的类型定义方法、存储方法及其基本运算（元素的插入、删除等）的实现方法，培养综合运用所学知识，根据具体问题进行

2、数据结构设计和算法设计的能力。二、实验内容用链表建立线性表，并进行线性表相关操作。要求：要有良好的人机界面，有菜单形式实现，具备头插法、尾插法建链表、插入、删除、显示、以及按值与位序查找的功能。三、实验要求1在问题分析的基础上选择合适的存储结构，进行算法设计，编制程序并上机调试成功。2按要求完成实验报告。3保存和打印出程序的运行结果，并结合程序进行分析。四、实验步骤1需求分析本演示程序用C语言编写，要有良好的人机界面，实现线性表操作的基本功能：头插法、尾插法建链表、插入、删除、显示、以及按值与位序查找的功能。1输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除

3、元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数。 2输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。 3程序所能达到的功能：完成单链表的生成、插入、删除、查找操作 4测试数据2概要设计 1为了实现上述程序功能，需要定义单链表的抽象数据类型：（1）createlist_l 初始化：头插法构造单链表；（2）createlist_l2初始化：尾插法构造单链表；两种二选一； （2）listinsert_l 操作结果：向单链表中插入元素;（3）listdelete_l操作结果：删除单链表中的元

4、素;（4）printlist_l 操作结果：遍历单链表;（5）getelem_l操作结果：按位序查找单链表; （6）locateElem_l操作结果按值查找单链表;各函数间关系如下:main()linklist/单链表结构scan()createlist_l listinsert_l listdelete_l printlist_l getelem_l locateElem_lcreatelist_l23详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。单链表定义typedef struct lnodeint data;struct l

5、node *next;lnode,*linklist;单链表的生成、插入、删除、查找操作linklist createlist_l(int n) int i; linklist l,p; l=(linklist)malloc(sizeof(lnode); l->next=NULL; printf("please input the data of :"); for(i=n;i>0;-i) p=(linklist)malloc(sizeof(lnode); scanf("%d",&p->data); p->next=l-&g

6、t;next;l->next=p; return l;linklist createlist_l2(int n) int i; linklist l,p,r; l=(linklist)malloc(sizeof(lnode); l->next=NULL;r=l; printf("please input the data of:"); for(i=1;i<=n;i+) p=(linklist)malloc(sizeof(lnode); scanf("%d",&p->data); p->next=NULL;r->

7、next=p;r=p;return l;linklist listinsert_l(linklist l,int i,int e) int j; linklist p,s; p=l;j=0; while(p&&j<i-1)p=p->next;+j; if(!p|j>i-1)printf("data is not lefal!"); s=(linklist)malloc(sizeof(lnode); s->data=e;s->next=p->next; p->next=s; return l;linklist list

8、delete_l(linklist l,int i,int &e)int j; linklist p,q; p=l;j=0; while(p->next&&j<i-1)p=p->next;+j; if(!(p->next)|j>i-1)printf("data is note legal!"); q=p->next;p->next=q->next;e=q->data;free(q);return l;void printlist_l(linklist l) linklist p; printf(&

9、quot;the data of L is:n"); for(p=l->next;p!=NULL;p=p->next) printf("%d",p->data); printf("n");int getelem_l(linklist l,int i) linklist p; int j,e; p=l->next;j=1; while(p&&j<i) p=p->next;+j; if(!p|j<i)return -1; e=p->data; return e;int locateEl

10、em_l(linklist l,int e) linklist p=l->next; int j=1;while(p&&p->data!=e)p=p->next;j+;if(!p) return -1;else return j;4调试分析1)分析算法的总体结构，分清程序中各部分应实现的功能；2)调试方法通常有二种：总体调试、分块调试。你主要采用哪种调试方法？ 总体调试：把算法组装成单个程序，按C程序结构标准分层检查调试； 分块调试：把算法分拆成几个功能模块，按C程序结构标准分模块调试；3)错误跟踪有两种方法：错误信息排查法、执行路线跟踪法。 错误信息排查法：

11、根据错误信息进行分类排查，要求分析者对C的错误代码要有足够的了解和认识，有经验的程序员多用此法。 执行路线跟踪法：变量分析法（跟踪变量的值）、插入标签法（插入输出标签），这种方法适合初学者。4）调试分析不宜面面俱到，具体写出关键问题就行。分析如下：主函数main()首先调用显示操作菜单函数scan()，再根据用户输入的数字选项分别调用以下函数：（1）createlist_l头插法构造单链表；（2）createlist_l2尾插法构造单链表；两种二选一； （2）listinsert_l向单链表中插入元素;（3）listdelete_l删除单链表中的元素;（4）printlist_l遍历单链表;（

12、5）getelem_l按位序查找单链表; （6）locateElem_l按值查找单链表; 由上述结构可知，采用分功能模块调试的方法较合理，即主要功能按以下顺序实现：添加查找删除遍历。5使用说明与测试结果程序名为TXL.exe，运行环境为DOS。程序执行后显示 （下图为参考截图例子。）第一次操作需选择1或者2，并且只能选择一种。程序执行显示我们选择的的是头插法构造单链表，输入1后显示要输入几个数1我们写5个请输入要插入的数据：我们插入15 25 35 45 55 遍历单链表删除表中第2个元素在第3个元素中插入68按位序查找单链表;查找第4个元素五、实验总结（调试和运行程序过程中产生的问题及采取的

13、措施；对算法的程序的讨论、分析，改进设想以及其它经验教训；对实验方式、组织、设备、题目的意见和建议等）附源程序清单：#include<stdio.h>#include<stdlib.h> typedef struct lnodeint data;struct lnode *next;lnode,*linklist; linklist createlist_l(int n) int i; linklist l,p; l=(linklist)malloc(sizeof(lnode); l->next=NULL; printf("please input th

14、e data of :"); for(i=n;i>0;-i) p=(linklist)malloc(sizeof(lnode); scanf("%d",&p->data); p->next=l->next;l->next=p; return l;linklist createlist_l2(int n) int i; linklist l,p,r; l=(linklist)malloc(sizeof(lnode); l->next=NULL;r=l; printf("please input the data

15、of:"); for(i=1;i<=n;i+) p=(linklist)malloc(sizeof(lnode); scanf("%d",&p->data); p->next=NULL;r->next=p;r=p;return l;linklist listinsert_l(linklist l,int i,int e) int j; linklist p,s; p=l;j=0; while(p&&j<i-1)p=p->next;+j; if(!p|j>i-1)printf("data i

16、s not lefal!"); s=(linklist)malloc(sizeof(lnode); s->data=e;s->next=p->next; p->next=s; return l;linklist listdelete_l(linklist l,int i,int &e)int j; linklist p,q; p=l;j=0; while(p->next&&j<i-1)p=p->next;+j; if(!(p->next)|j>i-1)printf("data is note le

17、gal!"); q=p->next;p->next=q->next;e=q->data;free(q);return l;void printlist_l(linklist l) linklist p; printf("the data of L is:n"); for(p=l->next;p!=NULL;p=p->next) printf("%d",p->data); printf("n");int getelem_l(linklist l,int i) linklist p; i

18、nt j,e; p=l->next;j=1; while(p&&j<i) p=p->next;+j; if(!p|j<i)return -1; e=p->data; return e;int locateElem_l(linklist l,int e) linklist p=l->next; int j=1;while(p&&p->data!=e)p=p->next;j+;if(!p) return -1;else return j;int scan()int d ; printf(" n");

19、 printf(" 请选择所要进行的操作，注意头插法与尾插法建链表。 n"); printf(" 1.头插法构造单链表; n"); printf(" 2.尾插法构造单链表; n"); printf(" 3.遍历单链表; n"); printf(" 4.按位序查找单链表; n"); printf(" 5.按值查找单链表; n"); printf(" 6.向单链表中插入元素; n"); printf(" 7.删除单链表中的元素; n");

20、printf(" n"); printf("n"); scanf("%d",&d);return (d);void main()int quit=0,n,i,e; linklist l; printf(" 单链表基本操作 n"); printf(" n"); printf("第一次操作需选择1或者2，并且只能选择一种。 第6小组n"); while(!quit) switch(scan() case 1:printf("please input n:"); scanf("%d",&n); l=createlist_l(n);break; case 2:printf("please input n:"); scanf("%d",&n); l=createlist_l2(n);break; case 3:printf("当前链表中元素为:n"); printlist_l(l); break; case 4:printf("请输入要