数据结构-存储结构的比较

《数据结构-存储结构的比较》由会员分享，可在线阅读，更多相关《数据结构-存储结构的比较（13页珍藏版）》请在装配图网上搜索。

1、南京邮电大学通达学院实验报告（2015 / 2016 学年 第 二 学期）课程名称 数据结构 B实验名称存储结构的比较实验时间年 月于指导单位大学计算机学指导教师学生姓名班级学号学院（系）专 业实验报告实验名称存储结构的比较指导教师实验类型验证实验学时2实验时间一、实验目的和要求1、掌握线性表的基本操作在顺序存储结构上的实现2、掌握线性表的基本操作在链接存储结构上的表现3、比较两者优缺点二、实验环境硬件：微型计算机软件：Windows操作系统Microsoft Visual C+6.0三、实验原理及内容（一）、原理1、给出实验所采用数据结构的ADT描述（如无具体的数据结构，该部分可省略）;2、

2、给出核心算法的C语言源代码，需加上详细注释；3、给出测试数据及运行结果、实验相关结论等；4、分析各主要算法的时间和空间复杂度（此为可选内容，不作要求）（二）、内容1、顺序存储:/线性表的最大可容纳量建立线性表的类#includeviostream using namespace std; int const maxsize = 100; class sequentlist public:int a100;int len;线性表的实际长度获取线性表中的元素void Get(sequentlist L)for (int i = 0; i = L.len - 1; i+)cout 线性表第vv i+

3、1 ai;cout vv endl;输出线性表的元素void Getout(sequentlist L)cout vv L = ;for (int i = 0; i v= L.len-1; i+)cout ai ;cout ;cout endl;查找元素x在线性表中的位置void Locate( sequentlist L,int x)int temp = -1;for(int i = 0;i = L.len;i+) 如果x在顺序表中就将序号记录在temp中if(ai = x) temp = i;cout 元素 x 的位置是vv temp = 100)判断插入是否合法cout vv 顺序表已满

4、！ vv endl;else if(i v 1) II (i L.len + 1)cout vv 插入的位置不合理！ vv endl;elsefor(int j = L.len; j = i; j-)将i位置之后的元素后移一位L.aj+1 = L.aj;L.ai = x; /将 x插入到i位置L.len+;删除元素void sequentlist:Delete(sequentlist &L,int i)if(iv0) II (i = L.len + 1) cout vv ”删除位置不合法！ ”；elsecout 删除第 i 个位置元素 endl;for(int j = i;j L.len -

5、1; j+) 将i位置之后的元素都前移一位aj = aj+1;L.len-;求交集操作void Intersection(sequentlist & LA,sequentlist & LB,sequentlist & LC)int temp = 0;LC.len = 0;将a中的元素赋给c中for(int i = 0; i LA.len; i+)LC.ai = LA.ai;LC.len = i;将b中的元素依次与c中的元素比较for(int j = 0; j LB.len;j+)for(int i = 0; i LA.len;i+)if(LC.ai = LB.aj)temp+;if(temp

6、= 0)如果b中的元素j不在c中则将b中的元素放在c中LC.aLC.len =LB.aj;LC.len = LC.len + 1;求并集void sequentlist:Union(sequentlist & LA,sequentlist & LB,sequentlist & LC)int i,j;LC.len = 0;先将a中的元素赋到c中for( i = 0; i LA.len;i+)LC.ai = LA.ai;LC.len = i;将b中的元素插入到c的后面for( j = 0;j 0; t-)for( j = 0; j LC.aj+1)int temp;临时交换变量temp = LC.

