考纲内容

  • 数据结构相关概念和术语
  • 数据结构三要素:逻辑结构、物理结构、数据运算
  • 算法时间复杂度与空间复杂度复杂度的分析与计算

可以用抽象数据类型定义一个完整的数据结构

基本概念和术语

1.1数据结构的基本概念

  • 数据
  • 数据元素
  • 数据对象
  • 数据类型

在C语言中整型,实型,字符型等基本数据,用户可以自定义类型数据,例如指针,结构体,数组。

  1. 抽象数据类型:抽取世纪问题的本质,在计算机中使用二进制数来表示数据,在高级语言中出现了数据类型,比如整型,实型。字符型,利用这些类型构造出线性表,栈,队列,树,图等复杂的抽象数据类型。

包括三部分:数据对象,数据对象关系的集合,以及数据对象的基本操作的集合

这就是写程序的过程

ASDT 抽象数据类型名{
数据对象:(数据对象的定义)
数据关系:(数据关系的定义)
基本操作:(基本操作的定义)
}

 

  • 数据结构

是相互之间存在一种或者多种特定关系数据元素的集合,数据元素非孤立存在,存的的关系称为结构,包括三方面内容,逻辑结构,存储结构和数据运算。数据的逻辑结构和存储结构密不可分,算法的设计取决于所选定的逻辑结构,实现算法依赖于采用的存储结构。

1.1.2数据结构三要素

  • 逻辑结构

线性结构一般是以表为主,而非线性是树,图之类,后面会细细道来。

绪论-你,与世界的距离

这也是在说明事物与事物之间的联系,有的人和你是同事是朋友,而有的人只是在相互合作,本质是数据对象之间的关系

数据的逻辑结构独立于存储结构

绪论-你,与世界的距离
  • 存储结构

数据结构在计算机中的表示(映像),也称为物理结构,包括元素的表示和关系的表示,数据的存储结构是用计算机语言实现的逻辑,依赖于计算机语言,数据的存储结构主要有顺序存储、链式存储、索引存储、散列存储。

1)顺序存储:把逻辑上相邻你的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的玲姐关系来实现,优点是随机存取,每个元素占用最少的存储空间,缺点是只能使用相邻的一整块存储单元,可能产生较多的外部碎片。

2)链式存储:不要求在逻辑上相邻,在物理上也相邻,借助指示元素存储地址的指针来表示元素之间的逻辑关系,有点是不会出现碎片现象,能和葱粉利用所有存储单元,驱动每个元素因指针而占用额外的存储空间且只能实现存取。

3)索引存储:在存储信息的同时,建立附加的索引表,索引表中的每项称为索引项,索引项的一般形式(关键词,地址)有待你是检索速度快,缺点是独家的索引表额外占用存储空间,另外增加或者删除数据也要修改索引表,会话费较多的时间。


  1. 对于两种不同的数据结构,逻辑结构和物理结构一定不相同吗?
  2. 举个例子。说明对相同的逻辑结构,同一种运算做不同的存储方式下实现时,其运算效率不同。