前言
上次简略的写了下有关于顺序表的相关知识点，现在又有了一些时间，就把剩下的单链表也出个简单易懂的教程吧，其实关于单链表，我个人觉得实用性比顺序表大很多，因为它能够灵活的实现数据的插入和删除等等，但是相对的写法也是比顺序表难一些，接下来就拿关键的部分来简单介绍吧，这次我也在后面补充上了我之前上课做的有关于单链表基本功能操作菜单，希望能给大家带来一定的帮助！
单链表的头文件及其结构体
单链表的结构体与顺序表有所不同，单链表的一个单位分为data域（文本域）和 指针域，而顺序表的则是有与存储相关的数组和数组大小和其表长。
#include <iostream>
#include <cstdio>
#include <malloc.h>
using namespace std;
typedef struct LNode
{
char data;
struct LNode* next; //指向后继结点
} LinkList; //单链表结点类型
单链表的空间开辟
这里也是和之前去顺序表差不多，使用了经典的malloc函数来开辟存储空间。
//开辟空间
void InitList(LinkList*& L)
{
L = (LinkList*)malloc(sizeof(LinkList)); //创建头结点
L->next = NULL; //单链表置为空表
}
单链表的数据插入
//插入数据
bool ListInsert(LinkList*& L, int i, char e)
{
int j = 0;
if (i <= 0) return false; //i错误返回假
LinkList* p = L, * s; //p指向头结点,j置为0(即头结点的序号为0)
while (j < i - 1 && p != NULL) //查找第i-1个结点p
{
j++;
p = p->next;
}
if (p == NULL) //未找到第i-1个结点,返回false
return false;
else //找到第i-1个结点p,插入新结点并返回true
{
s = (LinkList*)malloc(sizeof(LinkList));
s->data = e; //创建新结点s,其data域置为e
s->next = p->next; //将结点s插入到结点p之后
p->next = s;
return true;
}
}
单链表的插入操作和顺序表的插入操作有所不同，是先开辟好一个结点空间用来存储要插入的值（步骤1），然后将要开辟出来的s结点的指针域指向所要插入结点位置的下个结点的data域（步骤2），在将要插入位置的结点的指针域指向新开辟的s结点的data域（步骤3）,入下图：
单链表的数据删除
//删除数据
bool ListDelete(LinkList*& L, int i, char& e)
{
int j = 0;
if (i <= 0) return false; //i错误返回假
LinkList* p = L, * q; //p指向头结点,j置为0(即头结点的序号为0)
while (j < i - 1 && p != NULL) //查找第i-1个结点
{
j++;
p = p->next;
}
if (p == NULL) //未找到第i-1个结点,返回false
return false;
else //找到第i-1个结点p
{
q = p->next; //q指向第i个结点
if (q == NULL) //若不存在第i个结点,返回false
return false;
e = q->data;
p->next = q->next; //从单链表中删除q结点
free(q); //释放q结点
return true; //返回true表示成功删除第i个结点
}
}
经过循环后，p指向了所要删除结点的上一个结点（步骤1），q指向了p->next的结点（步骤2），将q所指向的data域的值赋值给e（步骤3）,将p结点的指针域指向q结点指针域所指向的结点（步骤4）,用free（）函数释放掉结点q。入下图：
关于我写的一个人机互动的单链表功能菜单
上面我就简单的说明了插入和删除功能，剩下的功能函数我写在了这个功能菜单下：
#include <iostream>
#include <cstdio>
#include <malloc.h>
using namespace std;
typedef struct LNode
{
char data;
struct LNode* next; //指向后继结点
} LinkList; //单链表结点类型
//开辟空间
void InitList(LinkList*& L)
{
L = (LinkList*)malloc(sizeof(LinkList)); //创建头结点
L->next = NULL; //单链表置为空表
}
//销毁链表
void DestroyList(LinkList*& L)
{
LinkList* p = L, * q = p->next;
while (q != NULL)
{
free(p);
p = q;
q = p->next;
}
free(p);
}
//判断是否为空表
bool ListEmpty(LinkList* L)
{
return(L->next == NULL);
}
//求链表长度
int ListLength(LinkList* L)
{
LinkList* p = L; //p指向头结点,n置为0(即头结点的序号为0)
int i = 0;
while (p->next != NULL)
{
i++;
p = p->next;
}
return(i); //循环结束返回链表长度的值
}
//输出单链表
void DispList(LinkList* L)
{
LinkList* p = L->next; //p指向首结点
while (p != NULL)
{
cout << p->data << " "; //p不为NULL,输出p结点的data域
p = p->next; //p移向下一个结点
}
cout << endl;
}
//获取元素位置
bool GetElem(LinkList* L, int i, char& e)
{
int j = 0;
if (i <= 0) return false; //i错误返回假
LinkList* p = L; //p指向头结点,j置为0(即头结点的序号为0)
while (j < i && p != NULL) //找第i个结点p
{
j++;
p = p->next;
}
if (p == NULL) //不存在第i个数据结点,返回false
{
return false;
}
else //存在第i个数据结点,返回true
{
e = p->data;
return true;
}
}
//用元素查找位置
int LocateElem(LinkList* L, char e)
{
int i = 1;
LinkList* p = L->next; //p指向首结点,i置为1(即首结点的序号为1)
while (p != NULL && p->data != e) //查找data值为e的结点,其序号为i
{
p = p->next;
i++;
}
if (p == NULL) //不存在值为e的结点,返回0
return(0);
else //存在值为e的结点,返回其逻辑序号i
return(i);
}
//插入数据
bool ListInsert(LinkList*& L, int i, char e)
{
int j = 0;
if (i <= 0) return false; //i错误返回假
LinkList* p = L, * s; //p指向头结点,j置为0(即头结点的序号为0)
while (j < i - 1 && p != NULL) //查找第i-1个结点p
{
j++;
p = p->next;
}
if (p == NULL) //未找到第i-1个结点,返回false
return false;
else //找到第i-1个结点p,插入新结点并返回true
{
s = (LinkList*)malloc(sizeof(LinkList));
s->data = e; //创建新结点s,其data域置为e
s->next = p->next; //将结点s插入到结点p之后
p->next = s;
return true;
}
}
//删除数据
bool ListDelete(LinkList*& L, int i, char& e)
{
int j = 0;
if (i <= 0) return false; //i错误返回假
LinkList* p = L, * q; //p指向头结点,j置为0(即头结点的序号为0)
while (j < i - 1 && p != NULL) //查找第i-1个结点
{
j++;
p = p->next;
}
if (p == NULL) //未找到第i-1个结点,返回false
return false;
else //找到第i-1个结点p
{
q = p->next; //q指向第i个结点
if (q == NULL) //若不存在第i个结点,返回false
return false;
e = q->data;
p->next = q->next; //从单链表中删除q结点
free(q); //释放q结点
return true; //返回true表示成功删除第i个结点
}
}
void menu() {
cout << "**************单链表的基本运算**************" << endl;
cout << "1.初始化单链表" << endl;
cout << "2.插入元素" << endl;
cout << "3.删除元素" << endl;
cout << "4.按序位查找单链表元素" << endl;
cout << "5.查找元素在单链表的位置" << endl;
cout << "6.单链表长度" << endl;
cout << "7.单链表是否为空" << endl;
cout << "8.输出单链表" << endl;
cout << "9.释放单链表" << endl;
}
int main()
{
LinkList* L;
int* l;
char e, a, b, c(0);
int k(1), m, x, y, z;
InitList(L);
menu();
while (k) {
cout << "请输入1--9进行运算" << endl;
cin >> m;
switch (m)
{
case 1: {
InitList(L);
cout << "初始化单链表成功" << endl;
break;
}
case 2: {
cout << "请输入你要插入的位置和元素" << endl;
cin >> x;
cin >> a;
ListInsert(L, x, a);
cout << "插入成功" << endl;
break;
}
case 3: {
cout << "请输入你要删除的位置和元素" << endl;
cin >> y;
cin >> b;
ListDelete(L, y, b);
cout << "删除成功" << endl;
break;
}
case 4: {
cout << "请输入你要查找单链表的位置：" << endl;
cin >> z;
GetElem(L, z, e);
cout << "单链表L的第" << z << "个元素 = " << e << endl;
break;
}
case 5: {
cout << "请输入你要查找元素的名称：" << endl;
cin >> e;
cout << "元素" << e << "的位置 = " << LocateElem(L, e) << endl;
break;
}
case 6: {
cout << "单链表长度=" << ListLength(L) << endl;
break;
}
case 7: {
cout << "单链表为" << (ListEmpty(L) ? "空" : "非空") << endl;
break;
}
case 8: {
cout << "单链表为：" << endl;
DispList(L);
break;
}
case 9: {
cout << "释放单链表" << endl;
DestroyList(L);
break;
}
default:
cout << "请问需要继续运算嘛？（ y(1)/n(0) ）" << endl;
cin >> k;
if (!k) {
cout << "感谢你的使用 (O v O) !" << endl;
}
break;
}
}
return 0;
}
运行图如下：
总结
以上就是我对学习完链表后的对其知识点的简单认知，有错的地方可以评论区告知我一下，希望的认知能给刚刚学习链表的同学们带来一些帮助！！！
如果有需要数据结构后面的栈和图还有二叉树的相关讲解，也可以评论区私聊我更新。