习题讲评(二)

第二章 线性表

P18 — P20

2.32 、2.39 、2.41

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

Status DuLNode_Pre(DuLinkList &L) //完成双向循环链表结点的pre域

{

for(p=L; p->next->pre = = NULL; p=p->next)

p->next->pre=p;

return OK;

}//DuLNode_Pre

2.39③ 已知稀疏多项式Pn(X)=c1xe1

+ c2xe2+…+cmxem 其中

n=

em >em-1>…….>e1>=0，ci≠0（i=1，2，…m），m≥1。试采用存储同多项式数m成正比的顺序存储结构，编写求Pn（x0）的算法（x0 为给定值），并分析你的算法的时间复杂度。

1

typedef struct{

float coef; //系数；

int exp；//指数；

}PolyTerm；

typedef struct{

PolyTerm *data;

int length;

int listsize;

} SqPoly; //类似顺序表中结构体的定义；

float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值{

PolyTerm *q;

xp=1;

2

q=P.data;

sum=0;

while(q->coef) //系数；

{

ex=0;

while(exexp){

xp*=x0;

ex++;

}

sum+=q->coef*xp;

q++;

}

return sum;

3

}//GetValue_SqPoly

时间复杂度：n2

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

void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导

{

p=L->next;

if(!p->data.exp) //跳过常数项

{

L->next=p->next;

p=p->next;

}

while(p!=L) //循环链表；

4

{

p->data.coef*=p->data.exp;//对每一项求导

p->data.exp--；

p=p->next;

}

}//QiuDao_LinkedPoly

cmxem的导数为：cmemxem-1

第三章 栈和队列

3.17 3.25 3.31 3.32 3.33

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

int IsReverse()

//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0

5

{

InitStack(s);

while((e=getchar()) != '&')

push(s,e);

while((e=getchar()) != '@')

{

if(StackEmpty(s)) return 0;

pop(s,c);

if(e!=c) return 0;

}

if(!StackEmpty(s)) return 0; return 1;

}//IsReverse

//判断栈中是否还有元素；6

3.25④试写出递归函数F（n）的递归算法，并消除递归：

F(n)=n+1 , n=0; F(n)=n*F(n/2) , n>0

Status F_recursive(int n, int &s) //递归算法；s为返回值；

{

if(n<0) return ERROR;

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

else

{

F_recurve(n/2, r) ;

s = n*r ;

}

return OK;

}//F_recursive

7

Status F_nonrecursive(int n,int s)//非递归算法

{

if(n<0) return ERROR;

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

else

{

InitStack(s); //s的元素类型为struct {int a; while(n!=0)

{

a=n; b=n/2;

push(s, {a, b});

n=b;

}//while

int b;}

8

sum=1;

while(!StackEmpty(s))

{

pop(s, t);

sum *= t.a;

}//while

}

return OK;

}//F_nonrecursive

3.31③假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘bcde’和‘ababa’则不是回文，试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

栈：后进先出；

队列：先进先出；

9

int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0

{

InitStack(S); //初始化栈；

InitQueue(Q); //初始化队列；

while((c=getchar()!='@')

{

Push(S,c); //入栈；

EnQueue(Q,c); //入队列；

}

while(!StackEmpty(S))

{

Pop(S,a); //出栈；

DeQueue(Q,b)); //出队列；

10

if(a!=b) return ERROR;

}

return OK; //若是回文，则返回OK；

}//Palindrome_Test

3.32④试利用循环队列编写求k阶斐波那契序列中前n+1项，（f0 ，f1 ，…. fn）的算法,要求满足: fn ≤max而fn+1>max,其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项 fn-k+1 ，…. fn）。

void GetFib_CyQueue(int k, int max)//求k阶斐波那契序列的前n+1项 {

InitCyQueue(Q); //其MAXSIZE设置为k for(i=0;iQ.base[k-1]=1; //给前k项赋初值0, …, 0, 1 for(i=0;i11

flag = 0; //设置标志； for(i=k; flag = = 0; i++) {

m=i % k; sum=0;

