数据结构上机作业1-5章

第一章

◆1.16② 试写一算法，如果三个整数X，Y和Z的值不是依次非递增的，则通过交换，令其为非递增。

void Descend(int &x, int &y, int&z)

/* 按从大到小顺序返回x，y和z的值 */

{int t;

if(x<y)

{

t=x;

x=y;

y=t;

}

if(x<z)

{

t=x;

x=z;

z=t;

}

if(y<z)

{

t=y;

y=z;

z=t;}

}

1.17③已知k阶裴波那契序列的定义为

f0=0, f1=0, ...,fk-2=0, fk-1=1;

fn=fn-1+fn-2+...+fn-k,n=k,k+1,...

试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。

要求实现下列函数：

Status Fibonacci(int k, int m, int &f)

/* 求k阶斐波那契序列的第m项的值f */

{int tempd;

int temp[100];

int i,j,sum=0;

if(k<2||m<0) return ERROR;

if(m<k-1) f=0;

else if (m==k-1) f=1;

else

{

for(i=0;i<=k-2;i++) temp[i]=0;

temp[k-1]=1;

for(i=k;i<=m;i++)

{

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

sum=sum+temp[j];

temp[i]=sum;

sum=0;

}

f=temp[m];

}

return OK;

}

1.18③假设有A、B、C、D、E五个高等院校进行田径对抗赛，

各院校的单项成绩均以存入计算机并构成一张表，表中每一行的形式为项目名称 性别校名 成绩 得分.编写算法，处理上述表格，以统计各院校的男、女总分和团

体总分，并输出。

void Scores(ResultType *result, ScoreType*score)

/* 求各校的男、女总分和团体总分, 并依次存入数组score*/

/* 假设比赛结果已经储存在result[ ]数组中, */

/* 并以特殊记录 {"", male, ' ', "", 0 }（域scorce=0）*/

/* 表示结束 */

{

int i = 0;

while( result[i].sport )

{

switch( result[i].schoolname )

{

case 'A':

score[0].totalscore+= result[i].score;

if( result[i].gender == female )

score[0].femalescore+=result[i].score;

else

score[0].malescore+=result[i].score;

break;

case 'B':

score[1].totalscore += result[i].score;

if( result[i].gender == female )

score[1].femalescore+=result[i].score;

else

score[1].malescore+= result[i].score;

break;

case 'C':

score[2].totalscore += result[i].score;

if( result[i].gender == female )

score[2].femalescore+=result[i].score;

else

score[2].malescore += result[i].score;

break;

case 'D':

score[3].totalscore+= result[i].score;

if( result[i].gender == female )

score[3].femalescore+=result[i].score;

else

score[3].malescore+=result[i].score;

break;

case 'E':

score[4].totalscore+= result[i].score;

if( result[i].gender == female )

score[4].femalescore+=result[i].score;

else

score[4].malescore+=result[i].score;

break;

}

i++;

}

}

◆1.19④ 试编写算法，计算i!×2^i的值并存入数组

a[0..ARRSIZE-1]的第i-1个分量中 (i=1,2,…,n)。

假设计算机中允许的整数最大值为MAXINT，则当n>ARRSIZE或对某个k(1≤k≤n)使k!×2^k>MAXINT时，应

按出错处理。注意选择你认为较好的出错处理方法。

1.19

Status Series(int ARRSIZE, int a[])

/* 求i!*2^i序列的值并依次存入长度为ARRSIZE的数组a； */

/* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */

{

int i=1;

int t=1;

a[0]=1;int n;

for(n=1;n<ARRSIZE;n++)

{

i=i*n;

t=2*n;

a[i]=i*t;

}

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

{

if(a[i]>MAXINT)

return OVERFLOW;

break;

}

return OK;

}

◆1.20④ 试编写算法求一元多项式

P(x) = a0 + a1x + a2x^2 + ... + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法

的时间复杂度。注意选择你认为较好的输入和输出方法。

1.20

float Polynomial(int n, int a[], float x)

/* 求一元多项式的值P(x)。 */

/* 数组a的元素a[i]为i次项的系数，i=0,...,n */

{int i;

float s=0;

for(i=n;i>=0;i--)

s=s*x+a[i];

return s;

}

第二章

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

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

持该表的有序性。

2.11

void InsertOrderList(SqList &L,ElemType x)

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

{

intj;

j=L.length-1;

while(L.elem[j]>x)

{

L.elem[j+1]=L.elem[j];

j--;

}

L.elem[j+1]=x;

L.length++;

}

◆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'的首元，则A<B；否则A>B。试写一个比较A和B大小的算法。（注意：在算法中，不要破坏原表A和B，也不一定先求得A'和B'才进行比较）。

char Compare(SqList A, SqList B)

// 比较顺序表A和B,

// 返回'<', 若A<B;

//'=', 若A=B;

//'>', 若A>B

{

inti=0;

while((i<=A.length-1)&&(i<=B.length-1)&&(A.elem[i]=B.elem[i]))++i;

if(i==A.length&&i==B.length)return '=';

elseif(i==A.length&&i!=B.length&&A.elem[i]<B.elem[i]) return'<';

elseif(i!=A.length&&i!=B.length&&A.elem[i]<B.elem[i]) return'<';

else return '>';

}

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

