数据结构—线性表相关（1）

定义：零个或多个数据元素的有限序列

线性表的顺序存储的结构代码。

 #define MAXSIZE 20  /*存储空间初始分配量*/
 typedef int ElemType; /*Elemtype类型根据实际情况而定， 这里假设为int*/
 typedef struct
ElemType data [MAXSIZE); 
int length;
} SqList;

这里，我们就发现描述顺序存储结构需要三个属性:

• 存储空间的起始位置:数组data ，它的存储位置就是存储空间的存储位置。
• 线性表的最大存储容量: 数组长度MaxSize 。
• 线性表的当前长度: length .

线性表顺序存储结构的优缺点

优点

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的"碎片"

头指针与头结点的区别

头指针

• 头指针是指链表指向第一个结点的指针，着链表有头结点，则是指向头结点的指针
• 头指针有标识作用，所以常用头指针冠以链表的名字
• 无论链表是否为空.头指针均不为空。头指针是链表由与必要元素

头结点

• 头结点是为了操作的统一和方便而设立的，放在第一个的结点之前，其数据域一锻无意义(也可存储链表的长度)
• 有了头结点.对在第一元素结点前插入结点和删除第一结点，其操作与其它结点操作就统一
• 头结点不一定是链表的必要元素

线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置

为了表示每个数据元素al 与其直接后继数据元素al+1 之间的逻辑关系， 对
数据元素a1来说,除了存储其本身的信息之外，还需存储一个指向其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。 指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai 的存储映像，称为结点(Node) 。

n 个结点( al 的存储映像) 链结成一个链表，即为线性表( a1 ， a2,…, an ) 的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

线性表链式存储结构头指针与头结点的异同

头指针

• 头指针是指链表指向第一个结点的指针，着链表有头结点，则是指向头结点的指针
• 头船指针具有标识作用，所以常用头指针冠以链表的名字
• 无论链表是否为空.头指针均不为空。头指针是链表的必要元素

头结点

• 头结点是为了操作的统一和方便而设立的，放在第一个元素的结点之前，其数据域一般无意义(也可存储链表的长度)
• 有了头结点.对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了
• 头结点不一定是链表的必要元素

单链表整表创建的算法思路:

1. 声明一结点p 和计数器变量i ;
2. 初始化一空链表L;
3. 让L的头结点的指针指向NULL ，即建立一个带头结点的单链表i
4. 循环:

• 生成一新结点赋值给p;
• 随机生成一数字赋值给p 的数据域p->data;
• 将p插入到头结点与前一新结点之间。

获得链表第i个数据的算法思路:

1. 声明一个结点p 指向链表第一个结点，初始化j 从1 开始;
2. 当j<i 时，就遍历链表，让p 的指针向后移动，不断指向下一结点， j 累加1;
3. 若到链表末尾p 为空，则说明第i 个元素不存在;
4. 否则查找成功，返回结点p 的数据。

单链表第i 个数据插入结点的算法思路:

1. 声明一结点p 指向链表第一个结点，初始化j 从1 开始i
2. 当j<i 时，就遍历链表，让p 的指针向后移动，不断指向下一结点， j 累加1;
3. 若到链表末尾p 为空，则说明第i 个元素不存在i
4. 否则查找成功，在系统中生成一个空结点s;
5. 将数据元素e 赋值给s->也ta ;
6. 单链表的插入标准语句s->next=p->next; p->next=s ;
7. 返回成功。

单链表第i个数据删除结点的算法思路:

1. 声明一结点p 指向链表第一个结点， 初始化j 从1 开始j
2. 当j<i就遍历链表，让p的指针向后移动，不断指向下一个结点j累加1
3. 若到链表末尾p 为空，则说明第i个元素不存在;
4. 否则查找成功，将欲删除的结点p->next赋值给q ;
5. 单链表的删除标准语句p->next=q->next;
6. 将q结点中的数据赋值给e，作为返回;
7. 释放q结点;
8. 返回成功。

单链表整表删除的算法思路如下:

1. 声明一结点p 和q ;
2. 将第一个结点赋值给p;
3. 循环:

• 将下一结点赋值给q;
• 释放p;
• 将q 赋值给p 。

单链表结构与顺序存储结构优缺点

存储分配方式

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能

• 查找
• 顺序存储结构o(1)
• 插入和删除
• 单链表o(n)
• 顺序存储结构需要平均移动表长一半的元素，时间为o(n)
• 单链表在线出某位置的指针后，插入和删除的时间仅为o(1)

空间性能

• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也也不受限制

欢迎关注，后续贴上相关代码和新的内容，总结备忘……