数据结构与算法(一)基础

数据结构是一门研究非数值计算程序设计问题中,计算机的操作对象以及他们之间的关系和操作的学科

数据是用来描述现实世界的数字字符图像声音以及能够输入到计算机中并能被计算机识别的符号的集合

数据结构三方面内容:

(1)数据的逻辑结构指数据元素之间固有的逻辑关系

(2)数据的存储结构指数据元素及其关系在计算机内的表示

( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除,更新,查询,排序等

一.数据结构基础概念

逻辑结构包括:

(1)线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继。
(2)非线性结构,一个结点可能有多个直接前趋和后继。:集合,树形结构、图形结构

存储结构包括:

1)顺序存储,逻辑相邻的结点存储在物理上相邻的存储单元内。逻辑顺序与存储顺序一致
2)链接存储,结点间的逻辑关系由附加指针字段表示,1.逻辑顺序与存储顺序不一致2.每个节点存取的费时不同
3)索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引。
4)散列存储,按结点的关键字直接计算出存储地址。

(操作)算法时间复杂度

是该算法的时间耗费,是求解问题规模n的函数。记为O(n)。
时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

评价算法的标准:正确性,高效性,健壮性(容错),可读性。

抽象数据类型的形式描述为:

ADT = ( D,S,P )

  其中:D 是数据对象,

S 是 D 上的关系集,

P 是 D 的基本操作集。

ADT 抽象数据类型名 {

 数据对象: 数据对象的定义

 数据关系: 数据关系的定义

 基本操作: 基本操作的定义

} ADT 抽象数据类型名

二.各类数据结构特点(算法时间复杂度)

    索引 插入 删除 查询 排序
  静态数组 O(1) O(1)  
  动态数组 O(1) O(n) O(n) O(n)  
  单链表 O(n) O(1) O(1) O(n)  
  双链表 O(n) O(1) O(1) O(n)  
  二叉排序树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  红黑树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  B树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  笛卡尔树 O(log(n)) O(log(n)) O(log(n))  
  哈希表 O(1) O(1) O(1)  
             
             
             
排序:

image

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>