描述：
一个完整的链表，用C语言写成（使用了C++中的引用&知识）。
可实现链表的增删改查、清空、求长度等功能。
链表中节点的数据域类型为char型。
参考：
青岛大学-王卓 数据结构课：https://www.bilibili.com/read/cv3285768
代码地址：Github: https://github.com/VicentWYS/Datadtructure--LinkList
项目结构：
main.cpp:
#include <iostream> #include<stdio.h> #include<stdlib.h> #include "function_for_LinkList.h" using namespace std; int main() { printf("测试单链表： "); testLinkList(); return 0; }
function_for_LinkList.h:
#ifndef FUNCTION_FOR_LINKLIST_H_INCLUDED #define FUNCTION_FOR_LINKLIST_H_INCLUDED //函数结果状态代码 #define OK '1' #define ERROR '0' typedef char ElemType; //节点 typedef struct Lnode{ ElemType data; //数据域 struct Lnode *next; //指针域 }Lnode, *LinkList; //单链表初始化 void InitList_L(LinkList &L); //判断链表是否为空(空表) int ListEmpty(LinkList L); //销毁单链表 void DestroyList_L(LinkList &L); //清空链表,但保留头节点和头指针 void ClearList(LinkList &L); //求表长 int ListLength_L(LinkList L); //取值：取单链表中第i个元素的内容 ElemType GetElem_L(LinkList L, int i); //按值查找 //根据指定数据获取改数据(第一次出现)所在位置(地址) Lnode *LocateElem_L(LinkList L, ElemType e); //按值查找2 //在链表L中查找值为e的数据元素的位置序号 //若查找失败，返回 0 int LocateElem_index_L(LinkList L, ElemType e); //插入元素 int ListInsert_L(LinkList &L, int i, ElemType e); //删除第i个节点 //首先定位到第i-1个节点 int ListDelete_L(LinkList &L, int i); //建立单链表：头插法 void CreateList_H(LinkList &L, ElemType e); //尾插法 //一次插入一个节点 void CreateList_R(LinkList &L, ElemType e); //展示单链表 void DisList(LinkList L); //测试 void testLinkList(); #endif // FUNCTION_FOR_LINKLIST_H_INCLUDED
function_for_LinkList.cpp:
#include<stdio.h> #include<stdlib.h> #include <iostream> #include "function_for_LinkList.h" //单链表初始化 void InitList_L(LinkList &L){ //&指引用型变量 L=(LinkList) malloc (sizeof(Lnode)); L->next = NULL; } //判断链表是否为空(空表) int ListEmpty(LinkList L){ //0:非空, 1:空 if(L->next != NULL){ //非空 return 0; }else{ return 1; //链表为空 } } //销毁单链表 void DestroyList_L(LinkList &L){ //从头到尾逐个删除,彻底消灭所有节点 Lnode *p; while(L){ //L非空 p = L; //p指向当前节点 L = L->next; //L指向下一节点 free(p); //销毁当前节点 } } //清空链表,但保留头节点和头指针 void ClearList(LinkList &L){ Lnode *p, *q; p = L->next; //p指向首元节点 while(p != NULL){ q = p->next; //q指向第二节点 free(p); p = q; }//节点清空完毕 L->next = NULL; //将头节点next指为空 } //求表长 int ListLength_L(LinkList L){ //从首元结点开始，依次计数所有节点 LinkList p; p= L->next; //p指向首元结点 int length=0; while(p != NULL){ //p非空 length++; //遍历单链表，统计节点数 p = p->next; //指向下一节点 } return length; } //取值：取单链表中第i个元素的内容 /* 从第一个节点顺链扫描，用指针p指向当前扫描到的节点, p初值：p=L->next; 变量 j 作为计数器，累计当前扫描过的节点数，j 初值为 1； 当 p 指向下一个节点时，j 加1； j == i 时，p 所指的节点就是要找的第 i 个节点； */ ElemType GetElem_L(LinkList L, int i){ //获取线性表L中某个元素的内容，通过变量e返回 Lnode *p; //游标p，指向当前节点 int j=1; //计数器 p = L->next; //初始化 while(p && j<i){ //向后扫描，直到p指向第i个元素或p为空 p=p->next; //理想情况，在j = i-1时，符合while条件，p指向第i个节点，j++变为i，此时再判断发现 j<i 不成立，所以跳出while循环， //跳出后，此时j = i,p指向的正好是第 i 个节点 j++; } if(!p || j>i){ return ERROR; //找不到元素，返回'0'，退出 } return p->data; //找到元素，返回其数据域 } //按值查找 //根据指定数据获取改数据(第一次出现)所在位置(地址) Lnode *LocateElem_L(LinkList L, ElemType e){ //在链表L中查找值为e的数据元素 //若找到，则返回L中值为e的数据元素的地址， //若找不到，则返回NULL LinkList p; p = L->next;//定义节点指针，指向首元节点 while(p && p->data!=e){ p=p->next; //当前节点不是要找的，游标后移 } return p; } //按值查找2 //在链表L中查找值为e的数据元素的位置序号 //若查找失败，返回 0 int LocateElem_index_L(LinkList L, ElemType e){ LinkList p; p=L->next; //定义指针p指向首元结点 int j=1; //声明计数器，保存所找位置序号 while(p && p->data!=e){ p=p->next; //当前节点不符合，则游标后移 j++; //计数器加1 } if(p != NULL){ //游标非空，表示在链表中找到了元素 return j; //返回所找元素位置序号 }else{ return 0; //否则， 没找到目标元素 } } //插入元素 //在第i个节点前插入值为e的新节点 //即：找到第 i-1 个节点，把待插入元素放到其后面 int ListInsert_L(LinkList &L, int i, ElemType e){ Lnode *p= L; //游标 int j=0; //计数器 while(p != NULL && j<i-1){ //寻找第 i-1 个节点 p=p->next; j++; } if(p==NULL){ //如果游标已经到了链表尾部（还没找到） return 0; //定位失败，返回0 }else{ //游标p指向了第i-1个节点 Lnode *newPoint = (LinkList)malloc(sizeof(Lnode)); //创建新节点 newPoint->data = e; newPoint->next = p->next; p->next = newPoint; return 1; //元素插入完毕，返回1 } } //删除第i个节点 //首先定位到第i-1个节点 int ListDelete_L(LinkList &L, int i){ LinkList p = L->next; //游标指向首元节点 int j=1; while(p!=NULL && j<i-1){ p=p->next; //游标后移 j++; //计数器自增 } if(p->next == NULL || j>i-1){ //错误情况：要找的i大于链表的表长，游标移动到了链尾也找不到 return 0; } //若已经定位到第i-1个节点处 LinkList q = p->next; //q指向第i个节点 p->next = q->next; free(q); //释放被删除节点的空间 return 1; } //建立单链表：头插法 //头插法插入顺序是倒序的 /* 从一个空表开始，读入数据 生成新节点，将读入的数据放到新节点的数据域中 从后到前逐个将节点放到链表头部 */ void CreateList_H(LinkList &L, ElemType e){ Lnode *p; p = (LinkList)malloc(sizeof(Lnode)); //创建新节点 p->data = e; p->next = NULL; //头插法核心代码 p->next = L->next; L->next = p; } //尾插法 //一次插入一个节点 void CreateList_R(LinkList &L, ElemType e){ //&指引用型变量 LinkList p = L; //游标，先指向头节点 LinkList newPoint = (LinkList)malloc(sizeof(Lnode));//建立新节点 newPoint->data = e; newPoint->next = NULL; while(p->next != NULL){ //游标找到链表最后一个节点 p=p->next; } p->next = newPoint; } //展示单链表 void DisList(LinkList L){ Lnode *p = L->next; while(p!=NULL){ printf("%c ", p->data); p=p->next; } printf(" "); } //测试 void testLinkList(){ LinkList L; //指向结构体的指针 ElemType e; //数据域 printf("初始化单链表： "); InitList_L(L); printf("测试头插法插入 a,b,c,d "); CreateList_H(L, 'd'); CreateList_H(L, 'c'); CreateList_H(L, 'b'); CreateList_H(L, 'a'); printf("输出单链表： "); DisList(L); printf("表长：%d ", ListLength_L(L)); // printf("测试尾插法插入： "); // CreateList_R(L, 'a'); // CreateList_R(L, 'b'); // CreateList_R(L, 'c'); // CreateList_R(L, 'd'); // printf("输出单链表： "); // DisList(L); // printf("表长：%d ", ListLength_L(L)); printf("判断链表是否为空表： "); printf("%d ", ListEmpty(L)); printf("清空链表： "); ClearList(L); printf("打印链表元素： "); DisList(L); printf("表长：%d ", ListLength_L(L)); printf("判断链表是否为空表： "); printf("%d ", ListEmpty(L)); printf("添加新元素： "); CreateList_H(L, 'o'); CreateList_H(L, 'p'); CreateList_H(L, 'q'); CreateList_H(L, 'r'); CreateList_H(L, 's'); printf("销毁链表： "); DestroyList_L(L); printf("打印链表元素： "); DisList(L); printf("表长：%d ", ListLength_L(L)); printf("判断链表是否为空表： "); printf("%d ", ListEmpty(L)); // printf("查找第1个位置的值：%c ", GetElem_L(L, 1)); // printf("查找第2个位置的值：%c ", GetElem_L(L, 2)); // printf("查找第3个位置的值：%c ", GetElem_L(L, 3)); // printf("查找第4个位置的值：%c ", GetElem_L(L, 4)); // printf("查找第10个位置的值：%c ", GetElem_L(L, 10)); // printf("查找a的位置：%d ", LocateElem_index_L(L, 'a')); // printf("查找b的位置：%d ", LocateElem_index_L(L, 'b')); // printf("查找c的位置：%d ", LocateElem_index_L(L, 'c')); // printf("查找d的位置：%d ", LocateElem_index_L(L, 'd')); // printf("在第3个元素前插入新元素'h',结果：%d ", ListInsert_L(L, 3, 'h')); // printf("打印链表： "); // DisList(L); // // printf("在第10个元素前插入新元素'y',结果：%d ", ListInsert_L(L, 10, 'y')); // printf("打印链表： "); // DisList(L); // // printf("删除第4个节点的元素：%d ", ListDelete_L(L, 4)); // DisList(L); }
测试结果：
