北邮数据结构实验报告

北邮数据结构实验报告

北邮数据结构实验报告

一、引言

数据结构是计算机科学中的重要基础知识，对于计算机程序的设计和性能优化

起着至关重要的作用。本报告旨在总结北邮数据结构实验的相关内容，包括实

验目的、实验设计、实验过程和实验结果等。

二、实验目的

本次实验旨在通过实践操作，加深对数据结构的理解和应用能力。具体目的如下：

1. 掌握线性表、栈和队列等基本数据结构的实现方法；

2. 熟悉二叉树、图等非线性数据结构的构建和遍历算法；

3. 学会使用递归和非递归算法解决实际问题；

4. 培养编程实践能力和团队合作意识。

三、实验设计

本次实验包括以下几个部分：

1. 线性表实验：设计一个线性表类，实现线性表的基本操作，如插入、删除和

查找等。通过实验，了解线性表的顺序存储和链式存储结构的特点和应用场景。

2. 栈和队列实验：设计栈和队列类，实现栈和队列的基本操作，如入栈、出栈、入队和出队等。通过实验，掌握栈和队列的应用，如括号匹配、迷宫求解等。

3. 二叉树实验：设计二叉树类，实现二叉树的创建、遍历和查找等操作。通过

实验，熟悉二叉树的前序、中序和后序遍历算法，并了解二叉树的应用，如表

达式求值等。

4. 图实验：设计图类，实现图的创建、遍历和最短路径等操作。通过实验，掌

握图的邻接矩阵和邻接表表示方法，并了解图的深度优先搜索和广度优先搜索

算法。

四、实验过程

1. 线性表实验：根据实验要求，首先选择线性表的存储结构，然后设计线性表类，实现插入、删除和查找等基本操作。在实验过程中，遇到了一些问题，如

边界条件的处理和内存管理等，通过团队合作，最终解决了这些问题。

2. 栈和队列实验：根据实验要求，设计栈和队列类，实现入栈、出栈、入队和

出队等基本操作。在实验过程中，我们发现了栈和队列在实际应用中的重要性，如括号匹配和迷宫求解等，通过实验加深了对栈和队列的理解。

3. 二叉树实验：根据实验要求，设计二叉树类，实现二叉树的创建、遍历和查

找等操作。在实验过程中，我们发现了二叉树在表达式求值和排序等方面的应用，通过实验加深了对二叉树的理解。

4. 图实验：根据实验要求，设计图类，实现图的创建、遍历和最短路径等操作。在实验过程中，我们发现了图在社交网络和路线规划等方面的应用，通过实验

加深了对图的理解。

五、实验结果

通过实验，我们成功设计和实现了线性表、栈、队列、二叉树和图等数据结构

的基本操作，并解决了实际问题。实验结果表明，我们对数据结构的理解和应

用能力得到了提高，并且加深了对计算机科学的认识。

六、结论

本次北邮数据结构实验通过实践操作，加深了对数据结构的理解和应用能力。

通过团队合作，我们成功设计和实现了线性表、栈、队列、二叉树和图等数据

结构的基本操作，并解决了实际问题。实验结果表明，我们对数据结构的理解

和应用能力得到了提高，并且加深了对计算机科学的认识。希望通过这次实验，能够为我们今后的学习和工作打下坚实的基础。

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

数据结构实验报告 实验名称： 学生姓名： 班级： 班内序号： 学号： 日期： 实验描述：使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 一．程序分析 1.存储结构：双向链表 2.关键算法分析： a)插入排序：⒈从有序数列和无序数列{a2,a3，…，an}开始进行排序； ⒉处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。用ai与ai-1，a i-2，…，a1进行比较，找出合适的位置将ai插入； ⒊重复第二步，共进行n-i次插入处理，数列全部有序。 b)冒泡排序： 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 3.针对所有的元素重复以上的步骤，除了最后一个。 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 c)快速排序：一趟快速排序的算法是： 1.设置两个变量i、j，排序开始的时候：i=0，j=N-1； 2.以第一个数组元素作为关键数据，赋值给key，即key=A[0]； 3.从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；

