线性表数据结构试验

1、淮海工学院计算机科学系实验报告书课程名：数据结构题目：线性表数据结构试验班级：学号：姓名：评语：成绩：指导教师：批阅时间：年月日数据结构实验报告- 1 -线性表实验报告要求1 目的与要求 :1 ）掌握线性表数据结构的基本概念和抽象数据类型描述；2 ）熟练掌握线性表数据结构的顺序和链式存储存表示；3 ）熟练掌握线性表顺序存储结构的基本操作算法实现；4 ）熟练掌握线性表的链式存储结构的基本操作算法实现;5 ）掌握线性表在实际问题中的应用和基本编程技巧;6 ）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；7 ）按照报告格式和内容要求，认真书写实验报告，并在试验后的第

2、三天提交电子（全班同学提交到学委，再统一打包提交给老师）和纸质（每班每次5 份，学委安排，保证每个同学至少提交一次） ；8 ）积极开展实验组组内交流和辅导，严禁复制和剽窃他人实验成果，一旦发现严肃处理；9 ）上实验课前，要求每个同学基本写好程序，并存储在自己的U 盘上，用于实验课堂操作时调试和运行。凡不做准备，没有提前编写程序者，拒绝上机试验。2 实验内容或题目一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型 int 。按照顺序存储结构实现如下算法：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入）的顺序存储结构（即顺序表），长度限定在25 之内；2）打印 / 显示

3、（遍历）该线性表（依次打印/ 显示出表中元素值） ；3）在顺序表中查找第i 个元素，并返回其值；4）在顺序表第i 个元素之前插入一已知元素；5）在顺序表中删除第i 个元素；6）求顺序表中所有元素值（整数）之和；数据结构实验报告- 2 -二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char 。按照动态单链表结构实现如下算法：1）按照头插法或尾插法创建一个带头结点的字符型单链表（链表的字符元素从键盘输入），长度限定在 10 之内；2）打印（遍历）该链表（依次打印出表中元素值，注意字符的输入顺序与链表的结点顺序）；3）在链表中查找第i 个元素， i 合法返回元素值，否则

4、，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；5）在链表中第i 个结点之前插入一个新结点；6）在线性表中删除第i 个结点； 7）计算链表的长度。3 实验步骤与源程序一、 顺序表的基本操作实现实验Common.h#include #include #include #define OK1#define ERROR0#define TRUE 1#define FALSE 0Seqlist.h#define ElemType int#define MAXSIZE25typedefstructElemTypeelemMAXSIZE;intlas

5、t;SeqList;#include common.h#include seqlist.hintLocate(SeqList L, int n)数据结构实验报告- 3 -int i=0;while (iL.last&i!=n)i+;if(i=L.last)return L.elemi;elsereturn(-1);intInsList(SeqList *L,int i,ElemType e)int k;if(iL-last+2)printf( 插入位置i 值不合法 );return(ERROR);if(L-last= MAXSIZE-1)printf( 表已满无法插入);return(ERRO

6、R);for(k=L-last;k=i-1;k-)L-elemk+1=L-elemk;L-elemi-1=e;L-last+;return(OK);intDelList(SeqList *L,int i,ElemType *e)数据结构实验报告- 4 -int k;if(iL-last+1)printf( 删除位置不合法!);return(ERROR);*e = L-elemi-1;for(k=i; klast; k+)L-elemk-1 = L-elemk;L-last-;return(OK);intAddList(SeqList *L)int k,s=0;for(k=0;klast;k+)

