數據結構實驗

1、實驗1 (C語言補充實驗)有順序表A和B,其元素值均按從小到大的升序排列，要求將它們合并成一個順序表C,且C的元素也是從小到大的升序排列。#includemain()intn,m,i=0,j=0,k=0,a5,b5,c10;/*必須設個m做為數組的輸入的計數器，不能用 i ，不然進行到 while 時 i 直接為 5*/ for(m=0;m=4;m+)scanf(%d,&am);/輸入數組afor(m=0;m=4;m+)scanf(%d,&bm);/輸入數組bwhile(i5&j5)if(aibj)ck=bj;k+;j+;elseck=ai;k+;i+;j+;/使輸入的兩組數組中相同的數只輸出

2、一個if(i5)for(n=i;n5;n+)ck=an;k+; elseif(j5) for(n=j;n5;n+)ck=bn;k+; for(i=0;ik;i+) printf(%3d,ci); printf(n);求AQB#include main()inti,j,k=0,a5,b5,c5;/A=a5,B=b5,An B=c5for(i=0;i5;i+)scanf(%d,&ai);/輸入 a 數組for(i=0;i5;i+)scanf(%d,&bi);/輸入 b 數組for(i=0;i5;i+) for(j=0;j5;j+)當有元素重復時，只取一個放入 c 中if(ai=bj)ck=ai;k

3、+;/for(i=0;ik;i+)printf(%3d,ci);printf(n);實驗 2(C 語言補充實驗)已知一個有序整型數組，編程將一個整型數m插入到該數組中，使得插入后的數組任然有序。#include#defineN4main()inti,j,m,k,aN+1;/k為最后輸出數組的長度變量printf( 請輸入有序整型數組 a%dn,N);for(i=0;iN;i+)scanf(%d,&ai);printf( 請輸入整型數 mn); scanf(%d,&m);if(a0a1)/ 遞增有序數組for(i=0;iN;i+)if(m=ai)k=N;break;/m 和數組元素相同if(mi

4、;j-)aj=aj-1;ai=m;k=N+1;break;if(i=N)k=N+1;aN=m;/m 比所有元素大if(a0a1)/ 遞減有序數組for(i=0;iai)/m 比當前元素大，數組右移for(j=N;ji;j-)aj=aj-1;ai=m;k=N+1;break;if(i=N)k=N+1;aN=m;/m 比所有元素小for(i=0;ik;i+)printf(%3d,ai);printf(n);補充實驗已知線性表LA和LB中的數據元素按值非遞減有序排序，現要求將LA和LB歸并為一個新的線性表 LC,且LC中的數據元素仍按值非遞減有序排列。#includeintGetelem(inta,

5、intt);/ 聲明得到數組元素函數 voidListInsert(intb,intp,intq);/ 聲明插入數組函數 main()intm,i=0,j=0,k=0,LA5,LB5,LC10,ai,bj;for(m=0;m5;m+)scanf(%d,&LAm);/ 輸入 La 數組for(m=0;m5;m+)scanf(%d,&LBm);/ 輸入 Lb 數組while(i5&j5)ai=Getelem(LA,i);/ 通過函數得到數組元素bj=Getelem(LB,j);if(aibj)ListInsert(LC,k+,bj);j+;/ 將較小的元素賦給新的數組else/ 相同的元素只要取一

6、個ListInsert(LC,k+,ai);i+;j+;while(i5)此時LB的元素都比LA小ai=Getelem(LA,i);ListInsert(LC,k+,ai);i+;/ 直接將 LA 整體插入 LCwhile(j5)此時LA的元素都比LB小bj=Getelem(LB,j);ListInsert(LC,k+,bj);j+;/ 直接將 LA 整體插入 LCfor(i=0;ik;i+)printf(%3d,LCi);printf(n);intGetelem(inta,intt)returnat; voidListInsert(intb,intp,intq)bp=q; 實驗 3輸入 n

