线性表
一、什么是线性表？
首先，它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，中间的每个元素都有且仅有一个直接前驱和后继。
线性表就是包含零个或多个元素的有限序列
其存储结构分为两种：
1. 顺序存储结构
2. 链式存储结构
二、线性表的顺序存储结构
2.1 顺序存储结构的定义
线性表的顺序存储结构，指的是用一段连续的存储单元依此存储线性表的数据元素。
说白了，就是就是在内存中找了块儿地儿，通过占位的形式，把一定的存储空间占用了，然后把相同类型的数据元素依此存放在这块空地中。
既然线性表的每个元素的数据类型都相同，所以可以用一维数组来实现顺序存储结构。
2.2 顺序存储结构的实现
先来看一下顺序存储结构的代码：
typedef int SeqListType;
typedef struct SeqList
{
SeqListType* data;
size_t size;
size_t capacity;
} SeqList;
我们可以发现描述顺序存储结构需要三个属性：
- 存储空间，也就是数组data
- 线性表最大存储容量，也就是动态开辟的容量capacity
- 线性表当前长度size
要注意，线性表的当前长度应当不大于线性表的最大存储容量。
2.3 插入操作
头插法算法思路：
- 断言传入的是否为空指针。
- 如果线性表长度大于线性表容量，则抛出异常或者增容。
- 从最后一个元素开始向前遍历到第一个元素，分别将它们向后移动一个位置。
- 将要插入元素填入头部。
- 表长加1.
代码实现如下：
static void IsExpansion(SeqList* pl)
{
assert(pl);
if (pl->size == pl->capacity)
{
SeqListType* newdata = (SeqListType*)realloc(pl->data, sizeof(SeqListType) * pl->capacity * 2);
if (newdata != NULL)
{
pl->data = newdata;
pl->capacity *= 2;
}
else
{
printf("%s\n", strerror(errno));
exit(-1);
}
}
}
void SeqListPushFront(SeqList* pl, SeqListType x)
{
assert(pl);
IsExpansion(pl);
int i;
for (i = pl->size - 1; i >= 0; i--)
{
pl->data[i + 1] = pl->data[i];
}
pl->data[0] = x;
pl->size += 1;
}
在这个代码中，为了方便，把扩容的操作封装成了一个函数。
这是头插法，那尾插法呢？
尾插法算法思路：
- 断言传入的是否为空指针。
- 如果线性表长度大于线性表容量，则抛出异常或者增容。
- 将要插入元素放入线性表尾部，同时size++
2.4 删除操作
既然有了插入操作，那么与之对应，必然也会有删除的操作。
头删法算法思路：
- 断言传入指针否为空且线性表当前长度是否为0
- 从删除位置开始遍历到最后一个元素位置，将他们分别前移一个位置。
- 表长减一
实现代码如下：
void SeqListPopFront(SeqList* pl)
{
assert(pl && pl->size > 0);
int i;
for (i = 1; i < pl->size; i++)
{
pl->data[i - 1] = pl->data[i];
}
pl->size -= 1;
}
头删法要移动元素，相对麻烦一点，而尾部删除就很简单了，除了断言之外，只需要将表长减一即可：
void SeqListPopBack(SeqList* pl)
{
assert(pl && pl->size > 0);
pl->size -= 1;
}
2.5 顺序存储结构的优缺点
优点：
1.无需为表中元素之间的逻辑关系而增加额外的存储空间
2.随机存取，能够快速的存取表中任意位置的元素
缺点：
1.插入和删除操作需要移动大量的元素
2.当线性表变化较大时，难以确定存储空间的容量
3.造成存储空间的碎片化（就像切蛋糕，把大块切走了，只剩下边边角角，虽然也能吃，但是吃不饱）
三、链式存储结构
3.1 链式存储结构的定义
链式存储结构除了要存储数据元素的信息外，还要存储其后继元素的地址。存储数据元素的信息就是数据域，而存储地址信息的称为指针域。而这两者组成的结构就是链表中的一个节点，当多个节点连接起来就是一个链表。
对于线性表而言，总得有头有尾。我们把链表的第一个结点的存储位置叫做头指针，而对于最后一个节点之后没有元素了，就把其指针域指向NULL。
3.2 头结点与头指针
有时候，为了更方便的对链表进行操作，会在单链表的第一个结点前设置一个节点，称为头结点。
头指针：
头指针指向链表的第一个节点，若有头结点则指向头结点。
头指针具有标识作用，所以常用头指针冠以链表的名字。
头指针是链表的必要元素。
头结点：
头结点是为了操作的统一和方便而设立的，放在链表第一个元素之前，其数据域大多无意义，但也可以用来保存链表长度。
有了头结点，对链表头部的插入和删除操作就统一了。
头结点不是链表的必要元素。
3.3 链式存储结构的实现
先来看一下链式存储结构的代码：
typedef int SLDataType;
typedef struct SListNode
{
SLDataType data;
struct SLNode* next;
} SLNode;
typedef SLNode* SLinkList;
3.4 插入操作
单链表的尾插法算法思路（无头结点）：
- 创建新结点
- 判断链表是否为空
- 为空则让头指针指向新结点
- 否则找到最后一个结点，让其指向新结点
static SLNode* BuySLNode(SLDataType x)
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
newnode->next = NULL;
newnode->data = x;
return newnode;
}
void SListPushBack(SLinkList* L, SLDataType x)
{
SLNode* cur = *L;
SLNode* newnode = BuySLNode(x);
if (cur == NULL)
{
*L = newnode;
}
else
{
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
}
这里尾插我传了二级指针，原因很简单，如果要改变头指针的指向的话，就要传二级指针，反之则没有必要。
头插法的思路就相对简单：
- 创建新结点。
- 新结点的next指向原链表
- 修改头指针指向新结点
void SListPushFront(SLinkList* L, SLDataType x)
{
SLNode* newnode = BuySLNode(x);
newnode->next = (*L);
(*L)= newnode;
}
3.4 删除操作
单链表尾删法算法思路：
- 判断链表是否为空
- 若只有一个结点，释放结点，同时让链表指空
- 若不止一个结点，找到最后一个结点及其前驱
- 让前驱节点指向NULL，同时释放尾结点
void SListPopBack(SLinkList* L)
{
assert(*L != NULL);
SLNode* tail = *L;
if (tail->next == NULL)
{
*L = NULL;
}
else
{
SLNode* prev = NULL;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
prev->next = tail->next;
}
free(tail);
tail = NULL;
}
单链表头删法算法思路：
- 判断链表是否为空
- 头指针指向第一个结点的next
- 释放第一个结点
void SListPopFront(SLinkList* L)
{
assert(*L);
SLNode* p = *L;
*L = p->next;
free(p);
p = NULL;
}
四、链式存储和顺序存储的优缺点
对单链表结构和顺序存储结构进行对比：
4.1 存储分配方式
顺序存储结构用一段连续的存储单元一次存储线性表的数据元素
单链表采用链式存储结构，用一组任意的存储单元存放线性表元素
4.2 时间性能
顺序存储结构是随机存取，查找是O(1)
单链表查找需要遍历链表，是O(n)
而对于插入和删除，顺序存储需要对元素进行移动，时间复杂度为O(n)
单链表在找到某位置后，插入和删除的时间复杂度是O(1)
4.3 空间性能
顺序存储结构需要预先分配存储空间，分配过多就会造成存储空间的浪费，而分配过少则会发生上溢
而单链表则按需分配，且元素个数不受限制
总结
根据顺序存储和链式存储的特性，若线性表需要进行频繁的查找很少进行删除和插入的操作，就可以采用顺序存储，反之则益采用链式存储。所以说，顺序存储和链式存储各有其优劣，在使用时要根据情况进行抉择。
|