数据结构实验报告一

数据结构实验报告

（实验名称）

1.实验目标

熟练掌握线性表的顺序存储结构和链式存储结构。

熟练掌握顺序表和链表的有关算法设计。

根据具体问题的需要，设计出合理的表示数据的顺序和链式结构，并设计相关算法。

2.实验内容和要求

内容：

<1>在第i个结点前插入值为x的结点。

实验测试数据基本要求：

第一组数据：线性表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2

第二组数据：线性表长度n=0，x=100，i=5

<2>删除线性表中第i个元素结点。

实验测试数据基本要求：

第一组数据：线性表长度n≥10，i分别为5,n,1,n+1,0

第二组数据：线性表长度n=0， i=5

<3>在一个递增有序的线性表L中插入一个值为x的元素，并保持其递增有

序特性。

实验测试数据基本要求：

线性表元素为（10,20,30,40,50,60,70,80,90,100）,

x分别为25，85，110和8

<4>求两个递增有序线性表L1和L2中的公共元素，放入新的顺序表L3中。

实验测试数据基本要求：

第一组

第一个线性表元素为（1，3，6，10，15，16，17，18，19，20）

第二个线性表元素为（1，2，3，4，5，6，7，8，9，10，18，20，30）第二组

第一个线性表元素为（1，3，6，10，15，16，17，18，19，20）

第二个线性表元素为（2，4，5，7，8，9，12，22）

第三组

第一个线性表元素为（）

第二个线性表元素为（1，2，3，4，5，6，7，8，9，10）

要求：每个题目分别用顺序存储和链式存储实现；

实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；

程序有适当的注释。

3.数据结构设计

顺序表结构，链表结构。

4.算法设计

（除书上给出的基本运算（这部分不必给出设计思想），其它实验内容要给出算法设计思想）

按顺序插入：首先插入一个元素，表长加一，用do，while循环整个顺序表，从最后一位开始，比x大的都向后移一位，在第一个小于x的后面停止遍历，吧x插在比x小的第一个数的后面。

寻找两个顺序表中相同的元素：运用嵌套循环，最外层循环遍历第一个表里面的元素为母元素，内部循环遍历第二个表为子元素。在子元素中查找与母元素相同的元素，改变第一个表里面的元素，把相同的放进去，最后删除表一中除了新放进来的元素。

5.运行和测试

顺序表：

1：

2：

3：

4：

链表：1：

2：

3：

4：

6.总结和心得

（这部分是重点，要认真写）

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串，线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

链表的结构非常多样，以下情况组合起来就有8种链表结构：

单向、双向

带头、不带头

循环、非循环

常用链表：无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头循环单链表：结构较无头单向非循环链表简单。实际操作当中使用较少。不带头双向循环链表：在Java的集合框架库中LinkedList底层实现就是不带头双向循环链表。

顺序表存储位置是相邻连续的，可以随即访问的一种数据结构，一个顺序表在使用前必须指定起长度，一旦分配内存，则在使用中不可以动态的更改。

他的优点是访问数据是比较方便，可以随即的访问表中的任何一个数据,缺点是定义的长度不可更改造成存储空间的浪费。链表是通过指针来描述元素关

系的一种数据结构，他可以是物理地址不连续的物理空间。不能随即访问链表元素，必须从表头开始，一步一步搜索元素。它的优点是：对于数组，可以动态的改变数据的长度，分配物理空间。在使用中如果一个数组在使用中，查询比较多，而插入，删除数据比较少，数组的长度不变时，选顺序表比较合理。如果插入，删除，长度不定的数组，可以选链表。

[7. 附录]

（源代码清单。纸质报告不做要求。电子报告，可直接附源文件，删除编译生成的所有文件）

seqList.h way.cpp线性表.cpp

数据结构实验报告格式

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

《数据结构》实验1实验报告

南京工程学院实验报告 <班级>_<学号>_<实验X>.RAR文件形式交付指导老师。 一、实验目的 1. 掌握查找的不同方法，并能用高级语言实现查找算法； 2. 熟练掌握二叉排序树的构造和查找方法。 3. 了解静态查找表及哈希表查找方法。 二、实验内容 设计一个算法读入一串整数，然后构造二叉排序树，进行查找。 三、实验步骤 1. 从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。 2. 在二叉排序树中查找某一结点。 3.用其它查找算法进行排序。

四、程序主要语句及作用 程序1的主要代码 public class BinarySearchTreeNode //二叉查找树结点 { public int key; public BinarySearchTreeNode left; public BinarySearchTreeNode right; public BinarySearchTreeNode(int nodeValue) { key = nodeValue; left = null; right = null; } public void InsertNode(BinarySearchTreeNode node)//插入结点 { if (node.key > this.key) { if (this.right == null) { this.right = node; return; } else this.right.InsertNode(node); } else { if (this.left == null) { this.left = node; return; } else this.left.InsertNode(node); } } public bool SearchKey(int searchValue) { if (this.key == searchValue) return true; if (searchValue > this.key) { if (this.right == null) return false; else return this.right.SearchKey(searchValue); } else { if (this.left == null) return false; else return this.left.SearchKey(searchValue); }

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

数据结构实验报告全集 实验一线性表基本操作和简单程序 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 始终指向生成的单链表的最后一个节点

数据结构实验报告

数据结构实验报告 一．题目要求 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）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件，

会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 （3）程序界面更加人性化。 Huffman Tree Demo (C) 2011-12-16 boj Usage: huffman [-c file] [-u file] output_file -c Compress file. e.g. huffman -c test.txt test.huff -u Uncompress file. e.g. huffman -u test.huff test.txt 目前的程序提示如上所示。如果要求实用性，可以考虑加入其他人性化的功能。 三、调研常用的压缩算法，对这些算法进行比较分析 （一）无损压缩算法 ①RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。 变体1：重复次数+字符 文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。

数据结构实验报告完整

华北电力大学 实验报告| | 实验名称数据结构实验 课程名称数据结构 | | 专业班级：学生姓名： 学号：成绩： 指导教师：实验日期：2015/7/3

实验报告说明： 本次实验报告共包含六个实验，分别为：简易停车场管理、约瑟夫环（基于链表和数组）、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。 编译环境：visual studio 2010 使用语言：C++ 所有程序经调试均能正常运行 实验目录 实验一约瑟夫环（基于链表和数组） 实验二简易停车场管理 实验三二叉树的建立和三种遍历 实验四图的建立和两种遍历 实验五哈希表的设计

实验一：约瑟夫环 一、实验目的 1.熟悉循环链表的定义和有关操作。 二、实验要求 1.认真阅读和掌握实验内容。 2．用循环链表解决约瑟夫问题。 3.输入和运行编出的相关操作的程序。 4.保存程序运行结果 , 并结合输入数据进行分析。 三、所用仪器设备 1.PC机。 2.Microsoft Visual C++运行环境。 四、实验原理 1.约瑟夫问题解决方案： 用两个指针分别指向链表开头和下一个，两指针依次挪动，符合题意就输出结点数据，在调整指针，删掉该结点。 五、代码 1、基于链表 #include using namespace std; struct Node { int data; Node* next; }; void main() { int m,n,j=1; cout<<"请输入m的值：";cin>>m; cout<<"请输入n的值：";cin>>n; Node* head=NULL; Node* s=new Node; for(int i=1;i<=n;i++) { Node* p=new Node; p->data=n+1-i;

数据结构实验报告模板

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、掌握线性表的定义； 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;

数据结构实验报告图实验

图实验一，邻接矩阵的实现 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．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 存储结构 带头结点的单链表

关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中 b、代码实现： Linklist::Linklist(int a[],int n)

堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)取链表长度函数 a、伪代码实现：判断该链表是否为空链表，如果是，输出长度0 如果不是空链表，新建立一个temp指针，初始化整形数n为0 将temp指针指向头结点 判断temp指针指向的结点的next域是否为空，如果不是，n加一，否 则return n 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next 域为0，返回n b 、代码实现 void Linklist::Getlength()Linklist(); cout<

数据结构实验总结报告

数据结构实验总结报告 李博杰PB10000603 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。 ①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件，会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。

数据结构实验报告一

数据结构实验报告 （实验名称） 1.实验目标 熟练掌握线性表的顺序存储结构和链式存储结构。 熟练掌握顺序表和链表的有关算法设计。 根据具体问题的需要，设计出合理的表示数据的顺序和链式结构，并设计相关算法。 2.实验内容和要求 内容： <1>在第i个结点前插入值为x的结点。 实验测试数据基本要求： 第一组数据：线性表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2 第二组数据：线性表长度n=0，x=100，i=5 <2>删除线性表中第i个元素结点。 实验测试数据基本要求： 第一组数据：线性表长度n≥10，i分别为5,n,1,n+1,0 第二组数据：线性表长度n=0， i=5 <3>在一个递增有序的线性表L中插入一个值为x的元素，并保持其递增有 序特性。 实验测试数据基本要求： 线性表元素为（10,20,30,40,50,60,70,80,90,100）, x分别为25，85，110和8 <4>求两个递增有序线性表L1和L2中的公共元素，放入新的顺序表L3中。 实验测试数据基本要求： 第一组 第一个线性表元素为（1，3，6，10，15，16，17，18，19，20） 第二个线性表元素为（1，2，3，4，5，6，7，8，9，10，18，20，30）第二组 第一个线性表元素为（1，3，6，10，15，16，17，18，19，20） 第二个线性表元素为（2，4，5，7，8，9，12，22） 第三组 第一个线性表元素为（） 第二个线性表元素为（1，2，3，4，5，6，7，8，9，10）

要求：每个题目分别用顺序存储和链式存储实现； 实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求； 程序有适当的注释。 3.数据结构设计 顺序表结构，链表结构。 4.算法设计 （除书上给出的基本运算（这部分不必给出设计思想），其它实验内容要给出算法设计思想） 按顺序插入：首先插入一个元素，表长加一，用do，while循环整个顺序表，从最后一位开始，比x大的都向后移一位，在第一个小于x的后面停止遍历，吧x插在比x小的第一个数的后面。 寻找两个顺序表中相同的元素：运用嵌套循环，最外层循环遍历第一个表里面的元素为母元素，内部循环遍历第二个表为子元素。在子元素中查找与母元素相同的元素，改变第一个表里面的元素，把相同的放进去，最后删除表一中除了新放进来的元素。 5.运行和测试 顺序表： 1： 2：

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

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、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难，到最后把这个做出来，付出了很多，也得到了很多，以前总以为自己对编程的地方还不行，现在，才发现只要认真做，没有什么不可能。 编程时要认真仔细，出现错误要及时找出并改正，（其中对英语的要求也体现出来了，因为它说明错误的时候都是英语）遇到问题要去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议，在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议，正所谓当局者迷旁观者清，把各个注意的问题要想到；同时要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，要注意符号的使用，注意对字符处理，特别是对指针的使用很容易出错且调试过程是不会报错的，那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。 通过近两周的学习与实践，体验了一下离开课堂的学习，也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子，在实行之的过程中并不是那么容易事让人有一种纸上谈兵的体会，正所谓纸上得来终觉浅绝知此事要躬行。实训过程中让我们对懂得的知识做了进一步深入了解，让我们的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人做事风格。 通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。 精品文档

数据结构实验报告[1]

云南大学 数据结构实验报告 第一次实验 学号： 姓名： 一、实验目的 1、复习变量、数据类型、语句、函数； 2、掌握函数的参数和值； 3、了解递归。 二、实验内容 1、（必做题）采用函数统计学生成绩：输入学生的成绩，计算并输出这些学生的最低分、最高分、平均分。 2、（必做题）采用递归和非递归方法计算k阶裴波那契序列的第n项的值，序列定义如下：f0=0, f1=0, …, fk-2=0, fk-1=1, fn= fn-1+fn-2+…+fn-k(n>=k) 要求：输入k(1<=k<=5)和n(0<=n<=30)，输出fn。 3、（选做题）采用递归和非递归方法求解汉诺塔问题，问题描述如下：有三根柱子A、B、C，在柱子A上从下向上有n个从大到小的圆盘，在柱子B和C上没有圆盘，现需将柱子A上的所有圆盘移到柱子C上，可以借助柱子B，要求每次只能移动一个圆盘，每根柱子上的圆盘只能大的在下，小的在上。要求：输入n，输出移动步骤。 三、算法描述 （采用自然语言描述） 1、①先输入需统计的学生人数。 ②根据学生人数输入成绩，计算成绩总和和平均分。 ③比较成绩大小，得出最低分和最高分。 ④输出计算结果。 2、⑴①写出不同情况下求k阶裴波那契序列的第n项的值的递归函数。 ②输入k和n。 ③输出计算结果。 四、详细设计 （画出程序流程图） 1、

2、⑴ 五、程序代码 （给出必要注释） 1、 #include #include #define N 100 /*先预计输入人数在0~100内，如果人数多于100再将100改成更大的数*/

void main() {int i,x[N],a; int max,min; float ave,sum=0.0; printf("请输入不多于%d的学生人数：",N); scanf("%d",&a); /*输入学生数*/ for(i=0;i=max) {max=x[i];} if(x[i]<=min) {min=x[i];} } printf("平均分是:%f",ave); printf("最高分是:%d",min); printf("最低分是:%d",max);/*输出平均分，最低分，最高分*/ return 0; } 2、 ⑴ #include #include int k; int Fibonacci (int n1) {if(n1

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

图实验 一，邻接矩阵的实现 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; } } template void MGraph::DFSTraverse(int v) { cout << vertex[v]; visited[v] = 1; for(int j = 0; j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0) DFSTraverse(j); } template void MGraph::BFSTraverse(int v) { int Q[MaxSize]; int front = -1, rear = -1; cout << vertex[v]; visited[v] = 1; Q[++rear] = v; while(front != rear) { v = Q[++front]; for(int j = 0;j < vertexNum; j++) if(arc[v][j] == 1 && visited[j] == 0){ cout << vertex[j]; visited[j] = 1;

数据结构实验报告

数据结构实验报告 第 6 次实验 学号：20141060106 姓名：叶佳伟 一、实验目的 1、复习图的逻辑结构、存储结构及基本操作； 2、掌握邻接矩阵、邻接表及图的创建、遍历； 3、了解图的应用。 二、实验内容 1、（必做题）假设图中数据元素类型是字符型，请采用邻接矩阵或邻接表实现图的以下基本操作： （ 1）构造图（包括有向图、有向网、无向图、无向网）； （ 2）根据深度优先遍历图； （ 3）根据广度优先遍历图。 三、算法描述 （采用自然语言描述） 四、详细设计 （画出程序流程图） 五、程序代码 （给出必要注释） #include #include #include #include #include #define INFINITY 255678 /*赋初值用*/ #define MAX_VERTEX_NUM 20 /* 最大顶点个数*/ enum {DG, DN, UDG, UDN}; typedef struct ArcCell {

int adj;/*顶点关系类型,对无权图,用1(是)或0(否)表示相邻否;对带权图,则为权值*/ char *info;/*弧相关信息指针*/ }AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM][5];/*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum, arcnum;/*图的当前顶点数和弧数*/ int kind; }MGraph; void CreateDG(MGraph *G); void CreateDN(MGraph *G); void CreateUDG(MGraph *G); void CreateUDN(MGraph *G); int LocateVex(MGraph *G, char v[]); void print(MGraph *G); int main(void) { MGraph *G; G = (MGraph *)malloc(sizeof(MGraph)); printf("请选者0-有向图,1-有向网,2-无向图,3-无向网: "); scanf("%d", &G->kind); switch(G->kind) { case DG : CreateDG(G); print(G); break; case DN : CreateDN(G); print(G); break; case UDG : CreateUDG(G); print(G); break; case UDN : CreateUDN(G);