线性表链式储存和顺序储存各有优点
“该笔记的一些说法是自己的理解，并不官方”
首先我们要创建一个结构体用来储存书籍的相关属性信息，我称为数据结构体（储存一组待储存的数据）
typedef struct book
{
string bnum;//书的编号
string bname;//书名
float bprice;//书的价格
}book;//书籍结构体
然后再创建一个结构体用来作为“表格”其中的成员有数据域和指针域（注意这只是一个表格）
typedef struct Node
{
ElemType M_e;//数据域
struct Node* next;//指针域
}Node;//表格结构体
一个个的表格连接起来就是链表，所以链表就是一个表格指向另一个表格，一直连续不断的指下去
typedef struct Node* LinkList;//链表
1. 表格定义好后我们便要初始化链表，初始化链表函数如下：
Status InitList(LinkList*L)//初始化链表（创造头结点）
{
*L = (LinkList)malloc(sizeof(Node));//开辟空间,L是个双重指针所以这里要解引用
if (!(*L))
return 0;
(*L)->next = NULL;
return 1;
}
初始化链表其实就是创造头结点的过程（头结点其实也就是一个表格，只是里面的数据域没有信息，只有指针域指向第一个结点）首先开辟一个表格的空间，判断是否开辟成功，开辟成功后由于此时链表还没有任何数据，所以初始化头结点指针域的指针指向空。
2.链表初始化好以后我们便可以定义向链表输入数据的函数creatListTail，过程如下：
void creatListTail(LinkList* L)
{
LinkList p,r;//p代表新输入数据的位置，r代表最后一个数据所在的位置
r = (*L);//初始化r
cout << "输入完毕按0退出" << endl;
while (1)
{
p = new Node;
/*向数据区输入数据*/
cout << "请输入书的编号" << endl;
cin >> p->M_e.bnum;
if (p->M_e.bnum == "0")
break;
cout << "请输入书名" << endl;
cin >> p->M_e.bname;
cout << "请输入书的价格" << endl;
cin >> p->M_e.bprice;
r->next = p;//把p接在r的后面
r = p;//此时p变为了最后一位，更新r为p
}
r->next = NULL;//r是最后一位所以指向空指针
}
这里我们使用的是尾插法，要定义一个表格指针r来一直指向链表最后一个表格的位置，便于将用户新输入的数据连到表格的最后，一开始表格内没有数据，所以r一开始初始化为指向头结点(*L)
用p来指向开辟的一个表格（也可以说是结点）的空间，将用户输入的数据储存到开辟的这个空间中，输入完毕后将新开辟的表格p连到r的后面，此时最后一位变成了p于是让r指向此时p所在的位置，记录最后一个表格的位置（最后一个表格后面肯定没有表格了所以将r的指针域指向空）
3.将数据输入到链表中后我们要将其输出，定义输出函数PrintdList如下：
void PrintdList(LinkList* L)//输出所有的数据
{
LinkList p;//用来遍历的指针
p = (*L)->next;//让p指向第一个结点
if (p == NULL)
{
cout << "链表没有数据哦" << endl;
return;
}
while (p)
{
cout << "编号：" << p->M_e.bnum << endl;
cout << "书名：" << p->M_e.bname << endl;
cout << "价格:" << p->M_e.bprice << endl;
cout << endl;
p = p->next;//打印出当前结点的数据后遍历到下一个结点
}
}
我们要输出所有表格的数据便要遍历所有表格，将遍历用的指针p初始化指向第一个表格后，判断第一个表格是否存在，没有存在就说明链表中没有数据。通过while循环不停的遍历并输出链表中的信息，直到指针p指向的位置没有数据为止。
4.我们接下来还需要有查询用户输入数据的功能，查询功能的函数 GetElem如下：
void GetElem(LinkList* L)//查询用户输入的数据
{
int a = 0;
string name;
string num;//定义一个临时变量来储存用户输入的数据
LinkList p=(*L)->next;//用来遍历链表;对p初始化
if (p == NULL)
{
cout << "链表没有数据哦" << endl;
return;
}
cout << "1.查询书名 2.查询书籍编号" << endl;
cin >> a;
switch (a)
{
case 1:
{
int dbd=1;
cout << "请输入您要查询的书名" << endl;
cin >> name;
do
{
if (p->M_e.bname == name)
{
dbd = 0;//找到数据退出循环
}
else
p = p->next;//不是当前数据，继续向下遍历
} while (dbd && p);
if (dbd == 0)
{
cout << "编号:" << p->M_e.bnum << endl;
cout << "书名：" << p->M_e.bname << endl;
cout << "价格:" << p->M_e.bprice << endl;
}
else
cout << "没有查到相关数据" << endl;
break;
}
case 2:
{
int dbd = 1;
cout << "请输入您要查询的书籍编号" << endl;
cin >> num;
do
{
if (p->M_e.bnum == num)
{
dbd = 0;//找到数据退出循环
}
else
p = p->next;//不是当前数据，继续向下遍历
} while (dbd && p);
if (dbd == 0)
{
cout << "编号:" << p->M_e.bnum << endl;
cout << "书名：" << p->M_e.bname << endl;
cout << "价格:" << p->M_e.bprice << endl;
}
else
cout << "没有查到相关数据" << endl;
break;
}
}
}
查询这里我们给了用户两种方法查询，一种通过书名查询，一种通过编号查询，两个过程差别不大，我们以查询书名为例：首先依然需要判断链表中是否有数据，避免做无用功。定义一个string类型的变量来储存用户输入的书名，在do while循环中将找到相关数据后退出循环的功能表现为改变dbd的值能更灵活。由于退出while循环的条件有找到相关数据后退出和p指针指向空后退出（链表内的数据全部遍历完）这两种情况，所以在后面要判断是哪一种情况退出的，当dbd为0就说明是因为找到了相关数据退出的，于是便输出此时p指向的表格内的数据，dbd不为0，就说明是因为遍历完链表退出的（没有找到相关数据）
5.接下来我们实现向链表指定位置插入数据的功能，函数ListInsert1和ListInsert2如下：
ListInsert1：
LinkList ListInsert1(LinkList* L, int i)//遍历到i-1的位置，并对一些特殊情况进行判断
{
LinkList p;
p = *L;
int j = 0;//用于计数
/*这里用while循环可以判断i值是否是合法输入，for循环就不行*/
while (p && j < i - 1)//将p指向i-1的位置(要在i处插入i-1处必须存在结点而i处随意)
{
p = p->next;
j++;
}
if (!p || j > i - 1)//判断是因为什么情况退出的while循环(没有查找到i处的情况)
{
cout << "无法插入到" << i << "处" << endl;
return NULL;
}
return p;
}
ListInsert2：
void ListInsert2(LinkList p, ElemType e)
{
LinkList s;
s = new Node;//开辟新结点
s->M_e = e;
s->next = p->next;
p->next = s;
cout << "插入成功" << endl;
}
函数ListInsert1是用于返回i-1处的位置，因为要在i处插入数据，那么i-1处就必须要有数据，所以用ListInsert1函数返回i-1的位置并且可以判断i-1处是否有数据，要是没有数据便说明无法插入，可以直接退出程序避免多余的操作。
要是ListInsert1成功返回i-1处的位置，我们便可以向程序输入数据，并调用ListInsert2函数将数据输入链表
6.接下来我们实现删除链表指定位置数据的功能，函数DeleteList1和DeleteList2如下：
DeleteList1：
LinkList DeleteList1(LinkList* L, int i)//遍历到i-1的位置，并对一些特殊情况进行判断
{
int j = 0;//用于计数
LinkList p;//用p来遍历到i处
p = *L;
while (p->next && j < i - 1)//遍历将p指向i-1处
{
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)//离开while循环p却没有指向i-1处的情况
{
cout << "无法删除" << i << "处的书籍" << endl;
return NULL;
}
return p;//此时p指向i-1处的位置
}
DeleteList2：
void DeleteList2(LinkList p)//删除链表i处的数据
{
LinkList q;
q = p->next;//记录即将删除的结点的地址便于一会释放
cout << "您删除的书籍为：" <<q->M_e.bname<< endl;
p->next = q->next;
free(q);
}
我们这里的DeleteList1和查询函数ListInsert1差别不大，都是返回i-1处的位置，虽然乍一看i-1处的数据存在与否和删除i处的数据没有太大关系，但p要指向i-1处的位置才好进行链表删除操作时指针域数据的改变。
7.接下来我们实现清空链表的功能，函数ClearList如下：
Status ClearList(LinkList* L)
{
LinkList p, q;
p = (*L)->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
cout << "链表已清空" << endl;
return 1;
}
用两个表格指针交替遍历便可以清空链表
接下来便是所有代码展示：
头文件FUNC.h
#pragma once
#include <iostream>
#include<string>
using namespace std;
typedef int Status;//Status代表函数类型，这里暂设定为int
typedef struct book
{
string bnum;//书的编号
string bname;//书名
float bprice;//书的价格
}book;//书籍结构体
typedef book ElemType;
typedef struct Node
{
ElemType M_e;//数据域
struct Node* next;//指针域
}Node;//表格结构体
typedef struct Node* LinkList;//链表
Status InitList(LinkList*L);//初始化链表
Status ClearList(LinkList* L);//清空链表
void creatListTail(LinkList* L);//向链表输入数据
void PrintdList(LinkList* L);//输出所有的数据
void GetElem(LinkList* L);//查询用户输入数据的信息
LinkList ListInsert1(LinkList* L, int i);//在链表的i处插入数据
void ListInsert2(LinkList p, ElemType e);
LinkList DeleteList1(LinkList* L, int i);//删除链表i处的数据
void DeleteList2(LinkList p);
源文件FUNC.cpp
#include "FUNC.h"
Status InitList(LinkList*L)//初始化链表（创造头结点）
{
*L = (LinkList)malloc(sizeof(Node));//开辟空间,L是个双重指针所以这里要解引用
if (!(*L))
return 0;
(*L)->next = NULL;
return 1;
}
/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList* L)
{
LinkList p, q;
p = (*L)->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
cout << "链表已清空" << endl;
return 1;
}
/*向链表输入数据*/
void creatListTail(LinkList* L)
{
LinkList p,r;//p代表新输入数据的位置，r代表最后一个数据所在的位置
r = (*L);//初始化r
cout << "输入完毕按0退出" << endl;
while (1)
{
p = new Node;
/*向数据区输入数据*/
cout << "请输入书的编号" << endl;
cin >> p->M_e.bnum;
if (p->M_e.bnum == "0")
break;
cout << "请输入书名" << endl;
cin >> p->M_e.bname;
cout << "请输入书的价格" << endl;
cin >> p->M_e.bprice;
r->next = p;//把p接在r的后面
r = p;//此时p变为了最后一位，更新r为p
}
r->next = NULL;//r是最后一位所以指向空指针
}
void PrintdList(LinkList* L)//输出所有的数据
{
LinkList p;//用来遍历的指针
p = (*L)->next;//让p指向第一个结点
if (p == NULL)
{
cout << "链表没有数据哦" << endl;
return;
}
while (p)
{
cout << "编号：" << p->M_e.bnum << endl;
cout << "书名：" << p->M_e.bname << endl;
cout << "价格:" << p->M_e.bprice << endl;
cout << endl;
p = p->next;//打印出当前结点的数据后遍历到下一个结点
}
}
void GetElem(LinkList* L)//查询用户输入的数据
{
int a = 0;
string name;
string num;//定义一个临时变量来储存用户输入的数据
LinkList p=(*L)->next;//用来遍历链表;对p初始化
if (p == NULL)
{
cout << "链表没有数据哦" << endl;
return;
}
cout << "1.查询书名 2.查询书籍编号" << endl;
cin >> a;
switch (a)
{
case 1:
{
int dbd=1;
cout << "请输入您要查询的书名" << endl;
cin >> name;
do
{
if (p->M_e.bname == name)
{
dbd = 0;//找到数据退出循环
}
else
p = p->next;//不是当前数据，继续向下遍历
} while (dbd && p);
if (dbd == 0)
{
cout << "编号:" << p->M_e.bnum << endl;
cout << "书名：" << p->M_e.bname << endl;
cout << "价格:" << p->M_e.bprice << endl;
}
else
cout << "没有查到相关数据" << endl;
break;
}
case 2:
{
int dbd = 1;
cout << "请输入您要查询的书籍编号" << endl;
cin >> num;
do
{
if (p->M_e.bnum == num)
{
dbd = 0;//找到数据退出循环
}
else
p = p->next;//不是当前数据，继续向下遍历
} while (dbd && p);
if (dbd == 0)
{
cout << "编号:" << p->M_e.bnum << endl;
cout << "书名：" << p->M_e.bname << endl;
cout << "价格:" << p->M_e.bprice << endl;
}
else
cout << "没有查到相关数据" << endl;
break;
}
}
}
/*在链表的i处插入数据*/
LinkList ListInsert1(LinkList* L, int i)//遍历到i-1的位置，并对一些特殊情况进行判断
{
LinkList p;
p = *L;
int j = 0;//用于计数
/*这里用while循环可以判断i值是否是合法输入，for循环就不行*/
while (p && j < i - 1)//将p指向i-1的位置(要在i处插入i-1处必须存在结点而i处随意)
{
p = p->next;
j++;
}
if (!p || j > i - 1)//判断是因为什么情况退出的while循环(没有查找到i处的情况)
{
cout << "无法插入到" << i << "处" << endl;
return NULL;
}
return p;
}
void ListInsert2(LinkList p, ElemType e)
{
LinkList s;
s = new Node;//开辟新结点
s->M_e = e;
s->next = p->next;
p->next = s;
cout << "插入成功" << endl;
}
/*删除链表i处的数据*/
LinkList DeleteList1(LinkList* L, int i)//遍历到i-1的位置，并对一些特殊情况进行判断
{
int j = 0;//用于计数
LinkList p;//用p来遍历到i处
p = *L;
while (p->next && j < i - 1)//遍历将p指向i-1处
{
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)//离开while循环p却没有指向i-1处的情况
{
cout << "无法删除" << i << "处的书籍" << endl;
return NULL;
}
return p;//此时p指向i-1处的位置
}
void DeleteList2(LinkList p)//删除链表i处的数据
{
LinkList q;
q = p->next;//记录即将删除的结点的地址便于一会释放
cout << "您删除的书籍为：" <<q->M_e.bname<< endl;
p->next = q->next;
free(q);
}
源文件text.cpp
#include "FUNC.h"
int main()
{
cout << "欢迎来到图书馆管理系统（链式储存）" << endl;
int b1 = 0;
LinkList L;//定义一个数据表L出来
if (!InitList(&L))//用了Initlist函数已经初始化链表
cout << "链表创建失败" << endl;
int APS = 1;
while (APS)//用APS方便后面退出while循环
{
system("pause");
system("cls");
cout << " 请选择您要进行的操作" << endl;
cout << "1.存储书籍，2.输出所有书籍 3.查询书籍 4.插入书籍 5.删除书籍 6.退出程序 7.删除所有书籍" << endl;
cin >> b1;
switch (b1)
{
case 1:
{
creatListTail(&L);
break;
}
case 2:
{
PrintdList(&L);
break;
}
case 3:
{
GetElem(&L);
break;
}
case 4:
{
ElemType e;//用一个临时变量储存用户输入的数据
LinkList p;//用临时变量储存函数ListInsert1的返回值
int i;
cout << "请输入在哪里插入书籍" << endl;
cin >> i;
p = ListInsert1(&L, i);
if (p)
{
cout << "请输入书籍编号" << endl;
cin >> e.bnum;
cout << "请输入书名" << endl;
cin >> e.bname;
cout << "请输入价格" << endl;
cin >> e.bprice;
ListInsert2(p, e);//用ListInsert2函数将数据输入链表
}
break;
}
case 5:
{
LinkList p;//用来接收函数DeleteList1返回的指针
ElemType e;//用来储存删除的数据
int i;
int verify;//用于确认是否删除数据
cout << "要删除哪个位置的数据" << endl;
cin >> i;
p=DeleteList1(&L, i);
cout << "要删除的书籍为:" << p->next->M_e.bname << endl;//p指向的是i-1处的数据而不是i处的，所以要用 p->next->M_e.bname来输出i处的书名
cout << "是否确认删除：1.是 2.否" << endl;
cin >> verify;
if (verify == 1)
{
DeleteList2(p);
}
else if (verify == 2)
{
cout << "取消删除" << endl;
}
else
cout << "非法输入" << endl;
break;
}
case 6:
{
cout << "感谢使用" << endl;
APS = 0;
break;
}
case 7:
{
int verify;
cout << "是否要清空链表：1.是 2.否" << endl;
cin >> verify;
if (verify == 1)
{
ClearList(&L);
}
else if (verify == 2)
{
cout << "取消清空" << endl;
}
else
cout << "非法输入" << endl;
break;
}
default:
{
cout << "该输入不合法" << endl;
break;
}
}
}
return 0;
}
线性表链式储存完成。