7、個整型數據，用鏈表的方法存儲這些數據并輸出。#include#include typedefstructLNodeintdate;structLNode*next;LNode,*LinkList;/ 此指針變量就是指 LNode 類型的結構體 voidCreatList(LinkList*L,intn)/ 順序輸入 n 個元素的值，建立頭結點 L inti;LinkListp,S;/S 為暫存結點(*L)=(LinkList)malloc(sizeof(LNode); S=(LinkList)malloc(sizeof(LNode);(*L)-next=NULL;S=(*L);for(i=0;

8、idate); p-next=S-next;S-next=p;S=S-next;/S 移向下一個voidPRINTF(LinkListL)/ 輸出函數LinkListq;q=L-next;while(q)printf(%4d,q-date);q=q-next; printf(n);main()LinkListM;intn;/n 為插入數的個數printf( 請輸入插入數的個數 n); scanf(%d,&n);printf(”請輸入這d個數n,n);CreatList(&M,n);printf( 該線性表順序輸出為 n);PRINTF(M);2, 3 n1 開始實驗 4 約瑟夫環(huán)算法 /* 約

9、瑟夫環(huán)問題是一個數學的應用問題：已知 n 個人(以編號 1， 分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數，數到 m的那個人出列；他的下一個人又從 報數，數到m的那個人又出列；依此規(guī)律重復下去，直到圓桌周圍的人全部出列。 */ #include#include typedefstructNodeintdate;structNode*next;LinkList;LinkList*CreatList(intn)/創(chuàng)建 n 個數的循環(huán)鏈表inti=1;LinkList*p,*q,*head;p=(LinkList*)malloc(sizeof(LinkList); p-date=i;head

