数据结构实验报告.doc

院 系： 计算机科学学院
专 业： 网络工程
年 级： 2012
课程名称： 数据结构
学 号： 2012213773
姓 名： 黄勇
指导教师： 吴立锋

2014年6月日

年级
 2012
班号
 1201
组号

 学号
 2012213773
专业
网络工程
 姓名
黄勇
实验名称
 第二章 线性表
实验室

实
验
目
的
或
要
求
  了解线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在某种存储结构上如何实现这些基本运算。在熟悉上述内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。

实
验
原
理
（
算
法
流
程
）
1、 实验内容
单链表的各种基本操作包括创建，查找，插入，删除，输出，合并等
2、存储结构描述及说明
链式存储结构
typedef struct node { char data; struct node *next; }linklist;
3、函数说明
linklist *rcrect(linklist *head) 尾插法建立单链表
void print(linklist *head) 输出函数，输出单链表。
linklist location(linklist *head) 按序号查找函数，按序号查找单链表中数据。
linklist inset(linklist *head) 插入函数，在单链表中插入数据。
linklist delet(linklist *head) 删除函数，删除单链表中的数据。
int main() 主函数，程序运行调用各子函数。
4、模块之间的调用关系
开 始
主函数
创建单链表
查找单链表数据
删除数据
输出函数
插入函数

程序清单：
#include
#include
#include
typedef struct node //定义节点类型
{
char data;
struct node *next; //因为上面结构体的类型名是struct node linklist是别名
}linklist; //一般List顺序表，linklist链表

int main()
{
int a;
linklist *head;
head=(linklist *)malloc(sizeof(linklist));
printf("请先建立单链表!\n");
linklist *rcrect(linklist *head); //调用尾插法
rcrect(head);
/*linklist *hcrect(); //或者调用头插法
hcrect();*/
for(;;)
{
printf("\n您想要对此单链表表做何种操作:\n0.退出\t1.查找\t2.插入\t3删除\n");
scanf("%d",&a);

if(a<0||a>3)
printf("您输入的数字有误，请重新输入!\n");
if(a==0) //退出
exit(0);
if(a==1)
{
linklist location(linklist *head); //调用按序号查找函数
location(head);
}
if(a==2)
{
linklist inset(linklist *head); //调用插入函数
inset(head);
}
if(a==3)//调用删除函数
{
linklist delet(linklist *head); //调用删除函数
delet(head);
}
}
return 0;
}

//1.尾插法建立单链表
linklist *rcrect(linklist *head) //尾插法 链接到已经建立好的单链表的末尾
{
linklist *p,*last;
char ch; //用于输入字符
last=head;
printf("请输入你要存储的字符,以!号结束：\n");
while(ch!='!')
{
p=(linklist *)malloc(sizeof(linklist));
scanf("%c",&ch);
p->data=ch; //每次都申请一个节点，数据域存放数据，指针域为空 // printf("%c\t",p->data); 可以用来测试存储是否正确
last->next=p;
last=p; //上一次的最后一个元素的地址赋给last
p->next=NULL;
}
void print(linklist *head); //调用输出函数
print(head);
return head;
}

//2.输出函数函数
void print(linklist *head)
{
linklist *p;
p=head->next;
printf("\n你存储的数据为:\n");
while(p!=NULL)
{
printf("%c\t",p->data);
p=p->next;
}
}

//3.按序号查找函数
linklist location(linklist *head)
{
linklist *p;
int i,k=0;
p=head;
printf("\n请输入你要查找链表中第几个元素：\n");
scanf("%d",&i);

while(p&&k p=p->next;
k++;
}
if(k>i||!p)
{
printf("输入的序号有误，查找失败！\n");
exit(0);
}
else
printf("第%d个元素的值为：%c\n",i,p->data);
return *head;
}
//4.插入函数
linklist inset(linklist *head)
{
linklist *p,*p1;
int i,k=0;
char ch;
p=head; //不能为head->next
printf("请输入你要在链表的第几个位置?\t插入什么元素?\n");
scanf("%d %c",&i,&ch);
p1=(linklist *)malloc(sizeof(linklist)); //新建一个节点
p1->data=ch;
p1->next=NULL;

while(p&&knext;
k++;
}
if(k>i-1||!p)
{
printf("输入的序号有误，插入失败！\n");
exit(0);
}
else
{
p1->next=p->next;
p->next=p1;
printf("插入后的新数据为:\n"); //输出插入后的新数据
p=head->next;
while(p!=NULL)
{
printf("%c\t",p->data);
p=p->next;
}
printf("\n");
}
return *head;
}
//5.删除函数
linklist delet(linklist *head)
{
linklist *p,*p1,*p2;
p=head;
int i,k=0;
printf("请输入你要删除第几个元素:\n");
scanf("%d",&i);
while(p&&knext;
k++;
}
if(k>i-1||!p)
{
printf("输入的序号有误，删除失败！\n");
exit(0);
}
else
{ p2=p->next;
p->next=p2->next;
free(p2);
printf("删除后的新数据为:\n"); //输出插入后的新数据
p=head->next;
while(p!=NULL)
{ printf("%c\t",p->data);
p=p->next;
} printf("\n");
}
return *head;} 

