数据结构实验一-线性表

1、实验一线性表学生姓名吴肖遥学号20151681310131专业班级电子信息5班实验地点理工大楼610实验日期2016.3.21指导教师李红雷实验环境Visual C+6.0实验学时2学时实验类型综合实验成绩一、实验目的1、深刻理解线性结构的特点，以及在计算机内的两种存储结构。2、 熟练掌握线性表的顺序存储结构和链式存储结构，及其它们的基本操作, 重点掌握查找、插入和删除等操作。二、实验要求1、认真阅读程序，将未完成的代码补全（红色部分）。2、上机调试，并运行程序。3、保存和截图程序的运行结果，并结合程序进行分析。三、实验内容和基本原理1、实验1.1顺序表的操作利用顺序表存储方式实现下列功能（见

2、参考程序1）：1）通过键盘输入数据建立一个线性表，并输出该线性表。女口，依次输入元素25,21,46,90,12,98。1&表 运“ 15性tlelWN 20线元元元程“ 普束 肖建结“ 叱. * 一_ = 12340=1性25线一一A.- 0 12 3 4 俞居居居居居居S 59 2三5,1 .入长2）根据屏幕菜单的选择，进行数据的插入、删除和查找，并在插入或删除 数据后，再输出线性表。如，在第 2个位置上插入元素43，然后输出顺序表 删除顺序表第4个元素，输出改变的顺序表。13811316S表15性Mows? 20线元元元程 逓存入專束 n W - 2 3 4 0请输入要执行的操作：2疇炎

3、豔鷄芫當值，43254321469 iB129fi310113询表15性20线元元元程 遥立入靠束 吴1-2 3 4 0请输入要执行的操作：3请输入要删除元素的位置：254321901298删除的元素为=463）在屏幕菜单中选择0,结束程序的运行。基本原理：在顺序表的第i个位置上插入一个元素时，必须先将线性表的第 i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，在把新元素插 入到该位置。当要删除第i个元素时，只需将第i个元素之后的所有元素前移一 个位置。程序代码（蓝色为补充的语句）：/* * * * * * * * * * * * * * * * * * * * * * * *PRO

4、GRAM:顺序结构的线性表*CONTENT:建立,插入,删除,查找*/* 编程语言： Visual c+ 6.0*/* * * * * * * * * * * * * * * * * * * * * *#in clude#in clude数据元素的类型顺序存储的结构体类型#defi ne MAXSIZE 20 typedef int ElemType; / typedef structElemType aMAXSIZE; in t le ngth;SqList;/SqList a,b,c; / 函数声明void creat_list(SqList *L);void out_list(SqLis

5、t L);void insert_sq(SqList *L,int i,ElemType e); ElemType delete_sq(SqList *L,int i);int locat_sq(SqList L,ElemType e);/ 主函数void main()int i,k,loc;ElemType e,x; char ch; do printf(nnn); printf(n printf(n 1. printf(n 2. printf(n 3. printf(n 4. printf(n 0. printf(n = printf(n scanf(%d,&k); switch(k) c

6、ase 1:creat_list(&a);吴肖遥 20151681310131); 建立线性表 ); 插入元素 ); 删除元素 ); 查找元素 ); 结束程序运行 ); =); 请输入要执行的操作 : );out_list(a);break;case 2:printf(n 请输入插入位置： ,a.length+1); scanf(%d,&i);printf( 请输入要插入的元素值： ); scanf(%d,&e);insert_sq(&a,i,e);out_list(a);break;case 3:printf(n 请输入要删除元素的位置： ,a.length); scanf(%d,&i);x

7、=delete_sq(&a,i);out_list(a);if(x!=-1)printf(n 删除的元素为： %dn,x);else printf( 要删除的元素不存在！ ); break;case 4:printf(n 请输入要查找的元素值： ); scanf(%d,&e); loc=locat_sq(a,e);if(loc=-1)printf(n 未找到指定元素！ ); elseprintf(n 已找到，元素的位置是 : %d ,loc); break;/*switch*/while(k!=0);printf(n 按回车键，返回 .n); ch=getchar();/*main*/ 建立线

