数据结构作业系统

本文格式为Word版，下载可任意编辑——数据结构作业系统◆2.11②设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。

要求实现以下函数：

voidInsertOrderList(SqListintlength;intlistsize;}SqList;

voidInsertOrderList(SqList

while(L.elem[i]i;j--){

L.elem[j]=L.elem[j-1];}

L.elem[i]=x;L.length+=1;}

◆2.12③设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大

的共同前缀为(x,y,y,z)，在两表中除去最大共同前缀后的子表分别为A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表，

则A=B；若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则AB。试写一个比较A和B大小的算法。（注意：在算法中，不要破坏原表A和B，也不一定先求得A'和B'才进行比较）。

要求实现以下函数：

charCompare(SqListA,SqListB);/*比较顺序表A和B,*//*返回'',若A>B*/

顺序表类型定义如下：typedefstruct{

ElemType*elem;intlength;intlistsize;}SqList;

charCompare(SqListA,SqListB)//比较顺序表A和B,//返回'',若A>B{

inti=0;

while(A.elem[i]==B.elem[i]

elseif(A.elem[i]B.elem[i]||i==B.length)return'>';}

2.13②试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。

实现以下函数：

LinkListLocate(LinkListL,ElemTypex);

//If'x'inthelinkedlistwhoseheadnodeispointed//by'L',thenreturnpointerpointingnode'x',//otherwisereturn'NULL'

单链表类型定义如下：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;

LinkListLocate(LinkListinti=0;p=L->next;

while(p->data!=x

p=p->next;}returnp;}

2.14②试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。

实现以下函数：

intLength(LinkListL);

//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'

单链表类型定义如下：typedefstructLNode{

ElemTypedata;structLNode*next;}LNode,*LinkList;intLength(LinkListL)

//Returnthelengthofthelinkedlist//whoseheadnodeispointedby'L'{

LinkListp;inti=0;p=L->next;

while(p!=NULL){

i++;

p=p->next;}

returni;}

2.17②试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现一致操作的算法进行比较。

实现以下函数：

