华中科技大学公开课-笔记01day

## 课程链接

http://open.163.com/newview/movie/free?pid=MEKB56M73&mid=MEKB5PVMF

## 知识提纲：

## 什么是数据结构

模型抽象

建立算法

解决算法

## 相关概念和术语

数据：

数据元素：数据基本单位

数据项：数据不可分割最小单位

数据对象：性质相同/类型相同的数据元素的集合

数据结构：相互之间有一种多种特定关系的数据元素的集合

四类基本结构：集合、线性结构、树形结构、图状结构

逻辑结构：线性结构-线性表、栈、队列、数组、广义表、字符串

非线性接口-树二叉树、图

数据的存储结构：

数据类型：

抽象数据类型：

## 算法的相关特性

算法的五个特性：有穷性、确定性、可行性、输入、输出

算法的设计要求：正确性、可读性、健壮性、高效和低存储

## 算法分析相关概念

算法时间复杂度：O(1)<O(log~2~n)<O(n)<O(nlog~2~n)<O(n^2^)<O(n^3^)<O(2^n^)

## 线性表的相关概念

视频错误

## 线性表顺序表示

## 线性表的插入删除

插入新元素后，新元素后面的向后移动。

移动元素的期望是n/2

删除元素的移动次数期望值是(n-1)/2

## 顺序存储结构的评价

优点：

是一种随机存取结构，存取任何元素的时间是一个常数，速度快

结构简单，逻辑上相邻的元素物理上也相邻

不需要使用指针，节省存储空间

缺点：

插入和删除要移动大量元素，消耗大量时间。

需要连续的存储空间

插入元素可能溢出

自由区中的存储空间不能被其他数据占用，存在浪费空间问题

## 单链表

不带表头单链表：

带表头单链表：