数据结构之链表
为了避免插入和删除的线性开销，我们需要允许表可以不连续存储，否则表的部分或全部需要整体移动。
链表由一系列不必在内存中相连的结构组成。每一个结构均含有表元素和指向包含该表后续元素的结构的指针。我们称之为NEXT指针，最后一个next指针指向NULL。
指针变量是包含存储另外某个数据地址的变量。因此，如果P被声明为指向一个结构的指针，那么存储在P中的值就被解释为主存中的一个位置，在该位置能够找到一个结构。该结构的一个域可以通过P->FieldName访问。
一.链表的创建操作
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int ElementType; // 定义数据类型,可根据需要进行其他类型定义
// 链表节点的定义
typedef struct ListNode {
ElementType Element; // 数据域，存放数据
struct ListNode* Next; // 指向下一个链表节点
}Node, *PNode;
// 链表创建函数定义
PNode CreateList(void) {
int len ; // 用于定义链表长度
int val ; // 用于存放节点数值
int i=0;
PNode PHead = (PNode)malloc(sizeof(Node)); // 创建分配一个头节点内存空间
//头节点相当于链表的哨兵，不存放数据，指向首节点（第一个节点）
if (PHead == NULL) // 判断是否分配成功
{
printf("空间分配失败 \n");
exit(-1);
}
PNode PTail = PHead; // 链表的末尾节点，初始指向头节点
PTail->Next = NULL; // 最后一个节点指针置为空
printf("请输入节点个数：");
scanf("%d", &len); // 输入节点个数
for(i=0;i<len;i++) {
PNode pNew = (PNode)malloc(sizeof(Node)); // 分配一个新节点
if (pNew == NULL) {
printf("分配新节点失败\n");
exit(-1);
}
printf("请输入第 %d 个节点的数据：", i + 1);
scanf("%d", &val); // 输入链表节点的数据
pNew->Element = val; // 把数据赋值给节点数据域
PTail->Next = pNew; // 末尾节点指针指向下一个新节点
pNew->Next = NULL; // 新节点指针指向为空
PTail = pNew; // 将新节点复制给末尾节点
}
printf("创建链表成功\n");
return PHead; // 返回头节点
}
// 主函数
int main() {
PNode List = CreateList(); //创建一个指针，使其指向新创建的链表的头指针
return 0;
}在liunx下运行
请输入节点个数：5
请输入第 1 个节点的数据：1
请输入第 2 个节点的数据：2
请输入第 3 个节点的数据：3
请输入第 4 个节点的数据：4
请输入第 5 个节点的数据：5
创建链表成功二.链表的遍历操作
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef int ElementType; // 定义数据类型,可根据需要进行其他类型定义
// 链表节点的定义
typedef struct ListNode {
ElementType Element; // 数据域，存放数据
struct ListNode* Next; // 指向下一个链表节点
}Node, *PNode;
// 链表创建函数定义
PNode CreateList(void) {
int len ; // 用于定义链表长度
int val ; // 用于存放节点数值
int i=0;
PNode PHead = (PNode)malloc(sizeof(Node)); // 创建分配一个头节点内存空间
//头节点相当于链表的哨兵，不存放数据，指向首节点（第一个节点）
if (PHead == NULL) // 判断是否分配成功
{
printf("空间分配失败 \n");
exit(-1);
}
PNode PTail = PHead; // 链表的末尾节点，初始指向头节点
PTail->Next = NULL; // 最后一个节点指针置为空
printf("请输入节点个数：");
scanf("%d", &len); // 输入节点个数
for(i=0;i<len;i++) {
PNode pNew = (PNode)malloc(sizeof(Node)); // 分配一个新节点
if (pNew == NULL) {
printf("分配新节点失败\n");
exit(-1);
}
printf("请输入第 %d 个节点的数据：", i + 1);
scanf("%d", &val); // 输入链表节点的数据
pNew->Element = val++; // 把数据赋值给节点数据域
PTail->Next = pNew; // 末尾节点指针指向下一个新节点
pNew->Next = NULL; // 新节点指针指向为空
PTail = pNew; // 将新节点复制给末尾节点
}
printf("创建链表成功\n");
return PHead; // 返回头节点
}
// 定义链表遍历函数
void TraverseList(PNode List) {
PNode P = List->Next; // 首节点赋值给临时节点P
printf("遍历链表的值为：");
if (P == NULL)
printf("链表为空");
while (P != NULL) //当临时节点P不为尾节点时，输出当前节点值
{
printf("%d ", P->Element);
P = P->Next;
}
printf("\n");
}
// 主函数
int main() {
PNode List = CreateList(); //创建一个指针，使其指向新创建的链表的头指针
TraverseList(List);
return 0;
}运行
请输入节点个数：5
请输入第 1 个节点的数据：2
请输入第 2 个节点的数据：3
请输入第 3 个节点的数据：4
请输入第 4 个节点的数据：5
请输入第 5 个节点的数据：6
创建链表成功
遍历链表的值为：2 3 4 5 6 三.链表的查询操作
// 定义链表查询函数
PNode FindList(PNode List) {
PNode P = List->Next; // 定义临时指针P指向首节点的地址
int num = 0; // 用于记录链表节点位置
int val = 0; // 用于存放要查询的值
printf("请输入要查询的数：");
scanf("%d", &val); // 输入要查询的数值
while (P != NULL&&P->Element != val) {
P = P->Next;
++num;
}
if (P != NULL)
printf("找到的节点为：%d", num + 1);
else
printf("找不到该节点");
printf("\n");
return P;
}
// 主函数
int main() {
PNode List = CreateList(); //创建一个指针，使其指向新创建的链表的头指针
TraverseList(List);
FindList(List);
return 0;
}运行
请输入节点个数：5
请输入第 1 个节点的数据：1
请输入第 2 个节点的数据：2
请输入第 3 个节点的数据：3
请输入第 4 个节点的数据：4
请输入第 5 个节点的数据：5
创建链表成功
遍历链表的值为：1 2 3 4 5
请输入要查询的数：2
找到的节点为：2请输入节点个数：4
请输入第 1 个节点的数据：20
请输入第 2 个节点的数据：30
请输入第 3 个节点的数据：40
请输入第 4 个节点的数据：50
创建链表成功
遍历链表的值为：20 30 40 50
请输入要查询的数：5
找不到该节点四.链表的插入操作
// 定义链表插入函数
// 在链表位置第pos节点前插入包含数据val的节点
void InsertList(PNode List, int pos, int val) {
int position = 0;
PNode P = List; // 定义节点p指向头节点
// 寻找pos节点的前驱结点
while (P != NULL&&position<pos - 1)
{
P = P->Next;
++position;
printf("检索节点中...：%d,%d\n", position,P->Element);
}
PNode Tmp = (PNode)malloc(sizeof(Node)); // 分配一个临时节点用来存储要插入的数据
if (Tmp == NULL)
{
printf("内存分配失败！");
exit(-1);
}
// 插入节点
Tmp->Element = val;
Tmp->Next = P->Next;
P->Next = Tmp;
}
// 主函数
int main() {
PNode List = CreateList(); //创建一个指针，使其指向新创建的链表的头指针
//TraverseList(List);
//FindList(List);
InsertList(List,3,60);
TraverseList(List);
return 0;
}请输入节点个数：5
请输入第 1 个节点的数据：20
请输入第 2 个节点的数据：10
请输入第 3 个节点的数据：30
请输入第 4 个节点的数据：40
请输入第 5 个节点的数据：4
创建链表成功
检索节点中...：1,20
检索节点中...：2,10
遍历链表的值为：20 10 60 30 40 4 五.链表的删除操作
删除整个链表操作
//定义删除整个链表函数
void DeleteTheList(PNode List) {
PNode P, Tmp;
P = List->Next; //定义指针P指向链表要删除的链表List的第一个点节点
List->Next = NULL;
while (P != NULL) {
Tmp = P->Next; //临时Tmp指向要删除的节点的下个节点
free(P); //释放指针P指向的节点
P = Tmp; //重新赋值
}
printf("删除链表成功！\n");
}
// 主函数
int main() {
PNode List = CreateList(); //创建一个指针，使其指向新创建的链表的头指针
//TraverseList(List);
//FindList(List);
//InsertList(List,3,60);
DeleteTheList(List);
TraverseList(List);
return 0;
}请输入节点个数：2
请输入第 1 个节点的数据：1
请输入第 2 个节点的数据：6
创建链表成功
删除链表成功！
遍历链表的值为：链表为空删除链表中的元素
// 定义删除链表元素函数
// 删除链表中的第pos节点
void DeleteList(PNode List, int pos) {
int position = 0;
PNode P = List; // 定义一个指针p指向链表头节点
// 寻找pos节点位置的前驱节点
while (P != NULL&&position < pos - 1) {
P = P->Next;
++position;
}
// 删除节点
PNode Tmp = P->Next; // 定义临时指针Tmp指向要删除的节点
P->Next = Tmp->Next; // 使要删除节点的前驱结点指向其后驱节点
free(Tmp); // 释放删除节点的内存空间，防止内存泄漏
Tmp = NULL; // 使q指向空指针，防止产生野指针
printf("删除节点成功！\n");
}
// 主函数
int main() {
PNode List = CreateList(); //创建一个指针，使其指向新创建的链表的头指针
//TraverseList(List);
//FindList(List);
//InsertList(List,3,60);
//DeleteTheList(List);
DeleteList(List,3);
TraverseList(List);
return 0;
}请输入节点个数：4
请输入第 1 个节点的数据：5
请输入第 2 个节点的数据：4
请输入第 3 个节点的数据：1
请输入第 4 个节点的数据：0
创建链表成功
删除节点成功！
遍历链表的值为：5 4 0 本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-04-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
