数据结构实验.pdf

《数据结构实验.pdf》由会员分享，可在线阅读，更多相关《数据结构实验.pdf（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、.-实验 1C 语言补充实验有顺序表 A 和 B，其元素值均按从小到大的升序排列，要求将它们合并成一个顺序表C，且 C 的元素也是从小到大的升序排列。#includemain()int n,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+;else if(j5)for(n=j;n5;n+)ck=bn;k+;for(i=0;ik;i+)printf(%3d,ci);printf(n);求 AB#includemain()int i,j,k=0,a5,b5,c5;/A=a5,B=b5,AB=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+)if(ai=bj)ck=ai;k+;/当有元素重复时，只

3、取一个放入c 中for(i=0;ik;i+)-.word.zl.-printf(%3d,ci);printf(n);实验 2C 语言补充实验一个有序整型数组，编程将一个整型数m 插入到该数组中，使得插入后的数组任然有序。#include#define N 4main()int i,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;/

4、m和数组元素一样if(mi;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比所有元素小-.word.zl.-for(i=0;ik;i+)printf(%3d,ai);printf(n);补充实验线性表 LA 和 LB 中的数据元素按值非递减有序排序，现要求将LA 和 LB 归并为一个新的线性表 LC，且 LC中的数据元素仍按值非递减

5、有序排列。#includeint Getelem(int a, int t);/声明得到数组元素函数void ListInsert(int b, int p,int q );/声明插入数组函数main()int m,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)

6、;j+;/将较小的元素赋给新的数组else/一样的元素只要取一个ListInsert(LC,k+,ai);i+;j+;-.word.zl.-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);int Getelem(int a,int t)re

7、turn at;void ListInsert(int b,int p,int q)bp=q;实验 3输入 n 个整型数据，用链表的方法存储这些数据并输出。#include#includetypedef struct LNodeint date;struct LNode *next;LNode ,*LinkList;/此指针变量就是指 LNode 类型的构造体void CreatList(LinkList *L,int n)/顺序输入 n 个元素的值，建立头结点Lint i;LinkList p,S;/S 为暂存结点(*L)=(LinkList)malloc(sizeof(LNode);S=(

8、LinkList)malloc(sizeof(LNode);(*L)-next=NULL;S=(*L);for(i=0;idate);p-next=S-next;-.word.zl.-S-next=p;S=S-next;/S 移向下一个void PRINTF(LinkList L)/输出函数LinkList q;q=L-next;while(q)printf(%4d,q-date);q=q-next; printf(n);main()LinkList M;int n;/n 为插入数的个数printf(请输入插入数的个数n);scanf(%d,&n);printf(请输入这%d 个数n,n);C

9、reatList( &M,n);printf(该线性表顺序输出为n);PRINTF(M);实验 4约瑟夫环算法/*约瑟夫环问题是一个数学的应用问题：n 个人以编号 1，2，3n 分别表示围坐在一圆桌周围。从编号为 k 的人开场报数，数到m 的那个人出列；他的下一个人又从1 开场报数，数到 m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。*/#include#includetypedef struct Nodeint date;struct Node *next;LinkList;LinkList *CreatList(int n)/创立 n 个数的循环链表int i=1;Lin

10、kList *p,*q,*head;p=(LinkList*)malloc(sizeof(LinkList);p-date=i;head=p;for(i=2;idate= i;p-next=q;p=q;-.word.zl.-p-next=head;return head;void Print(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);void FreeNode(LinkList *L,int k,int m)/输出

11、每个第 m 的数int i,j;LinkList *p,*q;p=L;for(i=1;inext;while(p-next!=p)for(j=1;jnext;printf(%d,p-date);q-next=p-next;p=p-next;printf(%d,p-date);void main()LinkList *L;int n,k,m;printf(请输入人数，从第几个人数，数到几：n k m=n);scanf(%d %d %d,&n,&k,&m);L=CreatList(n);printf(n 个数分别为);-.word.zl.-Print(L);printf(每次出列数为);FreeN

12、ode(L,k,m);printf(n);实验 5利用栈，判断输入的括号序列是否配对，假设配对那么将序列输出，否那么输出ERROR。#include #include #define STACK_INIT_SIZE 100typedef struct SqStackchar *base;/在栈构造之前和销毁之后，base 的值为 NULLchar *top;/栈顶指针int stacksize;/当前已分配的存储空间，以元素为单元SqStack;/建立栈void InitStack(SqStack *S)/初始化栈(*S).base=(char*)malloc(STACK_INIT_SIZE*

13、sizeof(char);(*S).top=(*S).base;(*S).stacksize = STACK_INIT_SIZE;/初始存储容量int StackEmpty(SqStack S)/判断栈是否为空if(S.top=S.base) return 1;/栈为空的条件的栈顶=栈尾else return 0;void Push(SqStack *S,char e) /插入元素 e 为第一个栈顶新的元素 *(*S).top)=e;(*S).top+;void Pop(SqStack *S,char *e) /删除 S1 的栈顶元素,并输出 e(*S).top-;*e=*(*S).top);

14、main()int i;char a,e;/a 为输入元素SqStack p;-.word.zl.-InitStack(&p);/初始化栈 pprintf(请输入需要判断的括号n);a=getchar();/输入 awhile(a!=n)/printf(+%cn,a);if(a=(|a=|a=)Push(&p,a);else if(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;/*defau

15、lt不能用来判断字符*/printf($%dn,i);if(i=0)break;a=getchar();if(!StackEmpty(p)printf(括号不匹配n); /栈不为空else if(StackEmpty(p) printf(括号匹配n);/栈为空实验 6利用循环队列模拟舞伴配对问题：在舞会上，男女各自排成一队。舞会开场时，依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，那么较长的那一队中未配对的者等待下一轮舞曲，舞曲完毕后，按照先配对的先分开进入各自的队列。 假设初始男女人数及舞会的轮数由参数给出， 模拟上述舞伴配对问题。输出第 n 个舞曲男女配对的序列。#incl

16、ude#include#include#define SIZE 100/最大队列长度typedef struct NameQueuechar BoyName10;char GirlName10;NameQueue;/定义名字构造体-.word.zl.-typedef struct SqQueueNameQueue *base;/初始化动态分配空间int front;int rear;SqQueue;/定义循环队列void InitQueue(SqQueue *Q)/构造一个空队列Q-base=(NameQueue *)malloc(SIZE*sizeof(NameQueue);Q-front=

17、Q-rear=0;int QueueEmpty(SqQueue Q)/判断队列是否为空if (Q.rear=Q.front) return 1;else return 0;void EnQueue(SqQueue *Q,NameQueue e) /插入元素 e 为 Q 的新的队尾元素if (Q-rear+1)%SIZE=Q-front)/队满exit(0);elseQ-baseQ-rear=e;Q-rear=(Q-rear+1)%SIZE;/入队void DeQueue(SqQueue *Q,NameQueue *e)/ 删除 Q 的队头元素, 并用 e 返回其值if (Q-rear=Q-fr

18、ont)/队满exit(0);else(*e)=Q-baseQ-front;Q-front=(Q-front+1)%SIZE;/出队void main()int i,time,BoyNum,GirlNum;/time 为舞会曲数,BoyNum 为男生人数，Girl 为女生人数char name10;/name 字符串数组储存SqQueue Boy,Girl,Dancer;/定义 Boy,Girl,Dancer 三个队列NameQueue e1,e2;printf(请输入舞会曲数,男生人数,女生人数n);scanf(%d %d %d,&time,&BoyNum,&GirlNum);InitQue

19、ue(&Boy);InitQueue(&Girl);-.word.zl.-InitQueue(&Dancer);getchar();printf(输入男生n);for(i=1;i=BoyNum;i+)gets(e1.BoyName);/输入男生strcpy(e1.GirlName, );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

20、(第%d 配对结果为n,i);while(!QueueEmpty(Boy)&!QueueEmpty(Girl)DeQueue(&Boy,&e1);strcpy(name,e1.BoyName);/用 name 字符串存储男生DeQueue(&Girl,&e1);strcpy(e1.BoyName,name);/此时 e1 里存有男生和女生EnQueue(&Dancer,e1);printf(%s-%s,e1.BoyName,e1.GirlName);while(!QueueEmpty(Dancer)/当舞会配对完成输出舞会队列里的男女DeQueue(&Dancer,&e1);strcpy(e2

21、.BoyName,e1.BoyName);strcpy(e2.GirlName, );EnQueue(&Boy,e2);strcpy(e1.BoyName, );EnQueue(&Girl,e1);printf(n);实验 7-.word.zl.-一个 MN 的稀疏矩阵 A，用三元组的方法压缩存储该矩阵，输出该三元组及矩阵转置后的三元组。 用跳着找，顺着存方法#include#define M 10/数组 A 的行数#define N 10/数组 A 的列数#define SIZE 100/假设非零元个数的最大值为100typedef structint i,j;/该非零元的行下标和列下标in

22、t e;/该非零元素的值Three; /(三元组)typedef structThree dataSIZE+1;/非零元三元组,data0不用int mu,nu,tu;/矩阵的行数，列数和非零元个数TSMatrix;/矩阵void zhuanzhi(TSMatrix A,TSMatrix *T)/采用三元组表存储表示， 求稀疏矩阵 A 的转置矩阵Tint p,q,col;/ p 为现在三元组下标，q 为原三元组下标,col 列数T-mu=A.nu;/ 矩阵 T 的行数等于矩阵 A 的列数T-nu=A.mu;/ 矩阵 T 的列数等于矩阵 A 的行数T-tu=A.tu;/ 矩阵 T 的非零元素数等

23、于矩阵A 的非零元素数if(A.tu)/ 把 A 中每一个非零元素转换到T 中相应位置 q=0;for(col=0;col=A.nu;col+)/ 按列号作扫描，做 col 趟for(p=0;pdataq.i= col;/ 新三元组的行号T-dataq.j= A.datap.i;/ 新三元组的列号T-dataq.e= A.datap.e;/ 新三元组的值q+;void Create(TSMatrix *A)/ 创立一个稀疏矩阵A int aMN,i,j, k=0;/ k 为三元组的下标int m,n;/ m、n 为 A 矩阵的行、列数printf(请输入矩阵的行、列数:n);scanf(%d

24、%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+1;/ 该元素的行位置赋给三元组的iA-datak.j=j+1;/ 该元素的列位置赋给三元组的jA-datak.e=aij;/ 该元素的值赋给三元组的ek+;/ 三元组下标加一A-mu=m;A-nu=n;A-tu=k;/ 给稀疏矩阵的行数，列数和非零元个数赋值void PRINT(TSMatrix A)int i;/k 为计数器for(i=0;iA.tu;i+)printf(%4d%4d%

25、4dn,A.datai.i,A.datai.j,A.datai.e);/ 依次输出三元组printf(n);main()TSMatrix A,T;Create(&A);/ 创立一个稀疏矩阵Aprintf(A 的三元组表(下标从 1 开场):n);printf(ijen);PRINT(A);zhuanzhi(A,&T);/ 采用三元组表存储表示，求稀疏矩阵 A 的转置矩阵Tprintf(转置后的三元组表(下标从 1 开场):n);printf(ijen);PRINT(T);实验 8一个 MN 的稀疏矩阵 A，用三元组的方法压缩存储该矩阵，输出该三元组及矩阵转置后的三元组。 用顺着找，跳着存方法#

26、include#define M 10/数组 A 的行数#define N 10/数组 A 的列数#define SIZE 100/假设非零元个数的最大值为100typedef structint i,j;/该非零元的行下标和列下标int e;/该非零元素的值Triple; /(三元组)typedef structTriple dataSIZE+1;/非零元三元组,data0不用int mu,nu,tu;/矩阵的行数，列数和非零元个数TSMatrix;/矩阵-.word.zl.-void FastTransposeSMatrix(TSMatrix A,TSMatrix *T)/采用三元组表存储

27、表示，求稀疏矩阵A 的转置矩阵 Tint t,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;for(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列的第一个非零元在新的三元组中的位置*

28、/for(p=0;pdataq.i=col;T-dataq.j=A.datap.i;T-dataq.e=A.datap.e;cpotcol+;void Create(TSMatrix *A)/ 创立一个稀疏矩阵A int aMN,i,j, k=0;/ k 为三元组的下标int m,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;/ 该

29、元素的行下标赋给三元组的iA-datak.j=j;/ 该元素的列下标赋给三元组的jA-datak.e=aij;/ 该元素的值赋给三元组的ek+;/ 三元组下标加一-.word.zl.-A-mu=m;A-nu=n;A-tu=k;/ 给稀疏矩阵的行数， 列数和非零元个数赋值void PRINT(TSMatrix A)int k;for(k=0;kA.tu;k+)printf(%4d%4d%4dn,A.datak.i,A.datak.j,A.datak.e);/ 依次输出三元组printf(n);main()TSMatrix A,T;Create(&A);/ 创立一个稀疏矩阵 Aprintf(A 的

30、三元组表:n);printf(ijen);PRINT(A);FastTransposeSMatrix(A,&T);/ 采用三元组表存储表示，求稀疏矩阵A 的转置矩阵 Tprintf(转置后的三元组表:n);printf(ijen);PRINT(T);实验 9有 10 个字符型数据，试将这十个字符按照从上到下、从左到右的次序建立一个二叉链表，并依次输出这10个字符。提示： 链表存储二叉树通常用具有两个指针域的链表作为二叉树的存储构造， 其中每个结点由数据域Data、左指针域和右指针域组成。两个指针域分别指向该结点的左、右孩子。假设某结点没有左孩子或右孩子，那么对应的指针域为空。最后，还需要一个链

31、表的头指针指向根结点。先序、后序遍历并输出用递归方法。#include#includetypedef struct BiTNodechar data;struct BiTNode *lchild, *rchild;/左右孩子指针BiTNode,*BiTree;BiTree CreateBiTree(BiTree T)char a; /scanf(%c,&a);a=getchar();if(a=0) T=NULL;else-.word.zl.-T=(BiTree)malloc(sizeof(BiTNode);T-data=a;/生成跟结点T-lchild=CreateBiTree(T-lchil

32、d);/构造左子树T-rchild=CreateBiTree(T-rchild);/构造右子树return T;void PreOrder(BiTree T)/先序遍历if(T)printf(%c,T-data);PreOrder(T-lchild);PreOrder(T-rchild);void InOrder(BiTree T)if(T)InOrder(T-lchild);printf(%c,T-data);InOrder(T-rchild);void PostOrder(BiTree T)if(T)PostOrder(T-lchild);PostOrder(T-rchild);print

33、f(%c,T-data);void main()BiTree L;printf(请输入二叉树序列n);L=(BiTree)malloc(sizeof(BiTNode);L=CreateBiTree(L);printf(n 递归方法n);printf(先序遍历二叉树序列为n);-/中序遍历/后序遍历.word.zl.-PreOrder(L);printf(n);printf(中序遍历二叉树序列为n);InOrder(L);printf(n);printf(后序遍历二叉树序列为n);PostOrder(L);printf(n);实验 11将一个二叉树，中序遍历并输出用非递归方法 。#include

34、#includetypedef struct BiTNodechar data;int flag;/标志变量struct BiTNode *lchild, *rchild;/左右孩子指针BiTNode,*BiTree;#define SIZE 100typedef struct SqStackBiTree *base;/在栈构造之前和销毁之后，base 的值为 NULLBiTree *top;/栈顶指针int stacksize;/当前已分配的存储空间，以元素为单元SqStack;/建立栈void InitStack(SqStack *S)/初始化栈S-base=(BiTree *)mallo

35、c(SIZE *sizeof(BiTNode);S-top=S-base;S-stacksize = SIZE;/初始存储容量int StackEmpty(SqStack S)/判断栈是否为空if(S.top=S.base) return 1; /栈为空的条件的栈顶=栈尾else return 0;void Push(SqStack *S,BiTree e)/插入元素 e 为第一个栈顶新的元素 *(*S).top)=e;(*S).top+;-.word.zl.-void Pop(SqStack *S,BiTree *e)/删除 S1 的栈顶元素,并输出 e(*S).top-;*e=*(*S).

36、top);BiTree CreateBiTree(BiTree T)char a;/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);/构造右子树return T;void PreOrder(BiTree T)/先序非递归BiTree p;SqStack S;InitStack(&S);p=(BiTree)malloc(si

37、zeof(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;/左子树为空, 进右子树void InOrder(BiTree T)/中序非递归-.word.zl.-BiTree p;SqStack S;InitStack(&S);p=(BiTree)malloc(sizeof(BiTNode);p=T;while(p|!StackEmpty(S)if(p)Push(&S,p);/预留 p 指针在栈中p=p-lchi

38、ld;elsePop(&S,&p);printf(%c,p-data);p=p-rchild;/ 左子树为空, 进右子树void PostOrder(BiTree T)/后序非递归BiTree p;SqStack S;InitStack(&S);p=(BiTree)malloc(sizeof(BiTNode);p=T;while(p|!StackEmpty(S)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 压

39、入栈p=p-rchild;else-.word.zl.-printf(%c,p-data);p=NULL;/把 p 赋为空是表示当前结点处理完毕需要从栈中弹出下个结点void main()BiTree L;printf(请输入二叉树序列n);L=(BiTree)malloc(sizeof(BiTNode);L=CreateBiTree(L);printf(n 非递归方法n);printf(先序遍历二叉树序列为n);PreOrder(L);printf(n);printf(中序遍历二叉树序列为n);InOrder(L);printf(n);printf(后序遍历二叉树序列为n);PostOrde

40、r(L);printf(n);实验 12将一个图用邻接矩阵的形式表示并输出，并输出每个顶点的度。#include#define MAX 20typedef struct ArcCellint vexsMAX;/顶点向量int arcsMAXMAX;/邻接矩阵的元素 and 边int vexnum,arcnum;/当前顶点数和边数MGraph;/邻接矩阵CreateDG(MGraph *G)/构造有向图 Gint i,k,j;printf(输入顶点和边数n);scanf(%d %d,&(G-vexnum),&(G-arcnum);for(i=0;ivexnum;i+)G-vexsi=i; /构造

41、顶点向量，用 for 循环给每个顶点向量赋值-.word.zl.-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(输入一条边依附的顶点n);scanf(%d %d,&i,&j);G-arcsij=1;/有弧就为 1CreateUDG(MGraph *G)/构造无向图 Gint i,k,j;printf(输入顶点和边数n);scanf(%d %d,&(

42、G-vexnum),&(G-arcnum);for(i=0;ivexnum;i+)G-vexsi=i;/构造顶点向量，用 for 循环给每个顶点向量赋值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(输入一条边依附的顶点n);scanf(%d %d,&i,&j);G-arcsij=G-arcsji=1;/对称矩阵的特征void Output(MGra

43、ph G)/输出函数int i,j;for(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)printf(%3d,G.arcsij);-.word.zl.-printf(n);void Count(MGraph G)/求每个顶点的度int i,j,aMAX=0;/一维数组 afor(i=0;iG.vexnum;i+)for(j=0;jG.vexnum;j+)if(G.arcsij=1) ai+;printf(%3d,ai);void main()MGraph G;/邻接矩阵 Gprintf(构造有向图n);CreateDG(&G);printf(输出有向图的邻接矩阵

44、为：n);Output(G);printf(有向图各顶点的度依次为n);Count(G);printf(nn);printf(构造无向图n);CreateUDG(&G);printf(输出无向图的邻接矩阵为：n);Output(G);printf(无向图各顶点的度依次为n);Count(G);printf(n);实验 13用邻接表的形式存储一个图，并对该图进展深度优先搜索。#include#include#define MAX 100typedef struct ArcNode/表节点int adjvex;/该弧所指向顶点的位置struct ArcNode *next;/指向下一个弧的指针Ar

45、cNode;typedef struct Vnode/头结点-.word.zl.-int data;/顶点信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针Vnode;typedef struct ALGraph/邻接表Vnode verticeMAX;/构造体数组int vexnum;/顶点数int arcnum;/弧数ALGraph;int visitedMAX;/设置标志数组int FirstAdjVex(ALGraph G,int v) /返回第一个邻接顶点if(G.verticev.firstarc)return G.verticev.firstarc-adjv

46、ex;else return -1;intNextAdjVex(ALGraph G,int v,int w)/返回 v 中相对于 w 的下一个邻接顶点int flag=0;ArcNode *p;p=G.verticev.firstarc;while(p)if(p-adjvex!=w&!visitedp-adjvex)/这个顶点不是 w 且没有访问过flag=1;break;p=p-next;if(flag)return p-adjvex;else return -1;void DFS(ALGraph G,int v)/从第 v 个顶点出发递归地深度优化遍历图Gint w;/给第 v 个结点标记

47、，并输出该结点visitedv=1;printf(%3d,G.verticev.data);/对 v 的所有子节点 w 进展深度优先遍历-.word.zl.-for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);void DFSTraverse(ALGraph G)/对 G 进展深度优先遍历int v;for(v=0;vG.vexnum;v+)visitedv=0;/初始化，将标志数组全设为0for(v=0;vvexnum),&(G-arcnum);for(i=0;ivexnum;i+)G-verticei.da

48、ta=i;G-verticei.firstarc=NULL;/顶点的边表头指针设为空for(k=0;karcnum;k+)/建立边表printf(输入边连接的顶点n);scanf(%d %d,&i,&j);p=(ArcNode *)malloc(sizeof(ArcNode); /生成新的表结点/前插p-adjvex=j;p-next=G-verticei.firstarc;G-verticei.firstarc=p;s=(ArcNode *)malloc(sizeof(ArcNode); /生成新的表结点/前插s-adjvex=i;s-next=G-verticej.firstarc;G-v

49、erticej.firstarc=s;void CreateALG(ALGraph *G)/建立有向图的邻接表-.word.zl.-int i,j,k;ArcNode *p;printf(输入有向图顶点数和边数n);scanf(%d %d,&(G-vexnum),&(G-arcnum);for(i=0;ivexnum;i+)G-verticei.data=i;G-verticei.firstarc=NULL;/顶点的边表头指针设为空for(k=0;karcnum;k+)/建立边表printf(输入边连接的顶点n);scanf(%d %d,&i,&j);p=(ArcNode *)malloc(s

50、izeof(ArcNode); /生成新的表结点/前插p-adjvex=j;p-next=G-verticei.firstarc;G-verticei.firstarc=p;void Output(ALGraph G)/输出邻接表int i;ArcNode *p;for(i=0;iadjvex);p=p-next;printf(n);void main()ALGraph G;CreateUG(&G);printf(邻接表输出结果为：n);printf(表头 表尾n);Output(G);printf(深度优先搜索结果为：n);-.word.zl.-DFSTraverse(G);printf(n