《数据结构》实验2顺序表答案

《数据结构》实验2顺序表答案实验报告《数据结构》实验2顺序表答案全文共11页，当前为第1页。院（系）：课程名称：数据结构日期：《数据结构》实验2顺序表答案全文共11页，当前为第1页。班级学号实验室专业计算机科学与技术姓名计算机号实验名称顺序表的运算成绩评定所用软件VC或TC教师签名实验目的掌握顺序表的基本概念掌握顺序表的建立、插入和删除等方法。掌握顺序表的基本算法。实验准备复习书上有关内容。阅读实验步骤中的函数，写出函数功能。写出实验的源程序。实验1.各子函数功能：*init_sqlist()顺序表的初始化creatsqlist(sqlist*L)顺序表的建立Location_sqlist(sqlist*L,intx)在顺序表中查找指定元素InsList(sqlist*L,inti,intx)将x插入到顺序表的第i个位置2.源程序以及运行结果如下：#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}SeqList;SeqList*init_sqlist(){SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));L->last=-1;returnL;}voidcreatsqlist(SeqList*L){inti;printf("请输入最后一个元素的下标");scanf("%d",&(L->last));printf("请输入%d个元素",L->last+1);for(i=0;i<=L->last;i++)scanf("%d",&(*L).elem[i]);}intDelList(SeqList*L,inti,elemtype*e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1*/{ intk; if((i<1)||(i>L->last+1)) { printf("删除位置不合法!"); return(0); } *e=L->elem[i-1];/*将删除的元素存放到e所指向的变量中*/ for(k=i;k<=L->last;k++) L->elem[k-1]=L->elem[k];/*将后面的元素依次前移*/ L->last--; return(1);}voidmain() {inti,x,j;SeqList*a;a=init_sqlist();creatsqlist(a);printf("\n建立的顺序表为：\n");for(i=0;i<=a->last;i++) printf("%d",a->elem[i]);printf("\n请问想要删除第几个元素？\n");scanf("%d",&j);if(DelList(a,j,&x))printf("\n被删除的元素是%d\n",x);/*执行函数调用*/printf("\n删除后的顺序表为：\n");for(i=0;i<=a->last;i++) printf("%d",a->elem[i]);printf("\n");}《数据结构》实验2顺序表答案全文共11页，当前为第2页。《数据结构》实验2顺序表答案全文共11页，当前为第2页。3.源代码如下：#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;sqlist*init_sqlist(){sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;returnL;}voidcreatsqlist(sqlist*L){inti; printf("请输入线性表的长度\n"); scanf("%d",&i); L->last=i-1; printf("请输入线性表中的各元素值，注意：必须有序\n"); for(i=0;i<=L->last;i++) scanf("%d",&(*L).elem[i]);}void merge(sqlist*LA,sqlist*LB,sqlist*LC){ inti,j,k; i=0;j=0;k=0; while(i<=LA->last&&j<=LB->last) if(LA->elem[i]<=LB->elem[j]) { LC->elem[k]=LA->elem[i]; i++; k++; } else { LC->elem[k]=LB->elem[j]; j++; k++;} while(i<=LA->last) /*当表LA有剩余元素时，则将表LA余下的元素赋给表LC*/ {《数据结构》实验2顺序表答案全文共11页，当前为第3页。 LC->elem[k]=LA->elem[i];《数据结构》实验2顺序表答案全文共11页，当前为第3页。 i++; k++; } while(j<=LB->last)/*当表LB有剩余元素时，则将表LB余下的元素赋给表LC*/ { LC->elem[k]=LB->elem[j]; j++; k++; } LC->last=LA->last+LB->last+1;}voidmain() {inti,x,j;sqlist*a,*b,c;printf("\n*******建立顺序表a********\n");a=init_sqlist();creatsqlist(a);printf("\n建立的顺序表a为：\n");for(i=0;i<=a->last;i++) printf("%d",a->elem[i]);printf("\n*******建立顺序表b********\n");b=init_sqlist();creatsqlist(b);printf("\n建立的顺序表b为：\n");for(i=0;i<=b->last;i++) printf("%d",b->elem[i]);merge(a,b,&c);printf("\n合并后的顺序表为：\n");for(i=0;i<=c.last;i++) printf("%d",c.elem[i]);printf("\n");《数据结构》实验2顺序表答案全文共11页，当前为第4页。}《数据结构》实验2顺序表答案全文共11页，当前为第4页。4.源程序为：#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;intInsList(sqlist*l,elemtypex){inti;if(l->last==MAXSIZE-1)return0;for(i=l->last;l->elem[i]>x&&i>=0;i--)l->elem[i+1]=l->elem[i];l->last++;l->elem[i+1]=x;return1;}voidmain() /*顺序表插入的主函数*/{inti,x;sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;printf("请输入元素的个数\n");scanf("%d",&x);for(i=0;i<x;i++){L->elem[i]=i*3;L->last=L->last+1;}printf("\n建立的顺序表为\n");for(i=0;i<=L->last;i++)printf("%d",L->elem[i]);《数据结构》实验2顺序表答案全文共11页，当前为第5页。printf("\n");《数据结构》实验2顺序表答案全文共11页，当前为第5页。printf("\n请输入要插入的数\n");scanf("%d",&x);InsList(L,x);/*执行函数调用*/printf("\n插入元素%d后的顺序表为\n",x);for(i=0;i<=L->last;i++)printf("%d",L->elem[i]);printf("\n");}5.将顺序表(a1，a2，...，an)重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值都比a1大(这里假设数据元素的类型具有可比性,不妨设为整型)基本思路：从第二个元素开始到最后一个元素，逐一向后扫描：（1）当前数据元素aI比a1大时，表明它已经在a1的后面，不必改变它与a1之间的位置，继续比较下一个。（2）当前结点若比a1小，说明它应该在a1的前面，此时将它上面的元素都依次向下移动一个位置，然后将它置入最上方。源程序如下：#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;//顺序表结构体类型的定义sqlist*init_sqlist()//顺序表的初始化{sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;returnL;}voidcreatsqlist(sqlist*L)//顺序表的建立《数据结构》实验2顺序表答案全文共11页，当前为第6页。{inti;《数据结构》实验2顺序表答案全文共11页，当前为第6页。printf("请输入顺序表中最后一个元素的下标\n");scanf("%d",&(*L).last);printf("请输入%d个元素\n",L->last+1);for(i=0;i<=(*L).last;i++)scanf("%d",&(*L).elem[i]);}voidpart(sqlist*L)//顺序表的拆分{inti,j;elemtypex,y;x=L->elem[0];/*将基准置入x中*/for(i=1;i<=L->last;i++)if(L->elem[i]<x)/*当前元素小于基准*/{y=L->elem[i];for(j=i-1;j>=0;j--)/*移动*/L->elem[j+1]=L->elem[j];L->elem[0]=y; }}voiddayin(sqlist*a){inti;for(i=0;i<=a->last;i++)printf("%d",a->elem[i]);//顺序表的输出printf("\n");}voidmain() /*顺序表的主函数*/{sqlist*a;a=init_sqlist();//调用函数对顺序表的初始化creatsqlist(a);//建立顺序表printf("建立的顺序表为：\n");dayin(a);//输出顺序表part(a);//顺序表的拆分printf("拆分后的顺序表为：\n");dayin(a);//输出拆分后的线性表《数据结构》实验2顺序表答案全文共11页，当前为第7页。}《数据结构》实验2顺序表答案全文共11页，当前为第7页。其中拆分函数还可以用如下方式实现，请比较两种算法的效率，即算法法的时间复杂度分析voidpart(sqlist*L){inti,j,k;elemtypex,y;x=L->elem[0];i=1;j=L->last;k=0;while(L->elem[j]>x)j--;if(i<j){L->elem[k]=L->elem[j];k=j;}while(L->elem[i]<=x)i++;if(i<j){L->elem[k]=L->elem[i];k=i;}L->elem[k]=x;}6.编写程序从一给定的顺序表A中删除值在x，y(x<=y)之间的所有元素。提示：1）方法：逐一比较每个元素的值，若元素值在X，Y之间，则删除。2）主函数的编写可模仿第一题#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;//顺序表结构体类型的定义sqlist*init_sqlist()//顺序表的初始化{sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;returnL;《数据结构》实验2顺序表答案全文共11页，当前为第8页。}《数据结构》实验2顺序表答案全文共11页，当前为第8页。voidcreatsqlist(sqlist*L)//顺序表的建立{inti;printf("请输入顺序表中最后一个元素的下标\n");scanf("%d",&(*L).last);printf("请输入%d个元素\n",L->last+1);for(i=0;i<=(*L).last;i++)scanf("%d",&(*L).elem[i]);}voiddele(sqlist*L)//顺序表的删除{inti,j;intx,y;printf("请输入要删除的值的下界");scanf("%d",&x);printf("请输入要删除的值的上界");scanf("%d",&y);for(i=0;i<=L->last;i++)if(L->elem[i]>=x&&L->elem[i]<=y){for(j=i;j<=L->last;j++)L->elem[j]=L->elem[j+1];L->last--; i--; }}voiddayin(sqlist*a){inti;for(i=0;i<=a->last;i++)printf("%d",a->elem[i]);//顺序表的输出printf("\n");}voidmain() /*顺序表的主函数*/{sqlist*a;a=init_sqlist();//调用函数对顺序进行初始化creatsqlist(a);//建立顺序表printf("建立的顺序表为：\n");dayin(a);//输出顺序表dele(a);//删除顺序表指定范围内的数printf("删除后的顺序表为：\n");dayin(a);//输出删除后的线性表}《数据结构》实验2顺序表答案全文共11页，当前为第9页。《数据结构》实验2顺序表答案全文共11页，当前为第9页。7.编写程序，将给定的顺序表逆置。例如：顺序表中的元素为：247191238逆置后为：831291742#defineMAXSIZE100#include"stdio.h"#include"stdlib.h"typedefintelemtype;typedefstruct{elemtypeelem[MAXSIZE];intlast;}sqlist;//顺序表结构体类型的定义sqlist*init_sqlist()//顺序表的初始化{sqlist*L;L=(sqlist*)malloc(sizeof(sqlist));L->last=-1;returnL;}voidcreatsqlist(sqlist*L)//顺序表的建立{inti;printf("请输入顺序表中最后一个元素的下标\n");scanf("%d",&(*L).last);printf("请输入%d个元素\n",L->last+1);for(i=0;i<=(*L).last;i++)scanf("%d",&(*L).elem[i]);}voidinver(sqlist*L)//顺序表的逆置{inti;elemtypet;for(i=0;i<=L->last/2;i++){t=L->elem[i];L->elem[i]=L->elem[L->last-i];L->elem[L->last-i]=t;}}voidshowsqlist(sqlist*a){inti;for(i=0;i<=a->last;i++)printf("%d",a->elem[i]);//顺序表的输出printf("\n");}voidmain() /*顺序表的主