7、s=s+L-elemk;return s;void main()SeqList l;int p,q,r,*q1;int i;q1=(int*)malloc(sizeof(int);printf( 请输入线性表的长度:);scanf(%d,&r);数据结构实验报告- 5 -l.last = r-1;printf( 请输入线性表的各元素值:n);for(i=0; i=l.last; i+)scanf(%d,&l.elemi);printf( 请输入要查找的元素的位置:n);scanf(%d,&q);p=Locate(l,q);if(p = -1)printf( 在此线性表中没有这样的元素!n);e

8、lseprintf( 该位置的元素为:%dn,p);printf( 请输入要插入的位置:n);scanf(%d,&p);printf( 请输入要插入的元素值:n);scanf(%d,&q);InsList(&l,p,q);for(i=0; i=l.last; i+)printf(%d,l.elemi);printf(n);printf( 请输入要删除的元素位置:n);scanf(%d,&p);DelList(&l,p,&q);printf( 删除的元素值为:%dn,q);printf( 删除后的元素序列:n);for(i=0; i=l.last; i+)数据结构实验报告- 6 -printf(

9、%d,l.elemi);printf(n);printf( 剩余数字之和为：);printf( n %dn,AddList(&l);二、链表（带头结点）基本操作实验Common.h#include #include #include #define OK1#define ERROR0#define TRUE 1#define FALSELinklist.htypedef char ElemType;typedef struct NodeElemType data;struct Node* next;Node, *LinkList;#include #include #define ElemTy

10、pe chartypedef struct Node数据结构实验报告- 7 -ElemType data;struct Node* next;Node, *LinkList;LinkListCreateFromHead()LinkListL;Node*s;charc;intflag=1,i=1;L=(LinkList)malloc(sizeof(Node);L-next=NULL;while(flag&idata=c;s-next=L-next;L-next=s;elseflag=0;i+;return L;数据结构实验报告- 8 -Node *search(LinkList L,int i)

11、int j=0;Node *p;p=L;while(p-next!=NULL&jnext;j+;if(i=j) return p;else return NULL;Node *locate(LinkList L,ElemType key)Node *p;p=L-next;while(p!=NULL)if(p-data!=key)p=p-next;else break;return p;void InsList(LinkList L,int i,ElemType e)Node *p,*s;数据结构实验报告- 9 -int k;p=L;k=0;while(p!=NULL&knext;k=k+1;i

12、f(k!=i-1)printf(error!);s=(Node *)malloc(sizeof(Node);s-data=e;s-next=p-next;p-next=s;void delLink(LinkList L,int i,ElemType *e)Node *p,*r;int k;p=L;k=0;while(p-next!=NULL&knext;k=k+1;数据结构实验报告- 10 -if(k!=i-1)printf( 位置不合理 );r=p-next;p-next=p-next-next;*e=r-data;free(r);int Listlength(LinkList L)Node

13、 *p;p=L-next;int j=0;while(p!=NULL)p=p-next;j+;return j;void main()LinkList l;Node *p;char e;数据结构 实验报告-11-char a;int i,n;printf( 用头插法建立单链表,请输入链表数据 , 以 $结束 !n);l = CreateFromHead();p = l-next;printf( 输入的字符依次为:);while(p!=NULL)printf(%c,p-data);p=p-next;printf(%cn);Node *p1;printf( 请输入要查找的字符的序号:);scanf

14、(%d,&n);printf( 要查找的字符:n);p1=search(l,n);printf(%c,p1-data);printf(%cn);printf( 插入后的字符:n);scanf(%c,&a);InsList(l,3,a);p1=l-next;while(p1!=NULL)printf(%c,p1-data);p1=p1-next;数据结构实验报告- 12 -printf(%cn);delLink(l,2,&e);p1=l-next;printf( 删除后的字符为:n);while(p1!=NULL)printf(%c,p1-data);p1=p1-next;printf(%cn);printf( 该字符串的长度为:n);i=Listlength(l);printf(%dn,i);printf( 输入要查找的字符:n);scanf(%c,&a);p1=locate(l,a);if(p1!=NULL)printf(true);printf(%cn);elseprintf(flase!);printf(%cn);数据结构实验报告- 13 -4 测试数据与实验结果（可以抓图粘贴）一 顺序表的基本操作实现实验数据结构实验报告- 14 -二、链表（带头结点）基本操作实验