前言

参考

该部分知识参考于《数据结构（C语言版 第2版）》29 ~ 36页

注意

这里的ElemType是以Book类型的数据作为举例，如果需要更改可以自行改变！

🌈每一个清晨，都是世界对你说的最温柔的早安：ૢ(≧▽≦)و✨

---

目录

前言

1、单链表的基本概念

2、宏定义

3、链表数据内容进行定义

4、单链表的初始化

5、单链表的销毁

6、清空链表数据

7、求链表的长度

8、判断链表是否为空

9、按位查找

10、按值查找

11、单链表数据的插入

12、单链表数据的删除

13、创建单链表

13.1 头插法

13.2 尾插法 

14、遍历打印链表

15、总代码

测试结果

结语

---

1、单链表的基本概念

单链表（Singly Linked List）是链表中最简单的一种形式，它是一系列节点的集合，每个节点都包含两个部分：一是存储数据的数据域（Data Field），二是存储下一个节点地址的指针域（或称为链接域，Link Field）。单链表中的节点以单向方式连接，即每个节点只能顺序地访问其后续节点（如果有的话），而不能直接访问其前驱节点（除非使用额外的数据结构来辅助）

 我们废话不多时直接开始进行单链表代码的实现

2、宏定义

#include<iostream>
using namespace std;//初始化定义
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//Status是函数返回值类型，其值是函数结果状态代码
typedef int Status;

3、链表数据内容进行定义

//图书的数据结构
typedef struct
{char no[20];char name[50];float peice;
}Book;//单链表的结构
typedef struct LNode
{Book data;struct LNode* next;
}LNode,*LinkList;//声明链表
LinkList L;

这里我们解释一些内容

typedef struct LNode
{
...
}LNode,*LinkList;

对于这个代码，目的是定义线性表的单链表储存结构。

关键在于LNode与*LinkList

抽象出两个句子：
typedef struct Node LNode;
typedef struct Node* LinkList;

• LNode，参照typede的用法，可以得知LNode就是struct LNode的别名，即LNode==struct LNode；
• LinkList，是一个指向该结构体的的指针的别名。其实这个*应该不是跟着LinkList，而是跟在LNode后面的,即LNode* == LinkList。

可以通过这样一个例子可以这样来理解
typedef struct int ElemType
typedef struct int* ElemTypePtr
第一个是 定义整型变量的别名 ElemType
第二个是 定义指向整型变量的指针的别名 ElemTypePtr

LNode Node;//定义结构体变量Node；
LinkList Ptr;//定义指向结构体的指针变量Ptr；

4、单链表的初始化

//链表初始化
Status InitLink(LinkList &L)
{L = new LNode;  //让L指针指向新开辟的结点L->next = NULL;  //让L指针指向结点的next域置为NULLreturn OK;
}

5、单链表的销毁

//链表销毁
Status DestroyLink(LinkList& L)
{LinkList p;  //p作为中间变量用于释放结点while (L){p = L;L = L->next;delete p;}//循环结束后，L将置为NULLreturn OK;
}

6、清空链表数据

//清空链表
Status CleanLink(LinkList& L)
{LinkList p; //作为中间变量p = L->next;  //p指向该链表的首元节点while (p){L->next = p->next;delete p;p = L->next;}L->next = NULL; //最后需要将头指针置为NULL，否则会成为野指针return OK;
}

7、求链表的长度

//求表长
int GetLengthLink(LinkList L)
{LinkList p;p = L->next;int count = 0;//用于计数while (p){++count;p = p->next;}return count;
}

8、判断链表是否为空

//判空
Status EmptyLink(LinkList L)
{if (L->next)return ERROR;  //不为空elsereturn OK;     //为空
}

9、按位查找

