《数 据 结 构》实 验 报 告
专 业
班 级
姓 名
学 号 学 期 指导老师
成绩：
教师评语：
学号： 姓名： 所在系： 班级： 实验名称： 线性结构基本算法的实现 实验日期 实验指导教师 刘勇 实验机房 ------------------------------------------------------------------------------------------------------
1. 实验目的：
(1) 掌握线性表顺序存储结构的基本操作：插入、删除、查找；
(2) 掌握线性表链式结构的基本操作：插入、删除、合并等运算；
（3）掌握栈和队列基本运算的算法；
（4）掌握稀疏矩阵的压缩存储的算法。
2. 实验内容：
（1）实现顺序表的创建、插入、删除和查找的操作；
（2）实现单链表 插入、删除、合并的操作；
（3）实现2个有序线性表的合并；
（4）利用顺序栈实现括号匹配的算法；
（5）实现顺序队列各种基本运算的算法；
（6）实现链栈各种基本运算的算法；（选做）
（7）实现链队列各种基本运算的算法；（选做）
（8）实现稀疏矩阵压缩存储的算法。
3．算法设计（编程思路或流程图或源代码）
内容：
1、 顺序表的插入和删除
2、 有序单链表的合并
3、 数制转换的算法实现
4、 快速转置算法的实现
4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）
5．讨论（通过实验的一些体会、学会的知识和技能等）
学号： 姓名： 所在系： 班级： 实验名称： 二叉树的基本应用 实验日期 实验指导教师 刘勇 实验机房 ------------------------------------------------------------------------------------------------------
2. 实验目的：
(1) 理解树这种数据结构。
(2)掌握二叉树二叉链表这种存储结构。
(3)完成二叉树各种基本运算的算法。
2. 实验内容：
（1）实现二叉树创建的算法。
（2）实现二叉树各种遍历算法。
（3）实现二叉树其他操作的算法，包括：统计叶子结点的个数、求二叉树的深度、线索二叉树等。
3．算法设计（编程思路或流程图）
1、 二叉树创建的算法
2、 #include <stdio.h>
3、 #include <stdlib.h>
4、 #include <malloc.h>
5、 #define MAX 20
6、 #define OK 1
7、 #define ERROR 0
8、 #define NULL 0
9、 #define OVERFLOW 0
10、 typedef char TElemType;
11、 typedef int Status;
12、 typedef struct BiTNode
13、 {
14、 TElemType data;
15、 struct BiTNode *lchild,*rchild;
16、 }BiTNode,*BiTree;
17、 BiTree CreateBiTree(BiTree T)
18、 {
19、
20、
21、
22、
23、
24、
25、
26、
27、
28、
29、
30、
31、
32、
33、
34、
35、
36、
37、
38、
39、
40、
41、
42、
43、
44、
45、
46、
47、
48、
49、
50、
51、
52、 char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { T=(BiTNode*)malloc(sizeof(BiTNode)); if(!T) exit(OVERFLOW); T->data=ch; T->lchild=CreateBiTree(T->lchild); T->rchild=CreateBiTree(T->rchild); } return T; } void LevelOrder(BiTree T) { BiTree Queue[MAX],b; int front,rear; front=rear=0; if(T) { Queue[rear++]=T; while(front!=rear) { b=Queue[front++]; printf("%2c",b->data); if(b->lchild!=NULL) Queue[rear++]=b->lchild; if(b->rchild!=NULL) Queue[rear++]=b->rchild; } } }
53、 叶子结点统计的算法 54、
55、
56、
57、
58、 #include <stdio.h> #include <stdlib.h> #include <malloc.h> #define MAX 20 #define OK 1
59、 60、 61、 62、 63、 64、 65、 66、 67、 68、 69、 70、 71、 72、 73、 74、 75、 76、 77、 78、 79、 80、 81、 82、 83、 84、 85、 86、 87、 88、 89、 90、 91、 92、 93、 94、 95、 96、 97、 98、
99、 #define ERROR 0 #define NULL 0 #define OVERFLOW 0 typedef char TElemType; typedef int Status; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree CreateBiTree(BiTree T) { char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { T=(BiTNode*)malloc(sizeof(BiTNode)); if(!T) exit(OVERFLOW); T->data=ch; T->lchild=CreateBiTree(T->lchild); T->rchild=CreateBiTree(T->rchild); } return T; } void LevelOrder(BiTree T) { BiTree Queue[MAX],b; int front,rear; front=rear=0; if(T) { Queue[rear++]=T; while(front!=rear) { b=Queue[front++]; printf("%2c",b->data); if(b->lchild!=NULL) Queue[rear++]=b->lchild;
100、
101、
102、
103、
104、
105、
106、
107、
108、
109、
110、
111、
112、
113、
114、
115、
116、
117、
118、
119、
120、
121、
122、
123、
124、
125、
126、
127、
128、
129、
130、
131、
132、
133、
134、
135、
136、
137、 if(b->rchild!=NULL) Queue[rear++]=b->rchild; } } } ***************************************************** #include <stdio.h> #include "BiTNode.h" int leafcount(BiTree bt) {/*统计二叉树bt中叶子结点个数*/ int n; if(bt==NULL) n=0; else if(bt->lchild==NULL&&bt->rchild==NULL) n=1; else n=leafcount(bt->lchild)+leafcount(bt->rchild); /*二叉树叶子结点数等于左·右子树的叶子结点数之和*/ return n; } void main() { BiTree T=NULL; int m; printf("*******构造一颗二叉树并统计叶子结点的个数*******\n"); printf("请输入所构造的二叉树的结点序列："); } T=CreateBiTree(T); if(T) { printf("二叉树建立成功！以层序遍历输出所构造的二叉树\n"); LevelOrder(T); m=leafcount(T); printf("\n该二叉树的叶子结点数是:%d\n",m); } else printf("二叉树建立不成功!!!\n");
138、 二叉树深度统计算法 139、 #include <stdio.h>
140、 141、 142、 143、 144、 145、 146、 147、 148、 149、 150、 151、 152、 153、 154、 155、 156、 157、 158、 159、 160、 161、 162、 163、 164、 165、 166、 167、 168、 169、 170、 171、 172、 173、 174、 175、 176、 177、 178、 179、
180、 #include <stdlib.h> #include <malloc.h> #define MAX 20 #define OK 1 #define ERROR 0 #define NULL 0 #define OVERFLOW 0 typedef char TElemType; typedef int Status; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree CreateBiTree(BiTree T) { char ch; scanf("%c",&ch); if(ch=='#') T=NULL; else { T=(BiTNode*)malloc(sizeof(BiTNode)); if(!T) exit(OVERFLOW); T->data=ch; T->lchild=CreateBiTree(T->lchild); T->rchild=CreateBiTree(T->rchild); } return T; } void LevelOrder(BiTree T) { BiTree Queue[MAX],b; int front,rear; front=rear=0; if(T) { Queue[rear++]=T; while(front!=rear) {
181、 182、 183、 184、 185、 186、 187、 188、 189、 190、 191、 192、 193、 194、 195、 196、 197、 198、 199、 200、 201、 202、 203、 204、 205、 206、 207、 208、 209、 210、 211、 212、 213、 214、 215、 216、 217、 218、 219、 220、
221、 b=Queue[front++]; printf("%2c",b->data); if(b->lchild!=NULL) Queue[rear++]=b->lchild; if(b->rchild!=NULL) Queue[rear++]=b->rchild; } } } ***************************************************** #include <stdio.h> #include "BiTNode.h" int depth(BITree T) {/*求二叉树深度*/ int dep1,dep2; if (T==NULL) return ERROR; else { dep1=depth(T->lchild); dep2=depth(T->rchild); return dep1>dep2?dep1+1:dep2+1; }//else }/*depth*/ void main() { BiTree T=NULL; printf("****** 构造一颗二叉树并对其进行深度统计 ******\n"); printf(" 请输入所构造二叉树的节点序列 "); T=CreateBiTree(T);/*建立一颗二叉树*/ if(T) { printf("二叉树建立成功！并以层序遍历输出二叉树\n"); LevleOrder(T); printf("\n二叉树的深度是：%d\n",depth(T)); } else
222、 printf("二叉树建立不成功！\n"); 223、
224、 }
4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）
5．讨论（通过实验的一些体会、学会的知识和技能等）
学号： 姓名： 所在系： 班级： 实验名称： 图的基本实现与应用 实验日期 实验指导教师 刘勇 实验机房 ------------------------------------------------------------------------------------------------------
3. 实验目的：
(1) 理解图这种数据结构。
(2) 掌握邻接矩阵、邻接表这种存储结构的实现方法。
(3) 完成图的遍历的算法。
2. 实验内容：
（1）实现图的邻接矩阵与邻接表结构的转换。（必做）
（2）实现图遍历的算法。（必做）
（3）实现图的拓扑排序的算法。
（4）实现图的最短路径的算法
3．算法设计（编程思路或流程图）
1、 图的邻接矩阵和邻接表创建的算法
2、 #define VEXTYPE int
3、 #define ADJTYPE int
4、 #define MAXLEN 40
5、 #include <stdio.h>
6、 #include <malloc.h>
7、 typedef struct
8、 {
9、 VEXTYPE vexs[MAXLEN];
10、 ADJTYPE arcs[MAXLEN][MAXLEN];
11、 int vexnum,arcnum;
12、 int kind;
13、 }MGRAPH;
14、 typedef struct node3
15、 16、 17、 18、 19、 20、 21、 22、 23、 24、 25、 26、 27、 28、 29、 30、 31、 32、 33、 34、 35、 36、 37、 38、 39、 40、 41、 42、 43、 44、 45、 46、 47、 48、 49、 50、 51、 52、 53、 54、
55、 { int adjvex; struct node3 *next; }EDGENODE; typedef struct { VEXTYPE vextex; EDGENODE *link; int id; }VEXNODE; typedef struct { VEXNODE adjlist[MAXLEN]; int vexnum,arcnum; int kind; }ADJGRAPH; MGRAPH create_mgraph() {/*建立图的邻接矩阵*/ int i,j,k; MGRAPH mg; mg.kind=2; printf("\n\n输入顶点数和边数: "); scanf("%d,%d",&i,&j);fflush(stdin); mg.vexnum=i; mg.arcnum=j; printf ("\n\n"); for (i=0;i<mg.vexnum; i++) { printf("输入顶点%d的值: ",i+1); scanf("%d",&mg.vexs[i]); fflush(stdin); } for(i=0;i<mg.vexnum;i++) for(j=0;j<mg.vexnum;j++) mg.arcs[i][j]=0; for(k=1;k<=mg.arcnum;k++) { printf("输入第%d条边的起始顶点和终止顶点（用逗号隔开）:",k); scanf("%d,%d",&i,&j); fflush(stdin); while(i<1||i>mg.vexnum||j<1||j>mg.vexnum)
56、 57、 58、 59、 60、 61、 62、 63、 64、 65、 66、 67、 68、 69、 70、 71、 72、 73、 74、 75、 76、 77、 78、 79、 80、 81、 82、 83、 84、 85、 86、 87、 88、 89、 90、 91、 92、 93、 94、 95、 96、 { printf("输入错，重新输入:"); scanf("%d,%d",&i,&j); mg.arcs[i-1][j-1]=1; mg.arcs[j-1][i-1]=1; return mg; } ADJGRAPH mg_to_adjg(MGRAPH mg) { int i,j,n; ADJGRAPH adjg; EDGENODE *p; n=mg.vexnum; adjg.vexnum=mg.vexnum; adjg.arcnum=mg.arcnum; for(i=0;i<n;i++) { adjg.adjlist[i].vertex=mg.vexs[i]; adjg.adjlist[i].link=NULL; for(j=0;j<n;j++) if(j!=i&&mg.arcs[i][j]==1) { p=(EDGENODE*)malloc(sizeof(EDGENODE)); p->adjvex=j; p->next=adjg.adjlist[i].link; adjg.adjlist[i].link=p; } } return adjg; } void main() {MGRAPH mg; ADJGRAPH adjg; int i,j,n; EDGENODE *p; printf("\n建立图的邻接矩阵并转换为图的邻接链表\n"); mg=create_mgraph();//建立图的邻接矩阵
97、
98、
99、
100、
101、
102、
103、
104、
105、
106、
107、
108、
109、
110、
111、
112、
113、
114、
115、
116、
117、
118、
119、
120、
121、
122、
123、
124、
125、
126、
127、
128、 printf("\n\n图的邻接矩阵显示： \n");//图的邻接矩阵显示 n=mg.vexnum; for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("<%d,%d>[%d]",i+1,j+1,mg.arcs[i][j]); printf("\n"); } adjg=mg_to_adjg(mg);//图的邻接矩阵转换为图的邻接链表 printf("\n"); printf("\n\n图的邻接链表显示： ");//图的邻接链表显示 for(i=0;i<n;i++) { printf("<%d>%d",i,adjg,adjlist[i].vertex); while(p!=NULL) { printf("->%d",p->adjvex); p=p->next; } printf("->NULL"); printf("\n"); } }
129、 图的两种遍历算法 #include <stdio.h>
#include <malloc.h>
#include "graph.h"
int visited[MAXV];
ALGraph *MatTolist(MGraph g) {
int i,j,n=g.vexnum;
ArcNode *p;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<n;i++)
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++)
for (j=n-1;j>=0;j--)
if (g.edges[i][j]!=0)
{
p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p;
}
G->n=n;
G->e=g.arcnum;
return G;
}
void DispAdj(ALGraph *G)
{
int i;
ArcNode *p;
for (i=0;i<G->n;i++)
{
p=G->adjist[i].firstarc;
if(p!=NULL)
printf("%3d",i);
while (p!NULL)
{
printf("%3d: ",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
void DFS(ALGraph *G,int v)
{
ArcNode *p;
visited[v]=1;
printf("%3d",v);
p=G->adjlist[v].firstarc;
whlie (p!=NULL)
{
if(visited[p->adjvex]==0)
DFS(G,p->adjvex);
p=p->nextarc;
}
}
void DFS1(ALGraph *G,int v)
{
int i,visited[MAXV],St[MAXV],top=-1; ArcNode *p;
for (i=0;i<G->n;i++)
visited[i]=0;
printf("%3d",v);
top++;
St[top]=v;
visited[v]=1;
while (top>-1)
{
v=St[top];
p=G->adjlist[v].firstarc;
while (p!=NULL&&visited[p->adjvex}==1) p=p->nextarc;
if(p==NULL)
top--;
else
{
v=p->adjvex;
printf("%3d",v);
visited[v]=1;
top++;St[top]=v;
}
}
printf("\n");
}
void BFS(ALGraph*G,int v)
{
ArcNode *p;
int queue[MAXV],front-0,rear=0;
int visited[MAXV];
int w,i;
for (i=0;i<G->n;i++)
visited[i]=0;
printf("%3d",v);
visited[v]=1;
rear=(rear=1)%MAXV;
queue[rear]=v;
while(front!=rear)
{
front=(front+1)%MAXV; w=queue[front];
p=G->adjlist[w].firstarc; while (p!=NULL)
{
if(visited[p->adjvex]==0) {
printf(%3d",p->adjvex); visited[p->adjvex]=1; rear=(rear+1)%MAXV; queue[rear]=p->adjvex; }
p=p->nextarc;
}
}
printf("\n");
}
void main()
{
int i,j;
MGraph g;
ALGraph *G;
int A[MAXV][5]={
{0,1,1,0,0},
{1,0,0,1,1},
{1,0,0,0,0},
{0,1,0,0,0},
{0,1,0,0,0},
};
g.vexnum=5;
g.arcnum=4;
for(i=0;i<g.vexnum;i++)
} for(j=0;j<g.vexnum;j++) g.edges[i][j]=A[i][j]; GMatToList(g); printf("图G的邻接表:\n"); DispAdj(G); printf("从顶点0开始的DFS（递归算法）: \n"); DFS(G,0); printf("\n"); printf("从顶点0开始的DFS（非递归算法）: \n"); DFS1(G,0); printf("从顶点0开始的BFS（递归算法）: \n"); BFS(G,0);
4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）
5．讨论（通过实验的一些体会、学会的知识和技能等）
学号： 姓名： 所在系： 班级： 实验名称： 查找与排序 实验日期 实验指导教师 刘勇 实验机房 ------------------------------------------------------------------------------------------------------
4. 实验目的：
(1) 理解查找与排序的各种算法。
(2) 掌握二叉排序树、哈希表查找、简单排序、快速排序的算法
2. 实验内容：
（1）顺序查找的设计与实现。
（2）折半查找的设计与实现。
（3）直接插入排序的设计与实现。
（4）快速排序的设计与实现。
3．算法设计（编程思路或流程图）
（1）
（2）
（3）
（4）
顺序查找的算法 折半查找的算法 直接插入排序算法 快速排序算法
4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）
5．讨论（通过实验的一些体会、学会的知识和技能等）