4.从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换； 5.重复第3、4步，直到i=j；(3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i，j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。 d)简单选择排序：设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟后就完成了记录序列的排序。 3.代码详细分析： #include #include using namespace std; struct Node //建立节点 { int data; Node* last; Node* next; Node() { last=NULL; next=NULL; } }; class List //建立链表 { private: Node* front; Node* rear; int length; public: List(); List(int a[],int n); void Insert(int x,Node* p); //在p后面插入节点 void Delete(Node* p); //删除p节点 void Print(); //打印 void SeqSort(); //插入排序 void BubSort(); //冒泡排序 void QuiSort(); //快速排序 void Qui(Node* first,Node* end,int* c); //快速排序的递归函数 void SelSort(); //简单选择排序 }; List::List(int a[],int n) //构造函数

北邮数据结构实验报告

北邮数据结构实验报告 北邮数据结构实验报告 一、引言 数据结构是计算机科学中的重要基础知识，对于计算机程序的设计和性能优化 起着至关重要的作用。本报告旨在总结北邮数据结构实验的相关内容，包括实 验目的、实验设计、实验过程和实验结果等。 二、实验目的 本次实验旨在通过实践操作，加深对数据结构的理解和应用能力。具体目的如下： 1. 掌握线性表、栈和队列等基本数据结构的实现方法； 2. 熟悉二叉树、图等非线性数据结构的构建和遍历算法； 3. 学会使用递归和非递归算法解决实际问题； 4. 培养编程实践能力和团队合作意识。 三、实验设计 本次实验包括以下几个部分： 1. 线性表实验：设计一个线性表类，实现线性表的基本操作，如插入、删除和 查找等。通过实验，了解线性表的顺序存储和链式存储结构的特点和应用场景。 2. 栈和队列实验：设计栈和队列类，实现栈和队列的基本操作，如入栈、出栈、入队和出队等。通过实验，掌握栈和队列的应用，如括号匹配、迷宫求解等。 3. 二叉树实验：设计二叉树类，实现二叉树的创建、遍历和查找等操作。通过 实验，熟悉二叉树的前序、中序和后序遍历算法，并了解二叉树的应用，如表 达式求值等。

4. 图实验：设计图类，实现图的创建、遍历和最短路径等操作。通过实验，掌 握图的邻接矩阵和邻接表表示方法，并了解图的深度优先搜索和广度优先搜索 算法。 四、实验过程 1. 线性表实验：根据实验要求，首先选择线性表的存储结构，然后设计线性表类，实现插入、删除和查找等基本操作。在实验过程中，遇到了一些问题，如 边界条件的处理和内存管理等，通过团队合作，最终解决了这些问题。 2. 栈和队列实验：根据实验要求，设计栈和队列类，实现入栈、出栈、入队和 出队等基本操作。在实验过程中，我们发现了栈和队列在实际应用中的重要性，如括号匹配和迷宫求解等，通过实验加深了对栈和队列的理解。 3. 二叉树实验：根据实验要求，设计二叉树类，实现二叉树的创建、遍历和查 找等操作。在实验过程中，我们发现了二叉树在表达式求值和排序等方面的应用，通过实验加深了对二叉树的理解。 4. 图实验：根据实验要求，设计图类，实现图的创建、遍历和最短路径等操作。在实验过程中，我们发现了图在社交网络和路线规划等方面的应用，通过实验 加深了对图的理解。 五、实验结果 通过实验，我们成功设计和实现了线性表、栈、队列、二叉树和图等数据结构 的基本操作，并解决了实际问题。实验结果表明，我们对数据结构的理解和应 用能力得到了提高，并且加深了对计算机科学的认识。 六、结论 本次北邮数据结构实验通过实践操作，加深了对数据结构的理解和应用能力。

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

数据结构实验报告 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 有序区待插入无序区

北京邮电大学数据结构实验报告一 通讯录

