一、什么是单链表
每个结点只包含一个指针域的链表，称为单链表。
（一）单链表结点的数据结构
单链表结点的数据结构图
// 结点结构体
typedef struct node
{
ElemType value;
struct node* link;
}Node;
（二）非空单链表数据结构
非空单链表的数据结构图
// 单链表结构体
typedef struct headerSingleList
{
Node* head;
int n;
}HeaderSingleList;
二、单链表的各个功能实现
（一）初始化
单链表的初始化：
（1）单链表的头指针赋值为
N
U
L
L
NULL
NULL
（2）单链表的长度初始化为0
// 单链表的初始化
Status Init(HeaderSingleList* list)
{
list->head = NULL;
list->n = 0;
return OK;
}
（二）根据索引查找元素
算法步骤：
（1）判断索引是否越界
（2）从头结点开始依次遍历单链表，直到找到目标结点
（3）将找到的值返回
void GetValue(HeaderSingleList* list, int i, int* value)
{
printf("调用了 GetValue() 函数\n");
Node* node = list->head;
for (int j = 0; j < i; j++)
{
node = node->link;
}
*value = node->value;
}
（三）根据索引插入元素
单链表的插入是指将新元素
x
x
x 插入到 初始链表
a
i
a_i
ai? 结点的后面。
算法步骤：
（1）为元素
x
x
x 生成新的结点，由指针
n
o
d
e
node
node 指向该结点，并将结点数据域
v
a
l
u
e
value
value 的值置为
x
x
x
（2）若传入的索引值
i
=
?
1
i = -1
i=?1，则表示要将新元素插入到头结点
（3）若传入的索引值
i
>
?
1
i > -1
i>?1，则表示要将新元素插入到非头结点，即新结点成为结点
a
i
a_i
ai?的直接后继结点，
a
i
+
1
a_{i+1}
ai+1?的直接前驱结点。
// 单链表的插入
Status Insert(HeaderSingleList* list, int i, int value)
{
// 如果插入的位置越界，则返回错误
if (i < -1 || i > list->n - 1)
{
return Error;
}
Node* newNode = malloc(sizeof(Node));
Node* before = list->head;
for (int j = 0; j < i; j++)
{
before = before->link;
}
newNode->value = value;
// 如果不是插入在头结点
if (i > -1)
{
newNode->link = before->link;
before->link = newNode;
}
// 如果插入在头结点
else
{
newNode->link = list->head;
list->head = newNode;
}
printf("调用了 Insert() 函数\n");
list->n++;
}
（N）未完待续
三、全部代码
#include <stdio.h>
#define ElemType int
#define Error 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define NotPresent 4
#define Duplicate 5
typedef int Status;
// 结点结构体
typedef struct node
{
ElemType value;
struct node* link;
}Node;
// 单链表结构体
typedef struct headerSingleList
{
Node* head;
int n;
}HeaderSingleList;
// 单链表的初始化
Status Init(HeaderSingleList* list)
{
list->head = NULL;
list->n = 0;
return OK;
}
// 单链表的插入
Status Insert(HeaderSingleList* list, int i, int value)
{
// 如果插入的位置越界，则返回错误
if (i < -1 || i > list->n - 1)
{
return Error;
}
Node* newNode = malloc(sizeof(Node));
Node* before = list->head;
for (int j = 0; j < i; j++)
{
before = before->link;
}
newNode->value = value;
// 如果不是插入在头结点
if (i > -1)
{
newNode->link = before->link;
before->link = newNode;
}
// 如果插入在头结点
else
{
newNode->link = list->head;
list->head = newNode;
}
printf("调用了 Insert() 函数\n");
list->n++;
}
void Delete(HeaderSingleList* list, int i)
{
if (list->n == 0)
{
return Error;
}
if (i < 0 || i >list->n - 1)
{
return Error;
}
Node* beforeNode = list->head;
Node* deleteNode = NULL;
// 如果删除头结点
if (i == 0)
{
list->head = list->head->link;
}
// 如果删除的不是头结点
else
{
// 找到要删除节点的前一个结点
for (int j = 0; j < i-1; j++)
{
beforeNode = beforeNode->link;
}
// 此时的 beforNode 是所要删除结点的前一个结点
deleteNode = beforeNode->link; // 要删除的结点deleteNode 为 beforNode 的下一个结点
beforeNode->link = deleteNode->link; // 将要删除结点的前一个结点的 link 指向 要删除结点的下一个结点
free(deleteNode);
}
printf("调用了 Delete(\%d) 函数\n", i);
list->n--;
}
void GetValue(HeaderSingleList* list, int i, int* value)
{
printf("调用了 GetValue() 函数\n");
Node* node = list->head;
for (int j = 0; j < i; j++)
{
node = node->link;
}
*value = node->value;
}
// 单链表的销毁
void Destory(HeaderSingleList* list)
{
printf("调用了 Destory() 函数\n");
Node* node = list->head;
while (list->head)
{
node = node->link;
free(list->head);
list->head = node;
}
}
void PrintAllValue(HeaderSingleList* list)
{
Node* node = NULL;
node = list->head;
while (node)
{
printf("%d -> ", node->value);
node = node->link;
}
printf("NULL\n\n");
}
int main()
{
HeaderSingleList* list = malloc(sizeof(HeaderSingleList));
Init(list);
Insert(list, -1, 4);
Insert(list, -1, 3);
Insert(list, -1, 2);
Insert(list, -1, 1);
Insert(list, -1, 0);
/*
int x = 0;
GetValue(list, 0, &x);
printf("%d\n", x);
*/
PrintAllValue(list);
Delete(list, 1);
PrintAllValue(list);
Destory(list);
PrintAllValue(list);
}