唐策善数据结构答案-用C语言描述原版

1、精选优质文档-倾情为你奉上第二章 线性表(参考答案) 2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链表la”。头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。开始结点：即上面所讲第一个元素的结点。2.2 只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。2·3 设线性表存放

2、在向量A的前elenum个分量中，且递增有序。协议算法将X插入适当位置、void insert(ElemType A,int elenum,ElemType x)/ 向量A目前有elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的递增有序。 int i=0,j; while (i<elenum && Ai<=x) i+; / 查找插入位置 for (j= elenum-1;j>=i;j-) Aj+1=Aj;/ 向后移动元素 Ai=x; / 插入元素 / 算法结束 2·4 void rightrotate(ElemType

3、A,int n,k)/ 以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。 int num=0; / 计数，最终应等于n int start=0; / 记录开始位置（下标） while (num<n) temp=Astart; /暂存起点元素值，temp与向量中元素类型相同 empty=start; /保存空位置下标 next=(start-K+n) %n; / 计算下一右移元素的下标 while (next !=start) Aempty=Anext;/ 右移 num+; / 右移元素数加1 empty=next; next=(next-K+n) %n; /

4、计算新右移元素的下标 Aempty=temp; / 把一轮右移中最后一个元素放到合适位置num+;start+; / 起点增1，若num<n则开始下一轮右移。 / 算法结束 2·5void insert(linklist *L,ElemType x)/ 带头结点的单链表L递增有序，本算法将x插入到链表中，并保持链表的递增有序。 linklist *p=L->next, *pre=L，*s;/ p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱 s=(linklist *)malloc(sizeof(linklist);/申请空间，不判断溢出s->dat

5、a=x;while (p && p->data<=x) pre=p; p=p->next; / 查找插入位置 pre->next=s; s->next=p; / 插入元素 / 算法结束  2·6void invert(linklist *L)/ 本算法将带头结点的单链表L逆置。 /算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以L为头结点的链表中。 linklist *p=L->next,*s;/ p为工作指针，指向当前元素，s为p的后继指针 L->next=null;/头结点摘下，指针域置空。

6、算法中头指针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

7、 saMAXSIZE)/ 本算法计算静态链表s中元素的个数。 int p=sa0.next, i=0;/ p为工作指针，指向当前元素，i 表示元素的个数，静态链指针等于-1时链表结束while (p！=-1) i+; p=sap.next; return(i); / 算法结束  2·8void union_invert(linklist *A,*B,*C)/ A和B是两个带头结点的递增有序的单链表，本算法将两表合并成 / 一个带头结点的递减有序单链表C，利用原表空间。 linklist *pa=A->next,*pb=B->next,*C=A,*r;/ pa,p

8、b为工作指针，分别指向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; / 恢复待逆置结点的指针 e

9、lse / 将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; / 保留后

10、继结点的指针 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的前驱

11、 pre->next=s;free(p); / 删除元素 / 算法结束  2·10void one_to_three(linklist *A,*B,*C)/ A是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。本算法/将A表分成 / 三个带头结点的循环单链表A、B和C，分别含有字母、数字和其它符号的同一类字符，利用原表空间。 linklist *p=A->next,r;/ p为工作指针，指向A表的当前元素，r为当前元素的后继指针,使表避免断开。 /算法思想是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。 B=(linklist

12、*)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->

13、;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·11void locate(dlinklist *L)/ L是带头结点的按访问频度递减的双向链表，本算法先查找数据x,/ 查找成功时结点的访问频度域增1，最后将该结点按频

14、度递减插入链表中适当位置。 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; /

15、以下查找p结点的插入位置 while (q !=L && q->freq<p-freq) q=q->prior;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 (i<=n/2) / 前一半字符进栈