数据结构实验报告 实验名称：实验一——题目二：建立通讯录管理 学生姓名：武文齐 班级：2011211113 班内序号：05 学号：2011210363 日期：2011年11月1日 1．实验要求 实现通讯录的建立、增加、删除、修改、查询等功能 能够实现简单的菜单交互，即可以根据用户输入的命令，选择不同的操作。 编写测试main()函数测试线性表的正确性 2. 程序分析 2.1代码 #include using namespace std; struct STUDENT { int ID; //学号 char name[10]; //姓名 char ch; //性别 char phone[13]; //电话 char addr[31]; //地址 struct STUDENT *next;//指向下一个学生的指针 }; class addresslist //定义类实现对通信录的操作 {

public: addresslist(); //构造函数建立通讯录并初始化 ~addresslist(); //析构函数释放开辟的内存空间 void adds(); //增加一个学生信息 void deletes(); //删除任意一个学生信息 void revise(); //修改任意一个学生的信息 void print(); //输出任意一个学生的信息 void control(); //对通信录操作的总控制 private: STUDENT *front; //建立头结点 int num; //定义学生的个数 }; addresslist::addresslist() //构造函数建立通讯录并初始化 { num=0; //通讯录建立，学生个数初始化为0 front=new STUDENT;front->next=NULL; //指针域为空，表示结束 cout<<"the addresslist have been built successfully "<next; //移动到下一个节点 delete front; //删除节点 } } void addresslist::adds( ) //增加一个学生信息 { STUDENT *s=new STUDENT; //为新增学生开辟空间 cout<<"please input id,name,sex,phone number and address in turns:"<>s->ID;cin>>s->name;cin>>s->ch;cin>>s->phone;cin>>s->addr; s->next=front->next;front->next=s; num++; //学生个数加1 }; void addresslist::deletes() //删除任意一个学生信息 { STUDENT *p=front,*l; //p用来指向删除节点的前一个位置，l保存删除要删节点后一个节点的地址 cout<<"please input the number you want to delete;"<

北邮数据结构 实验报告四——哈夫曼树

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

int weight;//结点权值 int parent;//双亲指针 int LChild;//左孩子指针 int RChild;//右孩子指针 }; 哈夫曼编码表： struct HCode//编码表的结点结构{ char data;//字符 char code[10];//编码 int k;//码长 }; 存储结构： 2.2 关键算法分析 一、初始化：

步骤： 1、设立数组，记录每一个字符出现的次数与字符对应的ASCII码 2、以字符不是回车或换行遍历输入的字符数组 3、将存储出现次数大于0的字符存储进叶子节点数组 4、相对应的，存储叶子结点的数据域字符出现的次数。 时间复杂度：O（n）空间复杂度：O（n） 二、创建哈夫曼树 步骤： 1、创建2n-1个数节点 2、将权值数组依次赋值进0到n-1的权值节点中 3、从0到i-1（最开始等于n-1）选择两个权值最小的节点x、y，将其连接为i节点的左 右孩子，改变x、y的双亲指针为i节点 4、I++，循环步骤4直到2n-1 时间复杂度：O（n^2）空间复杂度 O（n） 三、创建哈夫曼编码表 步骤： 1、创建n个编码表节点 2、依次将叶子节点的字符放入编码表节点数据域中 3、对每个编码表对应的树结点，向根节点开始回溯（为父节点的左孩子编码值为0，右孩 子为1，不断上移，直到根节点） 4、进行倒置 时间复杂度O（n）空间复杂度 O（n） 四、编码 步骤： 1、新建编码数组 2、从源码第一个字符开始在编码表中寻找到相应字符后将编码复制进编码数组 3、计算压缩比 时间复杂度O（n+e） n为源码 e为编码数组长度 空间复杂度O（n） 五、解码 步骤： 1、从根节点开始，按照编码串寻找（0为左子树，1为右子树）

北邮世纪学院数据结构实验文档

北邮世纪学院数据结构实验文档 实验一： <编程文档> <注意：生成日期和修改日期不需要填写，系统自动填写> <生成新文档的时候，需要修改页眉中标注的部分，不需要修改页脚> <修改文档之后，请刷新一下目录，由于我们的文档一般比较长，还是有目录比较好。> <文件名起名原则：_文档名称> 修订历史记录 本文档简要说明。

目录 修订历史记录 (1) 1问题描述 (3) 2主函数流程MAIN() (3) 2.1功能 (3) 2.2性能 (3) 2.3输人项 (3) 2.4输出项 (3) 2.5算法 (3) 2.6流程逻辑 (3) 2.7注释设计 (4) 2.8限制条件 (4) 3函数1设计说明 (4) 4源程序 (4) 5测试报告 (5) 5.1案例一：测试MAIN() (5) 5.2案例二：测试子函数 (5) 5.3尚未解决的问题 (5) 6心得体会 (5) 7分工及签名 (5)

1问题描述 给出对该程序的简要描述(作业题)，主要说明安排设计本程序的目的意义。 2主函数流程main() 2.1功能 说明该程序应具有的功能，可采用IPO图（即输入一处理一输出图）的形式。 2.2性能 说明对该程序的全部性能要求，包括对精度、灵活性和时间特性的要求。 2.3输人项 给出对每一个输入项的特性，包括名称、标识、数据的类型和格式、数据值的有效范围、输入的方式。数量和频度、输入媒体、输入数据的来源和安全保密条件等等。 2.4输出项 给出对每一个输出项的特性，包括名称、标识、数据的类型和格式，数据值的有效范围，输出的形式、数量和频度，输出媒体、对输出图形及符号的说明、安全保密条件等等。 2.5算法 详细说明本程序所选用的算法，具体的计算公式和计算步骤。 2.6流程逻辑 用图表（例如流程图、判定表等）辅以必要的说明来表示本程序的逻辑流程。 Word自带的绘图工具一般都不利于排版，建议使用Visio绘制所有的流程图和模块图，插入Word。 Visio可以有很多页，最好将自己的论文图片都放在一个vsd文件中。 流程图中的分支结构应该按照下面的例子来画：

北邮数据结构平衡二叉树报告概论

数据结构 实 验 报 告 实验名称：平衡二叉树

