- 一、单链表的概念及结构
- 二、无头+单向+非循环链表实现
- 1.单链表的创建
- 2.动态申请一个节点
- 3.单链表打印
- 4.单链表尾插
- 5.单链表头插
- 6.单链表尾删
- 7.单链表头删
- 8.单链表查找
- 9.单链表在pos位置之后插入
- 10.单链表删除pos位置之后的值
- 11.单链表销毁
- 三、总结
- 四、完整代码
二、无头+单向+非循环链表实现 1.单链表的创建概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链
接次序实现的 。实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
- 单向、双向
- 带头、不带头
- 循环、非循环
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
- 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结
构，如哈希桶、图的邻接表等等。- 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向
循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而
简单了。
typedef int DateType; //为了方便的改变数据的类型
typedef struct ListNode
{
DateType data;
struct ListNode* next;
}ListNode;
2.动态申请一个节点
ListNode* BuyListNode(DateType x)
{
//创建一个结构体节点
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL)//malloc之后判断指针是否为空
{
printf("malloc fail!n");
exit(-1);
}
node->data = x;//将节点中的data初始化为x
node->next = NULL;//将节点中的next置为空
return node;//将节点的地址送出去
}
3.单链表打印
void ListPrint(ListNode* phead)
{
while (phead != NULL)//当指针指向非空时，打印data
{
printf("%d->", phead->data);//这里用->辅助理解
phead = phead->next;//打印完后，就让phead指向下一个节点，类似于循环中的i++
}
printf("NULLn");//当没有结点，即phead为空时，打印NULL
}
4.单链表尾插
void ListPushBack(ListNode** pphead, DateType x)
{
ListNode* newnode = BuyListNode(x);//插入元素，先创建新结点
if (*pphead == NULL)//如果本来无结点，即*pphead为空，直接*pphead指向newnode即可
{
*pphead = newnode;
}
else//若本来有结点，那么就需要找尾，才能尾插
{
ListNode* tail = *pphead;
while (tail->next != NULL)//当尾结点的next为空时，停止循环找到尾了
{
tail = tail->next;
}
tail->next = newnode;//让尾指向newnode
}
}
5.单链表头插
void ListPushfront(ListNode** pphead, DateType x)
{
ListNode* newnode = BuyListNode(x);//插入元素，先创建新结点
newnode->next = *pphead;//先让newnode的next指向*pphead
*pphead = newnode;//再让*pphead指向newnode
//顺序一定不能错！！！
}
6.单链表尾删
void ListPopBack(ListNode** pphead)
{
assert(*pphead);//判断是否有结点，即*pphead是否为空
if ((*pphead)->next == NULL)//当只有一个结点时，直接free
{
free(*pphead);
*pphead = NULL;
}
else//当有多个结点时，找尾，然后尾删
{
ListNode* prev = *pphead;//尾的前一个结点，因为需要让尾的前一个结点指向NULL
ListNode* tail = *pphead;//尾
while (tail->next != NULL)//当尾的next指向NULL时，停止
{
prev = tail;
tail = tail->next;
}
free(tail);//删尾
tail = NULL;
prev->next = NULL;//让尾的前一个结点指向NULL
}
}
7.单链表头删
void ListPopFront(ListNode** pphead)
{
assert(*pphead);//判断是否有结点，即*pphead是否为空
if ((*pphead)->next == NULL)//当只有一个结点时，直接free
{
free(*pphead);
*pphead = NULL;
}
else//当有多个结点时
{
ListNode* next = (*pphead)->next;//创建临时指针保存(*pphead)->next
free(*pphead);//释放掉*pphead
*pphead = next;//将保存的(*pphead)->next重新赋给*pphead
}
}
8.单链表查找
ListNode* ListFind(ListNode* phead, DateType x)
{
assert(phead);//判断是否有结点，即*pphead是否为空
ListNode* cur = phead;
while (cur != NULL)//cur为NULL时，结束循环，找不到x
{
if (cur->data == x)//找到了返回
{
return cur;
}
cur = cur->next;
}
return cur;//当找不到时，返回NULL
}
9.单链表在pos位置之后插入
void ListInsertAfter(ListNode* pos, DateType x)
{
assert(pos);//判断需要插入的位置是否为空
ListNode* newnode = BuyListNode(x);//插入元素，先创建新结点
newnode->next = pos->next;
pos->next = newnode;
//注意顺序一定不能错
}
10.单链表删除pos位置之后的值
void ListEraseAfter(ListNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
ListNode* next = pos->next;//记录下pos->next，待会free
pos->next = next->next;
free(next);
next = NULL;
}
}
11.单链表销毁
void ListDestory(ListNode* phead)
{
assert(phead);
free(phead);
phead = NULL;
}
三、总结
四、完整代码细心
//LinkedList.h #pragma once #include#include #include typedef int DateType; typedef struct ListNode { DateType data; struct ListNode* next; }ListNode; ListNode* BuyListNode(DateType x); void ListPrint(ListNode* phead); void ListPushBack(ListNode** pphead, DateType x); void ListPushFront(ListNode** pphead, DateType x); void ListPopBack(ListNode** pphead); void ListPopFront(ListNode** pphead); ListNode* ListFind(ListNode* phead, DateType x); void ListInsertAfter(ListNode* pos, DateType x); void ListEraseAfter(ListNode* pos); void ListDestory(ListNode* phead);
//LinkedList.c
#include "SingleLinkedList.h"
ListNode* BuyListNode(DateType x)
{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL)
{
printf("malloc fail!n");
exit(-1);
}
node->data = x;
node->next = NULL;
return node;
}
void ListPrint(ListNode* phead)
{
while (phead != NULL)
{
printf("%d->", phead->data);
phead = phead->next;
}
printf("NULLn");
}
void ListPushBack(ListNode** pphead, DateType x)
{
ListNode* newnode = BuyListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
ListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void ListPushFront(ListNode** pphead, DateType x)
{
ListNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void ListPopBack(ListNode** pphead)
{
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
ListNode* prev = *pphead;
ListNode* tail = *pphead;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
void ListPopFront(ListNode** pphead)
{
assert(*pphead);
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
ListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}
ListNode* ListFind(ListNode* phead, DateType x)
{
assert(phead);
ListNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return cur;
}
void ListInsertAfter(ListNode* pos, DateType x)
{
assert(pos);
ListNode* newnode = BuyListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void ListEraseAfter(ListNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
ListNode* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}
}
void ListDestory(ListNode* phead)
{
assert(phead);
free(phead);
phead = NULL;
}
x)
{
assert(pos);
ListNode* newnode = BuyListNode(x); newnode->next = pos->next; pos->next = newnode;
}
void ListEraseAfter(ListNode* pos)
{
assert(pos);
if (pos->next == NULL)
{
return;
}
else
{
ListNode* next = pos->next;
pos->next = next->next;
free(next);
next = NULL;
}
}
void ListDestory(ListNode* phead)
{
assert(phead);
free(phead); phead = NULL;
}
