当前位置：文档之家› 数据结构实验4报告

数据结构实验4报告

任课教师：孙树森

《数据结构与算法》

（2012-2013学年第2学期）

实

验

报

告

学号：2011329700214

姓名：周咪咪

班级：11数字媒体技术（2）班

实验4快速排序

一、实验目的和要求

1 在掌握各种排序方法的排序过程的基础上，完成快速排序算法程序设计。

2 能够对排序算法进行基本的复杂度分析。

二、实验内容

排序就是把一组元素按照某个域的值的递增或递减的次序重新排列的过程。

快速排序

在待排序记录序列中任取一个记录作为枢轴，以它作为比较的“基准”，将待排序划分为左右两个子序列，使行左边子序列中记录的关键字均小于等于枢轴，右边子序列中各记录的关键字都大于等于枢轴。对所划分的两组分别重复上述过程，直到各个序列的记录个数为1时为止。快速排序函数原型QuickSort(SeqList sq)。

设计一个算法，在顺序表存储结构上实现快速排序。排序数据为学生的考试成绩单。成绩单由学生的学号、姓名和成绩组成，设计一个程序对给定的n个学生的成绩单按照名次列打印出每个学生的名次、学号、姓名和成绩。

三、实验步骤

1．输入待排序的记录

2. 对自定义记录类型重载比较运算符

3．排序

1）并选择第一个记录作为pivotkey记录

2）从high指向的记录开始,向前找到第一个关键字的值小于Pivotkey的记录,将其放到low指向的位置,low+1

3）.从low指向的记录开始,向后找到第一个关键字的值大于Pivotkey的记录,将其放到high指向的位置,high-1

4）重复2),3)，直到low=high，将枢轴记录放在low(high)指向的位置

5）重复2),3),4)，直到整个记录有序为止

6) 输出排序记录

，完成比较。

4. 附加要求：不采用运算法重载的方式，而是定义compare函数指针，通过传给quicksort 函数指针，完成排序。

四、实验提示

算法实现：

成功代码：在存储结构中添加一个CRecord * temp;原来暂存指针移动位置时所指内容，在快速排序函数中利用中间的存储结构list.temp[0]，实现两个指针的位置改变后所指内容的变化。

#include

using namespace std;

#define MaxSize 100 //定义顺序表的最大长度

typedef int DataType;//定义模板为整型数据

class CRecord //定义一个记录类，用来存放每一个学生信息中包含的数据

{

public:

int num;

char name[10];

int grade;

};

class SeqList{ //定义一个表格类，存放记录类中的信息，顺序表的长度和一个中间存储单位temp

public:

CRecord * data;

CRecord * temp;

int length;

};

//创建顺序表

void SLCreat(SeqList &sq)

