数据结构与算法课后习题解答

数据结构与算法课后习题解答

第一章绪论（参考答案）

1.3 (1) O(n)

(2) (2) O(n)

(3) (3) O(n)

(4) (4) O(n1/2)

(5) (5) 执行程序段的过程中，x,y值变化如下：

循环次数 x y

0（初始） 91 100

1 92 100

2 93 100

…… ……

9 100 100

10 101 100

11 91

12

……

20 99

21 91 98

…… ……

30 101 98

31 91 97

到y=0时，要执行10*100次，可记为O（10*y）=O（n）

数据结构与算法课后习题解答

1.5 2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n

第二章 线性表(参考答案)

在以下习题解答中，假定使用如下类型定义：

（1）顺序存储结构：

#define MAXSIZE 1024

typedef int ElemType;// 实际上，ElemType

typedef struct

{ ElemType data[MAXSIZE];

int last; // last

}sequenlist;

（2

*next；

}linklist;

（3）链式存储结构（双链表）

typedef struct node

{ElemType data;

struct node *prior,*next；

数据结构与算法课后习题解答

}dlinklist;

（4）静态链表

typedef struct

{ElemType data;

int next;

}node;

node sa[MAXSIZE];

2.1 la，往往简称为“链表la”。

是副产品）

2.2 2·3

void

elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的

{ int i=0,j;

while (i<elenum && A[i]<=x) i++; // 查找插入位置

for (j= elenum-1;j>=i;j--) A[j+1]=A[j];// 向后移动元素

A[i]=x; // 插入元素

数据结构与算法课后习题解答

} // 算法结束 2·4

void rightrotate(ElemType A[],int n,k)

// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。

