《数据结构》-王兆红(习题及解答)

习题去掉1，改为习题1去掉1，改为习题1.术语简述数据‌：是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。例如整数、字符串、图形、图像等。数据元素‌：是数据的基本单位，在程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据对象‌：是性质相同的数据元素的集合，是数据的一个子集。数据结构‌：是相互之间存在一种或多种特定关系的数据元素的集合。通常定义为二元组(D,R)，其中D是数据元素的有限集，R是D上关系的有限集。数据类型‌：是一个值的集合和定义在这个值集上的一组操作的总称。例如C语言中的int类型，其值集是整数范围，操作包括加、减、乘、除等。2.逻辑结构与存储结构数据的逻辑结构‌：指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的数学模型。通常分为以下四种基本形式：集合结构‌：数据元素之间除了“同属于一个集合”的关系外，别无其他关系。线性结构‌：数据元素之间存在一对一的关系（如线性表、栈、队列）。树形结构‌：数据元素之间存在一对多的层次关系（如二叉树、一般树）。图状结构（或网状结构）‌：数据元素之间存在多对多的任意关系（如图）。(注：也可简略分为线性结构和非线性结构两大类)数据的存储结构（物理结构）‌：指数据结构在计算机中的表示（又称映像），包括数据元素的表示和关系的表示。通常有以下四种基本形式：顺序存储结构‌：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系（如数组）。链式存储结构‌：借助指示元素存储地址的指针来表示数据元素之间的逻辑关系（如链表）。索引存储结构‌：建立索引表，通过索引来查找数据元素。散列存储结构（哈希存储）‌：根据关键字直接计算数据元素的存储地址。3.《数据结构》课程的内容和任务内容‌：主要研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作。具体包括：基本数据结构‌：线性表、栈、队列、串、数组、广义表、树和二叉树、图等。基本算法技术‌：查找（顺序查找、二分查找、哈希查找等）、排序（插入排序、交换排序、选择排序、归并排序等）。算法分析‌：时间复杂度和空间复杂度的分析与评估。任务‌：学会分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构。掌握各种基本数据结构及其上的典型算法实现。培养算法设计能力，能够针对具体问题设计出高效、正确的算法。提高程序设计的综合能力，为后续课程（如操作系统、编译原理、数据库系统等）打下坚实基础。4.算法的定义、衡量及生活实例何谓算法‌：算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每条指令表示一个或多个操作。算法具有五个重要特性：‌有穷性、确定性、可行性、输入、输出‌。衡量算法执行效率的两个方面‌：时间复杂度‌：算法运行所需的时间随问题规模增长的变化趋势。空间复杂度‌：算法运行过程中所需的辅助存储空间随问题规模增长的变化趋势。生活实例说明‌：问题‌：在一本按页码排序的电话簿中查找某人的电话号码。算法含义体现‌：方法一（顺序查找）‌：从第一页开始，逐页翻找，直到找到名字或翻完为止。这是一个算法，步骤明确，但若电话簿很厚，效率低。方法二（二分查找）‌：先翻开中间页，比较名字拼音。如果目标名字在中间页之前，则在前半部分继续对半翻找；如果在之后，则在后半部分对半翻找。重复此过程直到找到。这体现了算法的‌确定性‌（每一步操作明确）、‌有穷性‌（最终一定能找到或确定不存在）、‌可行性‌（人可以执行翻页和比较动作）。方法二比方法一更高效，体现了算法效率衡量的重要性。5.时间复杂度分析利用大O记法（理论上限）进行分析：(1)i=1;j=0;while(i+j<=n)if(i>j)j++;elsei++;分析‌：每次循环i或j增加1，初始i+j=1，终止条件i+j>n。因此循环执行次数约为n次。时间复杂度‌：O(n)(2)‌y=0;while((y+1)*(y+1)<=n)y++;(3)‌for(i=1;i*i<=n;++i){++x;s+=x;}(4)‌for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++){++x;s+=x;}​(5)‌for(k=1;k<=n;k++)for(i=0;i<=k-1;i++)for(j=0;j<=k-1;j++)if(i!=j){++x;s+=x;}6.求n!的算法及复杂度分析算法实现（C语言风格）：‌longlongFactorial(intn){if(n<0)return-1;//错误处理if(n==0||n==1)return1;longlongresult=1;for(inti=2;i<=n;i++){result*=i;}returnresult;}7.数组反序排列算法及复杂度分析方法一：原地逆置（In-place）算法思想‌：使用两个指针（或下标），一个指向头部，一个指向尾部，交换元素后向中间移动，直到相遇。代码实现：‌voidReverseInPlace(inta[],intn){inttemp;intleft=0;intright=n-1;while(left<right){temp=a[left];a[left]=a[right];a[right]=temp;left++;right--;}}方法二：辅助数组法算法思想‌：创建一个新数组，将原数组元素倒序存入新数组，然后再将新数组内容复制回原数组。代码实现：‌voidReverseWithAux(inta[],intn){intb;//或者动态分配int*b=(int*)malloc(n*sizeof(int));inti;//1.反序存储到新数组for(i=0;i<n;i++){b[i]=a[n-1-i];}//2.复制回原数组for(i=0;i<n;i++){a[i]=b[i];}//如果是动态分配，记得free(b);}

习题去掉1，改为习题2去掉1，改为习题已知一顺序表A，试编写一算法，删除所有元素值为给定值x的元素。//顺序表结构（假设）#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];intlength;}SeqList;voidDeleteAllX(SeqList*A,intx){intk=0;//k记录保留元素的个数for(inti=0;i<A->length;i++){if(A->data[i]!=x){A->data[k++]=A->data[i];//将不等于x的元素前移}}A->length=k;//更新表长}分析‌：时间复杂度：O(n)，遍历一次空间复杂度：O(1)，原地操作设线性表存放在数组A[MAXSIZE]的前num个位置上，且递增有序。试编写一算法，将x插入到线性表的适当位置上，并保持线性表的有序性。voidInsertOrder(intA[],int*num,intMAXSIZE,intx){if(*num>=MAXSIZE){printf("表满，无法插入\n");return;}inti=*num-1;//从后往前找到第一个小于等于x的位置while(i>=0&&A[i]>x){A[i+1]=A[i];//后移i--;}A[i+1]=x;//插入(*num)++;}分析‌：时间复杂度：O(n)，最坏需移动全部元素。空间复杂度：O(1)已知一顺序表L可能含有一个或n个值为给定值x的元素，试编写一算法返回所有这些值为x的元素下标，该算法的函数原型可参考以下形式voidLocate_SeqList(SeqListL,Elemtypex,intr[n]){}其中r[n]为一整型数组，用于存放返回下标。cvoidLocate_SeqList(SeqListL,intx,intr[],int*count){*count=0;for(inti=0;i<L.length;i++){if(L.data[i]==x){r[(*count)++]=i;//记录下标}}}//调用示例：//intr[MAXSIZE],count;//Locate_SeqList(L,x,r,&count);分析‌：时间复杂度：O(n)空间复杂度：O(1)（不计r数组）线性表用顺序存储，设计一算法，用尽可能少的辅助存储空间将顺序表中前m个元素与后n个元素进行整体互换。即将线性表：（a1，a2，…，am，b1，b2，bn）改变为：（b1，b2，…，bn，a1，a2，am）方法：三次逆转法（最少辅助空间）思想‌：原序列：a1a2...amb1b2...bn第一步：将前m个逆转→am...a2a1b1b2...bn第二步：将后n个逆转→am...a1bn...b2b1第三步：整体逆转→b1b2...bna1a2...amvoidReverse(intA[],intleft,intright){while(left<right){inttemp=A[left];A[left]=A[right];A[right]=temp;left++;right--;}}voidSwapMN(intA[],intm,intn,inttotal){//total=m+nReverse(A,0,m-1);//逆转前m个Reverse(A,m,total-1);//逆转后n个Reverse(A,0,total-1);//整体逆转}分析‌：时间复杂度：O(m+n)，每个元素最多被交换两次空间复杂度：O(1)，只用一个临时变量已知带头结点的单链表L中的结点是按整数值递增有序排列的，试编写一算法，将给定值x插入到表L中，使得L仍然有序，并分析算法的时间复杂度。typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;voidInsertOrdered(LinkListL,intx){LNode*pre=L;//从头结点开始LNode*p=L->next;//查找插入位置while(p!=NULL&&p->data<x){pre=p;p=p->next;}//创建新结点并插入LNode*s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=p;pre->next=s;}时间复杂度分析‌：最好：O(1)（插入表头）最坏：O(n)（插入表尾或中间）平均：O(n)试设计一学生信息表的单链表结点结构，该结点结构的数据域包含学生的学号（num）、姓名（name）、性别（sex）、年龄（age）、家庭住址（address）等5项，并编写一算法，创建具有n个学生记录的单链表的算法。结点结构定义typedefstructStudent{intnum;//学号charname;//姓名charsex;//性别'M'/'F'intage;//年龄charaddress;//家庭住址}Student;typedefstructLNode{Studentdata;structLNode*next;}LNode,*LinkList;创建n个学生记录的单链表（头插法）LinkListCreateStudentList(intn){LinkListL=(LNode*)malloc(sizeof(LNode));L->next=NULL;for(inti=0;i<n;i++){LNode*s=(LNode*)malloc(sizeof(LNode));printf("请输入第%d个学生信息(学号姓名性别年龄住址):\n",i+1);scanf("%d%s%c%d%s",&s->data.num,s->,&s->data.sex,&s->data.age,s->data.address);s->next=L->next;//头插法L->next=s;}returnL;}分析‌：时间复杂度：O(n)空间复杂度：O(1)试编写一算法，计算带有头结点的循环单链表L中结点的个数。intCountNodes(LinkListL){if(L==NULL||L->next==L)return0;intcount=0;LNode*p=L->next;//从第一个结点开始do{count++;p=p->next;}while(p!=L->next);//回到头结点returncount;}分析‌：时间复杂度：O(n)空间复杂度：O(1)一元稀疏多项式是指指数相差很大的一元多项式。试设计一元稀疏多项式的单链表结点结构，在该结构中，数据域需要存储每一项系数、指数，指针域与一般单链表相同，并进行相应的数据类型定义。数据类型定义ctypedefstructPolyNode{floatcoef;//系数intexpn;//指数structPolyNode*next;//指针域}PolyNode,*Polynomial;试编写一算法，在带有头结点的双向链表DL的第i个元素之前插入值为x的元素结点，并返回插入后的双向链表的头指针。typedefstructDNode{intdata;structDNode*prior,*next;}DNode,*DLinkList;DLinkListInsertBeforeI(DLinkListDL,inti,intx){if(i<1)returnDL;//位置非法DNode*p=DL->next;intj=1;//找到第i个结点while(p!=NULL&&j<i){p=p->next;j++;}if(p==NULL){printf("位置i超出链表长度\n");returnDL;}//创建新结点DNode*s=(DNode*)malloc(sizeof(DNode));s->data=x;//插入到p之前s->prior=p->prior;s->next=p;if(p->prior!=NULL)p->prior->next=s;p->prior=s;returnDL;}分析‌：时间复杂度：O(ｎ)，最坏O(n)空间复杂度：O(1)10﹒试编写一算法，在带有头结点的双向链表DL中删除第1个元素值为x的结点，并返回删除结点后的双向链表的头指针。DLinkListDeleteFirstX(DLinkListDL,intx){DNode*p=DL->next;//查找第一个值为x的结点while(p!=NULL&&p->data!=x){p=p->next;}if(p==NULL){printf("未找到值为%d的结点\n",x);returnDL;}//删除结点pif(p->prior!=NULL)p->prior->next=p->next;if(p->next!=NULL)p->next->prior=p->prior;free(p);returnDL;}分析‌：时间复杂度：O(n)，最坏需遍历全部结点空间复杂度：O(1)

习题去掉1，改为习题3去掉1，改为习题1、试以绘图法说明栈的特性。列举栈的两种用途，并简要说明它们是如何用到栈的特性的。d4←栈顶（Top）d3d2d1特性：后进先出（LIFO）——最后入栈的d4最先出栈用途说明‌①表达式求值：利用栈的LIFO特性，遇到左括号入栈，遇到右括号则栈顶运算符出栈进行运算，保证运算顺序正确（先算内层括号）‌②递归调用：函数调用时，系统用栈保存返回地址和局部变量，先调用的函数后返回（后进先出），保证嵌套调用的正确恢复2、设有编号为1，2，3，4的四辆列车依次进入某一火车站，列车调度员利用栈式结构对这四辆列车的出站序列进行调度，试写出所有可能的出站序列。序号出站序列序号出站序列112348321421243932413132410342141342114321514321243126213413423172143144213总数是卡特兰数3、试证明：若借助栈的结构输入数据的序列为d1，d2，…，dn，设i<j<k，则在输出序列中不可能出现这样的序列：dk，…，di，…，dj。证明（反证法）假设‌：输出序列中出现了dk,…,di,…,dj（其中i<j<k）。分析‌：因为i<j<k，入栈顺序是di先入，dj次之，dk最后入。输出中dk出现在di之前，说明dk出栈时di仍在栈中（否则di不可能在dk之后出）。既然dk出栈时di在栈中，那么di在dk之上（因为di先入）。又因为i<j<k，dj在di之后入栈、在dk之前入栈，所以当dk出栈时，dj一定也在栈中，且在di和dk之间。栈是LIFO结构，dj在di之上，所以‌dj必定比di先出栈‌。矛盾‌：假设中di出现在dj之前，但实际上dj应先于di出栈。结论‌：假设不成立，输出序列中不可能出现dk,…,di,…,dj。4、写出以下运算式的后续算术运算式：（1）3x2+x-1/x+5（2）(A+B)*C-D/(E+F)+G（3）A&&B||C!(D>E)后缀表达式‌：3x2^*x+1x/-5+AB+C*DEF+/-G+AB&&CDE>!||试以表3-2的形式，写出后缀表达式AB+C-DE/+用栈进行求值的过程。步骤栈状态（栈顶→栈底）操作读入AA压栈读入BBA压栈读入+(A+B)弹出A,B，计算A+B，结果压栈读入CC(A+B)压栈读入-(A+B-C)弹出C,(A+B)，计算(A+B)-C，结果压栈读入DD(A+B-C)压栈读入EED(A+B-C)压栈读入/(D/E)(A+B-C)弹出E,D，计算D/E，结果压栈读入+(A+B-C+D/E)弹出(D/E),(A+B-C)，相加称正读和反读都相同的序列为“回文”，例如“asdfgfdsa”和“qwerewq”是回文，而“zxcvbcxz”不是回文。试编写一算法判断读入的一个以“”为结束符的字符序列是否为回文。思路‌：读入字符时依次入栈栈中元素出栈顺序恰好是原序列的逆序将原序列与出栈序列逐位比较，全部相同则为回文#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100typedefstruct{chardata[MAXSIZE];inttop;}SeqStack;voidInitStack(SeqStack*S){S->top=-1;}intIsEmpty(SeqStack*S){returnS->top==-1;}voidPush(SeqStack*S,charch){if(S->top<MAXSIZE-1)S->data[++(S->top)]=ch;}charPop(SeqStack*S){if(!IsEmpty(S))returnS->data[(S->top)--];return'\0';}intIsPalindrome(){SeqStackS;InitStack(&S);charch,str[MAXSIZE];inti,len=0;printf("请输入字符序列（以#结束）：");ch=getchar();while(ch!='#'){str[len++]=ch;Push(&S,ch);ch=getchar();}for(i=0;i<len;i++){if(str[i]!=Pop(&S)){return0;//不是回文}}return1;//是回文}7、在一个有限的空间MAXSIZE（设MAXSIZE=1024）中设计两个顺序存储结构的栈S1和S2，当且仅当空间全满时才会产生溢出，并分别编写入栈算法push(S1，x)、push(S2，x)和出栈算法pop(S1)、pop(S2)。结构定义#defineMAXSIZE1024typedefstruct{chardata[MAXSIZE];inttop1;//S1栈顶，从0开始向右增长inttop2;//S2栈顶，从MAXSIZE-1开始向左增长}DoubleStack;入栈算法//S1入栈intPush_S1(DoubleStack*S,charx){if(S->top1+1==S->top2)//空间全满才溢出return0;//溢出S->data[++(S->top1)]=x;return1;//成功}//S2入栈intPush_S2(DoubleStack*S,charx){if(S->top1+1==S->top2)//空间全满才溢出return0;//溢出S->data[--(S->top2)]=x;return1;//成功}出栈算法//S1出栈charPop_S1(DoubleStack*S){if(S->top1==-1)return'\0';//栈空returnS->data[(S->top1)--];}//S2出栈charPop_S2(DoubleStack*S){if(S->top2==MAXSIZE)return'\0';//栈空returnS->data[(S->top2)++];}

习题去掉1，改为习题4去掉1，改为习题栈与队列习题解答简述栈和队列的相同点和不同点。相同点都是线性表 逻辑上都是线性结构都是受限操作 只能在特定位置插入/删除都可用顺序或链式存储 两种存储结构都适用不同点比较项 栈 队列插入删除位置 同一端（栈顶） 两端（队尾入，队头出）运算规则 后进先出（LIFO） 先进先出（FIFO）指针设置 一个栈顶指针 队头指针+队尾指针典型应用 递归、表达式求值、括号匹配 排队、缓冲区、广度优先搜索利用两个栈模拟一个队列的入队、出队和判断队空的运算。思路栈S1‌：负责入队（压栈）栈S2‌：负责出队（弹栈）当S2为空时，把S1中元素全部弹出压入S2（顺序颠倒，实现FIFO）算法实现typedefstruct{intdata[MAXSIZE];inttop;}SeqStack;voidInitStack(SeqStack*S){S->top=-1;}intIsEmpty(SeqStack*S){returnS->top==-1;}voidPush(SeqStack*S,intx){S->data[++(S->top)]=x;}intPop(SeqStack*S){returnS->data[(S->top)--];}//模拟队列的两个栈SeqStackS1,S2;//入队voidEnQueue(intx){Push(&S1,x);}//出队intDeQueue(){if(IsEmpty(&S1)&&IsEmpty(&S2)){printf("队列为空\n");return-1;}if(IsEmpty(&S2)){while(!IsEmpty(&S1)){Push(&S2,Pop(&S1));}}returnPop(&S2);}//判断队空intIsQueueEmpty(){returnIsEmpty(&S1)&&IsEmpty(&S2);}写一个算法，将一个链式队列中的元素依次取出，并打印元素值。typedefstructQNode{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;voidPrintQueue(LinkQueue*Q){if(Q->front==Q->rear){printf("队列为空\n");return;}QueuePtrp=Q->front->next;//从第一个元素开始while(p!=Q->rear){printf("%d",p->data);p=p->next;}printf("\n");}写出一个算法，求一个具有MAXSIZE个单元的循环队列中元素的个数。#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];intfront;//队头指针intrear;//队尾指针}CircularQueue;intCountElements(CircularQueue*Q){return(Q->rear-Q->front+MAXSIZE)%MAXSIZE;}说明‌：rear>=front时：元素个数=rear-frontrear<front时：元素个数=rear-front+MAXSIZE统一公式：(rear-front+MAXSIZE)%MAXSIZE对于一个具有m个元素的循环队列，写出求队列中元素个数的公式。元素个数=(rear−front+m)modm其中m为循环队列的最大容量（MAXSIZE）循环队列的队头指针总是指向队头元素的前一位置，链队列的队头指针总是指向队头元素，而无论循环队列还是链表队列，队尾指针总是指向队尾元素。试画出有两种不同存储结构的示意图，及这两种结构的元素出入队示意图。循环队列（数组存储）text队头指针front指向队头元素前一位置队尾指针rear指向队尾元素索引:0123456[][A][B][C][][][]↑↑frontrearfront=0(指向队头A的前一位置0)rear=3(指向队尾C)元素:A,B,C入队示意图‌：入队D前:front=0,rear=3入队D后:front=0,rear=4索引:0123456[][A][B][C][D][][]↑↑frontrear出队示意图‌：出队前:front=0,rear=4出队A后:front=1,rear=4索引:0123456[][][B][C][D][][]↑↑frontrear链队列（链表存储）front→[A]→[B]→[C]→[D]←rear↑↑队头指针(指队头结点)队尾指针(指向队尾结点)rear指向最后一个有数据的结点入队示意图‌：入队E前:front→[A]→[B]→[C]→[D]←rear入队E后:front→[A]→[B]→[C]→[D]→[E]←rear出队示意图‌：出队前:front→[A]→[B]→[C]→[D]←rear出队A后:front→[B]→[C]→[D]←rear设一数组se[m]存放循环队列的元素，同时设变量front和rear分别作为队头指针和队尾指针，试给出判别此循环队列的队空和队满条件，并且写出相应入队和出队的算法。判别条件表格条件 公式队空‌ front==rear//队头指向空队满‌ (rear+1)%m==front牺牲一个存储单元来区分队空和队满算法实现#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];intfront;intrear;}CircularQueue;voidInitQueue(CircularQueue*Q){Q->front=Q->rear=0;}intIsEmpty(CircularQueue*Q){returnQ->front==Q->rear;}intIsFull(CircularQueue*Q){return(Q->rear+1)%MAXSIZE==Q->front;}//入队intEnQueue(CircularQueue*Q,intx){if(IsFull(Q)){printf("队列已满\n");return0;}Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE;return1;}//出队intDeQueue(CircularQueue*Q,int*x){if(IsEmpty(Q)){printf("队列为空\n");return0;}*x=Q->data[Q->front];Q->front=(Q->front+1)%MAXSIZE;return1;}

习题去掉1，改为习题5去掉1，改为习题空串和空格串有什么区别？比较项空串空格串‌长度‌0>0（含空格字符）‌内容‌不含任何字符包含一个或多个空格字符''‌表示‌""""（如3个空格）‌本质‌无元素的串有元素的串（元素是空格）两个字符串相等的充要条件是什么？条件 说明①长度相等‌ len(s)=len(t)②对应位置上字符相等s[i]=t[i]串的三种机内表示方法是什么？序号方法说明1‌定长顺序存储‌用固定长度的数组存储，结构简单但浪费空间2‌堆分配存储‌运行时动态分配，按需申请空间3‌块链存储‌用链表存储，每个结点存一个字符块，适合长串写一算法。在定长顺序串上实现串的判等操作Equal(s,t)。#defineMAXSIZE100typedefstruct{chardata[MAXSIZE];intlength;}SeqString;intEqual(SeqStrings,SeqStringt){if(s.length!=t.length)return0;//长度不等，不相等for(inti=0;i<s.length;i++){if(s.data[i]!=t.data[i])return0;//对应字符不同}return1;//完全相等}写一算法。将字符串S2中的全部字符拷贝到字符串S1中，不能利用StrCopy函数。字符串采用堆分配存储表示。typedefstruct{char*ch;//指向堆中字符数组intlength;//串长度}HString;voidStrCopy(HString*S1,HStringS2){//释放S1原有空间if(S1->ch)free(S1->ch);//分配新空间S1->ch=(char*)malloc(S2.length*sizeof(char));//逐字符拷贝for(inti=0;i<S2.length;i++){S1->ch[i]=S2.ch[i];}S1->length=S2.length;}利用C的库函数strlen、strcpy和strcat写一个算法voidStrInsert(char*s,char*t,inti)，将串t插入到s的第i个位置上.若i大于s的长度，则插入不执行。#include<string.h>voidStrInsert(char*s,char*t,inti){intlen=strlen(s);if(i>len)return;//i大于s长度，不执行//在s的第i个位置插入t（i从1开始计数，转为下标i-1）chartemp;//拷贝s的前i-1个字符strncpy(temp,s,i-1);temp[i-1]='\0';//拼接tstrcat(temp,t);//拼接s剩余部分strcat(temp,s+i-1);//拷回sstrcpy(s,temp);}采用顺序结构存储串，编写一个函数，求串s和串t的一个最长的公共子串。#include<stdio.h>#include<string.h>//参数说明：//s：第一个顺序存储串，t：第二个顺序存储串，res：存放最终最长公共子串voidLongestCommonSub(chars[],chart[],charres[]){//第一步：计算两个字符串长度intlenS=strlen(s);intlenT=strlen(t);//第一步定义全局记录变量intmaxLen=0;//保存最长公共子串长度，初始0intstartIndex=0;//保存最长子串在s中的起始下标//第二步：外层循环，遍历S所有起点ifor(inti=0;i<lenS;i++){//第三步：内层循环，遍历T所有起点jfor(intj=0;j<lenT;j++){intk=0;//向后匹配的偏移量，从0开始//第四步：循环向后连续匹配字符，不越界且字符相等就继续while((i+k)<lenS&&(j+k)<lenT&&s[i+k]==t[j+k]){k++;}//第五步：如果本次匹配长度更长，更新记录if(k>maxLen){maxLen=k;startIndex=i;}}}//第六步：截取最长公共子串，存入结果数组resintpos=0;for(inti=startIndex;i<startIndex+maxLen;i++){res[pos++]=s[i];}res[pos]='\0';//字符串结束标记}intmain(){//顺序存储字符串（字符数组就是顺序存储结构）charstrS[100]="abcdefgh";charstrT[100]="xdefab";charresult[100];//调用函数LongestCommonSub(strS,strT,result);//第七步：判断输出结果if(maxLen==0)printf("两个字符串无公共连续子串\n");elseprintf("最长公共连续子串：%s\n",result);return0;}代码和思路一一对应对照1.

先求字符串长度、定义

maxLen

、

startIndex

；2.

for(i)

遍历S每一个起点；3.

for(j)

遍历T每一个起点；4.

while

循环从i、j位置向后连续匹配相同字符，统计匹配长度k；5.

判断

k>maxLen

，更新最长子串的长度和起始位置；6.

双重循环结束后，从原串截取最长片段赋值给结果数组；7.

主函数判断长度，输出最终答案。补充边界测试案例案例1：无公共字符strS="12345",strT="abcde"输出：两个字符串无公共连续子串案例2：完全相同字符串strS="hello",strT="hello"输出：hello采用顺序存储结构存储串，编写一个函数，求一个子串在一个字符串中出现的次数，如果该子串不出现则为0。intCountSubstring(char*s,char*t){intlen_s=strlen(s);intlen_t=strlen(t);intcount=0;if(len_t==0)return0;//空子串for(inti=0;i<=len_s-len_t;i++){intj;for(j=0;j<len_t;j++){if(s[i+j]!=t[j])break;}if(j==len_t)//完全匹配count++;}returncount;}已知主串s=“ADBADABBAABADABBADADA”模式串pat=“ADABBADADA”画出KMP算法匹配的全过程。主串‌：s="ADBADABBAABADABBADADA"模式串‌：pat="ADABBADADA"第一步：计算next数组j12345678910pat[j]ADABBADADAnext[j]0112112343模式串长度len=10匹配规则：s[i]=pat[j]：i++,j++s[i]<>pat[j]：j=next[j])；若(j=0)，(i++,j=1)终止：(j>10)匹配成功；(i>21)匹配失败三、KMP完整匹配过程初始状态：i=1,j=1第1轮匹配i=1,j=1：A=A→i=2,j=2i=2,j=2：D=D→i=3,j=3i=3,j=3：B<>Aj=next[3]=1i=3,j=1：B<>Aj=next[1]=0j=0→i=4,j=1当前位置：i=4,j=1plaintexts:ADBADABBAABADABBADADApat:AD×第2轮匹配（i=4,j=1）i=4,j=1:A=A→i=5,j=2i=5,j=2:D=D→i=6,j=3i=6,j=3:A=A→i=7,j=4i=7,j=4:B=B→i=8,j=5i=8,j=5:B=B→i=9,j=6i=9,j=6:A=A→i=10,j=7i=10,j=7：A<>Dj=next[7]=2i=10,j=2：A<>Dj=next[2]=1i=10,j=1：A=A→i=11,j=2i=11,j=2：B<>Dj=next[2]=1i=11,j=1：B<>Aj=next[1]=0j=0→i=12,j=1当前位置：i=12,j=1plaintexts:ADBADABBAABADABBADADApat:ADABBA×第3轮匹配（i=12,j=1）i=12,j=1:A=A→i=13,j=2i=13,j=2:D=D→i=14,j=3i=14,j=3:A=A→i=15,j=4i=15,j=4:B=B→i=16,j=5i=16,j=5:B=B→i=17,j=6i=17,j=6:A=A→i=18,j=7i=18,j=7:D=D→i=19,j=8i=19,j=8:A=A→i=20,j=9i=20,j=9:D=D→i=21,j=10i=21,j=10:A=A→i=22,j=11j=11>10匹配成功！匹配起始下标：i-len(pat)=22-10=12对齐示意图plaintexts:ADBADABBAAB[ADABBADADA]pat:ADABBADADA↑起点i=1210．编写对串求逆的算法。一、定义回顾#defineMAXLEN100typedefstruct{charch[MAXLEN+1];//ch[1..length]存放字符，ch[0]闲置intlength;}SString;方案1：顺序串求逆算法思想设串长度为n，使用双指针：i从前向后：初始i=1j从后向前：初始j=s.length交换s.ch[i]与s.ch[j]；i++，j--；直到i>=jC语言伪代码//功能：将顺序串s逆置voidStrReverse(SString&s){inti=1,j=s.length;chartemp;while(i<j){temp=s.ch[i];s.ch[i]=s.ch[j];s.ch[j]=temp;i++;j--;}}算法分析时间复杂度：\(O(n)\)，n为串长度空间复杂度：\(O(1)\)，原地逆置，仅使用临时变量方案2：另一种写法（不原地存储新串，适合题目要求保留原串）voidStrReverse(SStrings,SString&t){t.length=s.length;for(inti=1;i<=s.length;i++){t.ch[i]=s.ch[s.length-i+1];}}区别：生成新串t，原串s不变；原地逆置会直接修改原串。方案3：链式字符串（链串求逆）链结点定义：typedefstructLNode{chardata;structLNode*next;}LNode,*LinkStr;链串原地逆置算法（头插法）LinkStrLinkStrReverse(LinkStrhead){LNode*p=head->next,*q;head->next=NULL;//断开原链表while(p!=NULL){q=p->next;p->next=head->next;head->next=p;p=q;}returnhead;}11．编写算法，在串的堆存储结构上实现串的基本操作Concat（串连接）。1.堆串结构体定义堆存储：动态分配一维字符数组，通过指针引用字符空间。typedefstruct{char*ch;//动态分配的字符数组；NULL表示空串intlength;//串当前长度}HString;功能：Concat(&T,S1,S2)用T返回由S1和S2连接而成的新串，T=S1+S2。2.算法思想释放T原有空间（防止内存泄漏）；计算新串总长度：len=S1.length+S2.length；如果长度为0，置为空串直接返回；向堆区分配连续内存存放S1+S2；先复制S1全部字符，接着复制S2全部字符；设置T的长度。3.完整算法代码//由S1和S2连接得到新串TStatusConcat(HString&T,HStringS1,HStringS2){//释放T原有的堆空间if(T.ch)free(T.ch);intlen1=S1.length;intlen2=S2.length;T.length=len1+len2;if(T.length==0){T.ch=NULL;returnOK;}//分配堆空间T.ch=(char*)malloc(T.length*sizeof(char));if(!T.ch)returnOVERFLOW;//分配失败//复制S1for(inti=0;i<len1;i++)T.ch[i]=S1.ch[i];//复制S2，接在S1后面for(inti=0;i<len2;i++)T.ch[len1+i]=S2.ch[i];returnOK;}⚠️注意：堆串下标从0开始。复杂度分析时间复杂度：O(len(S1)+len(S2))空间复杂度：O(len(S1)+len(S2))（新建目标串空间）必须先释放T旧空间，否则内存泄漏；需要判断malloc是否成功；空串处理：长度为0时不能malloc，ch置NULL；区别：顺序串是静态数组，堆串是malloc动态堆内存。

习题去掉1，改为习题6去掉1，改为习题1．假设按行优先存储数组A[5][8]时，第一个元素的字节地址是100，每个整数占4个字节。问下列元素的存储地址是多少？(1)a00(2)a11(3)a25(4)a472．设有二维数组A(6×8)，每个元素占6个字节存储，实现存放，a00的起始地址为1000，计算：（1）数组A所占的存储空间。（2）元素A14和元素A47的地址。（3）元素A14和元素A47之间相差的字节数。二维数组A，假设A（1，1）与A（3，3）的地址分别为1204和1244，设每个元素占d个字节，求A（4，4）的地址。4．设数组R[n]的n个元素中（n>1）有多个零元素，试设计一个算法，将R中所有非零元素依次移动到R数组的前端。voidMoveNonZero(intR[],intn){intk=0;for(inti=0;i<n;i++){if(R[i]!=0){R[k]=R[i];k++;}}//可选：后面位置填充0for(inti=k;i<n;i++)R[i]=0;}时间\(O(n)\)，空间\(O(1)\)设有三角矩阵A，用一维数组B存放A中的对角线上的元素aij,试设计由A确定B中元素的算法。题意：三角矩阵A，一维数组B只存放对角线上元素a[i][i]矩阵下标从0开始，a[i][i]为第i个对角线元素。映射关系：B[i]=A[i][i]算法//若aij是对角线元素，返回B中的下标；否则返回-1intGetIndex(inti,intj){if(i==j)returni;elsereturn-1;}设有稀疏矩阵A如图6.21所示，求：将稀疏矩阵A表示成三元组表；将稀疏矩阵A的转置矩阵表示成三元组表。500408500408003000000700000000600000A=图6.21稀疏矩阵A的三元组表5,5,6（5行5列6个非0元素，下标1开始）1,1,51,4,41,5,82,3,33,4,75,1,6A的转置矩阵的三元组表5,5,61,1,51,4,41,5,62,3,33,4,74,1,8假设矩阵A和B均是具有m行n列的稀疏矩阵，且都采用三元组表示，编写一算法计算C=A+B，要求C也采用三元组表示。StatusAddSMatrix(TSMatrixA,TSMatrixB,TSMatrix&C){if(A.mu!=B.mu||A.nu!=B.nu)returnERROR;//行列不匹配，无法相加intp=0,q=0,r=0;intmu=A.mu,nu=A.nu;C.mu=mu;C.nu=nu;while(p<A.tu&&q<B.tu){Triplea=A.data[p];Tripleb=B.data[q];longposA=(long)a.i*nu+a.j;longposB=(long)b.i*nu+b.j;if(posA<posB)//A元素位置靠前{C.data[\(r++\)]=a;p++;}elseif(posA>posB)//B元素位置靠前{C.data[\(r++\)]=b;q++;}else//同一位置，相加{ElemTypesum=a.e+b.e;if(sum!=0){C.data[r].i=a.i;C.data[r].j=a.j;C.data[r].e=sum;\(r++\);}p++;q++;}}//复制A剩下元素while(p<A.tu)C.data[\(r++\)]=A.data[p++];//复制B剩下元素while(q<B.tu)C.data[\(r++\)]=B.data[q++];C.tu=r;returnOK;}广义表是线性结构还是非线性结构？为什么？广义表属于非线性结构。理由：线性表中所有元素均为原子，元素之间构成单一的线性序列；而广义表的数据元素既可以是原子，也可以是子广义表，存在嵌套层次关系，数据元素可能带有分支，不满足线性结构的定义，因此广义表是非线性结构。9.设有广义表：E=（b,g）,D=（c,d,e）,F=(D,f),C=(a,D),A(改大写)=(C,E,F),画出A的链式存储结构；求出各表的长度和深度。广义表长度（第一层元素个数）深度D=(c,d,e)31E=(b,g)21C=(a,D)22F=(D,f)22A=(C,E,F)3310．求下列对广义表操作的结果head(((a,b),(c,d)));head(tail(((a,b),(c,d)));tail(head(((a,b),(c,d)));tail(head(tail(((a,b),(c,d)))));head(tail(head(((a,b),(c,d)))));

习题去掉1，改为习题7去掉1，改为习题除了孩子兄弟表示法之外，树的其它表示法有什么缺点，为什么要用二叉树来表示树或森林？（1）树常见表示方法及缺点树常用4种表示：双亲表示法、孩子表示法、孩子兄弟表示法①双亲表示法存储结构：数组存储结点，每个结点保存〔数据父结点下标〔✅优点：快速查找某个结点的双亲❌缺点：查找孩子结点效率极低；想要遍历一个结点所有孩子，必须扫描整个数组；无法直接寻找兄弟结点。②孩子表示法两种实现：1）多重链表（每个结点设置多个指针，指针数量等于树的度）❌缺点：树中各个结点度不统一，需要开辟大量空指针，空间浪费严重。2）孩子链表（数组存结点，每个结点附带一条孩子链表）✅优化了空间；但仍存在短板：快速查找双亲不方便；查找兄弟结点麻烦。③孩子兄弟表示法（二叉树表示法）结点结构：〔数据域第一个孩子指针右兄弟指针〕这是可以把树/森林转化为二叉树的核心结构。（2）为什么要用二叉树表示树或森林？1.二叉树存储结构规整统一二叉树结点结构固定（左、右孩子两个指针），不存在指针数量不统一、空间浪费问题；相比树的多重链表，存储效率高。可以复用二叉树成熟算法树、森林的遍历、查找等操作，转换为二叉树之后，直接使用二叉树遍历（先序、中序）等一套成熟算法，不用单独为树设计新算法。树、森林与二叉树存在一一对应关系任何一棵树/森林唯一对应一棵二叉树，反过来这棵二叉树也能还原出原始树/森林，转换无信息丢失。4.便于算法实现计算机语言中指针实现二叉链表十分方便，是工程上最容易编码实现的树形存储方案。试画出具有三个结点的二叉树的各种形态。1.根结点，只有左孩子；左孩子只有左孩子A/B/C2.根结点，只有左孩子；左孩子只有右孩子A/B\C3.根结点，左、右各一个孩子A/\BC4.根结点，只有右孩子；右孩子只有左孩子A\B/C5.根结点，只有右孩子；右孩子只有右孩子A\B\C已知一棵二叉树如图所示，试分别写出按中序、先序和后序遍历时所得到的结点序列。并将其转换成对应的树或森林。题3图需要给出图号，并在图上面的正文中引出，也就是先文后图。全书类似统改需要给出图号，并在图上面的正文中引出，也就是先文后图。全书类似统改画出题3图用完全二叉树顺序存储的形态结构表。下标i1234567891011121314结点ABE∅CFG∅∅∅D∅∅H于如下图所示的树，写出其先根遍历和后根遍历序列，并将其转换成对应的二叉树题5图同上，全书统改同上，全书统改✅先根遍历（树）：ABCEIJFGKHD✅后根遍历（树）：BIJEFKGHCDA已知一棵二叉树的先序和中序遍历序列分别为：先序ABCDEFGHI中序BCAEDGHFI试恢复该二叉树。画出表达式((a+b)+c*(d+e))*(f+g)的二叉树，写出其相应的中序遍历序列，并将其转化为相应的树或森林。中序序列：a+b+c*d+e*f+g⚠注意：直接中序遍历没有括号，不能体现优先级；原始带括号表达式是人为添加，单纯遍历结果如上。画出如题3图所示的二叉树的先序和中序线索二叉树。先序序列：A,B,C,D,E,F,G,H中序序列：B,C,D,A,F,E,H,G已知有六个带权结点，其权值分别为3，10，6，12，5，15，试以他们为叶子结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序画图），计算出带权路径长度WPL，并写出每个结点的哈夫曼编码。正确哈夫曼编码汇总权值3：1010权值5：1011权值6：100权值10：00权值12：01权值15：11

习题去掉1，改为习题8去掉1，改为习题下列所示为一有向图，请给出该图下述要求：每个顶点的入/出度；习题、考研题目中的图需要编图号、图名，文中需要引出，先文后图，全书统查统改习题、考研题目中的图需要编图号、图名，文中需要引出，先文后图，全书统查统改顶点出边集合出度入边集合入度115，162211221，23，243621336123,43,633443124,52,643554115，652662，64，65316,362邻接矩阵；邻接表；逆邻接表；强连通分量。2．对一下给出的无向带权图（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树。（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。3．试列出下图中所有的拓扑排序。4．计算从顶点2到其他各顶点的最短路径及长度，画表写出求解过程。5．已知工程图表示如下，请求解关键路径，要求写出关键事件和关键活动的求解过程。(改)编写一个函数根据用户输入的偶对（以输入0表示结束）表示边，建立有向图的邻接表的算法。#defineMAX_VERTEX_NUM20//最大顶点数//边表结点typedefstructEdgeNode{intadjvex;//邻接点下标structEdgeNode*nextedge;}EdgeNode;//顶点表结点typedefstructVNode{intdata;//顶点编号EdgeNode*firstedge;}VNode,AdjList[MAX_VERTEX_NUM];//有向图邻接表typedefstruct{AdjListvertices;intvexnum;//当前顶点总数intarcnum;//当前边总数}ALGraph;/***@brief根据输入的偶对<i,j>建立有向图的邻接表存储结构*@paramG指向邻接表有向图ALGraph结构体的指针*@details输入格式：逐行输入有向边起点i、终点j；输入00终止录入*采用【头插法】构建边链表；自动识别并新增未出现过的顶点*有向边<i,j>代表从顶点i指向顶点j，仅在i的边链表增加边结点*/voidCreateDG(ALGraph*G){inti,j;//i：边起点数据；j：边终点数据EdgeNode*p;//临时边结点指针，用于