数据结构上机例题及答案

1、习题二2. 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->ne

3、xt!=NULL)q=p;p=p->next; if (p->data=a)q->next=s;s->next=p;elsep->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;elseq->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插入,并返回向量的新长度。实现本题功能的函数如下：i

5、nt insert(vector A , int n , ElemType x) /*向量 A 的长度为 n*/ inti , j；*/if (x>=An-1) An=x/*若x大于最后的元素，则将其插入到最后 elsei=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结点寻找插入位置，p指向待比较的结点，q指向p的

7、前驱结点*/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中也依值递增有序排列。试以不同的存储结构编写求得C的算法。顺序表；void SqList_I

8、ntersect_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+;else if(A.elemi!=A.elemk) A.elem+k=A.elemi;/当发现了一个在 A,B中都存在的元素i+;j+; 且C中没有，就添加到C中 /whilewhile(A.elemk) A.elemk+=0;SqList_Intersect_True单链

9、表。单链表chnode *or(chnode *head1,chnode *head2) chnode *p1,*p2,*q2,*h,*p;h=p=malloc(sizeof(chnode);p->next=NULL;p1=head1->next;while(pl) 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->n

10、ext)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)nodetype *p, *q

11、, *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=N

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

13、a , *b;node *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 *)malloc

14、(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。写出相应的求解算法。解:先构造一

15、个循环链表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->n

16、ext;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) c

17、har c;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' &&a

18、mp;c<= ' 9')rb->next=p;rb=p;elserc->next=p;rc=p;p=p->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->ne

19、xt;r->next=p;free(q);return(p);2.12假设有一个单向循环链表，其结点含三个域:pre、data 和 next,每个结点的pre值为空指针，试编写算法将此链表改为双向环形链表。分析：在遍历单链表时，可以利用指针记录当前访问结点和其前驱结点。知道了当前访问结点的前驱结点位置，就可以给当前访问结点的前驱指针赋值。这样在遍历了整个链表后，所有结点的前驱指针均得到赋值。Typedef struct Inodeelemtype data;struct Inode pre,next;lnode,*linklist;void singletodouble(linklist

20、 h)linklist pre,p;p=h->next;pre=h;while(p!=h)p->pre=pre;pre=p;p=p->next; p->pre=pre;2.13 设有一个二维数组 Amn，假设 A0存放位置在 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-6

21、44 ) /2=15LOC(3,3)=LOC(0,0 )+3*15+3=644+45+3=6922.14 设稀疏矩阵采用十字链表结构表示。试写出实现两个稀疏矩阵相加的算法。解：依题意，C=A+B ,则C中的非零元素cij只可能有3种情况：或者是 aij+bij ,或者是aij(bij=0)或者是bij(aij=0)。因此，当B加到A上时，对A矩阵的十字链表来说， 或者是改变结点的val域值(a+b%),或者不变(b=0),或者插入一个新结点(a=0),还可能是删除一个结点(aij+bij=0)。整个运算可从矩阵的第一行起逐行进行。对每一行都从行表头 出发分别找到 A和B在该行中的第一个非零元素

22、结点后开始比较，然后按4种不同情况分别处理(假设pa和pb分别指向A和B的十字链表中行值相同的两个结点)：若pa->col=pb->col 且pa->val+pb->val礼，则只要将 aij+bij的值送到 pa 所指结点 的值域中即可。(2)若 pa->col=pb->col 且pa->val+pb->val=0 ,则需要在 A 矩阵的十字链表中删除pa所指结点，此时需改变同一行中前一结点的right域值，以及同一列中前一结点的down域值。(3)若pa->col<pb->col 且pa->col为(即不是表头结点)，

23、则只需要将pa指针往右推进一步，并重新加以比较。(4)若pa->col>pb->col 或pa->col=0 ,则需要在 A 矩阵的十字链表中插入一个值为bij的结点。实现本题功能的程序如下：#include <stdio.h>#define MAX 100struct matnode *createmat(struct matnode *h)/*h是建立的十字链表各行首指针的数组*/ int m , n, t, s, i, r, c, v;struct matnode *p , *q;printf("行数 m ,列数n,非零元个数 t:"

