大学《数据结构》(C语言版)课程实验题目及参考代码 鲁东大学by ZYC.doc

数据结构实验实验一 线性表的基本操作实验二 栈和队列实验三 二叉树的操作实验四 图的遍历实验五 查找实验六 排序实验一 线性表的基本操作（1）实验要求：分别采用线性表的两种存储结构（顺序存储结构、链式存储结构）来实现以上基本操作。（2）实验目的：了解线性表的基本概念，掌握线性表的两种存储结构顺序存储和链式存储，掌握在两种存储结构上实现线性表的基本操作，掌握用C上机调试线性表操作的基本方法。（3）实验内容：a输入一组整型元素序列，建立线性表。b实现该线性表的遍历。c在该线性表中查找某一元素,查找成功显示查找元素，否则显示查找失败。d在该线性表中删除或插入指定元素。（4）参考代码：#include#include#define SIZE 20#define MORE 10typedef struct int *base; /存储空间基址 int length; /当前长度 int listsize; /当前存储容量 SqList;void InitList(SqList &L)/构造线性表 L.base=(int *)malloc(SIZE*sizeof(int); if(!L.base) exit(0); L.listsize=SIZE; scanf(%d,&L.length); printf(输入表中元素：n); for(int i=0;iL.length;i+) scanf(%d,&L.basei); void Output(SqList L)/遍历 for(int i=0;iL.length;i+) printf(%5d,L.basei); printf(n); void Locate(SqList L,int &e)/查找 int i; for(i=0;iL.length) printf(查找失败n);void Delete(SqList &L,int i,int &e)/删除第i个元素 int j; if(iL.length) exit(0); e=L.basei-1; for(j=i-1;jL.length;j+) L.basej=L.basej+1; L.length-;void Insert(SqList &L,int i,int e)/插入 SqList q,p; int j; if(iL.length+1) exit(0); if(L.length=L.listsize) int *newbase=(int *)realloc(L.base,(L.listsize+MORE)*sizeof(int); if(!newbase) exit(0); L.base=newbase; L.listsize+=MORE; for(j=L.length-1;j=i-1;j-) L.basej+1=L.basej; L.basei-1=e; L.length+;void main() SqList La,Lb,Lc; int d,k,e; printf(输入表的长度：n); InitList(La); printf(输入要查找的数：n); scanf(%d,&d) ; Locate(La,d); printf(要删除第几个数？n); scanf(%d,&k); Delete(La,k,e); printf(删除的数为：%dn,e); printf(删除后的表为：n); Output(La); int a,b; printf(输入要插入的位置和数：n); scanf(%d%d,&a,&b); Insert(La,a,b); printf(插入后的表为：n); Output(La);实验二 栈和队列（1）实验要求：掌握栈和队列的类型定义方法；掌握栈在两种不同的存储结构上实现的五种基本操作；掌握在循环队列上实现队列的基本操作，并能灵活运用以上栈和队列知识对现实生活中的实际问题提出解决方案。 （2）实验内容：实验（一）：假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”、方括号“”和“”和花括号“”和“”，且这三种括号可按任意的次序嵌套使用，利用栈的基本运算，设计程序，判断给定的表达式中所含括号是否正确匹配。要求：首先在主调函数中将算术表达式存放在一个字符数组中，然后利用栈（可以是顺序栈，也可以是链栈）的基本操作设计一个括号匹配的函数，在主调函数中调用此函数。实验（二）：利用循环队列模拟舞伴配对问题：在舞会上，男、女各自排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。要求：从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。（3）参考代码：实验（一）#include#include #define STACK_INIT_SIZE 100#define STACKINCREHENT 10 /栈类型定义typedef struct char *base; char *top ; int stacksize;Sqlist;/初始化栈void InitStack(Sqlist &S) S.base=(char *)malloc(sizeof(char)*STACK_INIT_SIZE); if(!S.base) exit(0); S.top=S.base; S.stacksize=STACK_INIT_SIZE; /判断栈是否为空int StackEmpty(Sqlist S) if(S.top=S.base) return 1; else return 0;/进栈操作void Push(Sqlist &S,char e) if(S.top-S.base =S.stacksize) S.base=(char *)realloc(S.base,sizeof(char)*(STACKINCREHENT+S.stacksize); if(!S.base) exit(0); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREHENT; *S.top=e; S.top+;/出栈操作void Pop(Sqlist &S,char &e) if(S.top=S.base) return; -S.top; e=*S.top;/括号配对检查int peidui(char *str) char *p,*c; Sqlist S; InitStack(S); for(p=str;*p;p+) if(*p=(|*p=) Push(S,*p); else if(*p=)|*p=|*p=) if(StackEmpty(S) return 0; Pop(S,*c); if(*p=)&*c!=() return 0; if(*p=&*c!=) return 0; if(*p=&*c!=) return 0; if(!StackEmpty(S) return 0; return 1;int main() char *str; int tmp; str=(a+b)*c; tmp=peidui(str); if(tmp=1) printf(配对成功); else printf(配对不成功); return 0; 实验（二）#include#include#includetypedef struct QNodechar name10;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue; void InitQueue(LinkQueue &Q) /构建一个空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(0);Q.front-next=Q.front; /InitQueuevoid EnQueue(LinkQueue &Q,char *str) /将字符串入队 QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(0);strcpy(p-name,str);p-next=NULL;Q.rear-next=p;Q.rear=p;void DeQueue(LinkQueue &Q,char *str) /将结点删除后连接到队列的后方 QueuePtr p;p=Q.front-next; strcpy(str,p-name);Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);void GetHead(LinkQueue Q,char *str) /若队列非空，取队头元素 QueuePtr p;if(Q.front!=Q.rear)p=Q.front-next; strcpy(str,p-name);void Dancer(LinkQueue &Q1,LinkQueue &Q2) /实现配对，输出配对人名单，打印下一轮等的人char str15,boy15,girl15,ch;int b,g,i,k,ls,j;printf(请输入男舞伴的人数:n);scanf(%d,&b);ch=getchar();printf(请输入男舞伴的名字:n);for(i=0;ib;i+)gets(str);EnQueue(Q1,str); printf(请输入女舞伴的人数:n);scanf(%d,&g);ch=getchar();printf(请输入女舞伴的名字:n);for(i=0;ig;i+)gets(str);EnQueue(Q2,str);printf(请输入舞会的轮数:n);scanf(%d,&ls);if(bg)k=b;else k=g;for(i=0;ils;i+)printf(第%d轮数配对如下:n,i+1);for(j=0;jk;j+)DeQueue(Q1,boy); DeQueue(Q2,girl);printf(%s%sn,boy,girl);EnQueue(Q1,boy); EnQueue(Q2,girl);if(bg)GetHead(Q2,str);printf(%s在等待n,str);else GetHead(Q1,str); printf(%s在等待n,str);int main()LinkQueue Q1,Q2; InitQueue(Q1);InitQueue(Q2);Dancer(Q1,Q2); 实验三 二叉树的操作（1）实验要求： 掌握二叉树的二叉链表的存储结构； 掌握二叉树的遍历思想；掌握二叉树的基本操作算法的程序实现。（2）实验内容：a输入根据用户的输入信息，建立二叉树的二叉链表。b利用递归和非递归实现二叉树的先序、中序、后序遍历，利用队列实现二叉树的层次遍历。c求所有叶子结点及其总数。（3）参考代码：#include #include typedef struct BiTNode int data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree; void CreateBiTree(BiTree &bt)/按先序遍历创建一个二叉树 int tmp; scanf(%d,&tmp); if(tmp=-1) bt=NULL; else bt=(BiTree)malloc(sizeof(BiTNode); if(!bt) return; bt-data=tmp; CreateBiTree(bt-lchild); CreateBiTree(bt-rchild); void InOrderTraverse(BiTree bt)/中序递归遍历 if(bt=NULL) return; else InOrderTraverse(bt-lchild); printf(%d,bt-data); InOrderTraverse(bt-rchild); void PreOrderTraverse(BiTree bt) /先序遍历二叉树 if (bt) printf(%4d,bt-data); PreOrderTraverse(bt-lchild); PreOrderTraverse(bt-rchild); void PostOrderTraverse(BiTree bt) /后序遍历二叉树 if (bt) PostOrderTraverse(bt-lchild); PostOrderTraverse(bt-rchild); printf(%4d,bt-data); #define MAXSTACK 15typedef struct /定义栈的存储结构BiTree *base;int top;SqStack; /栈操作的相关函数void InitStack(SqStack &S) S.base=(BiTree*)malloc(sizeof(BiTNode); if(!S.base) exit(0); S.top=0; void Push(SqStack &S,BiTree e) if(S.top=MAXSTACK) exit(0);S.baseS.top=e; S.top+; void Pop(SqStack &S,BiTree &e) if(S.top=0) exit(0); S.top-; e=S.baseS.top; int GetTop(SqStack S,BiTree &e) if(S.top=0) return 0; e=S.baseS.top-1; return 1; int StackEmpty(SqStack S) if (S.top=0) return 1; else return 0; void InOrderTraverse1(BiTree bt)/中序非递归遍历-用到栈 SqStack S; BiTree p; if (bt) InitStack(S); Push(S,bt); while(!StackEmpty(S) while(GetTop(S,p) & p) Push(S,p-lchild); Pop(S,p); if(!StackEmpty(S) Pop(S,p); printf(%d ,p-data); Push(S,p-rchild); /if void PreOrderTraverse1(BiTree bt) /先序遍历二叉树的非递归算法 SqStack S; BiTree p; if (bt) InitStack(S); Push(S,bt); while(!StackEmpty(S) while(GetTop(S,p) & p) printf(%4d,p-data); Push(S,p-lchild); Pop(S,p); if(!StackEmpty(S) Pop(S,p); Push(S,p-rchild); /ifvoid PostOrderTraverse1(BiTree bt) /后序遍历二叉树的非递归算法 SqStack S; BiTree p,q; if (bt) InitStack(S); Push(S,bt); while(!StackEmpty(S) while(GetTop(S,p) & p) Push(S,p-lchild); Pop(S,p); if(!StackEmpty(S) GetTop(S,p); Push(S,p-rchild); if(GetTop(S,p) & !p) Pop(S,p); /空结点出栈 Pop(S,p); printf(%4d,p-data); while(!StackEmpty(S) & GetTop(S,q) & q-rchild=p) Pop(S,p); printf(%4d,p-data); if(!StackEmpty(S) GetTop(S,p); Push(S,p-rchild); /if(!p) /if(!StackEmpty(S) /whie /if #define MAXQSIZE 100 /最大队列长度typedef struct BiTree *base; /初始化动态分配空间 int front; int rear; SqQueue; int InitQueue(SqQueue &Q)/构造一个空队列 Q.base=(BiTree *)malloc(MAXQSIZE * sizeof(BiTNode); if (! Q.base) return 0; Q.front=Q.rear=0; return 1; /InitQueue int EnQueue(SqQueue &Q,BiTree e)/插入元素e为Q的新的队尾元素 if (Q.rear+1)%MAXQSIZE=Q.front) return 0; Q.baseQ.rear=e; Q.rear=(Q.rear+1) % MAXQSIZE; return 1;int DeQueue(SqQueue &Q,BiTree &e) / 删除Q的队头元素,并用e返回其值 if(Q.front=Q.rear) return 0; e=Q.baseQ.front; Q.front=(Q.front+1) % MAXQSIZE; return 1; int EmptyQueue(SqQueue Q)/判队空 if(Q.front=Q.rear) return 1; else return 0; void LevelOrderTraverse(BiTree bt) /按层次遍历二叉树算法用到队列这种数据结构 SqQueue Q; BiTree p; if(!bt) return ; /空树 InitQueue(Q);/初始化空队列Q /p=bt; EnQueue(Q,bt); /根入队 while(!EmptyQueue(Q) DeQueue(Q,p); /队头p出队 printf(%d,p-data); /访问p if(p-lchild) EnQueue(Q,p-lchild); /p的左孩子入队 if(p-rchild) EnQueue(Q,p-rchild); /p的右孩子入队 void LeavesCount(BiTree bt,int &count)/求二叉树的叶子结点数 SqQueue Q; BiTree p; /p=bt; if(!bt) count=0; else InitQueue(Q); EnQueue(Q,bt); while(!EmptyQueue(Q) DeQueue(Q,p); if(!p-lchild & !p-rchild)count+; if(p-lchild) EnQueue(Q,p-lchild); /p的左孩子入队 if(p-rchild) EnQueue(Q,p-rchild); /p的右孩子入队 void main() BiTree bt; printf(建立二叉树:n); CreateBiTree(bt); printf(中序递归遍历二叉树：n); InOrderTraverse(bt); printf(n); printf(中序非递归遍历二叉树：n); InOrderTraverse1(bt); printf(n); printf(层次遍历二叉树：n); LevelOrderTraverse(bt); printf(n); int count=0; LeavesCount(bt,count); printf(叶子结点数为：%dn,count); 实验四 图的遍历（1）实验要求：了解有向图和无向图的概念；掌握利用邻接矩阵和邻接链表建立图的存储结构；掌握DFS、BFS的基本思想及对图的遍历操作；了解图结构在日常生活中的广泛应用。（2）实验内容：设计一个有向图和一个无向图，建立图的邻接矩阵或邻接表的存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。（3）编程思路：a.有向图采用邻接矩阵存储结构首先建立有向图的邻接矩阵存储结构，然后设计如下函数：CreateGraphM（&G）（建立有向图的邻接矩阵）、LocateVex(G, v )（查找顶点v在图G中的位置）、DFSTraverse（G）（深度优先遍历有向图）、DFS(G, v )（从第v顶点出发深度优先遍历有向图）、BFSTraverse（G）（广度优先遍历有向图）.还有队列的相关函数：InitQueue()、EmptyQueue()、EnQueue()、DeQueue()b.无向图采用邻接表存储结构首先建立无向图的邻接表存储结构，然后设计如下函数：CreateGraphAL（&G）（建立无向图的邻接表）、LocateVex(G, v )（查找顶点v在图G中的位置）、DFSTraverse（G）（深度优先遍历无向图）、DFS(G, v )（从第v顶点出发深度优先遍历无向图）、BFSTraverse（G）（广度优先遍历无向图）（4）参考代码：（一）有向图#include #include #define MAX_VERTEX_NUM 20typedef struct char vexsMAX_VERTEX_NUM; int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; int vexnum, arcnum;MGraph;int visited MAX_VERTEX_NUM;#define MAXQUEUE 20typedef struct /定义队列的存储结构int *base;int front, rear;SqQueue; /队列操作的相关函数void InitQueue(SqQueue &Q) Q.base = ( int* )malloc(sizeof( int ); if( !Q.base ) exit(0); Q.front = Q.rear = 0; void EnQueue(SqQueue &Q, int e) if( (Q.rear+1)%MAXQUEUE = Q.front) exit(0); Q.baseQ.rear = e; Q.rear = (Q.rear+1)%MAXQUEUE; void DeQueue(SqQueue &Q, int &e) if( Q.front = Q.rear ) exit(0); e = Q.baseQ.front; Q.front = (Q.front+1)%MAXQUEUE; int QueueEmpty(SqQueue Q) if( Q.front = Q.rear ) return 1; else return 0; /下面是对有向图的相关操作int LocateVex( MGraph G, char v ) /查找顶点v在图G中的位置 int i; for( i=0; iG.vexnum; i+) if( G.vexsi = v ) return i; return -1; /查找不成功 void CreateGraphM( MGraph &G ) /建立有向图的邻接矩阵 int i, j, k; char v1, v2; printf(输入有向图的顶点数及弧数：n); scanf( %d%d, &G.vexnum, &G.arcnum ); getchar(); printf(输入有向图的所有顶点：n ); for( i=0; iG.vexnum; i+ ) G.vexsi=getchar(); getchar(); for( i=0; iG.vexnum; i+ ) /初始化邻接矩阵 for( j=0; jG.vexnum; j+ ) G.arcsij=0; printf(输入有向图的所有弧：n ); for( k=0; kG.arcnum; k+ ) v1=getchar(); getchar(); v2=getchar(); getchar(); i = LocateVex( G, v1 ); j = LocateVex( G, v2 ); G.arcsij=1; void DFS( MGraph G, int v ) /从第v顶点出发深度优先遍历有向图 int k; printf( L, G.vexsv ); visitedv=1; for( k=0; kG.vexnum; k+ ) if( G.arcsvk = 1 & !visitedk ) DFS( G, k );void DFSTraverse( MGraph G ) /深度优先遍历有向图的递归算法 int v; for( v=0; vG.vexnum; v+ ) visitedv = 0; for( v=0; vG.vexnum; v+ ) if( !visitedv ) DFS( G, v ); void BFSTraverse( MGraph G ) /广度优先遍历有向图 SqQueue Q; int v, u, k; for( v=0; vG.vexnum; v+ ) visitedv = 0; InitQueue(Q); for( v=0; vG.vexnum; v+ ) if( !visitedv ) printf( L, G.vexsv); visitedv = 0; EnQueue( Q, v ); while( !QueueEmpty( Q ) DeQueue( Q, u ); for( k=0; kG.vexnum; k+ ) if( G.arcsuk = 1 & !visitedk ) printf( L, G.vexsk ); visitedk = 1; EnQueue( Q, k ); /if /while /ifvoid main() MGraph G; CreateGraphM( G ); printf( n深度优先遍历序列（递归算法）：n ); DFSTraverse( G ); printf( n广度优先遍历序列：n ); BFSTraverse( G ); printf(n);（二）无向图#include #include #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; struct ArcNode *nextarc;ArcNode; typedef struct VNode char data; ArcNode *firstarc;VNode , AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum, arcnum;ALGraph; int visited MAX_VERTEX_NUM; #define MAXQUEUE 20typedef struct /定义队列的存储结构int *base;int front, rear;SqQueue; /队列操作的相关函数void InitQueue(SqQueue &Q) Q.base = ( int* )malloc(sizeof( int ); if( !Q.base ) exit(0); Q.front = Q.rear = 0; void EnQueue(SqQueue &Q, int e) if( (Q.rear+1)%MAXQUEUE = Q.front) exit(0); Q.baseQ.rear = e; Q.rear = (Q.rear+1)%MAXQUEUE; void DeQueue(SqQueue &Q, int &e) if( Q.front = Q.rear ) exit(0); e = Q.baseQ.front; Q.front = (Q.front+1)%MAXQUEUE; int QueueEmpty(SqQueue Q) if( Q.front = Q.rear ) return 1; else return 0; /下面是对有向图的相关操作int LocateVex( ALGraph G, char v ) /查找顶点v在图G中的位置 int i; for( i=0; iG.vexnum; i+) if( G.verticesi.data = v ) return i; return -1; /查找不成功 void CreateGraphM( ALGraph &G ) /建立无向图的邻接表 int i, j, k; char v1, v2; ArcNode *pre, *p; printf(输入无向图的顶点数及边数：n); scanf( %d%d, &G.vexnum, &G.arcnum ); getchar(); printf(输入无向图的所有顶点：n ); for( i=0; iG.vexnum; i+ ) /初始化邻接表 G.v