數(shù)據(jù)結(jié)構(gòu)上機(jī)例題及答案.doc

《數(shù)據(jù)結(jié)構(gòu)上機(jī)例題及答案.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)上機(jī)例題及答案.doc（31頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

習(xí) 題 二描述以下四個(gè)概念的區(qū)別：頭指針變量，頭指針，頭結(jié)點(diǎn)，首結(jié)點(diǎn)（第一個(gè)結(jié)點(diǎn)）。解：頭指針變量和頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)或首結(jié)點(diǎn)）的指針；在首結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；首結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若單鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2.2簡(jiǎn)述線性表的兩種存儲(chǔ)結(jié)構(gòu)有哪些主要優(yōu)缺點(diǎn)及各自使用的場(chǎng)合。解：順序存儲(chǔ)是按索引直接存儲(chǔ)數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作將引起元素移動(dòng)，降低了效率；而鏈?zhǔn)酱鎯?chǔ)的元素存儲(chǔ)采用動(dòng)態(tài)分配，利用率高，但須增設(shè)表示結(jié)點(diǎn)之間有序關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入和刪除十分簡(jiǎn)單。順序存儲(chǔ)適用于線性表中元素?cái)?shù)量基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素的情況；而鏈?zhǔn)酱鎯?chǔ)適用于頻繁進(jìn)行元素動(dòng)態(tài)插入或刪除操作的場(chǎng)合。2.3 在頭結(jié)點(diǎn)為h的單鏈表中，把值為b的結(jié)點(diǎn)s插入到值為a的結(jié)點(diǎn)之前，若不存在a，就把結(jié)點(diǎn)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 設(shè)計(jì)一個(gè)算法將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解成兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B，使A中含有原鏈表中序號(hào)為奇數(shù)的元素，而B(niǎo)中含有原鏈表中序號(hào)為偶數(shù)的元素，并且保持元素原有的相對(duì)順序。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設(shè)線性表中的數(shù)據(jù)元素是按值非遞減有序排列的，試以不同的存儲(chǔ)結(jié)構(gòu)，編寫一算法，將x插入到線性表的適當(dāng)位置上，以保持線性表的有序性。 順序表； 解：本題的算法思想是：先找到適當(dāng)?shù)奈恢茫缓蠛笠圃乜粘鲆粋€(gè)位置，再將 x 插入，并返回向量的新長(zhǎng)度。實(shí)現(xiàn)本題功能的函數(shù)如下： int insert(vector A，int n，ElemType x) /*向量 A 的長(zhǎng)度為 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 插入，向量長(zhǎng)度增 1*/ return n; 單鏈表。解：本題算法的思想是先建立一個(gè)待插入的結(jié)點(diǎn)，然后依次與鏈表中的各結(jié)點(diǎn)的數(shù)據(jù)域比較大小，找到插入該結(jié)點(diǎn)的位置，最后插入該結(jié)點(diǎn)。實(shí)現(xiàn)本題功能的函數(shù)如下： node *insertorder(head，x) node *head; ElemType x; node *s，*p，*q; s=(node *)malloc(sizeof(node); /*建立一個(gè)待插入的結(jié)點(diǎn)*/ s-data=x; s-next=NULL; if (head=NULL | xdata) /*若單鏈表為空或 x 小于第一個(gè)結(jié)點(diǎn)的 date 域*/ s-next=head; /*則把 s 結(jié)點(diǎn)插入到表頭后面*/ head=s; else q=head; /*為 s 結(jié)點(diǎn)尋找插入位置，p 指向待比較的結(jié)點(diǎn)，q 指向 p 的前驅(qū)結(jié)點(diǎn)*/ p=q-next; while (p!=NULL & xp-data) /*若 x 小于 p 所指結(jié)點(diǎn)的 data 域值*/ if (xp-data) /*則退出 while 循環(huán)*/ q=p; p=p-next; s-next=p; /*將 s 結(jié)點(diǎn)插入到 q 和 p 之間*/ q-next=s; return(head); 2.6假設(shè)有A和B分別表示兩個(gè)遞增有序排列的線性表集合（即同一表中元素值各不相同）， 求A和B的交集C， 表C中也依值遞增有序排列。試以不同的存儲(chǔ)結(jié)構(gòu)編寫求得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.elemiB.elemj) j+;else if(A.elemi!=A.elemk)A.elem+k=A.elemi; /當(dāng)發(fā)現(xiàn)了一個(gè)在A,B中都存在的元素i+;j+; /且C中沒(méi)有,就添加到C中/whilewhile(A.elemk) A.elemk+=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設(shè)計(jì)一個(gè)算法求兩個(gè)遞增有序排列的線性表A和B 的差集。（每個(gè)單鏈表中不存在重復(fù)的元素）提示：即在A中而不在B中的結(jié)點(diǎn)的集合。typedef int elemtype；typedef struct linknodeelemtype 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；elser-next=p；s=p-next；r=p；r-next=NULL；p=s；s=heada；heada=heada-next；free(s)；return heada；2.8設(shè)有線性表A=(a1 ,a2 ,.,am )，B=(b1 ,b2 ,.,bn )。試寫一合并A、B為線性表C的算法，使得 (a1 ,b1 ,.,am ,bm ,bm+1 ,.,bn ) 當(dāng)mn時(shí) C (a1 ,b1 ,.,an ,bn ,an+1 ,.,am ) 當(dāng)mn時(shí)A、B和C均以單鏈表作存儲(chǔ)結(jié)構(gòu)，且C表利用A和B中結(jié)點(diǎn)空間。解：假設(shè) A，B 和 C 鏈表分別具有頭結(jié)點(diǎn)的指針 a，b 和 c。實(shí)現(xiàn)本題功能的函數(shù)如下： node *link(a，b) node *a，*b; node *r，*s，*p，*q，*c; c=(node *)malloc(sizeof(node); /*建立一個(gè)頭結(jié)點(diǎn)*/ r=c;p=a;q=b; while (p!=NULL | q!=NULL) if (p!=NULL) /*如果 A 鏈表還存在可取的結(jié)點(diǎn)，則復(fù)制一個(gè)同樣的結(jié)點(diǎn)鏈接到 C 中*/ s=(node *)malloc(sizeof(node); s-data=p-data; r-next=s; r=s; p=p-next; if (q!=NULL) /*如果 B 鏈表還存在可取的結(jié)點(diǎn)，則復(fù)制一個(gè)同樣的結(jié)點(diǎn)鏈接到 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; /*刪除頭結(jié)點(diǎn)*/ free(s); return(c); 2.9試用兩種線性表的存儲(chǔ)結(jié)構(gòu)來(lái)解決約瑟夫問(wèn)題。設(shè)有n個(gè)人圍坐在圓桌周圍，現(xiàn)從第s個(gè)人開(kāi)始報(bào)數(shù)，數(shù)到第m個(gè)人出列，然后從出列的下一個(gè)人重新開(kāi)始報(bào)數(shù)，數(shù)到第m個(gè)人又出列，如此重復(fù)直到所有的人全部出列為止。例如當(dāng)n=8,m=4,s=1,得到的新序列為：4，8，5，2，1，3，7，6。寫出相應(yīng)的求解算法。解：先構(gòu)造一個(gè)循環(huán)鏈表nodetype *crea(int n) nodetype *s,*r,*h; int I; for (i=1;idata=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已知單鏈表中的數(shù)據(jù)元素含有三類字符（即：字母字符、數(shù)字字符和其它字符），試編寫算法構(gòu)造三個(gè)環(huán)形鏈表，使每個(gè)環(huán)形鏈表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。解：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=A&cnext=p;ra=p; else if(c=0&cnext=p;rb=p; else rc-next=p;rc=p; p=p-next; ra-next=ha;rb-next=hb;rc-next=hc; 2.11假設(shè)有一個(gè)循環(huán)鏈表的長(zhǎng)度大于1，且表中既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知p為指向鏈表中某結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除結(jié)點(diǎn)p 的前趨結(jié)點(diǎn)。解：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假設(shè)有一個(gè)單向循環(huán)鏈表，其結(jié)點(diǎn)含三個(gè)域：pre、data和next， 每個(gè)結(jié)點(diǎn)的pre值為空指針，試編寫算法將此鏈表改為雙向環(huán)形鏈表。分析：在遍歷單鏈表時(shí)，可以利用指針記錄當(dāng)前訪問(wèn)結(jié)點(diǎn)和其前驅(qū)結(jié)點(diǎn)。知道了當(dāng)前訪問(wèn)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)位置，就可以給當(dāng)前訪問(wèn)結(jié)點(diǎn)的前驅(qū)指針賦值。這樣在遍歷了整個(gè)鏈表后，所有結(jié)點(diǎn)的前驅(qū)指針均得到賦值。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; pre=p; p=p-next; p-pre=pre; 2.13設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644（10），A22存放位置在676（10），每個(gè)元素占一個(gè)地址空間，求A33（10）存放在什么位置？分析 根據(jù)二維數(shù)組的地址計(jì)算公式：LOC(i,j)=LOC(0,0 )+n*i+j*s，首先要求出數(shù)組第二維的長(zhǎng)度，即n值。解 因?yàn)長(zhǎng)OC(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 設(shè)稀疏矩陣采用十字鏈表結(jié)構(gòu)表示。試寫出實(shí)現(xiàn)兩個(gè)稀疏矩陣相加的算法。 解：依題意，C=A+B，則 C 中的非零元素 cij只可能有 3 種情況：或者是 aij+bij，或者是 aij(bij=0)或者是 bij(aij=0)。因此，當(dāng) B 加到 A 上時(shí)，對(duì) A 矩陣的十字鏈表來(lái)說(shuō)，或者是改變結(jié)點(diǎn)的 val 域值(a+b0)，或者不變(b=0)，或者插入一個(gè)新結(jié)點(diǎn)(a=0)，還可能是刪除一個(gè)結(jié)點(diǎn)(aij+bij=0)。整個(gè)運(yùn)算可從矩陣的第一行起逐行進(jìn)行。對(duì)每一行都從行表頭出發(fā)分別找到 A 和 B 在該行中的第一個(gè)非零元素結(jié)點(diǎn)后開(kāi)始比較，然后按 4 種不同情況分別處理（假設(shè) pa 和 pb 分別指向 A 和 B 的十字鏈表中行值相同的兩個(gè)結(jié)點(diǎn)）： 若 pa-col=pb-col 且 pa-val+pb-val0，則只要將 aij+bij的值送到 pa 所指結(jié)點(diǎn)的值域中即可。（2）若 pa-col=pb-col 且 pa-val+pb-val=0，則需要在 A 矩陣的十字鏈表中刪除pa 所指結(jié)點(diǎn)，此時(shí)需改變同一行中前一結(jié)點(diǎn)的 right 域值，以及同一列中前一結(jié)點(diǎn)的 down域值。 （3）若 pa-colcol 且 pa-col0（即不是表頭結(jié)點(diǎn)），則只需要將 pa 指針往右推進(jìn)一步，并重新加以比較。 （4）若 pa-colpb-col 或 pa-col=0，則需要在 A 矩陣的十字鏈表中插入一個(gè)值為bij 的結(jié)點(diǎn)。實(shí)現(xiàn)本題功能的程序如下：#include #define MAX 100 struct matnode *createmat(struct matnode *h) /*h 是建立的十字鏈表各行首指針的數(shù)組*/ int m，n，t，s，i，r，c，v; struct matnode *p，*q; printf(行數(shù) m，列數(shù) n，非零元個(gè)數(shù) t:); scanf(%d，%d，%d，&m，&n，&t); p=(struct matnode *)malloc(sizeof(struct matnode);h0=p; p-row=m; p-col=n; s=mn ? m:n; /*s 為 m、n 中的較大者*/ for (i=1;itag.next=p; p-row=p-col=0; p-down=p-right=p; hs-tag.next=h0; for (i=1;irow=r; p-col=c; p-tag.val=v; q=hr; while (q-right!=hr & q-right-colright; p-right=q-right; q-right=p; q=hc; while(q-down!=hc & q-down-rowdown; 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-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) /*根據(jù) i(行號(hào))和 j(列號(hào))找出矩陣第 i 行第 j 列的非零元素在十字鏈表中的前驅(qū)結(jié)點(diǎn)*/ int i，j; struct matnode *h; struct matnode *d; d=hj; while (d-down-col!=0 & d-down-rowdown; 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(兩個(gè)矩陣不是同類型的，不能相加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-colpb-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(h0); main() struct matnode *hm，*hm1，*hm2; struct matnode *hMAX，*h1MAX; printf(第一個(gè)矩陣:n); hm1=createmat(h); printf(第二個(gè)矩陣:n); hm2=createmat(h1); hm=addmat(hm1，hm2，h); prmat(hm); 第二章上機(jī)內(nèi)容 1.設(shè)計(jì)一個(gè)程序，生成兩個(gè)按值非遞減有序排列的線性表LA和LB，再將LA和LB歸并為一個(gè)新的線性表LC，且LC中的數(shù)據(jù)仍按值非遞減有序排列，輸出線性表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 bhmrxyzzyyxsrpmlhhdb 2. 生成兩個(gè)多項(xiàng)式PA和PB，求PA和PB之和，輸出“和多項(xiàng)式”。解：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-expq-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設(shè)計(jì)一個(gè)統(tǒng)計(jì)選票的算法，輸出每個(gè)候選的得票結(jié)果（假設(shè)采用單鏈表存放選票，候選人編號(hào)依次為1，2，3，N，且每張選票選且只選一人）提示：以單鏈表存放選票，每個(gè)結(jié)點(diǎn)的data域存放該選票所選的候選人。用一個(gè)數(shù)組a統(tǒng)計(jì)得票結(jié)果。typedef int elemtype；typedef struct linknodeelemtype data；struct linknode *next； nodetype；nodetype *create()elemtype d；nodetype h=NULL,*s,*t；int I=1；printf（“建立一個(gè)單鏈表n”）；while (1)printf（“輸入第%d節(jié)點(diǎn)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；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；IN；I+)aI=0；nodetype *head；head=create()；sat(head,a)；printf（“候選人：”）；for (I=1；I=N；I+) printf( “%3d”,i)；printf（“n得票數(shù)：”）；for (I=1；I=N；I+)printf( “%3d”,ai)；printf( “n”）； 4. 編寫一算法來(lái)解決約瑟夫問(wèn)題。設(shè)有n個(gè)人圍坐在圓桌周圍，現(xiàn)從第s個(gè)人開(kāi)始報(bào)數(shù)，數(shù)到第m個(gè)人出列，然后從出列的下一個(gè)人重新開(kāi)始報(bào)數(shù)，數(shù)到第m個(gè)人又出列，如此重復(fù)直到所有的人全部出列為止。例如當(dāng)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;idata=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(“%dn”,p-data);void main() int n,k; nodetype *h; scanf(“%d”,&n); scanf(“%d”,&m); h=crea(n); jese(h,m);* 5設(shè)計(jì)一個(gè)算法求A和B兩個(gè)單鏈表表示的集合的交集、并集、差集。/*設(shè)計(jì)一個(gè)算法求A和B兩個(gè)單鏈表表示的集合的交集。*/#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(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; 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 jiaojin); 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(kongjin);exit(0); p=C; while(p!=NULL) printf(%d ,p-data);p=p-next; printf(n); getch();/*設(shè)計(jì)一個(gè)算法求A和B兩個(gè)單鏈表表示的集合的并集。*/#define NULL 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;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-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 bingjin); p=C; while(p!=NULL) printf(%d ,p-data); p=p-next; printf(n); getch();/*設(shè)計(jì)一個(gè)算法求A和B兩個(gè)單鏈表表示的集合的差集。*/#define NULL 0typedef 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,&n); while(n!=0) s=(Linklist)malloc(sizeof(struct lnode);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&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稀疏矩陣運(yùn)算器基本要求：以“帶行邏輯鏈接信息”的三元組順序表表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)果的矩陣則以通常的陣列形式列出。#define NULL 0#define maxsize 100typedef struct int i,j,v;jd;typedef struct jd datamaxsize; int mu,nu,vu;sh;void dis(sh *B) int x,y,p=1; for(x=1;xmu;x+) for(y=1;ynu;y+) if(x=B-datap.i&y=B-datap.j) printf(%-3d ,B-datap.v); p+;