2.4程序设计题1．设顺序表va中的数据元素递增有序。试设计一个算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
voidInsert_SqList(SqListva,intx)/*把x插入递增有序表va中*/{inti;if(va.length>MAXSIZE)return;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;va.length++;}/*Insert_SqList*/2．设A=（a1，a2，…，am）和B=（b1，b2，…，bn）均为顺序表，试设计一个比较A，B大小的算法（请注意：在算法中，不要破坏原表A和B）。
【算法分析】比较顺序表A和B，并用返回值表示结果，值为1，表示A>B；值为-1，表示A<B；值为0，表示A=B。
1）当两个顺序表可以互相比较时，若对应元素不等，则返回值为1或-1；2）当两个顺序表可以互相比较的部分完全相同时，若表长也相同，则返回值为0；否则，哪个较长，哪个就较大
【算法源代码】intListComp(SqListA,SqListB)
{for(i=1;i<=A.length&&i<=B.length;i++)if(A.elem[i]!=B.elem[i])returnA.elem[i]>B.elem[i]?1:-1;if(A.length==B.length)return0;returnA.length>B.length?1:-1;/*当两个顺序表可以互相比较的部分完全相同时，哪个较长，哪个就较大*/}/*ListComp*/3．已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试
设计一个算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。
【算法分析】1）单链表ha的头结点作为连接后的链表的头结点，即hc=ha；
2）查找单链表ha的最后一个结点，由指针p指向，即p->next==NULL；3）将单链表hb的首元结点（非头结点）连接在p之后，即p->next=hb->next；4）回收单链表hb的头结点空间
【算法源代码】voidListConcat(LinkListha,LinkListhb,LinkList*hc)/*把链表hb接在ha后面形成链表hc*/
{*hc=ha;p=ha;/*由指针p指向ha的尾元结点*/p=p->next;p->next=hb->next;free(hb);}/*ListConcat*/4．试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT（L，i，b），并和在带
头结点的动态单链表上实现相同操作的算法进行比较。【算法分析】1）生成新结点存放元素b，由指针new指向；
2）将new插入在单链表的第i个元素的位置上：若i==1，new插在链表首部；否则查找第i-1个结点，由指针p指向，然后将new插在p之后。【算法源代码】voidInsert(LinkList*L,inti,intb)
{LinkListnew;new=(LinkList*)malloc(sizeof(LNode));new->data=b;if(i==1){/*插入在链表头部*/New->next=*L;
·2·数据结构期末习题复习
}else{/*插入在第i个元素的位置*/p=*L;while(--i>1)p=p->next;new->next=p->next;p->next=new;}}/*Insert*/5．已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删
除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间（注意：mink和maxk是给定的两个参变量。它们的值可以和表中的元素相同，也可以不同）。
【算法分析】1）查找最后一个不大于mink的元素结点，由指针p指向；
2）如果还有比mink更大的元素，查找第一个不小于maxk的元素，由指针q指向；3）p->next=q，即删除表中所有值大于mink且小于maxk的元素。
【算法源代码】voidDelete_Between(LinkList*L,intmink,intmaxk)
{p=*L;while(p->next->data<=mink)p=p->next;/*p是最后一个不大于mink的元素*/if(p->next)/*如果还有比mink更大的元素*/{q=p->next;while(q->data<maxk)q=q->next;/*q是第一个不小于maxk的元素*/p->next=q;}}/*Delete_Between*/6．已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删
除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间。
【算法分析】1）初始化指针p和q，分别指向链表中相邻的两个元素；
2）当p->next不为空时，做如下处理：
①若相邻两元素不相等时，p和q都向后推一步；
②否则，当相邻元素相等时，删除多余元素。
【算法源代码】voidDelete_Equal(LinkList*L)
{p=(*L)->next;q=p->next;/*p和q指向相邻的两个元素*/while(p->next){if(p->data!=q->data)/*若相邻两元素不相等时，p和q都向后推一步*/{p=p->next;q=p->next;}else{while(q->data==p->data)/*当相邻元素相等时删除多余元素*/{r=q;q=q->next;free(r);}p->next=q;p=q;q=p->next;*L=new;
第2部分习题解析·3·
}/*else*/}/*while*/}/*Delete_Equal*/7．试设计一个算法，对带头结点的单链表实现就地逆置。
【算法分析】1）空表或长度为1的表，不做任何处理；
2）表长大于2时，做如下处理：
①首先将整个链表一分为二，即从链表的第一元素结点处断开；
②逐个地把剩余链表的当前元素q插入到链表的头部。
【算法源代码】voidLinkList_reverse(LinkListL)
{if(!L->next||!L->next->next)return;p=L->next;q=p->next;s=q->next;p->next=NULL;/*从链表的第一元素结点处断开*/while(s->next){q->next=p;p=q;q=s;s=s->next;/*把L的元素逐个插入新表表头*/}q->next=p;s->next=q;L->next=s;}/*LinkList_reverse*/8．设线性表A=（a1，a2，…，am）和B=（b1，b2，…，bn），试设计一个按下列规则合并A，B
为线性表C的算法，即使得
C=（a1，b1，…，am，bm，bm+1，…，bn）当m≤n时；
或者
C=（a1，b1，…，an，bn，an+1，…，am）当m＞n时。
线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。【算法分析】1）初始化指针p指向链表A的当前元素，指针q指向链表B的当前元素；
2）当链表A和B均为结束时，做如下处理：
①将B的元素插入
②若A非空，将A的元素插入
③指针p和q同时后移
【算法源代码】voidmerge1(LinkListA,LinkListB,LinkList*C)
{p=A->next;q=B->next;*C=A;while(p&&q){s=p->next;p->next=q;/*将B的元素插入*/if(s){t=q->next;q->next=s;/*若A非空，将A的元素插入*/}p=s;q=t;/*指针p和q同时后移*/}/*while*/}/*merge1*/9．假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请设计一个算法
将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。
【算法分析】按从小到大的顺序依次把A和B的元素插入新表的头部pc处，最后处理A或B的剩余元素。
【算法源代码】voidreverse_merge(LinkListA,LinkListB,LinkList*C)
{LinkListpa,pb,pre;pa=A->next;pb=B->next;/*pa和pb分别指向A和B的当前元素*/
·4·数据结构期末习题复习
pre=NULL;while(pa||pb){if(pa->data<pb->data||!pb)/*将A的元素插入新表*/{pc=pa;q=pa->next;pa->next=pre;pa=q;}else/*将B的元素插入新表*/{pc=pb;q=pb->next;pb->next=pre;pb=q;}pre=pc;}*C=A;A->next=pc;/*构造新表头*/}/*reverse_merge*/10．已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中
出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。
【算法分析】先从B和C中找出共有元素，记为same，再在A中从当前位置开始，凡小于same的元素均保留(存到新的位置)，等于same的就跳过，到大于same时就再找下一个same。
【算法源代码】voidSqList_Intersect_Delete(SqList*A,SqListB,SqListC)
{i=0;j=0;k=0;m=0;/*i指示A中元素原来的位置，m为移动后的位置*/while(i<(*A).length&&j<B.length&&k<C.length){if(B.elem[j]<C.elem[k])j++;elseif(B.elem[j]>C.elem[k])k++;else{same=B.elem[j];/*找到了相同元素same*/while(B.elem[j]==same)j++;while(C.elem[k]==same)k++;/*j和k后移到新的元素*/while(i<(*A).length&&(*A).elem[i]<same)(*A).elem[m++]=(*A).elem[i++];/*需保留的元素移动到新位置*/while(i<(*A).length&&(*A).elem[i]==same)i++;/*跳过相同的元素*/}}/*while*/while(i<(*A).length)(*A).elem[m++]=(*A).elem[i++];/*A的剩余元素重新存储*/(*A).length=m;}/*SqList_Intersect_Delete*/11．设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入
的原则把该链表整理成数据递增的有序单链表的算法.【算法分析】本题明确指出单链表带头结点，其结点数据是正整数且不相同，要求利用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开始，将各结点依次插入到有序链表中。
【算法源代码】voidInsertSort(LinkListla)
{if(la->next!=NULL)/*链表不为空表*/{p=la->next->next;/*p指向第一结点的后继*/la->next->next=NULL;/*直接插入原则认为第一元素有序，然后从第二元素起依次插入*/while(p!=NULL){r=p->next;/*暂存p的后继*/q=la;while(q->next!=NULL&&q->next->data<p->data)q=q->next;/*查找插入位置*/p->next=q->next;/*将p结点链入链表*/q->next=p;p=r;
第2部分习题解析·5·
}12．设有一个双向循环链表，每个结点中除有prior，data和next三个域外，还增设了一个访问频
度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE（L，X）的操作后，被访问的结点（元素值等于X的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的算法。【算法分析】
1）在双向链表中查找数据值为x的结点，由指针p指向，若找不到，直接返回，否则执行第2步；
2）修改x结点的访问频度freq，并将结点从链表上摘下；3）顺结点的前驱链查找该结点的位置，即找到一个结点的访问频度大于x结点的访问频度，由指针q指向；若q和p不是相邻结点，调整位置，把p插在q之后。【算法源代码】DuLNode*Locate_DuList(DuLinkList*L,intx){p=(*L)->next;while(p.data!=x&&p!=(*L))p=p->next;if(p==(*L))returnNULL;/*没找到x结点*/p->freq++;p->pre->next=p->next;p->next->pre=p->pre;/*将x结点从链表上摘下*/q=p->pre;while(q->freq<=p->freq&&p!=(*L))q=q->pre;/*查找插入位置*/if(q!=p->pre)/*将x结点插入*/{q->next->pre=p;p->next=q->next;q->next=p;p->pre=q;/*调整位置*/}returnp;}/*Locate_DuList*/13．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。
【算法分析】留下三个链表中公共数据，首先查找两表A和B中公共数据，再去C中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O（m+n+p），在查找每个链表时，指针不能回溯。
【算法源代码】LinkListCommon(LinkListA,LinkListB,LinkListC)
{pa=A->next;pb=B->next;pc=C->next;/*pa，pb和pc是工作指针*/pre=A;while(pa&&pb&&pc)/*当三表均不空时，查找共同元素*/{while(pa&&pb)if(pa->data<pb->data)/*处理pa结点，后移指针*/{u=pa;pa=pa->next;free(u);}elseif(pa->data>pb->data)pb=pb->next;elseif(pa&&pb)/*处理A和B表元素值相等的结点*/{while(pc&&pc->data<pa->data)pc=pc->next;if(pc){if(pc->data>pa->data)/*处理pa结点，后移指针*/{u=pa;pa=pa->next;free(u);}else{if(pre==A)/*结果表中第一个结点*/{pre->next=pa;pre=pa;pa=pa->next}elseif(pre->data==pa->data)/*重复结点不链入A表*/{u=pa;pa=pa->next;free(u);}
·6·数据结构期末习题复习
}14．设head为一单链表的头指针，单链表的每个结点由一个整数域data和指针域next组成，整数
在单链表中是无序的。编一函数，将head链中结点分成一个奇数链和一个偶数链，分别由p，q指向，每个链中的数据按由小到大排列。程序中不得使用malloc申请空间。【算法分析】本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用malloc申请空间，这就是要利用原链表空间，随着原链表的分解，新建链表随之排序。
【算法源代码】discreat(LinkListp,LinkListq,LinkListhead)
{p=NULL;q=NULL;/*p和q链表初始化为空表*/s=head;while(s!=NULL){r=s->next;/*暂存s的后继*/if(s->data%2==0)/*处理偶数*/if(p==NULL){p=s;p->next=NULL;}/*第一个偶数结点*/else{pre=p;if(pre->data>s->data){s->next=pre;p=s;}/*插入当前最小值结点*/else{while(pre->next!=NULL)if(pre->next->data<s->data)pre=pre->next;/*查找插入位置*/s->next=pre->next;/*链入结点*/pre->next=s;}}else/*处理奇数链if(q==NULL){q=s;q->next=NULL;}/*第一奇数结点*/else{pre=q;if(pre->data>s->data){s->next=pre;q=s;}/*修改头指针*/else{while(pre->next!=NULL)/*查找插入位置*/if(pre->next->data<s->data)pre=pre->next;s->next=pre->next;/*链入结点*/pre->next=s;}}/*结束奇数链结点*/s=r;/*s指向新的待排序结点*/}}}elseif(pa==NULL)pre->next=NULL;/*若A表已结束，置A表表尾*/else/*处理原A表未到尾而B或C到尾的情况*/{pre->next=NULL;/*置A表表尾标记*/while(pa!=NULL)/*删除原A表剩余元素。*/{u=pa;pa=pa->next;free(u);}}{pre->next=pa;pre=pa;pa=pa->next;}/*将新结点链入A表*/pb=pb->next;pc=pc->next;/*链表的工作指针后移*/}else
第2部分习题解析·7·
3.5程序设计题1．设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E);(注：算法中可调用栈操作的基本算法。)
【算法分析】判断表达式中括号是否匹配，可通过栈，简单说是左括号时进栈，右括号时退栈。退栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可消去。如此下去，输入表达式结束时，栈为空则正确，否则括号不匹配。
【算法源代码】intEXYX(charE[]){
/*E[]存放字符串表达式，以‘#’结束*/chars[30];/*s是一维数组，容量足够大，用作存放括号的栈*/inttop=0,i;/*top用作栈顶指针*/s[top]='#';/*‘#’先入栈，用于和表达式结束符号‘#’匹配*/i=0;/*字符数组E的工作指针*/while(E[i]!='#')/*逐字符处理字符表达式的数组*/switch(E[i]){case'(':s[++top]='(';i++;break;case')':if(s[top]=='('){top--;i++;break;}else{printf("括号不配对");exit(0);}case'#':if(s[top]=='#'){printf("括号配对\n");return(1);}else{printf("括号不配对\n");return(0);}/*括号不配对*/default:i++;/*读入其它字符，不作处理*/}}/*算法结束*/2．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写
出相应的入队列和出队列算法。
【算法分析】
根据队列的先进先出的性质，队列的入队操作在队尾进行，出队操作在队头进行。而题目所采用的数据结构是只设一个尾指针的循环链表。我们可以根据循环链表的特点找到头指针。
【算法源代码1】
voidEnQueue(LinkListrear,ElemTypex)/*rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾*/{s=(LinkList)malloc(sizeof(LNode));/*申请结点空间*/s->data=x;s->next=rear->next;/*将s结点链入队尾*/rear->next=s;rear=s;/*rear指向新队尾*/}
【算法源代码2】
voidDeQueue(LinkListrear)/*rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元
素；否则给出出错信息*/
{if(rear->next==rear){printf("队空\n");exit(0);}s=rear->next->next;/*s指向队头元素*/rear->next->next=s->next;/*队头元素出队*/printf("出队元素是:%d",s->data);if(s==rear)rear=rear->next;/*空队列*/free(s);}3．设整数序列a1，a2，…，an，给出求解最大值的递归程序。
【算法分析】根据题意，本题的函数定义为：
a[1]n=1
·8·数据结构期末习题复习
maxvalue(a,n)=a[n]a[n]>maxvalue(a,n-1)maxvalue(a,n-1)a[n]<maxvalue(a,n-1)
【算法源代码】
intMaxValue(inta[],intn)/*设整数序列存于数组a中，共有n个，本算法求解其最大值*/{intmax;if(n==1)max=a[1];elseif(a[n]>MaxValue(a,n-1))max=a[n];elsemax=MaxValue(a,n-1);return(max);}4．试将下列递归函数改写为非递归函数。voidtest(int*sum){intx;scanf("%d",&x);if(x==0)*sum=0;else{test(&sum);(*sum)+=x;}printf("%5d",*sum);}
【算法分析】该函数是以读入数据的顺序为相反顺序进行累加问题，可将读入数据放入栈中，等输入结束时，将栈中数据退出进行累加。累加的初值为0。【算法源代码】inttest()
{intx,sum=0,top=0,s[30];scanf("%d",&x);while(x!=0){s[++top]=a;scanf("%d",&x);}printf("%5d",sum);while(top){sum+=s[top--];printf("%5d",sum);}}5．编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。
【算法分析】利用两个临时栈s1和s2。先将s栈中的内容移到s1栈中，再将s1栈中的内容移到s2栈中，最后将s2栈中的内容移到s栈中，即可实现。【算法源代码】reverse(SqStack*s){SqStack*s1,*s2;/*s,s1,s2均为栈类型ElemTypex;/*栈中元素的类型，用于存储从栈中取出元素的临时变量*/initstack(s1);/*栈的初始化*/initstack(s2);while(!stackempty(s))/*如果栈不空，将s栈中的内容移到s1栈中*/{pop(s,x);/*取栈顶元素放入变量x中*/push(s1,x);/*将变量x入栈*/}while(!stackempty(s1))/*如果栈不空，将s1栈中的内容移到s2栈中*/{pop(s1,x);push(s2,x);}while(!stackempty(s2))/*如果栈不空，将s2栈中的内容移到s栈中*/{pop(s2,x);push(s,x);}}
第2部分习题解析·9·
6．假设循环队列中只设rear和length来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。
【算法分析】该题的关键问题是如何确定头指针，根据为指针rear和元素个数length很容易确定头指针。front=(rear-length+MAXSIZE)%MAXSIZE
【算法源代码】#defineMAXQSIZE100//最大队列长度
typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];//队列存储空间intrear;//尾指针，若队列不空，指向队列尾元素intlength;//队列内含元素的个数}CyQueue;intFullQueue(CyQueue*Q){/*判队满,队中元素个数等于空间大小*/returnQ->length==Maxsize;}voidEnQueue(CyQueue*Q,ElemTypex){/*入队if(FullQueue(Q)){printf("队已满，无法入队");return;}*/Q->Data[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE/*在循环意义上的加1*/Q->length++;}ElemTypeDeQueue(CyQueue*Q){/*出队*/intfront;/*设一个临时队头指针*/if(Q->length==0)Error("队已空，无元素可出队");front=(Q->rear+MAXSIZE-Q->length)%MAXSIZE;Q->length--;returnQ->Data[front];}7．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为
此双向栈设计初始化InitStack(S)、入栈Push(S,i,x)和出栈Pop(S,i)等算法，其中i为0或1，用以表示栈号。
【算法分析双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。
【算法源代码】voidInitStack(DuStack*S)/*初始化双向栈*/
{S->top[0]=-1;S->top[1]=STACKSIZE;}intEmptyStack(DuStack*S,inti)/*判栈空(栈号i)*/{return(i==0&&S->top[0]==-1||i==1&&S->top[1]==STACKSIZE);}intFullStack(DuStack*S)/*判栈满,满时肯定两头相遇*/{return(S->top[0]==S-top1-1);}voidPush(DuStack*S,inti,ElemTypex)/*进栈(栈号i)*/
·10·数据结构期末习题复习
{if(FullStack(S))Error("Stackoverflow");/*上溢、退出运行*/if(i==0)S->Data[++S->top0]=x;/*栈0入栈*/if(i==1)S->Data[--S->top[1]]=x;/*栈1入栈*/}ElemTypePop(DuStack*S,inti)/*出栈(栈号i)*/{if(EmptyStack(S,i))Error("Stackunderflow");/*下溢退出*/if(i==0)return(S->Data[S->top0--]);/*返回栈顶元素，指针值减1*/if(i==1)return(S->Data[S->top[1]++]);/*该栈是以另一端为底的，所以指针加1*/}8．回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。设计
一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)
【算法源代码】voidsympthy(LinkListhead,stack*s)/*判断长为n的字符串是否中心对称*/
{inti=1;LinkListp=head->next;while(i<=n/2)/*前一半字符进栈*/{push(s,p->data);p=p->next;}if(n%2!==0)p=p->next;/*奇数个结点时跳过中心结点*/while(p&&p->data==pop(s))p=p->next;if(p==NULL)printf("链表中心对称");elseprintf("链表不是中心对称");}/*算法结束*/9．用标志位方式设计出在循环队列中进行插入和删除运算的算法。
【算法分析】
可引入标志位flag，且规定当flag=0时表示队列空，当flag=1时表示队列非空。同时设front，rear和MAXSIZE分别为队头指针，队尾指针和队列的长度。其中，队头指针指向队头元素所在的实际存储单元的前一个位置，队尾指针指向队尾元素所在的位置。从而可得队满的条件是：(rear==front)&&(flag==1)
【算法源代码】intflag;/*设置全局变量flag作为标志位*/
enqueue(SqQueue*sq,ElemTypex){/*将x插入循环队列sq中，sq具有队头和队尾指针*/if((flag==1)&&(sq->rear==sq->front))/*判断队满*/printf("queueisfull!\n");else{sq->rear=(sq->rear+1)%MAXSIZE;sq->data[sq->rear]=x;}if(flag==0)flag=1;}ElemTypedequeue(SqQueue*sq)/*删除队列sq的队头元素，并返回该元素*/{ElemTypex;if(flag==0)printf("queueisempty!\n");/*判断队空*/else{sq->front=(sq->front+1)%MAXSIZE;x=sq->data[sq->front];
第2部分习题解析·11·
}if(sq->front==sq->rear)flag=0;returnx;}
第4章串
4.5算法设计题1．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。
【算法分析】判断字符串t是否是字符串s的子串，称为串的模式匹配，其基本思想是对串s和t各设一个指针i和j，i的值域是0..m-n，j的值域是0..n-1。初始值i和j均为0。模式匹配从s0和t0开始，若s0==t0，则i和j指针增加1，若在某个位置si!=tj，则主串指针i回溯到i=i-j+1，j仍从0开始，进行下一轮的比较，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否则，当i>m-n则为匹配失败。【算法源代码】
intindex(chars[],chart[],intm,intn){inti=0,j=0;while(i<=m-n&&j<=n-1)if(s[i]==t[j]){i++;j++;}/*对应字符相等，指针后移*/else{i=i-j+1;j=0;}/*对应字符不相等，i回溯，j仍为0*/if(i<=m-n&&j==n){printf("t在s串中位置是%d",i-n+1);return(i-n+1);}/*匹配成功*/elsereturn(0);/*匹配失败*/}2．函数voidinsert(char*s,char*t,intpos)将字符串t插入到字符串s中，插入位置为pos。请用c语言
实现该函数。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）
【算法分析】本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。
对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。
【算法源代码】voidinsert(char*s,char*t,intpos)/*将字符串t插入字符串s的第pos个位置*/
{inti=1,x=0,j;char*p=s,*q=t;/*p，q分别为字符串s和t的工作指针*/if(pos<1){printf("pos参数位置非法\n");exit(0);}while(*p!='\0'&&i<pos){p++;i++;}/*查pos位置*/if(*p=='/0'){printf("%d位置大于字符串s的长度",pos);exit(0);}else/*查找字符串的尾*/while(*p!='/0'){p++;i++;}/*查到尾时，i为字符'\0'的下标，p也指向'\0'*/while(*q!='\0'){q++;x++;}/*查找字符串t的长度x，循环结束时q指向'\0'*/for(j=i;j>=pos;j--){*(p+x)=*p;p--;}/*串s的pos后的子串右移，空出串t的位置*/q--;/*指针q回退到串t的最后一个字符for(j=1;j<=x;j++)*p--=*q--;/*将t串插入到s的pos位置上*/}
·12·数据结构期末习题复习
3．设计一个算法，统计在输入字符串中各个不同字符出现的频度。（字符串中的合法字符为'A'-'Z'这26个字母和'0'-'9'这10个数字）。
【算法分析】由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII代码值减去数字字符'0'的ASCII代码值，得出其数值(0..9)，字母的ASCII代码值减去字符'A'的ASCII代码值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字符串结束。
【算法源代码】voidCount()
/*统计输入字符串中数字字符和字母字符的个数*/{inti,num[36];charch;for(i=0;i<36;i++)num[i]=0;/*初始化*/while((ch=getchar())!='#')/*‘#’表示输入字符串结束*/if(('0'<=ch)&&(ch<='9')){i=ch-'0';num[i]++;}/*数字字符*/elseif(('A'<=ch)&&(ch<='Z')){i=ch-'A'+10;num[i]++;}/*字母字符*/for(i=0;i<10;i++)/*输出数字字符的个数*/printf("数字％d的个数＝％d\n",i,num[i]);for(i=10;i<36;i++)/*求出字母字符的个数*/printf("字母字符％c的个数＝％d\n",i+55,num[i]);}/*算法结束*/4．若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中
出现的字符。
【算法分析】查找过程是这样的，取S中的一个字符(结点)，然后和T中所有的字符一一比较，直到比完仍没有相同的字符时，查找过程结束，否则再取S中下一个字符，重新进行上述过程。
【算法源代码】charSearchNo(LinkStringS,LinkStringT)/*查找不在T中出现的字符*/
{LinkStringp,q;p=S;q=T;while(p){/*取S中结点字符*/while(q&&p->data!=q->data)/*进行字符比较*/q->next;if(q==NULL)returnp->data;/*找到并返回字符值*/q=T;/*指针恢复串T的开始结点*/p=p->next;}printf("there'snosuchcharacter.");returnNULL;}
5．如果一个字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。试设计一个算法，输入字符串s，以“！”作为结束标志。如果串s中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。
【算法分析】用字符数组s接受用户输入的字符串。设head指向当前发现的最长等值子串的串头，max记录此子串的长度。对s进行扫描，若发现新的等值子串，用count变量统计其长度，若他的长度大于原有的max，则对head和max进行更新。重复上述过程直到s末尾。【算法源代码】
#defineMAXSIZE100{inti,j,k,head,max,count;chars[MAXSIZE];
第2部分习题解析·13·
printf("输入字符串：");k=0;scanf("%c",&s[k]);while(s[k]!='!')scanf("%d",&s[++k]);i=0,j=1,head=0,max=1;for(;s[i]!='!'&&s[j]!='!';i=j,j++){count=1;while(s[i]==s[j]){j++;count++;}if(count>max){head=i;max=count;}}if(max>1){printf("最大等值子串：");for(k=head;k<(head+max);k++)printf("%c",s[k]);}elseprintf("无等值子串");printf("\n");}6．采用顺序存储结构存储的串，编写一个程序，将两个字符串进行比较，若s>t时返回1，s=t时
返回0，s<t时返回-1。不能用strcmp库函数。
【算法分析】从两个字符串的第一个字符开始逐个进行比较（按字符的ASCII码大小比较），直到出现不同的字符或遇到'\0'为止。如果全部字符都相同，就认为两个字符串相等，返回0。若出现了不相同的字符，则以第一个不相同的字符的比较结果为准。若前者字符大于后者字符，则返回1，否则返回-1。【算法源代码】
intcomp(SString*s1,SString*s2){inti=0,minlen;minlen=s1->len>s2->len?s1->len:s2->len;/*minlen存放s1与s2中的较短的字符串的长度*/while(i<=minlen){if(s1->data[i]==s2->data[i])/*如果s1与s2的当前字符相等，则比较下一个*/i++;elseif(s1->data[i]<s2->data[i])/*s1的当前值小于s2的当前值，返回-1*/retrun-1;elsereturn1;/*s1的当前值大于s2的当前值，返回1*/}if(s1->len==s2->len)return0;/*s1与s2所有字符均相等，且长度相等，则返回0*/}7．输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计其中的单词数。
【算法分析】单词的数目可以有空格出现的次数来决定（连续的多个空格作为出现一次空格；不包含一行开头的空格）。如果当前字符为非空格，而他前面的字符是空格，则表示新的单词出现，此时让num（单词数）累加1。如果当前字符为非空格，而他前面的字符也是非空格，则表示此字符仍然是
·14·数据结构期末习题复习
原单词的继续，num不应累加。前面一个单词是否为空格，可以设置一个变量word，若word=0，则表示前一个字符时空格，如果word=1，表示前一个字符为非空格。【算法源代码】
intcount(s)chars[80];{charc;inti,num=0,word=0;for(i=0;s[i]!='\0';i++){if(s[i]=='')word=0;elseif(word==0){word=1;num++;}}returnnum;}8．一个仅由字母组成的字符串s，长度为n，其结构为单链表，每个结点的data字段只存放一个字
母。试设计一个函数，去掉字符串中所有的X字母，并将串中的一个最小字母排列到串尾。
【算法分析】从链表的表头开始查找每一个结点，如果该结点的数据值为X，则删除该结点。同时在查找的过程中，顺便比较该结点与前驱结点的大小，如果该结点的值闭其前驱结点的值大，则顺便交换，直到整个链表结束。【算法源代码】
search(LinkLists,charx)/*在带头结点的单链表s中查找数据值为x的结点*/{LinkListp,q,r;chartemp;p=s->next;q=s;/*p表示当前操作的结点，q表示p的前驱结点*/while(p!=NULL){if(p->data==x){r=p;q-next=p->next;p=p->next;free(r);}/*找到释放结点*/else{q=p;p=p->next;}if(q!=s&&p->data>q->data)/*将结点值最小的结点移到表尾*/{temp=p->data;p->data=q->data;q->data=temp;}}}9．设计一个算法，将字符串s的全部字符复制到字符串t中，不能利用strcpy函数。
【算法分析】要实现两个字符串的复制，实质为两个字符数组之间的复制，在复制时，一个字符一个字符的复制，直到遇到'\0'，'\0'一同复制过去，'\0'之后的字符不复制。【算法源代码】
copy(chars[],chart[]){inti;for(i=0;s[i]!='\0';i++)t[i]=s[i];t[i]=s[i];
www.99jianzhu.com/包含内容：建筑图纸、PDF/word/ppt 流程，表格，案例，最新,免费下载,施工方案、工程书籍、建筑论文、合同表格、标准规范、CAD图纸等内容。