https://www.wendangku.net/doc/675457777.html,/computer/book/read/data-structure/h971111102.html 习题解答(唐策善版)(其他版本在上面)
第一章绪论(参考答案)
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 9
2 100
2 9
3 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 ,n3/2, (3/2)n , n log2n , 2 n ,n! , n n
第二章线性表(参考答案)
在以下习题解答中,假定使用如下类型定义:
(1)顺序存储结构:
#define MAXSIZE 1024
typedef int ElemType;// 实际上,ElemType可以是任意类型
typedef struct
{ ElemType data[MAXSIZE];
int last; // last表示终端结点在向量中的位置
}sequenlist;
(2)链式存储结构(单链表)
typedef struct node
{ElemType data;
struct node *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 insert(ElemType A[],int elenum,ElemType x)
// 向量A目前有elenum个元素,且递增有序,本算法将x插入到向量A中,并保持向量的递增有序。
{ int i=0,j;
while (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 { temp=A[start]; //暂存起点元素值,temp与向量中元素类型相同 empty=start; //保存空位置下标 next=(start-K+n) %n; // 计算下一右移元素的下标 while (next !=start) { A[empty]=A[next];// 右移 num++; // 右移元素数加1 empty=next; next=(next-K+n) %n; // 计算新右移元素的下标 } A[empty]=temp; // 把一轮右移中最后一个元素放到合适位置 num++; start++; // 起点增1,若num } } // 算法结束 算法二 算法思想:先将左面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 {temp=A[i]; A[i]=A[n-1-i]; A[n-1-i]=temp; } } // 算法结束 2·5 void insert(linklist *L,ElemType x) // 带头结点的单链表L递增有序,本算法将x插入到链表中,并保持链表的递增有序。{ linklist *p=L->next, *pre=L,*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逆置。 //算法思想是先将头结点从表上摘下,然后从第一个元素结点开始,依次前插入以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指向下个待逆置结点 } } // 算法结束 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 表示元素的个数,静态链指针等于-1时链表结束 while (p!=-1) { i++; p=sa[p].next; } return(i); } // 算法结束 2·8 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始终不变 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; // 恢复待逆置结点的指针 } // 以下while (pa)和while (pb)语句,只执行一个 while (pa) // 将A表中剩余元素逆置 { r=pa->next; // 保留后继结点的指针 pa->next=C->next; // 逆置 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为前驱指针,指向当前元素*p的前驱 while (p->next!=s) {pre=p; p=p->next;} // 查找*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->data<=’Z’) {p-> next=A->next; A->next=p;} // 将字母字符插入A表 else if (p->data>=’0’&&p->data<=’9’) {p->next=B->next; B->next=p;} // 将数字字符插入B 表 else {p->next=C->next; C->next=p;}// 将其它符号插入C 表p=r; // 恢复后继结点的指针 }//while } // 算法结束 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->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,则可能的出栈序列数为C2n n=(1/n+1)*(2n!/(n!)2) 3.2 证明:由j 然后p k 出栈;由j j >p k 说明p j 在p k 之后出栈,即p j 被p k 压在下面,后进先出。由 以上两条,不可能存在i j k i 。也就是说,若有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(“链表中心对称”); e lse printf(“链表不是中心对称”); } // 算法结束 3.4 int match() //从键盘读入算术表达式,本算法判断圆括号是否正确配对 (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 push(twostack *s,int i, ElemType x) // 两栈共享向量空间,i是0或1,表示两个栈,x是进栈元素, // 本算法是入栈操作 { if (abs(s->top[0] - s->top[1])==1) return(0);// 栈满 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); } return(x); // 退栈成功 } } // 算法结束 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); else if (m!=0 && n==0) return(Ackerman(m-1,1); else return(Ackerman(m-1,Ackerman(m,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是以带头结点的循环链表表示的队列的尾指针,这是出队算法 { 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 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];// 循环队列占m个存储单元 int rear,quelen; // rear指向队尾元素,quelen为元素个数 }sequeue; (1) int empty(sequeue *cq) // cq为循环队列,本算法判断队列是否为空 { 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在主串s中的第一次出现,若s串中包含t串,返回其//第一个字符在s中的位置,否则返回0 {m=length(s); n=length(t); i=1; while(i<=m-n+1) if(strcmp(substr(s,i,n),t)==0) break; else i++; if(i<=m-n+1) 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)replace(C,2,2,”k”)=”ok” 4.4 将S=“(xyz)*”转为T=“(x+z)*y” S=concat(S, substr(S,3,1)) // ”(xyz)*y” S=rep lace(S,3,1,”+”) // ”(x+z)*y” 4.5 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中字符在Y中均存在 }// 算法结束 4.6 int strcmp(seqstring *S, seqstring *T) // S和T是指向两个顺序串的指针,本算法比较两个串的大小,若S串大于T串,返回1;若S串等于T串,返回0;否则返回-1 {int i=0; while (s->ch[i]!=’\0’ && t->ch[i]!=’\0’) if (s->ch[i]>t->ch[i]) return(1); else if (s->ch[i] else i++; // 比较下一字符 if (s->ch[i]!=’\0’&& t->ch[i]==0) return(1); else if (s->ch[i]==’\0’&& t->ch[i]!=0) return(-1); 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->next;//sp 和tp分别是S和T串上的工作指针 while (sp && tp) if (sp->data==tp->data) // 相等时后移指针 {sp=sp->next; 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 A[2][3][2][3] A0000, A0001, A0002 A0010, A0011, A0012 A0100, A0101, A0102 A0110, A0111, A0112 A0200, A0201, A0202 A0210, A0211, A0212 将第一维的0变为1后,可列出另外18个元素。以行序为主(即行优先)时,先改 变右边的下标,从右到左进行。 5.2 设各维上下号为c1…d1,c2…d2,c3…d3,每个元素占l个单元。 LOC(a ijk)=LOC(a c1c2c3)+[(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)]*l 推广到n维数组!!(下界和上界)为(ci,di),其中1<=i<=n.则:其数据元素的存储位置为: LOC(a j1j2….jn)=LOC(a c1c2…cn)+[(d2-c2+1)…(d n-c n+1)(j1-c1)+(d3-c3+1) …(d n-c n+1) n (j2-c2)+…+(d n-c n+1)(j n-1-c n-1)+(j n-c n)]*l=LOC(a c1c2c3)+ ∑αi(j i-c i) i=1 n 其中α i ∏(d k -c k +1)(1<=i<=n) k=i+1 若从c开始,c数组下标从0开始,各维长度为b i(1<=i<=n)则: LOC(a j1j2…jn)=LOC(a00…0)+(b2* b3*…* b n*j1+ b3* …* b n*+ j2…+ b n* j n-1+ j n)*l n =LOC(a00…0)+ ∑αi j i其中:αi=l,αi-1=b i*αi,1 5.3 (1) k=2*i+j ( 0<=k<3n-2 ) (2) i=(k+1)/3 ( 0<=k<3n-2 ) j=k-2*i 5.4 void saddlepoint(int a[m][n]); // a是m行n列的二维数组,本算法求所有马鞍点 // b是一维数组,存放一行中可能的马鞍点的列值,k记相等值个数 // c是一维数组,存放某列可能马鞍点的行值,kk记相等值个数