1.实验目的和内容 根据平衡二叉树的抽象数据类型的定义，使用二叉链表实现一个平衡二叉树。 二叉树的基本功能： 1、平衡二叉树的建立 2、平衡二叉树的查找 3、平衡二叉树的插入 4、平衡二叉树的删除 5、平衡二叉树的销毁 6、其他：自定义操作 编写测试main()函数测试平衡二叉树的正确性。 2. 程序分析 2.1 存储结构 struct node { int key; //值 int height; //这个结点的父节点在这枝最长路径上的结点个数 node *left; //左孩子指针 node *right; //右孩子指针 node(int k){ key = k; left = right = 0; height = 1; } //构造函数}; 2.2 程序流程

2.3 关键算法分析（由于函数过多，在此只挑选部分重要函数） 算法1：void AVL_Tree::left_rotate(node *&x) [1] 算法功能：对 R-R型进行调整 [2] 算法基本思想：将结点右孩子进行逆时针旋转 [3] 算法空间、时间复杂度分析：都为0（1） [4] 代码逻辑 node *y = x->right; y为x的右孩子 x->right = y->left; 将y的左孩子赋给x的右孩子 y->left = x; x变为y的左孩子 fixheight(x); 修正x，y的height值 fixheight(y); x = y; 使x的父节点指向y 算法2：void A VL_Tree::right_rotate(node *&x) [1] 算法功能：对L-L型进行调整 [2] 算法基本思想：将左孩子进行顺时针旋转 [3] 算法空间、时间复杂度分析：都为0（1） [4] 代码逻辑 node *y = x->left; //y为x的左孩子 x->left = y->right; y的右孩子赋给x的左孩子

北邮数据结构实验报告排序

数据结构实验报告 实验名称：实验四——排序 学生姓名： 班级： 班内序号： 学号： 日期：2014年12月19日 1．实验要求 实验目的 通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 实验内容 使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性。 2. 程序分析 首先，题目要求测试不同的数据，所以可以手动输入待排序元素。其次，由于对一组数据要求用不同的排序算法来处理，所以需要一个复制函数把排序前的无序数组寄存出去，为下一次排序做准备。再次，由于每次排序后都需要把排序后的结果打印出来，代

码是一样的，根据相同的代码可以封装成一个函数的思想，所以还需增加一个打印函数。 2.1 存储结构 本程序采用简单数组来储存输入的待排序数组 2.2 关键算法分析 核心算法思想： 1. 利用教材讲述的基本算法思想，实现七种排序算法，统计其运行相关数据。 2. 将七种排序函数入口地址作为函数指针数组，实现快速调用和统计。使得程序代码可读性增、结构更加优化。 关键算法思想描述和实现： 关键算法1：实现七种算法的基本排序功能。 1、插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全 部记录排序完毕。插入排序的思想是：每次从无序区取一元素将其添加到有序区中。 2、希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序， 待整个序列基本有序时，再对全体记录进行一次直接插入排序。 3、冒泡排序：两两比较相邻记录的关键码，如果反序则交换，直到没有反序记录为止。 4、快速排序：首先选择一个基准，将记录分割为两部分，左支小于或等于基准，右支则 大于基准，然后对两部分重复上述过程，直至整个序列排序完成。 5、选择排序：从待排序的记录序列中选择关键码最小（或最大）的记录并将它与序列中 的第一个记录交换位置；然后从不包括第一个位置上的记录序列中选择关键码最小（或最大）的记录并将它与序列中的第二个记录交换位置；如此重复，直到序列中只剩下一个记录为止。 2.3 其他 时间复杂度与空间复杂度 理论分析可以得出各种排序算法的时间复杂度和空间复杂度，如下表所示： 排序方法平均情况最好情况 辅助空间 最坏情况 直接插入排序O(n2) O(n) O(n2) O(1) 希尔排序O(nlog2n)~O(n2) O(n1.3) O(n2) O(1) 起泡排序O(n2) O(n) O(n2) O(1) 快速排序O(nlog2n) O(nlog2n) O(n2) O(log2n)~O(n2) 简单选择排O(n2) O(n2) O(n2) O(1)

北京邮电大学数据结构课程设计报告

《数据结构》 课程设计报告 设计题目：多级目录文件检索算法设计 姓名___________________ 学号___________________ 班级___________________ 同组组员___________________ 实验报告日期：

一.需求分析（详细说明要实现的功能和功能间的关系） 程序旨在实现一个在Linux系统下(以Ubuntu 11.10发行版为蓝本)进行多级目录文件检索的功能。 程序支持传统检索和多星号通配符检索，在搜索结果中给出符合条件文件的文件名，最后修改时间和路径，并按照最后修改时间排序。 程序提供窗口形式的图形界面。程序运行过程中用户只需手动输入待查的关键字，查找的根路径可以简明的图形界面方式选择。查找的结果在窗口中显示，允许用户对显示窗口的大小进行任意调节，并使用滚动条查看不能完全显示的部分。 二.算法思想（对于实现较为复杂的功能，要写出所使用的算法和算法的思路） 1- 文件查找 程序递归调用一个子函数Filesearch(ENTRYPTR LIST, char* input, const char *dir_name)来实现对文件的查找，其思想近于树的先根遍历。每到达一层目录程序均读取文件名（Linux 下文件夹也被看做是一个文件）并调用KMP算法进行匹配（节点访问过程），然后判定当前文件的性质（宏S_ISDIR），若该“文件”确实是一个文件，则停止向下遍历返回上一层；若该“文件”是一个文件夹，那么进入该文件夹递归遍历下一层。 2- 模式匹配 程序使用KMP算法进行文件名和模式的匹配。该算法首先分析模式的特征（重复性）并生成一个next数组，然后根据next数组的指示在主串上滑动模式进行匹配。这种算法可以避免对不可能匹配的情况进行比对，从而降低模式匹配过程的时间复杂度。 3- 通配符 程序中调用了如下函数 const* strtok(char* str1, char* str2); 这个函数的作用是按照str2对str1进行分割。具体的调用过程如下： 第一次调用时，函数在str1中搜索str2。如果存在，那么返回str2第一个字母以前的部分，同时str1中str2之前的部分被截去；如果不存在，返回str2整个串。 第二次之后调用时，str1参数应设置为NULL。若原str1中含有多个str2，那么每次调用都将返回并从str1中截去上一个str2到本次查找到的str2之间的部分，直到再没有str2时，返回NULL。 利用这个函数，要实现星号通配符的查找，我们只需每次接收strtok函数返回的串并使用其进行模式匹配即可。记录下每次查找返回的位置并将它们进行比较，如果各串出现的先后关系也符合模式的顺序，那么这个文件名就是符合我们查找要求的。 三.整体设计（整个设计包含哪些函数，函数间的相互关系，每个函数所实现的功能，主要函数实现的过程） 1- 函数调用关系 -main: 打开窗口，控制窗口的显示和关闭 -void on_button_clicked (GtkWidget* button, gpointer user_data) button对象的响应函数,用于触发查找 -int Filesearch(ENTRYPTR LIST, char* input, const char *dir_name)

北邮数据结构实验四

数据结构实验报告 实验名称：实验四排序——题目一 学生姓名： 班级： 班内序号： 学号： 日期：2012年12月15日 1．实验要求 使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性。 2. 程序分析 首先，题目要求测试不同的数据，所以可以手动输入待排序元素。其次，由于对一组数据要求用不同的排序算法来处理，所以需要一个复制函数把排序前的无序数组寄存出去，为下一次排序做准备。再次，由于每次排序后都需要把排序后的结果打印出来，代码是一样的，根据相同的代码可以封装成一个函数的思想，所以还需增加一个打印函数。最后，由于题目中要求计算代码的执行时间精确到微妙级，而c++库函数中的clock（）函数等只能精确到毫秒级，故需调用微软公司在其多媒体Windows中提供了精确定时器的底层API支持，本实验中调用queryperformancefrequency 和queryperformancecounter函数即可满足精确到微妙级的要求。 2.1 存储结构 本程序采用简单数组来储存输入的待排序数组。

2.2关键算法分析 2.2.1 插入排序算法 插入排序的思想是：每次从无序区取一元素将其添加到有序区中。 C++描述如下，其中形参r[]为待排序数组，n为待排序元素个数 2.2.2 希尔排序算法 希尔排序是一种缩小增量排序的算法，首先将待排序元素集按照一定间隔分成多个子集，分别对这些子集进行直接插入排序，整个序列部分有序。然后缩小间隔，在进行直接插入排序，直到间隔为1，此时，整个序列已全部有序。其c++描述如下：

北邮信通院数据结构实验二__八皇后问题实验报告(内附源代码完整版)

数据结构实验报告 实验名称：实验二一一八皇后问题 学生姓名： 班级： 班内序号： 学号： 日期：2014年11月27日 1 . 实验要求 实验目的】 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学 习使用队列解决实际问题的能力 实验内容】 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 提示： 1、可以使用递归或非递归两种方法实现 2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上 2.程序分析

2.1存储结构 存储结构：栈（递归） 22关键算法分析 ①递归调用摆放皇后 1、关键算法伪代码： （1） •如果输入的row 大于皇后的数量，则输出皇后的位置 （2） 否则col 从0开始递增 （3） 检测（row ，col ）上的点是否符合条件，不符合则col 自增，符合则转到下 一个皇后的排列 2、代码详细分析： void SeqStack::PlaceQuee n(i nt row) 5(1:10) S (1:10) P 却 ■1 HP P 的 tot]* 4 Z | X P K 0+-! 4訂 F P E* E J D P D P ◎ ■1 O B P bottam+J d -------- ► 1 A' //摆放皇后 播A.X 与Y 后的栈