精品资料

组
内
分
工
（
可
选
）
无
实
验
结
果
分
析
及
心
得
体
会
实验结果截图：

心得体会：通过本次实验对于线性表的运用更熟练了，对于单链表的建立，删除，插入，输出更加熟悉。
成
绩
评
定

教师签名：
年 月 日

年级
 2012
班号
1201
组号

 学号
 2012213773
专业
网络工程
 姓名
 黄勇
实验名称
 第三章 栈和队列
实验室

实
验
目
的
或
要
求
  在掌握栈（队列）特点的基础上，懂得在什么样的情况下能够使用栈（队列）。能熟练使用栈（队列）的一种存储表示，以及在该存储结构上如何实现栈（队列）的基本操作。在熟悉上述内容的基础上，能够针对具体应用问题的特点，选择栈（队列）设计出相应的有效算法，解决与栈（队列）相关的实际问题。

实
验
原
理
（
算
法
流
程
）
 1、实验内容
括号匹配的检验。合法的括号包括（）和【】两类，利用栈判断任意输入的一个括号序列是否匹配对出现，若是输出“right“，否则输出”error！“。且提示错误原因。
2、 存储结构描述及说明
typedef struct
{
int *base;
int *top;
int stacksize;
}SqStack;顺序存储结构

3、函数说明
int InitStack(SqStack *S) 构造函数，构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE
int push(SqStack *S,int e) 插入函数，在栈S中插入元素e为新的栈顶元素。
int pop(SqStack *S,int *e) 删除函数，若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回ERROR
void match(char str[]) 检测函数，对输入的表达式进行检测，括号是否匹配，匹配则返回配对，否则返回不配对。
int main() 主函数。
4、模块之间的调用关系
主函数
构造函数
插入函数
删除函数
检测函数

 程序清单：
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#define ERROR -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct
{
int *base;
int *top;
int stacksize;
}SqStack;
int InitStack(SqStack *S)
{
S->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
if(!S->base)
{
printf("\n磁盘不足.\n");
getch();
exit(ERROR);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return 1;
}
int push(SqStack *S,int e)
{
if(S->top-S->base>=S->stacksize)
{
S->base=(int *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(int));
if(!S->base)
{
printf("\n磁盘不足.\n");
getch();
exit(ERROR);
}
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=e;
return 1;
}
int pop(SqStack *S,int *e)
{
if(S->top==S->base)
{
printf("\n栈已满.\n");
return ERROR;
}
*e=*--S->top;
return 1;
}
void match(char str[])
{
SqStack S;
char *p;
int e;
InitStack(&S);
p=str;
while(*p)
{
if(*p=='('||*p=='['||*p=='{')
push(&S,*p);
else if(*p==')'||*p==']'||*p=='}')
{
if(*(S.top-1)+1==*p||*(S.top-1)+2==*p)
pop(&S,&e);
else
{
printf("\n不配对.\n");
return;
}
}
p++;
}
if(S.top==S.base)
printf("\n配对.\n");
else
printf("\n不配对！\n");
}
int main()
{
char str[100];
printf("\n输入表达式:\n");
gets(str);
match(str);
getch();
return 0;
}

组
内
分
工
（
可
选
）
无
实
验
结
果
分
析
及
心
得
体
会
实验结果截图：

心得体会：通过本次实验，对于栈的运用更加熟练，对于栈的应用有了初步认识，在以后的学习中加深对于栈的认识，对于数据结构有了更深刻的印象。
成
绩
评
定

教师签名：
年 月 日

年级
 2012
班号
 1201
组号

 学号
2012213773 
专业
网络工程
 姓名
 黄勇
实验名称
 第六章 树和二叉树
实验室

实
验
目
的
或
要
求

了解二叉树的定义、性质、存储结构等相关知识，在熟悉这些内容的基础上掌握二叉树在某种存储结构下遍历以及相关算法的实现及应用，能根据本章所学到的有关知识设计出有效的算法。

实
验
原
理
（
算
法
流
程
）
 1、实验内容
二叉树的相关演示操作。自定义结点结构，以二叉链表为存储结构，完成以下功能：
1）以先序递归放松创建一棵二叉树。
2）输出二叉树的先序、中序和后序递归或非递归遍历下的结点访问次序；
3）输出二叉树所有的叶子节点和叶子节点个数；
4）输出二叉树的高度；
5）输出二叉树的按层次遍历序列（选作）
6）输出二叉树的形状(选作)
2、存储结构描述及说明
二叉链表存储结构。
3、函数说明
BinTree CreatBinTree(void) 输入先序序列，其中加入虚结点"#"以示空指针的位置构造二叉树
void Preorder(BinTree T) 先序遍历二叉树函数，以先序递归遍历二叉树，输出先序遍历。
void Inorder(BinTree T) 中序遍历二叉树函数，以中序递归遍历二叉树，输出中序遍历。
void Postorder(BinTree T) 后序遍历二叉树函数，以后序递归遍历二叉树，输出后序遍历。
int TreeDepth(BinTree T) 求二叉树深度及叶子节点数函数，采用后序遍历求二叉树的深度、结点数及叶子数并输出。
后序遍历二叉树
void main() 主函数。
4、模块之间的调用关系

中序遍历函数
先序遍历函数
主函数

求叶子节点及深度函数

先序创建二叉树函数

程序清单：#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define Max 20 //结点的最大个数

typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型

typedef BinTNode *BinTree; //定义二叉树的指针

int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//==========基于先序遍历算法创建二叉树==========
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}

//==========主函数=================
void main()
{
BinTree root
int i,depth;
printf("\n");
printf("输入二叉树的先序序列创建二叉树，用#代表空结点:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
//do { //从菜单中选择遍历方式，输入序号。
printf("\t********** 菜单 ************\n");
printf("\t1: 先序遍历\n");
printf("\t2: 中序遍历\n");
printf("\t3: 后序遍历\n");
printf("\t4: 求树的深度及叶子节点数\n");
printf("\t0: 退出\n");
printf("\t*******************************\n");
do { //从菜单中选择遍历方式，输入序号。
scanf("%d",&i); //输入菜单序号（0-5）
switch (i){
case 1: printf("先序遍历为: ");
Preorder(root); //先序遍历
break;
case 2: printf("中序遍历为: ");
Inorder(root); //中序遍历
break;
case 3: printf("后序遍历为: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子节点数
printf("树的深度=%d 树的叶子节点=%d",depth,NodeNum);
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}

（写不完时，可另加附页。）

组
内
分
工
（
可
选
）
无
实
验
结
果
分
析
及
心
得
体
会
实验结果截图：
心得体会：通过本次实验对于二叉树的运用更熟练，对于二叉树的先序、中序和后序遍历更加熟悉。
成
绩
评
定

教师签名：
年 月 日

年级
 2012
班号
 1201
组号

 学号
 2012213773
专业
网络工程
 姓名
黄勇 
实验名称
 第七章 图
实验室

实
验
目
的
或
要
求
了解图的基本概念，理解几种常用的存储结构、两种遍历算法以及图的应用算法，在熟悉这些内容的基础上，重点掌握图在邻接表这种存储结构下遍历算法的实现。

实
验
原
理
（
算
法
流
程
）
 1、实验内容
图在采用邻接表的存储结构下的基本操作，包括图的创建、图的深度优先搜索和广度优先搜索。

2、存储结构描述及说明
邻接表存储结构。
typedef struct st_arc

{
int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;

typedef struct
{
int vertex;
struct st_arc *firstarc;
}vernode;

typedef vernode adjlist[maxnode];

int queue[maxnode];
3、函数说明
void dfs(adjlist g,int k,int visited[]) 深度优先搜索函数，从顶点k出发，深度优先搜索。
void bfs(adjlist g,int k,int visited[]) 广度优先搜索函数，从顶点k出发，广度优先搜索。
void trave_bfs(adjlist g,int n) 广度优先搜索函数
void trave_dfs(adjlist g,int n) 深度优先搜索函数，
4、模块之间的调用关系
 主函数
创建图
广度优先搜索
深度优先搜索

程序清单：
#include "iostream"
#include "stdlib.h"
#include "stdio.h"
#include "malloc.h"
#define maxnode 40
#define null 0
#define m 20

typedef struct st_arc

{
int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;

typedef struct
{
int vertex;
struct st_arc *firstarc;
}vernode;

typedef vernode adjlist[maxnode];

int queue[maxnode];

void dfs(adjlist g,int k,int visited[]) //从顶点k出发，深度优先搜索
{
arcnode *p;
int w;
visited[k]=1;
printf("%d",g[k].vertex);
p=g[k].firstarc;
while(p!=null)
{
w=p>adjvex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}
}

void bfs(adjlist g,int k,int visited[]) //从顶点k出发，广度优先搜索
{
int front=0,rear=1,w;
arcnode *p;
visited[k]=1; //访问初始顶点
printf("%d",k);
queue[rear]=k; //初始顶点入队列
while(front!=rear) //队列不为空
{
front=(front+1)%m;
w=queue[front]; //按访问次序依次出队列
p=g[w].firstarc;
while(p!=null)
{
if(visited[p->adjvex]==0)
{
visited[p->adjvex]=1;
printf("%d",p->adjvex);
rear=(rear=1)%m;
queue[rear]=p->adjvex;;
}
p=p->nextarc;
}
}
}
void trave_bfs(adjlist g,int n)
{
int i,visited[maxnode]; //数组visited标志图中的顶点是否已被访问
for(i=1;i<=n;i++)
visited[i]=0;
for(i=1;i<=n;i++)
if(visited[i]==0)