北邮数据结构实验报告——线性表

线性表数据结构实验报告

1． 实验要求

一、 实验目的

通过选择下面四个题目之一进行实现，掌握如下内容：

熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法

学习指针、模板类、异常处理的使用

掌握线性表的操作的实现方法

学习使用线性表解决实际问题的能力

二、 实验内容

题目4

利用循环链表实现约瑟夫问题的求解。

约瑟夫问题如下：已知n 个人（n>=1）围坐一圆桌周围，从1开始顺序编号。从序号为1的人开始报数，顺时针数到m 的那个人出列；他的下一个人又从1开始报数，数到m 的那个人又出列；依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的编号。

2. 程序分析

2.1 存储结构

循环链表。线性表简称表，是由零个或多个具有相同类型的数据元素构成的有限序列。链表为了正确表示结点间的逻辑关系，在存储每个元素值的同时，还要存储该元素的直接后继元素的位置信息，这两部分信息构成了实际的存储结构，称为结点。如果将单链表的终端节点的指针域指向头结点，则整个链表构成一个环，成为单循环链表。如图所示：

创建链表完毕后，释放头结点，以便于操作，存储结构如下

2.2 关键算法分析

1．关键算法

约瑟夫问题的实质就是在含n 个元素的循环链表中依次删除第m 个元素，返回链表中最后一个元素值。即用数1、2、3…..n 初始化循环链表，从第一个元素开始查找第m-1个元素，删除第m 个元素，然后从第m+1个元素开始继续查找第m-1个元素，删除第m 个元

rear

rear

素，循环此过程直到链表中只剩下最后一个元素。

关键算法伪代码如下：

[1] 用数1、2、3…..n初始化循环链表，b指向头结点，rear指向尾节点,创建完毕后释放头

结点；

[2] 判断人数n或报数m是否为1；

[2.1] 人数n或报数m为1，将人数n赋给x；

[2.2] 当人数不为1时，进入循环；

[2.2.1] 初始化计数器i=1，之后满足循环条件i++；

[2.2.2] 查找第m-1个元素，p指向第m-1个元素；

[2.2.3] 初始化指针q指向p->next，p的指针域指向q的指针域，第m个元素摘链，删除q，指针p后移；

[2.2.4] 人数n减1；

[2.3] 尾指针rear指向最后的结点p，将此结点值赋给x；

[3] 返回x的值。

2．时间复杂度的计算

[1] O(n)

[2] O(1)

[2.1] O(1)

[2.2] O(n)

[2.2.1] O(n*m)

[2.2.2] O(n*m)

[2.2.3] O(n)

[2.2.4] O(n)

[3]O(1)

T(n) = n*m

2.3 其他

1、为了保证循环计数的准确，在含参构造函数中，创建结束后，特将无实际值

的头结点删去，这样就可以避免因头结点的存在而导致计数错误，也省去了

对头结点的判断。

伪代码如下：

[1] 初始化指针p，rear使其指向头结点；

[2] 用1、2、3…..n初始化循环链表；

[3] 将尾结点rear的指针域指向头结点的下一个结点，即第一个含值的结点；

[4] 删去p，即删除了头结点。

3. 程序运行结果

1．流程

（1）用1、2、3…..n初始化循环链表；

（2）计数，查找第m-1个元素，删除第m个元素，人数n减1；

（3）循环直到n=1，返回此刻的结点值。流程图如下

2、测试条件

N在正整数且整型范围内均可3、测试结果

4. 总结

（1）调试时出现的问题及解决方法

①在调试时出现了1 个无法解析的外部命令这一错误，在删除了析构函数后问

题解决

②起初未删除头结点，也忽略了对头节点的判断，之后将头结点释放，再次调整，

问题解决

③忽略了对m=1的判断，导致错误。增加对m的判断，问题解决。

（2）心得体会

熟悉了单循环链表的各种基本操作，特别对插入操作、查找操作和删除操作有了较深的理解，同时对于指针的使用更加熟练。在调试和异常处理上有了更多经验。在编程过程中，应特别注意边界问题的处理，以及要有很好的逻辑性。

（3）下一步的改进

代码运行之后可以进行多次情况判断，比如判断完一组人数和报数之后，可以继续让用户选择是否要继续进行输入人数、报数，进行判断，这样更加人性化。

附录：实验代码

#include

using namespace std;

template

struct Node //循环节点定义

{

T data; //编号

Node *next;

};

template

class CLinkList