Locate(L,x)。

实现下列函数：

LinkList Locate(LinkList L, ElemType x);

// If 'x' in the linked list whose headnode is pointed

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

// otherwise return 'NULL'

LinkList Locate(LinkList &L, ElemTypex)

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

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

//otherwise return 'NULL'

{

LinkList ha;

ha=L->next;

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

ha=ha->next;

if(ha==NULL)

return NULL;

else return ha;

}

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

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;

while(p->next!=NULL)

{

p=p->next;

i++;

}

return i;

}

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

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

{

LinkList p,s;

if(!L&&i==1)

{L=(LinkList)malloc(sizeof(LNode));

L->data=b;

L->next=NULL;

}

else

{ if(i==0) { }

else if(i==1)

{

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

s->data=b;

s->next=L;

L=s;

}

else

{

p=L; int j=1;

while(p&&j<i-1)

{

p=p->next;

j++ ;

}

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

s->data=b;

s->next=p->next;

p->next=s;

}

}

}

2.18② 同2.17题要求。试写一算法，

实现线性表操作DELETE(L,i)。

void Delete(LinkList &L, int i)

{

LinkList p,q;

if(i==0) { }

else if(i==1)

{

p=L;

L=L->next;

free(p);

}

else

{

int j=1;

p=L;

while(p->next!=NULL&&j<i-1)

{

p=p->next;

j++;

}

q=p->next;

p->next=q->next;

free(q);

}

}

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

void Purge(LinkList &L)

{LinkList p,q;

p=L->next;

q=p->next;

while(q)

{

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

{

q=q->next;

p->next=q;

}

q=q->next;

p=p->next;

}

}

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

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

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

void Inverse(SqList &L)

{

inttemp;

inti,j;

for(i=0,j=L.length-1;i<=j;i++,j--)

{

temp=L.elem[i];

L.elem[i]=L.elem[j];

L.elem[j]=temp;

}

}

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

void Inverse(LinkList &L)

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

{

LinkListp,q,r;

p=L->next;q=NULL;

while(p)

{

r=q;

q=p;

p=p->next;

q->next=r;

}

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*/

{

LinkList pa,pb,pc;

pa=ha->next;pb=hb->next;pc=hc=ha;

while(pa&&pb)

{

pc->next=pa;pc=pa;pa=pa->next;

pc->next=pb;pc=pb;pb=pb->next;

}

while(pa)

{

pc->next=pa;

pc=pa;

pa=pa->next;

}

while(pb)

{

pc->next=pb;

pc=pb;

pb=pb->next;

}

}

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

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

{

LinkList p,q,s,t;

lc=la; p=la->next; q=lb->next; lc->next=NULL;

while (p && q)

if (p->data<q->data)

{

s=p->next; p->next=lc->next;

lc->next=p; p=s;

}

else

{

t=q->next; q->next=lc->next;

lc->next=q; q=t;

}

while (p) {s=p->next; p->next=lc->next; lc->next=p; p=s;}

while (q) {t=q->next; q->next=lc->next; lc->next=q; q=t;}

free(lb);

}

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

ElemType DeleteNode(LinkList s)

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

{

LinkList p,q;

nti;

p=s;

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

p=p->next;

q=p->next;

i=q->data;

p->next=q->next;

free(q);

return i;

}

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

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

void PerfectBiLink(BiLinkList &CL)

{

BiLinkList p;

for(p=CL;!p->next->prev;p=p->next)

p->next->prev=p;

}

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

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

{

LinkList p,q,r,s;

p=lc;q=lo;

r=ld,s=ll->next;

while(s)

{

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

{

r->next=s;

r=r->next;

}

elseif(s->data>='A'&&s->data<='Z'||s->data>='a'&&s->data<='z')

{

p->next=s;

p=p->next;

}

else

{

q->next=s;

q=q->next;

}

s=s->next;

}

p->next=NULL;

q->next=NULL;

r->next=NULL;

}

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

void ReverseEven(BiLinkList &L)

{

BiLinkList p;

p=L->next;

if(p->next==L){}

else

{

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

{

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

p=p->next;

}

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

else p->next=L->prev;

p=p->next;

while(p->prev->prev!=L)

{

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

p=p->next;

}

p->next=L;

for(p=L;p->next!=L;p=p->next) p->next->prev=p;

L->prev=p;

}

}

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

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)

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

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

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

/* 入口时要求0≤e1<e2<...<em，算法内不对此再作验证*/

{int i;

float s = 0;

for( i = 0; i < pn.length; ++i ){

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

}

return s;

}

◆2.41②试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数（多项式），同时释放所有无用（被删）结点。

voidDifference(LinkedPoly &pa)

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

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

{

LinkedPoly p;

p=pa->next;

if(!p->exp)

{

pa->next=p->next;

p=p->next;

}

while(p!=pa)

{

p->coef=p->coef*p->exp ;

p->exp--;

p=p->next;

}

}