for(j=0; jQ.base[m]=sum; //求第i项的值存入队列中并取代已无用的第一项 printf(\"%d\ //要求满足: fn ≤max而fn+1>max; }

else flag=1; //退出循环； }

}//GetFib_CyQueue

12

3.33③在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。

双端循环队列：两端都可以进行入列和出列操作。

输出受限的双端循环队列：队头可以入列和出列，队尾只能入列。

rear指向最后一个元素的下一个位置；front指向第一个元素；

Status EnDQueue(DQueue &Q, int x) //输出受限的双端队列的入队操作

{

if((Q.rear+1)%MAXSIZE = = Q.front) return OVERFLOW; //队列满;牺牲一个结点；

avr = (Q.base[Q.rear-1] + Q.base[Q.front])/2; //队头和队尾作业的平均时间;

if(x>=avr) //插入队尾

{

Q.base[Q.rear]=x;

Q.rear=(Q.rear+1)%MAXSIZE; // rear指向最后一个元素的下一个位置;

13

}

else

{

Q.front=(Q.front-1)%MAXSIZE; // front下移一位；

Q.base[Q.front]=x; // front指向第一个元素；

} //插入在队头

return OK;

}//EnDQueue

Status DeDQueue(DQueue &Q, int &x) //输出受限的双端队列的出队操作

{ //只能在队头出列，队尾不允许出列；

if(Q.front = = Q.rear) return ERROR; //队列空；

x=Q.base[Q.front];

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

14

return OK;

}//DeDQueue

第四章 串

串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集。这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。

StrAssign (&T, chars) //串赋值

初始条件：chars 是字符串常量。

操作结果：把 chars 赋为 T 的值。

StrCopy (&T, S) //串复制

初始条件：串 S 存在。

操作结果：由串 S 复制得串 T。

利用最小操作子集中的操作也可实现

串判空 StrEmpty(S) 、串替换 Replace (&S, T, V) 、串删除 StrDelete (&S, pos, len) 、

15

串插入 StrInsert (&S, pos, T) 等操作。

串判空：

int StrEmpty(String S){

if (!StrLength(S))

return TRUE; //为空；

else return FALSE; //不为空；

}

串替换：

初始条件：串S, T和 V 均已存在，且 T 是非空串。

操作结果：用V替换主串S中出现的所有与（模式串） T相等的不重叠的子串。

int Replace(String &S, String T, String V);//将串S中所有子串T替换为V,并返回置换次数

{

for(n=0, i=1; i<=Strlen(S)-Strlen(T)+1; i++) //注意i的取值范围

16

if(!StrCompare(SubString(S, i, Strlen(T)), T)) //找到了与T匹配的子串

{ //分别把T的前面和后面部分保存为head和tail;

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

Strcopy (tail, SubString(S, i+Strlen(T), Strlen(S)-i-Strlen(T)+1));

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

Strcopy (S, Concat(S,tail)); //把head, V, tail连接为新串

i+=Strlen(V); //当前指针跳到插入串以后

n++;

}//if

return n;

}//Replace

分析: i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?

17

串删除:

int StrDelete (String &S, int pos, int len){

if(1≤pos≤StrLength(S)-len+1)

{

Strcopy (head, SubString(S, 1, pos-1));

Strcopy (tail, SubString(S, pos+len, Strlen(S)-pos-len+1));

Strcopy (S, Concat(head, tail)); //把head, tail连接为新串 return OK;

}

else return ERROR;

}// StrDelete

串插入:

初始条件：串S和T存在， 1≤pos≤StrLength(S)＋1。

18

操作结果：在串S的第pos个字符之前插入串T。

int StrInsert (String &S, int pos, String T);

{

if(1≤pos≤StrLength(S)＋1)

{

Strcopy (head, SubString(S, 1, pos-1));

Strcopy (tail, SubString(S, pos, Strlen(S)-pos+1));

Strcopy (S, Concat(head, T));

Strcopy (S, Concat(S,tail)); //把head, T, tail连接为新串

return OK;

}

else return ERROR;

}//StrInsert

19