10、=p;for(i=2;idate=i;p-next=q;p=q;p-next=head;returnhead;voidPrint(LinkList*L)/ 輸出 n 個數LinkList*p;p=L;printf(%d,p-date);p=p-next;while(p!=L) printf(%d,p-date);p=p-next; printf(n);輸出每個第m的數voidFreeNode(LinkList*L,intk,intm)/ inti,j;LinkList*p,*q;p=L; for(i=1;inext; while(p-next!=p) for(j=1;jnext; printf

11、(%d,p-date); q-next=p-next;p=p-next; printf(%d,p-date);voidmain()LinkList*L;intn,k,m;printf( 請輸入人數，從第幾個人數，數到幾： nkm=n);scanf(%d%d%d,&n,&k,&m);L=CreatList(n);printf(n 個數分別為 );Print(L);printf( 每次出列數為 );FreeNode(L,k,m);printf(n);實驗 5利用棧，判斷輸入的括號序列是否配對，若配對則將序列輸出，否則輸出ERROR#include#include #defineSTACK_INIT

12、_SIZE100 typedefstructSqStackchar*base;/ 在棧構造之前和銷毀之后， base 的值為 NULLchar*top;/ 棧頂指針intstacksize;/ 當前已分配的存儲空間，以元素為單元SqStack;/ 建立棧voidInitStack(SqStack*S) / 初始化棧(*S).base=(char*)malloc(STACK_INIT_SIZE*sizeof(char);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE; / 初始存儲容量intStackEmpty(SqStackS)if(S.to

13、p=S.base)return1;/ elsereturn0; voidPush(SqStack*S,chare)/ *(*S).top)=e;(*S).top+; voidPop(SqStack*S,char*e)/ (*S).top-;/ 判斷棧是否為空棧為空的條件的棧頂 =棧尾插入元素 e 為第一個棧頂新的元素刪除S1的棧頂元素，并輸出e*e=*(*S).top);main()inti;chara,e;/a 為輸入元素SqStackp;InitStack(&p);/ 初始化棧 p printf( 請輸入需要判斷的括號 n); a=getchar(); / 輸入 a while(a!=n)

14、/printf(+%cn,a); if(a=(|a=|a=)Push(&p,a); elseif(a=)|a=|a=) Pop(&p,&e);i=0;/printf(*%cn,e); switch(e)case(:if(a=)i=1;break; case:if(a=)i=1;break;case:if(a=)i=1;break;/*default不能用來判斷字符 */printf($%dn,i);if(i=0)break;a=getchar();if(!StackEmpty(p)printf( 括號不匹配 n);/ 棧不為空 elseif(StackEmpty(p)printf( 括號匹配

15、n);/ 棧為空 實驗 6利用循環(huán)隊列模擬舞伴配對問題：在舞會上，男女各自排成一隊。舞會開始 時，依次從男隊和女隊的隊頭各出一人配成舞伴。如果兩隊初始人數不等， 則較長的那一隊中未配對的者等待下一輪舞曲，舞曲結束后，按照先配對的 先分開進入各自的隊列。假設初始男女人數及舞會的輪數由參數給出，模擬 上述舞伴配對問題。輸出第 n 個舞曲男女配對的序列。#include#include#include#defineSIZE100 / 最大隊列長度 typedefstructNameQueuecharBoyName10;charGirlName10;NameQueue;typedefstructSqQ

16、ueueNameQueue*base;intfront;intrear;SqQueue;/ 定義循環(huán)隊列/ 定義名字結構體/ 初始化動態(tài)分配空間/ 構造一個空隊列voidInitQueue(SqQueue*Q)Q-base=(NameQueue*)malloc(SIZE*sizeof(NameQueue)Q-front=Q-rear=0; intQueueEmpty(SqQueueQ)if(Q.rear=Q.front)return1;elsereturn0;/ 判斷隊列是否為空 voidEnQueue(SqQueue*Q,NameQueuee)/ 插入元素 e 為 Q 的新的隊尾元素 if(

17、Q-rear+1)%SIZE=Q-front) / 隊滿 exit(0);elseQ-baseQ-rear=e;Q-rear=(Q-rear+1)%SIZE; / 入隊voidDeQueue(SqQueue*Q,NameQueue*e)刪除 Q 的隊頭元素,并用 e 返回其值if(Q-rear=Q-front)/ 隊滿exit(0);else(*e)=Q-baseQ-front;Q-front=(Q-front+1)%SIZE; / 出隊 voidmain()inti,time,BoyNum,GirlNum;Girl 為女生人數/time 為舞會曲數,BoyNum為男生人數，charname1

18、0;/name 字符串數組儲存姓名SqQueueBoy,Girl,Dancer;/ 定義 Boy,Girl,Dancer 三個隊列NameQueuee1,e2;printf( 請輸入舞會曲數 , 男生人數 , 女生人數 n); scanf(%d%d%d,&time,&BoyNum,&GirlNum);InitQueue(&Boy);InitQueue(&Girl);InitQueue(&Dancer);getchar();printf( 輸入男生姓名 n); for(i=1;i=BoyNum;i+)gets(e1.BoyName); / 輸入男生姓名 strcpy(e1.GirlName,);

19、EnQueue(&Boy,e1);printf( 輸入女生姓名 n); for(i=1;i=GirlNum;i+)gets(e1.GirlName); / 輸入女生姓名 strcpy(e1.BoyName,);EnQueue(&Girl,e1);printf(* 舞會配對順序 *n);for(i=1;i=time;i+)printf(第小配對結果為n,i);while(!QueueEmpty(Boy)&!QueueEmpty(Girl) DeQueue(&Boy,&e1);strcpy(name,e1.BoyName);/用name字符串存儲男生姓名DeQueue(&Girl,&e1);str

20、cpy(e1.BoyName,name);/ 此時 e1 里存有男生和女生姓名EnQueue(&Dancer,e1);printf(%s-%s,e1.BoyName,e1.GirlName);while(!QueueEmpty(Dancer)/ 當舞會配對完成輸出舞會隊列里的男女姓名DeQueue(&Dancer,&e1);strcpy(e2.BoyName,e1.BoyName);strcpy(e2.GirlName,);EnQueue(&Boy,e2);strcpy(e1.BoyName,);EnQueue(&Girl,e1);printf(n);實驗 7已知一個MX N的稀疏矩陣A,用三

21、元組的方法壓縮存儲該矩陣，輸出該三元組及矩陣轉置后的三元組。 (用跳著找，順著存方法)#include#defineM10/ 數組 A 的行數#defineN10/ 數組 A 的列數#defineSIZE100/ 假設非零元個數的最大值為 100 typedefstructinti,j; / 該非零元的行下標和列下標 inte;/ 該非零元素的值Three;/（ 三元組 ） typedefstructThreedataSIZE+1;/ 非零元三元組 ,data0 不用intmu,nu,tu;/矩陣的行數，列數和非零元個數TSMatrix;/（矩陣）voidzhuanzhi(TSMatrixA,

22、TSMatrix*T)/ 采用三元組表存儲表示，求稀疏矩陣 Ar的轉置矩陣 T intp,q,col;/p為現在三元組下標，q 為原三元組下標 ,col 列數T-mu=A.nu;/矩陣T的行數等于矩陣A的列數T-nu=A.mu;/矩陣T的列數等于矩陣A的行數T-tu=A.tu;/矩陣T的非零兀素數等于矩陣A的非零元素數if(A.tu)/ 把 A 中每一個非零元素轉換到 T中相應位置q=0;/ 按列號作掃描， 做 col 趟/ 在數據中找列號為 col 的三元if(A.datap.j=col)/轉置后的列數與 col 進行比較T-dataq.i=col;/ 新三元組的行號T-dataq.j=A.

23、datap.i;/新三元組的列號T-dataq.e=A.datap.e;/新三元組的值q+;voidCreate(TSMatrix*A)/創(chuàng)建一個稀疏矩陣 AintaMN,i,j,k=0;/k為三元組的下標intm,n;/m 、n為A矩陣的行、列數printf（ 請輸入矩陣的行、列數 :n）;scanf(%d%d,&m,&n); printf( 請輸入數組 a:n);for(i=0;im;i+)for(j=0;jn;j+)scanf(%d,&aij);for(i=0;im;i+)for(j=0;jn;j+)for(col=0;col=A.nu;col+) for(p=0;pdatak.i=i+

24、1;/ 該元素的行位置賦給三元組的 iA-datak.j=j+1;/ 該元素的列位置賦給三元組的 jA-datak.e=aij;/ 該元素的值賦給三元組的 e k+;/ 三元組下標加一A-mu=m;A-nu=n;A-tu=k;/ 給稀疏矩陣的行數，列數和非零元個數賦值voidPRINT(TSMatrixA)inti;/k 為計數器for(i=0;iA.tu;i+) printf(%4d%4d%4dn,A.datai.i,A.datai.j,A.datai.e);/ 依次輸出三元組printf(n);main()TSMatrixA,T;Create(&A);/ 創(chuàng)建一個稀疏矩陣 Aprintf(

25、A 的三元組表 ( 下標從 1 開始 ):n);printf(ijen);PRINT(A);zhuanzhi(A,&T);/ 采用三元組表存儲表示，求稀疏矩陣 A 的轉置矩陣 T printf(”轉置后的三元組表(下標從1開始):n);printf(ijen);PRINT(T);實驗 8已知一個MX N的稀疏矩陣A,用三元組的方法壓縮存儲該矩陣，輸出該三元組及矩陣轉置后的三元組。 (用順著找，跳著存方法)#include#defineM10 數組A的行數#defineN10數組A的列數#defineSIZE100/ 假設非零元個數的最大值為 100typedefstructinti,j;/ 該

26、非零元的行下標和列下標inte;/ 該非零元素的值Triple;/( 三元組 ) typedefstructTripledataSIZE+1;/ 非零元三元組 ,data0 不用 intmu,nu,tu;/ 矩陣的行數，列數和非零元個數TSMatrix;/ (矩陣) voidFastTransposeSMatrix(TSMatrixA,TSMatrix*T)/采用三元組表存儲表示，求稀疏矩陣A的轉置矩陣Tintt,p,q,col,numN,cpotN;T-mu=A.nu;T-nu=A.mu;T-tu=A.tu;if(T-tu)for(col=0;colA.nu;col+)numcol=0;fo

27、r(t=0;tA.tu;t+)numA.datat.j+;/ 求 A 中每一列含非零元個數cpot0=0;/ 求第 col 列中第一個非零元在新的三元組里面的序號 for(col=1;colA.nu;col+)cpotcol=cpotcol-1+numcol-1;/*numcol 表示矩陣 A 中非零 元的個數cpotcol 表示 A 中第 col 列的第一個非零元在新的三元組中的位置 */ for(p=0;pdataq.i=col;T-dataq.j=A.datap.i;T-dataq.e=A.datap.e;cpotcol+;voidCreate(TSMatrix*A) / 創(chuàng)建一個稀疏矩

28、陣 AintaMN,i,j,k=0;/k 為三元組的下標intm,n;m、n為M矩陣的行、列數printf( 請輸入矩陣的行、列數 :n);scanf(%d%d,&m,&n);printf( 請輸入行，列的數組 a:n);for(i=0;im;i+)for(j=0;jn;j+)scanf(%d,&aij);for(i=0;im;i+)for(j=0;jdatak.i=i;/ 該元素的行下標賦給三元組的 iA-datak.j=j;/ 該元素的列下標賦給三元組的 jA-datak.e=aij;/該元素的值賦給三元組的 ek+;/ 三元組下標加一A-mu=m;A-nu=n;A-tu=k;/ 給稀疏矩

29、陣的行數，列數和非零元個數賦值 voidPRINT(TSMatrixA)intk;for(k=0;kA.tu;k+) printf(%4d%4d%4dn,A.datak.i,A.datak.j,A.datak.e);/ 依次輸出三元組printf(n);main()TSMatrixA,T;Create(&A);/ 創(chuàng)建一個稀疏矩陣 A printf(A 的三元組表 :n);printf(ijen);PRINT(A);FastTransposeSMatrix(A,&T);/ 采用三元組表存儲表示，求稀疏矩陣 A 的 轉置矩陣 Tprintf( 轉置后的三元組表 :n);printf(ijen);

30、PRINT(T);實驗 9已知有 10 個字符型數據，試將這十個字符按照從上到下、從左到右的次序 建立一個二叉鏈表，并依次輸出這 10 個字符。(提示：鏈表存儲二叉樹通常用具有兩個指針域的鏈表作為二叉樹的存儲結 構，其中每個結點由數據域 Data、左指針域和右指針域組成。兩個指針域分 別指向該結點的左、右孩子。若某結點沒有左孩子或右孩子，則對應的指針 域為空。最后，還需要一個鏈表的頭指針指向根結點。 )先序、后序遍歷并 輸出(用遞歸方法) 。#include#includetypedefstructBiTNodechardata;structBiTNode*lchild,*rchild;/ 左

31、右孩子指針BiTNode,*BiTree;BiTreeCreateBiTree(BiTreeT)chara;/scanf(%c,&a);a=getchar();if(a=0)T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode);T-data=a; / 生成跟結點T-lchild=CreateBiTree(T-lchild);/構造左子樹T-rchild=CreateBiTree(T-rchild);/構造右子樹returnT;voidPreOrder(BiTreeT)/if(T)printf(%c,T-data);PreOrder(T-lchild);PreO

32、rder(T-rchild);voidInOrder(BiTreeT)/if(T)InOrder(T-lchild);printf(%c,T-data);InOrder(T-rchild);voidPostOrder(BiTreeT)/if(T)先序遍歷中序遍歷后序遍歷PostOrder(T-lchild);PostOrder(T-rchild);printf(%c,T-data);voidmain()BiTreeL;printf( 請輸入二叉樹序列 n);L=(BiTree)malloc(sizeof(BiTNode);L=CreateBiTree(L);printf(n 遞歸方法 n);p

33、rintf( 先序遍歷二叉樹序列為 n);PreOrder(L);printf(n);printf( 中序遍歷二叉樹序列為 n);InOrder(L);printf(n);printf( 后序遍歷二叉樹序列為 n);PostOrder(L);printf(n);實驗 11將一個已知二叉樹，中序遍歷并輸出(用非遞歸方法) 。#include#includetypedefstructBiTNodechardata;intflag;/ 標志變量structBiTNode*lchild,*rchild;/ 左右孩子指針BiTNode,*BiTree;#defineSIZE100typedefstruc

34、tSqStackBiTree*base;/ 在棧構造之前和銷毀之后， base 的值為 NULLBiTree*top; / 棧頂指針intstacksize;/ 當前已分配的存儲空間，以元素為單元SqStack; / 建立棧 voidInitStack(SqStack*S) /初始化棧S-base=(BiTree*)malloc(SIZE*sizeof(BiTNode);S-top=S-base;S-stacksize=SIZE; / 初始存儲容量intStackEmpty(SqStackS) / 判斷棧是否為空if(S.top=S.base)return1;/ 棧為空的條件的棧頂 =棧尾 e

35、lsereturn0;voidPush(SqStack*S,BiTreee)/ 插入元素 e 為第一個棧頂新的元素 *(*S).top)=e;(*S).top+;voidPop(SqStack*S,BiTree*e)刪除 S1 的棧頂元素,并輸出 e(*S).top-;*e=*(*S).top);BiTreeCreateBiTree(BiTreeT)chara;/scanf(%c,&a);a=getchar();if(a=0)T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode);構造左子樹構造右子樹T-lchild=CreateBiTree(T-lchild)

36、;/T-rchild=CreateBiTree(T-rchild);/ returnT;voidPreOrder(BiTreeT)/ 先序非遞歸 BiTreep;SqStackS;InitStack(&S);p=(BiTree)malloc(sizeof(BiTNode); p=T;while(p|!StackEmpty(S)if(p)printf(%c,p-data);Push(&S,p);/ 預留 p 指針在棧中 p=p-lchild;elsePop(&S,&p);p=p-rchild;/ 左子樹為空 , 進右子樹 voidInOrder(BiTreeT)/ 中序非遞歸BiTreep;Sq

37、StackS; InitStack(&S); p=(BiTree)malloc(sizeof(BiTNode);p=T; while(p|!StackEmpty(S)if(p)Push(&S,p);/ 預留 p 指針在棧中 p=p-lchild; elsePop(&S,&p);printf(%c,p-data);p=p-rchild;/ 左子樹為空 , 進右子樹voidPostOrder(BiTreeT)/ 后序非遞歸BiTreep;SqStackS;InitStack(&S);p=(BiTree)malloc(sizeof(BiTNode);p=T;while(p|!StackEmpty(S

38、)if(p)p-flag=0;Push(&S,p);/ 將 P 指針以及 flag 壓入棧p=p-lchild;elsePop(&S,&p);if(p-flag=0)p-flag=1;Push(&S,p);/ 再將 P 指針以及 flag 壓入棧p=p-rchild;elseprintf(%c,p-data);p=NULL;/ 把 p 賦為空是表示當前結點處理完畢需要從棧中彈出下個結點 voidmain()BiTreeL;printf( 請輸入二叉樹序列 n);L=(BiTree)malloc(sizeof(BiTNode);L=CreateBiTree(L);printf(n 非遞歸方法 n

39、);printf( 先序遍歷二叉樹序列為 n);PreOrder(L);printf(n);printf( 中序遍歷二叉樹序列為 n);InOrder(L);printf(n);printf( 后序遍歷二叉樹序列為 n);PostOrder(L);printf(n);實驗 12 將一個圖用鄰接矩陣的形式表示并輸出，并輸出每個頂點的度。 #include#defineMAX20 typedefstructArcCellintvexsMAX;/ 頂點向量 intarcsMAXMAX;/ 鄰接矩陣的元素 and 邊 intvexnum,arcnum;/ 當前頂點數和邊數MGraph;/ 鄰接矩陣Cr

40、eateDG(MGraph*G)/ 構造有向圖 Ginti,k,j;printf( 輸入頂點和邊數 n); scanf(%d%d,&(G-vexnum),&(G-arcnum);for(i=0;ivexnum;i+)G-vexsi=i;/ 構造頂點向量，用 for 循環(huán)給每個頂點向量賦值 printf( 構造的頂點序列為 n); for(i=0;ivexnum;i+)printf(%3d,G-vexsi);printf(n); for(i=0;ivexnum;i+)/ 初始化矩陣 for(j=0;jvexnum;j+)G-arcsij=0;for(k=0;karcnum;k+)printf(

41、輸入一條邊依附的頂點 n);scanf(%d%d,&i,&j);G-arcsij=1;/ 有弧就為 1CreateUDG(MGraph*G)/ 構造無向圖 Ginti,k,j;printf( 輸入頂點和邊數 n); scanf(%d%d,&(G-vexnum),&(G-arcnum); for(i=0;ivexnum;i+)G-vexsi=i;/ 構造頂點向量，用 for 循環(huán)給每個頂點向量賦值 printf( 構造的頂點序列為 n);for(i=0;ivexnum;i+)printf(%3d,G-vexsi);printf(n);for(i=0;ivexnum;i+)/ 初始化矩陣for(j

42、=0;jvexnum;j+)G-arcsij=0;for(k=0;karcnum;k+)printf( 輸入一條邊依附的頂點 n); scanf(%d%d,&i,&j);G-arcsij=G-arcsji=1;/ 對稱矩陣的特征 voidOutput(MGraphG)/ 輸出函數inti,j;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)printf(%3d,G.arcsij);printf(n);voidCount(MGraphG)/ 求每個頂點的度inti,j,aMAX=0;/ 一維數組 a for(i=0;iG.vexnum;i+)for(j=0;j

43、G.vexnum;j+)if(G.arcsij=1)ai+; printf(%3d,ai);voidmain()MGraphG;/ 鄰接矩陣 G printf( 構造有向圖 n); CreateDG(&G);printf( 輸出有向圖的鄰接矩陣為： n);Output(G);printf( 有向圖各頂點的度依次為 n);Count(G);printf(nn);printf( 構造無向圖 n);CreateUDG(&G);printf( 輸出無向圖的鄰接矩陣為： n);Output(G);printf( 無向圖各頂點的度依次為 n);Count(G);printf(n);實驗 13用鄰接表的形式

44、存儲一個圖，并對該圖進行深度優(yōu)先搜索。 #include#include#defineMAX100 typedefstructArcNode/ 表節(jié)點intadjvex;/ 該弧所指向頂點的位置 structArcNode*next;/ 指向下一個弧的指針 ArcNode;typedefstructVnode/ 頭結點intdata;/ 頂點信息ArcNode*firstarc;/ 指向第一條依附該頂點的弧的指針 Vnode;typedefstructALGraph/ 鄰接表VnodeverticeMAX;/ 結構體數組 intvexnum;/ 頂點數intarcnum;/ 弧數ALGraph;intvisitedMAX;/ 設置標志數組intFirstAdjVex(ALGraphG,intv)/ 返回第一個鄰接頂點 if(G.verticev.firstarc)returnG.verticev.firstarc-adjvex;elsereturn-1;intNextAdjVex(ALGraphG,intv,intw)/ 返回 v 中相對于 w 的下一個鄰接頂 點