1. 概念
链表就是将 结点 用链串起来的线性表，链就是 结点 中的指针域。
2. 接口实现
对比操作顺序表的结构体定义
用来操作顺序表的结构体定义
struct SeqList
{
int data[10]; // 顺序表
int last;
}
用来操作有头单向链表的结构体定义
struct LinkListNode
{
int data;
struct LinkListNode *next;
};
链表 操作链表的结构体就是链表中结点的结构体。
顺序表 操作顺序表的结构体中就包含了顺序表数组。
2.1. 定义操作单向链表的结构体
LL.h
// 1. 定义用来操作有头单向链表的结构体
typedef struct LinkListNode
{
int data;
struct LinkListNode *next;
} LLN, *LL;
2.2. 创建空的有头单向链表
在对有头单链表进行操作之前，需要对其进行初始化，即创建一个空的有头单链表。
初始化只需malloc开辟一个结点大小的空间存放有头单向链表头结点，然后让有头单链表中的头结点指针域指向NULL即可。
想要找到单向链表并对其进行操作就需要一个指针来指向单向链表的头结点，该指针就是头指针H。
LL.h
#ifndef _LL_H_
#define _LL_H_
#include <stdio.h>
#include <stdlib.h>
// 1. 定义用来操作有头单向链表的结构体
typedef int DataType;
typedef struct LinkListNode
{
DataType data;
struct LinkListNode *next;
} LLN, *LL;
// 2. 创建空的有头单向链表
LL LLCreate();
#endif
LL.c
#include "LL.h"
// 2. 创建空的有头单向链表
LL LLCreate()
{
LL H = (LL)malloc(sizeof(LLN));
if (NULL == H)
{
printf("LLCreate failed, H malloc err.\n");
return NULL;
}
H->next = NULL;
return H;
}
Test.c
#include "LL.h"
int main(int argc, char const *argv[])
{
LL H = LLCreate();
return 0;
}
开辟空间存放头结点，并返回指向头结点的指针，该指针称为该链表的头指针。
2.3. 长度
使用伪头指针遍历单向链表
有头单向链表的遍历条件：H->next != NULL
无头单向链表的遍历条件：H != NULL
长度
// 3. 长度
int LLLength(LL H)
{
int len = 0;
while (H->next != NULL) // 伪头指针指针域next不为空
{
len++;
H = H->next; // 伪头指针后移
}
return len;
}
2.4. 插入
假设要在有头单向链表的post位置插入一个新的结点。
post类比下标，即从0开始。
容错判断 [0, len]
post不能小于0post不能大于链表的长度
移动伪头指针，使其指向插入位置的前一个结点
for (int i = 0; i < post; i++)
H = H->next;
生成新结点
LL PNew = malloc()
PNew->data = data;
PNew->next = NULL;
插入（先后再前）
PNew->next = H->next;
H->next = PNew;
LL.c
// 4. 有头单向链表指定位置插入数据
void LLInsert(LL H, int post, DataType data)
{
// 4.1 容错判断 [0, len]
if (post < 0 || post > LLLength(H))
{
printf("LLInsert failed, post not at [0, len].\n");
return ;
}
// 4.2 移动伪头指针，使其指向插入位置前驱post-1
for (int i = 0; i < post; i++)
H = H->next;
// 4.3 开辟新结点存放插入数据
LL PNew = (LL)malloc(sizeof(LLN));
if (NULL == PNew)
{
printf("LLInsert failed, PNew malloc err.\n");
return ;
}
PNew->data = data;
PNew->next = NULL;
// 4.4 插入（先后再前）
PNew->next = H->next;
H->next = PNew;
}
Test.c
#include "LL.h"
int main(int argc, char const *argv[])
{
LL H = LLCreate();
LLInsert(H, 0, 100);
LLInsert(H, 1, 111);
LLInsert(H, 2, 222);
LLInsert(H, 3, 333);
int len = LLLength(H);
printf("LLLength is %d\n", len);
return 0;
}
2.5. 打印
LL.c
// 5. 打印
void LLPrint(LL H)
{
while (H->next != NULL) // 伪头指针指针域next不为空
{
H = H->next; // 伪头指针后移
printf("%d\t", H->data);
}
printf("\n");
}
Test.c
#include "LL.h"
int main(int argc, char const *argv[])
{
LL H = LLCreate();
LLInsert(H, 0, 100);
LLInsert(H, 1, 111);
LLInsert(H, 2, 222);
LLInsert(H, 3, 333);
int len = LLLength(H);
printf("LLLength is %d\n", len);
LLPrint(H);
return 0;
}
典型HG错误
// 5. 打印
void LLPrint_test(LL H)
{
for (int i = 0; i < LLLength(H); i++)
{
H = H->next;
printf("第%d次长度为%d\t", i, LLLength(H));
printf("%d\n", H->data);
}
}
2.6. 查找
返回指定数据在单向链表中首次出现的位置
思路：
post = 0- 遍历
- 如果相等
return post - 不等
post++
- 遍历结束没找到
return -1
LL.c
// 6. 查找指定数据在单向链表中首次出现的位置
int LLFind(LL H, DataType data)
{
int post = 0;
while (H->next) // while (H->next != NULL)
{
H = H->next;
if (H->data == data)
return post;
else
post++;
}
return -1;
}
2.7. 修改
修改指定位置数据
post类比下标，即从0开始。
LL.c
// 7. 修改指定位置数据
void LLModify(LL H, int post, DataType data)
{
// 7.1 容错判断 [0, len)
if (post < 0 || post >= LLLength(H))
{
printf("LLModify failed, post not at [0, len).\n");
return;
}
// 7.2 移动伪头指针指向post结点
for (int i = 0; i <= post; i++)
H = H->next;
// 7.3 修改数据
H->data = data;
}
Test.c
#include "LL.h"
int main(int argc, char const *argv[])
{
LL H = LLCreate();
LLInsert(H, 0, 100);
LLInsert(H, 1, 111);
LLInsert(H, 2, 222);
LLInsert(H, 3, 333);
int len = LLLength(H);
printf("LLLength is %d\n", len);
LLPrint(H);
int post = LLFind(H, 222);
if (post < 0)
printf("222 not found.\n");
else
printf("222's position is %d\n", post);
LLModify(H, 2, 999);
LLPrint(H);
return 0;
}
标签：int,LL,单向,next,链表,post,data From： https://blog.51cto.com/u_16225641/7079991