2018-07-30------数据结构
1、线性表的定义
线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列
除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，有且只有一个直接后继。
2、线性表的特点
表中元素个数有限
具有逻辑上的顺序性，各元素排序有先后次序
都是数据元素，每一个元素都是单个的
数据类型相同，每一个元素占有相同大小的存储空间
具有抽象性，只讨论逻辑关系，不讨论具体内容
3、线性表的基本操作
4、顺序表的定义
线性表的顺序存储又称为顺序表。使用一组地址连续的存储单元，一词存储线性表中的数据元素，特点是表中元素的逻辑顺序与物理顺序相同
注意：线性表中的元素的喂序是从1开始的，而数组下标是从0开始的
5、数组的分配
一维数组的静态分配：大小空间已经固定，空间满了后，再加入新的数据，会导致溢出
动态分配，存储数组的空间实在程序执行过程中通过动态存储分配语句分配的，一旦数据满，则重新开辟更大的存储空间
注：动态分配不是链式存储，还是顺序存储结构，物理结构没有变化，依然是随机存储方式
6、顺序表的特点
随机访问，即通过首地址和元素序号可以再O（1）的时间内找到指定的元素，存储密度高，每个节点只存储数据元素。
7、顺序表的基本操作
8、线性表的链式表示
由于顺序表的插入删除需要移动大量元素，所以引入链式存储，通过链的建立起元素之间的逻辑关系，对线性表的插入删除操作不需要移动元素，只需要修改指针。
9、单链表的定义
线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素，对每个链表节点，处了存放自身信息，还需要存放一个指向其后继的指针。
10、单链表的特点
是非随机存取的存储结构，不能直接找到表中某个特定的节点，需要查找时，需要从头遍历
通常用头指针来标识一个单链表，为了操作方便，在单链表的结点之前添加一个附加结点，称为头结点
11、头结点和头指针的区别
不管带不带头结点，头指针始终指向链表的第一个结点，，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息。
12、头结点的好处
1）由于开始结点的位置被存放在头结点的指针域中所以在链表的第一个位置上的操作和其他位置一样
2）无论链表是否为空，头指针都是指向头结点的非空指针
