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=(1n+1)*(2n!(n!)2) 3.2 证明：由j 3.3 void sympthy(linklist *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) 6 两栈共享向量空间,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指向出队元素 7 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 8 {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） （） 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); 9 else if (s->ch[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) 10