《2023年顺序表链表KMP实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年顺序表链表KMP实验报告.pdf（88页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、附 件（四）深 圳 大 学 实 验 报 告课程名称:数据结构实验与课程设计实验项目名称：顺序表、链表、堆栈队列、串K M P算法学院2 _专业2 _指导教师2 _报告人j学号 班级：实验时间：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _实验报告提交时间:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _教务处制一、实验目的与完毕说明：1.简朴介绍本实验的重要目的2.说明你自己在本次实验中完毕了第几项规定（必填）D S实验0
2、 1 顺序表1.Problem A:DS顺序表-一类实现目的：（1）实现顺序表的用C+语言和类实现顺序表（2）属性涉及:数组、实际长度、最大长度（设定为100 0）（3）操作涉及：创建、插入、删除、查找规定：I nput第 1 行先输入n 表达有n 个数据，即 n 是实际长度;接着输入n 个 数 据（完毕）第 2 行输入要插入的位置和新数据（完毕）第 3 行输入要插入的位置和新数据（完毕）第 4 行输入要删除的位置（完毕）第 5 行输入要删除的位置（完毕）第 6 行输入要查找的位置（完毕）第 7 行输入要查找的位置（完毕）Output第 1 行输出创建后的顺序表内容，涉及顺序表实际长度和数据（
3、完毕）每成功执行一次操作（插入或删除），输出执行后的顺序表内容（完毕）每成功执行一次查找，输出查找到的数据（完毕）假如执行操作失败（涉及插入、删除、查找等失败），输出字符串e r r o r,不必输出顺序表内容（完毕）2.P r o b l e m B:D S 顺序表一连续操作目的：（1）建立顺序表的类，属性涉及:数组、实际长度、最大长度（设定为1000）（2）实现连续多个插入，即从位置i 开始插入多个数据（3）实现连续多个删除，即从位置i 开始删除多个数据规定：I n p u t第 1 行先输入n 表达有n 个数据，即 n 是实际长度；接着输入n 个数据（完毕）第 2 行先输入i 表达插入开
4、始的位置，再输入k 表达有k 个插入数据,接着输入k个 数 据（完毕）第 3 行先输入i 表达删除开始的位置，再输入k 表达要删除k 个 数 据（完毕）O u t p u t顺序表内容涉及顺序表的实际长度和数据，数据之间用空格隔开（完毕）第 1 行输出创建后的顺序表内容（完毕）第 2 行输出执行连续插入后的顺序表内容（完毕）第 3 行输出执行连续删除后的顺序表内容（完毕）3.Prob lem C:DS顺序表-合并操作目的：(1)建立顺序表的类，属性涉及：数组、实际长度、最大长度(设定为1 0 00)(2)已知两个递增序列，把两个序列的数据合并到顺序表中，(3)并使得顺序表的数据递增有序。规定：
5、In p ut第 1行先输入n 表达有n 个数据，接着输入n 个数据，表达第1个序列，规定数据递增互不等(完毕)第 2 行先输入m 表达有m个数据，接着输入m个数据，表达第2 个序列，规定数据递增互不等(完毕)Out p ut顺序表内容涉及顺序表的实际长度和数据，数据之间用空格隔开(完毕)第 1行输出创建后的顺序表内容(完毕)DS实验02-一链表1.P roblem A:DS单链表一类实现目的：(1)用 C+语言和类实现单链表，含头结点(2)属性涉及:dala数据域、n e xt指针域（3）操作涉及:插入、删除、查找（4）注意：单链表不是数组，所以位置从1 开始相应首结点，头结点不放数据规定：
6、Inp u t第 1 行先输入n 表达有n 个数据，接着输入n 个数据（完毕）第 2 行输入要插入的位置和新数据（完毕）第 3 行输入要插入的位置和新数据（完毕）第 4 行输入要删除的位置（完毕）第 5 行输入要删除的位置（完毕）第 6 行输入要查找的位置（完毕）第 7 行输入要查找的位置（完毕）0utput数据之间用空格隔开,（完毕）第 1 行输出创建后的单链表的数据（完毕）每成功执行一次操作（插入或删除），输出执行后的单链表数据（完毕）每成功执行一次查找，输出查找到的数据（完毕）假如执行操作失败（涉及插入、删除、查找等失败），输出字符串erro r,不必输出单链表（完毕）2.Probl e
7、 m B:DS单链表一结点互换目的:（1）用 C+实现含头结点的单链表，然后实现单链表的两个结点互换位置。(2)注意不能简朴互换两个结点包含数据，必须通过修改指针来实现两个结点的位置互换(3)互换函数定义可以参考：(4 )sw a p(in t pa,in t pb)p a和 pb表达两个结点在单链表的位置序号(5)s wap(List Node*p,L i s tNode*q)P 和q 表达指向两个结点的指针规定：In p u t第 1 行先输入n 表达有n 个数据，接着输入n 个 数 据(完毕)第 2 行输入要互换的两个结点位置(完毕)第 3 行输入要互换的两个结点位置(完毕)O ut p
8、 ut第一行输出单链表创建后的所有数据，数据之间用空格隔开(完毕)第二行输出执行第1 次互换操作后的单链表数据，数据之间用空格隔开(完毕)第三行输出执行第2 次互换操作后的单链表数据，数据之间用空格隔开(完毕)假如发现输入位置不合法，输出字符串er r or,不必输出单链表(完毕)3.P r o b lem C:D S单链表一合并目的：(1)假定两个单链表是递增有序，定义并实现以下函数，完毕两个单链表的合并，继续保持递增有序(2)int L L _me r ge(L is t N o de*La,L i stN o d e *L b)规定：Input第 1 行先输入n表达有n个数据，接着输入n
9、个 数 据（完毕）第 2 行先输入m表达有M 个数据，接着输入m个数据（完毕）Out p ut输出合并后的单链表数据，数据之间用空格隔开（完毕）4.Problem D:DS线性表一多项式相加目的：（1）对于一元多项式 P （x）=p O+p l x+p 2 x 2+p n x n ，每个项都有系数和指数两部分,例如p 2x 2 的系数为p 2,指数为2（2）编程实现两个多项式的相加例如 5+x +2 x 2+3 x 3,-5 x+6 x 2+4 x 4,两者相力口结果：8 x 2 +3 x 3+4 x 4（3 ）其中系数5和一 5 都是x的 0次方的系数，相加后为0,所以不显示。x的 1次方同
10、理不显示。（4）可用顺序表或单链表实现规定：I nput第 1 行:输入t 表达有t 组测试数据（完毕）第 2行：输入n 表达有第1 组的第1 个多项式包含n 个项（完毕）第 3行：输入第一项的系数和指数，以此类推输入口行（完毕）接着输入m表达第1 组的第2个多项式包含m项（完毕）同理输入第2个多项式的m个项的系数和指数（完毕）参考上面输入第2组数据，以此类推输入t 组（完毕）假设所有数据都是整数（完毕）0 u t p u t对于每1 组数据，先用两行输出两个本来的多项式,再用一行输出运算结果,不必考虑结果全为0的 情 况（完毕）输出格式参考样本数据，格式规定涉及：1 .假如指数或系数是负数，
11、用小括号括起来（完毕）2 .假如系数为0,则该项不用输出（完毕）3 .假如指数不为0,则用符号一表达,例如x的 3次方,表达为x 3（完毕）4.多项式的每个项之间用符号+连接,每个+两边加1 个空格隔开（完毕）D S 实验0 3一堆栈与队列1.P r o b l e m A:D S 堆栈一逆序输出（S T L栈使用）目的：（1）C+中已经自带堆栈对象s t a c k,无需编写堆栈操作的具体实现代码。（2）本题目重要帮助大家熟悉s t a c k 对象的使用,然后实现字符串的逆序输出（3）输入一个字符串，按字符按输入顺序压入堆栈，然后根据堆栈后进先出的特点,做逆序输出规定：I np u t第一
12、行输入t,表达有t个测试实例（完毕）第二起，每一行输入一个字符串，注意字符串不要包含空格（完毕）O u t p u t每行逆序输出每一个字符串（完毕）2.P r o b l e m B:D S线性表综合练习一队列之银行排队目的：（1 ）在银行营业大厅共服务3种客户，类型为ABC,大厅分别设立了 3个窗口分别服务三种客户，即每个窗口只服务一种客户。现有一批客户来银行办理业务，每个客户都有类型和办理业务时间。每个窗口按照客户到来的顺序进行服务。规定：I np u t第一行输入先输入n表达客户数量（完毕）第二行输入每个客户的类型,数据之间用用空格隔开（完毕）第三行输入每个客户的办理时间，数据之间用用
13、空格隔开（完毕）O u t p u t第一行输出A类客户的平均办理时间（完毕）第二行输出B类客户的平均办理时间（完毕）第三行输出C类客户的平均办理时间（完毕）3.P r o b l e m C:D S堆栈一行编辑目的:(1)使用C+的 S T L 堆栈对象，编写程序实现行编辑功能。行编辑功能是：当输入#字符，则执行退格操作;假如无字符可退就不操作，不会报错(2)本程序默认不会显示#字符,所以连续输入多个#表达连续执行多次退格操作(3)每输入一行字符打回车则表达字符串结束(4)注意：必须使用堆栈实现,并且结果必须是正序输出规定：I np u t第一行输入一个整数t,表达有t 行字符串要输入(完毕
14、)第二行起输入一行字符串，共输入t 行(完毕)0 u t p u t每行输出最终解决后的结果,假如一行输入的字符串通过解决后没有字符输出，则直接输出 N UL L (完毕)4.P r o b l e m D:D S线性表综合练习-数制转换目的：(1)对于任意十进制数转换为k 进制,涉及整数部分和小数部分转换。整数部分采用除 k求余法，小数部分采用乘k 取整法例如x=1 9 .1 2 5,求 2 进制转换整数部分1 9,。小数部分0.1 2 51 99 /4/2 /1/2 =9 1 2.1 2 5 *2 =0.2 5 02 =4 1“。0.2 5 *2 =0.5 02 =2 3 0。0.5 *2
15、 =1 12 =1 0/2 =0 1(2)所以整数部分转为1 0 0 1 1 ,小数部分转为0.0 0 1,合起来为1 0 0 1 1.0 0 1(3 )提醒整数部分可用堆栈，小数部分可用队列实现(4)注意:必须按照上述方法来实现数制转换，其他方法0 分规定：I n p u t第一行输入一个t,表达下面将有t组测试数据。（完毕）接下来每行包含两个参数n和k,n表达要转换的数值，也许是非整数；k表达要转换的数制6（完毕）O u t p u t对于每一组测试数据，每行输出转换后的结果,结果精度到小数点后3位（完毕）5.P r o b 1 e m E:D S 堆栈一括号匹配目的：（1）解决表达式过程
16、中需要对括号匹配进行检查，括号匹配涉及三种：“（”和“）”,“广和”和 例 如 表 达 式 中 包 含 括 号 如 下：（）（。）（小）。1。2。3必。5 6 7 8。9。1 0 1 1 1 2（2）从上例可以看出第1和第2个括号匹配，第3和 第10个括号匹配,4和5匹配,6和9匹配，7和8匹配,11和1 2匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的解决这种括号匹配检查，可以遵循以下规则：1、当接受第1个左括号，表达新的一组匹配检查开始；随后假如连续接受到左括号，则不断进堆栈。2、当接受第1个右括号，则和最新进栈的左括号进行匹配，表达嵌套中1组括号已经匹配消除3、若到
17、最后,括号不能完全匹配，则说明输入的表达式有错（3）建议使用C+自带的s t ack对象来实现规定：In p u t第一行输入一个t,表达下面将有t 组测试数据。接下来的t 行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入（完毕）0 u t p ut对于每一行的表达式，检查括号是否匹配，匹配则输入ok,不匹配则输出error（完毕）6.Problem F:DS线性表综合练习一组队列目的：（1）组队列是队列结构中一种常见的队列结构，在很多地方有着广泛应用。组队列是是指队列内的元素分组聚集在一起。组队列包含两种命令：I、ENQUEUE,表达当有新的元素进入队列，一方面会检
18、索是否有同一组的元素已经存在，假如有,则新元素排在同组的最后，假如没有则插入队列末尾。2、DEQUEUE,表达队列头元素出队3、STOP,停止操作（2）建议使用C+自带的队列对象queue,编程更方便规定：Input第 1 行输入一个t（t=10）,表达1 个队列中有多少个组（完毕）第 2 行输入一个第1组的元素个数和数值第3 行输入一个第2 组的元素个数和数值，（完毕但不严谨）以此类推输入完n 组之后，开始输入多个操作命令（d a ta；p-d a ta=q d a ta;q-d a ta=te m p;r e t u r n o k ;)3.Pr oblem C:DS单链表一合并过程基本与
19、线性表合并相同。不同的是需要调整指针。4.Problem D:DS线性表-多项式相加线性表实现：建立两个数组分别存储系数和指数。多项式相加的操作过程基本与合并相似。先比较指数，若指数较小就插在最左边，若指数相等则相加再插入。一条多项式插完后另一条多项式剩余系数指数插在右边。链表实现：St a tu s Ma k e No d e (L i n k&p ,El e m Ty p e e,El e m T y p e e 1);分派一个结点Sta tu s Cr e a tPo l y n(p o l y n o m a i&P,L i n k&p );将结点插入多项式中。插入过程中比较指数大小按
20、由小到大的顺序插在相应的位置里,假如有相同指数的则系数相加(系数可为正负)，若系数为0 则调用删除函数删除该结点。S t a tu s A d d Po l y n (p o l y n o m a i&Pa,p o l y n o m a i&Pb,p o 1 y n o m a i&Pc);多项式相加。比线性表要简朴,直接把Pa,Pb 里的系数跟指数创建一个结点放入多项式P c中即可,相加直接在加入的时候完毕。DS实验03-堆栈与队列1.Pr o b 1 e m A:D S 堆栈一逆序输出(STL 栈使用)建立一个栈，将数值p u s h。进栈后用to p。返回值并p o p()弹出值逆向
21、输出。2.Pr o b l e m B:DS线性表综合练习一一队列之银行排队建立两个队列，一个为,另一个为,用于存储时间和字符，在一个个用f r o n t。取值并用p o p。弹出，用判断语句进行平均数求值。3.Pr o b l e m C:DS堆栈-行编辑建立两个栈，用其中一个栈存储s tr i n g 数组的每一个字符。先判断是否为#号且有多少个#号，若没有#号则p u s h ()字符进第二个栈，有多少个#号就P O P。多少个。全程判断栈是否为空。最后判断第二个栈是否为空，不为空就输出字符串，为空就输出NUL L。4.Pr o b l e m D:DS线性表综合练习一数制转换Pu s
22、 h 数值与进制数的余数进栈然后逆向输出。Pu s h数值与2的倍数取整进栈然后逆向输出。5.Pr o b l e m E：DS堆栈一括号匹配若栈为空时下一个就是右括号直接括号不匹配。若是左括号则进栈。一直进左括号知道有右括号出现。若右括号与to p ()匹配则P o p ()o若括号匹配则栈为空。6.Pr o b l e m F:D S 线性表综合练习-一组队列建立队列数组，同组的元素进入同一个队列中。7.Pr o b l e m G:D S 堆栈 表达式计算使用O P T R栈存储运算符，使用O P N D栈存储数字。0 P T R 先 P U S H 入#号，输入表达式时最后一位为#号，
23、在 c=0P T R.t o p()=#的时候结束表达式计算。读入字符的过程中不断有运算符和数字进栈，直到两个运算符遭遇的时候，判断栈内t o p ()运算符与c内运算符的优先级,即表达式中前一个运算符与后一个运算符的优先级。假如是小于，则直接让c 进 0P T R 栈，再读入下一个字符；假如是大于，则 0 PTR弹出一个运算符，OPND弹出两个数字进行计算求值重新放回0P N D 栈；假如是等于则O P T R出栈消除括号。只有左括号和右括号以及两个#号的优先级为等于号。而右括号出现的时候左括号以后的运算符都已计算并变成数字进入了 O P N D 栈,所以右括号出现时候O P T R.po
24、p ()弹出的必然是左括号。最后O P N D 会剩下最后一个数字即结果。函数：S t r c a t （c h a r 口，c h a r）在字符串后面加字符。8.P r o b l e m H:D S 堆栈一迷宫求解建立一个类C P 0 S,对象分别是x p,y p 作为坐标。建立存储类型为类的栈s t a c k 0从起点开始假如右边能走优先往右。直到右边不能走了就往下,假如右边和下边都不能走就p o p 0,同时刚刚的坐标上直接标记无法通 行（1）,然后判断下边能不能走。坐标轴到达了右下角即成功，假如最后p o p。到栈内没有元素了的话就说明没有途径。D S实验04-串应用K MP算法
25、1.P r o b 1 e m A:D S 串应用一KM P 算法n e x t j ：第一为0 的作用是让子串向右移动一格,此时i 会变。：1 的作用是子串换成第一个字符再进行比较，此 时 i 不会变。：j 取 n e x t j 的时候i 不变。：假如一直没有匹配到，j 一直为1,n e x t j 一直为0。假如有匹配到j 就会大于1;：子串有j 个字符,则n e x t中用到的只有前j 个。：n e x t j 大于0 时候表达调用第n e x t j 个位置的字符与m a in s t r i 匹配。三.实验程序或内容:1.针对每一项实验规定，给出编写的代码，2.可以粘贴所有代码，或
26、者可以只粘贴重要的代码(为了节省纸张)，但代码必须完整，至少是完整的函数。3.代码符合以下规定，评分更高：a.排版整齐，可读性高b.代码有注释，越具体越清楚越好DS实验01-顺序表1.Problem A:DS顺序表一类实现#i nclu d eusing namesp a c e st d;#d e fine o k 0#d efi n e e rr o r 1/顺序表类定义cl a s s S e q L i s t(private:in t*1 i st;int m a x s i z e;i n t s iz e;pub lie:SeqList();Se q L i s t();in t
27、 li s t_ s i z e();in t 1 ist_in s e rt(int i,int i t em);i n 11 i st_ del(int i);i nt 1 i s t_ge t(int i)；v o id list_dis p la y()；构造函数SeqList：:S eq L is t()(maxsize=l 0 00；s i z e=0；1 i st=n ew int max size;)/析构函数Seq List:S e q L i st()de I eteJlist；)返回长度int Se q Li s t:1 i st_ size()(return s i z
28、 e;)/插入函数int S eqLi s t：:1 i st_ i nser t(int i,i n t i t em)(if(i s i z e+l|ii-l;j-)1 i st j=1 i st j-l ;)1 ist j =item；size+;r e t u rn ok;)删除函数in t SeqLis t:lis t _del(int i)(i f(i siz e|i 0 I I size=0)retur n error;intj;fo r(j=i-l;js i z e 1 ;j+)(list j =1 is t j+1;)s i ze;r e t urn ok;)返回值函数i n
29、 t Se q L i st:l i st get(int i)i f(i s i ze)re t u rn e r r or;ret u r n 1 i s t i-1 ;)/输出函数v o id SeqLis t：:lis t _ d isplay()(int j;f or(j=0；js i ze；j+)(coutlistU M H;)c outendl;)i n t m a in()(i n t n,i,NUM,p o s it ion;S e qL i st L；/第 1 行先输入n 表达有n 个数据，即 n 是实际长度；接着输入n 个数据c i nn;fo r(i=0;ipos i
30、tionNUM;if(L.list_ i nsert(positio n,NUM)=-1 )cou t posit i on;i f(L Ji s t_ d e l(posit i o n)=1 )coutnerr o r en d 1；e l s e(c outL.list_size()；L.lis t _ d i splay()；)第5 行输入要删除的位置cin p o s i ti o n;if(L.list_de 1 (p o s itio n)=-1)c o u t ”e r ror end 1 ；el s e(coutL.l i s t_size()M；L.list_ di s p
31、lay();)/第 6 行输入耍查找的位置c i n p o s i ti o n;i f(L.list_ g et(p o s i t i o n)=-l)cou t e r rorMe n dl;e Isec o u tpo s i t i on;i f(L.l i s t _get(posit i on)=1)c ou t er r or”V Vendl;e 1 sec o u t L.li s t_ge t(p osit i o n)endl;retu r n 0；2.P r o b l e m B：DS顺序表一连续操作#in c 1 u deusing n amesp a ce s
32、t d;#de f ine o k 0#defi n e e rro r-1/顺序表类定义class Se q L i s t(p ri v a te:i n i*list；int max s ize;i n t s i ze;p u b lie：Seq L is t();SeqList();int lis t _size()；int 1 i st_in s e r t(in t i,int i t em)；in t li s t_del(int i)；i n t li s t _get(int i)；void 1 i st_ dis p lay()；构造函数Seq L is t：S e qL
33、ist()(ma x si z e=1 0 00;siz e=0；1 i st=new intma x s iz e;)析构函数Se q Lis t:SeqUs t()(d e le tel i st;)/返回长度i nt S e qL i st:1 i s t_ s i ze()(r e t urn si z e;/插入函数int SeqL i s t:list_ inser t(int i,int item)(i f(isi z e+l|ii-l;j-)l i s t j=l i s t j -IJ；)1 istj=i t em;s i z e+;ret u m ok；)删除函数in t
34、SeqList:li s t_del(i n t i)(i f(is i z e|i 0|size=0)return e r ror;in t j;fo r(j=i-l;jsize l;j+)(lis t j=listj+l;)s i z e -r et u r n o k;)/返回值函数i n t Se q Li s t:1 i s t_get(int i)(if(i size)iet u r n er r or;r e t u in 1 i st i-IJ;)/输出函数v o i d S e q L ist:l i st_ dis p 1 ay()(ini j；fo r(j=O;js i
35、ze；j+)(co utlist j ；)coutn;for(j=0；jn;j+)(c i n N U M;L.list_ ins e rt(j+1,NUM);)cou t L.l i s t _siz e()ik；for(j=0；j k;j+)c i n N U M；L.listJnsert(i+,NUM);)cou t L.list_ s i z e()”；L.1 i st_disp 1 a y()；第3 行先输入i 表达删除开始的位置，再输入k 表达要删除k 个数据c in i k;fo r(j=O;jk;j+)(L.l i s t _d el(i);)c out L,list_size
36、()n;L.list_display()；r etu r n 0;3.P ro b 1 em C:DS顺序表一合并操作#inclu d eusi n g n a mesp a ce s t d；#def i ne o k 0#d eiln e e rr o r-1/顺序表类定义c 1 as s S e qLis t(p r i v a te:in t*1 i st;in t maxsize;ini size；p ublic：S e q Lis t();S e qLis t();i n t lis t _size()；i nt 1 i s t_i n sert(int i,int i t em)
37、;i nt li s t_del(i n t i)；in t li s t get(int i);voi d list_disp 1 ay()；)；构造函数SeqList:SeqLis t()(ma x s ize=1 000;size=0;1 ist=new in t m a xsize；)/析构函数S eq L i s t:SeqLi s t()deleteljli s t;)返回长度int Se q Li s t:list_ size()(r eturn s i z e;)/插入函数int S e q L i st：1 i st_insert(i nt i,i nt item)(i f(
38、isiz e+1|i i-l;j-)(l i s t j=li s t j-IJ;list|jj=i tem;size+;r e t u r n ok;)/删除函数i n t Seq L i st:l i s t_del(int i)(i f(isize|I i0|I s i z e=0)retu r n error;i nt j；fo r(j=i-l；jsize-1;j+)listj=listu +l；s i z e ；return ok;)返回值函数int SeqLi s t:list_get(i nt i)(if(isiz e)return error;r eturn lis t I i
39、-1；)输出函数v o id S eqL i s t:：list_display()(intj；fo r(j=O;js i ze;j+)cou t 1 istj n;for(j=O;jm;f or(j=0;jm;j+)(cinN U M;L2.1 i st_insert(j+l,N U M);)i nt i=1;j=l;i nt k=l;/排列 Startwh i le(iLl.1 ist_size()+l|(jL2.1 ist_si z e()+1)(i f(i=L 1.1 i st_ size()+1)(whil e(j L2.I i st_ si z e()+1)(L3.1is t _
40、insert(k+,L2.1is t _ g e t(j);j+；)b r e ak;i f(j=L 2.1 is t _s i z e()+1)(whi 1 e(iL 2.1 ist_ g e t(j)L3.1 is t _i n s e rt(k+,L2.1ist_ g e t(j);j+;co n tin u e;i f(L l.lis t _g e t(i)L2.1 is t _get(j)L3.li s t_insert(k+,L l.li s t _ g et(i);i+;c ontinue;if(L 1 .lis t _get(i)=L2.1 i st_ ge t(j)(L3.1
41、ist_insert(k+,L2.1ist_get(j);j+;con t inue；)/排列Endc o u t L 3.1 ist_s i z e()L3.li s t dis p lay();retu r n 0;)D S 实验0 2 一链表1.P rob 1 e m A:D S 单链表一类实现#i nclu d e usi n g name s pace st d;#de f ine ok 1#def i n e err o r-1；cl a s s Li s tNode(p u b 1 ic:int d a t a；ListNode*next;Li s tN ode()next=NU
42、LL;)；c las s L inkLis t(pu b 1 i c:ListNode*h ead;i n t 1 e n;L i nkLi s t();L i nkList();Li s t No d e*L L_index(int i);int L L_ g e t(in t i);int LL_inse r t(in t i,int i t em);i n t L L _ del(int i);v oi d LL_di s p lay();)；LinkLi s t:：L in k L i st()(h ead=n e w L istN o d e();len=0；)L i nkLis t
43、：-L in k List()Li s tNo d e*p,*q；p=head;while(p!=NULL)(q=p；p=p-next;d elet e q;I1 en=0;hea d=NU L L;vo i d L i nkLi s t:LL_ display()(L i s t N o de*p;p=he a dnex t;while(p)(cou t p dat a*;p=p-n ex t;)coutendl;)List Node*Lin k List：LL_ind e x(in t i)(i f(i l e n)return NU LL;Lis t N o d e*p;p=h e a
44、d-next；while(p-next&-i)(p=p-next;)re t ur n p；)i n t LinkLis t:：LL_get(i nt i)(if(i l e n)r etu r n er r or;L i s tNo d e*p=NULL;p=head-n ext;while(p-next&-i)p=p-next；re t urn p-data;i nt Li n kLis t:LL_ i nsert(i n t i,int item)if(i le n+1 )r e tu r n error;ListNode*p;p=new ListNode()；p-d a ta=item
45、;i f(i=1)(Lis t Node*p E;pE=head-n e x t;he a d-next=p;pnex t=pE;1 en+;r e tu r n ok;)if(i=len+l)(L i s tNod e*pE；p E=he a d-ne x t;wh i 1 e(pE-n e xt)(p E=pE-n ext;)p E-n e xt=p;len+;r eturn o k;)e ls e(Lis t N o d e*p E,*p N；pE=h e ad-next;pN=pE；wh i 1 e(pE-n e x t&-i)(pN=pE;p E=p E-next;)pN-next=
46、p;p-n ex t=p E；1 en+；return ok;int LinkL i st:LL_del(i nt i)(i f(i 1 en)return e r ror;Li s t No d e*pE;if(i=l)(pE=head-next-n e x t;he a d next=pE;lenr e turn ok;)el s e(L i stNod e*pN;p E=h e ad-nex t;wh i le(pE-n e x t&i)(pN=pE；pE=pE n ex t;pE=p E-nex t;pN-next=pE；1 e n-;retur n ok;int ma i n()(i
47、nt n,i,NUM,p o s i t i o n;Li n k L ist L;/第 1 行先输入n 表达有n 个数据，即 n 是实际长度;接着输入n 个数据c i n n；for(i=0；i n；i+)(ci n N UM；L.LL_insert(i+l,NUM);)L.LL _ d i s p 1 a y();第2 行输入要插入的位置和新数据c in p os i ti o nNUM;if(L.LL_ i nsert(positi o n,NU M)=-l)cou t p o s i t ionNUM;if(L.LL_ in s e r t(pos i t ion,NUM)=-1)c
48、o ut e r ror n posi t i o n;i f(L.L L_ del(p o sition)=-l)cout e rro r e n d 1;e l s e(L.LL_ displayO;)/第 5 行输入要删除的位置c i n pos i tion；i f(L.L L_ del(po s it i on)=-1)cout uerror M endl;e IseL.LL_dis p lay();)第6 行输入要查找的位置c in p ositi o n;if(L.L L_ g e t(posi t io n)=-l)coutHe r rorue n dl；els ecout L
49、.LL_ge t(p osit i on)e nd 1 ;/第7 行输入要查找的位置c inposi t ion;i f(L.LL_get(p o sition)=-1)c o u t n e r r o r endl;e 1 sec ou t L.L L _get(posit i o n)e n d 1;retu r n 0;)2.矛roblem B：D S单链表一结点互换#in c ludeusi n g name s pace s t d;#define o k 1#define error-1;class Li s tN o de(pub 1 ic:i nt data;ListNod
50、e*next;Lis t N od e()next=N ULL；);c 1 as s L inkList(pu b 1 i c:Lis t Node*he a d;i nt 1 e n;L i nkLi s t();LinkL i st()；ListNo d e*LL_ i ndex(i nt i);int LL_get(int i);i n t LL_ insert(i nt i,in t item);int L L_ d el(in t i)；v o i d LL_display()；int s w a p(i nt p a,int pb);i nt s wap(Lis t N o d e