线性表顺序存储结构的优缺点
顺序表优点
- 无须为了表示中间的元素之间的逻辑关系而增加额外的存储空间；
- 因为以数组形式存储，可以快速地存取表中任一位置的元素。
顺序表缺点
- 插入和删除操作需要移动大量元素，时间复杂度为O(N)；
- 当线性表长度变化较大时，难以确定存储空间的容量；
- 造成存储空间的“碎片”。
顺序存储结构不足的解决办法
其实顺序表最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费极大时间，因为相邻两元素的存储位置也具有邻居关系。它们编号是1,2,3,...,n，它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。
那这样的话，我们反正都要让相邻的元素都留有足够余地，那么干脆所有的元素都不考虑相邻位置了，哪里有空位就到哪里，而只是让每个元素知道他下一个元素的位置在哪里，这样我们就可以在第一个元素时，就知道第二个元素的位置（内存地址），而找到它；在第二个元素时，就知道第三个元素的位置（内存地址），而找到它。这样所有的元素我们就都可以通过遍历而找到了。
其实这个思路也就是链表存储思路，而本篇文章着重讲述链表中的单链表。
线性表链式存储结构定义
在链式结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。
数据域：存储数据元素信息的域称为数据域；
指针域：存储直接后继位置的域称为指针域。
在指针域中存储的信息称为指针或链。数据域与指针域信息组成数据元素的存储映像，称为结点。
单链表：n个结点链结成的链表，此链表中的每个结点中只包含一个指针域。
单链表的代码实现以及分析
单链表的结构代码
单链表中的结点，是由存放数据元素的数据域和存放后继结点地址的指针域组成的。所以，假设这个数据为val，存放后继结点地址的指针为next。
typedef int SLNDataType;
typedef struct SListNode
{
struct SListNode* next;
SLNDataType val;
}SLNode;
单链表中的每一个节点都是一个结构体成员，也就是多个结构体构成了一条链表。这与顺序表不同，顺序表由于数组存储 ，所以就是一个结构体的数组中存储了多个节点。
单链表的遍历打印
void SLTPrint(SLNode* phead)
{
assert(phead);
SLNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->val);
cur = cur->next;
}
printf("NULL\n");
}单链表建立新的头结点
在创建新的头结点时，需要用到malloc函数，关于malloc的使用方法，这里不做过多阐述，大家有什么不懂的，可以点击链接（单击即可查看）详细学习malloc的使用方法哦。
C库函数中 void *malloc(size_t size) 分配所需的内存空间，并返回一个指向它的指针。
malloc是分配内存空间的函数。
SLNode* SLTCreateNode(SLNDataType x)
{
SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
if (newnode == NULL)
{
perror("malloc fail\n");
exit(-1);
}
newnode->next = NULL;
newnode->val = x;
return newnode;
}单链表的尾插
那如果这是一个空表的话，那么就直接让这个单链表为指针，指向新创建的节点。
void SLTPushBack(SLNode** pphead, SLNDataType x)
{
assert(pphead);
SLNode* Newnode = SLTCreateNode(x);
if (*pphead == NULL)
{
*pphead = Newnode;
}
else
{
SLNode* tail = pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = Newnode;
}
}单链表的头插
void SLTPushFront(SLNode** pphead, SLNDataType x)
{
assert(pphead);
SLNode* Newnode = SLTCreateNode(x);
Newnode->next = *pphead;
*pphead = Newnode;
}单链表的尾删
void SLTPopBack(SLNode** pphead)
{
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}单链表的头删
void SLTPopFront(SLNode** pphead)
{
assert(pphead);
assert(*pphead);
SLNode* cur = (*pphead)->next;
//注意在单链表头删的时候，如果只有一个节点，那也是可以的，就让那个临时的为空
free(*pphead);
*pphead = cur;
}单链表的查找x数据
SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
SLNode* cur = phead;
while (cur)
{
if (cur->val == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;
}单链表在pos位置插入x的数
SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
assert(*pphead);
assert(pphead);
assert(pos);
if (*pphead==pos)
{
SLTPushFront(pphead,x);
}
else
{
SLNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLNode* Newnode = SLTCreateNode(x);
prev->next = Newnode;
Newnode->next = pos;
}
}单链表删除pos位置上的值
void SLTErase(SLNode** pphead, SLNode* pos)
{
assert(*pphead);
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLNode* prev = *pphead;
while (prev->next!=pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}单链表的销毁
void SLTDestroy(SLNode** pphead)
{
assert(pphead);
SLNode* cur = *pphead;
while (cur)
{
SLNode* tmp = cur->next;
free(cur);
cur = tmp;
}
*pphead = NULL;
}