第三章

◆3.17③试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如'序列1&序列2'模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，'a+b&b+a'是属该模式的字符序列，而'1+3&3-1'则不是。

Status match(char *str)

/* 若str是属该模式的字符序列，*/

/* 则返回TRUE，否则返回FALSE */

{

SqStack s;

SElemType e;

InitStack(s);

int i=0;

while(str[i]!='&'&&str[i]!='@')

{

Push(s,str[i]);

i++;

}

if(str[i]=='@')

return FALSE;

if(str[i]=='&') i++;

while(str[i]!='@')

{

Pop(s,e);

if(e!=str[i])

return FALSE;

i++;

}

if(StackEmpty(s)&&str[i]=='@')

return TRUE;

else return FALSE;

}

3.18②试写一个判别表达式中开、闭括号是否配对出现的算法。

Status MatchCheck(SqList exp)

/* 顺序表exp表示表达式； */

/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */

/* 注：本函数不使用栈 */

{int i=0; int s=0;

while(exp.elem[i]!='\0')

{

if(exp.elem[i]=='(')

s++;

if(exp.elem[i]==')')

s--;

}

if(s==0)

return TRUE;

else return FALSE;

}

实现下列函数：

Status MatchCheck(SqList exp);

/* 顺序表exp表示表达式； */

/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */

/* 注：本函数不使用栈 */

顺序表类型定义如下：

typedef struct {

ElemType *elem;

int length;

int listsize;

} SqList;// 顺序表

◆3.19④ 假设一个算术表达式中可以包含三种括号：圆括号"(" 和")"，方括号"["和"]"和花括号"{"和"}"，且这三种括号可按任意的

次序嵌套使用（如：…[…{…}…[…]…]…[…]…(…)…）。编写判别给定表达式中所含括号是否正确配对出现的算法(已知表达式已存入数据元素

为字符的顺序表中)。

实现下列函数：

Status MatchCheck(SqList exp);

/* 顺序表exp表示表达式； */

/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */

顺序表类型定义如下：

typedef struct {

ElemType *elem;

int length;

int listsize;

} SqList;// 顺序表

Stack是一个已实现的栈。

可使用的相关类型和函数：

typedef char SElemType; // 栈Stack的元素类型

Status InitStack(Stack &s);

Status Push(Stack &s, SElemType e);

Status Pop(Stack &s, SElemType &e);

Status StackEmpty(Stack s);

Status GetTop(Stack s, SElemType &e);

Status MatchCheck(SqList exp)

/* 顺序表exp表示表达式； */

/* 若exp中的括号配对，则返回TRUE，否则返回FALSE */

{SqStack Q;

int i=0; SElemType e;

while(exp.elem[i]!='\0')

{

if(exp.elem[i]=='('||exp.elem[i]=='['||exp.elem[i]=='{')

Push(Q,exp.elem[i]);

else if(exp.elem[i]==')'||exp.elem[i]==']'||exp.elem[i]=='}')

{ if(!StackEmpty(Q))

Pop(Q,e) ;

else return FALSE;

if(e=='('&&exp.elem[i]!=')')

return ERROR;

if(e=='['&&exp.elem[i]!=']')

return ERROR;

if(e=='{'&&exp.elem[i]!='}')

return ERROR;

}

i++;

}

if(StackEmpty(Q))

return TRUE;

else return FALSE;

}

3.20③假设以二维数组g(1..m,1..n)表示一个图像区域，g[i,j]表示该区域中点(i,j)所具颜色，其值为从0到k的整数。编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色区域的点。

实现下列函数：

void ChangeColor(GTYPE g, int m, int n,

char c, int i0, int j0);

/* 在g[1..m][1..n]中，将元素g[i0][j0] */

/* 所在的同色区域的颜色置换为颜色c */

表示图像区域的类型定义如下：

typedef char GTYPE[m+1][n+1];

Stack是一个已实现的栈。

可使用的相关类型和函数：

typedef char SElemType; // 栈Stack的元素类型

Status StackInit(Stack &s, intinitsize);

Status Push(Stack &s, SElemType e);

Status Pop(Stack &s, SElemType &e);

Status StackEmpty(Stack s);

Status GetTop(Stack s, SElemType &e);

void ChangeColor(GTYPE g, int m, int n,

char c, int i0, int j0)

/* 在g[1..m][1..n]中，将元素g[i0][j0] */

/* 所在的同色区域的颜色置换为颜色c */

{Stack s;

int row,col;//行，列

InitStack(s);

char f;

f= g[i0][j0];

g[i0][j0] = c;

Push( s, i0);

Push( s, j0);

while( !StackEmpty(s) ){

Pop( s, col );

Pop( s, row );

if( row > 1 && g[row-1][col] == f ){

Push( s, row-1);

Push( s, col);

g[row-1][col] = c;

}

if( row < m && g[row+1][col] ==f ){

Push( s, row+1);

Push( s, col);

g[row+1][col] = c;

}

if( col > 1&& g[row][col-1] == f ){

Push( s, row);

Push( s, col-1);

g[row][col-1] = c;

}

if( col < n && g[row][col+1] == f ){

Push( s, row );

Push( s, col+1 );

g[row][col+1] = c;

}

}

}

