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

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

2、言源代码，需加上详细注释；3、给出测试数据及运行结果、实验相关结论等；4、分析各主要算法的时间和空间复杂度（此为可选内容，不作要求）。（二）、内容1、顺序存储:#include<iostream>usingnamespacestd;intconstmaxsize=100;classsequentlistpublic:inta100;intlen;voidGet(sequentlistL)/线性表的最大可容纳量建立线性表的类线性表的实际长度/获取线性表中的元素for(inti=0;i<=L.len-1;i+)cout<<"线性表第"<<

3、;i+1<<”的元素是cin>>ai;cout<<endl;voidGetout(sequentlistL)cout<<"L="for(inti=0;i<=L.len-1;i+)输出线性表的元素(cout<<ai<<"")cout<<""cout<<endl;/查找元素x在线性表中的位置voidLocate(sequentlistL,intx)(inttemp=-1;for(inti=0;i<=L.len;i+)/如果x在顺序表

4、中就将序号记录在temp中(if(ai=x)temp=i;cout<<"元素"<<x<<"的位置是"<<temp<<endl;if(temp=-1)cout<<x<<"元素不在表中"<<endl;如果元素不存在就输出错误/将元素x插入到第i个位置voidInsert(sequentlist&L,intx,inti)if(L.len>=100)判断插入是否合法cout<<"顺序表已满！"<&

5、lt;endl;elseif(i<1)|(i>L.len+1)cout<<"插入的位置不合理！"<<endl;elsefor(intj=L.len;j>=i;j-)将i位置之后的元素后移一位L.aj+1=L.aj;L.ai=x;/将x插入到i位置L.len+;删除元素voidsequentlist:Delete(sequentlist&L,inti)if(i<0)|(i>=L.len+1)cout<<"删除位置不合法！"elsecout<<"删除第"

6、<<i<<"个位置元素"<<endl;for(intj=i;j<L.len-1;j+)将i位置之后的元素都前移一位aj=aj+1;L.len-;求交集操作voidIntersection(sequentlist&LA,sequentlist&LB,sequentlist&LC)inttemp=0;LC.len=0;将a中的元素赋给c中for(inti=0;i<LA.len;i+)LC.ai=LA.ai;LC.len=i;将b中的元素依次与c中的元素比较for(intj=0;j<LB.len;j+)

7、for(inti=0;i<LA.len;i+)if(LC.ai=LB.aj)temp+;if(temp=0)如果b中的元素j不在c中则将b中的元素放在LC.aLC.len=LB.aj;LC.len=LC.len+1;求并集voidsequentlist:Union(sequentlist&LA,sequentlist&LB,sequentlist&LC)inti,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<LB.len;j+

8、)(LC.aLC.len+j=LB.aj;)LC.len=i+j;/对c中的元素进行排序，升序排列for(intt=LC.len-1;t>0;t-)(for(j=0;j<t;j+)if(LC.aj>LC.aj+1)(inttemp;临时交换变量temp=LC.aj+1;LC.aj+1=LC.aj;LC.aj=temp;);voidmain()定义线性表LsequentlistL;L.len=10;/定义L的实际表长L.Get(L);控制台输入L的兀素L.Getout(L);输出插入后的线性表LL.Locate(L,10);查找兀素10是否在线性表中L.Insert(L,3,5

9、);/将兀素3查到第5个位直L.Getout(L);L.Delete(L,2);/删除L的第2个位置上的兀素L.Getout(L);/定义线性表sequentlistLA,LB,LC;LA.len=4;LA.Get(LA);LB.len=7;LB.Get(LB);求线性表的a与b并集，并逆序排列LC.Union(LA,LB,LC);LC.Getout(LC);求线性表a与b的交集LC.Intersection(LA,LB,LC);LC.Getout(LC);)运行图,CAPROGRAMFLESMCROSOFTVISUALSTUDIOMVPROJECTS1412Q10114120101Deh&#

10、187;l=l®jiSiy匹匹兀元元元兀一薪ILJ二-r-v二L二1,-1二一一0L，二LJ二_01234567891TlpgrgFgrgB-rgrB-rgFgr051土5lMlrn85l9lFI加JI餐JI汪51031表表表秦一二二一二-一一.，二一一.二二一二一h二TkHFIHH#二M4IJ七二|J3二kH二线线线线阳线线线统线78»10>67B910>78910>L=(1234S6阮素18的位置是9L=<123453网除第2个位置元素=£124536核性表第1的元素是实验报告2、链接存储LinkListcreatListR1()(用尾

11、插入法建立带头结点的单链表char*ch=newchar();LinkListhead=(LinkList)malloc(sizeof(ListNode);生成头结点*headListNode*s,*r,*pp;r=head;r->next=NULL;scanf(%s",ch);while(strcmp(ch,#")!=0)(pp=LocateNode(head,ch);尾指针初值指向头结点/读入第一个结点的值/输入影吉束if(pp=NULL)(s=(ListNode*)malloc(sizeof(ListNode);/生成新的结点*sstrcpy(s->dat

12、a,ch);r->next=s;r=s;r->next=NULL;scanf(%s",ch);returnhead;新结点插入表尾尾指针r指向新的表尾读入下一个结点的值/返回表头指针intInsert(ListNode*head)/链表的插入(ListNode*in,*p,*q;/生成新结点intwh;in=(ListNode*)malloc(sizeof(ListNode);in->next=NULL;p=(ListNode*)malloc(sizeof(ListNode);p->next=NULL;q=(ListNode*)malloc(sizeof(Li

13、stNode);q->next=NULL;scanf(%s”,in->data);输入插入的数据scanf(%d”,&wh);插入输入数据的位置for(p=head;wh>0;p=p->next,wh-);q=p->next;p->next=in;in->next=q;)voidDeleteLlst(LlnkLlsthead,char*key)链表的删除(ListNode*p,*r,*q=head;p=LocateNode(head,key);按key值查找结点if(p=NULL)exit(0);若没有找到结点，退出while(q->ne

14、xt!=p)p为要删除的结点，q为p的前结点q=q->next;r=q->next;q->next=r->next;free(r);)运行图节：激S绅3实心加bug'linW5tB1口|回月居居居居居居14ITTkra-rJ;JJ;I，卜rIFrITHrR-»-J-!Jr.tt投审/人入人人人人人abcdeabcdeabcdettbbbFddveee青输入要删除的数据bbbML请输入插入的数据IXXX请输入伤嗷据插入的位置2tW.eee,ressanykeytocontinue3、比较两者优缺点顺序存储结构：(1)空间利用率高(2)存取某个元素速度快(

15、3)插入元素和删除元素存在元素移动，速度慢，耗时(4)有空间限制，当需要存储的元素个数可能多于顺序表的元素个数时，会出现“溢出”问题,当元素个数少于预先分配的空间时，空间浪费大。链式存储结构：(1) 占用额外的空间以存储指针(浪费空间)(2) 存储某个元素速度慢(3) 插入和删除元素速度快(4) 没有空间限制，存储元素的个数无上限。实验报告10四、实验小结（包括问题和解决方法、心得体会、意见与建议等）说明：这部分内容主要包括：在编程、调试或测试过程中遇到的问题及解决方法、本次实验的心得体会、进一步改进的设想等。（一）实验中遇到的主要问题及解决方法粗心是实验中比较常见的错误，符号忘加或是打错。线性