顺序表链表KMP实验报告

1、附件（四）深 圳 大大 学 实实 验 报报 告 课程名名称： 数据据结构实验验与课程设设计 实验项项目名称： 顺序表、链表、堆堆栈队列、串KMPP算法 学院： 专业： 指导教教师： 报告人人： 学号号： 班级： 实验时时间： 实验报报告提交时间： 教务处制实验目的与与完成说明明：1. 简简单介绍本本实验的主主要目的2. 说说明你自己己在本次实实验中完成成了第几项项要求（必填填）DS实验001-顺顺序表1. Prrobleem A: DS顺顺序表-类实现目的： (1)实现现顺序表的的用C+语言和类类实现顺序序表(2)属性性包括：数数组、实际际长度、最最大长度（设设定为10000）(3)操作作包括

2、：创创建、插入入、删除、查找要求：Inputt第1行先输输入n表示示有n个数数据，即nn是实际长长度；接着着输入n个个数据（完成）第2行输入入要插入的的位置和新新数据（完成）第3行输入入要插入的的位置和新新数据（完成）第4行输入入要删除的的位置（完成）第5行输入入要删除的的位置（完成）第6行输入入要查找的的位置（完成）第7行输入入要查找的的位置（完成）Outpuut第1行输出出创建后的的顺序表内内容，包括括顺序表实实际长度和和数据（完成）每成功执行行一次操作作（插入或或删除），输输出执行后后的顺序表表内容（完成）每成功执行行一次查找找，输出查查找到的数数据（完成）如果执行操操作失败（包包括插入

3、、删除、查查找等失败败），输出出字符串eerrorr，不必输输出顺序表表内容（完成）2. Prrobleem B: DS顺顺序表-连续操作作目的： (1)建立顺序序表的类，属属性包括：数组、实实际长度、最大长度度（设定为为10000）(2)实现现连续多个个插入，即即从位置ii开始插入入多个数据据(3)实现现连续多个个删除，即即从位置ii开始删除除多个数据据要求：Inputt第1行先输输入n表示示有n个数数据，即nn是实际长长度；接着着输入n个个数据（完成）第2行先输输入i表示示插入开始始的位置，再再输入k表表示有k个个插入数据据，接着输输入k个数数据（完成）第3行先输输入i表示示删除开始始的位

4、置，再再输入k表表示要删除除k个数据据（完成）Outpuut顺序表内容容包括顺序序表的实际际长度和数数据，数据据之间用空空格隔开（完成）第1行输出出创建后的的顺序表内内容（完成）第2行输出出执行连续续插入后的的顺序表内内容（完成）第3行输出出执行连续续删除后的的顺序表内内容（完成）3. Prrobleem C: DS顺顺序表-合并操作作目的： (1)建立立顺序表的的类，属性性包括：数数组、实际际长度、最最大长度（设设定为10000）(2)已知知两个递增增序列，把把两个序列列的数据合合并到顺序序表中，(3)并使使得顺序表表的数据递递增有序。要求：Inputt第1行先输输入n表示示有n个数数据，接

5、着着输入n个个数据，表表示第1个个序列，要要求数据递递增互不等等（完成）第2行先输输入m表示示有m个数数据，接着着输入m个个数据，表表示第2个个序列，要要求数据递递增互不等等（完成）Outpuut顺序表内容容包括顺序序表的实际际长度和数数据，数据据之间用空空格隔开（完成）第1行输出出创建后的的顺序表内内容（完成）DS实验002-链链表Probllem AA: DSS单链表-类实现现目的：(1)用CC+语言言和类实现现单链表，含含头结点(2)属性性包括：ddata数数据域、nnext指指针域(3)操作作包括：插插入、删除除、查找(4)注意意：单链表表不是数组组，所以位位置从1开开始对应首首结点，

6、头头结点不放放数据要求：Inputt第1行先输输入n表示示有n个数数据，接着着输入n个个数据（完成）第2行输入入要插入的的位置和新新数据（完成）第3行输入入要插入的的位置和新新数据（完成）第4行输入入要删除的的位置（完成）第5行输入入要删除的的位置（完成）第6行输入入要查找的的位置（完成）第7行输入入要查找的的位置（完成）Outpuut数据之间用用空格隔开开，（完成）第1行输出出创建后的的单链表的的数据（完成）每成功执行行一次操作作（插入或或删除），输输出执行后后的单链表表数据（完成）每成功执行行一次查找找，输出查查找到的数数据（完成）如果执行操操作失败（包包括插入、删除、查查找等失败败），输

