习题二和上机答案

习 题 二

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

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 ,...,am )，B=(b1 ,b2 ,...,bn )。试写一合并A、B为线性表C的算法，使得

(a1 ,b1 ,...,am ,bm ,bm+1 ,...,bn ) 当m≤n时 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 *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;inext; 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]存放位置在4（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=4+2*n+2=676 所以n=（676-2-4）/2=15

.

.

LOC(3,3)=LOC(0,0 )+3*15+3=4+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(\"\ 第%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->colright; p->right=q->right; q->right=p; q=h[c];

while(q->down!=h[c] && q->down->rowdown; 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(\"\%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；

.

.

} }

void main() {

int a[N+1], I； for (I=0；Ia[I]=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”,a[i])； 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 (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;inext; if (p->next!=p) { q=p->next;

printf(“ %d”,q->data); p->next=q->next; free(q); } p=p->next; }

printf(“%d\\n”,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 0 typedef 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(\"enter %d data:\ scanf(\"%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 *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 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++; }

p=p->next; } if(i==1)

{printf(\"kongji\\n\");exit(0);} p=C;

while(p!=NULL) { printf(\"%d \ p=p->next; }

printf(\"\\n\"); getch(); }󰀀

/*设计一个算法求A和B两个单链表表示的集合的并集。*/ #define NULL 0

typedef 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:\ scanf(\"%d\ while(p1->data!=0) {

if(i==1) head=p1; else p2->next=p1; p2=p1; i++;

printf(\"enter %d data:\

p1=(LNode *)malloc(sizeof(LNode)); scanf(\"%d\ }

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,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->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=p->next; }

printf(\"\\n\"); getch(); }

/*设计一个算法求A和B两个单链表表示的集合的差集。*/ #define NULL 0

typedef struct lnode {

int data;

struct lnode *next; }*Linklist;

Linklist creat() {

Linklist head,s; int n;

.

.

head=(Linklist)malloc(sizeof(struct lnode)); head->next=NULL; scanf(\"%d\ while(n!=0) {

s=(Linklist)malloc(sizeof(struct lnode)); s->data=n;

s->next=head->next; head->next=s; scanf(\"%d\ }

return head; }

void disp(Linklist head) {

Linklist p=head->next; while(p!=NULL) {

printf(\"%d \ p=p->next; }

printf(\"\\n\"); }

int find(int d,Linklist head) {

Linklist p=head->next;

while(p&&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 lnode)); 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 100 typedef struct {

int i,j,v; }jd;

typedef struct {

jd data[maxsize]; 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->data[p].i&&y==B->data[p].j) { printf(\"%-3d \ p++; }

else printf(\"%-3d \

.

.

}

printf(\"\\n\"); } }

sh *creat() {

int x,y,t,k=1;

sh *A=(sh *)malloc(sizeof(sh)); printf(\"enter mu,nu,vu\");

scanf(\"%d%d%d\ A->mu=x;A->nu=y;A->vu=t; while(k<=A->vu) {

scanf(\"%d%d%d\

A->data[k].i=x;A->data[k].j=y;A->data[k].v=t; k++; } return A; }

sh *add(sh *a,sh *b) {

int m,n,k;

sh *c=(sh *)malloc(sizeof(sh)); k=m=n=1;

if((a->mu!=b->mu)||(a->nu!=b->nu)) return NULL; while(m<=a->vu&&n<=b->vu) {

if(a->data[m].i==b->data[n].i) { if(a->data[m].j>b->data[n].j) c->data[k++]=b->data[n++]; else if(a->data[m].jdata[n].j) c->data[k++]=a->data[m++]; else { c->data[k]=a->data[m];c->data[k++].v=a->data[m++].v+b->data[n++].v; } }

else if(a->data[m].i>b->data[n].i) c->data[k++]=b->data[n++]; else c->data[k++]=a->data[m++]; }

while(m<=a->vu) c->data[k++]=a->data[m++]; while(n<=b->vu) c->data[k++]=b->data[n++]; c->mu=a->mu;c->nu=a->nu;c->vu=k-1; return c; }

sh *mul(sh *a,sh *b) {

.

.

int x,i,j,s,k=1;

sh *c=(sh *)malloc(sizeof(sh)); if(a->nu!=b->mu) return NULL; for(x=1;x<=a->mu;x++) for(i=1;i<=b->nu;i++) { s=0; for(j=1;j<=a->nu;j++) s+=chg(a,x,j)*chg(b,j,i); if(s!=0) { c->data[k].i=x;c->data[k].j=i;c->data[k].v=s;k++;} }

c->mu=a->mu; c->nu=b->nu; c->vu=k-1; return c; }

int chg(sh *a,int x,int y) {

int p;

for(p=1;p<=a->vu;p++)

if(a->data[p].i==x&&a->data[p].j==y) return a->data[p].v; return 0; }

main() {

sh *a,*b,*c;

printf(\"creat a:\\n\"); a=creat();

printf(\"the A:\\n\"); dis(a);

printf(\"creat b:\\n\"); b=creat();

printf(\"the B:\\n\"); dis(b); c=add(a,b);

printf(\"the A+B:\\n\");

if(add(a,b)==NULL) { printf(\"error!\\n\"); exit(0); } dis(c);

printf(\"the A*B:\\n\"); c=mul(a,b);

if(mul(a,b)==NULL) { printf(\"error!\\n\"); exit(0); } dis(c);

printf(\"\\n\"); getch();

.

.

}󰀀

.