//按照序号进行查找
Status GetElemLink(LinkList L, int i, Book& e)
{LinkList p;p = L->next;int j = 1;while (p && j < i){p = p->next;++j;}if (!p || j > i){return ERROR;  //如果没找到返回0}else{e = p->data;  //用引用返回得到的参数数据return OK;}
}

10、按值查找

//按照元素进行查找
LNode* LocateElem(LinkList L, Book e)
{LinkList p;p = L->next;while (p && p->data.no != e.no)  //这里按照书号查找，基本可以保证唯一性{p = p->next; }return p;   //查找到后返回e元素的结点地址p，查找失败后返回为NULL
}

11、单链表数据的插入

//链表插入
//将e节点元素插入到i节点的前面，则需要移动到i-1的位置
Status InsertLink(LinkList& L, int i, Book e)
{LinkList p;p = L;int j = 0;while (p && j < i - 1){++j;p = p->next;}if (!p && j > i - 1){return ERROR;}//该情况出现，即插入位置非法//循环结束后，已经移动到了i节点的前一个位置，进行尾插即可LinkList s = new LNode; //为即将要插入位置开辟一个结点s->data = e;s->next = p->next;//首先进行尾部连接p->next = s;//随后进行头部连接return OK;
}

 

12、单链表数据的删除

//链表删除某个结点
Status DeleteLink(LinkList& L, int i, Book e)
{LinkList p;p = L;int j = 0;while (p && j < i - 1){p = p->next;j++;}//循环结束后，p会指向要删除节点的前驱节点if (!(p->next) || j > i - 1){return ERROR;}//要判断位置是否非法//进行删除LinkList q;q = p->next;    //临时保存被删除节点的地址以备后续释放p->next = q->next;  //改变被删除节点的前驱节点的指针域e = q->data;  //删除时拿出来被删除节点的数据delete q;return OK;
}

 

13、创建单链表

13.1 头插法

//头插法
void CreatLink_F(LinkList &L, int n)
{L = new LNode;L->next = NULL;for (int i = 0; i < n; i++){LinkList p = new LNode;cout << "依次输入书的书号，书名和价格" << endl;cin >> p->data.no;cin >> p->data.name;cin >> p->data.peice;p->next = L->next;L->next = p;}
}

13.2 尾插法 

//尾插法
void CreatLink_L(LinkList& L, int n)
{L = new LNode;L->next = NULL;LinkList r = L;for (int i = 0; i < n; i++){LinkList p = new LNode;cout << "依次输入书的书号，书名和价格" << endl;cin >> p->data.no;cin >> p->data.name;cin >> p->data.peice;p->next = NULL;r = p;}
}

14、遍历打印链表

//遍历打印链表
void TraverseList(LinkList L)
{if (L == nullptr || L->next == nullptr) {cout << "链表为空" << endl;return;}LinkList p;p = L->next;while (p){cout << p->data.no << "  " << p->data.name << "  " << p->data.peice << endl;p = p->next;}
}

15、总代码

#include<iostream>
using namespace std;//初始化定义
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//Status是函数返回值类型，其值是函数结果状态代码
typedef int Status;//图书的数据结构
typedef struct
{char no[20];char name[50];float peice;
}Book;//单链表的结构
typedef struct LNode
{Book data;struct LNode* next;
}LNode,*LinkList;//声明链表
LinkList L;//链表初始化
Status InitLink(LinkList &L)
{L = new LNode;L->next = NULL;return OK;
}//链表销毁
Status DestroyLink(LinkList& L)
{LinkList p;while (L){p = L;L = L->next;delete p;}//循环结束后，L将置为NULLreturn OK;
}//清空链表
Status CleanLink(LinkList& L)
{LinkList p; //作为中间变量p = L->next;  //p指向该链表的首元节点while (p){L->next = p->next;delete p;p = L->next;}L->next = NULL; //最后需要将头指针置为NULL，否则会成为野指针return OK;
}//求表长
int GetLengthLink(LinkList L)
{LinkList p;p = L->next;int count = 0;//用于计数while (p){++count;p = p->next;}return count;
}//判空
Status EmptyLink(LinkList L)
{if (L->next)return ERROR;  //不为空elsereturn OK;     //为空
}//按照序号进行查找
Status GetElemLink(LinkList L, int i, Book& e)
{LinkList p;p = L->next;int j = 1;while (p && j < i){p = p->next;++j;}if (!p || j > i){return ERROR;  //如果没找到返回0}else{e = p->data;  //用引用返回得到的参数数据return OK;}
}//按照元素进行查找
LNode* LocateElem(LinkList L, Book e)
{LinkList p;p = L->next;while (p && p->data.no != e.no){p = p->next; }return p;   //查找到后返回e元素的结点地址p，查找失败后返回为NULL
}//链表插入
//将e节点元素插入到i节点的前面，则需要移动到i-1的位置
Status InsertLink(LinkList& L, int i, Book e)
{LinkList p;p = L;int j = 0;while (p && j < i - 1){++j;p = p->next;}if (!p && j > i - 1){return ERROR;}//该情况出现，即插入位置非法//循环结束后，已经移动到了i节点的前一个位置，进行尾插即可LinkList s = new LNode; //为即将要插入位置开辟一个结点s->data = e;s->next = p->next;//首先进行尾部连接p->next = s;//随后进行头部连接return OK;
}//链表删除某个结点
Status DeleteLink(LinkList& L, int i, Book e)
{LinkList p;p = L;int j = 0;while (p && j < i - 1){p = p->next;j++;}//循环结束后，p会指向要删除节点的前驱节点if (!(p->next) || j > i - 1){return ERROR;}//要判断位置是否非法//进行删除LinkList q;q = p->next;    //临时保存被删除节点的地址以备后续释放p->next = q->next;  //改变被删除节点的前驱节点的指针域e = q->data;  //删除时拿出来被删除节点的数据delete q;return OK;
}//创建单链表
//头插法
void CreatLink_F(LinkList &L, int n)
{L = new LNode;L->next = NULL;for (int i = 0; i < n; i++){LinkList p = new LNode;cout << "依次输入书的书号，书名和价格" << endl;cin >> p->data.no;cin >> p->data.name;cin >> p->data.peice;p->next = L->next;L->next = p;}
}
//尾插法
void CreatLink_L(LinkList& L, int n)
{L = new LNode;L->next = NULL;LinkList r = L;for (int i = 0; i < n; i++){LinkList p = new LNode;cout << "依次输入书的书号，书名和价格" << endl;cin >> p->data.no;cin >> p->data.name;cin >> p->data.peice;p->next = NULL;r = p;}
}//遍历打印链表
void TraverseList(LinkList L)
{if (L == nullptr || L->next == nullptr) {cout << "链表为空" << endl;return;}LinkList p;p = L->next;while (p){cout << p->data.no << "  " << p->data.name << "  " << p->data.peice << endl;p = p->next;}
}int main()
{cout << "初始化创建链表时需要输入3个数据" << endl;CreatLink_F(L, 3);TraverseList(L);
}

测试结果

---

结语

该部分内容，大家不要手懒，勤思考勤练习，一定可以学会的，加油！