习题二和上机答案

习题二

⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。

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!=NULL)

{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;

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 插入，并返回向量的新长度。实现本题功能的函数如下：

int insert(vector A，int n，ElemType x) /*向量 A 的长度为 n*/

{ int i，j；

if (x>=A[n-1]) A[n]=x /*若 x 大于最后的元素，则将其插入到最后*/

else

{ i=0；

while (x>=A[i]) i++； /*查找插入位置 i*/

for (j=n-1；j>=i；j--) A[j+1]=A[j]； /*移出插入 x 的位置*/

A[i]=x；

n++； /*将 x 插入，向量长度增 1*/

}

return n;

}

⑵单链表。

解：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域

比较大小，找到插入该结点的位置，最后插入该结点。实现本题功能的函数如下：

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 || xdata) /*若单链表为空或 x 小于第一个结点的

date 域*/

{

s->next=head; /*则把 s 结点插入到表头后面*/

head=s;

}

else

{ q=head; /*为 s 结点寻找插入位置，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中也依值递增有序排列。试以不同的存储结构编写求得C的算法。

⑴顺序表；

void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中

{

i=1;j=1;k=0;

while(A.elem[i]&&B.elem[j])

{

if(A.elem[i]

else if(A.elem[i]>B.elem[j]) j++;

else if(A.elem[i]!=A.elem[k])

{

A.elem[++k]=A.elem[i]; //当发现了一个在A,B中都存在的元素

i++;j++; //且C中没有,就添加到C中

}

}//while

while(A.elem[k]) A.elem[k++]=0;

}//SqList_Intersect_True

⑵单链表。

单链表

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->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 linknode

{

elemtype data；

struct linknode *next；

} nodetype；

nodetype *subs(nodetype *heada, nodetype *headb)

{

nodetype *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；

}

else

{

r->next=p；s=p->next；

r=p；r->next=NULL；

p=s；

}

}

s=heada；heada=heada->next；free(s)；

return heada；

}

2.8设有线性表A=(a1 ,a2 ,...,a m )，B=(b1 ,b2 ,...,b n )。试写一合并A、B为线性表C的算法，使得

(a1 ,b1 ,...,a m ,b m ,b m+1 ,...,b n ) 当m≤n时

C＝｛

(a1 ,b1 ,...,a n ,b n ,a n+1 ,...,a m ) 当m＞n时

A、B和C均以单链表作存储结构，且C表利用A和B中结点空间。

解：假设 A，B 和 C 链表分别具有头结点的指针 a，b 和 c。实现本题功能的函数如下：

node *link(a，b)

node *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(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。写出相应的求解算法。

解：

先构造一个循环链表

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

p=p->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;

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->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、data和next，每个结点的pre值为空指针，试编写算法将此链表改为双向环形链表。

分析：在遍历单链表时，可以利用指针记录当前访问结点和其前驱结点。知道了当前访问结点的前驱结点位置，就可以给当前访问结点的前驱指针赋值。这样在遍历了整个链表后，所有结点的前驱指针均得到赋值。

Typedef struct lnode

{elemtype 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;

pre=p;

p=p->next;

}

p->pre=pre;

}

2.13设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676

（10），每个元素占一个地址空间，求A[3][3]（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=15

LOC(3,3)=LOC(0,0)+3*15+3=644+45+3=692

2.14 设稀疏矩阵采用十字链表结构表示。试写出实现两个稀疏矩阵相加的算法。

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

（2）若pa->col=pb->col 且pa->val+pb->val=0，则需要在 A 矩阵的十字链表中删除pa 所指结点，此时需改变同一行中前一结点的right 域值，以及同一列中前一结点的down域值。

（3）若pa->colcol 且pa->col≠0（即不是表头结点），则只需要将pa 指针往右推进一步，并重新加以比较。

（4）若pa->col>pb->col 或pa->col=0，则需要在A 矩阵的十字链表中插入一个值为bij 的结点。

实现本题功能的程序如下：

#include

#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"，&m，&n，&t);

p=(struct matnode *)malloc(sizeof(struct matnode));

h[0]=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));

h[i]=p;

h[i-1]->tag.next=p;

p->row=p->col=0;

p->down=p->right=p;

}

h[s]->tag.next=h[0];

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=h[r];

while (q->right!=h[r] && q->right->col

q=q->right;

p->right=q->right;

q->right=p;

q=h[c];

while(q->down!=h[c] && q->down->row

q=q->down;

p->down=q->down;

q->down=p;

}

return(h[0]);

}

void prmat(struct matnode *hm)

{

struct matnode *p，*q;

printf("\n 按行表输出矩阵元素:\n");

printf("row=%d col=%d\n"，hm->row，hm->col);

p=hm->tag.next;

while (p!=hm)

{

q=p->right;

while (p!=q)

{

printf("\t%d，%d，%d\n"，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=h[j];

while (d->down->col!=0 && d->down->row

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=ha->tag.next;

cb=hb->tag.next;

do

{

pa=ca->right;

pb=cb->right;

qa=ca;

while (pb->col!=0)

if (pa->colcol && 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->right=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->right;

pb=pb->right;

}

ca=ca->tag.next;

cb=cb->tag.next;

} while (ca->row==0);

}

return(h[0]);

}

main()

{

struct matnode *hm，*hm1，*hm2;

struct matnode *h[MAX]，*h1[MAX];

printf("第一个矩阵:\n");

hm1=createmat(h);

printf("第二个矩阵:\n");

hm2=createmat(h1);

hm=addmat(hm1，hm2，h);

prmat(hm);

}

第二章上机内容

1.设计一个程序，生成两个按值非递减有序排列的线性表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（“%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 , q , s , c；

c= malloc(sizeof(listnode))；

c->next =NULL；

p=a；

q=b；

while(p->next&&q->next)

{

if (p->next->datanext->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 = 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)；

print(c)；

printf（“\n”）；

}

输入：ysplhd

zyxrmhb

输出：dhlpsy

bhmrxyz

zyyxsrpmlhhdb

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;

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->expexp)

{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 linknode

{

elemtype data；

struct linknode *next；

} nodetype；

nodetype *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；

}

else

{

s=(nodetype *)malloc(sizeof(nodetype))；

s->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)

{

a[p->data]++；

p=p->next；