2022年数据结构经典例题 .pdf

数据结构经典例题1.设计一个算法将L拆分成两个带头节点的单链表L1和 L2。void split(LinkList *&L,LinkList *&L1,LinkList *&L2) LinkList *p=L-next,*q,*r1; /p 指向第 1 个数据节点L1=L; /L1 利用原来 L的头节点r1=L1; /r1 始终指向 L1的尾节点L2=(LinkList *)malloc(sizeof(LinkList);/ 创建 L2 的头节点L2-next=NULL; / 置 L2的指针域为 NULL while (p!=NULL) r1-next=p; / 采用尾插法将 *p(data 值为 ai)插入 L1中r1=p; p=p-next; /p 移向下一个节点 (data 值为 bi) q=p-next; /由于头插法修改 p 的 next 域,故用 q 保存*p 的后继节点p-next=L2-next; / 采用头插法将 *p 插入 L2中L2-next=p; p=q; /p 重新指向 ai+1的节点 r1-next=NULL; / 尾节点 next 置空 2.查找链表中倒数第k 个位置上的节点（ k 为正整数）。若查找成功，算法输出该节点的 data 域的值，并返回 1；否则，只返回 0。typedef struct LNode int data; struct LNode *link; *LinkList; int Searchk(LinkList list,int k) LinkList p,q; int count=0; p=q=list-link; while (p!=NULL) if (countlink; p=p-link; if (countdata); return(1); 3.假定采用带头节点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。设str1 和 str2 分别指向两个单词所在单链表的头节点请设计一个时间上尽可能高效的算法，找出由str1 和 str2 所指向两个链表共同后缀的起始位置。typedef struct Node char data; struct Node *next; SNODE; SNODE * Findlist(SNODE *str1,SNODE *str2) int m,n; SNODE *p,*q; m=Listlen(str1); / 求单链表 str1 的长度 m n=Listlen(str2); / 求单链表 str2 的长度 n for (p=str1;mn;m-) / 若 m 大，则 str1 后移 m-n+1 个节点p=p-next; for (q=str2;mnext; while (p-next!=NULL & p-next!=q-next) p=p-next; /p 、q 两步后移找第一个指针值相等的节点q=q-next; return p-next; int Listlen(SNODE *head) / 求单链表的长度 int len=0; while (head-next!=NUL) len+; head=head-next; return len; 4.设计一个算法，删除一个单链表L中元素值最大的节点。void delmaxnode(LinkList *&L) LinkList *p=L-next,*pre=L,*maxp=p,*maxpre=pre; while (p!=NULL) / 用 p 扫描整个单链表 ,pre 始终指向其前驱节点 if (maxp-datadata) / 若找到一个更大的节点 maxp=p; / 更改 maxp maxpre=pre; / 更改 maxpre 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - pre=p; /p 、pre 同步后移一个节点p=p-next; maxpre-next=maxp-next; / 删除*maxp 节点free(maxp); / 释放*maxp 节点 5. 有一个带头节点的单链表L（至少有一个数据节点） ，设计一个算法使其元素递增有序排列。void sort(LinkList *&L) LinkList *p,*pre,*q; p=L-next-next; /p 指向 L的第 2 个数据节点L-next-next=NULL; / 构造只含一个数据节点的有序表while (p!=NULL) q=p-next; /q 保存*p 节点后继节点的指针pre=L; / 从有序表开头进行比较 ,pre 指向插入 *p 的前驱节点while (pre-next!=NULL & pre-next-datadata) pre=pre-next; / 在有序表中找插入 *p 的前驱节点 *pre p-next=pre-next;/将*pre 之后插入 *p pre-next=p; p=q; / 扫描原单链表余下的节点 6. 有一个带头节点的双链表L，设计一个算法将其所有元素逆置，即第1 个元素变为最后一个元素， 第 2 个元素变为倒数第2 个元素，最后一个元素变为第1 个元素。void reverse(DLinkList *&L) / 双链表节点逆置 DLinkList *p=L-next,*q; /p 指向开好节点L-next=NULL; / 构造只有头节点的双链表L while (p!=NULL) / 扫描 L的数据节点 q=p-next; / 用 q 保存其后继节点p-next=L-next; / 采用头插法将 *p 节点插入if (L-next!=NULL) / 修改其前驱指针L-next-prior=p; L-next=p; p-prior=L; p=q; / 让 p 重新指向其后继节点 7.编写出判断带头节点的双向循环链表L是否对称相等的算法。int Equeal(DLinkList *L) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - int same=1; DLinkList *p=L-next; /p 指向第一个数据节点DLinkList *q=L-prior; /q 指向最后数据节点while (same=1) if (p-data!=q-data) same=0; else if (p=q) break; / 数据节点为奇数的情况q=q-prior; if (p=q) break; / 数据节点为偶数的情况p=p-next; return same; 8.假设有两个有序表LA和 LB表示， 设计一个算法，将它们合并成一个有序表LC 。要求不破坏原有表LA和 LB。void UnionList(SqList *LA,SqList *LB,SqList *&LC) int i=0,j=0,k=0;/i 、j 分别为 LA、LB的下标 ,k 为 LC中元素个数LC=(SqList *)malloc(sizeof(SqList); / 建立有序顺序表 LC while (ilength & jlength) if (LA-dataidataj) LC-datak=LA-datai; i+;k+; else /LA-dataiLB-dataj LC-datak=LB-dataj; j+;k+; while (ilength) /LA 尚未扫描完 ,将其余元素插入 LC中 LC-datak=LA-datai; i+;k+; while (jlength) /LB 尚未扫描完 ,将其余元素插入 LC中 LC-datak=LB-dataj; j+;k+; LC-length=k; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 9.设有 4 个元素 a、b、c、d 进栈，给出它们所有可能的出栈次序。解：所有可能的出栈次序如下: abcd abdc acbd acdb adcb bacd badc bcad bcda bdca cbad cbda cdba dcba 10.编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。bool symmetry(ElemType str) int i; ElemType e; SqStack *st; InitStack(st); / 初始化栈for (i=0;stri!=0;i+) / 将串所有元素进栈Push(st,stri); / 元素进栈for (i=0;stri!=0;i+) Pop(st,e); / 退栈元素 e if (stri!=e) / 若 e 与当前串元素不同则不是对称串 DestroyStack(st);/销毁栈return false; DestroyStack(st); / 销毁栈return true; 11.编写一个算法判断输入的表达式中括号是否配对（假设只含有左、 右圆括号）bool Match(char exp,int n) int i=0; char e; bool match=true; SqStack *st; InitStack(st); / 初始化栈while (inext,*q; int find=0; while (p-next!=NULL & find=0) / 查找ab子串 if (p-data=a & p-next-data=b)/找到子串 p-data=x;p-next-data=z; / 替换为 xyz q=(LiString *)malloc(sizeof(LiString); q-data=y;q-next=p-next;p-next=q; find=1; else p=p-next; 13.含 n 个节点的三次树的最小高度是多少？最大高度是多少？解：设含 n 个节点的（为完全三次树时高度最小）的三次树的最小高度为h，则有：1+3+9+3h-2n1+3+9+3h-1 (3h-1-1)/2 n (3h-1)/2 3h-12n+13h 即：h= log3(2n+1)最大高度为 n-2。14. 假设图 G采用邻接表存储，设计一个算法，输出图G 中从顶点 u 到 v 的所有简单路径。void PathAll(ALGraph *G,int u,int v,int path,int d) /d 是到当前为止已走过的路径长度，调用时初值为-1 int w，i; ArcNode *p; visitedu=1; d+; / 路径长度增 1 pathd=u; / 将当前顶点添加到路径中if (u=v & d1) / 输出一条路径 printf(); for (i=0;iadjlistu.firstarc; /p 指向 u 的第一条边while (p!=NULL) w=p-adjvex; /w 为 u 的邻接顶点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - if (visitedw=0) / 若顶点未标记访问， 则递归访问之PathAll(G,w,v,path,d); p=p-nextarc / 找 u 的下一个邻接顶点 visitedu=0; / 恢复环境 void main() int pathMAXV,u=1,v=4,i,j; MGraph g; ALGraph *G; g.n=5;g.e=6; int AMAXVMAXV= 0,1,0,1,0 ，1,0,1,0,0，0,1,0,1,1， 1,0,1,0,1， 0,0,1,1,0 ; for (i=0;ig.n;i+) / 建立图的邻接矩阵for (j=0;jg.n;j+) g.edgesij=Aij; MatToList(g ，G); for (i=0;ig.n;i+) visitedi=0; printf( 图 G:n);DispAdj(G); / 输出邻接表printf( 从%d到%d的所有路径 :n，u，v); PathAll(G ，u，v，path，-1); printf(n); 15.普里姆（ Prim）算法如下：#define INF 32767 /INF 表示void Prim(MGraph g,int v) int lowcostMAXV; int min; int closestMAXV,i,j,k; for (i=0;ig.n;i+) /给 lowcost和 closest置初值 lowcosti=g.edgesvi; closesti=v; for (i=1;ig.n;i+) / 找出(n-1)个顶点 min=INF; for (j=0;jg.n;j+) /在(V-U)中找出离 U 最近的顶点 k if (lowcostj!=0 & lowcostjmin) min=lowcostj; k=j; /k 记录最近顶点的编号 printf( 边(%d,%d) 权为:%dn,closestk,k,min); lowcostk=0; / 标记 k 已经加入 U 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - for (j=0;jg.n;j+) / 修改数组 lowcost 和 closest if (g.edgeskj!=0 & g.edgeskjlowcostj) lowcostj=g.edgeskj; closestj=k; 16.冒泡排序void BubbleSort(RecType R,int n) int i,j; bool exchange;RecType temp; for (i=0;ii;j-) / 比较,找出最小关键字的记录if (Rj.keyRj-1.key) temp=Rj; Rj=Rj-1;Rj-1=temp; exchange=true; if (exchange=false) return; / 中途结束算法 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -