数据结构：一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系与操作等的学科。
数据：数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。
数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑与处理。
数据类型：是一个值的集合与定义在此集合上一组操作的总称。包括
原子类型：其值不可在分的数据类型
结构类型：其值可以在分解为若干成分的数据类型
抽象数据类型：ADT，指一个数学模型以及定义在该模型上的一组操作。通常用数据对象、数据关系、基本操作集这样的三元组来表示。有数据抽象与数据封装两个重要特性。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。包括（逻辑结构、存储结构与数据的运算）。
数据的逻辑结构：指数据元素之间的逻辑关系。包括集合、线性结构、树形结构、图状结构或网状结构。
数据的存储结构：指数据结构在计算机中的表示，也成物理结构。主要有顺序存储、连接存储、索引存储、散列存储。
数据的运算：施加在数据上的运算包括运算的定义与实现。定义是针对逻辑结构，指出运算的功能。实现是针对存储结构的，指出运算的具体操作步骤。
算法：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。有5个重要特性（有穷性、确定性、可行性、输入、输出）
算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求。
时间复杂度：一般情况下，算法中基本操作的重复次数是问题规模n的某个函数f（n），算法的时间度量记作T（n）=O（f（n）），表示随着问题规模n的增大，算法执行时间增长率与f（n）的增长率相同，称为时间复杂度。
空间复杂度：S（n）定义为该算法所耗费的村粗空间，是问题规模n的函数。
第二章：线性表
线性表：具有相同数据类型的n（n>=0）个数据元素的有限序列。
线性表的顺序存储又称顺序表；链式存储又称单链表。
静态链表：借助数组来描述线性表的链式存储结构，结点也有数据域与指针域。但指针是结点的相对地址（数组下标）。需要预先分配连续的内存空间。
栈：限定在表尾进行插入或删除操作的线性表。操作端称为栈顶，后进先出
队列：一种先进先出的线性表，只允许在表的一段插入元素，另一端删除元素，在队列中允许插入的一端为队尾，允许删除的一端为队头。
串：由零个或者多个字符组成的有限序列。串中任意个连续的字符组成的子序列称为该串的子串。字符在序列中的序号为该字符的位置。
树的结点包括一个数据元素以及若干指向其子树的分支。结点拥有的子树称为结点的度。度为0的结点称为叶子或终端结点。树的度是树内个结点的度的最大值。结点的子树的根称为该结点的孩子，相应的该节点为孩子的双亲。同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点的所经分支上的所有结点。反之，以某结点为根的子树中任一结点都称为该结点的子孙。
结点的层次：从树根开始定义，根结点为第1层，它的子结点为第2层，以此类推。
树的高度或深度：树中结点的最大层数。
有序树与无序树：树中结点的子树从左到右是有次序的，不能交换，叫做有序树。反之为无序树。
路径与路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。路径长度是路径上经过的边的个数。
树的路径长度：树根到每一个结点的路径长度之与
树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之与。
哈夫曼树：在含有N个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树或最优二叉树。
哈夫曼编码：一种广泛应用而且非常有效的数据压缩编码。
森林：m（m>=0）棵互不相交的树的集合。
二叉树：是另一种树形结构，每个结点至多有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
满二叉树：一棵高度为h，并且含有2^h -1个结点的二叉树称为满二叉树。即每层都有最多的结点，叶子集中在二叉树的最下一层且除叶子之外的每个结点度为2.
完全二叉树：设一个高度为h，有n个结点的二叉树，当且仅当其每一个结点都与高度为h 的满二叉树中编号为1-n的结点一一对应时，称为完全二叉树。
二叉排序树：一棵二叉树或是空二叉树或是具有以下性质的二叉树：左子树上所有关键字均小于根结点的关键字，右子树所有结点关键字大于根结点的关键字。左子树与右子树又各是一棵二叉排序树。
平衡二叉树：树上任一结点的左子树与右子树的深度之差不超过1.
平衡因子：该结点的左子树深度减去它的右子树深度。
二叉树的遍历：指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次且仅被访问一次。
线索二叉树：若结点有左（右）子树，则其lchild（rchild）域指向其左（右）孩子，否则令lchild（rchild）域指向其前驱（后继），这种结点构成的二叉链表作为二叉树的存储结构称为二叉链表。其中指向结点前驱与后继的指针叫做线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。
判定树：树中每个结点表示表中的一个记录，结点里的值为该记录在表中的位置，通常称这个查找过程的二叉树为判定树。
树的先根遍历：若树非空，则先访问根结点，再按从左到右的顺序遍历根节点的每一颗子树。其访问顺序与这棵树对应的二叉树的线序遍历顺序相同。
树的后跟遍历：若树非空，则按从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。其访问顺序与其对应的二叉树的中序遍历相同。
先序遍历森林：若森林非空，则按如下规则遍历：
·访问森林第一棵树的根结点
·选序遍历第一棵树中根结点的子树森林
·线序遍历除去第一棵树之后剩余的树构成的森林
中序遍历森林：若森林非空，则按如下规则进行遍历：
·中序遍历森林中第一棵树的根结点的子树森林
·访问第一棵树的根结点
·中序遍历除去第一棵树之后剩余的树构成的森林
图：由顶点集V与边集E组成，记作G=(V,E)
有向图：E为有向边的有限集合时，图G为有向图
无向图：E为无向边的有限集合时，图G为无向图
简单图：不存在重复边，不存在定点到自身的边称图G为简单图。与多重图相对
完全图：在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图。具有
n*（n-1）/2条边。有向图中，若任意两个顶点之间存在方向相反的两条弧，称为有向完全图，含有n（n-1）条有向边。
连通：若从顶点v到顶点w存在路径，则v与w是联通的。若图G中任意两个顶点都是联通的，则称图G为连通图，否则非连通图。无向图中的极大连通子图称为连通分量。
在有向图中，若从V到顶点W与从顶点W到顶点V都存在路径，则称两个顶点是强连通的，若图中任一对顶点都是强连通的，则称为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。
生成树与生成森林：连通图的生成树是包含图中所有顶点的一个极小连通子图。若顶点为n 则含有n-1条边。非连通图中，连通分量的生成树构成生成森林
最小生成树：一个带权连通无向图的生成树中边的权值之与最小的那个叫做此图的最小生成树。
有向树：如果一个有向图恰有一个顶点的入度为0，其余顶点的入度为1，则是一棵有向树。路径、路径长度与回路：顶点V到顶点Q之间的一条路径是指之间的一个顶点序列。路径的长度是路径上边的数目。第一个顶点与最后一个顶点相同的路径称为回路或环。
最短路径：带权图中，从一个顶点V0到另一个顶点V1的一条路径上所经过边的权值之与定义为该路径的带权路径长度，其中最短的那条称作最短路径。此路径的长度称为从v到u 的距离。
图的遍历：从图中某一顶点出发，按照某种搜索方法沿着图中的边对图中所有顶点访问一次且仅访问一次。
深度优先搜索：类似于树的先序遍历，假设从图中某顶点V出发，在访问了V之后一次从V 的未被访问的邻接点出发做深度优先遍历，知道图中所有与v有路径相同的顶点都被访问到。若图中还有顶点未访问，则另选图中一个未曾被方位的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问。
广度优先搜索：类似于树的层次遍历，从顶点v出发，访问了V之后依次访问v的各个未被访问过的邻接顶点。再依次访问它们的邻接点，并使先被访问的顶点的的邻接点先于后访问的顶点的邻接点。直到图中所有已被访问顶点的邻接点都被访问到。如果图中还有顶点未被访问，则另选一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问。AOV网，用有向无环图表示一个工程，顶点表示活动，有向边
AOE网，在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销（如时间），则称这个网络为AOE网。
关键路径：在AOE网中，路径长度最长的路径叫做关键路径，关键路径上的所有活动都是关键活动。
拓扑排序：由一个有向无环图的顶点组成的序列，当且仅当满足下列条件，称为该图的一个拓扑排序——1，每个顶点出现且仅出现一次。2若顶点a在b之前，不存在b到a的路径。查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
查找表（查找结构）：用于查找的数据集合称为查找表。
静态查找表：如果一个查找表的操作仅涉及查询某个特定的数据元素是否在查找表中与检索满足条件的某个特定的数据元素的各种属性，则称为静态查找表。
动态查找表：需要动态的插入或删除的查找表称为动态查找表。
关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
平均查找长度（ASL）：在查找的过程中，一次查找的长度指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。
折半查找：仅适用于有序的顺序表。将给定的值key与表中间位置元素的关键字比较，相等则查找成功返回位置。若不等则缩小查找范围，重复查找直到找到或者确定表中没有需查找的元素。
散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，
冲突：散列函数可能会把两个或以上的不同关键字映射到同一地址，这种情况为冲突
散列表：是根据关键字而直接进行访问的数据结构。散列表建立了关键字与存储地址指间的一种直接映射关系。
开放定址法：指的是可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。
拉链法（链地址法）：把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。
装填因子：是哈希表中填入的记录数与哈希表的长度之商，哈希表的平均查找长度是装填因子的函数，不是规模的函数。（散列表的查找效率取决于三个因素：散列函数/处理冲突的方法与装填因子）
二次聚集：指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象。
第十章：内部排序
排序：重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程。
算法的稳定性：假设Ri=Rj，且在排序之前Ri领先于Rj，若在排序后的序列中Ri仍然领先于Rj，则称所用的排序算法是稳定的，反之则称所用的算法是不稳定的。
内部排序：排序期间元素全部存放在内存中的排序；外部排序是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断的在内外存指间移动的排序。
插入排序：每次将一个待排序的记录，按关键字大小插入到前面已经排好序的子序列中，直至全部记录插入完成。
希尔排序：又称缩小增量排序，先将整个记录序列分割成若干子序列分别进行直接插入排序，待整个序列中记录基本有序时，再对全体进行一次直接插入排序。
冒泡排序：从前往后（或从后往前）两两比较相邻元素的值，若为逆序则交换，知道序列比较完，既完成一趟冒泡排序。这一趟确定的最小元素不再参与比较，重复上述过程直到一趟排序没有记录交换。
快速排序：通过一趟排序将带排记录分割成独立两部分，其中一部分的关键字均比另一部分小，分别对两部分再进行快速排序直至整个序列有序
选择排序：每一趟在未排序的记录中选择最小的记录作为有序序列部分的下一个记录。
归并排序：将两个或两个以上的有序表组合成一个新的有序表。二路归并排序的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。
基数排序：采用多关键字排序思想，借助“分配/收集”两种操作对但逻辑关键字进行排序。堆排序：一种树形选择排序方法。在排序过程中把L[1...N]堪称一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲与孩子之间的关系，在当前无序区选择最大或最小的元素。堆：n个关键字序列L[1...n]称为堆，当却仅当该序列满足：1，L（i）<=L(2i)且L（i）<=L(2i)或者2，L（i）>=L(2i)且L(i)<=L(2i)。
数据：是对客观事物的符号表示。 数据元素：是数据的基本单位，也称节点（node）或记录（record）。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。 数据项：有独立含义的数据最小单位，也称域(field)。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 根据数据元素间关系的基本特性，有四种基本数据结构集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 线性结构：结构中的数据元素之间存在一个对一个的关系。 树形结构：结构中的数据元素之间存在一个对多个的关系。 图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。 逻辑结构：抽象反映数据元素之间的逻辑关系。（算法设计）物理结构（存储结构）：数据结构在计算机中的表示。（算法实现） 存储结构分为： 顺序存储结构：借助元素在存储器中的相对位置来表
示数据元素间的逻辑关系。 链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。 算法：对特定问题求解步骤的一种描述。 算法的五个重要特性：有穷性，确定性，可行性，输入和输出。 算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。 衡量算法效率的方法：事后统计法和事前分析估算法。 算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n))，称T (n) 为算法的(渐近)时间复杂度算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。 栈：限定仅在表尾进行插入或删除操作线性表。入栈：插入元素的操作；出栈：删除栈顶元素的操作。 队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目； 空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号； 相等：串的值相等；空格串：由一个或多个空格组成的串，
第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 河南城建学院 《数据结构》课程设计任务书 班级0832131 专业计算机科学与技术 课程名称数据结构 指导教师张延红、薛冰 计算机科学与工程系 2018年6月 《数据结构》课程设计任务书 一、设计时间及地点 1、设计时间：第15周 2、设计地点：计算机系机房212、207 二、设计目的和要求 数据结构课程设计是在学完数据结构课程之后的实践教案环节。该实践教案是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力，培养科学的软件工作方法。学生通过数据结构课程设计在下述各方面得到锻炼： 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。 学生认真主动完成课程设计的要求，发挥自主学习的能力，充分利用时间，安排好课程设计，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。 三、设计题目和内容 建议设计题目： 1、运动会分数统计 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子工程，和w 个女子工程。工程编号为男子1……m，女子m+1……m+w。不同的工程取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。 数据结构概念名词解 释大全 数据：是对客观事物的符号表示。 数据元素：是数据的基本单位，也称节点（node）或记录（record）。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。 数据项：有独立含义的数据最小单位，也称域(field)。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 根据数据元素间关系的基本特性，有四种基本数据结构 集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。 线性结构：结构中的数据元素之间存在一个对一个的关系。 树形结构：结构中的数据元素之间存在一个对多个的关系。 图状结构或网状结结构：结构中的数据元素之间存在多个对多个的关系。 逻辑结构：抽象反映数据元素之间的逻辑关系。（算法设计） 物理结构（存储结构）：数据结构在计算机中的表示。（算法实现） 存储结构分为： 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。 链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。 算法：对特定问题求解步骤的一种描述。 算法的五个重要特性：有穷性，确定性，可行性，输入和输出。 算法设计的原则或要求：正确性，可读性，健壮性，效率与低存储量需求。 衡量算法效率的方法：事后统计法和事前分析估算法。 算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n))，称T (n) 为算法的(渐近)时间复杂度 算法运行时间的衡量准则：以基本操作在算法中重复执行的次数。 栈：限定仅在表尾进行插入或删除操作线性表。入栈：插入元素的操作；出栈：删除栈顶元素的操作。 队列：只能在队首进行删除、队尾进行插入的线性表。允许插入的一端叫队尾，删除的一端叫队头。串：由零个或多个字符组成的有限序列；空串：零个字符的串；长度：串中字符的数目； 空串：零个字符的串；子串：；串中任意个连续的字符组成的子序列；位置：字符在序列中的序号； 相等：串的值相等；空格串：由一个或多个空格组成的串，空格串的长度为串中空格字符的个数。 存储位置：LOC(i ,j)=LOC(0,0)+(b2*i+j)L 结点:包含一个数据元素及若干指向其子树的分支；结点的度: 结点拥有的子树； 树的度:树中所有结点的度的最大值；叶子结点: 度为零的结点；分支结点: 度大于零的结点 树的深度：树中叶子结点所在的最大层次森林：m棵互不相交的树的集合。 二叉树的性质： 性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i≥1) 性质 2：深度为 k 的二叉树上至多含 2k-1 个结点。（k≥1） 性质 3: 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。 性质 4: 具有 n 个结点的完全二叉树的深度为? log2n? +1。 满二叉树：指的是深度为k且含有2k-1个结点的二叉树。 完全二叉树：树中所含的n 个结点和满二叉树中编号为1 至n 的结点一一对应。 Data Structure 2015 hash table散列表：存放记录的数组 topological sort拓扑排序：将一个DAG中所有顶点在不违反前置依赖条件规定的基础上排成线性序列的过程称为拓扑排序（44） worst case 最差情况：从一个n元一维数组中找出一个给定的K，如果数组的最后一个元素是K，运行时间会相当长，因为要检查所有n 个元素，这是算法的最差情况（15） FIFO先进先出：队列元素只能从队尾插入，从队首删除（20）（P82）2014 growth rate增长率：算法的增长率是指当输入的值增长时，算法代价的增长速率（14） priority queue 优先队列：一些按照重要性或优先级来组织的对象成为优先队列（26） external sorting外排序：考虑到有一组记录因数量太大而无法存放到主存中的问题，由于记录必须驻留在外存中，因此这些排序方法称为外排序（32） connected component连通分量：无向图的最大连通子图称为连通分量（40） 2013 stack栈：是限定仅在一端进行插入或删除操作的线性表（19） priority queue 优先队列：一些按照重要性或优先级来组织的对象成为优先队列（26） BFS广度优先搜索：在进一步深入访问其他顶点之前，检查起点的所有相邻顶点（42） collision (in hashing)冲突：对于一个散列函数h和两个关键码值k1和k2，如果h(k1) =β= h(k2) ，其中β是表中的一个槽，那么就说k1和k2对于β在散列函数h下有冲（35） Chapter 1 Data Structures and Algorithms type类型：是指一组值的集合 data type数据类型：一个类型和定义在这个类型上的一组操作abstract data type (ADT) 抽象数据类型：指数据结构作为一个软件构件的实现 data structure数据结构：是ADT的实现 problem问题：一个需要完成的任务，即对应一组输入，就有一组相应的输出 function函数：是输入和输出之间的一种映射关系 algorithm算法：是指解决问题的一种方法或者一个过程algorithm算法是解决问题的步骤，它必须把每一次输入转化为正确的输出；一个算法应该由一系列具体步骤组成，下一步应执行的步骤必须明确；一个算法必须由有限步组成；算法必须可以终止。computer program计算机程序：被认为是使用某种程序设计语言对一个算法的具体实现 数据结构课程设计 报告 数据结构课程设计报告 压缩软件 一·问题描述 利用哈夫曼编码设计一个压缩软件，能对任何类型的文件进行哈夫曼编码，产生编码后的文件——压缩文件;也能对输入的压缩文件进行译码，生成压缩前的文件——解压文件。 二·基本要求 要求编码和译码的效率尽可能地高。 三·工具/准备工作 已学内容:哈夫曼树，哈夫曼树构造算法，哈夫曼编码，Huffman压缩算法。 需要的硬件设施与开发软件：一台计算机，并安装了Visual C++. 四·分析与实现 Huffman树中，叶子结点包含字符以及对应的字符频度（权值） struct HTNode{ //压缩用Huffman树结点 unsigned long weight; //字符频度（权值） unsigned int parent,lchild,rchild; }; 使用哈夫曼编码能够对文件进行压缩，由于字符的哈夫曼编码以比特为单位，而当将哈夫曼编码以压缩文件进行存储时，压缩文件最少以字节为单位进行存储，因此需要定义字节缓冲器，以便自动将比特转换为字节，定义如下： struct Buffer{ //字节缓冲压缩用Huffman树 char ch; //字节 unsigned int bits; //实际比特数 }; 定义哈夫曼树的抽象基类模板，实现建树，压缩，解压等功能 class HuffmanTree{ //Huffman树 public: void Code(); //编码 void UnCode(); //译码 private: HTNode HT[m+1]; //树结点表(HT[1]到HT[m]) char Leaf[n+1]; //叶结点对应字符(leaf[1]到leaf[n]) char *HuffmanCode[n+1]; //叶结点对应 1.数据结构：数据结构是所有数据元素以及数据元素之间的关系，可以看作是相互之间存 在着某种特定关系的数据元素的集合。 2.逻辑结构:逻辑结构是从逻辑关系上描述数据的，与存储结构无关，是独立于计算机的， 可以看作是从具体问题抽象出来的数学模型。 a.集合：指数据元素之间除了同属于一个集合的关系外，别无其他关系。 b.线性结构：指该结构中的节点之间存在着一一对应的关系。 c.树形结构：指该结构中的节点之间存在一对多的关系。 d.图形结构：指该结构中的节点存在多对多的关系。 3.存储结构：存储结构是逻辑结构用计算机语言表示或在计算机中的实现，也就是逻辑结 构在计算机中的存储。 a.顺序存储结构：该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元 里，节点之间的逻辑关系由存储单元的邻接关系来体现。 b.链式存储结构：节点间的逻辑关系是由附加的指针字段表示的。 c.索引存储结构：该结构通常是在存储节点信息的同时，还建立附加的索引表。 d.哈希表：根据节点的关键字通过哈希函数直接计算出一个值，并将这个值作为该 节点的存储地址。 4．算法：在具体存储结构中实现某个抽象的运算。 5．时间复杂度：执行算法所需要的计算工作量。 6．空间复杂度：执行算法所需要的内存空间。 7．线性表：具有相同特性的数据元素的一个有限序列。 8．线性表的顺序存储结构：把线性表中的所有元素按照逻辑顺序依次存储到从计算机存储器指定位置开始的一连续的存储空间中。 9．线性表的链式存储结构：每个存储节点不仅包含有元素本身的信息，而且包含元素之间逻辑关系的信息。 10．有序表：指其中所有元素以递增或递减方式有序排列的线性表。 11．栈：栈是一种只能在一端进行插入或删除操作的线性表。（采用顺序存储结构的栈称为顺序栈；采用链式存储结构的栈称为链式栈） 12．队列：队列是一种仅表的一端进行插入，而在表的另一点进行删除的线性表。（把存储队列元素的表从逻辑上看成一个环，环形队列） 13．串：由零个或多个字符组成的有限序列。 14．串的模式匹配：在主串中找到一个与子串相等的子串。 15．递归：在定义一个过程或函数时出现调用本过程或本函数的成分称为递归。 16．数组：数组是具有相同类型的数据元素的有限序列。 17．广义表：一个广义表是n(n>=0)个元素的一个序列。 18．树：树是由n(n>=0)个节点组成的有限集合。 a．表示方法：树形表示法；文氏图表示法；凹入表示法；括号表示法。 b.存储方法：双亲存储结构；孩子链存储结构；孩子兄弟链存储结构。 19．二叉树：它是有限的节点集合。 20．平衡二叉树：若一颗二叉树中每个节点的左右子树的高度至多相差1，称为平衡二叉树。21．哈夫曼树：在n个带权叶子节点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树。 22．图：由顶点和边构成。 存储方法：邻接矩阵存储法（特点：1>图的邻接矩阵表示唯一； 2>适用于存储边的数目较多的稠密图，存储空间为O（n2）; 安徽理工大学 数据结构 课程设计说明书题目: 一元多项式计算 院系：计算机科学与工程学院 专业班级：数字媒体13-1班 学号： 2013303102 学生姓名：钱福琛 指导教师：梁兴柱 2015年 1月 9 日 安徽理工大学课程设计（论文）任务书计算机科学与工程学院 2014年 11 月 10 日安徽理工大学课程设计（论文）成绩评定表 目录 1 问题描述 2 功能描述 2.1 课题要求........................................... 2.2 软件格式规定....................................... 3 设计 2 3.1 相关函数介绍说明................................... 3.2 主程序的流程基函数调用说明......................... 4 程序设计 4 4.1 多项式存储的实现................................... 4.2 加减乘除算法....................................... 4.2.1加法运算的实现............................... 4.2.2减法运算的实现............................... 4.2.3乘法运算的实现............................... 4.2.4除法运算的实现............................... 4.3 函数调用关系图..................................... 5 运行测试 计算机网络名词解释文件管理序列号：[K8UY-K9IO69-O6M243-OL889-F88688] 备考川大NET名词解释 1、计算机网络是利用通信设备和线路将地理位置不同的、功能独立的多个计算机系统互连起来，以功能完善的网总软件实现网络中资源共享和信息传递的系统。 2、联机系统是由一台中央计算机连接大量的地理位置分散的终端而构成的计算机系统。 3、PDN是公用数据网。网中传输的是数字化的数据，属于通信子网的一种。 4、OSI是开放系统互连参考模型。为ISO（国际标准化组织）制订的七层网络模型。 5、PSE是分组交换设备。作为网络的中间节点，它具有存储转发分组的功能。 6、PAD是分组装配/拆卸设备。在发送方将大的报文拆成若干分组，在接受方将属于同一报文的分组再重新组成报文的设备。 7、FEP是前端处理机。设置在中心计算机与通信线路之间，专门负责通信控制。 8、IMP是接口信息处理机，是网络中间节点的统称。 二、 1、数据通信：是一种通过计算机或其他数据装置与通信线路，完成数据编码信号的传输、转接、存储和处理的通信技术。 2、数据传输率：每秒能传输的二进制信息位数，单位为B/S。 3、信道容量：是信息传输数据能力的极限，是信息的最大数据传输速率。 4、自同步法：是指接收方能从数据信号波形中提取同步信号的方法。 5、PCM：称脉码调制，是将模拟数据换成数字信号编码的最常用方法。 6、FDM：又称时分多路复用技术，是在信道带宽超过原始信号所需带宽情况下，将物理停产的总带宽分成若干个与传输单个信号带宽相同的子停产，每个子信息 传输一路信号。 7、同步传输：是以一批字符为传输单位，仅在开始和结尾加同步标志，字符间和比特间均要求同步。 8、差错控制：是指在数据通信过程中能发现或纠正差错，把差错限制在尽可能小的允许范围内的技术和方法。 9、FEC：又叫向前纠错，是一种差错控制方法，接收端不但能发现错误，而且能确定二进制码元发生错误的位置，从而加以纠正。 10、信号：是数据的电子或电磁编码。 11、MODEM：又称调制解调器。其作用是完成数字数据和模拟信号之间的转换，使传输模拟信号的媒体能传输数字数据。发送端MODEM将数字数据调制转换为模拟信号，接收端MODEM再把模拟信号解调还原为原来的数字数据。 12、信号传输速率：也称码元率、调制速率或波特率，表示单位时间内通过信道传输的码元个数，单位记做BAND。 13、基带传输：是在线路中直接传送数字信号的电脉冲，是一种最简单的传输方式，适用于近距离通信的局域网。 14、串行通信：数据是逐位地在一条通信线上传输的，较之并行通信速度慢，传输距离远。 15、信宿：通信过程中接收和处理信息的设备或计算机。 16、信源：通信过程中产生和发送信息的设备或计算机。 17、全双工：允许数据同时在两个方向上传输，要有两条数据通道，发送端和接收端都要有独立的接收和发送能力。 18、冲击噪声：呈突发状，常由外界因素引起；其噪声幅度可能相当大，无法靠提高信噪比来避免，是传输中的主要差错。 第一章名词解释 这是书本上的课后习题上的： 1-26 试解释以下名词：协议栈、实体、对等层、协议数据单元、服务访问点、客户、 服务器、客户-服务器方式。 答：实体(entity) 表示任何可发送或接收信息的硬件或软件进程。 协议是控制两个对等实体进行通信的规则的集合。 客户(client)和服务器(server)都是指通信中所涉及的两个应用进程。客户是 服务的请求方，服务器是服务的提供方。 客户服务器方式所描述的是进程之间服务和被服务的关系。 协议栈:指计算机网络体系结构采用分层模型后,每层的主要功能由对等层协议 的运行来实现,因而每层可用一些主要协议来表征,几个层次画在一起很像一个栈的结构 对等层:在网络体系结构中,通信双方实现同样功能的层. 协议数据单元:对等层实体进行信息交换的数据单位. 服务访问点:在同一系统中相邻两层的实体进行交互（即交换信息）的地方.服务访问点SAP是一个抽象的概念,它实体上就是一个逻辑接口. 2-04 试解释以下名词：数据，信号，模拟数据，模拟信号，基带信号，带通信号，数 字数据，数字信号，码元，单工通信，半双工通信，全双工通信，串行传输，并行传输。 答：数据：是运送信息的实体。 信号：则是数据的电气的或电磁的表现。 模拟数据：运送信息的模拟信号。 模拟信号：连续变化的信号。 数字信号：取值为有限的几个离散值的信号。 数字数据：取值为不连续数值的数据。 码元(code)：在使用时间域（或简称为时域）的波形表示数字信号时，代表不同离散数值的基本波形。 单工通信：即只有一个方向的通信而没有反方向的交互。 半双工通信：即通信和双方都可以发送信息，但不能双方同时发送（当然也不能同时接收）。这种通信方式是一方发送另一方接收，过一段时间再反过来。 全双工通信：即通信的双方可以同时发送和接收信息。 基带信号（即基本频带信号）——来自信源的信号。像计算机输出的代表各种文字或图像文件的数据信号都属于基带信号。 带通信号——把基带信号经过载波调制后，把信号的频率范围搬移到较高的频段以便在信道中传输（即仅在一段频率范围内能够通过信道）。 车厢调度问题 摘要:实现栈的基本操作,即实现类型。程序对栈的任何存取，即更改，读取和状态判别等操作，必须借助于基本操作。在操作过程中的任何状态下都有两种可能的操作：“入”“出”。每个状态下处理问题的方法都是相同的，具有递归特性。关键字:栈递归打印 0.引言 《数据结构》是计算机科学与技术、软件工程及相关学科的专业基础课，也是软件设计的技术基础。《数据结构》课程的教学要求之一是训练学生进行复杂的程序设计的技能和培养良好程序设计的风格，其重要程度决不亚于理论知识的传授，因此课程设计环节是一个至关重要的环节，是训练学生从事工程科技的基本能力，是培养创新意识和创新能力的极为重要的环节。基本要求如下： (1) 熟练掌握基本的数据结构； (2) 熟练掌握各种算法； (3) 运用高级语言编写质量高、风格好的应用程序。 1.需求分析 (1)这个实验要求我用栈实现车厢调度. (2)车厢的个数是由用户输入的. (3)程序会自动给车厢进行从1到 n的编号. (4)用户输入车厢个数后,程序打印出所有可能的车厢出站顺序. 2.数据结构设计 在这个程序中存储结构是栈,对于栈的声明和定义如下: typedef struct SqStack { int *top; /*栈顶指针*/ int *base;/*在栈构造之前和销毁之后.base的值为NULL*/ int stacksize; /*当前分配的存储空间*/ }SqStack; /*顺序栈的结构体声明和定义*/ 3.算法设计 3.1 对算法的简单描述 这个实验中, 要求用到栈. 实现栈的基本操作,即实现类型。程序对栈的任何存取（即更改，读取和状态判别等操作）必须借助于基本操作。在操作过程中的任何状态下都有两种可能的操作：“入”“出”。每个状态下处理问题的方法都是相同的，具有递归特性。栈实现是方便的 无论如何调度，我们的操作都是入栈和出栈，设定入栈为1，出栈为-1，对n列车厢有2n次这样的操作，例如n=4，则有操作1111-1-1-1-1、1-11-11-11-1等.所以还要构造一个操作命令队列trainlist[]。 在算法中还要用到递归算法,其本质为: 一个数的进栈以后有两种处理方式：要么立刻出栈，或者下一个数的进栈。 一个数的出栈以后也有两种处理方式：要么继续出栈（栈不为空），或者下一个数的入栈。 3.2栈的基本操作 3.2.1构造一个栈 void InitStack2(SqStack *S,int base_size) { S->base=(int *)malloc(base_size * sizeof(int)); if(!S->base) { puts("ERROR!"); return ; } S->top=S->base; S->stacksize=base_size; }/*构造一个空栈*/ 3.2.2 插入新的栈顶元素 数据 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据项 是数据结构中讨论的最小单位，是数据记录中最基本的、不可分的数据单位。 数据元素 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象 是性质相同的数据元素的集合，是数据的一个子集。 数据处理 是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。 数据结构 是指互相之间存在一种或多种特定关系的数据元素的集合。（包括逻辑结构、存储结构和数据运算） I.逻辑结构：线性结构、非线性结构。 II.物理结构：又称为存储结构，是数据的逻辑结构在计算机中的表示（映像），包括顺序存储方法、链式存储方法、索引存储方法、散列存储方法。 数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型 是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。 算法 解决一个问题的方法和步骤。算法的特性：有穷性、确定性、输入、输出、可行性。算法设计的目的：正确性、可读性、健壮性、高效率与低存储量需求。 时间复杂度 T(n)＝ O(F(n))，它表示随问题规模Ｎ增大，算法执行时间增长率与F(n)的增长率相同．F(n)算法的时间复杂性。原地工作 算法执行时，若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 线性表 具有相同特性数据元素的一个有限序列。是N(N>=0)个同质元素的有限序列，除首尾元素外，每个元素有唯一的前驱和唯一的后继。 顺序表 把线性表中的所有元素按照其逻辑顺序，依次存储到指定的存储位置开始的一块连续的存储空间中。 单链表 每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接后继结点的地址（指针），称为指针域，元素的存储空间可以连续，也可以是不连续的。而数据元素之间的逻辑关系由指针域来确定。 双向链表 线性表采用链式存储时，每个结点除一个数据域外，包含两个指针域，一个指向该结点的直接后继，一个指向该结点的直接前驱，这种方式构成的链表，即为双向链表。 单循环链表 是单链表的另一种形式，它是一个首尾相接的链表，表中最后一个结点的指针域由NULL改为指向头结点或线性表的第一个结点，整个链表形成了一个环． 栈 一种只能在一端进行插入或删除操作的线性表。 队列 是一种受限线性表，其限制为允许在表的一端进行插入，而在表的另一端进行删除。（进行插入的一端称为队尾，进行删除的一端称为队头），先进先出的特点（FIFO） 循环队列 数据结构课题报告说明书 数据结构课题报告 指导教师：喝安全 组长：肖清泉 组员：朱智红、苏彦洲 班级：计算机科学与技术（正大） 专业：计算机科学与技术（帅范） 时间：2015-01-20 ——2015-03-01 课程设计题目：图书管理系统 、八 前 图书馆管理系统或许众所周知，任何一个学校，有关单位似乎都需要这个类似的系统以此管理图书与读者借阅情况。借此，我们合作也做出一个系统，尽管可能有些逊色，但感觉还是可以本系统总结了前人牛人的经验，剔除了其中的不足创造了自己独有的特色。传承了牛人的优点，经过我们仔细的观摩，思考后创造此系统。“书上得来终觉浅，要知此事需躬行。”是呀！在没亲身动手去编写程序时，我总觉得我会了。书本上的我都懂了。可我真的懂 了吗？答案是否定的。在编写过程中，会出现很多的问题，而这些问题你是在书本上是接触不到的。只有发现问题，解决问题，你才会有提高。在过去人们对信息管理的主要方式是基于文本、表格等纸质的手工处理之上的，而用手工进行图书借阅管理存在多种弊端，其中包括图书过于繁多，包含很多的信息数据的管理对于图书借阅情况如：借阅天数、超过限定借阅时间等等的统计和核实，往往采用对借阅卡的人工查询进行，对借阅天数等用人工计算、手抄进行。信息处理工作量大，容易出错；由于数据繁多，容易丢失，且不易查找。总的来说缺乏系统、规范的管理手段人们操控起来是很困难的；因此，使用电子化的管理手段将是大势所趋，建立一个图书管理系统也是图书管理部门提高工作效益的有效手段。系统能够合理高效地利用图书资源，使得图书借阅更加的科学合理。 第一章需求分析与目的概述 --------- 04 1.1 需求分析概述---------------- 一04 1.2 系统功冃匕分析------------- 一04 第二章系统设计---------- ---04 3.1 系统功能模块设计------------ ——04 3.1.1 信息录入--------------- 05 3.1.2 学生菜单-------------- 05 3.1.3 老师菜单-------------- 06 3.1.4 图书管理员菜单------------- 07 《数据结构》第二次单元测试 姓名学号. 分数. 一、单项选择题（每小题2分，共26分） 1. 数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2. 数据在计算机存储器内表示时， 物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C. 链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 J ( )。插入和删除元素 D.没 B. 头、尾 D.头、尾指栈 C. 线性表 k层的结点数最多为B.2K+1 C.2K-1 二、填空题（每空2分，共32分） 1. 一维数组的逻辑结构是__线性____，存储结构是____顺序存储____；对于二维或多维数组，分为____顺序____和_____链式______两种不同的存储方式。 2.栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，进行操作的这一端称为栈顶，与其对应的另一端称为栈底。 3. 在树型结构中，树根结点没有_____后继_____结点，其余每个结点的有且只有___1__个前趋驱结点；叶子结点没有_____子____结点；其余每个结点的后续结点可以____有多个结点______。 4. 线性结构中元素之间存在___一对一____关系；树型结构中元素之间存在__一对多_______关系。 5. 一棵深度为k的满二叉树的结点总数为__ (2^h)-1 ___，一棵深度为k的完全二叉树的结点总数的最小值为__(2^h)-1__，最大值为__(2^h)-1_。 6. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEFG，则该二叉树的 前序遍历序列为_ABDECFG___。 三、判断题（每题1分，共8分） 1. 数组可看作基本线性表的一种推广， 因此与线性表一样，可以对它进行插入、删 除等操作。（） 2. 对于不同的特殊矩阵应该采用不同的存 储方式。（） 3. 采用压缩存储之后，下三角矩阵的存 储空间可以节约一半。（） 4. 在一般情况下，采用压缩存储之后， 对称矩阵是所有特殊矩阵中存储空间节约 最多的。（） 5. 距阵中的数据元素可以是不同的数 据类型。（） 6. 矩阵中的行列数往往是不相等的。 （） 7．线性表的顺序存储结构比链式存 储结构更好。（） 页脚内容3 合肥学院 计算机科学与技术系 课程设计报告 2017～2018学年第二学期 课程数据结构与算法 课程设计名称文本文件单词的检索与计数 学生姓名陈映而 学号1604092001 专业班级16软件工程（1）班 指导教师孙斐 文本文件单词的检索与计数 一、问题分析和任务定义 要求编程建立一个文本文件，每个单词不包含空格且不跨行，单词由字符序列构成且区分大小写； 统计给定单词在文本文件中出现的总次数； 检索输出某个单词出现在文本中的行号、在该行中出现的次数以及位置。 （1）建立文本文件 （2）给定单词的计数 （3）检索单词出现在文本文件中的行号、次数及其位置 （4）主控菜单程序的结构 二、数据结构的选择和概要设计 数据结构：1.所有存储形式都用顺序存储 2.用矩阵检索单词出现的位置和次数 概要设计：该设计要求可分为三个部分实现： 1.对文件的操作，其中包括文本文档的建立，文件名由用户用键盘输入；以及读取文本文档内容并显示在屏幕上； 2.给定单词的计数，输入一个不含空格的单词，统计输出该单词在文本中的出现次数； 3.检索给定单词，输入一个单词，检索并输出该单词所在的行号、该行中出现的次数以及在该行中的相应位置。 图2-1 课题目录 图2-2 流程图 图2-3 函数关系 三、详细设计和编码 1.头文件包含： #include 本章主要介绍了如下一些基本概念： ?数据结构：数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 ?数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。 ?结点：结点也叫数据元素，它是组成数据的基本单位。 ?逻辑结构：结点和结点之间的逻辑关系称为数据的逻辑结构。 ?存储结构：数据在计算机中的存储表示称为数据的存储结构。 ?数据处理：数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。 ?数据类型：数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。 本章主要介绍了如下一些基本概念： 线性表：一个线性表是n≥0个数据元素a0，a1，a2，…，an-1的有限序列。 线性表的顺序存储结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。 线性表的链式存储结构：线性表的链式存储结构就是用一组任意的存储单元——结点（可以是不连续的）存储线性表的数据元素。表中每一个数据元素，都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。 循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结 循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结点。 双向链表：双向链表中，在每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。 除上述基本概念以外，学生还应该了解：线性表的基本操作（初始化、插入、删除、存取、复制、合并）、顺序存储结构的表示、线性表的链式存储结构的表示、一元多项式Pn(x)，掌握顺序存储结构（初始化、插入操作、删除操作）、单链表（单链表的初始化、单链表的插入、单链表的删除）。 本章主要介绍了如下一些基本概念： 栈：是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。因此，栈也被称为“后进先出”的线性表。 栈的顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的各个数据元素，称为栈的顺序存储结构。 双向栈：使两个栈共享一维数组stack[MAXNUM]，利用栈的“栈底位置不变，栈顶位置动态变化”的特性，将两个栈底分别设为-1和MAXNUM，而它们的栈顶都往中间方向延伸的栈称为双向栈。 数据结构习题 一、名词解释 1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、 算法、时间复杂度、空间复杂度。 2. 线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头 指针、头结点、首元结点（第1个元素结点）。 3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。 4. 树、叶子结点、结点的度、树的度、树的高（深）度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL哈夫曼编码。 5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、 （最小）生成树、邻接矩阵、邻接表、DFS BFSO 6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。 7. 排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2 路归并。 一、填空题 1. 数据结构是研究数据的 _逻辑结构_和—物理结构_ ,并在这种结构上定义相关的运算，设计实 现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为—时间复杂度和空间复杂度—。 2. 数据的基本单位是数据元素，数据的最小单位是数据项。 3. 算法是对特定问题求解—步骤___的一种描述，是指令的有限序列。 4. 一个算法的时间复杂度为（3n3+2n — 7）,其数量级表示为_0 （ n3） __。 5. 一个算法具有5个特性：_确定性、—可行性_、_有穷性_、输入和输出。 6. 算法性能的分析和度量，可以从算法的时间复杂度一和—空间复杂度—来评价算法的优劣。 7. 数据的逻辑结构包括集合结构、_线性结构 _、—树形结构_和_图型结构—四种类型。 8. 数据结构在计算机中的表示称为数据的物理结构，它可以采用 _顺序存储_ 或_链式存储_ 两种存储方法。 9. 线性表有两种存储结构，分别为_顺序存储 _ 和___________ 链式存储_。 10. 链式存储的特点是利用指针—来表示数据元素之间的逻辑关系。 11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用链式存储—存储结构。 12. 线性表中的数据元素之间具有 _一对一_的线性关系，除第一个和最后一个元素外，其他数据元素有且只有 一个_直接后继和直接前趋。 13. 在一个单链表中 P所指结点之后插入一个S所指结点时，应执行 s->next=_ p->next ___________ 和 p->next=_ S ________ 的操作。 数据是描述客观事物的符号,是能够被计算机输入,识别,处理的各种符号,是计算机化的信息。 2.数据项 数据不可分割的最小单位,一个元素由若干个数据项构成。 3.数据元素 它是组成数据的基本单位,是数据集合中的个体,在计算机程序中,通常作为一个整体进行考虑和处理。 4.数据对象 是性质相同的数据元素的集合,是数据的一个子集。 5.数据处理 是指对数据进行查找,插入,删除,合并,排序,统计以及简单计算等的操作过程。 6.数据结构 是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示(即数据的逻辑结构和物理结构),并对这种结构定义相适应的运算,设计出相应的算法,且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 7.数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 8.抽象数据类型 是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。 ９.算法 解决一个问题的方法和步骤。 10.时间复杂度 T(N)＝O(F(N)),它表示随问题规模Ｎ增大,算法执行时间增长率与F(N)的增长率相同,F(N)算法的时间复杂性。 11.原地工作 算法执行时,若额外空间相对于输入数据量来说是常数,则称此算法为原地工作。 12.线性表 一种数据结构,是N(N>=0)个同质元素的有限序列,除首尾元素外,每个元素有唯一的前驱和唯一的后继。 13.队列 是一种受限线性表,是先进先出的线性表 14.循环队列 在队列的顺序存储结构中,把存储空间的首尾逻辑上相连,构成一个环,使得存储空间上只要有空余的地址,就可以继续进行入队列操作,极大利用了物理空间。用头部和尾部两个指示器表示队列头和队列尾,插入在尾部进行,删除在头部进行。 15.单链表 每一个数据元素,都需用两部分来存储：一部分用于存放数据元素值,称为数据域；另一部分用于存放直接后继结点的地址(指针),称为指针域,元素的存储空间可以连续,也可以是不连续的。而数据元素之间的逻辑关系由指针域来确定。 16.双向链表 线性表采用链式存储时,每个结点除一个数据域外,包含两个指针域,一个指向该结点的直接后继,一个指向该结点的直接前驱,这种方式构成的链表,即为双向链表。 17.希尔排序 是插入排序的一种,又叫缩小增量排序,先按增量进行分组,组内插入排序,然后每次缩短增量,再进行分组和组内插入排序, 直到增量为1时,进行最后一次排序止。 18.完全图 任何一个有N个结点的无向图,若其边数为N(N-1)/2,则这个无向图就是完全图课程方案任务书(数据结构)信管
数据结构概念名词解释大全复习课程
数据结构名词解释整理
数据结构课程设计报告范本
数据结构名词解释整理
数据结构课程设计说明书讲解
计算机网络名词解释
计算机网络名词解释、简答题目汇总
数据结构课程设计说明书
数据结构名词解释
数据结构程序设计说明文档
《数据结构》考试及答案
数据结构课程设计-文本文件单词检索和计数
数据结构中的名词解释
数据结构复习题及答案
数据结构名词解释
相关主题
文本预览