{

public:

CLinkList() //无参构造函数

{

rear=new Node;

rear->next=rear;

}

CLinkList(int n);

int Josephus(int m,int n); //计算最后一个出列的人的编号

private:

Node *rear;

};

template

CLinkList::CLinkList(int n) //有参构造函数，是数据域依次为1、2、3....n {

rear=new Node;

rear->next=rear;

Node *b = rear;

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

{

Node *s=new Node ;

s->data = i;

s->next = rear->next;

rear->next = s;

rear = s;

}

rear->next = b->next;

delete b; //释放头节点便于操作

}

template

int CLinkList::Josephus(int m,int n) //计算最后一个出列的人的编号{

int x,i;

Node *p=rear->next;

if (n==1||m==1)

{

x=n;

}

else

{

while(n!=1)

{

i=1;

while (i!=(m-1))

{

p=p->next;

i++;

}

Node *q = p->next;

p->next = q->next;

delete q;

p = p->next;

n--;

} //剩余最后一个

x=p->data;

}

return x;

}

int main()

{

int M,N;

cout<<"请输入人数N:";

cin>>N;

if (N<=0)

{

cout<<"请输入正整数:";

cin>>N;

}

cout<<"请输入所报数M:";

cin>>M;

if (M<=0)

{

cout<<"请输入一个正整数:";

cin>>M;

}

CLinkList A(N);

cout<<"最后一个出列的人的编号:"<

return 0;

}

数据结构实验十一：图实验

一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义：

typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组

北邮信通院数据结构实验报告三哈夫曼编码器之欧阳光明创编

数据结构实验报告 欧阳光明（2021.03.07） 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期： 2014年12月11日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统 计，统计每个字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编 码，并将每个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并 将编码后的字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符 串进行译码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析， 讨论赫夫曼编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study

data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有 出现的 字符一律不用编码。 2. 程序分析 2.1 存储结构 Huffman树 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。

weight lchild rchildparent 2-1-1-1 5-1-1-1 6-1-1-1 7-1-1-1 9-1-1-1 weight lchild rchild parent

数据结构实验一题目一线性表实验报告

北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表

2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法

a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;idata=a[i]; r->next=s; r=s; } r->next=NULL; } 时间复杂度：O(n) 3、按位查找 a、伪代码实现: 初始化工作指针p和计数器j，p指向第一个结点，j=1 循环以下操作，直到p为空或者j等于1 b1：p指向下一个结点 b2：j加1 若p为空，说明第i个元素不存在，抛出异常 否则，说明p指向的元素就是所查找的元素，返回元素地址 b、代码实现 Node* Linklist::Get(int i)//得到指向第i个数的指针 {Node*p=front->next; int j=1; while(p&&j!=i)//p非空且j不等于i，指针后移 {p=p->next; j++;

数据结构实验报告图实验

