Day61 数据结构（线性表、链表）

1. 数据结构

1.1 概念

数据结构是计算机存储、组织数据的方式。

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构 可以带来更高的运行或者存储效率。

1.2 名词解释

数据-程序的操作对象。用于描述客观事物。

数据是一个抽象的概念， 将其进行分类后得到程序设计语言中的类型。如:int , float , char等等。 数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中被计算机程序处理的符号的总称。

数据元素:组成数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据项:一个数据元素由若干数据项组成。 就像我们可以把一本书的信息做为一个数据元素，而数目信息中的每一项（如书名，作者名等）为一个数据项

数据对象-性质相同的数据元素的集合(比如:数组,链表).

 

//声明一个结构体类型
struct MyTeacher //-种数据类型
{
    char name[32];
    int id;
    int age;
    char addr[128];
}
int main
{
    struct MyTeacher tech01; //数据元素
    struct MyTeacher tArray[30]; //数据对象
    memset(&t1, 0, sizeof(tech01));
    strcpy(tech01.name，"大明");
    strcpy(tech01.addr, "西安");
    tech01.id = 1001;
    tech01.age = 20;
}

数据结构**是指相互之间存在一种或多种特定关系的数据元素的集合。数据元素都不是孤立存在的，而 是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间关系的不同 特性，分为4中基本结构：

（1）集合：结构中的数据元素之间除了"同属于一个集合"的关系外，别无其他关系；

（2）线性结构：结构中的数据元素之间存在一个对一个的关系；

（3）树形结构：结构中的数据元素之间存在一个对多个的关系；

（4）图状结构：结构中的数据元素之间存在多个对多个的关系。

2. 线性表

2.1 概念

线性表是零个或者多个数据元素的有限序列。

特性: 数据元素之间是有顺序的. 数据元素个数是有限的. 数据元素的类型必须相同.

总结：线性表是具有相同类型的n( >= 0)个数据元素的有限序列( a0,a1, a2, ... an ) ai是表项，n是表长度。n=0时称为空表，在非空表中的每个数据元素都有一个确定的位置，ai是第i个数 据元素，称i为数据元素ai在线性表中的位序。

线性表是一个相当灵活的数据结构，他的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以 进行访问，还可进行插入和删除等。

数据元素之间的关系在计算机中有四种不同的存储结构：顺序存储结构、链式存储结构、索引存储结构 和散列存储结构。

2.2.1 特点

在数据元素的非空有限集合中，

• 0 为线性表的第一个元素,只有一个后继。
• an 为线性表的最后一个元素,只有一个前驱。
• 除a0和an外的其它元素ai,既有前驱，又有后继。
• 线性表能够逐项访问和顺序存取。

2.2.2 线性表的操作

• 创建线性表
• 销毁线性表
• 清空线性表
• 将元素插入线性表
• 将元素从线性表中删除
• 获取线性表中某个位置的元素
• 获取线性表的长度
• 判断线性表是否为空

2.2 线性表的顺序存储

2.2.1 基本概念

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。 

线性表(a1, a2, ..... an )的顺序存储示意图如下:

 2.2.2 线性表顺序存储的设计与实现

 操作要点:

●插入元素算法

■判断线性表是否合法

■判断插入位置是否合法

■把最后一个元素到插入位置的元素后移一个位置

■将新元素插入

■线性表长度加1

●获取元素操作

■判断线性表是否合法

■判断位置是否合法

■直接通过数组下标的方式获取元素

●删除元素算法

■判断线性表是否合法

■判断删除位置是否合法

■将元素取出

■将删除位置后的元素分 别向前移动一个位置

■线性表长度减1

2.2.3优点和缺点

优点:

●无需为线性表中的逻辑关系增加额外的空间。

●可以快速的获取表中合法位置的元素。

➢缺点:

●插入和删除操作需要移动大量元素。

●当线性表长度变化较大的时候 ,难以确定存储空间的容量

2.3 线性表的链式存储

2.3.1 基本概念

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两 个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

数据域：保存数据的地方 （当前节点所需要保存的数据）

指针域：保存地址的地方（是用来保存下一个节点的地址）

一般链表的头节点的数据域不存放任何数据，这是为了链表方便操作。

 ●单链表

■线性表的链式存储结构中 ,每个节点中只包含一个指针域,这样的链表叫单链表（即构成链表的每个 结点只有一个指向直接后继结点的指针）

■通过每个节点的指针域将线性表的数据元素按其逻辑次序链接在一 起(如图).

 ●双链表

■线性表的链式存储结构中 ,每个节点中包含两个指针域。

■指针域分别指向直接后继和直接前驱.

 ●单向循环链表

 ■线性表的链式存储结构中 ,每个节点中只包含一个指针域。

■表中最后一个结点的指针域指向头结点，整个链表形成一个环