首页天道酬勤数据结构c语言版知识总结,数据结构c++知识点

数据结构c语言版知识总结,数据结构c++知识点

admin 08-12 09:50 221次浏览

数据(DATA)是描述客观事物的数字、字符以及所有能输入计算机并能被计算机接受的各种符号集合的统称。

数据结构(data structure):数据元素之间存在的关系,由n(n >= 0)个数据元素组成的有限集合,数据元素之间具有某种特定的元素。

数据的逻辑结构:线性结构、树结构、图

数据的存储结构:顺序存储、链式存储

对数据进行操作:初始化、判断是否是空、存取、统计个数、遍历、插入、删除、查找、排序 ————用算法进行描述。

数据类型和抽象数据类型。

算法:有穷规则的集合,其规则确定一个解决某一特定类型问题的操作序列。算法设计依赖数据的逻辑结构,实现依赖数据的存储结构。算法分析的两个方面:时间代价、空间代价。

线性表的顺序存储(顺序表)和链式存储(链表)

一、顺序表(SeqList)使用一维数组一次存放书元素。一维数组占用一块内存空间,每个存储单元的地址是连续的,通过下标识别元素,它的下标就代表了他的存储单元序号,也就表示了它的位置。

查找顺序表中的元素是方便的,根据下标就可以取出要取的元素。

当顺序表的容量不够时,顺序表不能就地扩容,要申请另一个更大容量的数组进行数组元素复制。

对于插入、删除元素:先根据下标找到相应位置,若插入元素,将新插入插入位置后,将被加入位置的旧元素及之后的元素向后移动,移动次序是由后向前。若删除元素,将要删除的元素删除,其后的元素向前移动。插入和删除的操作时间主要用于移动元素。

二、线性表的链式存储结构(链表LinkedList)是用若干地址分散的存储单元存储数据元素,逻辑上相邻的数据元素在物理位置上不一定相邻。存储一个数据元素的存储单元成为结点Node,单链表的表示方式:结点(数据域,地址域)。

对于单链表的操作:遍历操作是从第0个结点开始,沿着结点的Next链,依次访问单链表中的每个结点,并且每个节点只访问一次。插入(删除)操作:根据要插入(删除)的结点数,从第0个结点遍历找到要插入(删除)的位置,将要插入的数据元素插入(将要删除的元素删除),改变原来结点间的链接关系,不用移动数据元素。而操作所花的时间都在查找上面。

三、特殊的线性表(栈和队列)

(一)特殊之处在于插入和删除操作的位置受到限制:

若插入和删除的操作只允许在线性表的一端进行,则为栈(stack),特点是先进后出;

若插入和删除操作分别在线性表的两端进行,则为队列(queue),特点是先进先出。

(ps. 栈和线性表是不同的抽象数据类型,栈的概念不依赖于线性表而存在。)

(二)应用

栈是嵌套调用机制的实现基础:由于函数返回次序与调用次序正好相反,借助栈来实现记忆函数的路径,就能获得函数返回的路径,当函数被调用时,操作系统将该函数的有关信息(地址、参数、局部变量值等)入栈,称为保护现场;一个函数执行完返回时,出栈,获得调用函数信息,称为恢复现场,程序返回调用函数继续运行。

使用栈以非递归方式实现递归算法(存在直接或间接调用自身的算法称为递归算法);

队列用于处理排队等待问题。(优先队列)

树和二叉树

完全二叉树(满二叉树)

Huffman树:带权外路径长度最小的二叉树,也成最优二叉树;Huffman编码是数据压缩技术中一种无损压缩编码。

树的遍历规则主要有两种:先根次序遍历和后根次序遍历。

树的存储结构:一棵树包含个结点间的层次关系与兄弟关系,两种关系的存储结构不同;树的层次关系,必须采用链式存储结构存储,通过链连接父母结点和孩子结点;一个结点的多个孩子结点(互称兄弟)之间是线性关系,可以采用顺序存储结构或链式存储结构存储。

B树:存储效率高,查询效率低——数据库索引

矩阵和规划

排序

插入排序:每次将一个元素,按其关键字值的大小插入到它前面已排序的子序列中,依次重复,直到插入全部元素。

直接插入排序:最好情况是N;最坏情况是N*N;空间复杂度是O(1);

二分法插入排序:在插入排序时采用顺序查找算法寻找位置。

希尔排序:缩小增量排序,即分组地直接插入排序。时间复杂度不容易计算,取决于增量的选择。

交换排序

冒泡排序:比较相邻的两个元素的大小,每次将数据序列中最大元素交换到最后。N*N;空间复杂度:O(1).

快速排序:在数据序列里选择一个元素作为基准值,每次从数据序列的两端开始交替进行,将小于基准值的元素交换到序列前端,将大于基准值的元素交换到序列后端,介于两者之间的位置则成为基准值的最终位置。同时,序列划分为两个子序列,再分别对两个子序列进行快速排序,直到子序列长度为1,则完成排序。最好情况:NN ;最坏情况是NN;快排是递归算法,会花费一定的时间和空间,使用栈保存参数,栈所占的空间和递归调用的次数有关,空间复杂度为O(N) ~ O(n).

直接选择排序:第一趟从n个元素的数据序列中选出关键字最大或最小的元素并放在最前或最后位置,下一趟再从n-1个参数中选出其中最大或最小的数放在相应位置,依次类推。 时间复杂度为O(n*n);空间复杂度为O(1).

堆排序:利用完全二叉树。将最大值或最小值移到根节点然后换下来,再找剩下的里面最大值或最小值。时间复杂度为O(n*N);堆排序的空间复杂度为O(1).

归并排序:将另个排序的子序列合并,形成一个排序数据序列。时间复杂度为O(n*N);空间复杂度为O(n).

(&如何在Clojure中将字符串附加到向量怎么用Java比较两个对象的大小解决IDEA和CMD中java命令提示错误: 找不到或无法加载主类的问题Android实现将一个Activity设置成窗口样式的方法
数据结构基础知识总结,数据结构教程知识点总结 数据结构考研简答题总结,数据结构考研重点章节
相关内容