数据结构 实验报告Word文档下载推荐.docx
《数据结构 实验报告Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构 实验报告Word文档下载推荐.docx（40页珍藏版）》请在冰点文库上搜索。
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}//Initlist_Sq
StatusListInsert_Sq（SqList&
L,inti,ElemTypee）
if（i<
1||i>
L.length+1）
returnERROR;
if（L.length>
=L.listsize）{
ElemType*newbase;
newbase=（ElemType*）realloc（L.elem,（L.listsize+LISTINCREMENT）*sizeof（ElemType））;
newbase）
exit（OVERFLOW）;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
ElemType*q=&
（L.elem[i-1]）;
for（ElemType*p=&
（L.elem[L.length-1]）;
p>
=q;
--p）{
*（p+1）=*p;
}
*q=e;
++L.length;
}//ListInsert_Sq
StatusListDelete_Sq（SqList&
L,inti）{
ElemTypee;
L.length）{
cout<
<
"
nofound!
endl;
ElemType*p=&
e=*p;
ElemType*q=L.elem+L.length-1;
for（++p;
p<
++p）
*（p-1）=*p;
--L.length;
cout<
e<
}//ListDelete_Sq
StatusListTraverse（SqList&
L）{
inti;
for（i=0;
i<
L.length;
i++）
L.elem[i]<
"
;
}//ListTraverse
StatusList_Sort_Input（SqList&
ElemTypea;
Inputthedata（if（-1）stop）:
cin>
>
a;
while（-1!
=a）{
for（i=1;
=L.length&
&
L.elem[i-1]<
i++）;
ListInsert_Sq（L,i,a）;
//ListTraverse（L）;
//cout<
cin>
}//List_Sort_Input&
ListInsert_Sq
intmain（）
{
inti,n;
SqListL;
Initlist_Sq（L）;
//ListInput（L）;
List_Sort_Input（L）;
while
（1）{
\nchecking....\n1.ListInsert_Sq\n2.ListDelete_Sq\n3.ListTraverse\n"
inputthechoice...."
n;
switch（n）{
case1:
cout<
inputthenumberanddata...."
cin>
i;
e;
ListInsert_Sq（L,i,e）;
break;
case2:
inputthedata...."
ListDelete_Sq（L,i）;
case3:
ListTraverse（L）;
}}
return0;
2.单链表
单链表是一种链式存储结构，结点中除数据域外增设一个指针域，指向直接后继结点。
通过单链表实现数据的插入、删除不需要移动数据，只需修改指针的指向。
插入操作：
1）找到待插入位置；
2）申请、填装新结点；
3）将新结点插入删除操作：
1）找到删除结点的位置；
2）删除结点
程序源代码：
iomanip>
#defineStatusbool
#defineElemTypeint
#defineLENsizeof（LNODE）
typedefstructLNODE
ElemTypedata;
LNODE*next;
}LinkList;
LinkList*Initlist（）
LinkList*head;
head=（LinkList*）malloc（sizeof（LinkList））;
head->
next=NULL;
returnhead;
}//initlist初始化
LinkList*Insert（LinkList*head,LinkList*s）
LinkList*p;
p=head;
while（p->
next!
=NULL&
p->
next->
data<
s->
data）
p=p->
next;
s->
next=p->
p->
next=s;
}//insert插入
StatusDelete（LinkList*head,LinkList*s）
head）exit（OVERFLOW）;
LinkList*p,*q;
next&
data!
=s->
q=p->
p->
next=q->
else
free（q）;
returnERROR;
returnOK;
}//Delete删除
LinkList*Create_Sort_LinkList（）
LinkList*p,*head=NULL;
Creatingalist...\n"
head=Initlist（）;
pleaseinputanumber（if（-1）stop）:
while（a!
=-1）
{
p=（LinkList*）malloc（sizeof（LinkList））;
data=a;
Insert（head,p）;
Pleaseinputanumber（if（-1）stop）:
if（p->
next==NULL）
}//createsort（&
insert）创建有序链表
StatusVisit（LinkList*head）
p=head->
if（NULL!
=p）
outputlist:
while（NULL!
{
headA=Create_Sort_LinkList（）;
Visit（headA）;
请输入你要插入的数：
Insert（headA,p）;
请输入你要删除的数：
b;
data=b;
Delete（headA,s）;
3.二叉树
二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。
遍历是二叉树的常用结构，通常有先序遍历，中序遍历，后序遍历三种。
用递归的方式实现
程序源代码：
#defineElemTypeint//顺序表的数据类型
#defineTElemTypeint//树的数据类型
#defineQElemTypeBiTree//队列的数据类型
#defineLISTINITSIZE100//顺序表的最大存储数
#defineMAXQSIZE100//队列的最大存储数
typedefstruct{
ElemType*elem;
intlength;
//当前长度
//当前分配的存储容量//（以sizeof（ElemType）为单位）
//俗称顺序表
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
{inti;
#defineMAX_TREE_SIZE100
//这里用了动态分配空间new
if（0==S.length）
{//表空
T=NULL;
//空树
ptr[1]=（BiTNode*）malloc（sizeof（BiTNode））;
ptr[1]->
data=S.elem[1];
//建立树根
T=ptr[1];
for（i=2;
=S.length-1;
{//依次建立子树
if（0==S.elem[i]）
{//数据为0表示无节点，指针为空
ptr[i]=NULL;
}
else
ptr[i]=（BiTNode*）malloc（sizeof（BiTNode））;
ptr[i]->
data=S.elem[i];
//
if（i>
=S.length/2）
{
//注意这里要对叶节点的左右指针做处理
ptr[i]->
lchild=NULL;
rchild=NULL;
}
j=i/2;
/找到结点i的双亲j
if（i==j*2）
{//左孩子
if（ptr[j]）//判断双亲是否为空
ptr[j]->
lchild=ptr[i];
//i是j的左孩子
else
{//右孩子
ptr[j]->
rchild=ptr[i];
//i是j的右孩子
returnOK;
}//CreateBitree_SqList
//树的遍历//
StatusPreOrderTraverse（BiTreeT）
{//先序遍历二叉树
if（T）
T->
//访问结点
PreOrderTraverse（T->
lchild）;
//遍历左子树
rchild）;
//遍历右子树
}//PreOrder
QElemType*base;
//指向树节点的指针数组
intfront;
intrear;
}SqQueue;
StatusInitQueue（SqQueue&
Q）
Q.base=（QElemType*）malloc（MAXQSIZE*sizeof（QElemType））;
Q.base）exit（OVERFLOW）;
Q.front=Q.rear=0;
}//InitQueue
StatusDeQueue（SqQueue&
Q,BiTree&
p）
//输出p是指针
if（Q.front==Q.rear）
returnERROR;
p=Q.base[Q.front];
Q.front=（Q.front+1）%MAXQSIZE;
}//DeQueue
StatusEnQueue（SqQueue&
Q,BiTreeT）//输入指针
if（（Q.rear+1）%MAXQSIZE==Q.front）
Q.base[Q.rear]=T;
Q.rear=（Q.rear+1）%MAXQSIZE;
}//EnQueue
StatusQueueEmpty（SqQueue&
}//QueueEmpty
StatusInOrderTraverse（BiTreeT）
{//中序遍历二叉树
InOrderTraverse（T->
}//InOrder
StatusNextOrderTraverse（BiTreeT）
{//后序遍历二叉树
NextOrderTraverse（T->
//遍历右cout<
}//NextOrder
{inti,j;
TElemTypedata;
创建一个二叉树"
BiTreeT;
//定义树
SqListS;
//顺序表
Initlist_Sq（S）;
//初始化顺序表
intarr[100]={0};
//初始化数组
do{cout<
输入结点的位置（0时结束）"
if（i!
=0）
{cout<
输入结点数据元素（0时结束）"
data;
while（data==0）{//data==0表示节点为空
结点位置不为0!
结点数据元素不为0!
cin>
if（j<
i）
j=i;
//找最大节点位置
arr[i]=data;
}while（i!
=0）;
S.elem=arr;
//用数组初始化顺序表
S.length=j+1;
//最大节点位置即表长
CreateBiTree_SqList（T,S）;
先序遍历：
PreOrderTraverse（T）;
中序遍历：
InOrderTraverse（T）;
后序遍历：
NextOrderTraverse（T）;
4.图
图结构是一种比树形结构更复杂的非线性结构。
通常用邻接矩阵或邻接表存储图结构。
所谓邻接矩阵的存储结构就是用一维数组途中结点的信息，用矩阵表示图中各结点的关系。
邻接表则是顺序存储与链式存储相结合。
实现方法：
邻接矩阵：
建立一个一维数组存储图中结点的信息。
两个结点之间若存在边关系则在相
应的矩阵中存入1，否则存入0。
邻接表：
对于图中的每个结点vi,将所有的邻接于vi的顶点vj链成一个单链表，这个单链表就成为顶点vi的邻接表，再将所有的顶点的邻接表的表头放入数组中，构成图的邻接表。
算法实现：
具体参见源程序代码。
ctime>
cstring>
#defineMAX_VERTEX_NUM20
#defineSTR_LENGTH5
typedefchar*VertexType;
typedefstructArcNode{
intadjvex;
//该弧所指向的顶点的位置
structArcNode*nextarc;
//指向下一条弧的指针
}ArcNode;
typedefstructVNode{
VertexTypedata;
//顶点信息字符串指针
ArcNode*firstarc;
//指向第一条依附该顶点的弧
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{
AdjListvertices;
intvexnum,arcnum;
//intkind;
//图的种类标志
}ALGraph;
StatusInitALGraph（ALGraph&
G）
{//图的初始化
MAX_VERTEX_NUM;
{//分配空间及指针初始化
G.vertices[i].data=（char*）malloc（STR_LENGTH*sizeof（char））;
G.vertices[i].firstarc=NULL;
//指针初始化为0
}//InitALGraph
intLocateVex（ALGraphG,char*t）
{//查找顶点在邻接表中下标位置
G.vexnum;
{//逐个比较即可
if（strcmp（G.vertices[i].data,t）==0）
returni;
return-1;
}//LocateVex
StatusBuild_AdjList（ALGraph&
G）//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表
{//图的邻接表存储建立
intv,a;
intm;
inti,j;
ArcNode*p,*q;
//指针
chart[STR_LENGTH],h[STR_LENGTH];
//临时存储顶点信息的字符串
InitALGraph（G）;
//初始化
输入顶点个数：
v;
while（v<
0）
vcan'
t<
=0!
}//顶点数不能为负
G.vexnum=v;
输入边数：
while（a<
0）
acan'
}//边数不能为负
G.arcnum=a;
输入各个顶点的信息（字符或字符串）：
cin.ignore（）;
//忽略换行符
for（m=0;
m<
m++）
顶点信息：
cin.getline（G.vertices[m].data,STR_LENGTH）;
//输入各顶点的符号
输入各个边的信息（弧头和弧尾）：
for（m=1;
=a;
{//输入各个边信息
边信息：
cou
升级会员 