《冲刺必会代码100题.pdf》由会员分享，可在线阅读，更多相关《冲刺必会代码100题.pdf（64页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1冲冲刺刺必必会会代代码码 1 10 00 0 题题顺顺序序表表1、已知线性表（a1,a2,an）按顺序结构存储且每个元素为不相等的整数。设计把所有奇数移动到所有偶数前边的算法（要要求求时时间间最最少少，辅辅助助空空间间最最少少）。【算法思想】：对于顺序表 L，从左向右找到偶数 L.datai，从右向左找到奇数L.dataj，将两者交换。循环这个过程直到 i 大于 j 为止。对应的算法如下：void move(SqList&L)int i=0,j=L.length-1,k;ElemType temp;while(i=j)while(L.datai%2=1)i+;/i 指向一个偶数while(L
2、.dataj%2=0)j-;/j 指向一个偶数if(i j)temp=L.datai;/交换 L.datai和 L.datajL.datai=L.dataj;L.dataj=temp;本算法的时间复杂度为 O(n)，空间复杂度为 O(1)。2、设计一个高效算法，将顺序表 L 中所有元素逆置，要求算法的空间复杂度为 O(1)。【算法思想】：扫描顺序表 L 的前半部分元素，对于元素 L.datai,将其与后半部分对应元素 L.dataL.length-i-1进行交换。对应的算法如下:void reverse(SqList&L)int i;ElemType x;for(i=0;i C.length)
3、/表长超过return false;int i=0,j=0,k=0;while(i A.length&jB.length)/循环，两两比较，小者存入结果表if(A.datai=B.dataj)C.datak+=A.datai+;elseC.datak+=B.dataj+;while(i A.length)C.datak+=A.datai+;while(j B.length)C.datak+=B.dataj+;C.length=k;return true;4、从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除元素的值。空出的位置由最后一个元素填补。【算法思想】搜素整个顺序表，查找最小值
4、元素并记在其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置。bool Delete_Min(SqList&L,ElemType&value)/删除顺序表 L 中最小值元素结点，并通过引用型参数 value 返回其值if(L.length=0)return false;/表空，终止操作value=L.data0;int pos=0;/假设 0 号元素的值最小for(int i=1;iL.length;i+)/循环遍历，寻找具有最小值的元素if(L.datai value)/让 value 记忆当前具有最小值的元素value=L.datai;pos=i;L.datapos=L.data
5、L.length-1;/空出的位置由最后一个元素填补L.length-;return true;35、已知长度为 n 的线性表 L 采用顺序存储结构,编写一个时间复杂度为 O(n)、空间复杂度为 O(1)的算法,该算法删除线性表中所有值为 x 的数据元素。【算法思想】解法 1：用 k 记录顺序表 L 中等于 x 的元素个数,边扫描 L 边统计 k,并将不为 x 的元素前移 k 位,最后修改 L 的长度。对应的算法如下:void del_x(SqList&L,ElemType x)int k,i=0;/k 用于记录 L 中值等于 x 的元素个数，初试值为 0while(iL.length)if(
6、L.datai=x)k+;/k 自增elseL.datai-k=L.datai;/将不为 x 的元素元素前移 k 个位置i+;L.length=L.length-k;/顺序表长度较少 k解法 2：用 i 从头开始遍历顺序表 L，k 置初始 0。若 L.datai不等于 x，则将其存放在 L.datak中，k 增 1;若 L.datai等于 x，则跳过继续判断下一个元素。最后顺序表长度置为 k。对应算法如下。void del_x(SqList&L,ElemType x)int i;k=0;/k 用于记录 L 中值等于 x 的元素个数，初试值为 0for(i=0;i=x&L.datai=y。voi
7、d del_xy(SqList&L,ElemType x,ElemType y)int i,k=0;for(i=0;j=x&L.datai=y)L.datak=L.datai;k+;L.length=k;/表长置为 k解法二：void del_xy(SqList&L,ElemType x,ElemType y)int i=0,k=0;while(i=x&L.datai 1)个整数存放在一维数组 R 中。试着设计一个在时间复杂度和空间复杂度都尽可能高效的算法，将 R 中保存的序列循环左移 p（0pn）个 位 置，即 将 R 中 的 数 据 由（x0,x1,xn-1）变 换 为（xp,xp+1,x
8、n-1,x0,x1,xp-1）。要求：（1）给出算法的基本设计思想；（2）根据算法设计思想，采用 C 或 C+语言描述，关键之处给出注释（3）说明你所设计算法的时间复杂度和空间复杂度。【算法思想】先将 n 个数据 x0,x1,xn-2,xn-1原地逆置，得到 xn-1,xn-2,x,x0,然后再将 n-p 个数据和后 p 个数据分别原地逆置，得到最终结果：xp,xp+1,xn-1,x0,x1,xp-1void Reverse(int R,int left,int right)/将数组原地逆置i=left,j=right;while(i 0&pnext;/pa 是链表 La 的工作指针，初始化为
9、首元结点pb=Lb-next;/pb 是链表 Lb 的工作指针，初始化为首元结点Lc=pc=La;/La 的头结点作为 Lc 的头结点while(pa&pb)if(pa-data data)/取较小者 Lb 中的元素，将 pb 链接在 pc 的后面，pb 指针后移pc-next=pa;pc=pa;pa=pa-next;/ifelse if(pa-data pb-data)/取较小者 Lb 中的元素，将 pb 链接在 pc 的后面，pb 指针后移pc-next=pb;pc=pb;pb=pb-next;/else ifelsepc-next=pa;pc=pa;pa=pa-next;q=pa-nex
10、t;free(pb);pb=q;pc-next=pa?pa:pb;/将非空的剩余元素直接链接在 Lc 表的最好free(Lb);/释放 Lb 的头结点72、将两个非递减的有序表合并为一个非递增的有序表。要求结果链表仍然使用原来两个链表的存储空间，不占用另外的存储空间。表中允许有重复的数据。【算算法法思思想想】与上述题目类似，从原有两个链表中依次摘取结点，通过更改结点的指针域重新建立新的元素之间的线性关系，得到一个新链表。但与上面题目不同的点有两个：为保证新表与原表顺序相反，需要利用前插法建立单链表，而不能利用后插法；当一个表到达表尾结点为空时，另一个非空表的剩余元素应该依次摘取，依次链接在 L
11、c 表的表头结点之后，而不能全部直接链接在 Lc 表的最后。算法思想是:假设待合并的链表为 La 和 Lb，合并后的新表使用头指针 Lc(Lc 的表头结点设为 La 的表头结点)指向。pa 和 pb 分别是链表 La 和 Lb 的工作指针，初始化为相应链表的首元结点。从首元结点开始进行比较，当两个链表 La 和 Lb均为到达表尾结点时，依次摘取其中较小者重新链接在 Lc 表的表头结点之后，如果两个表中的元素相等，只摘取 La 表中的元素，保留 Lb 表中的元素。当一个表到达表尾结点为空时,将非空表的剩余元素依次摘取，链接在 Lc 表的表头结点之后。最后释放链表 Lb 的头结点。void Mer
12、geList(LinkList&La,LinkList&Lb,LinkList&Lc)/将两个非递减的有序表 La 和 Lb 合并为一个非递增的有序链表 Lcpa=La-next;/pa 是链表的 La 的工作指针，初始化为首元结点pb=Lb-next;/pb 是链表 Lb 的工作指针，初始化为首元结点Lc=pc=La；/用 La 的头结点作为 Lc 的头结点Lc-next=NULL;while(pa|pb)/只要有一个表未到达表尾指针，用 q 指向待摘取的元素if(!pa)/La 表为空，用 q 指向 pb,pb 指针后移q=pb;pb=pb-next;else if(!pb)/Lb 表为空
13、，用 q 指向 pa,pa 指针后移q=pa;pa=pa-next;else if(pa-data data)/去较小者 La 中的元素，用 q 指向 pa，pa 指针后移q=pa;pa=pa-next;else/去较小者 Lb 中的元素，用 q 指向 pb，pb 指针后移8q=pb;pb=pb-next;q-next=Lc-next;Lc-next=q;free(Lb)3、已知两个链表 A 和 B 分别为两个集合，其元素递增排列。请设计一个算法，用于求出 A 与 B 的交集，并存放在 A 链表中。【算法思想】A 与 B 的交集是指同时出现在两个集合中的元素，因此，此题的关键点在于:依次摘取两
14、个表中相等的元素重新进行链接,删除其他不等的元素。算算法法思思想想是是:假设待合并的链表为 La 和 Lb，合并后的新表使用头指针 Lc(Lc 的表头结点设为 La 的表头结点)指向。pa 和 pb 分别是链表 La 和 Lb 的工作指针，初始化为相应链表的首元结点。从首元结点开始进行比较，当两个链表 La 和 Lb均为到达表尾结点时，如果两个表中的元素相等，摘取 La 表中的元素，删除 Lb表中的元素;如果其中一个表中的元素较小，删除此表中较小的元素，此表的工作指针后移。当链表 La 和 Lb 有一个到达表尾结点为空时，依次删除另一个非空表中的所有元素。最后释放链表 Lb 的头结点。void
15、 Intersection(LinkList&La,LinkList&Lb,LinkList&Lc)pa=La-next;/pa 是链表 La 的工作指针，初始化为首元结点pb=Lb-next;/pb 是链表 Lb 的工作指针，初始化为首元结点Lc=pc=La;/用 La 的头结点作为 Lc 的头结点while(pa&pb)if(pa-data=pb-data)/相等，交集并入结果表中pc-next=pa;pc=pa;pa=pa-next;u=pb;pb=pb-next;free(u);else if(pa-data data)/删除较小者 La 中的元素u=pa;9pa=pa-next;fr
16、ee(u);else/删除较小者 La 中的元素u=pb;pb=pb-next;free(u);while(pa)/Lb 为空，删除非空表 La 中的所有元素u=pa;pa=pa-next;free(u);while(pb)/La 为空，删除非空表 Lb 中的所有元素u=pb;pb=pb-next;free(u);pc-next=NULL;free(Lb)4、已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计两个算法求出两个集合 A 和 B 的差集（即仅由在 A 中出现而不在 B 中出现的元素所构成的集合），并且以同样的形式存储，同时返回该集合的元素个数。【算法思想】求两个集合
17、 A 和 B 的差集是指在 A 中删除 A 和 B 中共有的元素，即删除链表中的数据域相等的结点。由于要删除结点，此题的关键点在于:在遍历链表时，需要保存待删除结点的前驱。算算法法思思想想是是:假设待求的链表为 La 和 Lb，pa 和 pb 分别是链表 La 和 Lb 的工作指针，初始化为相应链表的首元结点。pre 为 La 中 pa 所指结点的前驱结点的指针，初始化为 La。从首元结点开始进行比较，当两个链表 La 和 Lb 均未到达表尾结点时，如果 La 表中的元素小于 Lb 表中的元素，La 表中的元素即为待求差集中的元素，差集元素个数增 1，pre 置为 La 表的工作指针 pa,p
18、a 后移;如果 Lb表中的元素小于La表中的元素,pb后移;如果La表中的元素等于Lb表中的元素，则在 La 表删除该元素值对应的结点。10void Difference(LinkList&La,LinkList&Lb,int&n)pa=La-next;/pa 是链表的 La 的工作指针，初始化为首元结点pa=Lb-next;/pb 是链表 Lb 的工作指针，初始化为首元结点pre=La;/pre 为 La 中 pa 所指结点的前驱结点的指针while(pa&pb)if(pa-data data)/A 链表当前的结点指针后移n+;pre=pa;pa=pa-next;else if(pb-dat
19、a pb-data)pb=pb-next;/A 链表当前的结点指针后移else/在 La 中删除 La 和 Lb 中元素值相同的结点pre-next=pa-next;u=pa;pa=pa-next;free(u);5、试试编编写写在在带带头头结结点点的的单单链链表表 L 中中删删除除一一个个最最小小值值结结点点的的高高效效率率算算法法（假假设设最最小小值值结结点点是是唯唯一一的的）。算算法法思思想想：用 p 从头至尾扫描单链表，pre 指向*p 结点的前驱，用 minp 保存值最小的结点指针（初值为 p）,minpre 指向*minp 结点的前驱（初值为 pre）。一遍扫描，一边比较，若 p-
20、data 小于 minp-data，则将 p、pre 分别赋值给 minp，minpre，如下图所示。当 p 扫描完毕，minp 指向最小值结点，minpre 指向最小值结点的前驱结点，再将 minp 所指结点删除即可。LinkList Delete_Min(LinkList&L)/L 是带头结点的单链表，本算法是删除其最小值结点LNode*pre=L,*p=pre-next;/p 为工作指针，pre 指向其前驱11LNode*minpre=pre,*minp=p;/保存最小值结点及其前驱while(p!=NULL)if(p-data data)minp=p;minpre=pre;pre=p;
21、/继续扫描下一节点p=p-next;minpre-next=minp-next;/删除最小值结点free(minp);return L;6、在带头结点的单链表 L 中，删除所有值为 x 的结点，并释放其空间，假设值为 x 的结点不唯一，试编写算法实现上述操作。算法思想：解解法法一一：用 p 从头至尾扫描单链表，pre 指向*p 结点的前驱。若 p 所指结点的值为 x，则删除，并让 p 移向下一个结点，否则让 pre、p 同步后移一个结点。提示：本算法其实也算的上是一个删删除除某某结结点点相相关关题题型型的的代代码码模模板板。此题是在无序单链表中删除满足某种条件的所有结点，这里的条件是结点的值为
22、 x，实际上，这个条件是可以任意改写的，只需要修改 if 条件即可。例如，我们要求删除结点 值 介 于 mink 和 maxk 之 间 的 所 有 结 点，则 只 需 要 将 if 语 句 修 改 为if(p-data mink&p-data next,*pre=L,*q;/置 p 和 pre 的初值while(p!=NULL)if(p-data=x)q=p;/q 指向该结点p=p-next;pre-next=p;/删除*q 结点free(q);/释放*q 结点的空间else/否则，pre 和 p 同步后移12pre=p;p=p-next;/else/while解解法法二二：采用尾插法建立单链
23、表。用 p 指针扫描 L 的所有结点，当其值不为 x时将其链接到 L 之后，否则将其释放。void Delet_x(Linklist&L,ElemType x)/L 为带头结点的单链表，本算法删除 L 中所有值为 x 的结点LNode*p=L-next,*r=L,*q;/r 指向尾节点，其初值为头结点while(p!=NULL)if(p-data!=x)/*p 结点值不为 x 时将其链接到 L 的尾部r-next=p;r=p;p=p-next;/继续扫描elseq=p;p=p-next;free(q);/whiler-next=NULL;/插入结束后置尾节点指针为 NULL7、试编写算法将带头
24、结点的单链表就地逆置，所谓“就地”是辅助空间复杂度为O(1)。算法思想：将头结点摘下，然后从第一结点开始，一次插入到头结点的后面（头插法建立单链表），直到最后一个结点为止，这样就实现了链表的逆置，如下图所示。13LinkList Reverse(LinkList L)/L 是带头结点的单链表，本算法将 L 逆置LNode*p,*r;/p 为工作指针，r 为 p 的后继，以防断链p=L-next;/从第一个元素结点开始L-next=NULL;/先将头结点 L 的 next 域值为 NULLwhile(p!=NULL)/依次将元素结点摘下r=p-next;/暂存 p 的后继p-next=L-nex
25、t;/将 p 结点插入到头结点之后L-next=p;p=r;return L;8、将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B，使得 A 表中中含有原标中序号为奇数的元素，而 B 表中含有原表中序号为偶数的元素，且保持其相对顺序不变。LinkList DisCreat(LinkList&A)/将 A 表中结点按照序号的奇偶性分解到表 A 或者表 B 中i=0;/i 记录表 A 中结点的序号B=(LinkList)malloc(sizeof(LNode);/创建 B 表表头B-next=NULL;/B 表初始化LNode*ra=A,*rb=B;/ra 和 rb 将分别指向将
26、创建的 A 表和 B 表的尾节点p=A-next;A-next=NULL;/将 A 表置空while(p!=NULL)i+;/序号+1if(i%2=0)/处理序号为偶数的链表结点14rb-next=p;/在表尾插入新结点rb=p;/rb 指向新尾结点elsera-next=p;/处理原序号为奇数的结点ra=p;/在 A 表尾插入新的结点p=p-next;/将 p 恢复为指向新的待处理结点ra-next=NULL;rb-next=NULL;return B;9、设 C=a1，b1，a2，b2，an，bn为线性表，采用头结点的 hc 单链表存放，设计一个就地算法，将其拆分为两个单链表，使得 A=a
27、1，a2，an，B=bn，b2，b1。算法思想：本本题题的的思思路路和和上上题题基基本本一一样样，不不设设置置序序号号变变量量。二者的差别仅在于对B 表的建立不采用尾插法，而是采用头插法。LinkList DisCreat(LinkList&A)LinkList B=(LinkList)malloc(sizeof(LNde);/创建 B 表表头B-next=NULL;/B 表的初始化LNode*p=A-next,*q;/p 为工作指针LNode*ra=A;/ra 始终指向 A 的尾节点while(p!=NULL)ra-next=p;ra=p;/将*p 链接到 A 的表尾p=p-next;q=p
28、-next;p-next=B-next;/头插后，*p 将断链，因此 q 记忆*p 的后继B-next=p;/*p 插入到 B 的前端p=q;ra-next=NULL;/A 的尾节点的 next 域置空return B;10、设计算法将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B 和C，其中 B 表的结点为 A 表中小于零的结点，而 C 表中的结点为 A 表中值大于15零的结点（链表 A 中的元素为非零整数，要求 B、C 表利用 A 表的结点）。【算法思想】首先将 B 表的头结点初始化 A 表的头结点，为 C 申请一个头结点，初始化为空表。从 A 表的首元结点开始，一次对 A 表
29、进行遍历。p 为工作指针，r 为 p 的后继指针。当p-datadata0时，将 p 指向的结点适用前插法插入到 C 表，然后 p 指向新的待插入的结点void Decompose(LinkList&A,LinkList&B,LinkList&C)/单链表 A 分解为两个具有相同结构的链表 B 和 CB=A;B-next=NULL;C=(LinkList)malloc(sizeof(LinkList);C-next=NULL;p=A-next;while(p!=NULL)r=p-next;/暂存 p 的后继if(p-data next=B-next;B-next=p;elsep-next=C-
30、next;C-next=p;p=r;/p 指向新的待处理结点11、设计一个算法，通过一趟遍历确定长度为 n 的单链表中值最大的结点，返回该结点的数据域。【算法思想】此题的关键在于：在遍历的时候利用指针 pmax 记录值最大的结点的 位置。算法思想：初值时候指针 pmax 指向首元结点，然后在遍历过程中，用 pmax 依次和后面的结点进行比较，发现大者则用 pmax 指向该结点。这样将链表从头到尾遍历一遍时，pmax 所指向的结点中的数据即为最大值。ElemType Max(LinkList L)16/确定单链表中值最大的结点if(L-next=NULL)return NULL;pmax=L-n
31、ext;/pmax 指向首元结点p=L-next-next;/p 指向第二个结点while(p!=NULL)/遍历链表，如果下一个结点存在if(p-data pmax-data)pmax=p;/pmax 指向数值大的结点p=p-max;/p 指向下一个结点，继续遍历return pmax-data;12、设设计计一一个个算算法法，删删除除递递增增有有序序表表中中值值大大于于 mink 且且小小于于 maxk（mink 和和 maxk是是给给定定的的两两个个参参数数，其其值值可可以以和和表表中中的的元元素素相相同同，也也可可以以不不同同）的的所所有有元元素素void Delete_Min_Max
32、(LinkList&L,int mink,int maxk)/删除递增有序表 L 中值大于 mink 且小于 maxk 的所有元素p=L-next;while(p&p-data next;while(p&p-data next;q=pre-next;pre-next=p;/修改待删除结点的指针while(q!=p)/依次释放待删除结点的空间s=q-next;free(q);q=s;13、在在一一个个递递增增有有序序的的线线性性表表中中，有有数数值值相相同同的的元元素素存存在在。若若存存储储方方式式为为单单链链表表，设设计计算算法法去去掉掉数数值值相相同同的的元元素素，使使表表中中不不再再具具有
33、有重重复复的的元元素素。【算法思想】注意到题目是有有序序表表，说明所有相同值域的结点都是相邻的。用 p 扫描递增单链17表 L，若*p 结点的值域等于其后继结点的值域，则删除后者，否则 p 移向下一个结点。void DeleteSame(LinkList&L)/L 是递增有序的单链表，本算法删除表中数值相同的元素LNode*p=L-next,*q;/p 为扫描工作指针if(p=NULL)return;while(p-next!=NULL)q=p-next;/q 指向*p 的后继结点if(p-data=q-data)/找到重复值的结点p-next=q-next;/释放 q 结点free(q);e
34、lsep=p-next;14、已知由单链表表示的线性表中,含有 3 类字符的数据元素(如:字母字符数字字符和其他字符),试编写算法构造3个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的节点空间作为这三个表的节点空间,头节点可另辟空间。【算法思想】先创建 3 个头节点,用 p 扫描带头节点的单键表 L,将不同类型的数据元素采用头插法插入到相应的循环单链表中。对应的算法如下:void Split(LinkList*L,LinkList*&A,LinkList*&B,LinkList*&C)LinkList*p=L-next,*q;A=(LinkList*)malloc(size
35、of(LinkList);A-next=A;B=(LinkList*)malloc(sizeof(LinkList);B-next=B;C=(LinkList*)malloc(sizeof(LinkList);C-next=C;while(p!=NULL)if(p-data=A&p-datadata=a&p-datanext;q-next=A-next;18A-next=p;/采用头插法建表 Aelse if(p-data=O&p-datanext;q-next=A-next;A-next=p;/采用头插法建表 Belseq=p;p=p-next;q-next=C-next;C-next=p;
36、/采用头插法建表 C15、已知带头节点的循环单链表 L 中至少有两个节点,每个节点的两个字段为data 和 next,其中 data 的类型为整型。试设计一个算法判断该链表中每个元素的值是否小于其后续两个节点的值之和。若满足,则返回 true;否则返回 false。【算法思想】用 p 扫描整个循环单链表 L,一旦找到这样的节点*p,它使得条件p-datanext-data+p-next-next-data 不成立,则中止循环,返回 0否则继续扫描。当 while 循环正常结束时返回 1。对应的算法如下:bool judge(LinkList*L)LinkList*p=L-next;bool b
37、=true;while(p-next-next!=L&b)if(p-data p-next-data+p-next-next-data)b=false;p=p-next;return b;19双双指指针针策策略略思思想想（重重点点）：一一快快，一一慢慢 一一早早，一一晚晚 一一左左，一一右右【2009 年统考】16、已知一个带有表头结点的单链表，结点结构为：假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中 倒数第 k 个位置上的结点(k 为正整数)。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只 返回 0。要求：（1）描述算
38、法的基本设计思想；（2）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C+语言实现），关键之处请给出简要注释。（1）【算法思想】定义指针 p 和 q，初始化指针时均指向单链表的首元结点。首先将 p 沿链表移动到第 k 个结点，而 q 指针保持不变，这样当 p 移动到第 k+1 个结点时，p 和 q 所指结点的间隔距离为 k。然后 p 和 q 同时向下移动，当 p 为 NULL 时，q 所指向的结点就是该链表倒数第 k 个结点。（2）【算法步骤】设定计数器 i=0，用指针 p 和 q 指向首元结点从首元结点开始依顺着链表 link 依次向下遍历链表，若
39、 p 为 NULL，则转向步骤。若 i 小于 k，则 i+1；否则，q 指向下一个结点。p 指向下一个结点，转步骤。若 i=k，则查找成功，输出该结点的 data 域的值，返回 1；否则，查找失败，返回 0.算算法法如如下下：typedef struct LNodeint data;struct LNode*next;LNode,*LinkList;int Search_k(LinkList list,int k)datalink20/查找链表上第 k 个位置上的结点int i=0;/初始化计数器p=q=list-link;/p，q 均指向首元结点while(p!=NULL)/扫描链表，直到
40、p 为空if(i link;/q 移到下一个结点p=p-link;/p 移动到下一个结点if(i=k)cout data;/查找成功，输出 data 域的值return 1;elsereturn 0;/如果链表长度小于 k，查找失败17、给定一个链表，判断链表中是否有环。如果有环，返回 1，否则返回 0。1）给出算法的基本思想2）根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释下图给出了一个有环的链表。typedef struct ListNodeint data;struct ListNode*next;【算法思想】快慢指针遍历链表，快指针步距为 2，慢指针步距为 1，如果链表
41、带环，两指针一定会在环中相遇。1、判断极端条件，如果链表为空，或者链表只有一个结点，一定不会带环，直接返回 NULL。2、创建快慢指针，都初始化指向头结点。因为快指针每次都要步进 2 个单位，所以在判断其自身有效性的同时还要判断其 next 指针的有效性，在循环条件中21将两语句逻辑与并列起来。初始化慢指针 slow=head，每次向后走一步；初始化快指针 fast=head-next，每次走两步，每走一步判断一次。如果存在环，fast 和 slow 必定会相遇。int hasCycle(ListNode*head)/判断链表是否有环if(head=NULL|head-next=NULL)re
42、turn 0;ListNode*fast=head-next;ListNode*slow=head;while(slow!=fast)if(fast=NULL|fast-next=NULL)/链表无环return 0;slow=slow-next;fast=fast-next-next;return 1;22栈和队列1.回回文文是是指指正正读读反反读读均均相相同同的的字字符符序序列列，如如“abba”和和“abdba”均均是是回回文文，但但“good”不不是是回回文文。试试写写一一个个算算法法判判断断给给定定字字符符序序列列是是否否是是回回文文。（提提示示：将将一一般般字字符符入入栈栈。）【算
43、算法法思思想想】将将字字符符串串前前一一半半入入栈栈，然然后后，栈栈中中元元素素和和字字符符串串后后一一半半比比较较。即即将将第第一一个个出出栈栈元元素素和和后后一一半半串串中中第第一一个个字字符符比比较较，若若相相等等，则则再再出出栈栈一一个个元元素素与与后后一一个个字字符符比比较较，依依次次类类推推，直直至至栈栈空空，在在这这种种情情况况下下可可判判断断该该字字符符序序列列是是回回文文。如如果果出出栈栈元元素素与与串串中中的的字字符符进进行行比比较较时时出出现现不不等等的的情情况况，则则可可判判断断该该字字符符序序列列不不是是回回文文。【算法思想】int isPalindrome(char
44、*t)InitStack(S);len=strlen(t);/求字符串长度for(int i=0;ilen/2;i+)/将一半字符入串Push(S,ti);if(len%2!=0)i+;/长度为奇数，跳过中间字段while(!EmptyStack(S)/每弹出一个字符与相应字符比较int tmp=Pop(S);if(tmp!=ti)return 0;/不相等返回 0elsei+return 1;/比较完毕均相等返回 12.假假设设以以数数组组 Qm存存放放循循环环队队列列的的元元素素，同同时时设设置置一一个个标标志志域域名名 tag，以以 tag=0 和和 tag=1 来来区区别别队队头头指指
45、针针（front）和和队队尾尾指指针针（rear）相相等等时时，队队列列状状态态为为“空空”还还是是“满满”。试试编编写写与与此此结结构构相相应应的的插插入入（EnQueue）和和删删除除（DeQueue）算算法法。【算法思想】在循环队列中，增设一个 tag 类型的整型变量，进队时置 tag 为 1，出队时置 tag为 0（因为入队操作可能导致队满，只有出队操作可能会导致队空）。队列 Q 初试时，置 tag=0，front=rear=0。这样队列的 4 要素如下：队空条件：Q.front=Q.rear&Q.tag=023队满条件：Q.front=Q.rear&Q.tag=1进队操作：Q.dat
46、aQ.rear=x;Q.rear=(Q.rear+1)%MaxSize;Q.tag=1。出队操作：x=Q.dataQ.front；Q.front=(Q.front+1)%MaxSize;Q.tag=0;/设 tag 法的循环队列入队算法int EnQueue(SqQueue&Q,ElemType x)if(Q.front=Q.rear&Q.tag=1)/两个条件都满足时则队满return 0;Q.dataQ.rear=x;Q.rear=(Q.rear+1)%MaxSize;Q.tag=1;return 1;/设 tag 法的循环队列出队算法int DeQueue(SqQueue&Q,ElemT
47、ype&x)if(Q.front=Q.rear&Q.tag=0)return 0;x=Q.dataQ.front;Q.front=(Q.front+1)%MaxSize;Q.tag=0;return 1;3.设设计计一一个个算算法法判判断断输输入入的的表表达达式式中中括括号号是是否否配配对对（假假设设只只含含有有左左、右右圆圆括括号号）【算法思想】该算法在表达式括号匹配时返回真，否则返回假。设置一个链栈 st，扫描表达式exp，遇到左括号时进栈；遇到右括号时，若栈顶为左括号，则出栈，否则返回假。当表达式扫描完毕且栈为空时返回真；否则返回假。算法如下：bool Match(char exp,in
48、t n)int i=0;char e;bool match=true;LinkStNode*st;InitStack(st);/初始化栈while(i lchild);/递归遍历左子树PreOrder(T-rchild);/递归遍历右子树非非递递归归算算法法：void PreOrder(BiTree T)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)printf(p-data);push(S,p);p=p-lchild;elsepop(S,p);p=p-rchild;262.二二叉叉树树的的中中序序非非递递归归遍遍历历中序遍历过程：若二叉树为空，则什么
49、也不做；否则：中中序序遍遍历历左左子子树树访访问问根根结结点点中中旬旬遍遍历历右右子子树树递递归归算算法法：void InOrder(BiTree T)if(T!=NULL)InOrder(T-lchild);visit(T);InOrder(T-rchild);非非递递归归算算法法：void InOrder(BiTree T)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)push(S,p);p=p-lchild;elsepop(S,p);printf(p-data);p=p-rchild;273.二二叉叉树树的的后后序序非非递递归归遍遍历历后后序序遍
50、遍历历过过程程：若若二二叉叉树树为为空空，什什么么也也不不做做，否否则则，后后序序遍遍历历左左子子树树后后序序遍遍历历右右子子树树后后序序遍遍历历根根结结点点递递归归算算法法：void PostOrder(BiTree T)if(T!=NULL)PostOrder(T-lchild);PostOrder(T-rchild);visit(T);非递归算法：void PostOrder(BiTree T)InitStack(T);p=T;while(p|!StackEmpty(S)if(p)push(S,p);p=p-lchild;elsepop(S,p);if(p-rchild&(p-rchil