8、性表void creat_list(SqList *L)int i;printf( 请输入线性表的长度 : ); scanf(%d,&L-length);for(i=0;ilength;i+)printf( 数据 %d =,i);scanf(%d,&(L-ai);/ 输出线性表void out_list(SqList L)int i;for(i=0;ilength=MAXSIZE) printf( 线性表已满 !n);else if(iL-length+1) printf( 输入位置错 !n); else for(j=L-length-1;j=i-1;j-) L-aj+1=L-aj; L-aj

9、+1=e;/* 将未完成的代码补全 , 提示：此处添加一条语句，将被删除的元素值赋给 e*/L-length+;/ 删除第 i 个元素，返回其值ElemType delete_sq(SqList *L,int i)ElemType x;int j;if(L-length=0)printf( 空表 !n);else if(iL-length)printf( 输入位置错！ n); x=-1;else x=L-ai-1; for(j=i;jlength-1;j+) L-aj-1=L-aj;/* 将未完成的代码补全 , 提示：此处添加一条语句，将被删除元素之后的元 素左移。 */L-length-;r

10、eturn(x);/ 查找值为 e 的元素，返回它的位置int locat_sq(SqList L,ElemType e)int i=0;while( L.ai!=e /* 将未完成的代码补全 , 提示：此处添加一条语句 */) i+;if（iv=L.le ngth-1）return（i+1）;2 、实验1.2链表的操作（见参考程序2）禾U用链式存储的方式实现线性表的创建、插入、删除和查找等操作。 1）请输入初始时链表长度，如输入 5。女口，依次输入元素abcdf,然后输出链表。本程序实规链式结构的线性克的操作。 市以进行插人 删除，定位，查找等操作。 请输入初始时链表长度：5请输入5个字符：

11、例如，abcdefgabcdf带表所有元素:f d c b a吴胃遥匸显示所有远素插入一个元素3删除一个元素4. 按关键字查找元素5-按序号查找元素6.退出程序1 _ 错表所有元素:f d c b a_* i f 2）删除一个元素，如输入c请选揑；_1显示所有兀素2. 插入一个元素3. 删除一个元素4. 按关犍字查找元素5. 按序号查找元素6. 退出程序3请输入要删除的元素所在位置:3 成功删除了一个元素乂错表厉有元素:f d b a3）插入一个元素，如输入e吴肖遥 请选择:_1 显示所有西素插入一个元素3. 删除一个元素4. 按关键字查孩元素5 接序号畲找兀素6退出程序2请输入元素（一个字符

12、）和要插入的位置:格式:字符，位置，例如a 3e, 3 埔入成功L槌表所有兀素：f d e b a4）按关键字查找元素。如输入e吴肖遥 请摄捱：_1 显示所有西素2. 插入一个元素3. 删除一个元素4. 按关键字查茨元素5. 擾序号畫找兀素6退出程序4请输入要查找的元素（一个字符）:e 该元素在链表的第扑位置。_、 *_= r5）按序号查找元素。如输入3青选择:_1 显示所有远素 P-插入一个元素 戈删除一个元素L按关键字查找元素 久按序号查找元素6*退也程序；青输営查找的位置：3 第?傅素是：e基本原理：在带头结点的单链表中第i （从1开始计数）个位置之后插入元 素、创建带头结点的单链表、在

13、带头结点的单链表中删除第 i个位置的元素等, 最后输出单链表的内容。程序代码（蓝色为补充部分）：/* * * * * * * * * * * * * * * * * * * * * * * *PROGRAM:链式结构的线性表*CONTENT:生成,插入,删除,定位,查找*/* 编程语言： Visual c+ 6.0*/* * * * * * * * * * * * * * * * * * * * * *#include #include #include #include #define LEN sizeof(LNode) / 定义 LEN为一个 / 节点的长度 enum BOOLFalse,

14、True; / 定义 BOO型typedef struct nodechar data; / 数据域struct node *next;/ 指向下一个节点的指针生成一个 / 单链表在单 / 链表中插入一个元素 在/ 单链表中删除一个元素 &); / 按关键字查找一个元素 /按序号查找一个元素示单链表 / 所有元素LNode,*LinkList;void CreatList(LinkList &,int); / BOOL ListInsert(LinkList &,int,char); / BOOL ListDelete(LinkList &,int,char &); / BOOLListFin

15、d_keyword(LinkList,char,int BOOL ListFind_order(LinkList,char &,int); void ListPrint(LinkList); /显int main() LinkList L;BOOL temp; int num,loc,flag=1; char j,ch;/ 程序解说 printf( 吴肖遥 printf( 本程序实现链式结构的线性表的操作。 n);printf( 可以进行插入，删除，定位，查找等操作。 n);/printf( 请输入初始时链表长度 :); / 输入生成单链表时的元素个数 scanf(%d,&num);Creat

16、List(L,num); /生成单链表ListPrint(L);while(flag) printf(请选择:n);printf(1.printf(2.printf(3.printf(4.printf(5.printf(6.显示链 / 表元素 插入链 / 表元素 删除链 / 表元素显示所有元素 n); / 插入一个元素 n); / 删除一个元素 n); /按关键字查找元素 n); /按/ 关键字查找按序号查找元素 n); / 按序号 / 查找 退出程序 n); /退出scanf( %c,&j);switch(j)case 1:ListPrint(L); break;case 2:printf(

17、 请输入元素 (一个字符)和要插入的位置 :n); printf( 格式: 字符，位置；例如 :a,3n);入的位置temp=ListInsert(L,loc,ch); / 插入 if(temp=False) printf( 插入失败 !n); / 插入失败 else printf( 插入成功 !n); /成 / 功插入ListPrint(L);break;case 3:printf( 请输入要删除的元素所在位置 :); scanf(%d,&loc); / 输入要删除的节点的位置 temp=ListDelete(L,loc,ch); / 删除 if(temp=False) printf( 删除

18、失败 !n); / 删除失败 else printf( 成功删除了一个元素 :%cn,ch); / 删除成功， 显示该元素ListPrint(L);break;case 4:if(L-next=NULL) / 链表为空 printf( 链表为空 !n);elseprintf( 请输入要查找的元素 ( 一个字符 ):);scanf( %c,&ch); / 输入要查找的元素 temp=ListFind_keyword(L,ch,loc); / 按关键字 / 查找 if(temp=False) printf( 没有找到该元素 !n); / 查找 失败else printf(该元素在链表的第并位置。n

19、,loc);/成功查找，显示该元素位置break;case 5:if(L-next=NULL)/链表为空printf( 链表为空 !n);elseprintf( 请输入要查找的位置 :); scanf(%d,&loc); /输入/ 要查找的元素的位置temp=ListFind_order(L,ch,loc); /按序号查找第 d个元素是：cn,loc,ch);成功查找，显示该元素程序结束，按任意键退出 !n);if(temp=False) printf(该位置不存在 !n); / 查找失else printf(/break;default:flag=0;printf(getch();n 个元素

20、的单链表生成头结点void CreatList(LinkList &v,int n)/ 生成一个带头结点的有int i;LinkList p; v=(LinkList)malloc(LEN); / v-next=NULL;abcdefgn,n);生成新结点prin tf(请输入dt字符：例如：getchar();将未完成的代码补全 , 此处添加一条代码for(i=n;i0;-i) p=(LinkList)malloc(LEN); / scanf(%c,&p-data); p-next = v-next;/ v-next=p;e,成功返回/True，失败返回False查找第 /i-1 个元素的位

21、置 没有找到 生成一个新 / 结点BOOL ListInsert(LinkList &v,int i,char e) / 在单链表的第 i 各位置插入元素 LinkList p,s;int j=0; p=v; while(p&jnext;+j; / if(!p|ji-1) return False; / s=(LinkList)malloc(LEN); /s-data=e; s-next=p-next;/ 将未完成的代码补全 , 此处添加一条代码/ 提示：将新结点插入到单链表中,即修改指针,完成插入操作 p-next=s;return True;BOOL ListDelete(LinkList

22、 &v,int i,char &e)/ 在单链表中删除第 i 个元素,成功删除返回 /True ,并用 e 返回该元素 值,失败返回 FalseLinkList p,q;int j=0;p=v; while(p-next&jnext;+j;if(!(p-next)|ji-1) return False; /查找/ 失败q=p-next;p-next=q-next;/* 将未完成的代码补全 , 此处添加一条代码 , 提示：删除该元素 */e=q-data;/* 将未完成的代码补全 , 此处添加一条代码 , 提示 :e 取得该元素值， 即修改 指针，删除结点 q*/free(q); / 释放该元素

23、空间return True;BOOL ListFind_keyword(LinkList v,char e,int &i)/ 在单链表中查找关键字为 e 的元素，成功返回 /True, 并用 i 返回该元素 位置，/ 失败返回 Falsei=1;LinkList p;p=v-next;while(p-data!=e)&(p-next!=NULL)/p指 / 针指向下一个，直到p=p-next; i+; / 找到或到链表尾为 止if(p-data!=e) /该元 / 素在链表中不存在return False;else return True;BOOL ListFind_order(LinkLis

24、t v,char &e,int i)/ 在单链表中查找第 i 个元素，成功返回 True，/ 并用 e 返回该元素值， / 失败返回 FalseLinkList p;int j=0;p=v;while( p!=NULL&jnext;+j;if(j!=i) return False; /查找失败else e=p-data; / 查找成功，用 e 取得 / 该元素值 return True;void ListPrint(LinkList v)/ 显示链表所有元素LinkList q; q=v-next;printf( 链表所有元素 :); while(q!=NULL)printf(%c ,q-da

25、ta);q=q-next; printf(n);四、实验步骤1 、顺序表的操作1 ）运行Visual C+6.0，创建一个C+源文件提示：选择菜单栏中的“文件”下拉菜单中的“新建”按钮，在弹出的对话 框中，选择“文件”子菜单中的“ C/C+Source File ”。选中“Add to project ” 复选框。然后给一个文件名，如“ sy1 ”，并保存在“桌面/姓名学号/”。2 ）将参考程序复制到文档窗口，选择菜单栏中的“组建”下拉菜单中的“编 译”选项，在弹出的对话框中选择“是”。3 ）将未完成的代码补充完整，然后选择菜单中的“组建”下拉菜单中的“执行”，或者直接点击工具栏中的“”进行连

26、接，调试和运行。4 ）运行程序，并检查插入、删除和查找等操作是否有误，正确后截图到word 文档中指定位置。5 *yl Mlcrofcori： VlMal C图1说明：当程序运行错误时，如图2所示，查看组建窗口，双击出错部分（单 击窗口然后滑动查看），逐条更改直到程序运行无误。参考程序1/* * * * * * *PROGRAM *CONTENT /*编程语言：:顺序结构的线性表:建立,插入，删除,查找Visual c+ 6.0*/*#i nclude#i nclude#defi ne MAXSIZE 20typedef int ElemType;/数据元素的类型typedef structE

27、lemType aMAXSIZE;int len gth;SqList;顺序存储的结构体类型SqList a,b,c;函数声明void creat_list(SqList *L);void out_list(SqList L);void in sert_sq(SqList *L,i nt i,ElemType e);ElemType delete_sq(SqList *L,i nt i);int locat_sq(SqList L,ElemType e);/主函数void mai n()int i,k,loc;ElemType e,x;char ch;do prin tf(nnn);print

28、f(n1.建立线性表);printf(n2.插入元素);printf(n3.删除元素);printf(n4.查找元素);printf(n0.结束程序运行);prin tf(n=);printf(n请输入要执行的操作：);sca nf(%d,&k);switch(k)case 1:creat_list(&a); out_list(a);break;case 2:printf(n 请输入插入位置： ,a.length+1); scanf(%d,&i);printf( 请输入要插入的元素值： ); scanf(%d,&e);insert_sq(&a,i,e);out_list(a);break;ca

29、se 3:printf(n 请输入要删除元素的位置： ,a.length); scanf(%d,&i);x=delete_sq(&a,i);out_list(a);if(x!=-1)printf(n 删除的元素为： %dn,x);else printf(要删除的元素不存在！);break;case 4:printf(n 请输入要查找的元素值： );scanf(%d,&e);loc=locat_sq(a,e);if(loc=-1)printf(n 未找到指定元素！ );elseprintf(n 已找到，元素的位置是 : %d ,loc);break;/*switch*/while(k!=0);p

30、rintf(n按回车键，返回 .n);ch=getchar();/*main*/建立线性表void creat_list(SqList *L)int i;printf(请输入线性表的长度：)；scanf(%d,&L-length);for(i=0；ilength；i+)printf( 数据 %d =,i)；scanf(%d,&(L-ai)；/输出线性表void out_list(SqList L)int i;for(i=0;ilength=MAXSIZE)printf(线性表已满!n);else if(iL-length+1)printf( 输入位置错 !n);else for(j=L-len

31、gth-1;j=i-1;j-) L-aj+1=L-aj;e*/* 将未完成的代码补全 ,提示：此处添加一条语句，将被删除的元素值赋给 L-length+;/删除第 i 个元素，返回其值ElemType delete_sq(SqList *L,int i)ElemType x;int j;if(L-length=0)printf(空表!n);else if(iL-length)printf( 输入位置错！ n);x=-1;else x=L-ai-1; for(j=i;jlength-1;j+)/*将未完成的代码补全，提示：此处添加一条语句，将被删除元素之后的元素左移 */L-le ngth-;r

32、eturn(x);查找值为e的元素，返回它的位置int locat_sq(SqList L,ElemType e)int i=0;while(/*将未完成的代码补全，提示：此处添加一条语句*/) i+;if(i#in clude #i nclude #i nclude #define LEN sizeof(LNode) /定义 LEN 为一个 /节点的长度enum BOOLFalse,True; 定义 BOOL 型typedef struct nodechar data;/ 数据域struct n ode *n ext;/指向下一个节点的指针LNode,*Li nkList;void Crea

33、tList(L in kList &,in t);生成一个单链表BOOL ListInsert(LinkList &,int,char); / 在单链表中插入一个元素BOOL ListDelete(LinkList &,int,char &); / 在单链表中删除一个元素BOOL ListFind_keyword(LinkList,char,int &); / 按关键字查找一个元素BOOL ListFi nd_order(Li nkList,char &,in t);按序号查找一个元素void ListPrint(LinkList);/显示单链表所有元素void mai n()LinkList

34、 L;BOOL temp;int num ,loc,flag=1;char j,ch;/ 程序解说 printf( 本程序实现链式结构的线性表的操作。 n); printf( 可以进行插入，删除，定位，查找等操作。 n);/printf( 请输入初始时链表长度 :); / 输入生成单链表时的元素个数 scanf(%d,&num);CreatList(L,num);/ 生成单链表ListPrint(L);while(flag) printf( 请选择 :n);printf(1.显示所有元素n);/显示链表元素printf(2. 插入一个元素 n);/插入链 /表元素printf(3.删除一个元素

35、n);删除链表元素printf(4. 按关键字查找元素 n); /按/关键字查找 printf(5. 按序号查找元素 n); /按序号 /查找 printf(6. 退出程序n);/退出scanf( %c,&j);switch(j)case 1:ListPrint(L); break;case 2:printf(请输入元素(一个字符)和要插入的位置:n); printf( 格式:字符，位置；例如 :a,3n);scanf( %c,%d,&ch,&loc);/输入要插入的元素和要插入的位Itemp=ListInsert(L,loc,ch);/插入if(temp=False) printf( 插入失

36、败 !n); /插入失败 else printf(插入成功!n); /成/功插入 ListPrint(L);break;case 3:pri ntf(请输入要删除的元素所在位置:);scanf(%d,&loc);/输入要删除的节点的位置temp=ListDelete(L,loc,ch);/删除if(temp=False) printf( 删除失败 !n); /删除失败else printf(成功删除了一个元素：cn,ch);删除成功，显示该元素ListPrint(L);break;case 4:if(L-next=NULL)/链表为空printf( 链表为空 !n);elseprintf( 请

37、输入要查找的元素 (一个字符 ):); scanf( %c,&ch);/输入要查找的元素temp=ListFind_keyword(L,ch,loc); /按关键字 /查找 if(temp=False) printf( 没有找到该元素 !n); /查找失败else printf(该元素在链表的第 d个位置。n,loc);/成功查找，显示该元素位置break;case 5:if(L-next=NULL)/链表为空printf( 链表为空 !n);elseprintf( 请输入要查找的位置 :);scanf(%d,&loc);/输入/要查找的元素的位置temp=ListFind_order(L,c

38、h,loc); /按序号查找 if(temp=False) printf( 该位置不存在 !n); / 查找失败 else printf(第%d 个元素是：cn,loc,ch);/成功查找，显示该元素break;default:flag=0;printf( 程序结束，按任意键退出 !n);getch();void CreatList(LinkList &v,int n)/生成一个带头结点的有n个元素的单链表int i;LinkList p;v=(LinkList)malloc(LEN); / 生成头结点v-next=NULL;printf(请输入 %d 个字符：例如：abcdefgn, n);getchar();for(i=n;i0;-i)p=(LinkList)malloc(LEN); / 生成新结点 scanf(%c,&p-data);/ 将未完成的代码补全 , 此处添加一条代码v-next=p;BOOL ListInsert(LinkList &v,int i,char e)/在单链表的第i各位置插入元素e,成功返回/True，失败返回FalseLinkList p,s;int j=0;p=v;while