{

sq.length = 0; //初始化顺序表长度为0

cout <<"请输入数据元素数:";

cin>>sq.length; //输入顺序表长度

sq.data= new CRecord[sq.length];//开辟data空间

sq.temp= new CRecord[sq.length];//开辟temp空间

cout <<"请输入数据元素值: "<

cout <<"学号姓名成绩: "<

for(int i = 0; i < sq.length; i++)//依次输入数据到顺序表中data的相对位置

{

cin >> sq.data[i].num>>sq .data[i].name>>sq. data[i].grade;

}

//一次快速排序

int partition(SeqList &list, int i, int j)

{

DataType pivotkey;//定义关键字

list.temp[0]=list.data[i];//把list.data[i]中的数据再存到list.temp[0]，供交换后使用

pivotkey = list.data[i].grade;//选择第一个记录作为pivotkey记录，初始化pivotkey为list.data[i].grade的成绩

while(i < j)

{

while(i < j&&list.data[j].grade >= pivotkey) //当j(顺序表中后者)中成绩大于等于pivotkey时

--j;//j值减少1取向向前的数据

list.data[i] = list.data[j];//将比枢轴记录小的记录交换到低位，把i中数据放到j指向的位置,即j-1

while(i < j&&list.data[i].grade <= pivotkey) //当i(顺序表中后者)中成绩小于等于pivotkey时

++i;//i值加1取向向后的数据

list.data[j] = list.data[i];;//将比枢轴记录大的记录交换到高位，把j中数据放到i指向的位置,即i-1

}

list.data[i]=list.temp[0];//完成交换

return i;

}

//快速排序，实现顺序表的完整排序

void QuickSort(SeqList & sq, int low, int high)

{

int pos;

if(low < high)

{

pos = partition(sq,low, high);

QuickSort(sq,low, pos-1);

QuickSort(sq, pos+1, high);

}

//排序

void Sort( SeqList & sq )

{

QuickSort(sq,0,sq.length-1);//定义low指针指向list.data[0].grade，hige指针指向

list.data[length-1].grade

}

//将顺序表输出显示在屏幕上

void SLPrint(SeqList & sq)

{

cout <<"快速排序后成绩排列结果: "<

cout <<"名次学号姓名成绩: "<

int i=sq.length-1;

int n=0;

while(i>=0)

{

n++;

cout<<" "<

cout << endl;

i--;

}

//主函数

void main( )

{

SeqList myList;

SLCreat(myList);

Sort(myList );

SLPrint(myList );

}

程序分析：

（1）整个程序实现过程，首先是需要定义两个结构体CRecord和SeqList用于定义学生信息和顺序表中信息结构。然后需要创建顺序表输入学生信息包括学生学号，姓名和成绩。接着定义一个快速排序函数partition实现每交换一对记录时所需操作。再定义QuickSort函数实现完整的快速排序过程，Sort函数设置好low和high指针指向，SLPrint函数实现快速排序后显示的结果。

在main函数中，首先定义创建一顺序表myList输入信息，再调用函数实现快速排序后结果。

（2）在partition函数中，先将枢轴记录暂存在list.temp[0]位置上，排序过程中只对list.data[i]和list.data[j] 的单向移动，直到一趟排序结束后再将枢轴记录移至正确位置上。

运行结果：

实验心得：

此次实验是关于快速排序算法的实现。

实验过程中，通过老师所给的代码再加上自己的修改基本掌握了快速排序。排序就是把一组元素按照某个域的值的递增或递减的次序重新排列的过程。在待排序记录序列中任取一个记录作为枢轴，以它作为比较的“基准”，将待排序划分为左右两个子序列，使行左边子序列中记录的关键字均小于等于枢轴，右边子序列中各记录的关键字都大于等于枢轴。对所划分的两组分别重复上述过程，直到各个序列的记录个数为1时为止。快速排序函数原型QuickSort(SeqList sq)。

实验过程中，虽然遇到了很多困难但是经过自己的修改和老师的帮助完成了实验，希望在接下来的学习中再接再厉更好地掌握数据结构算法设计。

数据结构实验报告格式

《数据结构课程实验》大纲一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。由于以下原因，使得掌握这门课程具有较大的难度：（1）内容丰富，学习量大，给学习带来困难；（2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点；（3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度；（4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。二、《数据结构课程实验》的目的和要求不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。三、《数据结构课程实验》内容课程实验共18学时，要求完成以下六个题目：实习一约瑟夫环问题（2学时）

(完整版)数据结构实验报告全集

数据结构实验报告全集实验一线性表基本操作和简单程序 1 ．实验目的（1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法；（2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求（1 ）认真阅读和掌握和本实验相关的教材内容。（2 ）认真阅读和掌握本章相关内容的程序。（3 ）上机运行程序。（4 ）保存和打印出程序的运行结果，并结合程序进行分析。（5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include// 库头文件------ 动态分配内存空间 typedef int elemtype;// 定义数据域的类型 typedef struct linknode// 定义结点类型 { elemtype data;// 定义数据域 struct linknode *next;// 定义结点指针 }nodetype; 2）创建单链表

nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"<> d; if(d==0) break;// 以0 表示输入结束 if(i==1)// 建立第一个结点 { h=(nodetype*)malloc(sizeof(nodetype));// 表示指针h h->data=d;h->next=NULL;t=h;//h 是头指针 } else// 建立其余结点 { s=(nodetype*) malloc(sizeof(nodetype)); s->data=d;s->next=NULL;t->next=s; t=s;//t 始终指向生成的单链表的最后一个节点

数据结构实验报告(四)

《数据结构》实验报告班级：学号：姓名：

实验四二叉树的基本操作实验环境：Visual C++ 实验目的： 1、掌握二叉树的二叉链式存储结构； 2、掌握二叉树的建立，遍历等操作。实验内容：通过完全前序序列创建一棵二叉树，完成如下功能： 1)输出二叉树的前序遍历序列； 2)输出二叉树的中序遍历序列； 3)输出二叉树的后序遍历序列； 4)统计二叉树的结点总数； 5)统计二叉树中叶子结点的个数；实验提示： //二叉树的二叉链式存储表示 typedef char TElemType; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

一、程序源代码 #include #include #define MAXSIZE 30 typedef char ElemType; typedef struct TNode *BiTree; struct TNode { char data; BiTree lchild; BiTree rchild; }; int IsEmpty_BiTree(BiTree *T) { if(*T == NULL) return 1; else return 0;

} void Create_BiTree(BiTree *T){ char ch; ch = getchar(); //当输入的是"#"时，认为该子树为空 if(ch == '#') *T = NULL; //创建树结点 else{ *T = (BiTree)malloc(sizeof(struct TNode)); (*T)->data = ch; //生成树结点 //生成左子树 Create_BiTree(&(*T)->lchild); //生成右子树 Create_BiTree(&(*T)->rchild); } } void TraverseBiTree(BiTree T) { //先序遍历 if(T == NULL) return;

数据结构实验报告

数据结构实验报告一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案对于前三个题目要求，我们用一个程序实现代码如下 #include #include #include #include "Stack.h"//栈的头文件，没有用上 typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree; intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL) { T = (BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1; } else if(keydata){ InsertBST(T->lChild,key); } else if(key>T->data){ InsertBST(T->rChild,key); } else return 0; } BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL; inti=0; while(i

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10;

template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif MGraph.cpp

#include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) {

数据结构图的遍历实验报告

实验项目名称：图的遍历一、实验目的应用所学的知识分析问题、解决问题，学会用建立图并对其进行遍历，提高实际编程能力及程序调试能力。二、实验容问题描述：建立有向图，并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数，能够打印出用邻接表或邻接矩阵表示的图的储存结构。三、实验仪器与设备计算机，Code::Blocks。四、实验原理用邻接表存储一个图，递归方法深度搜索和用队列进行广度搜索，并输出遍历的结果。五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include #include #include #include

typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;ivexnum;i++) if(strcmp(v,G->vexs[i].name)==0) { c=i; break;} return c;} MGraph * CreatUDN(MGraph *G)//初始化图，接受用户输入{ int i,j,k,w; char v1[20],v2[20]; printf("请输入图的顶点数,弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum);

数据结构实验报告模板

2009级数据结构实验报告实验名称：约瑟夫问题学生姓名：李凯班级：21班班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList&List) //单链表排序 ListClear(&L); //将单链表L中的所有元素删除，使单链表变为空表 ListDestroy(&L);//将单链表销毁 }ADT List 其他函数：主函数；结点类; 约瑟夫函数 2.1 存储结构

[内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析结点类： template class CirList;//声明单链表类 template class ListNode{//结点类定义； friend class CirList;//声明链表类LinkList为友元类； Type data;//结点的数据域； ListNode*next;//结点的指针域； public: ListNode():next(NULL){}//默认构造函数； ListNode(const Type &e):data(e),next(NULL){}//构造函数 Type & GetNodeData(){return data;}//返回结点的数据值； ListNode*GetNodePtr(){return next;}//返回结点的指针域的值； void SetNodeData(Type&e){data=e;}//设置结点的数据值； void SetNodePtr(ListNode*ptr){next=ptr;} //设置结点的指针值； }; 单循环链表类： templateclass CirList { ListNode*head;//循环链表头指针 public: CirList(){head=new ListNode();head->next=head;}//构造函数，建立带头节点的空循环链表 ~CirList(){CirListClear();delete head;}//析构函数，删除循环链表 void Clear();//将线性链表置为空表 void AddElem(Type &e);//添加元素 ListNode *GetElem(int i)const;//返回单链表第i个结点的地址 void CirListClear();//将循环链表置为空表 int Length()const;//求线性链表的长度 ListNode*ListNextElem(ListNode*p=NULL);//返回循环链表p指针指向节点的直接后继，若不输入参数，则返回头指针 ListNode*CirListRemove(ListNode*p);//在循环链表中删除p指针指向节点的直接后继，且将其地址通过函数值返回 CirList&operator=(CirList&List);//重载赋

数据结构实验报告图实验

邻接矩阵的实现 1. 实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph（DataType a[], int n, int e）; ~MGraph（）{ void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; }

int vertexNum, arcNum; }; #endif MGraph.cpp #include using namespace std; #include "MGraph.h" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: " cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } }

数据结构实验报告

实验一约瑟夫问题实验学时：3学时实验类型：设计实验要求：必修一、实验目的熟练掌握线性链表的基础知识；能够使用C++或其他程序设计语言编程实现线性链表；能够使用线性链表构造正确而且时间复杂度低的算法解决实际问题；锻炼程序设计能力。二、实验内容 M个教徒和N个非教徒在深海上遇险，必须将N个人投入海中，其余的人才能幸免于难，于是想了一个办法：所有人围成一圆圈，从第一个人开始依次报数，每数到第K个人就将他扔入大海，如此循环进行直到仅余M个人为止。设计一个算法，找出这样一个排序：使每次被扔进大海的都是非教徒。并用程序设计语言实现。三、实验原理、方法和手段使用循环单链表，将每个人作为一个结点，每个结点的指针域指向下一个人，采用循环链表的遍历对每隔N-1个结点的结点进行标记，直至标记出N个结点为止。该实验亦可用顺序表实现。四、实验组织运行要求本实验采用集中授课形式，每个同学独立完成上述实验要求。五、实验条件每人一台计算机独立完成实验，有如下条件：（1）硬件：联想高性能PC机；（2）软件：VC++ 6.0、VC++.Net。六、实验步骤（1）编写循环链表构造函数Node *Create( )，使链表中每个结点的数据域值为0，并让最后一个结点的指针域指向第一个结点；（2）编写约瑟夫问题函数 Node *Move(Node *H,int n); void Insert(Node *H,int pos,int data); （5）主函数中调用Create，Move和Insert，采用具体数据计算，输出结果。七、实验程序 // stdafx.h : 标准系统包含文件的包含文件， // 或是经常使用但不常更改的 // 特定于项目的包含文件 // #pragma once #include"targetver.h" #include #include #include using namespace std;

北京理工大学数据结构实验报告4

《数据结构与算法统计》实验报告 ——实验四学院：班级：学号：姓名：

一、实验目的 1、熟悉VC 环境，学会使用C 语言利用顺序表解决实际问题。 2、通过上机、编程调试，加强对线性表的理解和运用的能力。 3、锻炼动手编程，独立思考的能力。二、实验内容从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。三、程序设计 1、概要设计为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型： ADT SqList{ 数据对象：D={|,1,2,,,0}i i a a Elem Set i n n ∈=≥ 数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作： InPut(SqList &L) 操作结果：构造一个线性表L 。 OutPut(SqList L) 初始条件：线性表L 已存在。操作结果：按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件：线性表L 已存在。操作结果：对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件：线性表L 已存在。操作结果：对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件：线性表L 已存在。操作结果：对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序，调用OutPut(L)函数显示排序结果。再由主程序首先调用InPut(L)函数创建顺序表，调用QuickSort(L)函数进行交换排序，调用OutPut(L)函数显示排序结果。再由主程序首先调用InPut(L)函数创建顺序表，调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序结果。 ⑶模块调用关系

数据结构实验报告

本科实验报告课程名称：数据结构（C语言版）实验项目：线性表、树、图、查找、内排序实验地点：明向校区实验楼208 专业班级：学号：学生姓名：指导教师：杨永强 2019 年 1 月10日

#include #include #include #define OK 1 typedef struct{//项的表示，多项式的项作为LinkList的数据元素float coef;//系数 int expn;//指数 }term,ElemType; typedef struct LNode{ //单链表节点结构 ElemType data; struct LNode *next; }LNode, *LinkList; typedef LinkList polynomial; int CreatLinkList(polynomial &P,int n){ //创建多项式P = (polynomial)malloc(sizeof(LNode)); polynomial q=P; q->next=NULL; polynomial s; for(int i = 0; i < n; i++){ s = (polynomial)malloc(sizeof(LNode)); scanf("%f%d",&(s->data.coef),&(s->data.expn)); q->next = s; s->next = NULL; q=q->next; } return OK; } 运行结果 2. void PrintfPolyn(polynomial P){ polynomial q; for(q=P->next;q;q=q->next){ if(q->data.coef!=1) printf("%g",q->data.coef);

数据结构实验报告无向图

《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。一、需求分析 1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出（3）以广度优先遍历输出（4）结束 5.测试数据：顶点数和边数：6,5 顶点信息：a b c d e f 边的顶点对应序号： 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出： a d e c b f 广度优先遍历输出： a d c b e f 二概要设计为了实现上述操作，应以邻接链表为存储结构。 1.基本操作： void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v)

以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块：（1）主程序模块（2）无向图的邻接链表存储模块（3）深度优先遍历输出模块（4）广度优先遍历输出模块 3.模块调用图：三详细设计 1.元素类型，结点类型和指针类型：typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析：（1）主程序模块 int main()

数据结构实验报告及心得体会

2011~2012第一学期数据结构实验报告班级：信管一班学号：201051018 姓名：史孟晨

实验报告题目及要求一、实验题目设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统），输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。三、实验报告说明实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。

