当我超链接到老妈的肚子里

http://www.zydg.net/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 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 , 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）链式存储结构（单链表） 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=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 (numnext, *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->freqprior; 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 证明：由jpk 说明pj在pk之后出栈，即pj被pk 压在下面，后进先出。由以上两条，不可能存在inext; 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 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=replace(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]ch[i]) return(-1); 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(aijk)=LOC(ac1c2c3)+[(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)]*l 推广到n维数组！！（下界和上界）为（ci，di），其中1<=i<=n.则：其数据元素的存储位置为： LOC（aj1j2….jn）=LOC（ac1c2…cn）+[（d2-c2+1） …（dn-cn+1）(j1-c1)+(d3-c3+1) …（dn-cn+1） n (j2-c2)+…+(dn-cn+1)(jn-1-cn-1)+(jn-cn)]*l=LOC(ac1c2c3)+ ∑αi(ji-ci) i=1 n 其中αi∏（dk-ck+1）（1<=i<=n） k=i+1 若从c开始，c数组下标从0开始，各维长度为bi（1<=i<=n）则： LOC（aj1j2…jn）=LOC(a00…0)+(b2* b3*…* bn*j1+ b3* …* bn*+ j2…+ bn* jn-1+ jn)*l n =LOC(a00…0)+ ∑αiji 其中：αi=l，αi-1=bi*αi ，1=a[i][kk]) kk++; if(kk>=m)printf(“马鞍点 i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j]); } // END OF for jj } // END OF for i 最坏时间复杂度为O(m*(n+n*m)). (最坏时所有元素相同，都是马鞍点) 解法2: 若矩阵中元素值互不相同,则用一维数组row记下各行最小值，再用一维数组col记下各列最大值， 相等者为马鞍点。 for (i=0;icol[j]) col[j]=a[i][j]; // 重新确定最大值 } for (i=0;iA[max[j]][j]) max[j]=i; // 重新确定第j列最大值的行号 if (A[i][j]分析

定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析