实现思想
单链表是一种基本的数据结构，它由一系列节点组成，每个节点包含两部分：数据部分和指向下一个节点的指针。单链表的特点是每个节点只包含一个指向下一个节点的指针，因此只能从表头向表尾遍历。下面是单链表的一些基本特性和操作：
- 线性结构：数据元素之间是一对一的关系。
- 动态数据结构：在运行时可以增加或删除节点。
- 非连续性：数据元素在内存中不是连续存储的，每个节点通过指针指向下一个节点。
- 插入和删除节点：在链表的指定位置插入新节点，删除链表中的指定节点。
- 遍历链表：从表头开始，通过每个节点的指针访问下一个节点。
- 查找节点：查找链表中特定值的节点。
- 反转链表：将链表的节点顺序反转
包含头文件
#include<stdio.h>
#include<stdlib.h>结点设计
#define Initsize 10
typedef int Elemtype;
typedef struct {
Elemtype data[Initsize]; //定义数组data大小为Initsize，存储的是静态顺序表的数据
Elemtype* next; //定义next为Elemtype类型的指针，用于动态扩展顺序表的大小
int Maxsize; //定义变量Maxsize存储顺序表的大小
int lenth; //定义变量lenth存储顺序表所存储的数据个数
}SqlList;
/*以上封装等同于以下代码:
typedef struct LNode LNode;
typeddf struct LNode* LinkList;
*/接口函数定义
bool InitList(LinkList& A); //定义函数InitList用于初始化不带头结点的单链表
bool CheckList(LinkList& A); //定义函数CheckList用于查看不带头结点的单链表是否为空
bool InitNodeList(LinkList& A); //定义函数InitNodeList用于初始化带头结点的单链表
bool CheckNodeList(LinkList& A); //定义函数CheckNodeList用于查看带头结点的单链表是否为空
bool CheckOrder(LinkList& A,int len);//定义函数CheckOrder用于遍历链表查找结点并判空
bool InsertNextNode(LNode* A, Elemtype X);//定义函数InsertNextNode用于在指定结点进行后插操作
bool ListDelete(LinkList& A, int len, Elemtype X);//定义函数ListDelete用于按位序删除数据
bool NodeDelete(LNode* A); //定义函数NodeDelete用于指定结点删除数据
LNode* GetElem(LinkList& A,int len);//定义函数GetElem用于获取结点元素
LNode* LocateElem(LinkList& A, Elemtype X);//定义函数LocateElem用于按值查找结点
int ListLength(LinkList& A); //定义函数ListLenth用于查看单链表的长度
bool LoopCheckList(LinkList& A); //定义函数LoopCheckList用于循环遍历输出单链表中的元素
//定义函数ListNodeInsert用于在带头结点单链表中执行按位序插入
bool ListNodeInsert(LinkList& A,int len,Elemtype X);
//定义函数ListInsert用于在不带头结点的单链表中执行按位序插入
bool ListInsert(LinkList& A, int len, Elemtype X);
//定义函数InsertPriorNode用于在指定结点进行前插操作
bool InsertPriorNode(LNode* A, Elemtype X);
//定义函数NextManyElemList用于使用尾插法建立多个元素的单链表
bool NextManyElemList(LinkList& A);
//定义函数PrioeManyElemList用于使用头插法建立多个元素的单链表
bool PriorManyElemList(LinkList& A);
/*函数中带有&的形参意义解读:
属于CPP文件中的引用，指将指针另取其名，使用时可以引用指针(类似typedef函数)
如:LinkList& A ——>将传入的LihkList参数另取其名为A(调用A等同于调用该实参)
*/接口函数实现
bool LoopCheckList(LinkList& A) {//定义函数LoopCheckList用于循环遍历输出单链表中的元素
LNode* Q = A->next;
printf("单链表中所含的数据为:");
while (Q!=NULL) { //遍历输出单链表
printf(" %d", Q->data);
Q = Q->next;
}
return true;
}
bool PriorManyElemList(LinkList& A){
//定义函数PrioeManyElemList用于使用头插法建立多个元素的单链表
int len, J = 0;
LNode* Q = A;
Elemtype X;
printf("请输入要输入的数据个数:");
scanf_s("%d", &len);
printf("请输入数据");
while (J < len) {
scanf_s("%d", &X);
InsertPriorNode(Q, X);//调用函数InsertPriorNode用于在指定结点进行前插操作
printf("\n");
J++;
}
printf("使用头插法建立大小为%d的单链表成功", len);
return true;
}
bool NextManyElemList(LinkList& A) {
//定义函数NextManyElemList用于使用尾插法建立多个元素的单链表
int len,J=0;
LNode* Q = A;
Elemtype X;
printf("请输入要输入的数据个数:");
scanf_s("%d", &len);
printf("请输入数据");
while (J < len) {
scanf_s("%d", &X);
InsertNextNode(Q, X);//调用函数InsertNextNode用于在指定结点进行后插操作
Q = Q->next;
printf("\n");
J++;
}
printf("使用尾插法建立大小为%d的单链表成功", len);
return false;
}
int ListLength(LinkList& A) {//定义函数ListLenth用于查看单链表的长度
LNode* Q = A; //定义LNode指针指向头指针所含的指针域
int len = 0; //定义变量len存储单链表长度
while (Q->next != NULL) {//遍历单链表
Q = Q->next;
len++;
}
return len;
}
LNode* LocateElem(LinkList& A,Elemtype X) { //定义函数LocateElem用于按值查找结点
LNode* Q = A->next; //定义LNode指针指向头指针所含的指针域
while (Q != NULL && Q->data != X) { //遍历单链表，寻找数据域为X的结点
Q = Q->next;
}
if (Q == NULL) { //判断单链表中是否存在满足条件的结点
printf("不存在数据域为%d的结点", X);
}
else {
return Q;
}
}
LNode* GetElem(LinkList& A,int len) { //定义函数GetElem用于获取结点元素
if (len < 0) { //判断传入的结点是否有误
printf("输入的结点次序有误");
return A;
}
LNode* Q = A; //定义LNode指针指向传入的头指针
int J = 0;
while (Q != NULL && J < len) { //遍历单链表寻找传入次序的结点
Q = Q->next;
J++;
}
return Q;
}
bool NodeDelete(LNode* A) { //定义函数NodeDelete用于指定结点删除数据
if (A == NULL) {
printf("传入的结点不存在");
return false;
}
if (A->next == NULL) {
printf("传入的结点为最后一个结点，需要遍历单链表才能删除该结点");
return false;
}
LNode* Q = A->next;
A->data == Q->data;
A->next = Q->next;
free(Q);
printf("传入的结点已删除");
return true;
}
bool ListDelete(LinkList& A, int len, Elemtype X) {//定义函数ListDelete用于按位序删除数据
LNode* Q = A; //定义一个LNode指针Q指向传入的单链表A
if (CheckOrder(Q, len)) { //调用函数CheckOrder寻找传入次序的前驱结点
if (Q->next == NULL) { //查看其传入的结点的前驱结点里的指针域next是否为空
printf("输入的结点不存在");
return false;
}
LNode* W = Q ->next; //定义一个LNdoe指针W指向前驱结点的指针域next
X = W->data; //获取删除的结点的数据域data
Q->next = W->next; //更新前驱结点的数据域next
printf("指定次序的单链表已删除，其删除的数据域为:%d", X);
free(W); //使用函数free释放删除的结点空间
return true;
}
else {
return false;
}
}
bool InsertPriorNode(LNode* A, Elemtype X) {
//定义函数InsertPriorNode用于在指定结点进行前插操作
if (CheckList(A)) { //判断插入的结点是否为空
printf("传入的结点不存在");
return false;
}
LNode* Q = (LNode*)malloc(sizeof(LNode)); //向计算机申请一个大小为LNode的空间
if (CheckList(Q)) { //判断使用malloc1函数是否申请到空间
printf("计算机内存不足，无法分配空间创建链表插入");
return false;
}
Q->data = X; //进行单链表的前插操作，并更新数据
Q->next = A->next;
A->next = Q;
printf("在指定结点前执行前插操作成功，其数据域保存的数据为%d", X);
return true;
}
bool InsertNextNode(LNode *A, Elemtype X) {//定义函数InsertNextNode用于在指定结点进行后插入
if (CheckList(A)) { //判断插入的结点是否为空
printf("传入的结点不存在");
return false;
}
LNode* Q = (LNode*)malloc(sizeof(LNode)); //向计算机申请一个大小为LNode的空间
if (CheckList(Q)) { //判断使用malloc1函数是否申请到空间
printf("计算机内存不足，无法分配空间创建链表插入");
return false;
}
Q->next = A->next; //进行单链表的后插操作，并更新数据
A->next = Q;
Q->data = X;
printf("在指定结点后执行后插入成功，其数据域保存的数据为%d", X);
return true;
}
bool ListInsert(LinkList& A, int len, Elemtype X) {
//定义函数ListInsert用于在不带头结点的单链表中执行按位序插入
if (len == 1) { //传入的次序为1的情况
LNode* W = (LNode*)malloc(sizeof(LNode));
W->next = A;
W->data = X;
A = W; //更新头指针指向的地址
printf("在次序%d中插入单链表成功，其存储的数据为%d", len, X);
return true;
}
ListNodeInsert(A,len,X); //调用函数ListNodeInsert执行后插操作
}
bool ListNodeInsert(LinkList& A, int len, Elemtype X) {
//定义函数ListNodeInsert用于在单链表中执行按位序插入
LNode* Q = A; //定义一个LNode指针Q指向传入的单链表A
if (CheckOrder(Q, len)) { //调用函数CheckOrder寻找传入次序的前驱结点
LNode* W = (LNode*)malloc(sizeof(LNode)); //定义LNode指针W指向新开辟的大小为LNode的空间
W->data = X; //更新单链表数据
W->next = Q->next;
Q->next = W;
printf("在次序%d中插入单链表成功，其存储的数据为%d", len, X);
return true;
}
else {
return false;
}
}
bool CheckOrder(LinkList& A, int len) {//定义函数CheckOrder用于遍历链表查找结点并判空
if (len < 1) { //判断传入的次序是否合法
printf("传入的次序过小");
return false;
}
LNode* W = A; //定义一个LNode型的指针存储传入的头结点地址
int J = 0; //定义变量J用于循环便利单链表
while (W != NULL && J < len - 1) { //遍历单链表，寻找满足该次序的前驱结点
W = W->next;
J++;
}
if (W == NULL) { //判断传入的次序是否合法
printf("传入的次序过大");
return false;
}
A = W; //改变传入的单链表A指向的地址
}
bool CheckNodeList(LinkList& A) {//定义函数CheckNodeList用于查看带头结点的单链表是否为空
return (A->next == NULL);
}
bool InitNodeList(LinkList& A) { //定义函数InirNodeList用于初始化带头结点的单链表
A = (LNode*)malloc(sizeof(LNode)); //使用函数malloc向计算机申请一片大小为LNode类型的空间，将其地址强转为LNode型
if (CheckList(A)) { //判断申请的空间是否成功
printf("计算机内存不足，初始化带头结点的单链表失败");
return false;
}
A->next = NULL; //将头结点所含的指针域next值指向空(头结点不存储数据域data)
printf("初始化带头结点的单链表成功");
return true;
}
bool CheckList(LinkList& A) {//定义函数CheckList用于查看链表是否为空
return (A == NULL);
}
bool InitList(LinkList& A) {//定义函数InitList用于初始化不带头结点的单链表
A = NULL; //将传入的单链表A赋值为NULL，意为课表
printf("初始化不带头结点的单链表成功\n");
return true;
}