◆3.21③假设表达式由单字母变量和双目四则运

算算符构成。试写一个算法，将一个通常书写形式

且书写正确的表达式转换为逆波兰式。

实现下列函数：

char *RPExpression(char *e);

/* 返回表达式e的逆波兰式 */

Stack是一个已实现的栈。

可使用的相关类型和函数：

typedef char SElemType; // 栈Stack的元素类型

Status InitStack(Stack &s);

Status Push(Stack &s, SElemType e);

Status Pop(Stack &s, SElemType &e);

Status StackEmpty(Stack s);

intprecede(char op)

{int x;

switch(op)

{

case '*': x=2;break;

case '/': x=2;break;

case '+': x=1;break;

case '-': x=1;break;

default : x=0;

}

return x;

}

char *RPExpression(char *e)

{/* 返回表达式e的逆波兰式 */

char *c;

c=(char*)malloc(sizeof(char)*20);//不能用char c[]

Stack s1;

InitStack(s1);

int i=0,j=0;

char ch;

Push(s1,'@');

ch=e[i++];

while(ch!= 0)

{

if(ch=='(')

{

Push(s1,ch);

ch=e[i++];

}

else if(ch==')')

{

while(Top(s1)!='(')

{

Pop(s1,c[j++]);

}

/* to[j++]=pop(&s1);*/

Pop(s1,ch);

ch=e[i++];

}

else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')

{

char w;

w=Top(s1);

while(precede(w)>=precede(ch))

{

Pop(s1,c[j++]);

w=Top(s1);

}

Push(s1,ch);

ch=e[i++];

}

else

{

//while((ch<='z'&&ch>='a')||(ch<='Z' &&ch>='A')){

c[j++]=ch;

ch=e[i++];

//}

//c[j++]=' ';

}

}

Pop(s1,ch);

while(ch!='@')

{

c[j++]=ch;

Pop(s1,ch);

}

//c[j++]=;

c[j++]=0;

return c;

}

3.24③试编写如下定义的递归函数的递归算法:

g(m,n) = 0 当m=0,n>=0

g(m,n) = g(m-1,2n)+n 当m>0,n>=0

并根据算法画出求g(5,2)时栈的变化过程。

int G(int m, int n)

/* if m<0 or n<0 then return -1. */

{

intF;

if(m<0||n<0) return -1;

else if(m==0&&n>0)F=0;

elseif(m==0&&n==0) F=0;

else if(m>0&&n>=0)

F=G(m-1,2*n)+n;

return F;

}

3.25

int F(int n)

/* if n<0 then return -1. */

{int f;

if(n<0) return -1;

else

{

if(n==0) f=n+1;

else f=n*F(n/2);

return f;

}

}

3.25④试写出求递归函数F(n)的递归算法，

并消除递归：

F(n) = n+1 当n=0

F(n) = nF(n/2) 当n>0

实现下列函数：

int F(int n);

/* if n<0 then return -1. */

int F(int n)

/* if n<0 then return -1. */

{int f;

if(n<0) return -1;

else

{

if(n==0) f=n+1;

elsef=n*F(n/2);

return f;

}

}

◆3.28② 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。

实现下列函数：

Status InitCLQueue(CLQueue &rear);

Status EnCLQueue(CLQueue &rear,ElemType x);

Status DeCLQueue(CLQueue &rear,ElemType &x);

带头结点循环链队列CLQueue的类型为以下LinkList类型：

typedef struct LNode{

ElemType data;

struct LNode *next;

} LNode, *LinkList;

typedef LinkList CLQueue;

Status InitCLQueue(CLQueue &rear)

{

rear=(LNode*)malloc(sizeof(LNode));

rear->next=rear;

return OK;

}

Status EnCLQueue(CLQueue &rear,ElemType x)

{

LinkList p;

p=(LNode*)malloc(sizeof(LNode));

p->data=x;

p->next=rear->next;

rear->next=p;

rear=p;

return OK;

}

Status DeCLQueue(CLQueue &rear,ElemType &x)

{LinkList p;

if(rear->next!=rear )

{

p=rear->next;

rear->next=p->next;

free(p);

return OK; }

else return ERROR;

}

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

实现下列函数：

Status EnCQueue(CTagQueue &Q, QElemTypex);

Status DeCQueue(CTagQueue &Q, QElemType&x);

本题的循环队列CTagQueue的类型定义如下：

typedef char QElemType;

typedef struct {

QElemType elem[MAXQSIZE];

int tag;

int front;

int rear;

} CTagQueue;

Status EnCQueue(CTagQueue &Q, QElemTypex)

{int tag;

if(Q.front==Q.rear&&tag==1)

return ERROR;

Q.elem[Q.rear]=x;

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

tag=1;

return OK;

}

Status DeCQueue(CTagQueue &Q, QElemType&x)

{

int tag;

if(Q.front==Q.rear&&tag==0)

return ERROR;

x=Q.elem[Q.front];

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

if(Q.front==Q.rear)

tag=0;

return OK;

}

