位置:首页  >   程序积累  > 数据结构以及常用数据结构的定义

数据结构以及常用数据结构的定义


数据:描述客观事物的符号,如文本、图片、视频
数据元素:组成数据的,有一定意义的基本单位
数据项:一个数据元素可以由若干个数据项组成
数据对象:性质相同的数据元素的组合
数据结构:数据结构是计算机用来组织和存储数据的方式。具体定义:数据结构是指相互之间存在着一种或者多种关系的数据元素的集合和该集合中数据元素的关系组成

数据结构:
逻辑结构 
1.线性结构 (线性表、栈、队、串、数组)
2.非线性结构  树结构和图结构
物理(存储)结构
1.顺序结构
2.链式结构
3.索引结构
4.散列结构
数据运算
1.插入运算
2.删除运算
3.修改运算
4.查找运算
5.排序运算

时间复杂度
1.一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数T(n)
注:如果一个循环次数n次的for语句,如果里面有3条赋值语句,那么总执行次数就是3n,所以这个函数T(n)就是循环次数,T(n)=3n,语句的执行次数(频度)*单位执行时间 就是总执行时间

2.从T(n)中找到同数量级(同阶)函数记作f(n),例如T(n)= 3n的同数量级的函数f(n)=n
注:如果T(n)=n^3+n^2+n,则 f(n)=n^3

3.这个时候我们能够计算出时间复杂度了 T(n)=O(f(n))
用T(n)/f(n),然后求极限值--------  (n^3+n^2+n)/n^3 = 1+1/n+1/n^2  ,求极限值 是一个常数,那么时间复杂度就是 O(f(n)),也就是O(n^3)

简单推导时间复杂度
1.用常数1取代执行时间中的所有加法常数
2.在修改后的执行次数函数中,只保留最高阶项
3.如果最高阶存在且不是1,则去掉他的系数
4.得到的结果就是大O阶
简单说就是 最高阶的执行次数


线性表的特点
定义:零个或多个数据元素的有限序列
除首尾外,均只有一个直接前驱和直接后继

一个数组元素可以有若干数据项组成
线性表有顺序存储和链式存储两种数据结构 
堆栈、队列、串、数组等都是线性表

单链表
head -> A -> B -> C -> D -> E
data-next 
节点包括 1、data数据域,存放节点的值 2、next指针域,存放节点的直接后继的地址
插入节点:头插/尾插,也叫前插和后插,其实就是head所指向节点不一样,当然他们的时间复杂度也不一样
删除节点:先找到要删除的节点位置,将父节点的next指向其子节点,然后删除该节点
查询节点:从head开始一级一级往下找
编辑节点:从head开始一级一级往下找,找到后编辑内容
节点排序:。


双链表
head <-> A <-> B <-> C <-> D <-> E
pre-data-next 
节点包括 1、data数据域,存放节点的值 2、pre指针域,存放节点的直接前驱的地址 3、next指针域,存放节点的直接后继的地址

队列QUEUE
队列是只允许在一端进行插入,则在另外一端进行删除的运算受限的线性表
1.允许删除的一端成为队头(Front)
2.允许插入的一端为队尾(Rear)
3.队列中没有元素成为空队列
4.队列亦称作先进先出的线性表,简称FIFO表

堆栈
先进后出



它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做树是是因为它看起来像一颗倒挂的树
特点
1.每个节点有零个或者多个子节点
2.没有父节点的节点成为根节点
3.每一个非根节点有且只有一个父节点
4.除了根节点外,每个子节点可以分为多个不相符的子树

无序树:树中任意节点的子节点之间没有顺序关系,这种树叫做无序树,也叫做自由树
有序数: 树中任意节点的子节点之间有顺序关系,成为有序树
二叉树:每个节点最多包含两个子树的树称为二叉树 完全二叉树:对于一颗二叉树,假设其深度d(d>1).除了第d层外,其他各层的节点,数目均已达最大值,且第d层所有节点从左向右连续的紧密排列,这样的二叉树称为完全二叉树
满二叉树:对于上述的完全二叉树,如果去掉其第d层的所有节点,那么剩下的部分就构成一个满二叉树(此时该满二叉树的深度为d-1)
霍夫曼树:带全路径最短的二叉树称为霍夫曼树或者最优二叉树



遍历二叉树
    A
  B    C
D E   F
  G H  I
1.先序遍历 ABCDEFGHI  首先访问根结点,然后遍历左子树,然后遍历右子树。简称 根-左-右
2.中序遍历 DBAGECHFI  首先遍历左子树,然后访问根节点,然后遍历右子树。简称 左-根- 右
3.后序遍历 DBGEHIFCA   首先遍历左子树,然后遍历右子树,最后访问根节点。简称 左-右-根

二叉排序数
二叉排序树又称二叉查找数,也成二叉搜索树,它或者是一颗空树;或者是具有下列性质的二叉树:
1.若左子树不空,则左子树上所有节点的值均小于它的根节点的值
2.若右子树不空,则右子树上所有节点的值均小于他的根节点的值
3.左、右子树也分别为二叉排序树



快速排序
通过一趟排序,将待排序部分记录分隔成独立的两部分,其中一部分记录的关键字均比另外一部分记录的关键值小,在分别对这两部分记录进行下一趟排序,以达到整个序列有序。
快速排序就是比较适合用递归来处理的。


简单选择排序
排序思想:设所排序序列的记录个数为n。i取1,2,。。。。n-1,从所有n-i+1个记录中找到排序码最小的记录,与第i个记录交换。执行n-1趟后完成了记录序列的排序。

直接插入排序
每次从无序表中取出第一个元素,把他插入到有序表的合适位置,使有序表依然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中;第二趟把第三个数据与前两个数从前向后扫描,第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后完成了整个排序过程。






文章属性
精彩评论