以上两条，不可能存在i 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 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] 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个元素。以行序为主（即行优先）时，先改 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构——用C语言描述》+课后题答案(2)在线全文阅读。
相关推荐：