◆3.30②假设将循环队列定义为：以域变量rear

和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。

实现下列函数：

Status EnCQueue(CLenQueue &Q, QElemTypex);

Status DeCQueue(CLenQueue &Q, QElemType&x);

本题的循环队列CLenQueue的类型定义如下：

typedef char QElemType;

typedef struct {

QElemType elem[MAXQSIZE];

int length;

int rear;

} CLenQueue;

StatusEnCQueue(CLenQueue&Q,

QElemType x)

{

if(Q.length==MAXQSIZE)

return ERROR;

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

Q.elem[Q.rear]=x;

Q.length++;

return OK;

}

Status DeCQueue(CLenQueue &Q, QElemType&x)

{

if(Q.length==0)

return ERROR;

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

Q.length--;

return x;

}

◆3.31③假设称正读和反读都相同的字符序列为"回文"，例如，'abba'和'abcba'是回文，'abcde'

和'ababab'则不是回文。试写一个算法判别读入的

一个以'@'为结束符的字符序列是否是"回文"。

实现下列函数：

Status Palindrome(char *word);

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

可使用栈Stack和队列Queue及其下列操作：

Status InitStack(Stack &S);

Status Push(Stack &S, ElemType x);

Status Pop(Stack &S, ElemType&x);

Status StackEmpty(Stack S);

Status InitQueue(Queue &Q);

Status EnQueue(Queue &Q, ElemType x);

Status DeQueue(Queue &Q, ElemType&x);

Status QueueEmpty(Queue Q);

Status Palindrome(char *word)

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

{

Stack Q;

SElemType e,f;

Queue S;

char *p;

p=word;

InitStack(Q);

InitQueue(S);

while(*p!='@')

{

Push(Q,*p);EnQueue(S,*p);

p++;

}

while(!StackEmpty(Q))

{ Pop(Q,e); DeQueue(S,f);

if(e!=f)

return ERROR;

}

return OK;

}

第四章

4.10③ 编写对串求逆的递推算法。

要求实现以下函数：

void Reverse(StringType &s);

/* Reverse s by iteration. */

StringType是串的一个抽象数据类型，它包含以下6种基本操作：

void InitStr(StringType &s);

// 初始化s为空串。

void StrAssign(StringType &t,StringType s);

// 将s的值赋给t。s的实际参数是串变量。

int StrCompare(StringType s, StringType t);

// 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s<t，返回值<0。

int StrLength(StringType s);

// 返回s中的元素个数，即该串的长度。

StringType Concat(StringType &s,StringType t);

// 返回由s和t联接而成的新串。

StringType SubString(StringType s, intstart, int len);

// 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时，

// 返回s中第start个字符起长度为len的子串，否则返回空串。

// 注意,不要使用 " s= " 的形式为StringType 类型的变量赋值 ,

// 而要使用 StrAssign 函数!!!

void Reverse(StringType &s)

/* Reverse s by iteration. */

{

int i=0,j=StrLength(s)-1;

char temp;

while(i<=j)

{

temp=s[i];

s[i]=s[j];

s[j]=temp;

i++;j--;

}

}

4.12③ 编写一个实现串的置换操作Replace(&S,T,V)的算法。

要求实现以下函数：

void Replace(StringType &S, StringTypeT, StringType V);

/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */

StringType是串的一个抽象数据类型，它包含以下6种基本操作：

void InitStr(StringType &s);

// 初始化s为空串。

void StrAssign(StringType &t,StringType s);

// 将s的值赋给t。s的实际参数是串变量。

int StrCompare(StringType s, StringType t);

// 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s<t，返回值<0。

int StrLength(StringType s);

// 返回s中的元素个数，即该串的长度。

StringType Concat(StringType &s,StringType t);

// 返回由s和t联接而成的新串。

StringType SubString(StringType s, intstart, int len);

// 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时，

// 返回s中第start个字符起长度为len的子串，否则返回空串。

// 注意,不要使用 " s= " 的形式为StringType 类型的变量赋值 ,

// 而要使用 StrAssign 函数!!!

void Replace(StringType &S, StringTypeT, StringType V)

/* 以串 v 置换串 s 中出现的所有和串 t 相同的非空串 */

{

int i; StringType head,tail;

//InitStr(head);InitStr(tail);

for(i=1;i<=StrLength(S)-StrLength(T)+1;i++)

if(!StrCompare(SubString(S,i,StrLength(T)),T))

{

StrAssign(head,SubString(S,1,i-1));

StrAssign(tail,SubString(S,i+StrLength(T),StrLength(S)-i-StrLength(T)+1));

StrAssign(S,Concat(head,V));

Concat(S,tail);

i=i+StrLength(V)-1;

}

}

4.13③ 编写算法，从串s中删除所有和串t相同的子串。

要求实现以下函数：

void DelSubString(StringType &scrStr,StringType subStr);

/* Remove all substring matching 'subStr'from 'scrStr'. */

StringType是串的一个抽象数据类型，它包含以下6种基本操作：

void InitStr(StringType &s);