{ int num=0; // 计数，最终应等于n

int start=0; // 记录开始位置（下标）

while (num<n)

{ temp=A[start]; //暂存起点元素值，temp

empty=start; //保存空位置下标

next=(start-K+n) %n; //

while (next !=start)

{ A[empty]=A[next];//

num++; 1

// 计算新右移元素的下标

// 把一轮右移中最后一个元素放到合适位置

num++;

start++; // 起点增1，若num<n则开始下一轮右移。 }

} // 算法结束

数据结构与算法课后习题解答

算法二

算法思想：先将左面n-k个元素逆置，接着将右面k个元素逆置，最后再将这n个元素逆置。

void rightrotate(ElemType A[],int n,k)

// 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。

{ ElemType temp;

for(i=0;i<(n-k)/2;i++) //左面n-k个元素逆置

{temp=A[i]; A[i]=A[n-k-1-i]; A[n-k-1-i]=temp; }

for(i=1;i<=k;i++) //右面k个元素逆置

{temp=A[n-k-i]; A[n-k-i]=A[n-i]; A[n-i]=temp; }

for(i=0;i<n/2;i++) //全部n个元素逆置

{temp=A[i]; A[i]=A[n-1-i]; A[n-1-i]=temp; }

} // 算法结束 2·5

void

// L递增有序，本算法将x插入到链表中，并保持链表的递增有序。

，*s;

// p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱

s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出

s->data=x;

while (p && p->data<=x) {pre=p; p=p->next;} // 查找插入位置

pre->next=s; s->next=p; // 插入元素

数据结构与算法课后习题解答

} // 算法结束 2·6

void invert(linklist *L)

// 本算法将带头结点的单链表L逆置。

//点的链表中。

{ linklist *p=L->next,*s;

// p为工作指针，指向当前元素，s为p的后继指针

L->next=null;//

while (p)

{s=p->next; //

p->next=L->next; // 逆置

L->next=p;

p=s; }

} 2·7

(1) int length1(linklist *L)

// 本算法计算带头结点的单链表L的长度

{ linklist *p=L->next; int i=0;

数据结构与算法课后习题解答

// p为工作指针，指向当前元素，i 表示链表的长度

while (p)

{ i++; p=p->next; }

return(i);

} // 算法结束

(2) int length1(node sa[MAXSIZE])

// 本算法计算静态链表s中元素的个数。

{ int p=sa[0].next, i=0;

// p为工作指针，指向当前元素，i 时链表结束

while (p！=-1)

{ i++; p=sa[p].next; }

return(i);

} // 算法结束 2·8

void

// C，利用原表空间。

{ linklist *pa=A->next,*pb=B->next,*C=A,*r;

// pa,pb为工作指针，分别指向A表和B表的当前元素，r为当前逆置

//元素的后继指针, 使逆置元素的表避免断开。

//算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。

数据结构与算法课后习题解答

C->next=null;//头结点摘下，指针域置空。算法中头指针C始终不变

while (pa && pb) // 两表均不空时作

if (pa->data<=pb->data) // 将A表中元素合并且逆置

{ r=pa->next; // 保留后继结点的指针

pa->next=C->next; // 逆置

C->next=pa;

pa=r; // 恢复待逆置结点的指针 }

else // 将B表中元素合并且逆置

{ r=pb->next; // 保留后继结点的指针

pb->next=C->next; // 逆置

C->next=pb;

pb=r; // }

// 以下语句，只执行一个

// 将A表中剩余元素逆置

// 保留后继结点的指针

// 逆置

C->next=pa;

pa=r; // 恢复待逆置结点的指针 }

while (pb) // 将B表中剩余元素逆置

数据结构与算法课后习题解答

{ r=pb->next; // 保留后继结点的指针

pb->next=C->next; // 逆置

C->next=pb;

pb=r; // 恢复待逆置结点的指针 }

free(B);//释放B表头结点

} // 算法结束 2·9

void deleteprior(linklist *L)

// 长度大于1*s 的前驱结点

{ linklist *p=s->next,*pre=s; // p

// pre的前驱

// 查找*s的前驱

pre->next=s;

free(p); //

} 2·10

void one_to_three(linklist *A,*B,*C)

// A是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法//将A表分成

// 三个带头结点的循环单链表A、B和C，分别含有字母、数字和其它符号的同一类字符，

数据结构与算法课后习题解答

利用原表空间。

{ linklist *p=A->next,r;

// p为工作指针，指向A表的当前元素，r为当前元素的后继指针,使表避免断开。

//算法思想是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。

B=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出

B->next=null; // 准备循环链表的头结点

C=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出

C->next=null; // 准备循环链表的头结点

while(p)

{ r=p->next; // 用以记住后继结点

if (p->data>=’a’&&p->data<=’z’||p->data>=’A’&& p-

{p-> next=A->next; A->next=p;} A表

else if (p->data>=’0’&&p-

// 将数字字符插入B 表

将其它符号插入C 表

p=r; 恢复后继结点的指针

} // 2·11

void locate(dlinklist *L)

// L是带头结点的按访问频度递减的双向链表，本算法先查找数据x,

// 查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。

数据结构与算法课后习题解答

{ linklist *p=L->next,*q;

//p为工作指针，指向L表的当前元素，q为p的前驱，用于查找插入位置。

while (p && p->data !=x) p=p->next; // 查找值为x的结点。

if (!p) return (“不存在值为x的结点”);

else { p->freq++; // 令元素值为x的结点的freq域加1 。

p->next->prir=p->prior; // 将p结点从链表上摘下。

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

q=p->prior; // 以下查找p结点的插入位置

while (q !=L && q->freq<p-freq) q=q->prior;

p->next=q->next; q->next->prior=p;// 将p

p->prior=q; q->next=p；

}

} // 算法结束

第三章 )

//

//

3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 1

1 2 4 3 2 1 4 3 3 2 4 1

1 3 2 4 2 3 1 4 3 4 2 1

1 3 4 2 2 3 4 1

数据结构与算法课后习题解答

1 4 3 2 2 4 3 1

设入栈序列元素数为n，则可能的出栈序列数为C2nn=(1/n+1)*(2n!/(n!)2)

3.2 证明：由j<k和pj<pk 说明pj在pk之前出栈，即在k未进栈之前pj已出栈，之后k进栈，然后pk出栈；由j<k和pj>pk 说明pj在pk之后出栈，即pj被pk 压在下面，后进先出。由以上两条，不可能存在i<j<k使pj<pk<pi。也就是说，若有1，2，3顺序入栈，不可能有3，1，2的出栈序列。

3.3 void sympthy(linklist *head, stack *s)

//判断长为n的字符串是否中心对称

{ int i=1; linklist *p=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()；

else printf()

} // 算法结束 3.4

//

（init s;//初始化栈s

scanf(“%c”,&ch);

while (ch!=’#’) //’#’是表达式输入结束符号

switch (ch)

, case ’(’: push(s,ch); break;

数据结构与算法课后习题解答

case ’)’: if (empty(s)) {printf(“括号不配对”); exit(0);}

pop(s); }

if (!empty(s)) printf(“括号不配对”);

else printf(“括号配对”);

} // 算法结束 3.5

typedef struct // 两栈共享一向量空间

{ ElemType v[m]; // 栈可用空间0—m-1

int top[2] // 栈顶指针

}twostack;

int

// ,i0或1，表示两个栈，x是进栈元素，

//

栈满

else {switch (i)

{case 0: s->v[++(s->top)]=x; break;

case 1: s->v[--(s->top)]=x; break;

default: printf(“栈编号输入错误”); return(0);

}

数据结构与算法课后习题解答

return(1); // 入栈成功

}

} // 算法结束

ElemType pop(twostack *s,int i)

// 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作

{ ElemType x;

if (i!=0 && i!=1) return(0);// 栈编号错误

else {switch (i)

{case 0: if(s->top[0]==-1) return(0);//栈空

else x=s->v[s->top--];break;

case 1: if(s->top[1]==m) return(0);//

else x=s->v[s->top++]; break;

default: printf();return(0);

}

// 退栈成功

ElemType top (twostack *s,int i)

// 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作

{ ElemType x;

switch (i)

数据结构与算法课后习题解答

{case 0: if(s->top[0]==-1) return(0);//栈空

else x=s->v[s->top]; break;

case 1: if(s->top[1]==m) return(0);//栈空

else x=s->v[s->top]; break;

default: printf(“栈编号输入错误”);return(0);

}

return(x); // 取栈顶元素成功

} // 算法结束 3．6

void Ackerman(int m,int n)

// Ackerman 函数的递归算法

{ if (m==0) return(n+1);

} //

3．7

(1) linklist *init(linklist *q)

// q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空

{ q=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出

q->next=q;

数据结构与算法课后习题解答

return (q);

} // 算法结束

(2) linklist *enqueue(linklist *q，ElemType x)

// q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队

{ s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出

s->next=q->next; // 将元素结点s入队列

q->next=s;

q=s; // 修改队尾指针

return (q);

} // 算法结束

(3) linklist *delqueue(linklist *q)

//q

指向出队元素

// 若队列中只一个元素，置空队列

修改队头元素指针

// 释放出队结点 }

return (q);

} // 算法结束。算法并未返回出队元素 3.8

数据结构与算法课后习题解答

typedef struct

{ElemType data[m];// 循环队列占m个存储单元

int front,rear; // front和rear为队头元素和队尾元素的指针

// 约定front指向队头元素的前一位置，rear指向队尾元素

}sequeue;

int queuelength(sequeue *cq)

// cq为循环队列，本算法计算其长度

{ return (cq->rear - cq->front + m) % m;

} // 算法结束 3.9

typedef struct

{ElemType sequ[m];//

int rear,quelen; ,quelen为元素个数

}sequeue;

{ return (cq->quelen==0 ? 1: 0);

} // 算法结束

(2) sequeue *enqueue(sequeue *cq，ElemType x)

// cq是如上定义的循环队列，本算法将元素x入队

{if (cq->quelen==m) return(0); // 队满

数据结构与算法课后习题解答

else { cq->rear=(cq->rear+1) % m; // 计算插入元素位置

cq->sequ[cq->rear]=x; // 将元素x入队列

cq->quelen++; // 修改队列长度

}

return (cq);

} // 算法结束

ElemType delqueue(sequeue *cq)

// cq

{if (cq->quelen==0) return(0); // 队空

else { int front=(cq->rear - cq->quelen + 1+m) % m;//

cq->quelen--; //

return (cq->sequ[front]); //

}

} // 算法结束

参考答案)

在以下习题解答中，假定使用如下类型定义：

#define MAXSIZE 1024

typedef struct

{ char data[MAXSIZE];

数据结构与算法课后习题解答

int curlen; // curlen表示终端结点在向量中的位置

}seqstring;

typedef struct node

{char data;

struct node *next ；

}linkstring;

4.2 int index(string s,t)

//s,t是字符串，本算法求子串t在主串ss串中包含t串，返回其

//第一个字符在s中的位置，否则返回0

{m=length(s); n=length(t); i=1;

while(i<=m-n+1)

else

return(i);//模式匹配成功

else return(0);//s串中无子串t

}//算法index结束

4.3 设A=” ”, B=”mule”, C=”old”, D=”my” 则：

（a） （a） strcat（A,B）=”mule”

（b） （b） strcat(B,A)=”mule”

数据结构与算法课后习题解答

（c） （c） strcat(strcat(D,C),B)=”myoldmule”

（d） （d） substr(B,3,2)=”le”

（e） （e） substr(C,1,0)=” ”

（f） （f） strlen(A)=0

（g） （g） strlen(D)=2

（h） （h） index(B,D)=0

（i） （i） index(C,”d”)=3

（j） （j） insert(D,2,C)=”moldy”

（k） （k） insert(B,1,A)=”mule”

（l） （l） delete(B,2,2)=”me”

（m） （m） delete(B,2,0)=”mule

（n） （n） ””ok”

4.4 将S=“（xyz）*”转为”

char search(linkstring *X, linkstring *Y)

// X和Y是用带头结点的结点大小为1的单链表表示的串，本算法查找X中第一个不在Y中出现的字符。算法思想是先从X中取出一个字符，到Y中去查找，如找到，则在X中取下一字符，重复以上过程；若没找到，则该字符为所求

{ linkstring *p, *q,*pre; // p,q为工作指针，pre控制循环

数据结构与算法课后习题解答

p=X->next; q=Y->next; pre=p;

while (p && q)

{ ch=p->data; // 取X中的字符

while (q && q->data!=ch) q=q->next; // 和Y中字符比较

if (!q) return(ch); // 找到Y中没有的字符

else { pre=p->next; // 上一字符在Y中存在，

p=pre; // 取X中下一字符。

q=Y->next; // 再从Y

} }

return(null); // X

}// 算法结束 4.6

int

// S和TS串大于T串，返回1；若0；否则返回-1

while (s->ch*i+!=’\0’ && t->ch*i+!=’\0’)

if (s->ch[i]>t->ch[i]) return(1);

else if (s->ch[i]<t->ch[i]) return(-1);

else i++; // 比较下一字符

本文来源：https://www.bwwdw.com/article/k8pe.html