7、出出字符串eerrorr，不必输输出单链表表（完成）Probllem BB: DSS单链表-结点交交换目的：(1)用CC+实现现含头结点点的单链表表，然后实实现单链表表的两个结结点交换位位置。(2)注意意不能简单单交换两个个结点包含含数据，必必须通过修修改指针来来实现两个个结点的位位置交换(3)交换换函数定义义可以参考考：(4)swwap（iint pa, int ppb) /paa和pb表表示两个结结点在单链链表的位置置序号(5)swwap (ListtNodee * pp, LiistNoode * q) /pp和q表示示指向两个个结点的指指针要求：Inputt第1行先输输入n表示示有n个

8、数数据，接着着输入n个个数据（完成）第2行输入入要交换的的两个结点点位置（完成）第3行输入入要交换的的两个结点点位置（完成）Outpuut第一行输出出单链表创创建后的所所有数据，数数据之间用用空格隔开开（完成）第二行输出出执行第11次交换操操作后的单单链表数据据，数据之之间用空格格隔开（完成）第三行输出出执行第22次交换操操作后的单单链表数据据，数据之之间用空格格隔开（完成）如果发现输输入位置不不合法，输输出字符串串erroor，不必必输出单链链表（完成）Probllem CC: DSS单链表-合并目的：(1)假定定两个单链链表是递增增有序，定定义并实现现以下函数数，完成两两个单链表表的合并，

9、继继续保持递递增有序(2)innt LLL_merrge(LListNNode *La, LisstNodde *LLb)要求：Inputt第1行先输输入n表示示有n个数数据，接着着输入n个个数据（完成）第2行先输输入m表示示有M个数数据，接着着输入m个个数据（完成）Outpuut输出合并后后的单链表表数据，数数据之间用用空格隔开开（完成）Probllem DD: DSS线性表-多项式式相加目的：(1)对于于一元多项项式 pp(x)=p0+pp1x+pp2x2+ +pnnxn ，每个项项都有系数数和指数两两部分，例例如p2xx2的系数数为p2,指数为22(2)编程程实现两个个多项式的的相加例如

10、5+xx+2x22+3x33，-5-x+6xx2+4xx4，两者者相加结果果：8x22+3x33+4x44 (3)其中中系数5和和-5都是是x的0次次方的系数数，相加后后为0，所所以不显示示。x的11次方同理理不显示。(4)可用用顺序表或或单链表实实现要求：Inputt第1行：输输入t表示示有t组测测试数据（完成）第2行：输输入n表示示有第1组组的第1个个多项式包包含n个项项（完成）第3行：输输入第一项项的系数和和指数，以以此类推输输入n行（完成）接着输入mm表示第11组的第22个多项式式包含m项项（完成）同理输入第第2个多项项式的m个个项的系数数和指数（完成）参考上面输输入第2组组数据，以以

11、此类推输输入t组（完成）假设所有数数据都是整整数（完成）Outpuut对于每1组组数据，先先用两行输输出两个原原来的多项项式，再用用一行输出出运算结果果，不必考考虑结果全全为0的情情况（完成）输出格式参参考样本数数据，格式式要求包括括：1.如果指指数或系数数是负数，用用小括号括括起来（完成）2.如果系系数为0，则则该项不用用输出（完成）3.如果指指数不为00，则用符符号表示示，例如xx的3次方方，表示为为x3（完成）4.多项式式的每个项项之间用符符号+连接接，每个+两边加11个空格隔隔开（完成）DS实验003-堆堆栈与队列列Probllem AA: DSS堆栈-逆序输出出（STLL栈使用）目的

12、：(1)C+中已经经自带堆栈栈对象sttack，无无需编写堆堆栈操作的的具体实现现代码。(2)本题题目主要帮帮助大家熟熟悉staack对象象的使用，然然后实现字字符串的逆逆序输出(3)输入入一个字符符串，按字字符按输入入顺序压入入堆栈，然然后根据堆堆栈后进先先出的特点点，做逆序序输出要求：Inputt第一行输入入t，表示示有t个测测试实例（完成）第二起，每每一行输入入一个字符符串，注意意字符串不不要包含空空格（完成）Outpuut每行逆序输输出每一个个字符串（完成）Probllem BB: DSS线性表综综合练习-队列之之银行排队队目的：(1)在银银行营业大大厅共服务务3种客户，类类型为ABC

