线性表的抽象数据类型的实现实验报告.doc

《线性表的抽象数据类型的实现实验报告.doc》由会员分享，可在线阅读，更多相关《线性表的抽象数据类型的实现实验报告.doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.数据结构实验报告实验名称：线性表的抽象数据类型的实现学号：2011129127姓名：刘瑞奇指导老师：解德祥计算机与信息学院实验1线性表的抽象数据类型的实现实验目的1. 掌握线性表的顺序存储结构和链式存储结构；2. 熟练掌握顺序表和链表基本算法的实现；3. 掌握利用线性表数据结构解决实际问题的方法和基本技巧；4. 按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；5. 按时提交实验报告。实验环境计算机、C语言程序设计环境实验学时2学时，选做实验。实验内容一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。按照顺序存储结

2、构实现如下算法（各算法边界条件和返回结果适当给出）： 创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在20之内； 打印（遍历）该线性表（依次打印出表中元素值）； 在线性表中查找第i个元素，并返回其值； 在线性表中第i个元素之前插入一已知元素； 在线性表中删除第i个元素； 求线性表中所有元素值（整数）之和；实验步骤C源程序代码/*file:seqlist.cpp*/#include#include#include#define size 20#define elemtype intstruct seqlistelemtype elemsize;int last;void men

3、u()printf(n.);printf(n0.退出操作.);printf(n1.建立数据类型为整形的顺序表（长度小于20).);printf(n2.打印线性表.);printf(n3.在线性表中查找第i个元素，并返回其值.);printf(n4.在线性表中第i个元素之前插入一已知元素.);printf(n5.在线性表中删除第i个元素.);printf(n6.求线性表中所有元素值（整数）之和.);printf(n7.初始化.n);void ins(seqlist *L)L-last=-1;void creat(seqlist *L)int i=0;elemtype j;printf(请输入线性

4、表元素(-1结束):);scanf(%d,&j);while(j!=-1) L-elemi+=j;L-last+;if(isize-1) break;scanf(%d,&j);void print(seqlist *L)int i;printf(顺序表中元素为:);for(i=0;ilast;i+)printf(%dt,L-elemi);int find(seqlist *L,int i)if(iL-last+1)return 0;elsereturn(L-elemi-1);int insert(seqlist *L,int i,int x)int j;if(L-last+1=size|iL-

5、last+2)return 0;L-last+;for(j=L-last;j=i-1;j-)L-elemj+1=L-elemj;L-elemi-1=x;return 1;int del(seqlist *L,int i)int e,j;if(L-last=-1|iL-last+1)return 0;elsee=L-elemi-1;for(j=i;jlast+1;j+)L-elemj-1=L-elemj;L-last-;return 1;int sum(seqlist *L)int i=0,s=0;if(L-last=-1)return 0;for(i=0;ilast;i+)s+=L-elemi