for (int col=0;col< n;col++) // 遍历0~7 , { Push(col); if (Check()) //判断摆放皇后的位置是否合适 { if (row< n-1) //若还没有放到最后一个，则进行下一个皇后的放置 PlaceQuee n(row+1); else { nu m++; //计数器加1 Print(n); //打印成功的坐标点 } } Pop(); //若不符合条件则出栈} 3、计算时间复杂度：0(n2) ②判断皇后位置是否合适: 1、关键算法伪代码：

北邮数据结构实验报告三题目2-哈夫曼树

1 1．实验要求 利用二叉树结构实现哈夫曼编/ 解码器 (1). 初始化：能够对输入的任意长度的字符串s 进行统计，统计每个字符的频度，并建立哈夫曼树。 (2). 建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 (3). 编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 (4). 译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。 (5). 打印：以直观的方式打印哈夫曼树。 (6). 计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。 (7). 用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。 2.程序分析 2.1存储结构 二叉树：示意图：root 2.2

1 {2.3 关键算法分析 1. 定义哈夫曼树的模板类#include #include using namespace std; struct LNode { char ch; int weight; char code[20]; LNode* next; }; struct TNode { int weight; // int Lchild; // int Rchild; // int Parent; // }; class Huffman 结点权值 左孩子指针 右孩子指针 双亲指针 // 链表的节点, 用来统计字符频率，并编码 // 字符 // 权值 // 字符编码 // 指向下一个节点 // 哈弗曼树结点的结构体

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

2008级数据结构实验报告 实验名称：实验四排序 学生姓名： 班级： 班内序号： 学号： 日期： 实验要求 a. 实验目的 通过实现下述实验内容，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 b. 实验内容 2 题目2 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动 次数（其中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精 确到微秒（选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性

2.程序分析： 1.存储结构：单链表 结点结构体为： struct Node ｛ int data ； Node * next ｝ 2. 核心算法思想： 1. 利用教材讲述的基本算法思想，实现四种排序算法，统计其运行相关数据。 2. 将四种排序函数入口地址作为函数头指针，实现快速调用和统计。使得程序代码可读性 增、结构更加优化。 3. 关键算法的实现： 关键算法1： 实现四种算法的基本排序功能。 1、 插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排头结点，排序完毕。 具体实现为：每次将s 赋值为头结点，而p 最初赋值为第一个含有data 的指针。每次比较p 和s 的后继的数据大小，若是p 的数据小于s 的数据则将p 的后继结点插入到s 结点的后面同时s 返回到头结点重新比较插入，直至p 到达链表的尾部。 void LinkSort::InsertSort() //插入排序

北邮数据结构实验报告

北邮数据结构实验报告 北京邮电大学信息与通信工程学院 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;//编码表中的总字符数 二叉树的节点结构

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

数据结构实验报告 实验名称：实验一线性表——题目1 学生姓名：申宇飞 班级：信通3班 班内序号： 03 学号： 2012210064 日期： 2013年11月4日 1.实验要求 实验目的： 熟练掌握线性表的基本操作，包括：创建、插入、删除、查找、输出、求长度、合并等运算，以及各类操作在顺序存储结构和链式存储结构上的实现。 实验内容： 根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。 线性表存储结构（五选一）： 1、带头结点的单链表 2、不带头结点的单链表 3、循环链表 4、双链表 5、静态链表 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2.程序分析 2.1 存储结构 链表的具体存储表示为：

① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的） ② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息（称为指针） 链表的结点结构 ┌──┬──┐ │data│next│ └──┴──┘ data 域--存放结点值的数据域 next 域--存放结点的直接后继的地址（位置）的指针域（链域） 地址 内存单元 1000H 头指针 1020H 1080H 10C0H 2.2 关键算法分析 1、关键算法： 1：头插法 自然语言描述： a:在堆中建立新结点 b:将a[i]写入到新结点的数据域 c:修改新结点的指针域 d:修改头结点的指针域。将新结点加入链表中 伪代码描述 a:Node * s=new Node b:s->data=a[i] c:s->next=front->next; d:front->next=s 2：尾插法 自然语言描述： a:在堆中建立新结点： b:将a[i]写入到新结点的数据域：

北邮数据结构实验报告3二叉树含源码

数据结构实验报告 实验名称：实验三——树题目一 学生姓名：申宇飞 班级：2012211103 班内序号：03 学号：2012210064 日期：2013年12月3日 1．实验要求 掌握二叉树基本操作的实现方法 根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。 二叉树的基本功能： 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 4、后序遍历二叉树 5、按层序遍历二叉树 6、求二叉树的深度 7、求指定结点到根的路径 8、二叉树的销毁 9、其他：自定义操作 编写测试main()函数测试线性表的正确性 2. 程序分析 2.1 存储结构 采用二叉树的存储结构，其中每个二叉树的结点定义了一个结构体，该结构体包 含三个元素，分别是一个T类型的数据域data，一个指向T类型的指针左孩子，一个指向T 类型的指针右孩子，示意图如图所示。 采用了队列的存储结构。示意图如图所示：

对于二叉树中每个结点的data 域的赋值，我们事先把这些data 储存在一个数组中，通过对数组元素的调用事先对二叉树中每个结点的data 域的赋值。 2.2 关键算法分析 一：二叉树的建立： A ． 自然语言描述： 1首先判断调用的数组是否为空，如果为空，直接将一个已经初始化好的根节点置为空。 2 如果该数组不为空，则把调用的数组的第一个元素的赋给根节点的data 域。 3 采用递归的思想，分别将根节点的左右孩子作为根节点，递归调用该函数。完成对左右子树的赋值。 B ． 代码详细分析： template void BiTree::Create(Node *&R,T* buf,int i) { if (buf[i-1]==0) R = NULL; else { R=new Node; R->data = buf[i-1]; Create(R->lch, buf, 2*i); Create(R->rch, buf, 2*i+1); } lch data rch lch data rch lch data rch lch data rch lch data rch lch data rch

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

数据结构实验报告 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期：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 13238 16548 2967-1 2.2 关键算法分析 （1）计算出现字符的权值 利用ASCII码统计出现字符的次数，再将未出现的字符进行筛选，将出现的字符及頻数存储在数组a[]中。 void Huffman::Init() {

北邮数据结构上机 一元多项式

数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的测试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作实现方法 培养使用线性表解决实际问题的能力 实验内容： 利用线性表实现一个一元多项式Polynomial; f(x)=a0+a1x+a2x2+a3x3+…+anxn 提示：Polynomial的结点结构如下： struct term { float coef;\\系数 int expn;\\指数 }； 可以使用链表实现，也可以使用顺序表实现 具体要求如下： 能够实现一元多项式的输入和输出 能够进行一元多项式相加 能够进行一元多项式相减 能够计算一元多项式在x处的值 能够计算一元多项式的导数（选作） 能够进行一元多项式相乘（选作） 编写main ()函数测试算法的正确性 2. 程序分析 由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，

那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。 本程序完成的主要功能： 1、输入和输出：需要输入的信息有多项式的项数，用来向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。 2、多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到的结果都插入到新的链表中，形成结果多项式。 3、多项式在某点的值：由用户输入x 的值，然后求出每项的值相加即可。 4、多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。 5、多项式的乘法：根据输入信息八两多项式计算，并输出一个新的多项式。 2.1 存储结构 本程序采用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一个结点的地址。示意图如下： 2.2 关键算法分析 1、多项式的输入： 自然语言描述： 1. 设置多项式的项数n ； 2. 按照多项式的项数申请动态结构数组element *e=new element[n]存储多项式 的系数和指数； 3. 按照指数递增的次序输入各项的系数以及指数，分别存入coef 和exp ； 4. 再将输入的系数以及指数赋给每一个结点的coef 和exp 域； 5. 利用头插法将每个结点加入链表。 ·伪代码： 1. 输入项数n ； 2. element *e=new element[n]; 3. 运用for 循环，循环n 次 3.1 element *e=new element[n]; 3.2 cin>>e[i].exp; 3.3 cin>>e[i].coef; 3.4 return e; 4. 运用头插法将结点插入链表。 2、多项式的输出 ·自然语言描述： next coef1 exp1 next Coef2 exp2 next coefn expn next …… front