实验一 线性表的基本操作及应用.doc

数据结构实验报告(实验一&实验二)班级:软件121学号:4122姓名:程猛实验一线性表的基本操作及应用【实验目的】理解线性表的逻辑结构特性是数据元素之间存在着线性关系,掌握顺序表的特点是逻辑上相邻的元素的存储地址也相邻,熟练掌握线性表的查找、插入和删除等算法并灵活运用这些算法。【实验内容】(任选一题)1、建立一个顺序表,要求完成以下操作:实现顺序表的初始化、销毁顺序表、重置顺序表为空表、判断顺序表是否是空表、求顺序表的元素个数、取顺序表中的一个数据、查找顺序表中的一个元素值、查找某一位置元素的前驱和后继、将一个值插入到指定的位置、删除指定位置的元素。按此方法定义另一个顺序表,实现两个顺序表的合并;如果这两个顺序表元素值是有序的,实现这两个顺序表的合并,并使合并后的数据也是有序排列的。要求(a)顺序表的初始状态可直接赋值,也可将初态置为空表,从键盘读入数据元素。(b)每做一次操作将结果打印出来。2、建立单链表L(分别采用头插法和尾插法),打印单链表中的数据、打印单链表长度、按值查找元素、按位置取元素、插入结点和删除结点。(a)初始将单链表置空(b)在单链表中插入元素(c)按值查找元素(d)按位置取元素(e)插入结点(f)删除结点3、以循环单链表为存储结构,编写程序求解约瑟夫问题。编号为1,2,···,n的n个人围坐在一圆桌旁,从第s个人开始报数,报到第m的人退席,下一个人又重新从1开始报数,依此重复,直至所有的人都退席。要求(a)循环单链表的初始状态可直接赋值,也可将初态置为空表,从键盘(文件)读入数据元素。(b)输出删除元素的顺序(c)分析算法的时间性能【源代码】#include""#include<>#include<>#defineSIZE10#defineREMENT5typedefstruct{ int*elem; intlength; intlsize;}Sqlist;SqlistL;voidstate_initlist(Sqlist&L)//线性表的初始化{ =(int*)malloc(SIZE*sizeof(int)); =0; =SIZE; }voidcreatlist(Sqlist&L)//线性表的建立{ int*p; inte; =(int*)malloc(sizeof(int)); printf("请输入线性表的数据:\n"); scanf_s("%d",&e); *()=e; for(inti=1;i<10;i++) { p=(int*)malloc(sizeof(int)); scanf_s("%d",p); e=*p; *(+i)=e; ++; }}intinsertelem(Sqlist&L,inti,inte)//插入{ int*p,*q; if(i<0||i>-1) exit(0); if(>=) { =(int*)realloc(,(+REMENT)*sizeof(int)); if(!) exit(0); +=REMENT; } q=+i; for(p=+;p>=q;p--) { *(p+1)=*p; } *q=e; ++; return0;}intdeletlist(Sqlist&L,inti)//删除{ int*p,*q; inte; if(i<0||i>) exit(0); q=+i; e=[i]; for(p=+;q<=p;q++) *q=*(q+1); --; return0;}voidmain(){ inti,a,b,k;//(1) do { printf("请选择要进行的操作:.\n"); scanf("%d",&k); switch(k) {case1:state_initlist(L);break; case2:creatlist(L);break; case3: state_initlist(L);//(3) creatlist(L);//(4) printf("请输入插入线性表的位置i的值:\n");//(5) scanf_s("%d",&i);//(7) printf("请输入要插入线性表的值:\n");//(8) scanf_s("%d",&a);//(9) b=insertelem(L,i,a);//(10) printf("输出新的线性表的