// 初始化s为空串。

void StrAssign(StringType &t,StringType s);

// 将s的值赋给t。s的实际参数是串变量。

int StrCompare(StringType s, StringType t);

// 比较s和t。若s>t，返回值>0；若s=t，返回值=0；若s<t，返回值<0。

int StrLength(StringType s);

// 返回s中的元素个数，即该串的长度。

StringType Concat(StringType &s,StringType t);

// 返回由s和t联接而成的新串。

StringType SubString(StringType s, intstart, int len);

// 当1<=start<=StrLength(s)且0<=len<=StrLength(s)- start+1时，

// 返回s中第start个字符起长度为len的子串，否则返回空串。

// 注意,不要使用 " s= " 的形式为StringType 类型的变量赋值 ,

// 而要使用 StrAssign 函数!!!

void DelSubString(StringType &scrStr,StringType subStr)

/* Remove all substring matching 'subStr'from 'scrStr'. */

{

StringType head,tail,S;

int i;

InitStr(head);

InitStr(tail);

for(i=1;i<=StrLength(scrStr)-StrLength(subStr)+1;i++)

if(!StrCompare(SubString(scrStr,i,StrLength(subStr)),subStr))

{

StrAssign(head,SubString(scrStr,1,i-1));

StrAssign(tail,SubString(scrStr,i+StrLength(subStr),StrLength(scrStr)-i-StrLength(subStr)+1));

StrAssign(scrStr,Concat(head,tail));

i--; /*向后退一位*/

}

}

4.17③ 编写算法，实现串的基本操作Replace(&S,T,V)。要求采用教科书4.2.1节中所定义的定长顺序存储表示，但不允许调用串的基本操作。

要求实现以下函数：

Status Replace(SString& s, SString t,SString v);

/* 用串v替换串s中所有和串t匹配的子串。 */

/* 若有与t匹配的子串被替换，则返回TRUE；*/

/* 否则返回FALSE*/

定长顺序串SString的类型定义：

typedef unsigned charSString[MAXSTRLEN+1];

/* s[0] is the string's length */

int Index(SString s, SString t,int pos )

{

int i = pos;

int j = 1;

while( i<= s[0]&&j<=t[0])

{

if( s[i] == t[j] ){ ++i; ++j; }

else{i= i-j+2;j=1;}

}

if( j > t[0] ) return i -t[0];

else return 0;

}

Status Replace(SString& s, SString t,SString v)

/* 用串v替换串s中所有和串t匹配的子串。 */

/* 若有与t匹配的子串被替换，则返回TRUE；*/

/* 否则返回FALSE*/

{int flag = 0;//是否替换的标志

int i,j,w,r; //i是s1的标志，j是s的标志，

SString s1;

for( i = 0; i <= s[0]; i++ )

s1[i] = s[i];

for( i = 1, j = 1; i <= s1[0]; )

{

w = Index( s1, t, i); //返回t的起始位置

if( !w )

{

while( i <= s1[0] )

s[j++] = s1[i++];

}

else

{

while( i < w )

s[j++] = s1[i++];

for( r = 1; r <= v[0]; r++ )

s[j++] = v[r];

flag++;

i += t[0];

}

}

s[0] = --j;

if( flag )

return TRUE;

return FALSE;

}

/*int i,j,k,l;

for(i=1;i<=s[0]-t[0]+1;i++)

{

for(j=i,k=1;t[k]&&s[j]==t[k];j++,k++)

if(k>t[0])

{

if(t[0]==v[0])

for(l=1;i<=t[0];l++)

s[i+l-1]=v[l];

else if(t[0]<v[0])

{

for(l=s[0];l>i+t[0];l--)

s[l+v[0]-t[0]]=s[l];

for(l=1;l<=v[0];l++)

s[i+l-1]=v[l];

}

else

{

for(l=i+v[0];l<=s[0]+v[0]-t[0];l++)

s[l]=s[l-v[0]+t[0]];

for(l=1;l<=v[0];l++)

s[i+l-1]=v[l];

}

s[0]=s[0]-t[0]+v[0];

i=i+v[0];

}

}

return TRUE; */

4.20③ 编写算法，从串s中删除所有和串t相同的子串。

要求实现以下函数：

Status DelSub(SString &s, SString t);

/* 从串s中删除所有和串t匹配的子串。 */

/* 若有与t匹配的子串被删除，则返回TRUE；*/

/* 否则返回FALSE*/

定长顺序串SString的类型定义：

typedef unsigned charSString[MAXSTRLEN+1];

/* s[0] is the string's length */

int Index(SString s, SString t,int pos )

{

int i = pos;

int j = 1;

while( i<= s[0]&&j<=t[0])

{

if( s[i] == t[j] ){ ++i; ++j; }

else{i= i-j+2;j=1;}

}

if( j > t[0] ) return i -t[0];

else return 0;

}

Status DelSub(SString &s, SString t)

/* 从串s中删除所有和串t匹配的子串。 */

/* 若有与t匹配的子串被删除，则返回TRUE；*/

/* 否则返回FALSE*/