16、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.4int match()/从键盘读入算术表达式，本算法判断圆括号是否正确配对（init s;/初始化栈sscanf(“%c”,&ch);while (ch!=#) /#是表达式输入结束符号switch (ch)

17、 case (: push(s,ch); break;case ): if (empty(s) printf(“括号不配对”); 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是进栈元素，/

18、 本算法是入栈操作 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); / 入栈成功 / 算法结束 ElemType pop(twostack *s,int i)/ 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作 ElemType x;if (i!=0 &

19、;& i!=1) return(0);/ 栈编号错误 else switch (i)case 0: if(s->top0=-1) return(0);/栈空else x=s->vs->top-;break;case 1: if(s->top1=m) return(0);/栈空else x=s->vs->top+; break;default: printf(“栈编号输入错误”);return(0);return(x); / 退栈成功 / 算法结束  ElemType top (twostack *s,int i)/ 两栈共享向量空间,i是0

20、或1，表示两个栈，本算法是取栈顶元素操作 ElemType x;switch (i)case 0: if(s->top0=-1) return(0);/栈空else x=s->vs->top; break;case 1: if(s->top1=m) return(0);/栈空else x=s->vs->top; break;default: printf(“栈编号输入错误”);return(0);return(x); / 取栈顶元素成功 / 算法结束  36void Ackerman(int m,int n)/ Ackerman 函数的递归算法 i

21、f (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) / 算法结束  37(1) linklist *init(linklist *q)/ q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空 q=(linklist *)malloc(sizeof(linklist);/申请空间，不判断空间溢出q->next=q;return (q); / 算法结束 (2) linklist *enqueue(li

22、nklist *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

23、 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 structElemType datam;/ 循环队列占m个存储单元 int front,rear; / front和rear为队头元素和队尾元素的指针 / 约定front指向队头元素的前一位置，rear指

24、向队尾元素 sequeue; int queuelength(sequeue *cq)/ cq为循环队列，本算法计算其长度 return (cq->rear - cq->front + m) % m; / 算法结束  3.9 typedef structElemType sequm;/ 循环队列占m个存储单元 int rear,quelen; / rear指向队尾元素,quelen为元素个数sequeue;(1) int empty(sequeue *cq)/ cq为循环队列，本算法判断队列是否为空 return (cq->quelen=0 ? 1: 0); / 算

25、法结束 (2) sequeue *enqueue(sequeue *cq，ElemType x)/ cq是如上定义的循环队列，本算法将元素x入队if (cq->quelen=m) return(0); / 队满 else cq->rear=(cq->rear+1) % m; / 计算插入元素位置 cq->sequcq->rear=x; / 将元素x入队列 cq->quelen+; / 修改队列长度 return (cq); / 算法结束 ElemType delqueue(sequeue *cq)/ cq是以如上定义的循环队列，本算法是出队算法，且返回出队元

26、素 if (cq->quelen=0) return(0); / 队空 else int front=(cq->rear - cq->quelen + 1+m) % m;/ 出队元素位置 cq->quelen-; / 修改队列长度 return (cq->sequfront); / 返回队头元素 / 算法结束第四章 串 (参考答案) 4.2 用串的去其他运算构成子串的定位运算index。 int index(string s,t)/s,t是字符串，本算法求子串t在主串s中的第一次出现，若s串中包含t串，返回其/第一个字符在s中的位置，否则返回0m=len

27、gth(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.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)

28、/ 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 (!

29、q) return(ch); / 找到Y中没有的字符 else pre=p->next; / 上一字符在Y中存在，p=pre; / 取X中下一字符。 q=Y->next; / 再从Y的第一个字符开始比较return(null); / X中字符在Y中均存在 / 算法结束  4.6 是设计一算法，在顺序串上实现串的比较运算 strcmp(s,t)int strcmp(seqstring *S, seqstring *T)/ S和T是指向两个顺序串的指针，本算法比较两个串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否则返回-1 int i=0;while (s-&g

30、t;chi!=0 && t->chi!=0)if (s->chi>t->chi) return(1);else if (s->chi<t->chi) return(-1);else i+; / 比较下一字符 if (s->chi!=0&& t->chi=0) return(1);else if (s->chi=0&& t->chi!=0) return(-1);else return(0);/ 算法结束4.7 linkstring *invert(linkstring *S, li

31、nkstring *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->n

32、ext;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/

33、算法结束 第五章 多维数组和广义表（参考答案）5.1 A2323A0000 , A0001 , A0002 A0010 , A0011 , A0012 A0100 , A0101 , A0102 A0110 , A0111 , A0112 A0200 , A0201 , A0202 A0210 , A0211 , A0212 将第一维的0变为1后，可列出另外18个元素。以行序为主（即行优先）时，先改变右边的下标，从右到左进行。5.2 设各维上下号为c1d1，c2d2，c3d3，每个元素占l个单元。LOC(aijk)=LOC(ac1c2c3)+(i-c1)*(d2-c2+1)*(d3-c3+1)

34、+(j-c2)*(d3-c3+1)+(k-c3)*l推广到n维数组！（下界和上界）为（ci，di），其中1<=i<=n.则：其数据元素的存储位置为：LOC（aj1j2.jn）=LOC（ac1c2cn）+（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=1n其中i（dk-ck+1）（1<=i<=n）k=i+15.7 (1) head(p,h,w)=p(2) tail(b,k,p,h)=(k,p,h)(3

35、) head(a,b),(c,d)=(a,b)(4) tail(a,b),(c,d)=(c,d)(5) head(tail(a,b),(c,d)=(c,d)(6) tail(head(a,b),(c,d)=(b)第6章 树和二叉树（参考答案）6.8int height(bitree bt)/ bt链表为存储结构的是以二叉二叉树，本算法求二叉树bt的高度 int bl,br; / 局部变量，分别表示二叉树左、右子树的高度 if (bt=null) return(0);else bl=height(bt->lchild);br=height(bt->rchild);return(bl&

36、gt;br? bl+1: br+1); / 左右子树高度的大者加1（根） / 算法结束 6.227,19,2,6,32,3,21,10其对应字母分别为a,b,c,e,f,g,h。哈夫曼编码：a：0010b：10c：00000d：0001e：01f：00001g：11h：0011第七章 图（参考答案）71（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）Aij= =0为顶点，I 和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。73（1）邻接表（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1（3）从顶点4开始的BFS序列：V4,V5,V3,V6,

37、V1,V276简单回路指起点和终点相同的简单路径。算法基本思想是利用图的遍历，以顶点VK开始，若遍历中再通到VK，则存在简单回路，否则不存在简单回路。Adjlisttp g ; visited1.n=0;Int found =0;/全程变量Int dfs(btxptr x)/从k顶点深度优先遍历图g，看是否存在k的简单回路 visitedx=1;p=gx.firstarc;while(p!=null) w=p->adjvex;if(w= =k) found=1;exit(0);/有简单回路，退出if (!visitedk ) dfs(w );p=p->nextarc;/while(

38、p!=null)/ dfs711void toposort_dfs （graph g；vtptr v）/从顶点v开始，利用深度优先遍历对图g进行拓扑排序。/基本思想是利用栈s存放顶点，首先出栈的顶点是出度为0的顶点，是拓扑序列中最后一个顶/点。若出栈元素个数等于顶点数，则拓扑排序成功，输出的是逆拓扑排序序列。 visited1.n=0;top=0;num=0;/初始化；top为栈顶指针，num记出栈元素数s+top=v;/顶点入栈while (top!=0) w=firstadj(g,v);/求顶点v的第一邻接点while (w！=0) / w!=0的含义是w存在 if ( !visitedw

39、) s+top=w;w=nextadj(g,v,w);/求下一个邻接点if (top!=0) v=stop-; num+; printf(v);/输出顶点printf(“n”);if (num<n) printf(“ 从”,”v”,”顶点开始拓扑排序不能顺利完成 ”)；else printf(“拓扑排序成功，输出的是一个逆拓扑序列.n”);第八章 排序（参考答案）8.4void TwoWayBubbleSort( rectype rn+1; int n)/ 对r1.n进行双向冒泡排序。即相邻两遍向两个相反方向起泡 int i=1, exchange=1; / 设标记 while (exc

40、hange) exchange=0; / 假定本趟无交换 for (j=n-i+1 j>=i+1;j-) / 向前起泡，一趟有一最小冒出 if (rj<rj-1) rjß>rj-1; exchange=1; / 有交换 for (j= i+1;j>=n-I;j+) / 向后起泡，一趟有一最大沉底 if (rj>rj+1) rjß>rj+1; exchange=1; / 有交换 i+; / end of WHILE exchange /算法结束 8.6void QuickSort(rectype rn+1; int n)/ 对r1.n进行快

41、速排序的非递归算法 typedef struct int low,high; nodenode sn+1；int top;int quickpass(rectype r,int,int); / 函数声明 top=1; stop.low=1; stop.high=n;while (top>0)ss=stop.low; tt=stop.high; top-;if (ss<tt) k=quickpass(r,ss,tt);if (k-ss>1) top+; stop.low=ss; stop.high=k-1;if (tt-k>1) top+; stop.low=k+1; s

42、top.high=tt; / 算法结束 int quickpass(rectype r;int s,t)i=s; j=t; rp=ri; x=ri.key;while （i<j）while (i<j && x<=rj.key) j-;if (i<j) ri+=rj; while (i<j && x>=rj.key) i+;if (i<j) rj-=ri;ri=rp; return (i); / 一次划分算法结束 8.7void QuickSort(rectype rn+1; int n)/ 对r1.n进行快速排序的非递归

43、算法 对8.6算法的改进 typedef struct int low,high; nodenode sn+1；int top;int quickpass(rectype r,int,int); / 函数声明 top=1; stop.low=1; stop.high=n;ss=stop.low; tt=stop.high; top-; flag=true;while (flag | top>0)k=quickpass(r,ss,tt);if (k-ss>tt-k) / 一趟排序后分割成左右两部分 if (k-ss>1) / 左部子序列长度大于右部，左部进栈 top+; sto

44、p.low=ss; stop.high=k-1; if (tt-k>1) ss=k+1; / 右部短的直接处理 else flag=false; / 右部处理完，需退栈 else if (tt-k>1) /右部子序列长度大于左部，右部进栈 top=top+1; stop.low=k+1; stop.high=tt; if (k-ss>1) tt=k-1 / 左部短的直接处理 else flag=false / 左部处理完，需退栈 if (!flag && top>0)ss=stop.low; tt=stop.high; top-; flag=true;

45、/ end of while (flag | top>0) / 算法结束 int quickpass(rectype r;int s,t)/ 用“三者取中法”对8.6进行改进 int i=s, j=t, mid=(s+t)/2; rectype tmp;if (ri.key>rmid.key) tmp=ri;ri=rmid;rmid=tmp if (rmid.key>rj.key)tmp=rj;rj=rmid;if (tmp>ri) rmid=tmp; else rmid=ri;ri=tmp tmp=ri;ri=rmid;rmid=tmp / 三者取中：最佳2次比较3次

46、移动；最差3次比较10次移动 rp=ri; x=ri.key;while （i<j）while (i<j && x<=rj.key) j-;if (i<j) ri+=rj; while (i<j && x>=rj.key) i+;if (i<j) rj-=ri;ri=rp; return (i); / 一次划分算法结束 8.8viod searchjrec（rectype r，int j）/在无序记录rn中，找到第j（0<=j<n）个记录。算法利用快速排序思想，找到第一/轴元素的位置i，若i=j则查找结束。否

47、则根据j<i或j>i在0i、1或i+1n+1之间查/找，直到/i=j为止。 int quichpass (rectype r,int,int) / 函数声明i=quichpass(r,0,n-1); / 查找枢轴位置whilehile(i!=j)if (j<i) i=quichpass(r,0.i-1);else i=quichpass(r,i+1.n-1);/ searchjrec算法结束8.9viod rearrange (rectype r,int n)/本算法重排具有n个元素的数r，使取负值的关键字放到取非负值的关键字之前。 int i=0,j=n-1; rp=r0;

48、while(i<j)while(i<j&&rj.key>=0) j-;if(i<j) ri+=rj;/取负值关键字记录放到左面while(i<j&&ri.key<0) i+;if(i<j) rj-=ri/ 取非负值关键字记录放到右面/while(i<j)8.9void arrange(rectype rn+1; int n)/ 对r1.n进行整理，使关键字为负值的记录排在非负值的记录之前 int i=0, j=-1;rp=r0; while (i<j) while (i<j && rj.

49、key>=0) j-;if (i<j) ri+=rj; /将关键字取负值的记录放到前面while (i<j && ri.key<0) i+;if (i<j) rj-=ri;/将关键字取非负值的记录放到后面ri=rp;/算法结束 /本算法并未判断轴枢的关键字的正负，在排序中并未和轴枢/记录比较，而是按正负区分，提高了效率 8.10typedef struct nodeElemTypedata;struct node *next;linklist;void simpleselect(linklist *head)/head是单链表的头指针，本算法对其进

50、行直接选择排序。设p指向无序区第一个记录（开始是链表的第一个记录），用q指向一趟排序中的最小记录，为简便起见，将p和q所指结点的数据交换。p=head->next;while (p->next!=null) / 剩最后一个元素时，排序结束 q=p; / 设当前结点为最小 s=p->next; / s指向待比较结点 while (s!=null)if (s->data>q->data) s=s->next;else q=s; s=s->next; / 用指向新的最小 if (q!=p) x=q->data; q->data=p->

51、data; p->data=x; p=p->next; / 链表指针后移，指向下一个最小值结点 /算法结束 8.14 void CountSort(rectype r; int n);/ 对r0.n-1进行计数排序 int cn = 0;/ c数组初始化，元素值指其在r中的位置。如ci=j,(0<=i,j<n)/ 则意味着ri 应在r的第 j 位置上。for (i=0;i<n;i+) / 一趟扫描比较选出大小，给数组 c 赋值for (j=i+1;j<n;j+)if (ri>rj) ci=ci+1else cj=cj+1;for (i=0;i<n

52、;i+)while (ci!=i) /若ci = i，则ri 正好是第i个元素;否则，需要调整 k=ci;temp=rk; rk=ri; ri=temp; / rk和ri交换ci=ck; / 将ck存入ci,ck=k; / rk已是第k个记录/ while (ci!=i)第九章 查找（参考答案）9.1 int seqsearch( rectype r, keytype k)/ 监视哨设在n个元素的升序顺序表低下标端，顺序查找关键字为k的数据/ 元素。若存在，则返回其在顺序表中的位置，否则，返回0 r0.key=k; i=n; while (ri.key>k) i-;if (i>0 && ri.key=k) return(i); else r