数据结构
2025-04-16 18:34:55 1 举报AI智能生成
天津滨海职业技术学院武清校区 人工智能 沐雨
作者其他创作
大纲/内容
栈和对列
栈的定义及其运算
栈: 只允许在表的一端进行插入和删除的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)进栈（插入）: 将一个数据元素存放在栈顶出栈（删除）：将栈顶元素取出并删除特点:后进先出(LIFO )
栈的顺序储存结构
利用一批地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设一个栈顶指针top 指向栈顶元素在顺序栈中的位置
栈的链式储存结构
链栈采用带表头结点的单链表结构，将尾结点定为栈底，首元结点定为栈顶链栈由它的栈顶指针top唯一确定插入与删除仅在栈顶处执行链栈无栈满问题，空间可扩充适合于多栈操作
队列的定义及运算
队列：只允许在表的一端进行插入，在另一端进行删除的，操作受限制的线性表允许插入的一端称之为队尾(rear)允许删除的一端称之为队头(front)入队（插入）: 将一个数据元素存放在队尾出队（删除）：将队头元素取出并删除特点:先进先出(FIFO)
队列的顺序储存结构
顺序存储结构定义typedef struct { ElemType elem[MAXSIZE]; int front,rear; /*队头、队尾指针*/ }SqQueue;
队列的链式储存结构
链式队列用带表头结点单链表表示，简称链队列一个链队列用两个指针分别指示队头和队尾，队头指针front在链表链头，队尾指针rear在链表链尾链队列在入队时无队满问题，但有队空问题 队空条件为:front == rear
排序
排序的基本概念
排序(sorting)：把一批任意序列的数据元素（或记录），重新排列成一个按关键字有序的序列。
插入排序
插入排序的基本方法是：每步将一个待排序的记录，按其关键字大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。
交换排序
交换排序的基本思想是两两比较待排序记录的关键字，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之，直到所有记录都排好序为止。
选择排序
选择排序的基本思想是：每一趟 (例如第 i 趟，i = 1, …, n-1) 在后面 n-i 个待排序记录中选出关键字最小的记录, 作为有序记录序列的第 i 个记录。待到第 n-1 趟作完，待排序记录只剩下1个，就不用再选了。
归并排序
归并:将两个或两个以上的有序表合并成一个新的有序表。
基数排序
基数排序是采用“分配”与“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。
内部排序总结
线性表和数组
线性表
定义：n（ 0）个数据元素组成的有限序列
线性表的顺序存储
储存方式：用内存中一批地址连续的存储单元依次存储线性表中的数据元素
数组
基本概念：数组是一种常用的数据结构，几乎所有高级语言都提供数组类型。
线性表的链式存储
线性表的顺序存储结构的不足之处 ●插入和删除操作时需移动大量信息，效率较低； ●不易扩充； ●内存空间不能充分利用。
树和二叉树
树的基本概念
树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。在数据结构中，树是一种抽象的数据类型，数据的顶部节点是树的入口节点，也被称为根节点
二叉树
二叉树是n(n≥0)个结点的有限集，它可以为空集(n=0)或由一个根结点及两棵互不相交的左子树和右子树组成 。
满二叉树定义：一棵深度为k有且仅有2K-1个结点的二叉树。
完全二叉树定义：允许最下一层上的结点都集中在该层最 左边的若干位置上，右侧可以缺少结点的二叉树
遍历二叉树
遍历二叉树 以某种次序访问二叉树中的每个结点，且每个结点仅被访问一次访问 如查询结点数据域的内容、输出结点的数据、修改结点的数据或是执行对结点的其他操作
线索二叉树
遍历二叉树实质上是对一个非线性结构的线性化操作，得到一个线性序列在线性序列中，每个结点（除第一个和最后一个外）仅有一个前驱和一个后继，因此，有时为了操作方便，需要知道树中结点按某次序遍历时的前趋和后继结点，但它们是在遍历的动态过程中得到的建立线索二叉树保存结点的前趋和后继信息
线索二叉树的基本概念：假设二叉链表有n 个结点，则有2n个指针域,其中 空指针域 = 2n-(n-1) = (n+1) 个利用这些空闲的指针域：当某结点无左孩子时，令其lchild 域指向其前趋结点当该结点无右孩子时，令其rchild 域指向其后继结点为区分结点的指针域究竟指向孩子结点还是指向前趋或后继结点，需在原结点结构中增加两个标志域
树和森林
对于一般树，树中孩子的次序并不重要，只要双亲与孩子的关系正确即可。但在二叉树中，左、右孩子的次序是严格区分的。所以在讨论二叉树与一般树之间的转换时，为不引起混淆，就约定按树上现有结点次序进行转换。
哈夫曼树及其应用
哈夫曼树的基本概念：路径长度 两个结点之间的路径长度是连接两结点的路径上的分支数树的路径长度 根结点到各结点的路径长度之和
0 条评论
下一页