13、，大大厅分别设设置了3个窗口分分别服务三三种客户，即即每个窗口口只服务一一种客户。现有一批批客户来银银行办理业业务，每个个客户都有有类型和办办理业务时时间。每个个窗口按照照客户到来来的顺序进进行服务。要求：Inputt第一行输入入先输入nn表示客户户数量（完成）第二行输入入每个客户户的类型，数数据之间用用用空格隔隔开（完成）第三行输入入每个客户户的办理时时间，数据据之间用用用空格隔开开（完成）Outpuut第一行输出出A类客户户的平均办办理时间（完成）第二行输出出B类客户户的平均办办理时间（完成）第三行输出出C类客户户的平均办办理时间（完成）Probllem CC: DSS堆栈-行编辑目的：(

14、1)使用用C+的的STL堆堆栈对象，编编写程序实实现行编辑辑功能。行行编辑功能能是：当输输入#字符符，则执行行退格操作作；如果无无字符可退退就不操作作，不会报报错(2)本程程序默认不不会显示#字符，所所以连续输输入多个#表示连续续执行多次次退格操作作(3)每输输入一行字字符打回车车则表示字字符串结束束(4)注意意：必须使使用堆栈实实现，而且且结果必须须是正序输输出要求：Inputt第一行输入入一个整数数t，表示示有t行字字符串要输输入（完成成）第二行起输输入一行字字符串，共共输入t行行（完成）Outpuut每行输出最最终处理后后的结果，如如果一行输输入的字符符串经过处处理后没有有字符输出出，则

15、直接接输出NUULL（完完成）Probllem DD: DSS线性表综综合练习-数制转转换目的：(1)对于于任意十进进制数转换换为k进制制，包括整整数部分和和小数部分分转换。整整数部分采采用除k求求余法，小小数部分采采用乘k取取整法例如如x=199.1255，求2进进制转换整数部分119，小数部分分0.122519 / 2 = 9 10.1225 * 2 = 0.255 009 / 22 = 44 110.255 * 22 = 00.5 004 / 22 = 22 00 0.5 * 2 = 1 12 / 22 = 11 001 / 22 = 00 11(2)所以以整数部分分转为 1100111

16、，小数部部分转为00.0011，合起来来为100011.0001(3)提示示整数部分分可用堆栈栈，小数部部分可用队队列实现(4)注意意：必须按按照上述方方法来实现现数制转换换，其他方方法0分要求：Inputt第一行输入入一个t，表表示下面将将有t组测测试数据。（完成）接下来每行行包含两个个参数n和和k，n表表示要转换换的数值，可可能是非整整数；k表表示要转换换的数制，11k=16（完成）Outpuut对于每一组组测试数据据，每行输输出转换后后的结果，结结果精度到到小数点后后3位（完成）Probllem EE: DSS堆栈-括号匹配配目的：(1)处理理表达式过过程中需要要对括号匹匹配进行检检验，

17、括号号匹配包括括三种：“(”和“)”，“”和“”，“”和“”。例例如表达式式中包含括括号如下：()()()1233456789101112(2)从上上例可以看看出第1和和第2个括括号匹配，第第3和第110个括号号匹配，44和5匹配配，6和99匹配，77和8匹配配，11和和12匹配配。从中可可以看到括括号嵌套的的的情况是是比较复杂杂的，使用用堆栈可以以很方便的的处理这种种括号匹配配检验，可可以遵循以以下规则：1、 当接接收第1个个左括号，表表示新的一一组匹配检检查开始；随后如果果连续接收收到左括号号，则不断断进堆栈。2、 当接接受第1个个右括号，则则和最新进进栈的左括括号进行匹匹配，表示示嵌套中

18、11组括号已已经匹配消消除3、 若到到最后，括括号不能完完全匹配，则则说明输入入的表达式式有错(3)建议议使用C+自带的的stacck对象来来实现要求：Inputt第一行输入入一个t，表表示下面将将有t组测测试数据。接下来的的t行的每每行输入一一个表达式式，表达式式只考虑英英文半角状状态输入，无无需考虑中中文全角输输入（完成）Outpuut对于每一行行的表达式式，检查括括号是否匹匹配，匹配配则输入ook，不匹匹配则输出出erroor（完成）Probllem FF: DSS线性表综综合练习-组队列列目的：(1)组队队列是队列列结构中一一种常见的的队列结构构，在很多多地方有着着广泛应用用。组队列列