三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1; } for(i=0;ia[i+1].score[j]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp; flag=1;

数据结构实验报告图实验

图实验一，邻接矩阵的实现 1.实验目的（1）掌握图的逻辑结构（2）掌握图的邻接矩阵的存储结构（3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容（1）建立无向图的邻接矩阵存储（2）进行深度优先遍历（3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template class MGraph { public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; }; #endif #include using namespace std; #include "" extern int visited[MaxSize]; template MGraph::MGraph(DataType a[], int n, int e) { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0;

数据结构实验报告

浙江科技学院《数据结构》实验报告年级班级学号姓名任课老师实验指导教师实验地点信息学院

实验一线性表操作（一元多项式的运算）实验目的： 1、定义线性表的链式存储 2、实现对线性表的一些基本操作和具体函数定义实验要求： 1、定义线性表的链式存储； 2、实现对线性表的一些基本操作和具体函数定义。 3、定义输出一元多项式的函数； 4、编写主程序调用上面的函数实现一元多项式的加减。数据输入输出要求：输入示例： 3 2 3 3 4 5 7 5 2 1 3 3 -3 4 4 6 5 7 （说明：第一个数据3表示该第一个一元多项式的项数为3，后面的2 3 表示第一项的系数为2 指数为3；按指数递增的次序输入）输出示例：一元多项式1： 2x(3)+3x(4)+5x(7) 一元多项式2： 2x(1)+3x(3)-3x(4)+4x(6)+5x(7) 加的结果：2x(1)+5x(3) +4x(6)+10x(7) 减的结果：-2x(1)-1x(3)＋6x(4)-4x(6) 程序代码： #include #include #include

#include #define null NULL #define polymal(poly*)malloc(sizeof(poly)) using namespace std; struct poly{ pair data; poly* next; }; void read(poly*a) { poly* poi = a; int n, xs, cs; cin >> n; for(int i = 0; i < n; i++) { poly* nex = polymal; cin >> cs >> xs; nex->data= make_pair(xs, cs); poi->next= nex; poi = poi->next; } poi->next= null; } void add(poly*a, poly*b, poly*ans) { poly* apo = a->next, *bpo = b->next, *cpo = ans; while(apo && bpo) { poly* sum = polymal; if(apo->data.first< bpo->data.first) { sum->data= apo->data; apo = apo->next; } else if(apo->data.first> bpo->data.first) { sum->data= bpo->data; bpo = bpo->next; } else{ sum->data= make_pair(apo->data.first, apo->data.second+bpo ->data.second); apo = apo->next, bpo = bpo->next; if(!sum->data.second) { free(sum); continue; } }

数据结构实验报告34354

合肥师范学院实验报告册 2013 / 2014 学年第2 学期系别计算机科学与技术系实验课程数据库原理专业计算机软件班级12级软件（1）班姓名张志强学号59 指导教师潘洁珠

实验一——数据库基本操作一、实验目的 1.熟悉MS SQL SERVER运行界面，掌握服务器的基本操作。 2.掌握界面操作方法完成用户数据库建立、备份和还原。 3.建立两个实验用的数据库，使用企业管理器和查询分析器对数据库和表进行基本操作。二、实验预习内容在认真阅读教材及实验指导书的基础上，上机前请预习以下内容，并在空白处填写相应的步骤或命令。 1.熟悉SQL SERVER 2000 的运行环境，练习服务器基本操作：打开、停止、关闭。 2.使用SQL SERVER 2000 中的企业管理器完成以下任务。数据库名称：STC 表：STU（sno char(9), sname varchar(50), ssex char(2) , sage int, sdept char(2) ）； COUTSES（cno char(3), cname varchar(50), cpno char(3), credit int ）； SC（sno char(9), cno char(3), grade int ）；说明：以上为表结构，以sno char（9）为例，说明sno属性设置为字符类型，宽度为9，int指整型数据。 1）建立数据库STC，分别建立以上三张表，并完成数据录入。（表结构及数据参见教材）2）分析并建立各表的主码，用下划线在上面表结构中标出主码。 3）建立各表之间的关联，请简述操作步骤。

数据结构实验报告 - 答案汇总

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

专业班级学号姓名实验1 实验题目：单链表的插入和删除实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。实验要求：建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序：（1）增加插入结点的功能。（2）将建立链表的方法改为头插入法。程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存

数据结构图实验报告

数据结构教程上机实验报告实验七、图算法上机实现一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。二、实验内容： 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "" #include "" #define MAXSIZE 30 typedef struct

{ char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge;

ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q }

(最新版)数据结构实验报告答案

《数据结构与算法分析》课程设计内容体系主要内容《数据结构课程设计》课程，可使学生深化理解书本知识，致力于用学过的理论知识和上机取得的实践经验，解决具体、复杂的实际问题，培养软件工作者所需的动手能力、独立解决问题的能力。该课程设计侧重软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧、多人合作，以至一整套软件工作规范的训练和科学作风的培养。一、课程设计要求学生必须仔细阅读《数据结构与算法分析》课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时的向教师汇报。课程设计按照教学要求需要两周时间完成，两周中每天（按每周5天）至少要上3-4小时的机来调试C语言设计的程序，总共至少要上机调试程序30小时。二、数据结构课程设计的具体内容本次课程设计完成如下模块（共9个模块，学生可以在其中至少挑选6个功能块完成，但有**号的模块是必须要选择的）（1）运动会分数统计** 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）功能要求：可以输入各个项目的前三名或前五名的成绩；

●能统计各学校总分； ●可以按学校编号、学校总分、男女团体总分排序输出； ●可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；（2）订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：可以订票（订票情况可以存在一个数据文件中，结构自己设定），如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；