voidInsert(LinkList

单链表类型定义如下：typedefstructLNode{

ElemTypedata;structLNode*next;}LNode,*LinkList;

voidInsert(LinkListintj=2;p=L;

while(jnext;}

if(i!=0q->data=b;

q->next=p->next;p->next=q;}

if(i==1){

q=(LinkList)malloc(sizeof(LNode));q->data=b;q->next=p;L=q;}}

2.18②同2.17题要求。试写一算法，实现线性表操作DELETE(L,i)。

实现以下函数：

voidDelete(LinkList

单链表类型定义如下：typedefstructLNode{

ElemTypedata;structLNode*next;}LNode,*LinkList;

voidDelete(LinkListintj=2;p=L;

while(jnext;}

if(i!=0

p->next=q->next;free(q);}

if(i==1){q=L;

L=L->next;free(q);}}

2.20②同2.19题条件，试写一高效的算法，删除表中所有值一致的多余元素(使得操作后的线性表中所有元素的值均不一致)同时释放被删结点空间，并分析你的算法的时间繁杂度。

实现以下函数：

voidPurge(LinkList

单链表类型定义如下：typedefstructLNode{

ElemTypedata;structLNode*next;}LNode,*LinkList;voidPurge(LinkListinti=0;p=L;

while(p!=NULL

p->next=q->next;free(q);}

else

p=p->next;}}

◆2.21③试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。

实现以下函数：

voidInverse(SqList

顺序表类型定义如下：typedefstruct{

ElemType*elem;intlength;intlistsize;}SqList;

voidInverse(SqListi=L.length/2;for(j=0;jnext;

while(p->next!=NULL){

k=q;

q=p->next;

p->next=q->next;q->next=k;}

L->next=q;}

2.23③设线性表A=(a1,...,am),B=(b1,...,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均未显式存储。

实现以下函数：

voidMerge(LinkListha,LinkListhb,LinkListstructLNode*next;}LNode,*LinkList;

voidMerge(LinkListha,LinkListhb,LinkListp=ha->next;q=hb->next;

if(p==NULL)hc=hb;elseif(q==NULL)hc=ha;else{

while(p->next!=NULLr=q->next;p->next=q;p=k;

q->next=p;q=r;}

if(p->next!=NULL)q->next=p->next;p->next=q;hc=ha;}}

◆2.24④假设有两个按元素值递增有序排列的线性表

A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值一致的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。

实现以下函数：

voidUnion(LinkList

/*依题意，利用la和lb原表的结点空间构造lc表*/

单链表类型定义如下：typedefstructLNode{

ElemTypedata;structLNode*next;}LNode,*LinkList;

voidUnion(LinkListLinkListpb=lb->next;

LinkListpre=NULL;LinkListq,pc;while(pa||pb){

if((pa->datadata

q=pa->next;pa->next=pre;pa=q;}else

{pc=pb;

q=pb->next;pb->next=pre;pb=q;}

pre=pc;

printf(\}lc=la;

la->next=pc;//构造新表头

/*LinkListpa=la->next;LinkListpb=lb->next;LinkListpc=la;lc=la;

while(papc=pa;

pa=pa->next;}else{

pc->next=pb;pc=pb;

pb=pb->next;}}

pc->next=pa?pa:pb;free(lb);

//将c实现就地逆置LinkListp,q;p=lc->next;while(p->next){

q=p->next;

p->next=p->next->next;q->next=lc->next;

'lc->next=q;}*/}

2.31②假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

实现以下函数：

ElemTypeDeleteNode(LinkLists);

/*删除指针s所指结点的前驱结点，并返回被删结点的元素值*/

单链表类型定义如下：typedefstructLNode{

ElemTypedata;structLNode*next;}LNode,*LinkList;

ElemTypeDeleteNode(LinkLists)

/*删除指针s所指结点的前驱结点，并返回被删结点的元素值*/{

LinkListp;p=s->next;

while(p->next->next!=s)p=p->next;

ElemTypee=p->next->data;p->next=s;returne;}

2.32②已知有一个单向循环链表，其每个结点中含三个域：prev、data和next，其中data为数据域，next为指向后继结点的指针域，prev也为指针域，但它的值为空(NULL)，试编写算法将此单向循环链表改为双向循环链表，即使prev成为指向前驱结点的指针域。

实现以下函数：

voidPerfectBiLink(BiLinkList

双向循环链表类型定义如下：typedefstructBiNode{

ElemTypedata;

intfreq;//2.38题用structBiNode*prev,*next;}BiNode,*BiLinkList;

voidPerfectBiLink(BiLinkListk=p=q=CL;

while(p->next!=q){

p=p->next;p->prev=k;k=p;}

q->prev=p;}

◆2.33③已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。

实现以下函数：

voidSplit(LinkList

单链表类型定义如下：typedefstructLNode{

ElemTypedata;structLNode*next;}LNode,*LinkList;

voidSplit(LinkLists=L->next;

A=(LinkList)malloc(sizeof(LNode));p=A;B=(LinkList)malloc(sizeof(LNode));q=B;

C=(LinkList)malloc(sizeof(LNode));r=C;//建立头结点while(s){

if((s->data>='a'p=s;}

elseif(s->data>='0'q=s;}else{

r->next=s;r=s;}

s=s->next;}//while

p->next=A;q->next=B;r->next=C;//完成循环链表}

2.37④设以带头结点的双向循环链表表示的线性表L=(a1,a2,...,an)。试写一时间繁杂度为O(n)的算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。

实现以下函数：

voidReverseEven(BiLinkList

双向循环链表类型定义如下：typedefstructBiNode{ElemTypedata;

intfreq;//2.38题用structBiNode*prev,*next;}BiNode,*BiLinkList;

voidReverseEven(BiLinkListp=L->next;

while(p->next!=Lp=p->next;

}//此时p指向最终一个奇数结点if(p->next==L)p->next=L->prev->prev;elsep->next=L->prev;

p=p->next;//此时p指向最终一个偶数结点while(p->prev->prev!=L)

{

p->next=p->prev->prev;p=p->next;}

if(p!=L)

p->next=L;//按题目要求调整了next链的结构,此时pre链仍为原状for(p=L;p->next!=L;p=p->next)p->next->prev=p;L->prev=p;//调整pre链的结构,同2.32方法}

◆2.39③试对稀疏多项式Pn(x)采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为给定值），并分析你的算法的时间繁杂度。

实现以下函数：

floatEvaluate(SqPolypn,floatx);

/*pn.data[i].coef存放ai，*//*pn.data[i].exp存放ei(i=1,2,...,m)*/

/*本算法计算并返回多项式的值。不判别溢出。*//*入口时要求0≤e1next;if(t->exp==0){free(t);

pa->next=pa->next->next;}

p=pa->next;

while(p!=pa){p->coef*=p->exp;p->exp--;

//if(p->next->exp==0)p->next=p->next->next;p=p->next;}}

◆3.17③试写一个算法，识别依次读入的一个以@为终止符的字符序列是否为形如'序列1

/*若str是属该模式的字符序列，*//*则返回TRUE，否则返回FALSE*/

Stack是一个已实现的栈。可使用的相关类型和函数：

typedefcharSElemType;//栈Stack的元素类型StatusInitStack(Stack

StatusPush(StackStatusPop(StackStatusStackEmpty(Stacks);

StatusGetTop(Stacks,SElemType

Statusmatch(char*str)

/*若str是属该模式的字符序列，*//*则返回TRUE，否则返回FALSE*/{

Stacks;

SElemTypee;InitStack(s);while(*str!='str++;}str++;

while(*str!='@'){

if(StackEmpty(s))returnFALSE;Pop(s,e);if(*str!=e)

returnFALSE;

}

3.24③试编写如下定义的递归函数的递归算法:g(m,n)=0当m=0,n>=0g(m,n)=g(m-1,2n)+n当m>0,n>=0并根据算法画出求g(5,2)时栈的变化过程。

实现以下函数：intg(intm,intn);

/*ifm0

实现以下函数：intF(intn);

/*ifnnext=rear;returnOK;}

StatusEnCLQueue(CLQueue

p=(LinkList)malloc(sizeof(LNode));if(p==NULL)exit(0);else{

p->data=x;

p->next=rear->next;rear->next=p;rear=p;}

returnOK;}

StatusDeCLQueue(CLQueue

if(rear==rear->next)returnERROR;p=rear->next->next;x=p->data;

rear->next->next=p->next;

free(p);returnOK;}

3.29③假使希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针值一致时的队列状态是\空\还是\满\。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度探讨设标志和不设标志这两种方法的使用范围（譬如，当循环队列容量较小而队列中每个元素占的空间较多时，那一种方法较好？）。

实现以下函数：

StatusEnCQueue(CTagQueueStatusDeCQueue(CTagQueue

此题的循环队列CTagQueue的类型定义如下：typedefcharQElemType;typedefstruct{

QElemTypeelem[MAXQSIZE];inttag;intfront;intrear;}CTagQueue;

StatusEnCQueue(CTagQueueelse{

Q.elem[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXQSIZE;}

returnOK;}

StatusDeCQueue(CTagQueueelse{

x=Q.elem[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;}

returnOK;}

◆3.30②假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。

实现以下函数：

StatusEnCQueue(CLenQueueStatusDeCQueue(CLenQueue

此题的循环队列CLenQueue的类型定义如下：typedefcharQElemType;typedefstruct{

QElemTypeelem[MAXQSIZE];intlength;intrear;}CLenQueue;

StatusEnCQueue(CLenQueueelse{

Q.rear=(Q.rear+1)%MAXQSIZE;Q.elem[Q.rear]=x;Q.length+=1;}

returnOK;}

StatusDeCQueue(CLenQueueelse{

x=Q.elem[(MAXQSIZE-Q.length+Q.rear+1)%MAXQSIZE];

Q.length--;}

returnOK;}

◆3.31③假设称正读和反读都一致的字符序列为\回文\，例如，'abba'和'abcba'是回文，'abcde'和'ababab'则不是回文。试写一个算法判别读入的一个以'@'为终止符的字符序列是否是\回文\。

实现以下函数：

StatusPalindrome(char*word);

/*利用栈和队列判定字符序列word是否是回文*/

可使用栈Stack和队列Queue及其以下操作：StatusInitStack(StackStatusPush(StackStatusPop(StackStatusStackEmpty(StackS);

StatusInitQueue(Queue

StatusEnQueue(QueueStatusDeQueue(QueueS