《唐策善数据结构答案-用C语言描述原版》由会员分享，可在线阅读，更多相关《唐策善数据结构答案-用C语言描述原版（29页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表(参考答案)2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是 la，往往简称为“链表 la”。头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品） ，其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。23 设线性表存放在向量 A的前 elenum 个分量中，且递
2、增有序。协议算法将 X 插入适当位置、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; / 插入元素 / 算法结束24 void rightrotate(ElemType A,int n,k)/ 以向量作存储结构，本算法将向量中的 n 个元素循环右移 k位，且只用一个辅助空间。 int num=0; / 计数，最终应等于 n int start=
3、0; / 记录开始位置（下标） while (numnext, *pre=L，*s;/ p 为工作指针，指向当前元素，pre 为前驱指针，指向当前元素的前驱 s=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出s-data=x;while (p & p-datanext; / 查找插入位置 pre-next=s; s-next=p; / 插入元素 / 算法结束 26void invert(linklist *L)/ 本算法将带头结点的单链表 L 逆置。 /算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以 L 为头结点的链表中。
4、 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 指向下个待逆置结点 / 算法结束 27(1) int length1(linklist *L)/ 本算法计算带头结点的单链表 L 的长度 linklist *p=L-next; int i=0;/ p 为工作指针，指向当前元素，i 表示链表的长度 while (p) i+;
5、 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.next; return(i); / 算法结束 28void union_invert(linklist *A,*B,*C)/ A 和 B 是两个带头结点的递增有序的单链表，本算法将两表合并成 / 一个带头结点的递减有序单链表 C，利用原表空间。 linklist
6、*pa=A-next,*pb=B-next,*C=A,*r;/ pa,pb 为工作指针，分别指向 A 表和 B 表的当前元素，r 为当前逆置/元素的后继指针, 使逆置元素的表避免断开。 /算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。 C-next=null;/头结点摘下，指针域置空。算法中头指针 C 始终不变 while (pa & pb) / 两表均不空时作 if (pa-datadata) / 将 A 表中元素合并且逆置 r=pa-next; / 保留后继结点的指针 pa-next=C-next; / 逆置 C-next=pa; pa=r; / 恢复待逆置结点的指针
7、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; / 逆置
8、 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) pre=p; p=p-next; / 查找*s 的前驱 pre-next=s;free(p); / 删除元素 / 算法结束 210void one_to_three
9、(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=
10、(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出C-next=null; / 准备循环链表的头结点 while(p) r=p-next; / 用以记住后继结点 if (p-data=a&p-datadata=A& p-data next=A-next; A-next=p; / 将字母字符插入 A 表 else if (p-data=0&p-datanext=B-next; B-next=p; / 将数字字符插入 B 表 else p-next=C-next; C-next=p;/ 将其它符号插入 C 表 p=r; / 恢复后继结点的指针 /whil
11、e / 算法结束 211void 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-pr
12、ir=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.3 void sympthy(linklist *head, stack *s)/判断长为 n 的字符串是否中心对称 int i=1; linklist *p=head-next;while (idata); p=p-nex
13、t; if (n % 2 !=0) p=p-next;/ 奇数个结点时跳过中心结点 while (p & p-data=pop(s) p=p-next;if (p=null) printf(“链表中心对称”)；else printf(“链表不是中心对称”)； / 算法结束 3.4int match()/从键盘读入算术表达式，本算法判断圆括号是否正确配对（init s;/初始化栈 sscanf(“%c”,&ch);while (ch!=#) /#是表达式输入结束符号switch (ch) case (: push(s,ch); break;case ): if (empty(s) printf(
14、“括号不配对”); exit(0);pop(s);if (!empty(s) printf(“括号不配对”); else printf(“括号配对”); / 算法结束 3.5typedef struct / 两栈共享一向量空间 ElemType vm; / 栈可用空间 0m-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: printf(“栈编号输入错误”); return(0);return(1); / 入栈成功 / 算法结束 ElemTy
