《数据结构实验一线性表及其应用.pdf》由会员分享，可在线阅读，更多相关《数据结构实验一线性表及其应用.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-实验一线性表及其应用 一、实验目的 1.熟悉 C 语言的上机环境，进一步掌握 C 语言的构造特点。2.掌握线性表的顺序存储构造的定义及 C 语言实现。3.掌握线性表的链式存储构造单链表的定义及 C 语言实现。4.掌握线性表在顺序存储构造即顺序表中的各种根本操作。5.掌握线性表在链式存储构造单链表中的各种根本操作。二、实验容 1.顺序线性表的建立、插入及删除。2.链式线性表的建立、插入及删除。三、实验步骤 1.建立含 n 个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。2.利用前面的实验先建立一个顺序表 L=21，23，14，5，56，17，31，然后在第 i 个位置插入元素 68。3
2、.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。四、实现提示 1.由于 C 语言的数组类型也有随机存取的特点，一维数组的机表示就是顺序构造。因此，可用 C 语言的一维数组实现线性表的顺序存储。在此，我们利用 C 语言的构造体类型定义顺序表：#define MA*SIZE 1024 typedef int elemtype;/*线性表中存放整型元素 */typedef struct elemtype vecMA*SIZE;int len;/*顺序表的长度 */sequenlist;将此构造定义放在一个头文件 sqlist.h 里，可防止在后面的参
3、考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。2.注意如何取到第 i 个元素，在插入过程中注意溢出情况以及数组的下标与位序顺序表中元素的次序的区别。3.单链表的结点构造除数据域外，还含有一个指针域。用 C 语言描述结点构造如下：typedef int elemtype;typedef struct node-elemtype data;/数据域 struct node*ne*t;/指针域 linklist;注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到 C 语言的标准函数 malloc()，如给指针变量 p 分配一个结点的地址：p=(linklist*)m
4、alloc(sizeof(linklist);该语句的功能是申请分配一个类型为 linklist 的结点的地址空间，并将首地址存入指针变量 p 中。当结点不需要时可以用标准函数 free(p)释放结点存储空间，这时 p 为空值NULL。五、思考与提高 1.如果按由表尾至表头的次序输入数据元素，应如何建立顺序表。2.在 main 函数里如果去掉 L=&a 语句，会出现什么结果？六、完整参考程序 1.顺序线性表的建立、插入及删除。#include#include#define MA*30 /定义线性表的最大长度 enum BOOLFalse,True;/定义 BOOL 型 typedef stru
5、ct char elemMA*;/线性表 int last;/last 指示当前线性表的长度 sqlist;void initial(sqlist&);/初始化线性表 BOOL insert(sqlist&,int,char);/在线性表中插入元素 BOOL del(sqlist&,int,char&);/在线性表中删除元素 int locate(sqlist,char);/在线性表中定位元素 void print(sqlist);/显示线性表中所有元素 void main()sqlist S;/S 为一线性表 int loc,flag=1;char j,ch;BOOL temp;printf
6、(本程序用来实现顺序构造的线性表。n);printf(可以实现查找、插入、删除等操作。n);initial(S);/初始化线性表-while(flag)printf(请选择:n);printf(1.显示所有元素n);printf(2.插入一个元素n);printf(3.删除一个元素n);printf(4.查找一个元素n);printf(5.退出程序 n);scanf(%c,&j);switch(j)case 1:print(S);break;/显示所有元素 case 2:printf(请输入要插入的元素(一个字符)和插入位置:n);printf(格式：字符，位置；例如:a,2n);scanf(
7、%c,%d,&ch,&loc);/输入要插入的元素和插入的位置 temp=insert(S,loc,ch);/插入 if(temp=False)printf(插入失败!n);/插入失败 else printf(插入成功!n);print(S);/插入成功 break;case 3:printf(请输入要删除元素的位置:);scanf(%d,&loc);/输入要删除的元素的位置 temp=del(S,loc,ch);/删除 if(temp=True)printf(删除了一个元素:%cn,ch);/删除成功 else printf(该元素不存在!n);/删除失败 print(S);break;ca
8、se 4:printf(请输入要查找的元素:);scanf(%c,&ch);/输入要查找的元素 loc=locate(S,ch);/定位 if(loc!=-1)printf(该元素所在位置:%dn,loc+1);/显示该元素位置 else printf(%c 不存在!n,ch);/当前元素不存在 break;default:flag=0;printf(程序完毕，按任意键退出!n);-getch();void initial(sqlist&v)/初始化线性表 int i;printf(请输入初始线性表长度：n=);/输入线性表初始化时的长度 scanf(%d,&v.last);printf(请输
9、入从 1 到%d 的各元素(字符)，例如:abcdefgn,v.last);getchar();for(i=0;iv.last;i+)scanf(%c,&v.elemi);/输入线性表的各元素 BOOL insert(sqlist&v,int loc,char ch)/插入一个元素，成功返回 True，失败返回 False int i;if(locv.last+1)printf(插入位置不合理!n);/位置不合理 return False;else if(v.last=MA*)/线性表已满 printf(线性表已满!n);return False;else for(i=v.last-1;i=l
10、oc-1;i-)v.elemi+1=v.elemi;/其后元素依次后移 v.elemloc-1=ch;/插入元素 v.last+;/线性表长度加一 return True;BOOL del(sqlist&v,int loc,char&ch)/删除一个元素，成功返回 True，并用 ch 返回该元素值，失败返回 False int j;if(locv.last)/删除位置不合理-return False;else ch=v.elemloc-1;/ch 取得该元素值 for(j=loc-1;jv.last-1;j+)v.elemj=v.elemj+1;/其后元素依次前移 v.last-;/线性表长
11、度减一 return True;int locate(sqlist v,char ch)/在线性表中查找 ch 的位置，成功返回其位置，失败返回-1 int i=0;while(iv.last&v.elemi!=ch)i+;/当前位置后移，直到找到为止 if(v.elemi=ch)/找到当前元素 return i;else return(-1);void print(sqlist v)/显示当前线性表所有元素 int i;for(i=0;iv.last;i+)printf(%c,v.elemi);printf(n);2.链式线性表的建立、插入及删除。#include#include#inclu
12、de#define LEN sizeof(LNode)/定义 LEN 为一个节点的长度 enum BOOLFalse,True;/定义 BOOL 型 typedef struct node char data;/数据域 struct node*ne*t;/指向下一个节点的指针 LNode,*LinkList;void CreatList(LinkList&,int);/生成一个单链表 BOOL ListInsert(LinkList&,int,char);/在单链表中插入一个元素 BOOL ListDelete(LinkList&,int,char&);/在单链表中删除一个元素 BOOL Li
13、stFind_keyword(LinkList,char,int&);/按关键字查找一个元素-BOOL ListFind_order(LinkList,char&,int);/按序号查找一个元素 void ListPrint(LinkList);/显示单链表所有元素 void main()LinkList L;BOOL temp;int num,loc,flag=1;char j,ch;printf(本程序实现链式构造的线性表的操作。n);printf(可以进展插入，删除，定位，查找等操作。n);printf(请输入初始时链表长度:);/输入生成单链表时的元素个数 scanf(%d,&num)
14、;CreatList(L,num);/生成单链表 ListPrint(L);while(flag)printf(请选择:n);printf(1.显示所有元素n);/显示链表元素 printf(2.插入一个元素n);/插入链表元素 printf(3.删除一个元素n);/删除链表元素 printf(4.按关键字查找元素n);/按关键字查找 printf(5.按序号查找元素n);/按序号查找 printf(6.退出程序 n);/退出 scanf(%c,&j);switch(j)case 1:ListPrint(L);break;case 2:printf(请输入元素(一个字符)和要插入的位置:n);
15、printf(格式:字符，位置；例如:a,3n);scanf(%c,%d,&ch,&loc);/输入要插入的元素和要插入的位置 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(删除失败!n);/删除失败 el
16、se printf(成功删除了一个元素:%cn,ch);/删除成功，显示该元素 ListPrint(L);break;case 4:if(L-ne*t=NULL)/链表为空 printf(链表为空!n);elseprintf(请输入要查找的元素(一个字符):);scanf(%c,&ch);/输入要查找的元素 temp=ListFind_keyword(L,ch,loc);/按关键字查找 if(temp=False)printf(没有找到该元素!n);/查找失败 else printf(该元素在链表的第%d 个位置。n,loc);/成功查找，显示该元素位置 break;case 5:if(L-n
17、e*t=NULL)/链表为空 printf(链表为空!n);elseprintf(请输入要查找的位置:);scanf(%d,&loc);/输入要查找的元素的位置 temp=ListFind_order(L,ch,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 个元素
18、的单链表 int i;-LinkList p;v=(LinkList)malloc(LEN);/生成头结点 v-ne*t=NULL;printf(请输入%d 个字符：例如：abcdefgn,n);getchar();for(i=n;i0;-i)p=(LinkList)malloc(LEN);/生成新结点 scanf(%c,&p-data);p-ne*t=v-ne*t;v-ne*t=p;BOOL ListInsert(LinkList&v,int i,char e)/在单链表的第 i 各位置插入元素 e，成功返回 True，失败返回 False LinkList p,s;int j=0;p=v;
19、while(p&jne*t;+j;/查找第 i-1 个元素的位置 if(!p|ji-1)return False;/没有找到 s=(LinkList)malloc(LEN);/生成一个新结点 s-data=e;s-ne*t=p-ne*t;/将新结点插入到单链表中 p-ne*t=s;return True;BOOL ListDelete(LinkList&v,int i,char&e)/在单链表中删除第 i 个元素，成功删除返回 True，并用 e 返回该元素值，失败返回 False LinkList p,q;int j=0;p=v;while(p-ne*t&jne*t;+j;if(!(p-ne
20、*t)|ji-1)return False;/查找失败 q=p-ne*t;p-ne*t=q-ne*t;/删除该元素-e=q-data;/e 取得该元素值 free(q);/释放该元素空间 return True;BOOL ListFind_keyword(LinkList v,char e,int&i)/在单链表中查找关键字为 e 的元素，成功返回 True,并用 i 返回该元素位置，/失败返回 False i=1;LinkList p;p=v-ne*t;while(p-data!=e)&(p-ne*t!=NULL)/p 指针指向下一个，直到 p=p-ne*t;i+;/找到或到链表尾为止 if
21、(p-data!=e)/该元素在链表中不存在 return False;else return True;BOOL ListFind_order(LinkList v,char&e,int i)/在单链表中查找第 i 个元素，成功返回 True，并用 e 返回该元素值，/失败返回 False LinkList p;int j=0;p=v;while(p-ne*t&jne*t;+j;if(j!=i)return False;/查找失败 else e=p-data;/查找成功，用 e 取得该元素值 return True;void ListPrint(LinkList v)/显示链表所有元素 LinkList q;q=v-ne*t;printf(链表所有元素:);-while(q!=NULL)printf(%c,q-data);q=q-ne*t;printf(n);