线性结构基本算法的实现-数据结构实验报告 本文关键词：数据结构，线性，算法，结构，实验
线性结构基本算法的实现-数据结构实验报告 本文简介：《数据结构》实验报告专业计算机科学与技术班级121班姓名张航学号1208010117学期2013-2014第1学期指导老师刘勇成绩：实验1234总分成绩教师评语：数据结构上机实验报告学号：1208010117姓名：张航所在系：计算机科学与技术班级：121班实验名称：线性结构基本算法的实现实验日期20
线性结构基本算法的实现-数据结构实验报告 本文内容：
《数
据
结
构》实
验
报
告
专
业
计算机科学与技术
班
级
121班
姓
名
张航
学
号
1208010117
学
期
2013-2014第1学期
指导老师
刘勇
成绩：
实验
1
2
3
4
总分
成绩
教师评语：
数据结构
上机实验报告
学号：1208010117
姓名：
张航
所在系：计算机科学与技术
班级：121班
实验名称：
线性结构基本算法的实现
实验日期
2013/11/6
实验指导教师
刘勇
实验机房
4号机房
------------------------------------------------------------------------------------------------------
1.
实验目的：
(1)
掌握线性表顺序存储结构的基本操作：插入、删除、查找；
(2)
掌握线性表链式结构的基本操作：插入、删除、合并等运算；
（3）掌握栈和队列基本运算的算法；
（4）掌握稀疏矩阵的压缩存储的算法。
2.
实验内容：
（1）实现顺序表的创建、插入、删除和查找的操作；
（2）实现单链表
插入、删除、合并的操作；
（3）实现2个有序线性表的合并；
（4）利用顺序栈实现括号匹配的算法；
（5）实现顺序队列各种基本运算的算法；
（6）实现链栈各种基本运算的算法；（选做）
（7）实现链队列各种基本运算的算法；（选做）
（8）实现稀疏矩阵压缩存储的算法。
3．算法设计（编程思路或流程图或源代码）
内容：
1、
顺序表的插入和删除
//SqList.h
#include
#include
#include
#define
ElemType
int
#define
OK
1
#define
ERROR
0
#define
OVERFLOW
0
typedef
struct
{
ElemTypeelem;
int
length;
int
listsize;
}SqList;
int
InitList
(SqListL)
{
L->elem
=
(ElemType)malloc(100
sizeof(ElemType));
if
(!L->elem)
return
OVERFLOW;
L->listsize
=
100;
L->length
=0;
return
OK;
}
int
CreateList
(SqListL,int
n)
{
int
i;
L->length
=
n;
printf
(“请输入%d个整数：/n“,L->length);
for
(i=0;ilength;i++)
scanf
(“%d“,return
OK;
}
void
TravelList
(SqListL)
{
int
i;
for
(i=0;ilength;i++)
printf
(“当前顺序表第%d个元素为：%d/n“,i+1,L->elem[i]);
}
int
InsertList
(SqListL,int
i,ElemType
e)
{
ElemTypenewbase,*p,*q;
if
(i(L->length+1))
return
ERROR;
if
(L->length
>=
L->listsize)
{
newbase
=
(ElemType)realloc(L->elem,(100+50)
sizeof(ElemType));
if
(!newbase)
return
ERROR;
L->elem
=
newbase;
L->listsize
=
100+50;
}
p=
for
(q=q>=p;q--)(q+1)
=q;p
=
e;
L->length++;
return
OK;
}
int
DelList
(SqListL,int
i,ElemType
if
(iL->length
||
L->length
==
0)
return
ERROR;
p=
x=*p;
for
(q=q>p;p++)p
=(p+1);
L->length--;
return
OK;
}
//.cpp
#include
#include
#include
“SqList.h“void
main
()
{
int
n,i;
ElemType
e,x;
SqList
sq;
SqListl
=
printf
(“*
顺
序
表
的
基
本
操
作/n“);
printf
(“计算机12117张航/n/n/n“);
printf
(“*
初始化顺序表/n“);
InitList
(l);
printf
(“成功初始化顺序表！/n/n“);
printf
(“*
建立顺序表/n“);
printf
(“输入要建立顺序表的长度：/n“);
scanf
(“%d“,CreateList
(l,n);
printf
(“成功建立顺序表！/n“);
TravelList
(l);
printf
(“/n/n“);
printf
(“*
顺序表的插入
/n“);
printf
(“输入插入位置及插入元素：/n“);
scanf
(“%d%d“,InsertList
(l,i,e);
printf
(“成功插入顺序表！/n“);
TravelList
(l);
printf
(“/n/n“);
printf
(“*
顺序表的删除
/n“);
printf
(“输入删除位置：/n“);
scanf
(“%d“,DelList
(l,i,x);
printf
(“成功删除顺序表第%d个元素%d/n“,i,x);
}
2、
有序单链表的合并
//LinkList.h
#include
#include
#include
#define
ElemType
int
#define
NULL
0
typedef
struct
LNode
{
ElemType
data;
LNodenext;
}*LinkList;
void
CreateList
(LinkList
L,int
n)
{
int
i;
LinkList
p,q;
p
=
L;
for
(i=1;idata);
q->next
=
p->next;
p->next
=
q;
p
=
p->next;
}
}
void
TravelList
(LinkList
L)
{
int
i
=
1;
LinkList
p;
p
=
L->next;
while
(p)
{
printf
(“第%d个元素为：%d/n“,i,p->data);
i++;
p
=
p->next;
}
}
void
MergeList
(LinkList
La,LinkList
Lb,LinkList
Lc)
{
LinkList
pa,pb,pc;
pa
=
La->next;
pb
=
Lb->next;
Lc=pc=La;
while
(pa
pc
=
pa;
pa
=
pa->next;
}
else
{
pc->next
=
pb;
pc
=
pb;
pb
=
pb->next;
}
}
pc->next
=
pa?
pa
:
pb;
free(Lb);
}
//.cpp
#include
#include
#include
#include“LinkList.h“void
main
()
{
LinkList
La,Lb,Lc;
int
n1,n2;
La
=
(LinkList)malloc(sizeof(LNode));
La->next
=
NULL;
Lb
=
(LinkList)malloc(sizeof(LNode));
Lb->next
=
NULL;
printf
(“*
两个有序单链表的合并操作/n“);
printf
(“计算机12117张航/n/n/n“);
printf
(“输入第一个单链表的长度：/n“);
scanf
(“%d“,printf
(“非递减顺序输入%d个整数：/n“,n1);
CreateList
(La,n1);
printf
(“第一个单链表中的元素为：/n“);
TravelList
(La);
printf
(“/n/n“);
printf
(“输入第二个单链表的长度：/n“);
scanf
(“%d“,printf
(“非递减顺序输入%d个整数：/n“,n2);
CreateList
(Lb,n2);
printf
(“第二个单链表中的元素为：/n“);
TravelList
(Lb);
printf
(“/n/n“);
printf
(“正在执行合并操作/n/n/n“);
Lc
=
La;
MergeList
(La,Lb,Lc);
printf
(“合并后单链表的元素为：/n“);
TravelList
(Lc);
}
3、
数制转换的算法实现
//SqStack.h
#include
#include
#include
#define
OK
1
#define
ERROR
0
#define
OVERFLOW
0
#define
ElemType
int
typedef
struct
{
ElemTypebase;
ElemTypetop;
int
stacksize;
}SqStack;
int
InitStack
(SqStackS)
{
S->base
=
(ElemType)malloc(20
sizeof(ElemType));
if
(!S)
return
OVERFLOW;
S->top
=
S->base;
S->stacksize
=
20;
return
OK;
}
int
Push
(SqStackS,ElemType
e)
{
if
(S->top
-
S->base
>=
S->stacksize)
{
S->base
=
(ElemType)realloc(S->base,(20+10)
sizeof(ElemType));
if
(!S->base)
return
OVERFLOW;
S->top
=
S->base
+
S->stacksize;
S->stacksize
=
20
+
10;
}(S->top++)
=
e;
return
OK;
}
int
Pop
(SqStackS,ElemType
x
=(--S->top);
return
OK;
}
//.cpp
#include
#include
#include
#include“SqStack.h“void
conversion
(int
n,int
m)
{
int
e;
SqStack
sq;
SqStacks=
InitStack
(s);
while
(n)
{
Push
(s,n%m);
n
=
n/m;
}
while
(sq.base
!=
sq.top)
{
Pop
(s,e);
printf
(“%d“,e);
}
}
void
main
()
{
int
n,m;
printf
(“*
数
制
转
换/n“);
printf
(“计算机12117张航/n/n/n“);
printf
(“输入一个10进制整数：/n“);
scanf
(“%d“,printf
(“输入需要转换的数制：/n“);
scanf
(“%d“,printf
(“正在进行转换/n/n“);
printf
(“10进制数%d转换成%d进制数为：/n“,n,m);
conversion
(n,m);
printf
(“/n“);
}
4、
快速转置算法的实现
//.cpp
#include
#include
#include
#define
OK
1
#define
ERROR
0
#define
OVERFLOW
0
#define
ElemType
int
#define
MAXSIZE
12500
typedef
struct
{
int
r,c;
ElemType
e;
}Triple;
typedef
struct
{
Triple
data[MAXSIZE];
int
rows,cols,nums;
}TSMatrix;
int
CreateMatrix
(TSMatrix
t.rows
=
5;
t.cols
=
5;
t.nums
=
0;
for
(i=0;inext
=
pa?
pa
:
pb;等价于if(pa)
pc->next=pa
else
pc->next
=
pb;
free(Lb);
这一句，返回的Lc
指向了La，所以不能free
La。Lc中的Lb的数据是从
Lb->next
开始插入的pb
=
Lb->next。Lb这个指针还指向一个链表头，所以需要free。
算法3
x
=(--S->top);此句第一次写成x
=
--S->top;导致编译出错。S->top还是一个指针，*(--S->top)才是指针所指的内容，才可以赋值给整形变量x。
算法4
调试过程中第一个大错误是将int
CreateMatrix
(TSMatrix
p
#include
#include
#define
OK
1
#define
ERROR
0
#define
OVERFLOW
0
#define
NULL
0
#define
ElemType
char
typedef
struct
BiTNode
{
ElemType
data;
struct
BiTNodelchild,*rchild;
}BiTNode,*BiTree;
int
CreateBiTree
(BiTree
scanf
(“%c“,if
(ch
==
#
)
T
=
NULL;
else
{
T
=
(BiTNode)malloc(sizeof(BiTNode));
if
(!T)
exit
(OVERFLOW);
T->data
=
ch;
CreateBiTree
(T->lchild);
CreateBiTree
(T->rchild);
}
return
OK;
}
void
LevelBiTree
(BiTree
T)
{
BiTree
Queue[20],b;
int
front,rear;
front
=
rear
=
0;
if
(T)
{
Queue[rear]
=
T;
rear
=
(rear+1)%20;
while
(front
!=
rear)
{
b
=
Queue[front];
printf
(“%2c“,b->data);
front
=
(front+1)%20;
if
(b->lchild
!=
NULL)
{
Queue[rear]
=
b->lchild;
rear
=
(rear+1)%20;
}
if
(b->rchild
!=
NULL)
{
Queue[rear]
=
b->rchild;
rear
=
(rear+1)%20;
}
}
}
}
//.cpp
#include
#include
#include
#include“BiTNode.h“void
main
()
{
BiTree
T
=
NULL;
printf
(“*
二叉树的建立与输出/n“);
printf
(“计算机12117张航/n/n/n“);
printf
(“先序遍历顺序输入二叉树的字符序列：/n“);
CreateBiTree
(T);
printf
(“层次遍历输出当前二叉树：/n“);
LevelBiTree
(T);
printf
(“/n“);
}
2、
叶子结点统计的算法
//BiTNode
//.cpp
#include
#include
#include“BiTNode.h“int
leafcount
(BiTree
T)
{
int
n;
if
(T
==
NULL)
n
=
0;
else
if
(T->lchild
==
NULL
else
n
=
leafcount
(T->lchild)
+
leafcount
(T->rchild);
return
n;
}
void
main
()
{
BiTree
T
=
NULL;
printf
(“*
统计二叉树的叶子结点/n“);
printf
(“计算机12117张航/n/n/n“);
printf
(“先序遍历顺序输入二叉树的字符序列：/n“);
CreateBiTree
(T);
printf
(“层次遍历输出当前二叉树：/n“);
LevelBiTree
(T);
printf
(“/n“);
printf
(“当前二叉树的叶子结点数是：%d/n“,leafcount
(T));
}
3、
二叉树深度统计算法
//BiTNode.h
//.cpp
#include
#include
#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;
}
}
void
main
()
{
BiTree
T
=
NULL;
printf
(“*
二叉树深度的统计/n“);
printf
(“计算机12117张航/n/n/n“);
printf
(“先序遍历顺序输入二叉树的字符序列：/n“);
CreateBiTree
(T);
printf
(“层次遍历输出当前二叉树：/n“);
LevelBiTree
(T);
printf
(“/n“);
printf
(“二叉树的深度是：%d/n“,depth
(T));
}
4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）
BiTNode.h中CreateBiTree函数最初定义为int
CreateBiTree
(BiTree
T)，导致程序运行时对main()中T赋值后LevelBiTree
(T)为空，原因是按值传递形参T和实参T占用不同内存单元，调用CreateBiTree
()时，形参发生变化然后所在内存空间被释放，而实参至始至终没发生变化。将函数按照按地址传递定义后，问题迎刃而解。
5．讨论（通过实验的一些体会、学会的知识和技能等）
通过算法2、3，我对递归回溯有了更深的体会。
数据结构
上机实验报告
学号：1208010117
姓名：
张航
所在系：计算机科学与技术
班级：
121班
实验名称：
图的基本实现与应用
实验日期
2012/12/04
实验指导教师
刘勇
实验机房
4号机房
------------------------------------------------------------------------------------------------------
3.
实验目的：
(1)
理解图这种数据结构。
(2)
掌握邻接矩阵、邻接表这种存储结构的实现方法。
(3)
完成图的遍历的算法。
2.
实验内容：
（1）实现图的邻接矩阵与邻接表结构的转换。（必做）
（2）实现图遍历的算法。（必做）
（3）实现图的拓扑排序的算法。
（4）实现图的最短路径的算法
3．算法设计（编程思路或流程图）
1、
图的邻接矩阵和邻接表创建的算法
//.cpp
#include
#include
#include
#define
VEXTYPE
int
#define
ADJTYPE
int
#define
NULL
0
#define
OK
1
#define
ERROR
0
typedef
struct
{
VEXTYPE
vexs[20];
ADJTYPE
arcs[20][20];
int
vexnum,arcnum;
}MGRAPH;
typedef
struct
ArcNode
{
int
adjvex;
struct
ArcNodenextarc;
}ArcNode;
typedef
struct
VNode
{
VEXTYPE
data;
ArcNodefirstarc;
}VNode;
typedef
struct
{
VNode
vertics[20];
int
vexnum,arcnum;
}ALGRAPH;
int
CreateMGraph
(MGRAPH
printf
(“输入顶点数和边数：/n“);
scanf
(“%d%d“,for
(i=0;i[%d]“,i+1,j+1,G.arcs[i][j]);
printf
(“/n“);
}
}
int
mg_to_alg
(MGRAPH
G,ALGRAPH
ArcNodep;
ALG.vexnum
=
G.vexnum;
ALG.arcnum
=
G.arcnum;
for
(i=0;iadjvex
=
j;
p->nextarc
=
ALG.vertics[i].firstarc;
ALG.vertics[i].firstarc
=
p;
}
}
return
OK;
}
void
OutALGraph
(ALGRAPH
ALG)
{
int
i;
ArcNodep;
printf
(“图的邻接链表显示:/n“);
for
(i=0;i%d“,i,ALG.vertics[i].data);
p
=
ALG.vertics[i].firstarc;
while
(p)
{
printf
(“->%d“,p->adjvex);
p
=
p->nextarc;
}
printf
(“->NULL/n“);
}
}
void
main
()
{
printf
(“*
图的邻接矩阵和邻接链表的建立/n“);
printf
(“计算机12117张航/n/n/n“);
MGRAPH
mg;
CreateMGraph
(mg);
OutMGraph
(mg);
printf
(“/n/n“);
ALGRAPH
alg;
mg_to_alg
(mg,alg);
OutALGraph
(alg);
}
2、
图的两种遍历算法
#include
#include
#include
#define
VEXTYPE
int
#define
ADJTYPE
int
#define
NULL
0
#define
OK
1
#define
ERROR
-1
#define
TRUE
1
#define
FALSE
0
typedef
struct
{
VEXTYPE
vexs[20];
ADJTYPE
arcs[20][20];
int
vexnum,arcnum;
int
kind;
}MGRAPH;
typedef
struct
ArcNode
{
int
adjvex;
struct
ArcNodenextarc;
}ArcNode;
typedef
struct
VNode
{
VEXTYPE
data;
ArcNodefirstarc;
}VNode;
typedef
struct
{
VNode
vertics[20];
int
vexnum,arcnum;
int
kind;
}ALGRAPH;
bool
visited[20];
int
CreateMGraph
(MGRAPH
printf
(“输入顶点数和边数：/n“);
scanf
(“%d%d“,for
(i=0;i[%d]“,i+1,j+1,G.arcs[i][j]);
printf
(“/n“);
}
}
int
mg_to_alg
(MGRAPH
G,ALGRAPH
ArcNodep;
ALG.vexnum
=
G.vexnum;
ALG.arcnum
=
G.arcnum;
for
(i=0;iadjvex
=
j;
p->nextarc
=
ALG.vertics[i].firstarc;
ALG.vertics[i].firstarc
=
p;
}
}
return
OK;
}
void
OutALGraph
(ALGRAPH
ALG)
{
int
i;
ArcNodep;
printf
(“图的邻接链表显示：/n“);
for
(i=0;i%d“,i,ALG.vertics[i].data);
p
=
ALG.vertics[i].firstarc;
while
(p)
{
printf
(“->%d“,p->adjvex);
p
=
p->nextarc;
}
printf
(“->NULL/n“);
}
}
void
DFS
(ALGRAPH
ALG,int
v)
{
ArcNodep;
visited[v]
=
1;
printf
(“%3d“,v);
p
=
ALG.vertics[v].firstarc;
while
(p)
{
if
(!visited[p->adjvex])
DFS
(ALG,p->adjvex);
p
=
p->nextarc;
}
}
void
BFS
(ALGRAPH
ALG,int
v)
{
ArcNodep;
int
queue[20],rear=0,front=0;
int
i,w;
for
(i=0;iadjvex])
{
printf
(“%3d“,p->adjvex);
visited[p->adjvex]
=
1;
rear
=
(rear+1)%20;
queue[rear]
=
p->adjvex;
}
p
=
p->nextarc;
}
}
}
void
main
()
{
printf
(“*图的遍历*/n“);
printf
(“计算机12117张航/n“);
MGRAPH
mg;
CreateMGraph
(mg);
OutMGraph
(mg);
printf
(“/n/n“);
ALGRAPH
alg;
mg_to_alg
(mg,alg);
OutALGraph
(alg);
printf
(“/n/nDFS遍历：/n“);
DFS
(alg,0);
printf
(“/n/nBFS遍历：/n“);
BFS
(alg,0);
printf
(“/n/n“);
}
4．程序调试（实验数据记录——根据程序要求输入几组不同数据，记录程序运行结果，并分析结果,分析程序运行中出现的主要错误。或对其他程序环境的使用情况的记录。注：必须认真书写）
算法1
mg_to_alg
()中语句p->nextarc
=
ALG.vertics[i].firstarc;
ALG.vertics[i].firstarc
=
p;设计简洁有效：是先将新建表结点nextarc指针指向头结点firstarc指针所指的地址，然后将头结点firstarc指针指向新建表结点。对于不考虑链表中结点顺序，只将关联结点链接在一起，上述两条语句再合适不过了。
5．讨论（通过实验的一些体会、学会的知识和技能等）
通过本实验，我了解到图的邻接矩阵的建立实则是用一个一维数组记录图中各结点信息，用一个二维数组记录各结点之间关系（边或弧的信息），然后对两数组赋值的过程；图的邻接链表的建立实则是定义一个表示图中各结点的头结点结构体，定义一个表示与图中各结点关联结点的表结点结构体，定义一个囊括图总体信息的结构体，然后对各头结点赋值（链接关联表结点）的过程。
数据结构
上机实验报告
学号：
1208010117
姓名：
张航
所在系：
计算机科学与技术
班级：
121班
实验名称：
查找与排序
实验日期
2013/12/18
实验指导教师
刘勇
实验机房
4号机房
------------------------------------------------------------------------------------------------------
4.
实验目的：
(1)
理解查找与排序的各种算法。
(2)
掌握二叉排序树、哈希表查找、简单排序、快速排序的算法
2.
实验内容：
（1）顺序查找的设计与实现。
（2）折半查找的设计与实现。
（3）直接插入排序的设计与实现。
（4）快速排序的设计与实现。
3．算法设计（编程思路或流程图）
（1）
顺序查找的算法
#include
#include
#include
#define
ElemType
int
#define
TRUE
1
typedef
struct
{
ElemTypeelem;
int
length;
}SqList;
int
CreateSqList
(SqList
s_l.elem
=
(ElemType)malloc
((n+1)*sizeof(ElemType));
printf
(“请输入%d个关