{

int flag = 0;//是否替换的标志

int i,j,w; //i是s1的标志，j是s的标志，

for( i = 1, j = 1; i <= s[0]; )

{

w = Index( s, t, i); //返回t的起始位置

if( !w )

{

while( i <= s[0] )

s[j++] = s[i++];

}

else

{

while( i < w )

s[j++] = s[i++];

flag++;

i += t[0];

}

}

s[0] = --j;

if( flag )

return TRUE;

return FALSE;

}

4.24③采用教科书4.2.2节中所定义的堆分配存储表示。试写一算法，在串的堆存储结构上实现串基本操作Concat(&T,s1, s2)。

要求实现以下函数：

Status Concat(HString &S, HString S1,HString S2)

/* 用S返回由S1和S2联接而成的新串 */

堆串HString的类型定义：

typedef struct {

char *ch; // 若是非空串,则按串长分配存储区,否则ch为NULL

int length; // 串长度

} HString;

Status Concat(HString &S, HString S1,HString S2)

/* 用S返回由S1和S2联接而成的新串 */

{

int i, j;

if( !(S.ch=(char*)realloc(S.ch,(S1.length+S2.length)*sizeof(char))))

exit(OVERFLOW);

for(i=0;i<S1.length;i++)

S.ch[i]=S1.ch[i];

for(j=0;j<S2.length;j++)

S.ch[j+i]=S2.ch[j];

S.length=S1.length+S2.length;

}

4.30⑤假设以定长顺序存储结构表示串，试设计

一个算法，求串s中出现的第一个最长重复子串及

其位置，并分析你的算法的时间复杂度。

要求实现以下函数：

void CommonStr(SString s, SString &sub,int &loc);

/* 求串s中出现的第一个最长重复子串sub及其位置loc */

定长顺序串SString的类型定义：

typedef unsigned char SString[MAXSTRLEN+1];

/* s[0] is the string's length */

void CommonStr(SString s, SString &sub,int &loc)

/* 求串s中出现的第一个最长重复子串sub及其位置loc */

{int index=0,length=0,length1,i=0,j,k;

while(i<s[0])

{

j=i+1;

while(j<=s[0])

{

if(s[i]==s[j])

{

length1=1;

for(k=1;s[i+k]==s[j+k];k++)

length1++;

if(length1>=length)

{

index=i;

length=length1;

}

j=j+length1;

}

else j++;

}

i++;

}

loc=index;

sub[0]=length;

}

第五章

5.21④ 假设稀疏矩阵A和B均以三元组表作为存储结构。

试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

要求实现以下函数：

Status AddTSM(TSMatrix A,TSMatrixB,TSMatrix &C);

/* 三元组表示的稀疏矩阵加法: C=A+B */

稀疏矩阵的三元组顺序表类型TSMatrix的定义：

#define MAXSIZE 20 // 非零元个数的最大值

typedef struct {

int i,j; // 行下标,列下标

ElemType e; // 非零元素值

}Triple;

typedef struct {

Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用

intmu,nu,tu; // 矩阵的行数、列数和非零元个数

}TSMatrix;

Status AddTSM(TSMatrix A,TSMatrixB,TSMatrix &C)

/* 三元组表示的稀疏矩阵加法: C=A+B */

{if(A.mu != B.mu || A.nu != B.nu )

return ERROR;

C.mu=A.mu;C.nu=A.nu;C.tu=0;

intpa=1;

intpb=1;

intpc=1;

ElemType ce;

intx;

for(x=1;x<=A.mu;x++)

//对矩阵的每一行进行加法

{

while(A.data[pa].i<x) pa++;

while(B.data[pb].i<x) pb++;

while(A.data[pa].i==x&&B.data[pb].i==x)

//行列值都相等的元素

{

if(A.data[pa].j==B.data[pb].j)

{

ce=A.data[pa].e+B.data[pb].e;

if(ce) //和不为0

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=ce;

pa++;pb++;pc++;

}

}//if

else if(A.data[pa].j>B.data[pb].j)

{

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j;

C.data[pc].e=B.data[pb].e;

pb++;pc++;

}

else

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=A.data[pa].e;

pa++;pc++;

}

}//while

while(A.data[pa].i==x) //插入A中剩余的元素(第x行)

{

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j;

C.data[pc].e=A.data[pa].e;

pa++;pc++;

}

while(B.data[pb].i==x) //插入B中剩余的元素(第x行)

{

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j;

C.data[pc].e=B.data[pb].e;

pb++;pc++;

}

}//for

C.tu=pc;

return OK;

}//TSMatrix_Add

