实验1-线性结构

实验项目名称：线性结构实验学时：8同组学生姓名：孙沛╱实验地点：1314实验日期：2018.10.18—2018.11.8实验成绩：批改教师：批改时间：实验一线性结构一、实验目的和要求1、实验目的(1)掌握顺序表的定位、插入、删除等操作。(2)掌握单链表的定位、插入、删除等操作。(3)掌握应用栈解决问题的方法；掌握利用栈进行表达式求解的算法；掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。(4)掌握串的存储及应用。2、实验要求(1)注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。(2)链表不能实现直接定位，一定注意指针的保存，防止丢失。二、实验仪器和设备VisualC++6.0三、实验内容与过程（含程序清单及流程图）（一）顺序表1、必做题(1)编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。(2)编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。(3)在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。(4)删除顺序表中所有等于x的数据元素。2、选做题：已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。（二）单链表1、必做题(1)编写程序建立一个单链表，并逐个输出单链表中所有数据元素。(2)在递增有序的单链表中插入一个新结点x，保持单链表的有序性。解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。(3)编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。2、选做题：已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表LA中删除自第i个元素起共len个元素后，将它们插入到表LB中第j个元素之前。（三）栈和队列1、必做题(1)判断一个算术表达式中开括号和闭括号是否配对。(2)测试“汉诺塔”问题。(3)假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。2、选做题：在顺序存储结构上实现输出受限的双端循环队列的入列和出列算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。（四）串1、必做题(1)编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。(2)编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。(3)设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。2、选做题：假设以链结构表示串，编写算法实现将串S插入到串T中某个字符之后，若串T中不存在这个字符，则将串S联接在串T的末尾。提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单：（一）顺序表(1)编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。#includestdio.htypedefintdatatype;#definemaxsize1024typedefstruct{datatypedata[maxsize];intlast;}sequenlist;intmain(){sequenlistL;inti,n;printf(请输入元素个数：);scanf(%d,&n);printf(\n请输入元素：);for(i=0;in;i++)scanf(%d,,&L.data[i]);printf(元素输出：);for(i=0;in;i++)printf(%d\t,L.data[i]);printf(\n);}(2)编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。（2）#includestdio.htypedefintdatatype;#definemaxsize1024typedefstruct{datatypedata[maxsize];intlast;}sequenlist;intfun(sequenlistL,intx,intn){inti;for(i=0;in;i++)if(L.data[i]==x)returni;return-1;}intmain(){sequenlistL;inti,n,y;intx;printf(输入元素个数：);scanf(%d,&n);for(i=0;in;i++){scanf(%d,,&L.data[i]);}printf(\n输入查找元素：);scanf(%d,&x);y=fun(L,x,n);if(y==-1)printf(\n数据元素%d位置为-1\n,x);elseprintf(\n数据元素%d位置为%d\n,x,y);}(3)在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。#includestdio.h#definemaxsize100typedefstruct{intdata[maxsize];intlast;}sequenlist;main(){inti,x,j;sequenlistl={{11,12,14,15,16,17,18},6};printf(原数据为:);for(i=0;i=l.last;i++)printf(%2d,l.data[i]);printf(\n插入元素为：);scanf(%d,&x);for(i=1;i=l.last;i++)if(l.data[i-1]x)break;if(il.last){l.data[l.last+1]=x;}else{for(j=l.last;j=i-1;j--)l.data[j+1]=l.data[j];l.data[i-1]=x;}l.last++;printf(\n插入后数据为：\n);for(j=0;j=l.last;j++)printf(%3d,l.data[j]);printf(\n);return0;}(4)删除顺序表中所有等于x的数据元素。#includestdio.h#definemaxsize100typedefstruct{intdata[maxsize];intlast;}sequenlist;main(){inti,j,x=0,k=0;sequenlistL={{1,3,5,7,2,4,6,8,2,9},9};printf(\n原数据:);for(i=0;i=L.last;i++)printf(%3d,L.data[i]);printf(\n删除元素：);scanf(%d,&x);for(i=1;i=L.last+1;i++)if(L.data[i-1]==x){for(j=i;j=L.last+1;j++)L.data[j-1]=L.data[j];L.last--;i--;k=1;}if(k==1){printf(删除后元素为：\n);for(j=0;j=L.last;j++)printf(%3d,L.data[j]);}elseprintf(Notfound!\n);printf(\n);}（二）单链表1、必做题(1)编写程序建立一个单链表，并逐个输出单链表中所有数据元素。#includestdlib.h#includestdio.htypedefintdatattype;typedefstructnode{chardata;structnode*next;}linklist;main(){charch;linklist*head,*s,*r,*p;head=(linklist*)malloc(sizeof(linklist));r=head;scanf(%c,&ch);while(ch!='$'){s=(linklist*)malloc(sizeof(linklist));s-data=ch;r-next=s;r=s;scanf(%c,&ch);}r-next=NULL;r=head-next;while(r!=NULL){printf(%c,r-data);r=r-next;}}(2)在递增有序的单链表中插入一个新结点x，保持单链表的有序性。#includestdio.h#includestdlib.htypedefintdatattype;typedefstructnode{intdata;structnode*next;}linklist;main(){intx,y;linklist*head,*s,*r,*p,*q,*m,*n;head=(linklist*)malloc(sizeof(linklist));r=head;printf(输入：);scanf(%d,&x);while(x!=0){s=(linklist*)malloc(sizeof(linklist));s-data=x;r-next=s;r=s;scanf(%d,&x);}r-next=NULL;printf(插入：);scanf(%d,&y);p=head-next;while(p!=NULL){if(p-datay)p=p-next;elsebreak;}q=(linklist*)malloc(sizeof(linklist));q-data=y;m=head;while(m-next!=p)m=m-next;q-next=p;m-next=q;n=head-next;printf(序列为：);while(n!=NULL){printf(%3d,n-data);n=n-next;}}(3)编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。#includestdio.h#includestdlib.htypedefintdatattype;typedefstructnode{intdata;structnode*next;}linklist;main(){inta;linklist*head,*s,*r,*p,*q,*t;head=(linklist*)malloc(sizeof(linklist));r=head;printf(输入：);scanf(%d,&a);while(a!=0){s=(linklist*)malloc(sizeof(linklist));s-data=a;r-next=s;r=s;scanf(%d,&a);}r-next=NULL;printf(\n序列为：\n);p=head-next;while(p){printf(%d,p-data);p=p-next;}p=head-next;q=p-next;while(q!=NULL){t=q-next;q-next=p;p=q;q=t;}head-next-next=NULL;head-next=p;printf(\n转换后：\n);p=head-next;while(p!=NULL){printf(%d,p-data);p=p-next;}}（三）栈和队列(1)判断一个算术表达式中开括号和闭括号是否配对。#includestdio.h#includestdlib