(完整版)数据结构作业系统_第二章答案

◆2.11② 设顺序表L中的数据元素递增有序。

试写一算法，将x插入到L的适当位置上，并保

持该表的有序性。

要求实现下列函数：

void InsertOrderList(SqList &L, ElemType x)

/* 在有序的顺序表 L 中保序插入数据元素 x */

顺序表类型定义如下：

typedef struct {

ElemType *elem;

int length;

int listsize;

} SqList;

void InsertOrderList(SqList &L, ElemType x)

// 在有序的顺序表 L 中保序插入数据元素 x

{

int i=0,j;

while([i]

i++;

for(j=;j>i;j--)

{

[j]=[j-1];

}

[i]=x;

+=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'才进行比较）。

要求实现下列函数：

char Compare(SqList A, SqList B);

/* 比较顺序表A和B, */

/* 返回'<', 若A

/* '=', 若A=B; */

/* '>', 若A>B */

顺序表类型定义如下：

typedef struct {

ElemType *elem;

int length;

int listsize;

} SqList;

char Compare(SqList A, SqList B)

// 比较顺序表A和B,

// 返回'<', 若A

// '=', 若A=B;

// '>', 若A>B

{

int i=0;

while([i]==[i]&&i<&&i<)

i++;

if(i==&&i==)

return '=';

else if([i]<[i]||i==)

return '<';

else if([i]>[i]||i==)

return '>';

}

2.13② 试写一算法在带头结点的单链表结构上实现线性表操作

Locate(L,x)。

实现下列函数：

LinkList Locate(LinkList L, ElemType x);

// If 'x' in the linked list whose head node is pointed

// by 'L', then return pointer pointing node 'x',

// otherwise return 'NULL'

单链表类型定义如下：

typedef struct LNode {

ElemType data;

struct LNode *next;

} LNode, *LinkList;

LinkList Locate(LinkList &L, ElemType x)

// If 'x' in the linked list whose head node is pointed

// by 'L', then return pointer ha pointing node 'x',

// otherwise return 'NULL'

{

LinkList p;

int i=0;

p=L->next;

while(p->data!=x&&p!=NULL)

{

i++;

p=p->next;

}

return p;

}

2.14② 试写一算法在带头结点的单链表结构上实现线性表

操作Length(L)。

实现下列函数：

int Length(LinkList L);

// Return the length of the linked list

// whose head node is pointed by 'L'

单链表类型定义如下：

typedef struct LNode{

ElemType data;

struct LNode *next;

} LNode, *LinkList;

int Length(LinkList L)

// Return the length of the linked list

// whose head node is pointed by 'L'

{

LinkList p;

int i=0;

p=L->next;

while(p!=NULL)

{

i++;

p=p->next;

}

return i;

}

2.17② 试写一算法，在无头结点的动态单链表上实现

线性表操作INSERT(L,i,b)，并和在带头结点的动态单

链表上实现相同操作的算法进行比较。

实现下列函数：

void Insert(LinkList &L, int i, ElemType b);

单链表类型定义如下：

typedef struct LNode{

ElemType data;

struct LNode *next;

} LNode, *LinkList;

void Insert(LinkList &L, int i, ElemType b)

{

LinkList p,q;

int j=2;

p=L;

while(j

{

j++;

p=p->next;

}

if(i!=0&&i!=1)

{

q=(LinkList)malloc(sizeof(LNode));

q->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)。

实现下列函数：

void Delete(LinkList &L, int i);

单链表类型定义如下：

typedef struct LNode{

ElemType data;

struct LNode *next;

} LNode, *LinkList;

void Delete(LinkList &L, int i)

{

LinkList p,q;

int j=2;

p=L;

while(j

{

j++;

p=p->next;

}

if(i!=0&&i!=1)

{

q=p->next;

p->next=q->next;

free(q);

}

if(i==1)

{

q=L;

L=L->next;

free(q);

}

}

2.20② 同2.19题条件，试写一高效的算法，删除表中所

有值相同的多余元素 (使得操作后的线性表中所有元素的

值均不相同) 同时释放被删结点空间，并分析你的算法的

时间复杂度。

实现下列函数：

void Purge(LinkList &L);

单链表类型定义如下：

typedef struct LNode{

ElemType data;

struct LNode *next;

} LNode, *LinkList;

void Purge(LinkList &L)

{

LinkList p,q;

int i=0;

p=L;

while(p!=NULL&&p->next!=NULL)

{

if(p->data==p->next->data)

{

q=p->next;

p->next=q->next;

free(q);

}

else

p=p->next;

}

}

◆2.21③ 试写一算法，实现顺序表的就地逆置，

即利用原表的存储空间将线性表(a1,a2,…,an)

逆置为(an,an-1,…,a1)。

实现下列函数：

void Inverse(SqList &L);

顺序表类型定义如下：

typedef struct {

ElemType *elem;

int length;

int listsize;

} SqList;

void Inverse(SqList &L)

{

int i=0,j=0;

i=/2;

for(j=0;j

{

ElemType e=[j];

[j]=[-j-1];

[-j-1]=e;

}

}

◆2.22③ 试写一算法，对单链表实现就地逆置。

实现下列函数：

void Inverse(LinkList &L);

/* 对带头结点的单链表L实现就地逆置 */

单链表类型定义如下：

typedef struct LNode{

ElemType data;

struct LNode *next;

} LNode, *LinkList;

void Inverse(LinkList &L)

/* 对带头结点的单链表L实现就地逆置 */

{

LinkList p,q,k;

q=p=L->next;

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均未

显式存储。

实现下列函数：

void Merge(LinkList ha, LinkList hb, LinkList &hc)

/* 依题意，合并带头结点的单链表ha和hb为hc */

单链表类型定义如下：

typedef struct LNode{

ElemType data;

struct LNode *next;

} LNode, *LinkList;

void Merge(LinkList ha, LinkList hb, LinkList &hc)

/* 依题意，合并带头结点的单链表ha和hb为hc */

{

LinkList p,q,k,r;

p=ha->next;

q=hb->next;

if(p==NULL)hc=hb;

else if(q==NULL) hc=ha;

else

{

while(p->next!=NULL&&q->next!=NULL)

{

k=p->next;

r=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表。

实现下列函数：

void Union(LinkList &lc, LinkList la, LinkList lb);

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

单链表类型定义如下：

typedef struct LNode{

ElemType data;

struct LNode *next;

} LNode, *LinkList;

void Union(LinkList &lc, LinkList la, LinkList lb)

{

LinkList pa=la->next;

LinkList pb=lb->next;

LinkList pre=NULL;

LinkList q,pc;

while(pa||pb)

{

if((pa->datadata&&pa!=NULL)||pb==NULL)

{

pc=pa;

q=pa->next;

pa->next=pre;

pa=q;

}

else

{

pc=pb;

q=pb->next;

pb->next=pre;

pb=q;

}

pre=pc;

printf("%s","done");

}

lc=la;

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

/* LinkList pa = la->next;

LinkList pb = lb->next;

LinkList pc = la;

lc = la;

while( pa && pb )

{

if( pa->data <= pb->data )

{

pc->next = pa;

pc = pa;

pa = pa->next;

}

else

{

pc->next = pb;

pc = pb;

pb = pb->next;

}

}

pc->next = pa? pa: pb;

free( lb );

//将c实现就地逆置

LinkList p,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所指结

点的前驱结点。

实现下列函数：

ElemType DeleteNode(LinkList s);

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

单链表类型定义如下：

typedef struct LNode{

ElemType data;

struct LNode *next;

} LNode, *LinkList;

ElemType DeleteNode(LinkList s)

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

{

LinkList p;

p=s->next;

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

p=p->next;

ElemType e=p->next->data;

p->next=s;

return e;

}

2.32② 已知有一个单向循环链表，其每个结点中

含三个域：prev、data和next，其中data为数据域，

next为指向后继结点的指针域，prev也为指针域，

但它的值为空(NULL)，试编写算法将此单向循环链

表改为双向循环链表，即使prev成为指向前驱结点

的指针域。

实现下列函数：

void PerfectBiLink(BiLinkList &CL);

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

typedef struct BiNode {

ElemType data;

int freq; // 2.38题用

struct BiNode *prev,

*next;

} BiNode, *BiLinkList;

void PerfectBiLink(BiLinkList &CL)

{

BiLinkList p,q,k;

k=p=q=CL;

while(p->next!=q)

{

p=p->next;

p->prev=k;

k=p;

}

q->prev=p;

}

◆2.33③ 已知由一个线性链表表示的线性表中含有

三类字符的数据元素（如：字母字符、数字字符和其

它字符），试编写算法将该线性链表分割为三个循环

链表，其中每个循环链表表示的线性表中均只含一类

字符。

实现下列函数：

void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll);

单链表类型定义如下：

typedef struct LNode{

ElemType data;

struct LNode *next;

} LNode, *LinkList;

void Split(LinkList &A, LinkList &B, LinkList &C, LinkList L)

{

LinkList s,p,q,r;

s=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'&&s->data<='z')||(s->data<='Z'&&s->data>='A'))

{

p->next=s;p=s;

}

else if(s->data>='0'&&s->data<='9')

{

q->next=s;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)。

实现下列函数：

void ReverseEven(BiLinkList &L);

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

typedef struct BiNode {

ElemType data;

int freq; // 2.38题用

struct BiNode *prev,

*next;

} BiNode, *BiLinkList;

void ReverseEven(BiLinkList &L)

{

BiLinkList p=NULL;

p=L->next;

while(p->next!=L&&p->next->next!=L)

{

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

p=p->next;

} //此时p指向最后一个奇数结点

if(p->next==L) p->next=L->prev->prev;

else p->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为

给定值），并分析你的算法的时间复杂度。

实现下列函数：

float Evaluate(SqPoly pn, float x);

/* [i].coef 存放ai， */

/* [i].exp存放ei (i=1,2,...,m) */

/* 本算法计算并返回多项式的值。不判别溢出。 */

/* 入口时要求0≤e1

多项式的顺序存储结构:

typedef struct {

int coef;

int exp;

} PolyTerm;

typedef struct {

PolyTerm *data;

int length;

} SqPoly;

float f(float x,int j)

{

int i;

float s = 1;

for( i = 0 ; i < j; ++i ){

s *= x;

}

return s;

}

float Evaluate(SqPoly pn, float x)

/* [i].coef 存放ai， */

/* [i].exp存放ei (i=1,2,...,m) */

/* 本算法计算并返回多项式的值。不判别溢出。 */

/* 入口时要求0≤e1

{

int i;

float s = 0;

for( i = 0; i < ; ++i ){

s += [i].coef * f( x, [i].exp );

}

return s;

}

◆2.41② 试以循环链表作稀疏多项式的存储结构，

编写求其导函数的算法，要求利用原多项式中的结

点空间存放其导函数（多项式），同时释放所有无

用（被删）结点。

实现下列函数：

void Difference(LinkedPoly &pa);

/* 稀疏多项式 pa 以循环链表作存储结构， */

/* 将此链表修改成它的导函数，并释放无用结点 */

链式多项式的类型定义：

typedef struct PolyNode {

int coef;

int exp;

struct PolyNode *next;

} PolyNode, *PolyLink; // 多项式元素（项）结点类型

typedef PolyLink LinkedPoly; // 链式多项式

void Difference(LinkedPoly &pa)

/* 稀疏多项式 pa 以循环链表作存储结构， */

/* 将此链表修改成它的导函数，并释放无用结点 */

{

LinkedPoly p,t;

t = pa->next;

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;

}

}