/*

{int s=1,t=1,k=1;

while(s<A.tu&&t<B.tu)

if(A.data[s].i==B.data[t].i)

{

if(A.data[s].i<B.data[t].i)

{C.data[k].i=A.data[s].i;

C.data[k].j=A.data[s].j;

C.data[k].e=A.data[s].e;

k++;

s++;

}

else if(A.data[s].i>B.data[t].i)

{C.data[k].i=B.data[t].i;

C.data[k].j=B.data[t].j;

C.data[k].e=B.data[t].e;

k++;

t++;

}

else

{

C.data[k].i=B.data[t].i;

C.data[k].j=B.data[t].j;

C.data[k].e=A.data[s].e+B.data[t].e;

if(C.data[k].e!=0)

k++;

s++;

t++;

}

}

else if(A.data[s].i<B.data[t].i)

{C.data[k].i=A.data[s].i;

C.data[k].j=A.data[s].j;

C.data[k].e=A.data[s].e;

k++;

s++;

}

else

{C.data[k].i=B.data[t].i;

C.data[k].j=B.data[t].j;

C.data[k].e=B.data[t].e;

k++;

t++;

}

C.mu=A.mu;

C.nu=A.nu;

C.tu=k;

return 1;

}

*/

5.23② 三元组表的一种变型是，从三元组表中去掉行下标域得到二元组表，另设一个行起始向量，其每个分量是二元组表的一个下标值，指示该行中第一个非零元素在二元组表中的起始位置。试编写一个算法，由矩阵元素的下标值i，j求矩阵元素。试讨论这种方法和三元组表相比有什么优缺点。

要求实现以下函数：

Status GetElem(T2SMatrix M, int i, int j,ElemType &e);

/* 求二元组矩阵的元素A[i][j]的值e */

稀疏矩阵的二元组顺序表＋行起始向量的类型T2SMatrix的定义：

typedef struct{

int j;

ElemType e;

}TwoTuples;

typedef struct{

TwoTuples data[MAXSIZE];

int cpot[MAXROW]; // 这个向量存储每一行在二元组中的起始位置

int mu,nu,tu;

} T2SMatrix; // 二元组矩阵类型

Status GetElem(T2SMatrix M, int i, int j,ElemType &e)

/* 求二元组矩阵的元素A[i][j]的值e */

{int t;

if( i > M.mu || i < 0 || j > M.nu || j < 0 ) //i,j超出范围，0<i<M.mu,0<j<M.nu

return ERROR;

for( t = M.cpot[i]; M.data[t].j != j&&t < M.cpot[i+1]; t++ );

if( t == M.cpot[i+1] )

e = 0;

else

e = M.data[t].e;

return OK;

}

/*

Status GetElem(T2SMatrix M, int i, int j,ElemType &e)

{

for(s=A.cpot[i];s<A.cpot[i+1]&&A.data[s].j!=j;s++);//注意查找范围

if(s<A.cpot[i+1]&&A.data[s].j==j) //找到了元素A[i][j]

{

e=A.data[s];

return OK;

}

return ERROR;

}

*/

5.26③ 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。

要求实现以下函数：

void OutCSM(CrossList M);

/* 以三元组格式输出十字链表表示的矩阵 */

稀疏矩阵的十字链表存储表示:

typedef struct OLNode {

inti,j; // 该非零元的行和列下标

ElemType e; // 非零元素值

OLNode *right,*down; // 该非零元所在行表和列表的后继链域

}OLNode, *OLink;

typedef struct {

OLink *rhead,*chead; // 行和列链表头指针向量基址

intmu,nu,tu; // 稀疏矩阵的行数、列数和非零元个数

}CrossList;

void OutCSM(CrossList M, void(*Out3)(int,int, int))

/* 用函数Out3,依次以三元组格式输出十字链表表示的矩阵 */

{int i; OLink p;

for(i=0;i<=M.mu;i++)

{

if(M.rhead[i])

for(p=M.rhead[i];p;p=p->right)

Out3(i,p->j,p->e);

}

}

5.30③ 试按表头、表尾的分析方法重写求广义表

的深度的递归算法。

要求实现以下函数：

int GListDepth(GList ls);

/* Return the depth of list */

广义表类型GList的定义：

typedef enum {ATOM,LIST} ElemTag;

typedef struct GLNode{

ElemTag tag;

union {

char atom;

struct {

GLNode *hp, *tp;

} ptr;

}un;

} *GList;

int GListDepth(GList ls)

/* Return the depth of list */

{ int m,n;

if(ls==NULL) return 1;

else if(ls->tag==0) return 0;

m=GListDepth(ls->un.ptr.hp)+1;

n=GListDepth(ls->un.ptr.tp);

if(m>n) return m;

else return n;

}

/*

{ int m,n;

if(ls==NULL) return 1;

else if(ls->tag==0) return 0;

m=GListDepth(ls->ptr.hp)+1;

n=GListDepth(ls->ptr.tp);

return m>n?m:n;

}*/

5.33④ 试编写递归算法，输出广义表中所有原子项及其所在层次。

广义表类型GList的定义：

typedef enum {ATOM,LIST} ElemTag;

typedef struct GLNode{

ElemTag tag;

union {

char atom;

struct {

GLNode *hp, *tp;

} ptr;

}un;

} *GList;

void OutAtom(GList A, int layer,void(*Out2)(char, int))

/* 递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次 */

{

if(!A) return ;

if(!A->tag)Out2(A->un.atom,layer);

else

{

OutAtom(A->un.ptr.hp,layer+1,Out2);

OutAtom(A->un.ptr.tp,layer,Out2);

}

}