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

数据结构实验课程设计题目：实验一线性表的抽象数据类型的实现姓名：杨静 学号：2011114105班级： 2班 （44号 ） 组长：指导老师：解德祥计算机与信息学院实验一线性表的抽象数据类型的实现实验目的1. 掌握线性表的顺序存储结构和链式存储结构；2. 熟练掌握顺序表和链表基本算法的实现；3. 掌握利用线性表数据结构解决实际问题的方法和基本技巧；4. 按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；5. 按时提交实验报告。实验环境:计算机、C语言程序设计环境实验学时:2学时，选做实验。实验内容一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）： 创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在20之内； 打印（遍历）该线性表（依次打印出表中元素值）； 在线性表中查找第i个元素，并返回其值； 在线性表中第i个元素之前插入一已知元素； 在线性表中删除第i个元素； 求线性表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）： 创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内； 打印（遍历）该链表（依次打印出表中元素值）； 在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE； 在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE； 在链表中按照有序方式插入一已知字符元素； 在线性表中删除第i个结点； 计算链表的长度。实验步骤：C源程序代码如下：#include#define OK 1#define ERROR 0#define MAXSIZE 20typedef int ElemType;typedef structElemType elemMAXSIZE; int last; SeqList;void CreateSeqList(SeqList *L) int x,i=0;printf(请输入正整数，不超过20个:n); scanf(%d,&x);while(ielemi=x; scanf(%d,&x); i+; L-last=i;void PrintList(SeqList *L) int i; printf(数据元素为:n);for(i=0;ilast;i+) printf(%dn,L-elemi); int Locate(SeqList *L,int i ) if(i=1&ilast) return L-elemi-1; else return 0; int InsList(SeqList *L,int i,ElemType e) int k; if(iL-last+2) printf(插入i位置值不合法); return(ERROR); if(L-last=MAXSIZE-1) printf(表已满，无法插入); return(ERROR); for(k=L-last;k=i-1;k+) L-elemk+1=L-elemk; L-elemi-1=e; L-last+; return(OK); int DelList(SeqList *L,int i,ElemType *e) int k; if(iL-last+1) printf(删除位置不合法); return(ERROR); *e=L-elemi-1; for(k=i;ilast;k+) L-elemk-1=L-elemk; L-last-; return(OK); int SumList(SeqList *L)int i,sum=0;for(i=0;ilast;i+)sum=sum+L-elemi; return(sum);void jiemian() SeqList L; int j,i,a; printf(创建新链表请按1n打印链表请按2n按序号查找元素请按3n在链表中查找与一已知字符相同的第一个结点请按4n在链表中按照有序方式插入一已知字符元素请按5n在线性表中删除第i个结点请按6n计算链表的长度请按7n操作结束请按0n); scanf(%d,&j); while(j) switch(j) case 1:CreateSeqList(&L); break; case 2: printf(打印顺序表如下:n); PrintList(&L); break; case 3:printf(请问你要查找第几个元素:n); scanf(%d,&i); if(Locate(&L,i ) printf(您要找的元素为%dn,Locate(&L,i ); else printf(i值不合法!); break; case 4:printf(请您输入选择插入位置以及输入插入元素:n); scanf(%d%d,&i,&a); if(InsList(&L,i,a) PrintList(&L); else printf(i值不合法!n); break; case 5: printf(请您输入要删除元素的位置:n); scanf(%d,&i); if(DelList(&L,i,&a) PrintList(&L); else printf(i值不合法!n); break; case 6:printf(所有元素之和为:%dn,SumList(&L); break; case 7: break; default: printf(数据输入错误，请重新输入!); printf(操作结束请按7;继续操作请按1-6,请输入您的选择:n);scanf(%d,&j); void main() jiemian();链表（带头结点）基本操作实验：#includestdlib.h#includestdio.hstruct LNode char elem; struct LNode* next;*l,*p,*q;void Order(struct LNode * l, int n) int i;char swap,*e,*f; for(i=1;inext; while(p-next!=l) if(p-elemp-next-elem) e=&p-elem; f=&p-next-elem; swap=*e; *e=*f; *f=swap; p=p-next; return;void Print(struct LNode * l, int n) int i; p=l-next; for(i=1;ielem); p=p-next; printf(n); return;void Locate(struct LNode * l, int n,int m) int i; if(mn) printf(FALSE!t);return; else p=l; for(i=1;inext; printf(The elem is:%cn,p-elem); return;void Insertelem(struct LNode * l, int n,char m) q=(struct LNode *)malloc(sizeof(struct LNode); q-next=l-next; l-next=q; q-elem=m; n=n+1; Order(l,n); Print(l,n); return;void Delete(struct LNode * l, int n,int m) int i; p=l; for(i=1;inext; p-next=p-next-next; n=n-1; printf(删除后的链表为:n); Print(l,n); return;void Length(int n) int i;int length=0; for(i=1;inext=NULL; printf(请输入链表的元素数: ); scanf(%d,&n);getchar(); if(n0;i-) q=(struct LNode *)malloc(sizeof(struct LNode); q-next=l-next; l-next=q; p=l; while(p-next!=NULL) p=p-next; p-next=l; printf(输入元素:); p=l-next; for(i=1;ielem); getchar(); p=p-next; Order(l,n); printf(-n); printf(您输入的元素为:n); Print(l,n); printf(-n); printf(输入您想查找的元素序号:); scanf(%d,&a);getchar(); Locate(l,n,a); printf(-n); pri