24、;);scanf("%d , %d , %d", &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-&

25、gt;right=p;hs->tag.next=h0;for (i=1;i<=t;i+)printf("t第%个元素(行号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<

26、c)q=q->right;p->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-&

27、gt;row , hm->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 mat

28、node *d;d=hj；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

29、");exit(0);elseca=ha->tag.next;cb=hb->tag.next;dopa=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

30、;p->right=pa;qa->right=p;qa=p;q=colpred(p->row ,p->col , h);p->down=q->down;q->down=p;pb=pb->right;精品资料elsepa->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->

31、;right;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 .

32、设计一个程序，生成两个按值非递减有序排列的线性表LA和LB,再将LA和LB归并为一个新的线性表 LC,且LC中的数据仍按值非递减有序排列，输出线性表LA, LB,LC。精品资料解:#includeStdio.h "#includealloc.h "typedef struct nodechar data ;struct node *next ; listnode ;typedef struct node *link;void print(link head)struct node *p;printf ( h");printf ( h");p= head-

33、>next ;while(p)printf ( %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 he

34、ad ;link merge(link a , link b)link p , 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->

35、next ;c->next = s ;while (p->next)s = 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

36、(a);print(b);c = merge ( a , b);print(c)；printf ( h");输入：ysplhdzyxrmhb输出:dhlpsybhmrxyzzyyxsrpmlhhdb2 .生成两个多项式 PA和PB,求PA和PB之和，输出“和多项式”。解：typedef struct nodeint 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-&g

37、t;next;q=pb->next;pre=pa;while (p!=NULL)&&(q!=NULL)if (p->exp>q->exp)r=q->next;q->next=p;pre->next=q;pre=q;q=r;elseif(p->exp=q->exp)x=p->coef+q->coef;if (x!=0)p->coef=x;s=p；elsepre->next=p->next;free(p)；p=pre->next;r=p；q=q->next;free(r);elseif

38、(p->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

39、*create()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->

40、;data=d ; s->next=NULL ; t->next=s ;t=s ;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( &quo

41、t;3d”，i);printf ( "n 得票数：”)；for (I=1 ; I<=N ; I+)printf( “%3d"，ai);printf( "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 (

42、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->next;if (p->next!=p) q=p->next;printf( " %d”

43、,q->data);p->next=q->next;free(q);p=p->next;printf( "%dn " ,p->data);void main()int n,k;nodetype *h;scanf( "%d" ,&n);scanf( "%d" ,&m);h=crea(n);jese(h,m);* 5.设计一个算法求 A和B两个单链表表示的集合的交集、并集、差集/*设计一个算法求 A和B两个单链表表示的集合的交集。*/#define NULL 0typedef int stat

44、us;typedef struct Inodeint data;struct lnode *next;LNode;LNode *creat()LNode *head=NULL,*p1,*p2;int i=1,d;while(1)printf("enter %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;elsep1=(LNode *)mallo

45、c(sizeof(LNode);p1->data=d;p1->next=NULL;p2->next=p1;p2=p1;i+；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;printf("creat A:n");A=creat();printf("creat B:n");B

46、=creat();P=A；printf("the jiaoji'n");while(p!=NULL)if(find(B,p->data)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+；LNode *creat()if(i=1)printf("kongji'n");exit(0);p=C;while(p!=NULL)printf("%d &

47、quot;,p->data);p=p->next;printf("n");getch()；/*设计一个算法求 A和B两个单链表表示的集合的并集。*/#define NULL 0typedef int status;typedef struct lnodeint data;struct lnode *next;LNode;LNode *head=NULL,*p1,*p2;int i=1;p1=p2=(LNode *)malloc(sizeof(LNode);printf("enter %d data:",i);scanf("%d&qu

48、ot;,&p1->data);while(p1->data!=0)if(i=1) head=p1;else p2->next=p1;p2=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->dat

49、a=d) return 1;p=p->next;return 0;main()LNode *A,*B,*C,*p,*q1,*q2;int i=1,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;els

50、e q2->next=q1;q2=q1;i+；p=p->next;p=B；while(p!=NULL)q1=(LNode *)malloc(sizeof(LNode);q1->data=p->data;q1->next=NULL;if(k=0) C=q2=q1;k=1;else q2->next=q1;q2=q1;p=p->next;printf("the bingji'n");p=C;while(p!=NULL)printf("%d ",p->data);p=p->next;printf(&

51、quot;n");getch()；*/*设计一个算法求 A和B两个单链表表示的集合的差集#define NULL 0typedef struct Inodeint data;struct lnode *next;*Linklist;Linklist creat()Linklist head,s;int n;head=(Linklist)malloc(sizeof(struct lnode);head->next=NULL;scanf("%d",&n);while(n!=0)s=(Linklist)malloc(sizeof(struct Inode)

52、;s->data=n;s->next=head->next;head->next=s;scanf("%d",&n);return head;void disp(Linklist head)Linklist p=head->next;while(p!=NULL)printf("%d ",p->data);p=p->next;printf("n");int find(int d,Linklist head)Linklist p=head->next;while(p&&

53、p->data!=d) p=p->next;if(!p) return 0;return 1;main()Linklist A,B,C,p,s;C=(Linklist)malloc(sizeof(struct lnode);C->next=NULL;printf("creat A:n");A=creat();printf("creat B:n");B=creat();p=A->next;while(p!=NULL)if(!find(p->data,B)s=(Linklist)malloc(sizeof(struct lnod

54、e); s->data=p->data;s->next=C->next;C->next=s;p=p->next;printf("A:");disp(A)；printf("B:");disp(B)；printf("C:");disp(C)；getch()； 6.稀疏矩阵运算器基本要求：以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结果的矩阵则以通常的阵列形式列出。#define NULL 0#define maxsize

55、100typedef structint i,j,v；jd；typedef structjd datamaxsize;int mu,nu,vu;sh;void dis(sh *B)int x,y,p=1;for(x=1;x<=B->mu;x+)for(y=1;y<=B->nu;y+)if(x=B->datap.i&&y=B->datap.j) printf("%-3d ”,B->datap.v);p+;else printf("%-3d ",0);printf("n");sh *creat()