数据结构实验五

上机题五报告增加了计算时间的算法

可以比较各个排序的所用时间

姓名：

学号：

完成日期：2015年6月2日

题目：堆排序、快排、基数排序

1.1 需求分析

1. 程序功能：对于给定的一串数据，可以从小到大排序并计算所用时间。

2. 测试数据：

1.2 概要设计

1.2.1 主程序流程

开始

输出原始数据

进行排序

输出排序结果和时间

结束

1.2.2 模块调用图

1.3 详细设计

1、快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此使整个数据变成有序序列。

void QuickSort(int a[], int left, int right) 设置两个变量left 、right ，排序开始的时候left=1，right =N ；

{

if(left < right)

{

int pivotPos = Partition(a, left, right);

QuickSort(a, left, pivotPos-1);// 从left 开始向后搜索，即由前开始向后搜索（left=left+1），找到第一个大于X 的值，两者交换；

QuickSort(a, pivotPos+1, right);//从left 开始向后搜索，即由前开始向后搜索（left=left+1），找到第一个大于X 的值，两者交换；

//重复上述两步，直到left= right ；

}

}

int Partition(int a[], int low, int high)

数据结构实验报告

实验五

图子系统

实验题目：图的遍历问题

专业班级：网络工程 1002班

组长：王星（30）

组员：郭坤铭（43）

张磊（44）

2012年 5月 18日

实验报告

实验类型__综合__实验室_软件实验室二__

一、实验题目

图的遍历问题

二、实验目的和要求

1、掌握图的存储思想及其存储实现

2、掌握图的深度、广度优先遍历算法思想及其程序实现

3、掌握图的常见应用算法的思想及其程序实现

三、需求分析

本演示程序用c++6.0编写，完成用户用键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北。（1）建立一个有向图或无向图（自定）的邻接表并输出该邻接表。（2）在图的邻接表的基础上计算各顶点的度，并输出。（3）以有向图的邻接表为基础实现输出它的拓扑排序序列。（4）采用邻接表存储实现无向图的深度优先遍历。（5）采用邻接表存储实现无向图的广度优先遍历。（6）采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法。最后，在主函数中设计一个简单的菜单，分别调试上述算法。

四、概要设计

为了实现上述程序功能，需要定义如下内容

基本数据类型定义如下：

typedef struct node{ //边表结点

int adj; //边表结点数据域

struct node *next;

}node;

typedef struct vnode //顶点表结点

{ char name[20];

node *fnext;

}vnode,AList[20];

typedef struct

