实验报告数据结构与算法
编程是为了解决问题，这些问题并表都是数值计算，其所处理的数据并不都是数值，但计算机所能处理的最终是0和1的二进制串，所以需要把问题中的数据用计算机能处理的方式来表示，这就需要数据结构。
简单的说，数据结构是数据在计算机中的表示方式，有逻辑结构和物理结构之分，如逻辑上同样的队列，物理上可以是顺序存储，也可以是链式存储。
通俗的讲，算法就是解决问题的方法，比如同样的排序，可以用冒泡排序、插入排序等，不同的算法可以达到相同的目标，但是效率可能有所不同。
2. 数据结构完整版实验报告
(一)实验目的和要求
实验目的：熟练掌握线性表的基本操作在顺序存储结构上的实现。
实验要求：任选一种高级程序语言编写源程序，并调试通过，测试正确。
(二)实验主要内容
1. 建立n个元素的顺序表SqList，实现顺序表的基本操作；
2. 在SqList的元素i之后插入一个元素，实现顺序表插入的基本操作；
3. 在sqList中删除指定位置i上的元素，实现顺序表删除的操作。
4.
(三)主要仪器设备
PC机，Windows XP操作平台，Visual C++
(四)实验原理
顺序表操作：定义一个顺序表类，该类包括顺序表的存储空间、存储容量和长度，以及构造、插入、删除、遍历等操作的方法
(五)实验步骤与调试分析：
顺序表操作：先构造有四个数据的顺序表，在第4个位置插入9，再读取并删除第3个元素。
(六)实验结果与分析：
顺序表操作：
（七）附录（源程序）：
#include<iostream>
using namespace std;
const int LIST_INIT_SIZE=10; //顺序表初始长度
const int LISTINCREMENT=5; //顺序表长度增值
class SqList
{
int *L; //定义存储空间起始地址
int length; //顺序表当前长度
int listsize; //顺序表当前存储容量
bool flag; //设立标志值记录操作成败
public:
SqList(int v1,int v2,int v3,int v4); //构造函数构造并初始化顺序表
void ListInsert(int i,int e); //实现将e插入到顺序表中第i个位置
void ListDelete(int i,int &e); //实现删除顺序表第i个元素
void ListVisit(); //实现顺序表的遍历
};
SqList::SqList(int v1,int v2,int v3,int v4) //构造并初始化顺序表
{
L=new int[LIST_INIT_SIZE];
if(!L) //分配失败
{
flag=false;
cout<<"ERROR"<<endl;
}
else //分配成功，进行初始化
{
*L=v1;
*(L+1)=v2;
*(L+2)=v3;
*(L+3)=v4;
length=4;
listsize=LIST_INIT_SIZE;
flag=true;
}
}
void SqList::ListInsert(int i,int e) //插入元素
{
int *p,*q;
int t;
if(i<1||i>length+1) cout<<"ERROR"<<endl; //插入位置错误
else
{
if(length==listsize) //空间不足，增加分配
{
p=new int[listsize+LISTINCREMENT];
if(!p) cout<<"ERROR"<<endl; //分配失败
else //分配成功，复制顺序表
{
for(t=0;t<length;t++)
*(p+t)=*(L+t);
q=L;L=p;p=q;
delete q;
listsize+=LISTINCREMENT;
}
}
for(t=length;t>=i;t--)
*(L+length)=*(L+length-1);
*(L+i-1)=e;
length++; //插入成功，表长加1
}
}
void SqList::ListDelete(int i,int &e)
{
if(i<1||i>length) cout<<"ERROR"<<endl; //删除位置错误
else
{
e=*(L+i-1);
while(i<length)
{
*(L+i-1)=*(L+i);
i++;
}
length--; //删除成功表长减1
}
}
void SqList::ListVisit() //遍历
{
int i;
for(i=0;i<length;i++)
cout<<" "<<*(L+i);
cout<<endl;
}
int main()
{
int e=0;
SqList list(2,3,4,5);
list.ListVisit();
list.ListInsert(4,9);
list.ListVisit();
list.ListDelete(3,e);
list.ListVisit();
cout<<"e="<<e<<endl;
return 0;
}
3. 一文带你认识30个重要的数据结构和算法
数组是最简单也是最常见的数据结构。它们的特点是可以通过索引（位置）轻松访问元素。
它们是做什么用的？
想象一下有一排剧院椅。每把椅子都分配了一个位置（从左到右），因此每个观众都会从他将要坐的椅子上分配一个号码。这是一个数组。将问题扩展到整个剧院（椅子的行和列），您将拥有一个二维数组（矩阵）。
特性
链表是线性数据结构，就像数组一样。链表和数组的主要区别在于链表的元素不存储在连续的内存位置。它由节点组成——实体存储当前元素的值和下一个元素的地址引用。这样，元素通过指针链接。
它们是做什么用的？
链表的一个相关应用是浏览器的上一页和下一页的实现。双链表是存储用户搜索键哗显示的页面的完美数据结构。
特性
堆栈是一种抽象数据类型，它形式化了受限访问集合的概念。该限制遵循 LIFO（后进先出）规则。因此，添加到堆栈中的最后一个元素是您从中删除的第一个元素。
堆栈可以使用数组或链表来实现。
它们是做什么用的？
现实生活中最常见的例子是在食堂中将盘子叠放在宽枝一起。位于顶部的板首先被移除。放置在最底部的盘子是在堆栈中保留时间最长的盘子。
堆栈最有用的一种情况是您需要获取给定元素的相反顺序。只需将它们全部推入堆栈，然后弹出它们。
另一个有趣的应用是有效括号问题。给定一串括号，您可以使用堆栈检查它们是否匹配。
特性
队列是受限访问集合中的另一种数据类型，就像前面讨论的堆栈一样。主要区别在于队列是按照FIFO（先进先出）模型组织的：队列中第一个插入的元素是第一个被移除的元素。队列可以使用固定长度的数组、循环数组或链表来实现。
它们是做什么用的？
这种抽象数据类型 (ADT) 的最佳用途当然是模拟现实生活中的队列。例如，在呼叫中心应用程序中，队列用于保存等待从顾问那里获得帮助的客户——这些客户应该按照他们呼叫的顺序获得帮助。
一种特殊且非常重要的队列类型是优先级队列。元素根据与它们关联的“优先级”被引入队列：具有最高优先级的元素首先被引入队列。这个 ADT 在许多图算法（Dijkstra 算法、BFS、Prim 算法、霍夫曼编码 ）中是必不可少的。它是使用堆实现的。
另一种特殊类型的队列是deque 队列（双关语它的发音是“deck”）。可以从队列的两端插入/删除元素。
特性
Maps （dictionaries）是包含键集合和值集合的抽象数据类型。每个键都有一个与之关联的值。
哈希表是一种特殊类型的映射。它使用散列函数生成一个散列码，放入一个桶或槽数组：键被散列，结果散列指示值的存储位置。
最常见的散列函数（在众多散列函数中）是模常数函数。例如，如果常量是 6，则键 x 的值是x%6。
理想情况下，散列函数会将每个键分配给一个唯一的桶，但他们的大多数设计都采用了不完善的函数，这可能会导致具有相同生成值的键之间发生冲突。这种碰撞总是以某种方式适应的。
它们是做什么用的？
Maps 最着名的应用是语言词典。语言中的每个词都为其指定了定义。它是使用有序映射实现的（其键按字母顺序排列）。
通讯录也是一张Map。每个名字都有一个分配给它的电话号码。
另一个有用的应用是值的标准化。假设我们要为一天中的每一分钟（24 小时 = 1440 分钟）分配一个从 0 到 1439 的索引。哈希函数将为h(x) = x.小时*60+x.分钟。
特性
术语：
因为maps 是使用自平衡红黑树实现的（文章后面会解释），所以所有操作都在 O(log n) 内完成；所有哈希表操作都是常量。
图是表示一对两个集合的非线性数据结构：G={V, E}，其中 V 是顶点（节点）的集合，而 E 是边（箭头）的集合。节点是由边互连的值 - 描述两个节点之间的依赖关系（有时与成本/距离相关联）的线。
图有两种主要类型：有稿巧行向图和无向图。在无向图中，边(x, y)在两个方向上都可用：(x, y)和(y, x)。在有向图中，边(x, y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x, y)与箭头(y, x) 不同。
它们是做什么用的？
特性
图论是一个广阔的领域，但我们将重点介绍一些最知名的概念：
一棵树是一个无向图，在连通性方面最小（如果我们消除一条边，图将不再连接）和在无环方面最大（如果我们添加一条边，图将不再是无环的）。所以任何无环连通无向图都是一棵树，但为了简单起见，我们将有根树称为树。
根是一个固定节点，它确定树中边的方向，所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。
一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是唯一的。
它们是做什么用的？
我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你最古老的祖先是树的根。最年轻的一代代表叶子的集合。
树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。
特性
二叉树是一种特殊类型的树：每个顶点最多可以有两个子节点。在严格二叉树中，除了叶子之外，每个节点都有两个孩子。具有 n 层的完整二叉树具有所有2ⁿ-1 个可能的节点。
二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。
它们是做什么用的？
BT 的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法 (RPN)。这样，它们就可以形成一个二叉树，其中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树（AST）。
BST 经常使用，因为它们可以快速搜索键属性。AVL 树、红黑树、有序集和映射是使用 BST 实现的。
特性
BST 有三种类型的 DFS 遍历：
所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。
AVL 树在每次插入/删除后都是自平衡的，因为节点的左子树和右子树的高度之间的模块差异最大为 1。 AVL 以其发明者的名字命名：Adelson-Velsky 和 Landis。
在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。
在 Splay 树中，最近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然是 O(log n)。
它们是做什么用的？
AVL 似乎是数据库理论中最好的数据结构。
RBT（红黑树） 用于组织可比较的数据片段，例如文本片段或数字。在 Java 8 版本中，HashMap 是使用 RBT 实现的。计算几何和函数式编程中的数据结构也是用 RBT 构建的。
在 Windows NT 中（在虚拟内存、网络和文件系统代码中），Splay 树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索（替换用于长文本字符串的字符串）。
特性
最小堆是一棵二叉树，其中每个节点的值都大于或等于其父节点的值：val[par[x]]
4. 写一个数据结构的实验报告。要求研究数据结构的一个典型算法，有实验内容，实验步骤(代码)，分析，总结
课程设计任务书及成绩评定
课题名称
宿舍管理查询软件
Ⅰ、题目的目的和要求：
巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。
（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。
（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。
第四章详细设计
#include "fstream"
#include "iostream"
#include "cstring"
using namespace std;
/************************学生信息定义**********************************/
typedef struct Stu
{ char name[8];
char num[6];
char room[5];
}Stu;
typedef struct{
Stu *elem;
int length;
}Snode;
/*****************************学生信息处理及用户交互****************/
int Init_Stu(Snode &st); //创建学生信息
int Sort_Stu(Snode &st,intlow,int high); //快速排序算法
int Search_Stu(Snode st, char sn[]); //学生姓名二分查找并输出
void s(Stu &s1,Stu s2); //结构体s2赋给s1
int display(Snode st); //学生数据输出
void SavePass(); //密码问题
int quanxian(); //管理员登陆
/*******************************主函数程序****************************/
int main()
{ int suc=0;
charch1,choice,look[10];
Snode stu;
while(suc==0)
{ suc=quanxian();
if(suc==0)
{ cerr<<"您输入的用户信息不存在，请重新输入:"<<endl<<"退出输入'y'或 'Y',否则'n'或'N'："<<endl<<endl;
cin>>ch1;
if(ch1=='y'||ch1=='Y')
return0;
}
cout<<endl<<endl<<endl<<endl;
}
cout<<"\t\t****\n\n\t\t\t欢迎进入学生宿舍管理查询系统 \n\n\t\t****\n\n";
cout<<"\t\t\t***************主菜单***************\n\n";
5. 算法与数据结构实验顺序表的应用实验报告
者visual c++都行。
看看这个也许你会明白的更多一些。
实验一 多项式相加
一、实验目的
熟悉链表的使用。
掌握如何使用C语言实现链表的说明、创建以及结点的插入和删除等操作。
二、实验要求
熟悉C语言编程。
三、实验内容
对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到“和多项式”中去。
四、实验步骤
1. 用链表作一元多项式的数据结构，用C语言对链表作说明
2. 生成输入一元多项式的函数
3. 输入一元多项式A(x)和B(x)
4. 以一元多项式A(x)为和多项式，将B(x)多项式中系数加入到A(x)中去
实验二 后缀表达式计算
一、实验目的
熟悉栈的使用。
掌握如何使用C语言实现栈的说明、创建以及进栈和出栈等操作。
二、实验要求
熟悉C语言编程。
三、实验内容
先将中缀表达式（就是我们通常所见的）转换为后缀表达式，比如 a+b*c+d 要变成 abc*+d+；转换的方法用栈来实现，涉及到运算符的优先级；然后用另一个栈来对后缀表达式计算结果
四、实验步骤
1．读入字母/数字--〉字母/数字进栈
2．读入运算符--〉退出两个字母/数字，用运算符计算结果，并将结果进栈
3．栈能刚好退完，则最后的即为结果。否则表明表达式有误
实验三 Kmp算法
一、实验目的
熟悉字符串的使用。
掌握如何kmp算法实验字符串的模式匹配。
二、实验要求
熟悉C语言编程。
三、实验内容
求出子串（模式串）的next，利用kmp算法实验模式与主串的匹配算法。
四、实验步骤
1．生成模式串的next函数
2．从第1个字符开始，进行模式串与主串的比较，
3．如果出现失配，将模式串的第next[j]位置开始，继续与主串进行比较。
实验四 Huffman 编码
一、实验目的
熟悉Huffman编码方法。
了解并弄懂Huffman编码实现信息的无损压缩原理。
二、实验要求
熟悉C语言编程。
三、实验内容
1.根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F=，其中每棵二叉树Ti中只有一个带树为Ti的根结点
2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和
3.在F中删除这两棵树，同时将新得到的二叉树加入F中
4.重复2, 3，直到F只含一棵树为止
四、实验步骤
1．用C语言实现二叉树的说明
2．输入n个权值，并生成n个二叉树
3．对n个二叉树逐步生成Huffman树
4．对Huffman树的每个叶子结点生成编码
实验五 关键路径
一、实验目的
熟悉关键路径的实现方法。
了解AOE-网以及关键路径在工程实践中的应用。
二、实验要求
熟悉C语言编程。
三、实验内容
根据输入的弧，生成AOE-网。从始点开始，找出到终点的多条路径，求这些路径上的关键活动。由关键活动组成的从始点到终点的路径，即为关键路径。
四、实验步骤
1．输入e条弧，生成AOE-网的存储结构。
2．从始点v0出发，令ve[0]=0，按拓扑有序求ve[j]
3．从终点vn-1出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求vl[i]
4．根据各顶点的ve和vl值，求每条弧(活动)ai的最早开始时间e[ai]和最迟开始时间l[ai]
5．如果e[ai]=l[ai]，则ai为关键活动
实验六 最短路经
一、实验目的
熟悉最短路径的实现方法。
了解AOE-网以及最短路径在求解实际问题中的应用。
二、实验要求
熟悉C语言编程。
三、实验内容
从始点v0开始，逐步求v0到其它可达的各顶点的最短路径，直到所有顶点计算完成为止。
四、实验步骤
1．输入e条弧，生成AOE-网的存储结构。
2．初始化： S ← ;
dist[j] ← Edge[0][j], j = 1, 2, …, n-1; // n为图中顶点个数
3.求出最短路径的长度：
dist[k] ← min , i V- S ;
S ← S U ;
4.修改从v0到V-S集合中各顶点的最短路径：
dist[i] ← min,
对于每一个 i 属于 V- S ;
5.判断：若 S = V, 则算法结束，否则转 2。
实验七 二叉排序树
一、实验目的
熟悉二叉排序树的使用。
掌握如何使用C语言实现二叉树的说明、创建以及二叉排序树的生成等操作。
二、实验要求
熟悉C语言编程。
三、实验内容
给定一个记录关键字的值，与二叉排序树的根结点值比较，如果小于根结点的值，则向左子树查找；如果大于根结点的值，则向右子树查找。如果查找到叶子结点leaf，仍没有找到记录，则：如果关键字的值小于leaf的值，则插入该leaf结点的左边，做leaf的左孩子，否则做leaf的右孩子。
四、实验步骤
1．用C语言实现二叉树的说明
2．直接将输入的值作为根结点的值
3．与根结点比较，小于则放到左子树上，大于则放到右子树上。
实验八 希尔排序
一、实验目的
熟悉希尔排序的使用。
掌握如何使用C语言实现若干记录的排序。
二、实验要求
熟悉C语言编程。
三、实验内容
先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
四、实验步骤
1．输入待排序记录
2．首先取一个整数 gap < n(待排序记录数) 作为间隔, 将全部记录分为 gap 个子序列, 所有距离为 gap 的记录放在同一个子序列中
3．在每一个子序列中分别施行直接插入排序。
4．然后缩小间隔 gap, 例如取 gap = gap/2
5．重复上述的子序列划分和排序工作，直到最后取gap = 1, 将所有记录放在同一个序列中排序为止。
实验九 快速排序
一、实验目的
熟悉快速排序的使用。
掌握如何使用C语言实现若干记录的排序。
二、实验要求
熟悉C语言编程。
三、实验内容
通过一趟将待排记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小。再对两个部分分别进行快速排序。
四、实验步骤
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，直到整个记录有序为止
实验十 堆排序
一、实验目的
熟悉堆排序的使用。
掌握如何使用C语言实现若干记录的排序。
二、实验要求
熟悉C语言编程。
三、实验内容
首先将一个无序序列建成一个堆；然后输出堆顶元素；在输出堆顶元素之后，调整剩余的元素成为一个新堆。
四、实验步骤
1．输入记录，按顺序创建一个完全二叉树
2．根据筛选算法，从最后一个结点开始，一直到根结点，逐步筛选，建造初始堆。
3．输出堆顶记录，将最后一个结点放到堆顶，并做筛选，重新建造一个堆
4．直到所有记录输出为止
6. 01 - 数据结构和算法的认识
了解数据结构和算法的一些基本概念，主要掌握时间复杂度的计算
数据结构是指所有数据元素以及数据元素之间的关系，可以看做是相互之间存在着某种特定关系的数据元素的集合，即可以把数据结构看成是 带结构的数据元素的集合 。
数据的逻辑结构是从逻辑关系上描述数据的，常常将数据的逻辑结构简称为数据结构。
集合：
树形结构：
图形结构：
逻辑结构在计算机中的存储方式。依赖于计算机语言
顺序存储结构：
链式存储结构：
索引存储结构：
散列（哈希）存储结构：
数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称，数据类型是数据结构在计算机的具体体现。
注意：
算法是对特定问题求解步骤的一种描述
特性： 有穷性、确定性、可行性、有输入、有输出
算法设计好后，还需要分析算法的优劣，从两方面考虑
一个算法由控制结构和原操作构成，算法的运算时间取决于两者的综合效果，算法执行时间大致为基本运算时所需时间与运行次数的乘积。因此一个算法的执行效率可以由其最基本的运算的执行次数来衡量。
计算公式： T(n)=O(f(n))
说明：
注意： O 的作用在于只求出T(n)的最高阶项，忽略低阶项和常数
O(1)
没有进行循环的算法中，基本运算次数与问题规模无关，所以是常数
对数阶 O(log2n)
次数为x，而2的x次方等于n，那么就是对数阶
线性阶 O(n)
只有一层循环
平方阶 O(n^2)
立方阶 O(n^3)
三层循环，肯定就是n^3了
排序：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) <O(2^n) < O(n!) < O(n^n)
也叫加权平均时间复杂度，将执行的概率也加入计算。
是一种特殊的加权平均时间复杂度，把耗时多的操作分摊到耗时低的操作。
这个时间复杂度 其实是O(1),而不是O(n)
算法空间复杂度是指计算算法所需的存储空间， 其计算公式为S(n) = n(f(n))
所以在考察算法的空间复杂度，主要考虑算法执行所需要的临时占用的存储空间大小的量度。
数组逆序,将一维v1.43数组a中的n个数逆序存放在原数组中.
复杂度计算:
说明：
7. 什么是数据结构和算法
数据结构，Data_Structure，其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。数据结构则是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
数据结构是计算机专业学生在大学期间都会学习的一门课程，但是由于课程偏理论，缺乏实际操作的学习体验，而让大家产生了一种“数据结构不重要，我只要学习了Java/C语言/Python同样能敲代码”的错觉，但其实它是一门集技术性、理论性和实践性于一体的课程。
算法是某一系列运算步骤，它表达解决某一类计算问题的一般方法，对这类方法的任何一个输入，它可以按步骤一步一步计算，最终产生一个输出。
小码哥的李明杰也说过所有的计算问题，都离不开要计算的对象或者要处理的信息，如何高效的把它们组织起来，就是数据结构关心的问题，所以算法是离不开数据结构的，这就是数据与算法。