图实验一，邻接矩阵的实现 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++) {

数据结构实验报告图实验

邻接矩阵的实现 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哈夫曼编码

数据结构实验报告 实验名称：实验3——哈夫曼编码 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月24日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 2. 程序分析 2.1存储结构： struct HNode { char c;//存字符内容 int weight; int lchild, rchild, parent; }; struct HCode

{ char data; char code[100]; }; //字符及其编码结构 class Huffman { private: HNode* huffTree; //Huffman树 HCode* HCodeTable; //Huffman编码表 public: Huffman(void); void CreateHTree(int a[], int n); //创建huffman树 void CreateCodeTable(char b[], int n); //创建编码表 void Encode(char *s, string *d); //编码 void Decode(char *s, char *d); //解码 void differ(char *,int n); char str2[100];//数组中不同的字符组成的串 int dif;//str2[]的大小 ~Huffman(void); }; 结点结构为如下所示： 三叉树的节点结构： struct HNode//哈夫曼树结点的结构体 { int weight;//结点权值 int parent;//双亲指针 int lchild;//左孩子指针 int rchild;//右孩子指针 char data;//字符 }; 示意图为： int weight int parent int lchild int rchild Char c 编码表节点结构：

数据结构线性表实验报告

《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 1.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求：

数据结构实验

实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include main() { intn,m,i=0,j=0,k=0,a[5],b[5],c[10];/* 必须设个m做为数组的输入的计数器，不能用i ，不然进行到while 时i 直接为5*/ for(m=0;m<=4;m++)scanf("%d",&a[m]);// 输入数组a for(m=0;m<=4;m++)scanf("%d",&b[m]);// 输入数组b while(i<5&&j<5) {if(a[i]b[j]){c[k]=b[j];k++;j++;} else{c[k]=a[i];k++;i++;j++;}// 使输入的两组数组中相同的数只输出一 个 } if(i<5) for(n=i;n<5;n++) {c[k]=a[n];k++;} elseif(j<5) for(n=j;n<5;n++) {c[k]=b[n];k++;} for(i=0;i

求A QB #include main() { inti,j,k=0,a[5],b[5],c[5];//A=a[5],B=b[5],A n B=c[5] for(i=0;i<5;i++)scanf("%d",&a[i]);// 输入a 数组 for(i=0;i<5;i++)scanf("%d",&b[i]);〃输入b 数组 for(i=0;i<5;i++) {for(j=0;j<5;j++) if(a[i]==b[j]){c[k]=a[i];k++;}// 当有元素重复时，只取一个放入 c 中} for(i=0;i #defineN4 main() { inti,j,m,k,a[N+1];//k 为最后输出数组的长度变量

北邮数据结构第四次实验题目一排序

数据结构实验报告实验名称：实验四排序（题目1） 姓名： 班级： 班内序号： 学号：

1．实验要求 实验目的：学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容：使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换 计为3次移动）。 3、对2的结果进行分析，验证上述各种算法的时间复杂度。 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 2.2 关键算法分析 2.2.1 插入排序 插入排序的基本方法是寻找一个指定元素在待排序元素中的位置，然后插入。一趟直接插入排序的C++描述过程如下： ①将待插入纪录赋值给哨兵r[0]：r[0]=r[i]; ②从后向前进行顺序查找：for(j=i-1;r[0]

{r[j+1]=r[j];move++; comp++;} //循环中移动计数器++ comp++; //比较计数器++ r[j+1]=r[0];move++; //移动计数器++ } comp++; //比较计数器++ } cout<<"本次直接插入排序数据长度为："<=1;d=d/2) //以d 为增量在子序列中进行插入排序 { for(int i=d+1;i<=n;i++) //一趟希尔排序 { if(r[i]0&&r[0]

北邮数据结构实验四-链表排序

数据结构实验报告 实验名称：实验四——链表的排序 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 [内容要求] 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒 （选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性 代码要求 1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出

2. 程序分析 2.1 存储结构 [内容要求] 存储结构：双链表 2.2 关键算法分析 [内容要求] 定义类： template class LinkList { public: LinkList(){front = new Node ;front->next=rear;front->prior=NULL;rear=new Node;rear->next=NULL;rear->prior=front;} LinkList(T a[],int n); void BackLinkList(T a[]);//恢复原链表 ~LinkList();//析构函数 void PrintList();//打印数列 void InsertSort();//插入排序 void BubbleSort();//冒泡排序 Node * Partion(Node *i,Node *j);//快速排序中寻找轴值的函数 void Qsort(Node *i,Node *j);//快速排序 void SelectSort();//选择排序 Node*front; Node*rear; }; 成员函数包括：构造函数：单链表，打印单链表，插入排序，快速排序，冒泡排序，选择排序，析构函数 公有成员：头指针和尾指针 1、构造函数： LinkList::LinkList(T a[],int n) { front=new Node; rear=new Node; front->prior=NULL;front->next=rear; rear->next=NULL;rear->prior=front; Node *s; for (int i=n-1;i>=0;i--) {

数据结构实验报告(图)

附录A 实验报告 课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号 专业班级：媒体161 组别：无 姓名：学号： 实验报告内容 验证性实验 一、预习准备： 实验目的： 1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围； 2、熟练掌握几种常见图的遍历方法及遍历算法； 实验环境：Widows操作系统、VC6.0 实验原理： 1.定义： 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的,）。 邻接矩阵——表示顶点间相联关系的矩阵 设G=(V,E) 是有n 1 个顶点的图，G 的邻接矩阵A 是具有以下性质的n 阶方阵特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2 有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n2 9

无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中， 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧） 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。图的遍历有两条路径：深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。 实验内容和要求： 选用任一种图的存储结构，建立如下图所示的带权有向图： 要求：1、建立边的条数为零的图；

北邮信通院数据结构实验报告三哈夫曼编码器

数据结构实验报告 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期：2014年12月11日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。

2. 程序分析 2.1 存储结构 Huffman树 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。 weight lchild rchild parent

2-1-1-1 5-1-1-1 6-1-1-1 7-1-1-1 9-1-1-1 weight lchild rchild parent 2-1-15 5-1-15 6-1-16 7-1-16 9-1-17 7017

数据结构线性表的应用实验报告

实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________

实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。

2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。

数据结构图实验报告

数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的xx优先搜索 3.图的xx优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "stdio.h" #include "stdlib.h" #define MAXSIZE 30 typedefstruct{charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵

}MGraph;//MGraph为采用邻近矩阵存储的图类型 voidCreatMGraph(MGraph *g,inte,int n) {//建立无向图的邻近矩阵g->egdes，n为顶点个数，e为边数inti,j,k; printf("Input data of vertexs(0~n-1): \n"); for(i=0;ivertex[i]=i; //读入顶点信息 for(i=0;iedges[i][j]=0; //初始化邻接矩阵 for(k=1;k<=e;k++)//输入e条边{}printf("Input edges of(i,j): "); scanf("%d,%d",&i,&j); g->edges[i][j]=1; g->edges[j][i]=1;}void main(){inti,j,n,e; MGraph *g; //建立指向采用邻接矩阵存储图类型指针 g=(MGraph*)malloc(sizeof(MGraph));//生成采用邻接举证存储图类型的存储空间}2)运行结果： printf("Input size of MGraph: "); //输入邻接矩阵的大小scanf("%d",&n); printf("Input number of edge: "); //输入邻接矩阵的边数scanf("%d",&e);

北邮数据结构实验 第三次实验 排序

数据结构实验报告 1．实验要求 (1)实验目的 通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 (2)实验内容 使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒 （选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试排序算法的正确性。 2. 程序分析 2.1 存储结构 顺序表: 示意图： 2.2 关键算法分析 （1）测试数据的产生：正序、逆序、随机数据 用两个数组实现乱序、顺序以及逆序数据的排序。 基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第

二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。 <1> pRandom1=new long int[Max+1];pRandom2=new long int[Max+1]; <2> srand((unsigned)time(NULL)); for(int i = 1; i <= Max;i++ ) pRandom2[i]=rand(); <3> memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int)); （2）排序算法： <1>插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。 /1/int j=0; /2/ for(int i =2; i <= Max;i++) parray[0]=parray[i];comparetimes[0]++; /4/parray[j+1]=parray[0];movetimes[0]+=2; 示意图： r1,r2,r3,…,ri-1,ri,ri+1,…,rn 有序区待插入无序区 <2>希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。 int Sort::ShellSort(long int parray[]) {int j=0; for(int d=Max/2;d>=1;d/=2) {for(int i=d+1;i<=Max;i++) { parray[0]=parray[i]; comparetimes[1]++; for(j=i-d;j>0 && parray[0]冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。 int Sort::BubbleSort(long int parray[])

数据结构实验一 实验报告

班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include #include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; // 定义函数返回值类型 typedef struct

{ char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next;

数据结构实验—图实验报告

精品文档数据结构 实 验 报 告

目的要求 １．掌握图的存储思想及其存储实现。 ２．掌握图的深度、广度优先遍历算法思想及其程序实现。 ３．掌握图的常见应用算法的思想及其程序实现。 实验内容 １．键盘输入数据，建立一个有向图的邻接表。 ２．输出该邻接表。 3．在有向图的邻接表的基础上计算各顶点的度，并输出。 4．以有向图的邻接表为基础实现输出它的拓扑排序序列。 5．采用邻接表存储实现无向图的深度优先递归遍历。 6．采用邻接表存储实现无向图的广度优先遍历。 7．在主函数中设计一个简单的菜单，分别调试上述算法。 源程序： 主程序的头文件：队列 #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int QElemType; typedef struct QNode{ //队的操作 QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; void InitQueue(LinkQueue &Q){ //初始化队列 Q.front =Q.rear =(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); //存储分配失败 Q.front ->next =NULL; } int EnQueue(LinkQueue &Q,QElemType e) //插入元素e为Q的新的队尾元素{ QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e;

数据结构线性表实验报告

实验报告 实验一线性表 实验目的： 1.理解线性表的逻辑结构特性； 2.熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 3.熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用； 4.掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。 实验原理： 线性表顺序存储结构下的基本算法； 线性表链式存储结构下的基本算法； 实验内容： 2－21设计单循环链表，要求： （1）单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。 （2）设计一个测试主函数，实际运行验证所设计单循环链表的正确性。 2－22 .设计一个有序顺序表，要求： （1）有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。 （2）设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。 （3）设计合并函数ListMerge（L1,L2,L3）,功能是把有序顺序表L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。 程序代码： 2－21（1）头文件LinList.h如下： typedef struct node { DataType data; struct node *next; }SLNode; /*（1）初始化ListInitiate(SLNode * * head)*/ void ListInitiate(SLNode * * head) { /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/ if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1);