19、是是指队队列内的元元素分组聚聚集在一起起。组队列列包含两种种命令：1、 ENNQUEUUE，表示示当有新的的元素进入入队列，首首先会检索索是否有同同一组的元元素已经存存在，如果果有，则新新元素排在在同组的最最后，如果果没有则插插入队列末末尾。2、 DEEQUEUUE，表示示队列头元元素出队3、 STTOP，停停止操作(2)建议议使用C+自带的的队列对象象queuue，编程程更方便要求：Inputt第1行输入入一个t(t=110)，表表示1个队队列中有多多少个组（完成）第2行输入入一个第11组的元素素个数和数数值第3行行输入一个个第2组的的元素个数数和数值，（完成但不严谨）以此类推输输入完n组组

20、之后，开开始输入多多个操作命命令(dataa;p-ddata=q-ddata;q-ddata=tempp; rreturrn okk; Probllem CC: DSS单链表-合并 过过程基本与与线性表合合并相同。不同的是是需要调整整指针。Probllem DD: DSS线性表-多项式式相加线性表实现现： 建立两两个数组分分别存储系系数和指数数。多项式相加加的操作过过程基本与与合并相似似。先比较较指数，若若指数较小小就插在最最左边，若若指数相等等则相加再再插入。一一条多项式式插完后另另一条多项项式剩余系系数指数插插在右边。链表实现：Statuus MaakeNoode(LLink& p,EEl

21、emTType e,EllemTyype ee1);分分配一个结结点Statuus CrreatPPolynn(pollynommai &P,Liink& p);将将结点插入入多项式中中。插入过过程中比较较指数大小按按由小到大大的顺序插插在相应的的位置里，如如果有相同同指数的则则系数相加加（系数可可为正负），若若系数为00则调用删删除函数删删除该结点点。Statuus AdddPollyn(ppolynnomaii &Paa,pollynommai &Pb,ppolynnomaii &Pcc);多项式相加加。比线性性表要简单单，直接把把Pa，PPb里的系系数跟指数创建建一个结点点放入多项项式P

22、c中中即可，相相加直接在在加入的时时候完成。DS实验003-堆堆栈与队列列Probllem AA: DSS堆栈-逆序输出出（STLL栈使用）建立一个栈栈，将数值值pushh()进栈栈后用toop()返返回值并ppop()弹出值逆逆向输出。Probllem BB: DSS线性表综综合练习-队列之之银行排队队建立两个队队列，一个个为，另另一个为，用于于存储时间间和字符，在在一个个用用fronnt()取取值并用ppop()弹出，用用判断语句句进行平均均数求值。Probllem CC: DSS堆栈-行编辑建立两个栈栈，用其中中一个栈存存储strring数数组的每一一个字符。先判断是是否为#号号且有多少

23、少个#号，若若没有#号号则pussh()字字符进第二二个栈，有有多少个#号就poop()多多少个。全全程判断栈栈是否为空空。最后判判断第二个个栈是否为为空，不为为空就输出出字符串，为为空就输出出NULLL。Probllem DD: DSS线性表综综合练习-数制转转换Push数数值与进制制数的余数数进栈然后后逆向输出出。Push数数值与2的的倍数取整整进栈然后后逆向输出出。Probllem EE: DSS堆栈-括号匹配配若栈为空时时下一个就就是右括号号直接括号号不匹配。若是左括号号则进栈。一直进左括括号知道有有右括号出出现。若右括号与与top()匹配则则pop()。若括号匹配配则栈为空空。Pro

24、bllem FF: DSS线性表综综合练习-组队列列建立队列数数组，同组组的元素进进入同一个个队列中。Probllem GG: DSS堆栈-表达式计计算使用OPTTR栈存储储运算符，使使用OPNND栈存储储数字。OPTR先先PUSHH入#号，输输入表达式式时最后一一位为#号号，在c= =OPPTR.ttop()= =#的时候结结束表达式式计算。读入字符的的过程中不不断有运算算符和数字字进栈，直直到两个运运算符遭遇遇的时候，判判断栈内ttop()运算符与与c内运算算符的优先先级，即表表达式中前前一个运算算符与后一一个运算符符的优先级级。如果是小于于，则直接接让c进OOPTR栈栈，再读入入下一个字

25、字符；如果是大于于，则OPPTR弹出出一个运算算符，OPPND弹出出两个数字字进行计算算求值重新新放回OPPND栈；如果是等于于则OPTTR出栈消消除括号。只有左括括号和右括括号以及两两个#号的的优先级为为等于号。而右括号号出现的时时候左括号号以后的运运算符都已已计算并变变成数字进进入了OPPND栈，所所以右括号号出现时候候OPTRR.popp()弹出出的必然是是左括号。最后OPNND会剩下下最后一个个数字即结结果。函数： SStrcaat(chhar,chaar)在字字符串后面面加字符。Probllem HH: DSS堆栈-迷宫求解解建立一个类类CPOSS，对象分分别是xpp,yp作作为坐标

26、。建立存储储类型为类类的栈sttack。从起点开始始如果右边边能走优先先往右。直直到右边不不能走了就就往下，如如果右边和和下边都不不能走就ppop（），同同时刚刚的的坐标上直直接标记无无法通行（11），然后后判断下边边能不能走走。坐标轴轴到达了右右下角即成成功，如果果最后poop（）到到栈内没有有元素了的的话就说明明没有路径径。DS实验004-串串应用KMMP算法Probllem AA: DSS串应用-KMPP算法nextj：第一为00的作用是让子子串向右移移动一格，此此时i会变变。：1的作用用是子串换换成第一个个字符再进行比较较，此时ii不会变。：j取neextjj的时候候i不变。：如果一直

27、直没有匹配配到，j一一直为1，nnextj一直直为0。如如果有匹配配到j就会会大于1；：子串有jj个字符，则则nextt中用到的的只有前jj个。：nexttj大大于0时候候表示调用用第nexxtj个位置的的字符与mmainsstrii匹配。三实验程程序或内容容：1. 针对对每一项实实验要求，给给出编写的的代码，2. 可以以粘贴全部部代码，或或者可以只只粘贴重要要的代码（为为了节省纸纸张），但代码必必须完整，至至少是完整整的函数。3. 代码码符合以下下要求，评评分更高：a. 排版版整齐，可可读性高b. 代码码有注释，越越详细越清清晰越好DS实验001-顺顺序表1. Prrobleem A: DS

28、顺顺序表-类实现#incllude usingg nammespaace sstd; #defiine ook 0 #defiine eerrorr -1 /顺序表表类定义 classs SeqqListt privaate: iint *listt; iint mmaxsiize; iint ssize; publiic: SSeqLiist(); SeqLList(); iint llist_sizee(); iint llist_inseert(iint ii,intt iteem); iint llist_del(int ii); iint llist_get(int ii); vvo

29、id listt_dissplayy(); ; /构造函函数SeqLiist:SeqLList() mmaxsiize=11000; ssize=0; llist=new intmmaxsiize; /析构函函数SeqLiist:SeqqListt() ddelettellist; /返回长长度int SSeqLiist:listt_sizze() rreturrn siize; /插入函函数int SSeqLiist:listt_inssert(int ii,intt iteem) iif(isizee+1|ii-1;j-) llistj=llistj-1; llistj=iitem; ss

30、ize+; rreturrn okk; /删除函函数int SSeqLiist:listt_dell(intt i) iif(isizee|i0|ssize=0)rreturrn errror; iint jj; ffor(jj=i-11;jssize-1;j+) llistj=llistj+1; ssize-; rreturrn okk; /返回值值函数int SSeqLiist:listt_gett(intt i) iif(isiize)reeturnn errror; rreturrn liistii-1; /输出函函数void SeqLList:lisst_diisplaay() ii

31、nt jj; ffor(jj=0;jjsizze;j+) ccoutlisstj ; ccoutn; ffor(ii=0;iiNUM; LL.lisst_innsertt(i+11,NUMM); ccoutL.llist_sizee()posiitionnNUUM; iif(L.listt_inssert(posiitionn,NUMM)=-1)coouterrrorenddl; eelse ccoutL.llist_sizee()posiitionnNUUM; iif(L.listt_inssert(posiitionn,NUMM)=-1)coouterrrorenddl; eelse cc

32、outL.llist_sizee()posiitionn; iif(L.listt_dell(possitioon)=-1)ccouterrrorenndl; eelse ccoutL.llist_sizee()posiitionn; iif(L.listt_dell(possitioon)=-1)ccouterrrorenndl; eelse ccoutL.llist_sizee()posiitionn; iif(L.listt_gett(possitioon)=-1)ccouterrrorenndl; eelse ccoutL.llist_get(posiitionn)posiitionn

33、; iif(L.listt_gett(possitioon)=-1)ccouterrrorenndl; eelse ccoutL.llist_get(posiitionn)eendl; rreturrn 0; 2.Prooblemm B: DS顺序序表-连连续操作#incllude usingg nammespaace sstd; #defiine ook 0 #defiine eerrorr -1 /顺序表表类定义 classs SeqqListt privaate: iint *listt; iint mmaxsiize; iint ssize; publiic: SSeqLiist();

34、 SeqLList(); iint llist_sizee(); iint llist_inseert(iint ii,intt iteem); iint llist_del(int ii); iint llist_get(int ii); vvoid listt_dissplayy(); ; /构造函函数SeqLiist:SeqLList() mmaxsiize=11000; ssize=0; llist=new intmmaxsiize; /析构函函数SeqLiist:SeqqListt() ddelettellist; /返回长长度int SSeqLiist:listt_sizze()

35、rreturrn siize; /插入函函数int SSeqLiist:listt_inssert(int ii,intt iteem) iif(isizee+1|ii-1;j-) llistj=llistj-1; llistj=iitem; ssize+; rreturrn okk; /删除函函数int SSeqLiist:listt_dell(intt i) iif(isizee|i0|ssize=0)rreturrn errror; iint jj; ffor(jj=i-11;jssize-1;j+) llistj=llistj+1; ssize-; rreturrn okk; /返回值

36、值函数int SSeqLiist:listt_gett(intt i) iif(isiize)reeturnn errror; rreturrn liistii-1; /输出函函数void SeqLList:lisst_diisplaay() iint jj; ffor(jj=0;jjsizze;j+) ccoutlisstj ; ccoutn; ffor(jj=0;jjNUM; LL.lisst_innsertt(j+11,NUMM); ccoutL.llist_sizee()ikk; ffor(jj=0;jjNUM; LL.lisst_innsertt(i+,NUMM); ccoutL.l

37、list_sizee()ikk; ffor(jj=0;jjk;jj+) LL.lisst_deel(i); ccoutL.llist_sizee() ; LL.lisst_diisplaay(); rreturrn 0; 3. Prrobleem C: DS顺顺序表-合并操作作#incllude usingg nammespaace sstd; #defiine ook 0 #defiine eerrorr -1 /顺序表表类定义 classs SeqqListt privaate: iint *listt; iint mmaxsiize; iint ssize; publiic: SSeqL

38、iist(); SeqLList(); iint llist_sizee(); iint llist_inseert(iint ii,intt iteem); iint llist_del(int ii); iint llist_get(int ii); vvoid listt_dissplayy(); ; /构造函函数SeqLiist:SeqLList() mmaxsiize=11000; ssize=0; llist=new intmmaxsiize; /析构函函数SeqLiist:SeqqListt() ddelettellist; /返回长长度int SSeqLiist:listt_s

39、izze() rreturrn siize; /插入函函数int SSeqLiist:listt_inssert(int ii,intt iteem) iif(isizee+1|ii-1;j-) llistj=llistj-1; llistj=iitem; ssize+; rreturrn okk; /删除函函数int SSeqLiist:listt_dell(intt i) iif(isizee|i0|ssize=0)rreturrn errror; iint jj; ffor(jj=i-11;jssize-1;j+) llistj=llistj+1; ssize-; rreturrn ok

40、k; /返回值值函数int SSeqLiist:listt_gett(intt i) iif(isiize)rreturrn errror; rreturrn liistii-1; /输出函函数void SeqLList:lisst_diisplaay() iint jj; ffor(jj=0;jjsizze;j+) ccoutlisstj ; ccoutn; ffor(jj=0;jjNUM; LL1.liist_iinserrt(j+1,NUUM); ccinm; ffor(jj=0;jjNUM; LL2.liist_iinserrt(j+1,NUUM); iint ii=1; jj=1;

41、int kk=1; /排列SStartt wwhilee(iLL1.liist_ssize()+1|jLL2.liist_ssize()+1) iif(i=L1.listt_sizze()+1) wwhilee(jLL2.liist_ssize()+1) LL3.liist_iinserrt(k+,L22.lisst_geet(j); jj+; bbreakk; iif(j=L2.listt_sizze()+1) wwhilee(iL2.listt_gett(j) LL3.liist_iinserrt(k+,L22.lisst_geet(j); jj+; ccontiinue; iif(L11

42、.lisst_geet(i)L2.listt_gett(j) LL3.liist_iinserrt(k+,L11.lisst_geet(i); ii+; ccontiinue; iif(L11.lisst_geet(i)=L22.lisst_geet(j) LL3.liist_iinserrt(k+,L22.lisst_geet(j); jj+; ccontiinue; /排列EEnd ccoutL3.listt_sizze() ; LL3.liist_ddispllay(); rreturrn 0; DS实验002-链链表Probllem AA: DSS单链表-类实现现#incllude u

43、singg nammespaace sstd; #defiine ook 1 #defiine eerrorr -1; classs LisstNodde publiic: iint ddata; LListNNode *nexxt; LListNNode()neext=NNULL; ; classs LinnkLisst publiic: LListNNode *heaad; iint llen; LLinkLList(); LinkkListt(); LListNNode *LL_indeex(innt i); iint LLL_geet(innt i); iint LLL_innsert

44、t(intt i,innt ittem); iint LLL_deel(innt i); vvoid LL_ddispllay(); ; LinkLList:LinnkLisst() hhead= neww LisstNodde(); llen=00; LinkLList:LiinkLiist() LListNNode *p,*q; pp=heaad; wwhilee(p!=NULLL) qq=p; pp=p-nextt; ddelette q; llen=00; hhead=NULLL; void LinkkListt:LLL_dissplayy() LListNNode *p; pp=he

45、aad-nnext; wwhilee(p) ccoutdataanextt; ccoutenddl; ListNNode* LinnkLisst:LLL_inndex(int ii) iif(ileen)reeturnn NULLL; LListNNode *p; pp=heaad-nnext; wwhilee(p-nextt & -i) pp=p-nextt; rreturrn p; int LLinkLList:LL_get(int ii) iif(ilenn)retturn erroor; LListNNode *p=NNULL; pp=heaad-nnext; wwhilee(p-ne

46、xtt & -i) pp=p-nextt; rreturrn p-datta; int LLinkLList:LL_inseert(iint ii,intt iteem) iif(ilenn+1)rreturrn errror; LListNNode *p; pp=neww LisstNodde(); pp-daata=iitem; iif(i=1) LListNNode *pE; ppE=heead-nextt; hhead-nexxt=p; pp-neext=ppE; llen+; rreturrn okk; iif(i=lenn+1) LListNNode *pE; ppE=heead-

47、nextt; wwhilee(pE-nexxt) ppE=pEE-neext; ppE-nnext=p; llen+; rreturrn okk; eelse LListNNode *pE,*pN; ppE=heead-nextt; ppN=pEE; wwhilee(pE-nexxt & -ii) ppN=pEE; ppE=pEE-neext; ppN-nnext=p; pp-neext=ppE; llen+; rreturrn okk; int LLinkLList:LL_del(int ii) iif(ilenn)retturn erroor; LListNNode *pE; iif(i=

48、1) ppE=heead-nextt-neext; hhead-nexxt=pEE; llen-; rreturrn okk; eelse LListNNode *pN; ppE=heead-nextt; wwhilee(pE-nexxt & -ii) ppN=pEE; ppE=pEE-neext; ppE=pEE-neext; ppN-nnext=pE; llen-; rreturrn okk; int mmain() innt n,i,NUUM,poositiion; LLinkLList L; /第1行行先输入nn表示有nn个数据，即即n是实际际长度；接接着输入nn个数据 ccinn;

49、ffor(ii=0;iiNUM; LL.LL_inseert(ii+1,NNUM); LL.LL_dispplay(); /第2行行输入要插插入的位置置和新数据据 ccinposiitionnNUUM; iif(L.LL_iinserrt(poositiion,NNUM)=-1)coutteerrorrposiitionnNUUM; iif(L.LL_iinserrt(poositiion,NNUM)=-1)coutteerrorrposiitionn; iif(L.LL_ddel(pposittion)=-11)couuterroorposiitionn; iif(L.LL_ddel(ppo

50、sittion)=-11)couuterroorposiitionn; iif(L.LL_gget(pposittion)=-11)couuterroorendll; eelse ccoutL.LLL_geet(poositiion)posiitionn; iif(L.LL_gget(pposittion)=-11)couuterroorendll; eelse ccoutL.LLL_geet(poositiion)enddl; rreturrn 0; 2.Prrobleem B: DS单单链表-结点交换换#incllude usingg nammespaace sstd; #defiine

51、ook 1 #defiine eerrorr -1; classs LisstNodde publiic: iint ddata; LListNNode *nexxt; LListNNode()neext=NNULL; ; classs LinkkListt publiic: LListNNode *heaad; iint llen; LLinkLList(); LinkkListt(); LListNNode *LL_indeex(innt i); iint LLL_geet(innt i); iint LLL_innsertt(intt i,innt ittem); iint LLL_de

52、el(innt i); vvoid LL_ddispllay(); iint sswap(int pa, int ppb); iint sswap(ListtNodee *p,ListtNodee *q); ; LinkLList:LinnkLisst() hhead= neww LisstNodde(); llen=00; LinkLList:LiinkLiist() LListNNode *p,*q; pp=heaad; wwhilee(p!=NULLL) qq=p; pp=p-nextt; ddelette q; llen=00; hhead=NULLL; void LinkkListt

53、:LLL_dissplayy() LListNNode *p; pp=heaad-nnext; ccoutdataa; pp=p-nextt; wwhilee(p) ccout datta; pp=p-nextt; ccoutenddl; ListNNode* LinnkLisst:LLL_inndex(int ii) iif(ilenn)retturn NULLL; iif(i=0)rreturrn heead; LListNNode *p; pp=heaad-nnext; wwhilee(p-nextt & -i) pp=p-nextt; rreturrn p; int LLinkLLis

54、t:LL_get(int ii) iif(ilenn)retturn erroor; rreturrn LLL_inddex(ii)-ddata; int LLinkLList:LL_inseert(iint ii,intt iteem) iif(ilenn+1)rreturrn errror; LListNNode *p; pp=neww LisstNodde; pp-daata=iitem; iif(i=lenn+1) LLL_inndex(len)-neext=pp; llen+; rreturrn okk; eelse LListNNode *pNeex,*ppPre; ppNex=L

55、L_iindexx(i-11); ppPre=LL_iindexx(i); ppNex-nexxt=p; pp-neext=ppPre; llen+; rreturrn okk; int LLinkLList:LL_del(int ii) iif(ilenn)retturn erroor; LListNNode *pNeex,*ppPre; ppNex=LL_iindexx(i-11); ppPre=LL_iindexx(i+11); ppNex-nexxt=pPPre; llen-; rreturrn okk; int LLinkLList:swaap(innt ppa, iint ppb)

56、 iif(paallen|pblenn)retturn erroor; LListNNode *a_ppNex,*a,*a_pPPre,*b_pNNex,*b,*bb_pPrre; aa_pNeex=LLL_inddex(ppa-1); aa=LL_indeex(paa); aa_pPrre=LLL_inddex(ppa+1); bb_pNeex=LLL_inddex(ppb-1); bb=LL_indeex(pbb); bb_pPrre=LLL_inddex(ppb+1); iif(a-nexxt=bb) aa_pNeex-nnext=b; bb-neext=bb_pNeex; bb_pNe

57、ex-nnext=b_pPPre; rreturrn okk; iif(b-nexxt=aa) bb_pNeex-nnext=a; aa-neext=aa_pNeex; aa_pNeex-nnext=a_pPPre; rreturrn okk; aa_pNeex-nnext=b; bb-neext=aa_pPrre; bb_pNeex-nnext=a; aa-neext=bb_pPrre; rreturrn okk; /改变指指针进行交交换int LLinkLList:swaap(LiistNoode *p,LiistNoode *q) iif(p=heaad|qq=heead|!p|!q)r

58、returrn errror; LListNNode *a_ppNex,*a,*a_pPPre,*b_pNNex,*b,*bb_pPrre; aa=p; aa_pPrre=p-nexxt; bb=q; bb_pPrre=q-nexxt; aa_pNeex=heead; bb_pNeex=heead; wwhilee(a_ppNex-nexxt!=pp) aa_pNeex=a_pNexx-neext; whille(b_pNexx-neext!=q) bb_pNeex=b_pNexx-neext; iif(a-nexxt=bb) aa_pNeex-nnext=b; bb-neext=bb_pNe

59、ex; bb_pNeex-nnext=b_pPPre; rreturrn okk; iif(b-nexxt=aa) bb_pNeex-nnext=a; aa-neext=aa_pNeex; aa_pNeex-nnext=a_pPPre; rreturrn okk; aa_pNeex-nnext=b; bb-neext=aa_pPrre; bb_pNeex-nnext=a; aa-neext=bb_pPrre; rreturrn okk; /*改变数数值进行交交换int LLinkLList:swaap(LiistNoode *p,LiistNoode *q) iif(p=heaad|qq=he

60、ead|!p|!q)rreturrn errror; int tempp;tempp=p-dataa;p-ddata=q-ddata;q-ddata=tempp; rreturrn okk; */ int mmain() innt n,i,NUUM,nuum1,nnum2; LLinkLList L; /第1行行先输入nn表示有nn个数据，即即n是实际际长度；接接着输入nn个数据 ccinn; ffor(ii=0;iiNUM; LL.LL_inseert(ii+1,NNUM); iif(n!=0)LL.LL_dispplay(); /第2行行输入要交交换的两个个结点位置置 ccinnum11n