北邮数据结构实验报告

北京邮电大学信息与通信工程学院

第1页 数据结构实验报告

实验名称： 实验1——单链表的构造

学生姓名： XXXXNB

班 级： XXXX

班内序号：

学 号：XXXX

日 期： XXXXX

1．实验要求

根据线性表的抽象数据类型的定义，完成带头结点的单链表的基本功能。

单链表的基本功能：

1、构造：使用头插法、尾插法两种方法

2、插入：要求建立的链表按照关键字从小到大有序

3、删除

4、查找

5、获取链表长度

6、销毁

7、其他：可自行定义

编写测试main()函数测试线性表的正确性。

2. 程序分

编程完成单链表的一般性功能如单链表的构造：使用头插法、尾插法两种方法插入：要求建立的链表按照关键字从小到大有序，删除，查找，获取链表长度，销毁

用《数据结构》中的相关思想结合C++语言基本知识编写一个单链表结构。本程序为使用方便，几乎不用特殊的命令，只需按提示输入即可，适合更多的用户使用。

2.1 存储结构

单链表的存储结构：

北京邮电大学信息与通信工程学院

第2页

2.2 关键算法分析

1.头插法

自然语言描述：a.在堆中建立新结点

b.将a[i]写入到新结点的数据域

c.修改新结点的指针域

d.修改头结点的指针域,将新结点加入链表中

//在构建之初为了链表的美观性构造，进行了排序

代码描述：

//头插法构造函数

template

LinkList::LinkList(T a[], int n)

{

for (int i = n - 1; i >= 1; i--)//冒泡排序，对数组进行从小到大排序

{

for (int j = 0; j < i; j++)

{

if (a[j]>a[j + 1])

{

T t = a[j + 1];

北京邮电大学信息与通信工程学院

第1页 数据结构实验报告

实验名称： 实验一—线性表实现一个多项式

学生姓名： 黄锦雨

班 级：2011211109

班内序号： 20

学 号： 2011210263

日 期： 2012年10月31日

实验目的：

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

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

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

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

实验内容：

利用线性表实现一个一元多项式Polynomial

f(x) = a0 + a1x + a2x2 + a3x3 + … + anxn

要求：

1． 能够实现一元多项式的输入和输出

2． 能够进行一元多项式相加

3． 能够进行一元多项式相减

4． 能够计算一元多项式在x处的值

5． 能够计算一元多项式的导数（选作）

6． 能够进行一元多项式相乘（选作）

7． 编写测试main()函数测试线性表的正确性

2. 程序分析

由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。

两个多项式要进行多次的计算，为了保护原始的数据，方便进行以后的计算，故选择把结果存储在一个新建的链表里。

2.1本程序完成的主要功能：

1. 输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。

2. 多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到的结果都插入到新的链表中，形成结果多项式。

北邮数据结构实验报告

北京邮电大学信息与通信工程学院

2009级数据结构实验报告

实验名称：实验三哈夫曼编/解码器的实现

学生姓名：陈聪捷

日期：2010年11月28日

1.实验要求

一、实验目的：

了解哈夫曼树的思想和相关概念;

二、实验内容：

利用二叉树结构实现哈夫曼编/解码器

1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。

2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。

3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。

4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。

5.打印：以直观的方式打印哈夫曼树。

6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。 7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。

2.程序分析

2.1存储结构

二叉树

template

classBiTree

{

public:

BiTree();//构造函数，其前序序列由键盘输入

~BiTree(void);//析构函数

BiNode*Getroot();//获得指向根结点的指针

protected:

BiNode*root;//指向根结点的头指针

};

//声明类BiTree及定义结构BiNode

Data：

二叉树是由一个根结点和两棵互不相交的左右子树构成

data:

HCode*HCodeTable;//编码表

inttSize;//编码表中的总字符数

二叉树的节点结构 template

structBiNode//二叉树的结点结构{

Tdata;//记录数据

Tlchild;//左孩子

Trchild;//右孩子

Tparent;//双亲

};

编码表的节点结构

structHCode

{

北京邮电大学电信工程学院

数据结构实验报告

实验名称: 实验二一一栈和队

学生姓名: 申宇飞

班 级：

班内序号： 03

学 号：

日 期： 2013年11月18日

1- 实验要求

1.1实验目的：

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

> 进一步掌握指针、模板类、异常处理的使用

> 掌握栈的操作的实现方法

> 掌握队列的操作的实现方法

> 学习使用栈解决实际问题的能力

> 学习使用队列解决实际问题的能力

1.2实验内容

题目1

根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。

要求：

1、 实现一个共享栈

2、 实现一个链栈

3、 实现一个循环队列

4、 实现一个链队列

编写测试mainO函数测试线性表的正确性。

2. 程序分析

2.1存储结构

链栈：栈的链式存储结构,其实现原理类似于单链表，结点结构与单链表相同，但链栈 在实现时直接采用栈顶指针指向栈顶元素。 北京邮电大学电信工程学院

第］页北京邮电大学信息与通信工程学院

第3页

关键算法分析

链栈：

一、 入栈操作 算法步骤：

自然语言描述：

1、 建立新结点

2、 给p结点的数据域赋值

3、 修改p结点的指针域，将其指向栈顶结点

4、 栈顶指针指向p结点 伪代码描述：

1) Node * s = new Node;

2) p->data = x;

3) p->next = top;

4) top = p;

二、 出栈操作

算法步骤：

自然语言描述：

1、 判断栈是否为空

2、 保存栈顶结点的数据域

3、 定义指针p指向栈顶结点

4、 栈顶指针指向下一个结点

5、 释放p结点 伪代码描述：

1) if(EmptyO)throw" F溢“；

2) T x = top->data;

3) Node * p = top;

4) top = top->next;

5) elete p;

三、 链栈的取栈顶元素