6、;return s;int isempty(seqlist *L)if(L-last=-1)return 1;else return 0;void main()int i,cz,e;elemtype date;seqlist L;menu();printf(请输入你要执行的操作的序号:);i=scanf(%d,&cz);while(1)if(!i)printf(只能输入数值);elsebreak;printf(n再输入一次：);rewind(stdin);i=scanf(%d,&cz);while(cz)switch(cz)case 1:if(isempty(&L)ins(&L); creat

7、(&L);elseprintf(表已经存在，先清空再进行此操作！n);break;case 2:if(isempty(&L)printf(表为空n);elseprint(&L);break;case 3:printf(输入待查找元素的位置:n);scanf(%d,&i);if(find(&L,i)printf(查找的第%d个元素为%dn,i,find(&L,i);elseprintf(查找位置错误n);break;case 4:printf(请输入要插入的元素及位置:n);scanf(%d,&date);scanf(%d,&i);if(insert(&L,i,date)printf(插入元素成

8、功!n);else printf(插入位置不合法或栈已满!n);break;case 5:printf(请输入要删除元素的位置n);scanf(%d,&i);e=L.elemi-1;if(del(&L,i)printf(删除第%d个值为%d的元素n,i,e);printf(删除成功n);Elseprintf(删除位置不合法或表已空n);break;case 6:if(isempty(&L)printf(表已空!n);else printf(线性表中所有元素值（整数）和:%dn,sum(&L);break;case 7:ins(&L);break;default: printf(无此操作!n);

9、break;menu();printf(请输入你要执行的操作的序号:);i=scanf(%d,&cz);while(1)if(!i) printf(n只能输入数值);elsebreak;printf(n再输入一次：);rewind(stdin);i=scanf(%d,&cz);测试数据与实验结果7.初始化1.建表2.打印3.查找4.插入不合法 长度超过205.删除然后打印4.插入合法6.求和二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）： 创建任意字符型有序（递增排序）单循环链表（即链表的字符元素

10、随机在键盘上输入），长度限定在15之内； 打印（遍历）该链表（依次打印出表中元素值）； 在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE； 在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE； 在链表中按照有序方式插入一已知字符元素； 在线性表中删除第i个结点； 计算链表的长度。实验步骤C源程序代码 #include#include#include#define elemtype char#define size 15static int n=0;typedef struct Nodeelemtype data;struct Node * next;

11、Node,*linklist;void init(linklist *L)*L=(linklist)malloc(sizeof(Node);(*L)-next=*L;n=0;void creat(linklist L)int i=0,j;Node *s,*r;elemtype csize,t;r=L-next;printf(请输入字符型元素(最多15个,输入字符结束):);scanf(%s,c);while(ci!=)n+;i+;i=0;for(i=0;in;i+)for(j=i;jn-i-1;j+)if(cjcj+1)t=cj;cj=cj+1;cj+1=t;for(i=0;idata=t;r

12、-next=s;r=s;void length(linklist L)printf(链表长度为:%d,n);void show(linklist L)int j;Node *p;p=L;if(!p)printf(表为空!);return;for(j=0;jnext-data);p=p-next;int isempty(linklist L)Node *pre;pre=L;if(pre-next=L)return 1;return 0;void find4(linklist L,int i)int j=0;Node *p;if(isize)printf(查找位置错误!);p=L;while(jn

13、ext;j+;if(i=j)printf(%c,p-data);void find5(linklist L,elemtype k)int i=1,j;Node *p;p=L-next;if(n=0)printf(表为空!n);return;for(j=0;jdata!=k)p=p-next;else printf(第%d个元素是要查找的元素%c,i,k);return;printf(链表中无此字符!);void insert(linklist L,elemtype t)Node *r,*s;int i=0;r=L;if(n=size)printf(表已满!);return;for(i;in-1

14、&tnext-data;i+)i+;r=r-next;s=(Node *)malloc(sizeof(Node);s-data=t;s-next=r-next;r-next=s;printf(插入成功!);n+;return;void del(linklist L,int i)int j=0;Node *p,*r;if(in) printf(删除位置不对!);return;p=L;while(jnext;printf(开始删除);r=p-next;p-next=r-next;free(r);printf(删除成功!);n-;void menu()printf(.n);printf(0.退出程序

15、.n);printf(1.初始化单循环链表.n);printf(2.创建任意字符型有序（递减排序 最长15）单循环链表.n);printf(3.打印（遍历）该链表（依次打印出表中元素值）.n);printf(4.在链表中查找第i个元素.n);printf(5.在链表中查找与一已知字符相同的第一个结点.n);printf(6.在链表中按照有序方式插入一已知字符元素.n);printf(7.在线性表中删除第i个结点.n);printf(8.计算链表的长度.n);printf(.n);void main()int cz,i,j,k;char key,t;linklist L;menu();print

16、f(请输入你要执行的操作的序号:);i=scanf(%d,&cz);while(1)if(!i)printf(n只能输入数值);elsebreak;printf(n再输入一次：);rewind(stdin);i=scanf(%d,&cz);while(cz)switch(cz)case 1:init(&L);break;case 2:if(isempty(L)creat(L);elseprintf(表已存在，请先初始化单循环链表!n);break;case 3:show(L);break;case 4:printf(请输入查找的第i个元素的i值:);j=scanf(%d,&i);while(1

17、)if(!j)printf(n只能输入数值);elsebreak;printf(n再输入一次：);rewind(stdin);j=scanf(%d,&cz);find4(L,i);break;case 5:printf(请输入要查找的字符:);rewind(stdin);scanf(%c,&key);find5(L,key);break;case 6:printf(请输入要插入的字符:);rewind(stdin);scanf(%c,&t);insert(L,t);break;case 7:printf(输入要删除的第i个元素的i值:);scanf(%d,&k);del(L,k);break;case 8:length(L);break;default:printf(无此操作!n);break;menu();printf(请输入你要执行的操作的序号:);i=scanf(%d,&cz);while(1)if(!i)printf(n只能输入数值);elsebreak;printf(n再输入一次：);rewind(stdin);i=scanf(%d,&cz);测试数据与实验结果