7、aj+1;LC.aj+1 = LC.aj;LC.aj = temp;void main()定义线性表Lsequentlist L;L.len = 10;定义L的实际表长L.Get(L);控制台输入L的兀素L.Getout(L);输出插入后的线性表LL.Locate(L,10);查找兀素10是否在线性表中L.Insert(L,3,5);将元素3查到第5个位置L.Getout(L);L.Delete(L,2);删除L的第2个位置上的兀素L.Getout(L);定义线性表sequentlist LA , LB,LC;LA.len = 4;LA.Get(LA);LB.len = 7;LB.Get(LB

8、);求线性表的a与b并集，并逆序排列673678918789108910 C:PROGRAM FILESMICROSOFT VISUAL STUDIOMPROJECTS141201 Dl1412D101Deb.I 回 I47匸山匸匸纟七B匸017 - 7.- 7.- 7.- 7 - 7.- 7.- 一.-CT- 丫-1- -1- - -14二 1- - -1- - -1- - - - - -M-L-L-L-L-L-L-L-L-L-刀0 1234567891 第第第第第第第第第第 I 注主注主生生主主主注LC.Union(LA,LB,LC);LC.Getout(LC);求线性表a与b的交集LC.

9、Intersection(LA,LB,LC);LC.Getout(LC);运行图L = 12345元素10的位置是9L = 1 2 3 4 5删除第2个位萱元素L = next=NULL; scanf(“s,ch); while(strcmp(ch, “#)!=0)尾指针初值指向头结点读入第一个结点的值输入#结束pp=LocateNode(head,ch);if(pp=NULL)s=(ListNode *)malloc(sizeof(ListNode);生成新的结点*$strcpy(s-data,ch);r-next=s;r=s; r-next=NULL; scanf(“s,ch);retur

10、n head;新结点插入表尾尾指针r指向新的表尾读入下一个结点的值返回表头指针int Insert(ListNode *head)链表的插入ListNode *in,*p,*q;int wh;in=(ListNode *)malloc(sizeof(ListNode);in-next=NULL;生成新结点p=(ListNode *)malloc(sizeof(ListNode);p-next=NULL;q=(ListNode *)malloc(sizeof(ListNode);q-next=NULL; scanf(“ s”,in-data);输入插入的数据scanf(“ d”,&wh);插入输

11、入数据的位置for(p=head;wh0;p=p-next,wh-);q=p-next;p-next=in;in-next=q;void DeleteList(LinkList head,char *key)链表的删除ListNode *p,*r,*q=head;p=LocateNode(head,key);按 key 值查找结点if(p=NULL)exit(0);若没有找到结点，退出while(q-next!=p)/p为要删除的结点，q为p的前结点q=q-next;r=q-next;q-next=r-next;free(r);运行图9：處结旳实验Debuglinldist.exe話齬 数数数

12、数数数 AAAAAAA I主冃主冃主冃主冃主冃主月 、1XKaaabbbcccdddeeehe data is： aaa bbb.ccc Fddd, eee,请输入要删除的数据：bbbhe data is s aaaF ccc.ddd.eee.请输入插入的数据：xxxxxxdddeee 请输入你数据插入的位置：2The data is: aaa cccF Press &ny key to cont inue3、比较两者优缺点顺序存储结构:（1）空间利用率高（2）存取某个元素速度快（3）插入元素和删除元素存在元素移动，速度慢，耗时（4）有空间限制，当需要存储的元素个数可能多于顺序表的元素个数时，

13、会出现“溢出”问题,当元素个数少于预先分配的空间时，空间浪费大。链式存储结构：（1）占用额外的空间以存储指针（浪费空间）（2）存储某个元素速度慢（3）插入和删除元素速度快（4）没有空间限制，存储元素的个数无上限。实验报告四、实验小结（包括问题和解决方法、心得体会、意见与建议等）说明：这部分内容主要包括：在编程、调试或测试过程中遇到的问题及解决方法、本次实验的 心得体会、进一步改进的设想等。（一）实验中遇到的主要问题及解决方法粗心是实验中比较常见的错误，符号忘加或是打错。线性表的初始化为一个空表时，忘了要给空，以至于程序一直出错插入删除等操作非法时，忘了加返回值。我觉得在写函数时应该在草稿纸上画出简单的流程图，让思路更加清晰，在编写代码时也不会 出现较大的错误。（二）实验心得通过此次上机实验，我基本掌握了线性表的基本操作在顺序存储和链接存储上的实现，完成了本次实验的各种操作，了解了两种存储方式的定义和基本操作的实现，也知道了两者的优缺点。实践出真理，通过本次实验课，我的问题得到解决，希望在以后的学习中能有更好的成绩，逐 渐提高自己。成绩批阅人日期