{ AList List; //邻接表

int v,e; //顶点树和边数

实验报告五查找（学科：数据结构）

姓名单位班级学号实验日期成绩评定教师签名批改日期

实验名称：实验五查找

5.1 折半查找

【问题描述】

某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序。

【基本信息】

（1）建立现有学生信息表，平均成绩已有序。

（2）输入插入学生的记录信息。

（3）用折半查找找到插入位置，并插入记录。

【测试数据】

自行设计。

【实验提示】

（1）用结构数组存储成绩信息表。

（2）对记录中的平均成绩进行折半查找。

【实验报告内容】

设计程序代码如下:

#include<stdio.h>

#include<string.h>

#define N 5

struct student{

char name[10];

float avg;

}

void insort(struct student s[],int n)

{

int low,hight,mid,k;

char y[10];

float x;

low=1;

hight=n;

strcpy(y,s[0].name );

x=s[0].avg ;

while(low<=hight)

{

mid=(low+hight)/2;

if(x>s[mid].avg )

hight=mid-1;

else

low=mid+1;

}

for(k=0;k<low-1;k++){

strcpy(s[k].name,s[k+1].name) ;

数据结构C语言版实验五报告

实验五

一、实验目的

1、理解二叉树的类型定义域性质。

2、掌握二叉树的二叉链表储存结构的表示和实现方法。

3、掌握二叉树遍历操作的算法实现。

4、熟悉二叉树遍历操作的应用。

二、实验内容

1、建立二叉树的二叉链表储存结构。

2、实现二叉树的先序、中序和后序三种遍历操作（验证性内容）。

3、应用二叉树的遍历操作来实现判断儿科二叉树是否相等的操作（设计性内容）。

4、求从二叉树根结点到指定结点P之间的路径（应用性设计内容）。

三、验证性实验

1、实验要求

编程实现如下功能：

（1）假如二叉树的结点值是字符，根据输入的一颗二叉树的完整先序遍历序列建立一颗以二叉树链表表示的二叉树。

（2）对二叉树进行先序、中序和后序遍历操作，并输出表里序列，观察输出的序列是否与逻辑上的序列一致。

（3）主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行哪一种遍历操作。

2、参考代码：

#include

#include

typedef struct Bitnode

{

char data;

struct Bitnode *lchild,*rchild;

}Bitnode,*Bitree;

Bitree create(Bitree T)//创建树

{

char x;

scanf("%c",&x);

if(x=='#')

T=NULL;

else

{

T=(Bitree)malloc(sizeof(Bitnode));

T->data=x;

T->lchild=create(T->lchild);

T->rchild=create(T->rchild);

数据结构实验五图子系统

实验五

实验题目:图子系统

指导老师:王春红

专业班级:计算机科学与技术系1105班姓名:李慧2011100521杜丽20111005122

白莹2011100523王媛2011100529

2013年 5月23日

实验类型综合实验室_软件实验室一__

一、实验题目

1

图子系统

二、实验目的和要求

,(掌握图的存储思想及其存储实现

,(掌握图的深度、广度优先遍历算法思想及其程序实现

,(掌握图的常见应用算法的思想及其程序实现。三、实验内容

实验内容二:所有顶点对的最短路径

1(设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。

2(设计分析

用有向加权图表示的交通图中，有向边<vi,vj>表示第i个村庄和第j个

村庄之间有道路，边上的权表示这条道路的长度。该问题的实质是求解任意两顶点间的最短路径问题。即求出每个顶点到其他顶点的最短路径的最大值，最大值最小的顶点作为医院所在村庄。

3(结构类型定义

typedef char vextype;/*顶点数据类型*/

typedef int edgetype;/*边数据类型*/

typedef struct

{

vextype vex[maxsize];

edgetype arc[maxsize][maxsize];

int vexnum,arcnum;

}Mgraph;

小组分工:

组长:王媛定义结构体和主函数

组员:李慧 void juzhen(Mgraph *G)

《数据结构》上机作业——实验报告（五）[推荐]

第一篇：《数据结构》上机作业——实验报告(五)[推荐]

“计算机软件技术基础”课程实验报告

（五）实验名称：排序算法

班级_______ 姓名__________ 学号______实验日期：

实验机时：3 学时实验成绩：

-----------------

一.实验目的：

1、掌握主要排序算法的思想和实现技术。

二.实验内容：

1、设计一程序，要求：输入学生“软件技术基础”课的成绩（学

号、姓名、平均成绩、总学分）；按总学分对学生数据进行排序。（要求：实现任选3种排序算法）

三.程序：

1、程序规范（输入数据、功能、输出数据）

2、设计分析（数据表示、算法）

3、C源代码（电子版）

四.程序调试：

第二篇：《数据结构》上机作业——实验报告(六)

“计算机软件技术基础”课程实验报告

（六）实验名称：数据库及SQL语言

班级_______ 姓名__________ 学号______实验日期：

实验机时：3 学时实验成绩：

-----------------

一.实验目的：

1、学习数据库设计的一般过程及相关技术；

2、学习access数据库管理系统；

3、掌握数据库的输入、查询、更新操作。

二.实验内容：

1、需求陈述：某校图书馆要建立一个图书数据管理系统。该图书馆的图书（书名、分类号、作者、出版社）存放在不同的借阅室（室名），读者（姓名、系名、类别）在书架上找到所需图书后，可以到服务台办理借阅（借阅时间）。

设计要求：

λ分析需求，建立数据库的概念模型；

λ将概念模型转换为关系模型（注意：是否需要作规范化处理）；λ写出创建基本表的SQL语句；

HUNAN UNIVERSITY 课程实习报告

题目：四则运算表达式求值

学生姓名康小雪

学生学号 20090810310

专业班级计科三班

指导老师李晓鸿

完成日期2010-10-24

一、需求分析

1．该程序可以从通过从键盘输入一个中缀表达式，判断该表达式是否合法，若合法将其转化为后缀表达式，并计算其结果，否则说明该表达式错误

2．.输入的表达式包含数字和运算符及括号，之间用空格隔开

3．数字可以为整数和小数

4．运算结果保留两位小数

输入输出举例

输入：21+23*（12-6）

输出：21 23 12 6 -*+

二、概要设计

在表达式中每个运算符应对应两个操作数，与二叉树中非叶子结点和叶子结点之间的关系刚好相同，于是，本题可采用二叉树来将中缀表达式变为后缀表达式。

最后用堆栈来实现后缀表达式的计算。

抽象数据类型

二叉树

ADT BiTree

{

数据对象D：D是具有相同特性的数据元素集合

数据关系R：

若D为空集，则R为空集，则称BinaryTree为空二叉树；

若D不为空集，否则R={H}，H是如下二元关系：

（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；

（2）若D-{root}≠空集，则存在D-{root}的一个划分{D1,Dr} 且D1∩Dr=空集；

（3）若D1≠空集，则D1中存在唯一元素x1，<root，x1>∈H,且存在D1shang de guanxi H1=H;ruo Dr≠空集，则Dr中存在唯一的元素，xr，<root，xr>∈H，

且存在Dr上的关系Hr∈H;H={<root,x1>,<root,xr>,H1,Hr};

《数据结构》实验报告

实验序号：5 实验项目名称：队列的操作

#include <iostream>

#include <queue>

using namespace std;

void main()

{

queue<int> q; //使用前需定义一个queue变量，且定义时已经初始化char c;

printf("请输入所有元素的值，以‘#’结束：\n");

c=getchar();

while(c!='#')

{

q.push(c); //进队列

c=getchar();

}

printf("该队列长度为:%d\n",q.size());

printf("队列打印输出为：");

while(!q.empty())

{

printf("%c ",q.front()); //得到队首的值

q.pop(); //出队列

}

printf("\n");

}

实验五：有向图的基本操作

目标：

本实验主要练习用邻接矩阵表示的有向图的基本操作。

问题描述：

给定一个有向（无权）图(UDGraph)，用字符’A’,’B’,’C’…标识的顶点存储

在一个顺序表vexs中;有向边存储在邻接矩阵adjMatrix中, adjMatrix[i][j]=1表示第i个顶

点到第j个顶点间有弧，否则表示没有。如何在图G中寻找到顶点v路径长度为k的所有顶点。

基本要求：

1.实现以下基本操作：

(1) createGraph(&G,int MaxVertices)：创建一个最多可有MaxVextices个顶点的图。

(2) getNumVertices(G)：返回图G中的顶点个数。

(3) getNumEdges(G)：返回图G中的边个数。

(4) validVertex(G,char v)：如果顶点v在图G中，则返回TRUE。

(5) hasEdge(G, char u, char v)：如果图G中存在从u到v的有向边，则返回TRUE。

(6) addVertex(G, char u)：如果图中不存在顶点u，将其添加到图中。

(7) addEdge(G, char u, char v)：如果图G中不存在从u到v的有向边，则加入该边。

(8) removeEdge(G, char u, char v)：如果图G中存在从u到v的有向边，则去除该边。

2. 添加操作length2Paths(G, char v)寻找图G中所有经过2条边可到顶点v的路径。该操作创建并返回与图G相同数目顶点的新图NG；如果图G中存在一条从u到v的长

数据结构实验报告实验五

一.实验内容：

实现哈夫曼编码的生成算法。

二.实验目的：

1、使学生熟练掌握哈夫曼树的生成算法。

2、熟练掌握哈夫曼编码的方法。

三.问题描述：

已知n个字符在原文中出现的频率，求它们的哈夫曼编码。

1、读入n个字符，以及字符的权值，试建立一棵Huffman 树。

2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。

四.问题的实现

(1)郝夫曼树的存储表示

typedef struct{

unsigned int weight;

unsigned int parent,lchild,rchild;

}HTNode,*HuffmanTree; //动态分配数组存储郝夫曼树

郝夫曼编码的存储表示

typedef char* *HuffmanCode;//动态分配数组存储郝

夫曼编码

(2)主要的实现思路：

a.首先定义郝夫曼树的存储形式，这里使用了数组

b.用select()遍历n个字符，找出权值最小的两个

c.构造郝夫曼树HT，并求出n个字符的郝夫曼编码HC

总结

1.基本上没有什么太大的问题，在调用select()这个

函数时，想把权值最小的两个结点的序号带回HuffmanCoding()，所以把那2个序号设置成了引用。

2.在编程过程中，在什么时候分配内存，什么时候初

始化花的时间比较长

3.最后基本上实现后，发现结果仍然存在问题，经过

分步调试，发现了特别低级的输入错误。把HT.weight=HT.weight+HT.weight;中的s2写成了i 附：

实验五、查找排序算法的实现

一、实验目的

1．掌握顺序、二分法查找方法及适用场合，并能在解决实际问题时灵活应用。

2．掌握各种排序（直接插入，希尔，冒泡，快速排序，简单选择，堆排序等）方法及适用场合，并能在解决实际问题时灵活应用。

二、实验内容

随机输入（或随机产生）30个数

（1）采用冒泡排序完成对这30个数的排序

（2）采用顺序、折半查找在（1）中排好序的数据中完成查找任务

（3）分别采用插入、快速和希尔完成对这30个数的排序任务，并输出每一趟排序后的结果

三、实验代码：

#include <stdio.h>

#include <time.h>

#include <stdlib.h>

#define MaxSize 100

typedef struct

{

int key;

}RecordType;

//直接插入排序

void InsertSort(RecordType r[], int length)

{

for (int i=2; i<=length;i++)

{

r[0]=r[i];

int j=i-1;

while (r[0].key<r[j].key)

{

r[j+1]=r[j];

j=j-1;

}

r[j+1]=r[0];

}

}

//冒泡排序

void BubbleSort(RecordType r[], int length)

{

int t;

for (int i=1; i<=length; i++)

{

for (int j=1; j<=length-i; j++)

{

if (r[j].key>r[j+1].key)

数据结构上机实验五

实验内容:查找表和内部排序的基本算法

实验要求:

1) 基本操作要作为函数被调用，做到模块化.

2) 基本上实现每个实验题目的要求.

分组要求：可单独完成，也可两人一组。

实验目的:

1)熟悉C/C++基本编程,培养动手能力.

2)通过实验,加深对查找算法的理解.

评分标准：

1) 只完成第一和第二题，根据情况得4，5-分；

2）完成前3题，根据情况得5，6分；

3）在2）基础上，选做四）中题目，根据情况得6，7分。

题目:

一)顺序表与有序表的查找

(1)建立一个顺序表，利用教材9.1.1的顺序查找算法进行查找；

#include"stdio.h"

#include"stdlib.h"

typedef struct node{

int key;

}keynode;

typedef struct Node{

keynode r[50];

int length;

}list,*sqlist;

int Createsqlist(sqlist s)

{

int i;

printf("请输入您要输入的数据的个数:\n");

scanf("%d",&(s->length));

printf("请输入您想输入的%d个数据;\n",s->length);

for(i=0;i<s->length;i++)

scanf("%d",&(s->r[i].key));

printf("\n");

printf("您所输入的数据为:\n\n");

for(i=0;i<s->length;i++)

printf("%-5d",s->r[i].key);

实验五查找得实现

一、实验内容

1、建立一个线性表,对表中数据元素存放得先后次序没有任何要求.输入待查数据元素得关键字进行查找。为了简化算法,数据元素只含一个整型关键字字段,数据元素得其余数据部分忽略不考虑.建议采用前哨得作用，以提高查找效率。

2、查找表得存储结构为有序表,输入待查数据元素得关键字利用折半查找方法进行查找.此程序中要求对整型量关键字数据得输入按从小到大排序输入。二、源代码与执行结果

1、

＃inclｕｄｅ〈ｉoｓtreａm>

ｕsiｎg namespace stｄ；

＃defｉne MAX １０0

＃deｆinｅKｅyTｙpe iｎｔ

typｅｄef stｒuct

{

ＫｅｙＴｙpe key ；

｝DataTｙpe；

typedef struｃt

{

ﻩDaｔaＴyｐｅelem[ＭAX］;

iｎｔlength ；

}SeqTａble ，＊PSeｑTable ；

PSeｑTable Ｉniｔ_SｅqＴable（)

{

ﻩＰSｅqTable p ＝（ＰＳｅｑTable）malｌoc(ｓizeof（SeｑTable)) ;

ﻩiｆ（p ！＝ＮULＬ）

｛

p->lｅｎgtｈ= 0 ；

ﻩｒｅｔｕrnｐ；

}

ﻩelsｅ

｛

ﻩｃｏｕt〈<"Ouｔｏf space!”〈〈endl ；

ﻩrｅtuｒn NＵＬL;

ﻩ}

｝

int insert＿SeqTable（PSeｑTable p,KeｙType x)

{

ｉｆ(ｐ-＞length〉= ＭＡX）

ﻩ｛

ﻩcｏｕt〈<”ｏverｆｌow！"<<endl ;