1、数据结构课后习题参考答案 第一章 绪论 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 99 12 92 100 20 101 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 , n
2、3/2 , (3/2)n , nlog2n , 2 n , n! , n n 第二章 线性表 (参考答案 ) 在以下习题解答中，假定使用如下类型定义： （ 1）顺序存储结构： #define MAXSIZE 1024 typedef int ElemType;/ 实际上， ElemType 可以是任意类型 typedef struct ElemType dataMAXSIZE; int last; / last 表示终端结点在向量中的位置 sequenlist; （ 2）链式存储结构（单链表） typedef struct node ElemType data; struct node *ne
3、xt； linklist; （ 3）链式存储结构（双链表） typedef struct node ElemType data; struct node *prior,*next； dlinklist; （ 4）静态链表 typedef struct ElemType data; int next; node; node saMAXSIZE; 2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是 la，往往简称为“链表 la”。 头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）
4、之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品 ），其指针域指向头结点。这样在插入和删除中头结点不变。 开始结点：即上面所讲第一个元素的结点。 2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。 23 void insert(ElemType A,int elenum,ElemType x) / 向量 A 目前有 elenum 个元素，且递增有序，本算法将 x 插入到向量 A 中，并保持向量的递增有序。 int i=0,j; while (i=i;j-) Aj+1=Aj;/ 向后移动元素 Ai=x; / 插入元素 / 算法结
5、束 24 void rightrotate(ElemType A,int n,k) / 以向量作存储结构，本算法将向量中的 n 个元素循环右移 k 位，且只用一个辅助空间。 int num=0; / 计数，最终应等于 n int start=0; / 记录开始位置（下标） while (numnext, *pre=L， *s; / p 为工作指针，指向当前元素， pre 为前驱指针，指向当前元素的前驱 s=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出 s-data=x; while (p / 查找插入位置 pre-next=s; s-next=
6、p; / 插入元素 / 算法结束 26 void invert(linklist *L) / 本算法将带头结点的单链表 L 逆置。 /算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次 前插入 以 L 为头结点的 链表中。 linklist *p=L-next,*s; / p 为工作指针，指向当前元素， s 为 p 的后继指针 L-next=null;/头结点摘下，指针域置空。算法中头指针 L 始终不变 while (p) s=p-next; / 保留后继结点的指针 p-next=L-next; / 逆置 L-next=p; p=s; / 将 p 指向下个待逆置结点 / 算法结束
7、27 (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 saMAXSIZE) / 本算法计算静态链表 s 中元素的个数。 int p=sa0.next, i=0; / p 为工作指针，指向当前元素， i 表示元 素的个数，静态链指针等于 -1 时链表结束 while (p！ =-1) i+; p=sap.n
8、ext; return(i); / 算法结束 28 void union_invert(linklist *A,*B,*C) / A 和 B 是两个带头结点的递增有序的单链表，本算法将两表合并成 / 一个带头结点的递减有序单链表 C，利用原表空间。 linklist *pa=A-next,*pb=B-next,*C=A,*r; / pa,pb为工作指针，分别指向 A 表和 B 表的当前元素， r 为当前逆置 /元素的后继指针 , 使逆置元素的表避免断开。 /算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。 C-next=null;/头结点摘下，指针域置空。算法中头指针 C 始
9、终不变 while (pa / 保留后继结点的指针 pa-next=C-next; / 逆置 C-next=pa; pa=r; / 恢复待逆置结点的指针 else / 将 B 表中元素合并且逆置 r=pb-next; / 保留后继结点的指针 pb-next=C-next; / 逆置 C-next=pb; pb=r; / 恢复待逆置结点的指针 / 以下 while (pa)和 while (pb)语句，只执行一个 while (pa) / 将 A 表中剩余元素逆置 r=pa-next; / 保留后继结点的指针 pa-next=C-next; / 逆置 C-next=pa; pa=r; / 恢复待
10、逆置结点的指针 while (pb) / 将 B 表中剩余元素逆置 r=pb-next; / 保留后继结点的指针 pb-next=C-next; / 逆置 C-next=pb; pb=r; / 恢复待逆置结点的指针 free(B);/释放 B表头结点 / 算法结束 29 void deleteprior(linklist *L) / 长度大于 1 的单循环链表，既无头结点，也无头指针，本算法删除 *s 的前驱结点 linklist *p=s-next,*pre=s; / p 为工作指针， 指向当前元素， / pre 为前驱指针，指向当前元素 *p 的前驱 while (p-next!=s) p
11、re=p; p=p-next; / 查找 *s 的前驱 pre-next=s; free(p); / 删除元素 / 算法结束 210 void one_to_three(linklist *A,*B,*C) / A 是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法 /将 A 表分成 / 三个带头结点的循环单链表 A、 B 和 C，分别含有字母 、数字和其它符号的同一类字符，利用原表空间。 linklist *p=A-next,r; / p 为工作指针，指向 A 表的当前元素， r 为当前元素的后继指针 ,使表避免断开。 /算法思想是取出当前元素，根据是字母、数字或其
12、它符号，分别插入相应表中。 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 A-next=p; / 将字母字符插入 A 表 else if (p-data=0 B-next=p; / 将数字字符插入 B 表 else p-next=C-next; C-nex
13、t=p;/ 将其它符号插入 C 表 p=r; / 恢复后继结点的指针 /while / 算法结束 211 void locate(dlinklist *L) / L 是带头结点的按访问频度递减的双向链表，本算法先查找数据 x, / 查找成功时结点的访问频度域增 1，最后将该结 点按频度递减插入链表中适当位置。 linklist *p=L-next,*q; /p 为工作指针，指向 L 表的当前元素， q 为 p 的前驱，用于查找插入位置。 while (p / 查找值为 x 的结点。 if (!p) return (“ 不存在值为 x 的结点 ”); else p-freq+; / 令元素值为
14、x 的结点的 freq 域加 1 。 p-next-prir=p-prior; / 将 p 结点从链表上摘下。 p-prior-next=p-next; q=p-prior; / 以下查找 p 结点的插入位置 while (q !=L 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
15、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 证明：由 jpk 说明 pj在 pk之后出栈，即 pj被 pk 压在下面，后进先出。由以上两条，不可能存在 inext; while (idata); p=p-next; if (n % 2 !=0) p=p-next;/ 奇数个结点时跳过中心结点 while (p if (p=null) printf(“ 链表中心对
16、称 ”) ； else printf(“ 链表不是中心对称 ”) ； / 算法结束 3.4 int match() /从键盘读入算术表达式，本算法判断圆括号是否正确配对 （ init s;/初始化栈 s scanf(“%c”, while (ch!=#) /# 是表达式输入结束符号 switch (ch) case (: push(s,ch); break; case ): if (empty(s) printf(“ 括号不配对 ”); exit(0); pop(s); if (!empty(s) printf(“ 括号不配对 ”); else printf(“ 括号配对 ”); / 算法结束
17、 3.5 typedef struct / 两栈共享一向量空间 ElemType vm; / 栈可用空间 0 m-1 int top2 / 栈顶指针 twostack; int push(twostack *s,int i, ElemType x) / 两栈共享向量空间 ,i 是 0 或 1，表示两个栈， x 是进栈元素， / 本算法是入栈操作 if (abs(s-top0 - s-top1)=1) return(0);/ 栈满 else switch (i) case 0: s-v+(s-top)=x; break; case 1: s-v-(s-top)=x; break; default
18、: printf(“ 栈编号输入错误 ”); return(0); return(1); / 入栈成功 / 算法结束 ElemType pop(twostack *s,int i) / 两栈共享向量空间 ,i 是 0 或 1，表示两个栈，本算法是退栈操作 ElemType x; if (i!=0 / 栈编号错误 else switch (i) case 0: if(s-top0=-1) return(0);/栈空 else x=s-vs-top-;break; case 1: if(s-top1=m) return(0);/栈空 else x=s-vs-top+; break; default
19、: printf(“ 栈编号输入错误 ”);return(0); return(x); / 退栈成功 / 算法结束 ElemType top (twostack *s,int i) / 两栈共享向量空间 ,i 是 0 或 1，表示两个栈，本算法是取栈顶元素操作 ElemType x; switch (i) case 0: if(s-top0=-1) return(0);/栈空 else x=s-vs-top; break; case 1: if(s-top1=m) return(0);/栈空 else x=s-vs-top; break; default: printf(“ 栈编号输入错误 ”
20、);return(0); return(x); / 取栈顶元素成功 / 算法结束 3 6 void Ackerman(int m,int n) / Ackerman 函数的递归算法 if (m=0) return(n+1); else if (m!=0 else return(Ackerman(m-1,Ackerman(m,n-1) / 算法结束 3 7 (1) linklist *init(linklist *q) / q 是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空 q=(linklist *)malloc(sizeof(linklist);/申请空间，不判断空间溢出 q-n
21、ext=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 是以带头结点的循环链表表示的队列的尾指针， 这是出队算
22、法 if (q=q-next) return (null); / 判断队列是否为空 else linklist *s=q-next-next; / s 指向出队元素 if (s=q) q=q-next; / 若队列中只一个元素，置空队列 else q-next-next=s-next;/ 修改队头元素指针 free (s); / 释放出队结点 return (q); / 算法结束。算法并未 返回出队元素 3.8 typedef struct ElemType datam;/ 循环队列占 m 个存储单元 int front,rear; / front 和 rear 为队头元素和队尾元素的指针 /
23、 约定 front 指向队头元素的前一位置， rear 指向队尾元素 sequeue; int queuelength(sequeue *cq) / cq 为循环队列，本算法计算其长度 return (cq-rear - cq-front + m) % m; / 算法结束 3.9 typedef struct ElemType sequm;/ 循环队列占 m 个存储单元 int rear,quelen; / rear 指向队尾元素 ,quelen 为元素个数 sequeue; (1) int empty(sequeue *cq) / cq 为循环队列，本算法判断队列是否为空 return (c
24、q-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-sequcq-rear=x; / 将元素 x 入队列 cq-quelen+; / 修改队列长度 return (cq); / 算法结束 ElemType delqueue(sequeue *cq) / cq 是以如上定义的循环队列，本算法是出队
25、算法，且返回出队元素 if (cq-quelen=0) return(0); / 队空 else int front=(cq-rear - cq-quelen + 1+m) % m;/ 出队元素位置 cq-quelen-; / 修改队列长度 return (cq-sequfront); / 返回队头元 素 / 算法结束 第四章 串 (参考答案 ) 在以下习题解答中，假定使用如下类型定义： #define MAXSIZE 1024 typedef struct char dataMAXSIZE; int curlen; / curlen 表示终端结点在向量中的位置 seqstring; type
26、def struct node char data; struct node *next ； linkstring; 4.2 int index(string s,t) /s,t 是字符串，本算法求子串 t 在主串 s 中的第一次出现，若 s 串中包含 t 串，返回其 /第一个字符在 s 中的位置，否则返回 0 m=length(s); n=length(t); i=1; while(inext; q=Y-next; pre=p; while (p / 取 X 中的字符 while (q / 和 Y 中字符比较 if (!q) return(ch); / 找到 Y 中没有的字符 else pr
27、e=p-next; / 上一字符在 Y 中存在， p=pre; / 取 X 中下一字符。 q=Y-next; / 再从 Y 的第一个字符开始比较 return(null); / X 中字符在 Y 中均存在 / 算法结束 4.6 int strcmp(seqstring *S, seqstring *T) / S 和 T 是指向两个顺序串的指针，本 算法比较两个串的大小，若 S 串大于 T 串，返回 1；若 S 串等于 T 串，返回 0；否则返回 -1 int i=0; while (s-chi!= 0 else if (s-chichi) return(-1); else i+; / 比较下一
28、字符 if (s-chi!= 0 else if (s-chi= 0 else return(0); / 算法结束 4.7 linkstring *invert(linkstring *S, linkstring *T) / S 和 T 是用带头结点的结点大小为 1 的单链表表示的串， S 是主串， T 是 / 模式串。本算法是先模式匹配，查找 T 在 S 中的第一次出现。如模式匹 / 配成功，则将 S 中的子串（ T 串）逆置。 linkstring *pre,*sp, *tp; pre=S; / pre 是前驱指针，指向 S 中与 T 匹配时， T 中的前驱 sp=S-next; tp=T
29、-next;/sp 和 tp 分别是 S 和 T 串上的工作指针 while (sp tp=tp-next; else / 失配时主串回溯到下一个字符，子串再以第一个字符开始 pre=pre-next; sp=pre-next; tp=T-next; if (tp!=null) return (null); / 匹配失败，没有逆置 else / 以下是 T 串逆置 tp=pre-next; / tp 是逆置的工作指针，现在指向待逆置的第一个字符 pre-next=sp; / 将 S 中与 T 串匹配时的前驱指向匹配后的后继 while (tp!=sp) r=tp-next; tp-next=pre-next; pre-next=tp; tp=r / 算法结束 第五章 多维数组和广义表（参考 答案） 5.1 A2323 A0000 , A0001 , A0002 A0010 , A0011 , A0012 A0100 , A0101 , A0102 A0110 , A0111 , A0112 A0200 , A0201 , A0202
