数据结构和算法1

1.数据结构

数据结构是指相互之间具有（存在）一定联系（关系）的数据元素的集合。元素之间的互相联系称为逻辑结构。数据元素的逻辑结构基本类型有四种：

集合：结构中的数据元素除了“同属于一个集合”外，没有其他关系。

线性结构：结构中的数据元素之间存在着一对一的关系

树型结构：结构中的数据元素之间存在着一对多的关系

图状结构或网状结构：机构中的数据元素之间存在着多对多的关系

2.数据结构的存储方式

数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。

元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构，即：顺序存储结构和链式存储结构。

顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素的逻辑结构（关系）。

链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针（pointer），用该指针来表示数据元素的逻辑结构（关系）。

3.逻辑结构和物理结构

逻辑结构 物理结构

线性表 线性存储结构

链式存储结构

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

树 线性存储结构

链式存储结构

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

图 复合存储结构

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

数据的逻辑结构

┌───────────┃──────────┐

线性结构 非线性结构

┏━━━━━━━━╋━━━━━━━━━┓┏━━━━━━━╋━━━━━━━━━┓

┃ 受限线性表 线性表推广 集合 树型结构 图状结构

┃ ┏╋┓ ┏╋┓ ┏━━╋━━┓ ┏━━╋━━┓

一般线性表 栈和队列 串 数组 广义表 一般树 二叉树 有向图 无向图

4.数据结构的运算

数据结构的主要运算包括：

1.建立一个（create）数据结构

2.消除（destroy）一个数据结构

3.从一个数据结构中删除（delete）一个数据元素

4.把一个数据元素插入（insert）到一个数据结构中

5.对一个数据结构进行访问（access）

6.对一个数据结构（中的数据元素）进行修改（modify）

7.对一个数据结构进行排序（sort）

8.对一个数据结构进行查找（search）

5.线性表（linear list）

是由n（n>=0）个类型相同的数据元素a1,a2....an组成的有限序列。记作（a1,a2,...,ai-1,ai,ai+1,...,an）这里的数据元素ai(1<=i<=n)只是一个抽象的符号，其具体含义在不同情况下可以不同，它既可以是原子类型，也可也是结构类型，但同一线表中的数据元素必须属于同一数据对象。此外，线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性

表（a1,a2,...,ai-1,ai,ai+1,...,an）.表中ai-1,领先于ai,称ai-1是ai的直接前驱，而称ai,是ai-1的直接后续。除了第一个元素a1外，每个元素ai有且仅有一个被称为直接前驱的结点ai-1, 除了最后一个元素an外，每个元素ai有且仅有一个被称为直接后继的结点ai+1.线性表中元素的个数n被定义为线性表的长度，n=0时被称为空表。线性表的特点可以概况如下：

同一性：线性表由同类数据元素组成，每个ai必须属于同一个数据对象

有穷性：线性表由有限个数据元素组成。表长度就是表中数据元素的个数

有序性：线性表中表中相邻的数据元素之间存在着序偶关系（ai,ai+1）

由此可以看出，线性表是一种最简单的数据结构，因为数据结构之间是由一前驱一后继的直观有序的关系确定；线性表又是一种最常见的数据结构，因为矩阵，数组，字符串：堆栈，队列等都符合线性条件。