线性表
1.1.链表
链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。
和顺序表不同，使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。
所以在链表中，每个数据元素可以配有一个指针用于找到下一个元素即节点，这意味着，链表上每个“元素”都长下图这个样子：
1.1.1.链表的特性
逻辑结构：线性结构
存储结构：链式存储
特点：内存不连续，通过指针来链接
解决问题：长度固定和插入删除麻烦问题
操作：增删改查
struct node_t
{
int data; // 数据域
struct node_t *next; // 指针域，指向下一个节点，存放的是下一个节点的地址
};
1.1.2.单向链表
1）有单向链表，存在头节点，头节点数据域无效，指针域有效
2）无头单向链表，每一个节点都有数据域和指针域，都有效
遍历无头单向链表
#include <stdio.h>
typedef struct node_t
{
int data; // 数据域：存放节点数据
struct node_t *next; // 指针域：保存下一个节点的地址
} link_node_t, *link_list_t;
int main(int argc, char const *argv[])
{
// 1. 定义三个节点
link_node_t A = {10, NULL};
link_node_t B = {20, NULL};
link_node_t C = {30, NULL};
// 2. 将节点链接起来
A.next = &B;
B.next = &C;
// 3. 定义一个指针，指向第一个节点，用于遍历链表
link_list_t p = &A;
// 4. 遍历无头链表
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\\n");
return 0;
}
遍历有头单项链表
#include <stdio.h>
typedef struct node_t
{
int data; // 数据域：存放节点数据
struct node_t *next; // 指针域：保存下一个节点的地址
} link_node_t, *link_list_t;
int main(int argc, char const *argv[])
{
// 1. 定义三个节点
link_node_t A = {10, NULL};
link_node_t B = {20, NULL};
link_node_t C = {30, NULL};
// 2. 将节点链接起来
A.next = &B;
B.next = &C;
// 3. 定义一个头节点，数据域无效，指针域指向第一个节点
link_node_t h = {'\\0', &A};
// 4. 定义一个指针，指向头节点
link_list_t p = &h;
// ５. 遍历有头链表
#if 1
// 方法一
while (p->next != NULL)
{
p = p->next;
printf("%d ", p->data);
}
printf("\\n");
#else
// 方法二
p = p->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\\n");
#endif
return 0;
}
有头单向链表的函数操作
linklist.h
#ifndef __LINKLIST_H__
#define __LINKLIST_H__
typedef int datatype;
typedef struct node_t
{
datatype data;//数据域
struct node_t *next;//指针域,指向自身结构体的指针
}link_node_t,*link_list_t;
//1.创建一个空的有头单向链表
link_node_t *createEmptyLinkList();
//2.链表指定位置插入数据
int insertIntoPostLinkList(link_node_t *p,int post, datatype data);
//3.计算链表的长度。
int lengthLinkList(link_node_t *p);
//4.遍历链表
void showLinkList(link_node_t *p);
//5.判断链表是否为空
int isEmptyLinkList(link_node_t *p);
//6.链表指定位置删除数据
int deletePostLinkList(link_node_t *p, int post);
//7.清空单向链表
void clearLinkList(link_node_t *p);
//8.修改指定位置的数据 post 被修改的位置 data修改成的数据
int changePostLinkList(link_node_t *p, int post, datatype data);
//9.查找指定数据出现的位置 data被查找的数据 //search 查找
int searchDataLinkList(link_node_t *p, datatype data);
//10.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int deleteDataLinkList(link_node_t *p, datatype data);
//11.转置链表
//解题思想：
//(1) 将头节点与当前链表断开，断开前保存下头节点的下一个节点，保证后面链表能找得到，定义一个q保存头节点的下一个节点，断开后前面相当于一个空的链表，后面是一个无头的单向链表
//(2) 遍历无头链表的所有节点，将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)
void reverseLinkList(link_node_t *p);
#endif
1）创建一个空的有头单项链表
只有一个头节点，指针域赋值为NULL
//1.创建一个空的有头单向链表
link_node_t *createEmptyLinkList()
{
link_list_t h = (link_list_t)malloc(sizeof(link_node_t));
if(NULL == h)
{
printf("createEmptyLinkList err\\n");
return NULL;
}
h->next = NULL;
return h;
}
2）链表指定位置插入数据
// 2.链表指定位置插入数据
int insertIntoPostLinkList(link_node_t *p, int post, datatype data)
{
link_list_t pnew = NULL;
// 1. 容错判断
if (post < 0 || post > lengthLinkList(p))
{
printf("insertIntoPostLinkList err\\n");
return -1;
}
// 2. 创建新节点, 并初始化
pnew = (link_list_t)malloc(sizeof(link_node_t));
if (NULL == pnew)
{
printf("pnew err\\n");
return -1;
}
pnew->data = data;
pnew->next = NULL;
// 3. 将头指针移动，指向插入位置前一个节点
for (int i = 0; i < post; i++)
p = p->next;
// 4. 将新节点插入到链表中，先连后面，在连前面
pnew->next = p->next;
p->next = pnew;
return 0;
}
3）计算链表的长度
// 3.计算链表的长度。
int lengthLinkList(link_node_t *p)
{
int len = 0;
while (p->next != NULL)
{
p = p->next;
len++;
}
return len;
}
4）遍历链表
//4.遍历链表
void showLinkList(link_node_t *p)
{
while(p->next != NULL)
{
p = p->next;
printf("%d ", p->data);
}
printf("\\n");
}
5）判断链表是否为空
//5.判断链表是否为空
int isEmptyLinkList(link_node_t *p)
{
return p->next == NULL;
}
6）链表指定位置删除数据
//6.链表指定位置删除数据
int deletePostLinkList(link_node_t *p, int post)
{
link_list_t pdel = NULL;
// 1. 容错判断
if(isEmptyLinkList(p) || post < 0 || post >= lengthLinkList(p))
{
printf("deletePostLinkList err\\n");
return -1;
}
// 2. 将头指针移动，指向被删除位置的前一个节点
for(int i = 0; i < post; i++)
p = p->next;
// 3. 删除操作
// 1) 定义一个pdel指向被删除的节点
pdel = p->next;
// 2) 跨过被删除的节点
p->next = pdel->next;
// 3) 释放被删除的节点
free(pdel);
pdel = NULL;
return 0;
}
7）清空单向链表
思想：
循环进行删除，每次删除头节点的下一个节点:
(1)定义一个pdel指针，指向被删除节点
(2)跨过被删除节点
(3)释放被删除节点
// 7.清空单向链表
void clearLinkList(link_node_t *p)
{
link_list_t pdel = NULL;
while (p->next != NULL)
{
// 1. 定义一个pdel指向被删除的节点
pdel = p->next;
// 2. 跨过被删除的节点
p->next = pdel->next;
// 3. 释放被删除的节点
free(pdel);
pdel = NULL;
}
}
8）修改指定位置的数据
// 8.修改指定位置的数据 post 被修改的位置 data修改成的数据
int changePostLinkList(link_node_t *p, int post, datatype data)
{
// 1. 容错判断
if (isEmptyLinkList(p) || post < 0 || post >= lengthLinkList(p))
{
printf("changePostLinkList err\\n");
return -1;
}
// 2. 将头指针移动到要修改的节点位置
for(int i = 0; i <= post; i++)
p = p->next;
// 3. 修改数据
p->data = data;
return 0;
}
9）查找指定数据在链表的位置
//9.查找指定数据出现的位置 data被查找的数据 //search 查找
int searchDataLinkList(link_node_t *p, datatype data)
{
int post = 0; // 记录找到的位置
while(p->next != NULL)
{
p = p->next;
if(p->data == data)
{
return post;
}
post++;
}
return -1;
}
10）删除单项链表中出现的指定数据
思想：p始终指向被删除节点的前一个，让q相当于遍历无头结点，pdel用于指向删除节点。
// 10.删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
int deleteDataLinkList(link_node_t *p, datatype data)
{
link_list_t pdel = NULL;
// 1. 定义一个指针q，指向头节点的下一个节点
link_list_t q = p->next;
// 2. 用q来遍历无头链表，将每一个节点与data做比较
while (q != NULL)
{
if (q->data == data)
{
// 1) 将pdel指向被删除的节点
pdel = q;
// 2) 将q指向删除节点的下一个节点
q = pdel->next;
// 3) 跨过被删除的节点
p->next = pdel->next;
// 4) 释放被删除的节点
free(pdel);
pdel = NULL;
}
else
{
// 不是指定的数据，将p和q向后移动一个位置
q = q->next;
p = p->next;
}
}
return 0;
}
11）转置链表
解题思想：
(1) 将头节点与当前链表断开，断开前保存下头节点的下一个节点，保证后面链表能找得到，定义一个q保存头节点的下一个节点，断开后前面相当于一个空的链表，后面是一个无头的单向链表
(2) 遍历无头链表的所有节点，将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)
// 反转有头单向链表 (p 指向头节点)
void reverseLinkList(link_node_t *p)
{
// 1. 判空保护：如果链表为空，直接返回
if (p == NULL || p->next == NULL) {
return;
}
// 2. 断开链表：q 指向第一个有效节点，头节点 p 变成空链表
link_list_t q = p->next; // q 用来遍历旧链表
p->next = NULL; // 头节点与后面断开，此时 p 是空链表的头
// 3. 遍历旧链表，逐个头插到新链表（即 p 后面）
link_list_t r = NULL; // r 用来保存当前要插入的节点
while (q != NULL)
{
r = q; // ① 取出当前旧链表的第一个节点
q = q->next; // ② 指针后移（**关键！必须先移，否则等会丢失旧链表**）
r->next = p->next; // ③ 头插：新节点的 next 指向当前新链表的第一个节点
p->next = r; // ④ 头节点指向新插入的节点
}
}
