习题二和上机答案

1、习 题 二描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存

2、储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b)Lnode *p,*q,*s;s=(Lnode*)malloc(sizeof(Lnode);s->data=b;p=h->next;while(p->data!=a&&p->next!=NU

3、LL) q=p; p=p->next; if (p->data=a) q->next=s; s->next=p; else p->next=s; s->next=NULL; 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。Lnode *cf(Lnode *ha) Lnode *p,*q,*s,*hb;int t;p=ha->next;q=ha;t=0;hb=(Lnode*)malloc(sizeof(Lnode);s=hb;

4、while(p->next!=NULL) if (t=0) q=p;p=p->next;t=1; else q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; s->next=NULL; return (hb); 2.5设线性表中的数据元素是按值非递减有序排列的，试以不同的存储结构，编写一算法，将x插入到线性表的适当位置上，以保持线性表的有序性。 顺序表； 解：本题的算法思想是：先找到适当的位置，然后后移元素空出一个位置，再将 x 插入，并返回向量的新长度。实现

5、本题功能的函数如下： int insert(vector A，int n，ElemType x) /*向量 A 的长度为 n*/ int i，j； if (x>=An-1) An=x /*若 x 大于最后的元素，则将其插入到最后*/ else i=0； while (x>=Ai) i+； /*查找插入位置 i*/ for (j=n-1；j>=i；j-) Aj+1=Aj； /*移出插入 x 的位置*/ Ai=x； n+； /*将 x 插入，向量长度增 1*/ return n; 单链表。解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插

6、入该结点的位置，最后插入该结点。实现本题功能的函数如下： node *insertorder(head，x) node *head; ElemType x; node *s，*p，*q; s=(node *)malloc(sizeof(node); /*建立一个待插入的结点*/ s->data=x; s->next=NULL; if (head=NULL | x<head->data) /*若单链表为空或 x 小于第一个结点的 date 域*/ s->next=head; /*则把 s 结点插入到表头后面*/ head=s; else q=head; /*为 s

7、结点寻找插入位置，p 指向待比较的结点，q 指向 p 的前驱结点*/ p=q->next; while (p!=NULL && x>p->data) /*若 x 小于 p 所指结点的 data 域值*/ if (x>p->data) /*则退出 while 循环*/ q=p; p=p->next; s->next=p; /*将 s 结点插入到 q 和 p 之间*/ q->next=s; return(head); 2.6假设有A和B分别表示两个递增有序排列的线性表集合（即同一表中元素值各不相同）， 求A和B的交集C， 表C中也依值

8、递增有序排列。试以不同的存储结构编写求得C的算法。 顺序表；void SqList_Intersect_True(SqList &A,SqList B)/求元素递增排列的线性表A和B的元素的交集并存回A中  i=1;j=1;k=0;  while(A.elemi&&B.elemj)      if(A.elemi<B.elemj) i+;    else if(A.elemi>B.elemj) j+; 

9、0;  else if(A.elemi!=A.elemk)          A.elem+k=A.elemi; /当发现了一个在A,B中都存在的元素      i+;j+; /且C中没有,就添加到C中      /while  while(A.elemk) A.elemk+=0;/SqList_Intersect_True 单链表。单链

10、表chnode *or(chnode *head1,chnode *head2) chnode *p1,*p2,*q2,*h,*p; h=p=malloc(sizeof(chnode); p->next=NULL; p1=head1->next; while(p1) p2=head2;q2=p2->next; while(q2->data!=p1->data)&&q2) p2=q2; q2=q2->next; if(p1->data=q2->data) p2->next=q2->next; if(q2) while(p

11、->next) p=p->next; p->next=q2; p=q2; q2->next=NULL; p1=p1->next; return(h); 2.7设计一个算法求两个递增有序排列的线性表A和B 的差集。（每个单链表中不存在重复的元素）提示：即在A中而不在B中的结点的集合。typedef int elemtype；typedef struct linknodeelemtype data；struct linknode *next； nodetype； nodetype *subs(nodetype *heada, nodetype *headb)nodet

12、ype *p, *q, *r, *s；s=(nodetype *)malloc(sizeof(nodetype)；s->next=heada；heada=s；p=heada->next；r=heada；r->next=NULL；while (p!=NULL)q=headb；while (q!=NULL && q->data!=p->data) q=q->next；if (q!=NULL)s=p->next；free(p)；p=s；elser->next=p；s=p->next；r=p；r->next=NULL；p=s；

13、s=heada；heada=heada->next；free(s)；return heada；2.8设有线性表A=(a1 ,a2 ,.,am )，B=(b1 ,b2 ,.,bn )。试写一合并A、B为线性表C的算法，使得 (a1 ,b1 ,.,am ,bm ,bm+1 ,.,bn ) 当mn时 C (a1 ,b1 ,.,an ,bn ,an+1 ,.,am ) 当mn时A、B和C均以单链表作存储结构，且C表利用A和B中结点空间。解：假设 A，B 和 C 链表分别具有头结点的指针 a，b 和 c。实现本题功能的函数如下： node *link(a，b) node *a，*b; node *

14、r，*s，*p，*q，*c; c=(node *)malloc(sizeof(node); /*建立一个头结点*/ r=c;p=a;q=b; while (p!=NULL | q!=NULL) if (p!=NULL) /*如果 A 链表还存在可取的结点，则复制一个同样的结点链接到 C 中*/ s=(node *)malloc(sizeof(node); s->data=p->data; r->next=s; r=s; p=p->next; if (q!=NULL) /*如果 B 链表还存在可取的结点，则复制一个同样的结点链接到 C 中*/ s=(node *)mall

15、oc(sizeof(node); s->data=q->data; r->next=s; r=s; q=q->next; r->next=NULL; s=c; c=c->next; /*删除头结点*/ free(s); return(c); 2.9试用两种线性表的存储结构来解决约瑟夫问题。设有n个人围坐在圆桌周围，现从第s个人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，如此重复直到所有的人全部出列为止。例如当n=8,m=4,s=1,得到的新序列为：4，8，5，2，1，3，7，6。写出相应的求解算法。解：先构造一个循环链表

16、nodetype *crea(int n) nodetype *s,*r,*h; int I; for (i=1;i<=n;i+) s=(nodetype *)malloc(sizeof (nodetype); s->data=I;s->next=NULL; if(i=1) h=s;else r->next=s;r=s;r->next=h;return h;void jese (nodetype *h,int m) nodetype *p=h,*q; int I; while (p->next!=p) for (i=1;i<m-1;i+) p=p-&g

17、t;next; if (p->next!=p) q=p->next; printf(“%d”,q->data); p->next=q->next; free(q); p=p->next; printf(“%d”,p->data);2.10已知单链表中的数据元素含有三类字符（即：字母字符、数字字符和其它字符），试编写算法构造三个环形链表，使每个环形链表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。解：void split (nodetype *ha,nodetype *hb,nodetype *hc) char c;

18、 nodetype *ra,*rb,*rc,*p=ha->next; ra=ha;ra->next=NULL; rb=hb;rb->next=NULL; rc=hc;rc->next=NULL; while (p!=ha) c=p->data; if (c>=a&&c<=z)|(c>=A&&c<=Z) ra->next=p;ra=p; else if(c>=0&&c<=9) rb->next=p;rb=p; else rc->next=p;rc=p; p=p-&g

19、t;next; ra->next=ha;rb->next=hb;rc->next=hc; 2.11假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知p为指向链表中某结点的指针，试编写算法在链表中删除结点p 的前趋结点。解：nodetype *delprev(nodetype *p) nodetype *r=p,*q=r->next; while (q->next!=p) r=r->next;q=r->next; r->next=p; free(q); return(p); 2.12假设有一个单向循环链表，其结点含三个域：pre、da

20、ta和next， 每个结点的pre值为空指针，试编写算法将此链表改为双向环形链表。分析：在遍历单链表时，可以利用指针记录当前访问结点和其前驱结点。知道了当前访问结点的前驱结点位置，就可以给当前访问结点的前驱指针赋值。这样在遍历了整个链表后，所有结点的前驱指针均得到赋值。Typedef struct lnodeelemtype data; struct lnode pre,next;lnode,*linklist;void singletodouble(linklist h)linklist pre,p;p=h->next;pre=h;while(p!=h) p->pre=pre;

21、pre=p; p=p->next; p->pre=pre; 2.13设有一个二维数组Amn，假设A00存放位置在644（10），A22存放位置在676（10），每个元素占一个地址空间，求A33（10）存放在什么位置？分析 根据二维数组的地址计算公式：LOC(i,j)=LOC(0,0 )+n*i+j*s，首先要求出数组第二维的长度，即n值。解 因为LOC(2，2)=LOC(0,0 )+ 2*n+2=644+2*n+2=676 所以n=（676-2-644）/2=15LOC(3,3)=LOC(0,0 )+3*15+3=644+45+3=6922.14 设稀疏矩阵采用十字链表结构表示。试

22、写出实现两个稀疏矩阵相加的算法。 解：依题意，C=A+B，则 C 中的非零元素 cij只可能有 3 种情况：或者是 aij+bij，或者是 aij(bij=0)或者是 bij(aij=0)。因此，当 B 加到 A 上时，对 A 矩阵的十字链表来说，或者是改变结点的 val 域值(a+b0)，或者不变(b=0)，或者插入一个新结点(a=0)，还可能是删除一个结点(aij+bij=0)。整个运算可从矩阵的第一行起逐行进行。对每一行都从行表头出发分别找到 A 和 B 在该行中的第一个非零元素结点后开始比较，然后按 4 种不同情况分别处理（假设 pa 和 pb 分别指向 A 和 B 的十字链表中行值相

23、同的两个结点）： 若 pa->col=pb->col 且 pa->val+pb->val0，则只要将 aij+bij的值送到 pa 所指结点的值域中即可。（2）若 pa->col=pb->col 且 pa->val+pb->val=0，则需要在 A 矩阵的十字链表中删除pa 所指结点，此时需改变同一行中前一结点的 right 域值，以及同一列中前一结点的 down域值。 （3）若 pa->col<pb->col 且 pa->col0（即不是表头结点），则只需要将 pa 指针往右推进一步，并重新加以比较。 （4）若 pa-&

24、gt;col>pb->col 或 pa->col=0，则需要在 A 矩阵的十字链表中插入一个值为bij 的结点。实现本题功能的程序如下：#include <stdio.h>#define MAX 100 struct matnode *createmat(struct matnode *h) /*h 是建立的十字链表各行首指针的数组*/ int m，n，t，s，i，r，c，v; struct matnode *p，*q; printf("行数 m，列数 n，非零元个数 t:"); scanf("%d，%d，%d"，&

25、m，&n，&t); p=(struct matnode *)malloc(sizeof(struct matnode);h0=p; p->row=m; p->col=n; s=m>n ? m:n; /*s 为 m、n 中的较大者*/ for (i=1;i<=s;i+) p=(struct matnode *)malloc(sizeof(struct matnode); hi=p; hi-1->tag.next=p; p->row=p->col=0; p->down=p->right=p; hs->tag.next=h0

26、; for (i=1;i<=t;i+) printf("t 第%d 个元素(行号 r，列号 c，值 v):"，i); scanf("%d，%d，%d"，&r，&c，&v); p=(struct matnode *)malloc(sizeof(struct matnode); p->row=r; p->col=c; p->tag.val=v; q=hr; while (q->right!=hr && q->right->col<c) q=q->right; p-&

27、gt;right=q->right; q->right=p; q=hc; while(q->down!=hc && q->down->row<r) q=q->down; p->down=q->down; q->down=p; return(h0); void prmat(struct matnode *hm) struct matnode *p，*q; printf("n 按行表输出矩阵元素:n"); printf("row=%d col=%dn"，hm->row，hm-&

28、gt;col); p=hm->tag.next; while (p!=hm) q=p->right; while (p!=q) printf("t%d，%d，%dn"，q->row，q->col，q->tag.val);q=q->right; p=p->tag.next; struct matnode *colpred(i，j，h) /*根据 i(行号)和 j(列号)找出矩阵第 i 行第 j 列的非零元素在十字链表中的前驱结点*/ int i，j; struct matnode *h; struct matnode *d; d=hj

29、; while (d->down->col!=0 && d->down->row<i) d=d->down; return(d); struct matnode *addmat(ha，hb，h) struct matnode *ha，*hb，*h; struct matnode *p，*q，*ca，*cb，*pa，*pb，*qa; if (ha->row!=hb->row | ha->col!=hb->col) printf("两个矩阵不是同类型的，不能相加n"); exit(0); else ca

30、=ha->tag.next; cb=hb->tag.next; do pa=ca->right; pb=cb->right; qa=ca; while (pb->col!=0) if (pa->col<pb->col && pa->col!=0) qa=pa; pa=pa->right; else if (pa->col>pb->col | pa->col=0) p=(struct matnode *)malloc(sizeof(struct matnode); *p=*pb; p->ri

31、ght=pa; qa->right=p; qa=p; q=colpred(p->row，p->col，h); p->down=q->down; q->down=p; pb=pb->right; else pa->tag.val+=pb->tag.val; if (pa->tag.val=0) qa->right=pa->right; q=colpred(pa->row，pa->col，h); q->down=pa->down; free(pa); else qa=pa; pa=pa->righ

32、t; pb=pb->right; ca=ca->tag.next; cb=cb->tag.next; while (ca->row=0); return(h0); main() struct matnode *hm，*hm1，*hm2; struct matnode *hMAX，*h1MAX; printf("第一个矩阵:n"); hm1=createmat(h); printf("第二个矩阵:n"); hm2=createmat(h1); hm=addmat(hm1，hm2，h); prmat(hm); 第二章上机内容 1.设计

33、一个程序，生成两个按值非递减有序排列的线性表LA和LB，再将LA和LB归并为一个新的线性表LC，且LC中的数据仍按值非递减有序排列，输出线性表LA，LB，LC。解：#include “stdio.h”#include “alloc.h”typedef struct node char data； struct node *next； listnode；typedef struct node *link；void print(link head) struct node *p； printf（“n”）； printf（“n”）； p= head->next； while(p) printf

34、（“%c”, p->data)； p = p->next； link creat() /*头插法建立单链表*/ link head ,s； char ch； head = malloc(sizeof(listnode)； head->next =NULL； while( ch= getchar()!=n) s= malloc(sizeof(listnode)； s->data= ch； s->next = head->next； head->next = s； return head；link merge(link a , link b) link p

35、 , q , s , c； c= malloc(sizeof(listnode)； c->next =NULL； p=a； q=b； while(p->next&&q->next) if (p->next->data<q->next->data) s = p->next；p->next=s->next； else s = q->next；q->next = s->next； s->next = c->next； c->next = s； while (p->next) s

36、 = p->next； p->next = s->next； s->next = c->next； c->next = s； while(q->next) s = q->next； q->next = s->next； s->next = c->next； c->next = s； free(p)；free(q)； return c；main() link a , b , c； a = creat()； b = creat()； print(a)； print(b)； c = merge ( a , b)； prin

37、t(c)； printf（“n”）；输入：ysplhd zyxrmhb输出：dhlpsy bhmrxyzzyyxsrpmlhhdb 2. 生成两个多项式PA和PB，求PA和PB之和，输出“和多项式”。解：typedef struct node int exp; float coef; struct node *next; polynode; polynode *p,*q; polynode *polyadd(pa,pb) polynode *pa,*pb; polynode *p,*q,*pre,*r; float x; p=pa->next; q=pb->next; pre=pa

38、; while (p!=NULL)&&(q!=NULL) if (p->exp>q->exp) r=q->next; q->next=p; pre->next=q; pre=q; q=r; else if(p->exp=q->exp) x=p->coef+q->coef; if (x!=0) p->coef=x; s=p; else pre->next=p->next; free(p); p=pre->next; r=p; q=q->next; free(r); else if (p-&g

39、t;exp<q->exp) pre=p; p=p->next; if (q!=NULL) pre->next=q; free(pb); 3设计一个统计选票的算法，输出每个候选的得票结果（假设采用单链表存放选票，候选人编号依次为1，2，3，N，且每张选票选且只选一人）提示：以单链表存放选票，每个结点的data域存放该选票所选的候选人。用一个数组a统计得票结果。typedef int elemtype；typedef struct linknodeelemtype data；struct linknode *next； nodetype；nodetype *create()

40、elemtype d；nodetype h=NULL,*s,*t；int I=1；printf（“建立一个单链表n”）；while (1)printf（“输入第%d节点data域值：”,i)；scanf（“%d”,&d)；if (d= =0) break；if(I= =1)h=(nodetype *)malloc(sizeof(nodetype)；h->data=d；h->next=NULL；t=h；elses=(nodetype *)malloc(sizeof(nodetype)；s->data=d；s->next=NULL；t->next=s；t=s；

41、I+；return h； void sat (nodetype *h, int a)nodetype *p=h；while (p!=NULL)ap->data+；p=p->next；void main()int aN+1, I；for (I=0；I<N；I+)aI=0；nodetype *head；head=create()；sat(head,a)；printf（“候选人：”）；for (I=1；I<=N；I+) printf( “%3d”,i)；printf（“n得票数：”）；for (I=1；I<=N；I+)printf( “%3d”,ai)；printf(

42、“n”）； 4. 编写一算法来解决约瑟夫问题。设有n个人围坐在圆桌周围，现从第s个人开始报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m个人又出列，如此重复直到所有的人全部出列为止。例如当n=8,m=4,s=1,得到的新序列为：4，8，5，2，1，3，7，6。 解：nodetype *crea(int n) nodetype *s,*r,*h; int I; for (i=1;i<=n;i+) s=(nodetype *)malloc(sizeof (nodetype); s->data=I;s->next=NULL; if(i=1) h=s;else r-

43、>next=s;r=s;r->next=h;return h;void jese (nodetype *h,int m) nodetype *p=h,*q; int I; while (p->next!=p) for (i=1;i<m-1;i+) p=p->next; if (p->next!=p) q=p->next; printf(“ %d”,q->data); p->next=q->next; free(q); p=p->next; printf(“%dn”,p->data);void main() int n,k;

44、 nodetype *h; scanf(“%d”,&n); scanf(“%d”,&m); h=crea(n); jese(h,m);* 5设计一个算法求A和B两个单链表表示的集合的交集、并集、差集。/*设计一个算法求A和B两个单链表表示的集合的交集。*/#define NULL 0typedef int status;typedef struct lnode int data; struct lnode *next;LNode;LNode *creat() LNode *head=NULL,*p1,*p2; int i=1,d; while(1) printf("e

45、nter %d data:",i);scanf("%d",&d);if(d=0) break;if(i=1) head=(LNode *)malloc(sizeof(LNode); head->data=d;head->next=NULL;p2=head; else p1=(LNode *)malloc(sizeof(LNode); p1->data=d;p1->next=NULL;p2->next=p1; p2=p1; i+; return head;status find(LNode *head,int d) LNode

46、*p=head; while(p!=NULL) if(p->data=d) return 1;p=p->next; return 0;main() LNode *A,*B,*C,*p,*q1,*q2; int i=1; printf("creat A:n"); A=creat(); printf("creat B:n"); B=creat(); p=A; printf("the jiaojin"); while(p!=NULL) if(find(B,p->data) q1=(LNode *)malloc(sizeof

47、(LNode); q1->data=p->data; q1->next=NULL; if(i=1) C=q2=q1; else q2->next=q1; q2=q1; i+; p=p->next; if(i=1) printf("kongjin");exit(0); p=C; while(p!=NULL) printf("%d ",p->data);p=p->next; printf("n"); getch();/*设计一个算法求A和B两个单链表表示的集合的并集。*/#define NULL

48、0typedef int status;typedef struct lnode int data; struct lnode *next;LNode;LNode *creat() LNode *head=NULL,*p1,*p2; int i=1; p1=p2=(LNode *)malloc(sizeof(LNode); printf("enter %d data:",i); scanf("%d",&p1->data); while(p1->data!=0) if(i=1) head=p1;else p2->next=p1;p

49、2=p1;i+;printf("enter %d data:",i);p1=(LNode *)malloc(sizeof(LNode);scanf("%d",&p1->data); p2->next=NULL; return head;status find(LNode *head,int d) LNode *p=head; while(p!=NULL) if(p->data=d) return 1; p=p->next; return 0;main() LNode *A,*B,*C,*p,*q1,*q2; int i=1

50、,k=0; printf("creat A:n"); A=creat(); printf("creat B:n"); B=creat(); p=A; while(p!=NULL) if(!find(B,p->data) k=1; q1=(LNode *)malloc(sizeof(LNode); q1->data=p->data; q1->next=NULL; if(i=1) C=q2=q1; else q2->next=q1; q2=q1; i+; p=p->next; p=B; while(p!=NULL) q1=(LNode *)malloc(sizeof(LNode);q1->data=p->data;q1->