《顺序表,单链表,栈,队列2011.11.2》由会员分享，可在线阅读，更多相关《顺序表,单链表,栈,队列2011.11.2（24页珍藏版）》请在金锄头文库上搜索。
1、实验名称（一）：实现顺序表和单链表的基本运算实验名称（一）：实现顺序表和单链表的基本运算姓名：李秋玉 班级：2010 计算机一班 学号：2010131145一、实验目的：了解顺序表的结构特点及有关概念，掌握顺序表的一、实验目的：了解顺序表的结构特点及有关概念，掌握顺序表的各种基本操作算法思想及其实现。了解单链表的结构特点及有关概各种基本操作算法思想及其实现。了解单链表的结构特点及有关概念，掌握单链表的各种基本操作算法思想及其实现。念，掌握单链表的各种基本操作算法思想及其实现。 二、实验内容：二、实验内容： （1）编写一个程序，实现顺序表的各种基本运算： 1、初始化顺序表； 2、顺序表的插入；
2、3、顺序表的输出； 4、求顺序表的长 度 5、判断顺序表是否为空； 6、输出顺序表的第 i 位置的个元素 ； 7、在顺 序表中查找一个给定元素在表中的位置； 8、顺序表的删除；9、释放顺序表 （2）编写一个程序，实现单链表的各种基本运算： 1、初始化单链表； 2、单链表的插入； 3、单链表的输出；4、求单链表的长 度 5、判断单链表是否为空； 6、输出单链表的第 i 位置的元素 ； 7、在单链 表中查找一个给定元素在表中的位置； 8、单链表的删除； 9、释放单链表三、算法思想与算法描述：三、算法思想与算法描述：顺序表：将一个个元素采用尾插入法插入到顺序表中，如顺序表：将一个个元素采用尾插入法插
3、入到顺序表中，如ListInsert(L,1,ListInsert(L,1,ff););就是将就是将 f f 插入到到单链表的第一个位置，之插入到到单链表的第一个位置，之后按此方法可以插入其他元素。之后完成其他操作，包含了条件语后按此方法可以插入其他元素。之后完成其他操作，包含了条件语句，循环语句，返回语句等。单链表：句，循环语句，返回语句等。单链表：由于单链表不像顺序栈那样由于单链表不像顺序栈那样连续的，而是通过连续的，而是通过*next*next 来指向结点，首先创立一个空栈来便于插来指向结点，首先创立一个空栈来便于插入。来实现之后一系列操作。入。来实现之后一系列操作。四、实验步骤与算法实
4、现：四、实验步骤与算法实现：（1 1）顺序表：）顺序表：1 1、初始化顺序表：构造一个空的线性表，实际只需、初始化顺序表：构造一个空的线性表，实际只需分配线性表的存储空间并分配线性表的存储空间并 lengthlength 为为 0.0. 2 2、顺序表的插入：该运算、顺序表的插入：该运算在顺序表在顺序表 L L 的第的第 i i 个位置上插入新元素个位置上插入新元素 e e。如果。如果 i i 值不正确，则显值不正确，则显示相应错误信息：否则将顺序表原来第示相应错误信息：否则将顺序表原来第 i i 个元素及以后元素均要向个元素及以后元素均要向后移一位。后移一位。3 3、顺序表的输出；当顺序表不
5、为空的时候，显示、顺序表的输出；当顺序表不为空的时候，显示 L L 中的中的元素的值元素的值 4 4、求顺序表的长度该运算返回顺序表、求顺序表的长度该运算返回顺序表 L L 的长度，实际只的长度，实际只需返回需返回 lengthlength 的值的值 5 5、判断顺序表是否为空；看元素中的、判断顺序表是否为空；看元素中的 lengthlength是否为是否为 0,0, 6 6、输出顺序表的第、输出顺序表的第 i i 位置的个元素位置的个元素 ；用；用 e e 返回返回 L L 中第中第i i 个元素的值。个元素的值。 7 7、在顺序表中查找一个给定元素在表中的位置；、在顺序表中查找一个给定元素
6、在表中的位置；该运算顺序查找第一个值域与该运算顺序查找第一个值域与 e e 相等的元素得逻辑顺序。若不存在，相等的元素得逻辑顺序。若不存在，则返回则返回 0 0 8 8、顺序表的删除；该运算删除顺序表、顺序表的删除；该运算删除顺序表 L L 的第的第 i i 个元素。个元素。如果如果 i i 值不正确，则显示相应错误信息；否则将线性表第值不正确，则显示相应错误信息；否则将线性表第 i i 个元素个元素以后元素均向前移一个位置，移动方向为从左到右。以后元素均向前移一个位置，移动方向为从左到右。9 9、释放顺序表：、释放顺序表：free(L);free(L);(2)(2)单链表：单链表：1 1、初
7、始化单链表；建立一个空的单链表，及创建一个、初始化单链表；建立一个空的单链表，及创建一个头结点头结点 2 2、单链表的插入；、单链表的插入； 先在单链表中找到第先在单链表中找到第 i-1i-1 个结点个结点*p*p，若，若存在这样的结点，将值为存在这样的结点，将值为 e e 的结点插入的结点插入*s*s 其后其后 3 3、单链表的输出；、单链表的输出；逐一扫描单链表逐一扫描单链表 L L 的每个数据结点，并显示各个结点的每个数据结点，并显示各个结点 datadata 的值的值 4 4、求单链表的长度返回单链表结点的个数求单链表的长度返回单链表结点的个数 5 5、判断单链表是否为空；、判断单链表
8、是否为空；若单链表若单链表 L L 没有数据结点，则返回真，否返回假没有数据结点，则返回真，否返回假 6 6、输出单链表的、输出单链表的第第 i i 位置的元素位置的元素 ；若存在第；若存在第 i i 个数据结点，则将其个数据结点，则将其 datadata 值域赋给值域赋给变量变量 e e 7 7、在单链表中查找一个给定元素在表中的位置；在单链表、在单链表中查找一个给定元素在表中的位置；在单链表l l 中从头开始找一个值域与中从头开始找一个值域与 e e 相等的结点，若存在这样的结点，则相等的结点，若存在这样的结点，则返回位置返回位置 8 8、单链表的删除；、单链表的删除； 先在单链表先在单链
9、表 L L 中找到第中找到第 i-1i-1 个结点个结点*p*p，若存在这样的结点，且也存在直接后继结点，则删除该直接后，若存在这样的结点，且也存在直接后继结点，则删除该直接后继结点继结点 9 9、释放单链表释放单链表、释放单链表释放单链表 L L 占用的空间，即逐一释放全部占用的空间，即逐一释放全部结点的空间。结点的空间。五、实验测试及结果：五、实验测试及结果：（1 1）顺序表：）顺序表：#include #include #include#define MaxSize 50 typedef char ElemType; typedef struct ElemType elemMaxSize
10、;int length; SqList; void InitList(SqList * L-length=0; void DestroyList(SqList *L) free(L); int ListEmpty(SqList *L) return(L-length=0); int ListLength(SqList *L) return(L-length); void DispList(SqList *L) int i; if (ListEmpty(L) return; for (i=0;ilength;i+)printf(“%c“,L-elemi); printf(“n“); int Ge
11、tElem(SqList *L,int i,ElemType e=L-elemi-1; return 1; int LocateElem(SqList *L, ElemType e) int i=0; while (ilength if (i=L-length)return 0; elsereturn i+1; int ListInsert(SqList * if (iL-length+1)return 0; i-; for (j=L-length;ji;j-) L-elemj=L-elemj-1; L-elemi=e; L-length+; return 1; int ListDelete(
12、SqList * if (iL-length)return 0; i-; e=L-elemi; for (j=i;jlength-1;j+)L-elemj=L-elemj+1; L-length-; return 1; void main() SqList *L; ElemType e; printf(“(1)初始化顺序表Ln“);InitList(L); printf(“(2)依次采用尾插法插入f,b,f,m,o元素n“); ListInsert(L,1,f); ListInsert(L,2,b); ListInsert(L,3,f); ListInsert(L,4,m); ListInse
13、rt(L,5,o); printf(“(3)输出顺序表L:“); DispList(L); printf(“(4)顺序表L长度=%dn“,ListLength(L); if(ListEmpty(L) printf(“顺序表L为空n“); else printf(“顺序表L不为空n“); GetElem(L,3,e); printf(“(6)顺序表L的第个元素=%cn“,e); printf(“(7)元素a的位置=%dn“,LocateElem(L,a); printf(“(8)在第个元素位置上插入f元素n“); ListInsert(L,4,f); printf(“(9)输出顺序表L:“);
14、DispList(L); printf(“(10)删除L的第个元素n“);ListDelete(L,3,e); printf(“(11)输出顺序表L:“); DispList(L); printf(“(12)释放顺序表Ln“); DestroyList(L); 调试结果： (1)初始化顺序表L (2)依次采用尾插法插入f,b,f,m,o元素 (3)输出顺序表L:fbfmo (4)顺序表L长度=5 顺序表L不为空 (6)顺序表L的第3个元素=f (7)元素a的位置=0 (8)在第4个元素位置上插入f元素 (9)输出顺序表L:fbffmo (10)删除L的第3个元素 (11)输出顺序表L:fbfm
15、o (12)释放顺序表L 请按任意键继续. . .（2）单链表： #include#include #include typedef char ElemType; typedef struct LNode ElemType data; struct LNode *next; LinkList; void Creat(LinkList * L-next=NULL; void Insert(LinkList *s=(LinkList *)malloc(sizeof(LinkList);s-data=e;s-next=L-next;L-next=s; void Dis(LinkList *L)/ 3
16、、单链表的输出LinkList *p=L-next;while(p!=NULL) printf(“%3d“,p-data);p=p-next; int Length(LinkList *L)/4、求单链表的长度LinkList *p=L-next;int n=0;while(p!=NULL)n+;p=p-next;return n; int empty(LinkList *L)/5、判断单链表是否为空return(L-next=NULL); ElemType some(LinkList *L,int i)/6、输出单链表的第i位置的元素 LinkList *p=L-next;int j=1; while(
