C/C++ 数据结构与算法【线性表】 顺序表+链表详细解析【日常学习，考研必备】带图+详细代码
1）线性表的定义
线性表（List）：零个或多个数据元素的有限序列。
线性表的数据集合为{a1,a2,…,an}，假设每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
在较复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件
2）线性表的顺序存储结构
一、顺序表
1、顺序表的基本概念
概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。
特点：逻辑上相邻的数据元素，物理次序也是相邻的。
只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，因为高级语言中的数组类型也是有随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序储存结构，用动态分配的一维数组表示线性表。
2、顺序表的存储结构
普通变量用.来引用
指针变量用->来引用
模板：
#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量
//顺序表数据结构
typedef struct
{
ElemType *elem[LIST_INIT_SIZE];
int length; // 当前长度
}SqList;
静态数组定义：
#define MAXSIZE 100
typedef struct {
ElemType elem [MAXSIZE];
int length;
}SqList;
动态数组定义：
typedef struct {
ElemType *elem;
int length;
}Sqlist;
L.elem = (ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
常见基本操作：
InitList(&L) // 初始化操作，建立一个空的线性表L
DestroyList(&L)// 销毁已存在的线性表L
ClearList(&L) // 将线性表清空
Listlnsert(&L, i, e)// 在线性表L中第i个位置插入新元素e
ListDelete(&L,i, &e)// 删除线性表L中第i个位置元素，用e返回
IsEmpty(L)// 若线性表为空，返回true，否则false
ListLength(L)// 返回线性表L的元素个数
LocateElem(L,e)// L中查找与给定值e相等的元素，若成功返回该元素在表中的序号否则返回 0
GetElem(L, i, &e)// 将线性表L中的第i个位置元素返回给e
二、代码具体实现：
1、定义顺序表结构
#include<iostream>
#include<malloc.h>
using namespace std;
// 函数结果状态码
#define OK 1 //成功标识
#define ERROR 0 //失败标识
#define MAXSIZE 100 //线性表存储空间的初始分配量
typedef int Status;//Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int ElemType; //ElemType的类型根据实际情况而定，这里假定为int
//顺序表数据结构
typedef struct
{
ElemType *elem;
int length;
}SqList;
2、顺序表的初始化
Status InitList(SqList &L){ // 构造一个空的顺序表L
// 构造一个空的线性表L
L.elem = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
if(!L.elem){
return ERROR;
}
L.length = 0;
return OK;
}
3、顺序表的清空与销毁
// 顺序表L的销毁
void DestroyList(SqList &L){
if(L.elem) {
delete L.elem;// 释放存储空间
}
}
// 顺序表L的清空
void ClearList(SqList &L){
L.length = 0;// 将线性表的长度置为 0 ，元素个数为0，存储空间还在
}
4、求顺序表长度和判断是否为空
// 求顺序表L的长度
int GetLength(SqList L){ // 这里不需要改变原值，不要需要引用
return (L.length);
}
// 判断线性表L是否为空
int IsEmpty(SqList &L){
if(L.length == 0){
return 1;
}else{
return 0;
}
}
5、顺序表的插入
// 顺序表L的插入
Status ListInsert(SqList &L,int i,ElemType e){
if(i < 1 || i > L.length + 1) return ERROR; // i值不合法
if(L.length == MAXSIZE) return ERROR; // 当前存储空间已满
int j;
for(j = L.length - 1;j >= i - 1;j--){
L.elem[j + 1] = L.elem[j]; // 插入位置及之后的元素后移
}
L.elem[i - 1] = e; // 将新元素e放入第i个位置
L.length++; // 表长增 1
return OK;
}
6、顺序表的删除
// 顺序表L的删除
Status ListDelete(SqList &L,int i){
if(i < 1 || i > L.length) return ERROR; // i值不合法
int j;
for (j = i;j <= L.length - 1;j++){
L.elem[j - 1] = L.elem[j]; // 被删除元素之后的元素前移
}
L.length--; // 表长减 1
return OK;
}
7、顺序表的查找
7.1 按位查找
Status GetElem(SqList &L,int i,ElemType &e){
if (L.length == 0 || i < 1 || i > L.length) return ERROR;// 判断i值是否合理，若不合理，返回ERROR
e = L.elem[i - 1]; //第i-1的单元存储着第i个数据
return OK;
} // 复杂度 O(1)
7.2 按值查找
Status LocateELem(SqList &L, ElemType &e){
//在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)
for (int i = 0;i < L.length;i++){
if(L.elem[i] == e) {
return i + 1;
}//查找成功，返回序号
}
return ERROR; //查找失败，返回0
}
8、顺序表的输入与输出
// 顺序表的输入
void ListCreate(SqList& L)
{
cout << "输入线性表中的元素：(以-1作为结束标志)" << endl;
int i = 0; //线性表数组元素的下标
cin >> L.elem[i];
while (L.elem[i] != -1 ) //线性表结束输入的标志
{
L.length++;
i++;
cin >> L.elem[i];
}
}
//顺序表的输出
void PrintSqList(SqList &L)
{
int i;
for (i = 0; i < L.length; i++) {
cout << L.elem[i] << ' ';
}
}
9、运行测试
int main(){
SqList L; //定义线性表L
InitList(L); //初始化线性表L
ListCreate(L); //线性表的输入
cout << "线性表为：" << endl;
PrintSqList(L); //线性表的输出
cout << endl << "此时线性表中的元素个数为：" << L.length;
cout << endl << "---------------------------------------";
int a1,x1 = 0;
cout << endl << "要获取第几个元素" << endl;
cin >> x1;
GetElem(L, x1,a1);
cout << "获取第"<<x1<<"个元素为：" <<a1<<endl;
int a;
cout << "请输入要查找的元素：" << endl;
cin >> a;
LocateELem(L, a);
int x2, b;
cout << "要插入的位置 ";
cin >> x2;
cout<< "要插入的元素 ";
cin >> b;
ListInsert(L, x2, b);
cout << "线性表为：" << endl;
PrintSqList(L); //线性表的输出
int x3;
cout <<endl<< "要删除第几个元素？";
cin >> x3;
ListDelete(L, x3);
cout << "线性表为：" << endl;
PrintSqList(L); //线性表的输出
system("pause");
return 0;
}
10、总体代码
// 函数结果状态码
#define OK 1 //成功标识
#define ERROR 0 //失败标识
#define MAXSIZE 100 //线性表存储空间的初始分配量
typedef int Status;//Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int ElemType; //ElemType的类型根据实际情况而定，这里假定为int
//顺序表数据结构
typedef struct
{
ElemType *elem;
int length;
}SqList;
// 顺序表L的初始化
Status InitList(SqList &L){ // 构造一个空的顺序表L
// 构造一个空的线性表L
L.elem = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));
if(!L.elem){
return ERROR;
}
L.length = 0;
return OK;
}
// 顺序表L的销毁
void DestroyList(SqList &L){
if(L.elem) {
delete L.elem;// 释放存储空间
}
}
// 顺序表L的清空
void ClearList(SqList &L){
L.length = 0;// 将线性表的长度置为 0 ，元素个数为0，存储空间还在
}
// 求顺序表L的长度
int GetLength(SqList L){ // 这里不需要改变原值，不要需要引用
return (L.length);
}
// 判断线性表L是否为空
int IsEmpty(SqList &L){
if(L.length == 0){
return 1;
}else{
return 0;
}
}
// 顺序表L的插入
Status ListInsert(SqList &L,int i,ElemType e){
if(i < 1 || i > L.length + 1) return ERROR; // i值不合法
if(L.length == MAXSIZE) return ERROR; // 当前存储空间已满
int j;
for(j = L.length - 1;j >= i - 1;j--){
L.elem[j + 1] = L.elem[j]; // 插入位置及之后的元素后移
}
L.elem[i - 1] = e; // 将新元素e放入第i个位置
L.length++; // 表长增 1
return OK;
}
// 顺序表L的删除
Status ListDelete(SqList &L,int i){
if(i < 1 || i > L.length) return ERROR; // i值不合法
int j;
for (j = i;j <= L.length - 1;j++){
L.elem[j - 1] = L.elem[j]; // 被删除元素之后的元素前移
}
L.length--; // 表长减 1
return OK;
}
// 顺序表L的查找
// 按位查找（根据位置i获取相应位置数据元素的内容）
Status GetElem(SqList &L,int i,ElemType &e){
if (L.length == 0 || i < 1 || i > L.length) return ERROR;// 判断i值是否合理，若不合理，返回ERROR
e = L.elem[i - 1]; //第i-1的单元存储着第i个数据
return OK;
} // 复杂度 O(1)
// 按值查找 （查找与指定值e相同元素的位置）
Status LocateELem(SqList &L, ElemType &e){
//在线性表L中查找值为e的数据元素，返回其序号(是第几个元素)
for (int i = 0;i < L.length;i++){
if(L.elem[i] == e) {
return i + 1;
}//查找成功，返回序号
}
return ERROR; //查找失败，返回0
}
// 顺序表的输入
void ListCreate(SqList& L)
{
cout << "输入线性表中的元素：(以-1作为结束标志)" << endl;
int i = 0; //线性表数组元素的下标
cin >> L.elem[i];
while (L.elem[i] != -1 ) //线性表结束输入的标志
{
L.length++;
i++;
cin >> L.elem[i];
}
}
//顺序表的输出
void PrintSqList(SqList &L)
{
int i;
for (i = 0; i < L.length; i++) {
cout << L.elem[i] << ' ';
}
}
int main(){
SqList L; //定义线性表L
InitList(L); //初始化线性表L
ListCreate(L); //线性表的输入
cout << "线性表为：" << endl;
PrintSqList(L); //线性表的输出
cout << endl << "此时线性表中的元素个数为：" << L.length;
cout << endl << "---------------------------------------";
int a1,x1 = 0;
cout << endl << "要获取第几个元素" << endl;
cin >> x1;
GetElem(L, x1,a1);
cout << "获取第"<<x1<<"个元素为：" <<a1<<endl;
int a;
cout << "请输入要查找的元素：" << endl;
cin >> a;
LocateELem(L, a);
int x2, b;
cout << "要插入的位置 ";
cin >> x2;
cout<< "要插入的元素 ";
cin >> b;
ListInsert(L, x2, b);
cout << "线性表为：" << endl;
PrintSqList(L); //线性表的输出
int x3;
cout <<endl<< "要删除第几个元素？";
cin >> x3;
ListDelete(L, x3);
cout << "线性表为：" << endl;
PrintSqList(L); //线性表的输出
system("pause");
return 0;
}
11、运行结果
12、小结
12.1、顺序表的操作算法分析
- 时间复杂度
查找、插入、删除算法的平均时间复杂度 O(n)
- 空间复杂度
显然，顺序表操作算法的空间复杂度 S(n) = O(1)（没有占用辅助空间）
12.2、优缺点
- 优点:
存储密度大（结点本身所占存储量 / 结点结构所占存储量）可以随机存取表中任一元素
- 缺点:
在插入、删除某一元素时，需要移动大量元素
浪费存储空间
属于静态存储形式，数据元素的个数不能自由扩充
3）线性表的链式存储结构
介绍：
- 用一组物理位置任意的存储单元来存放线性表的数据元素。
- 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。
- 链表中元素的逻辑次序和物理次序不一定相同。
在链式结构中，除了要存储数据元素的信息外，还要存储它的后继元素的存储地址。因此，为了表示每个数据元素ai与其直接后继元素ai + 1之间的逻辑关系，对数据ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域（存的是下一结点的地址）。
特点：
（1）结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
（2）访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。
结点；
指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。
分类：
头指针、头节点、首元结点：
头节点的作用：
1 便于首元结点的处理
首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它位一一致，无须进行特殊处理。
2 便于空表和非空表的统一处理
无论链表是否为空，头指针都是指向头结点的非空指针因此空表和非空表的处理也就统一了。
头结点的数据域内装的是什么：
头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。
空链表，头结点的直接后继为空。
假设p是指向线性表第i个数据元素的指针，p -> data表示第 i 个位置的数据域，
p -> next表示第 i + 1 个位置的指针域，
则第p+i个数据元素可表示为：
一、单链表
1、单链表的基本概念
n个结点（ai的存储映像）链结成一个链表，即为线性表（a1, a2, …, an）的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
单链表是由表头唯一确定的，因此单链表可以用头指针的名字来命名，若指针名是L，则把链表称为表L。
2、单链表的存储结构
模板:
typedef struct Lnode{ // 声明结点的类型和指向结点的指针类型
ElemType data; // 结点的数据域
struct Lnode *next; // 结点的指针域
}Lnode,*Linklist; // LinkList 为指向结构体 Lnode 的指针类型
定义链表：
LinkList L;
定义结点指针p：
LNode *p; 或者 LinkList p;
二、代码总体实现
1、定义单链表结构
#include<iostream>
#include<malloc.h>
using namespace std;
// 函数结果状态码
#define OK 1 //成功标识
#define ERROR 0 //失败标识
#define MAXSIZE 100 //线性表存储空间的初始分配量
typedef int Status;//Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int ElemType; //ElemType的类型根据实际情况而定，这里假定为int
typedef struct LNode { // 声明结点的类型和指向结点的指针类型
ElemType data; // 结点的数据域
struct LNode *next; // 结点的指针域
}LNode, *LinkList; // LinkList 为指向结构体 Lnode 的指针类型
2、单链表的初始化
Status InitList(LinkList &L) {
// 从内存中获得一块空间，将这块空间的地址赋给 L
L = new LNode; // 或者 L = (LinkList) malloc (sizeof(LNode));
if (!L) {
return ERROR;
}
L->next = NULL;
return OK;
}
3、单链表的创建
3.1 头插法
元素插在链表头部，也叫前插法
// 头插法
void ListCreateT(LinkList &L, int n) {
LinkList p;
L = new LNode;
L->next = NULL; // 先建立一个带头结点的单链表
for (int i = n; i > 0; --i) {
p = new LNode; // 生成新结点 p=(LNode*)malloc(sizeof(LNode))
cin >> p->data; // 输入元素值 scanf(&p-> data);
p->next = L->next; // 插入到表头
L->next = p;
}
}
3.2 尾插法：
元素插入到链表尾部，也叫后插法
// 尾插法 比较常用
// 正位序输入n个元素的值，建立带表头结点的单链表
void ListCreateW(LinkList &L, int n) {
L = new LNode;
L->next = NULL;
LinkList p, r = L; // 尾指针r指向头结点
for (int i = 0; i < n; ++i) {
p = new LNode;
cin >> p->data; // 生成新结点 ，输入元素值
p->next = NULL;
r->next = p; // 插入到表尾
r = p;//r指向新的尾结点
}
}
4、单链表的清空与销毁
// 单链表的销毁
Status DestroyList(LinkList &L) {
LNode *p;// 或者LinkList p;
while (L) {
p = L;
L = L->next;
delete p;
}
return OK;
}
// 单链表的清空
Status ClearList(LinkList &L) { // 将L重置为空表
LNode *p, *q; // 或者LinkList p,q;
p = L->next;
while (p) { // 没到表尾
q = p->next;
delete p;
p = q;
}
L->next = NULL; // 头结点指针域为空
return OK;
}
5、求单链表长度和判断是否为空
// 求单链表的表长
int ListLength(LinkList L) {
LinkList p;
p = L->next;
int i = 0;
while (p) {
i++;
p = p->next;
}
return i;
}
// 判断链表是否为空（判断头节点指针域是否为空）
int ListEmpty(LinkList L) { // 若L为空表，则返回1，否则返回0
if (L->next) { // 非空
return 0;
}
else {
return 1;
}
}
6、单链表的插入
若将将节点s插入到节点p和几点 p -> next之间，如下图所示，其核心操作是：
s -> next = p -> next;
p -> next = s;
具体代码如下：
//在L中第i个元素之前插入数据元素
Status ListInsert(LinkList& L, int i, ElemType e) {
LinkList p = L,s;
int j = 0;
while (p && j < i - 1) {
p = p->next; // 寻找第i-1个结点，p指向i-1结点
++j;
}
if (!p || j > i - 1) { // i大子表长 + 1或者小于1，插入位置非法
return ERROR;
}
s = new LNode;
s->data = e; // 生成新结点s，将结点s的数据域置为e
s->next = p->next; //将 结点s插入L中
p->next = s;
return OK;
}
7、单链表的删除
// 将线性表L中第i个数据元素删除
Status ListDelete(LinkList &L, int i){
LinkList p = L,q;
int j = 0;
while (p->next && j < i - 1) {
p = p->next;
++j;
}
// 寻找第i个结点，并令p指向其前驱
if (!(p->next) || j > i - 1) {
return ERROR; // 删除位置不合理
}
q = p -> next; // 临时保存被删结点的地址以备释放
p->next = q->next; // 改变删除结点前驱结点的指针域
delete q; // 释放删除结点的空间
return OK;
}
8、单链表的查找
常见取值：
// 单链表的取值
Status GetElem(LinkList L, int i, ElemType &e) { // 获取单链表中的某个数据元素的内容，通过变量e返回
// 初始化
LinkList p;
p = L->next;
int j = 1;
while (p && j < i) { // 向后扫描，直到p指向第i个元素或p为空
p = p->next;
++j;
}
if (!p || j > i) {
return ERROR; // 第i个元素不存在
}
e = p->data; // 取第i个元素
return OK;
}
按位查询：
// 按位查找（根据指定数据获取该数据所在的位置）（地址）
LNode *LocateELem(LinkList L, ElemType e) {
// 在单链表中查找值为 e 的数据元素
// 找到，返回值为 e 数据元素的地址，查找失败返回NULL
LinkList p;
p = L->next;
while (p && p->data != e) {
p = p->next;
}
return p;
}
按值查询：
int GetELem(LinkList L, ElemType e) {
// 返回L中值为e的数据元素的位置序号，查找失败返回0
LinkList p;
p = L->next;
int j = 1;
while (p && p->data != e) {
p = p->next;
j++;
}
if (p) {
return j;
}
else {
return 0;
}
}
9、单链表的打印
// 单链表的遍历
void PrintSqList(LinkList &L)
{
LinkList p = L->next;
while (p)
{
printf("%d -> ", p->data);
p = p->next;
}
printf("NULL");
printf("\n");
//最后打印出来的效果就是 1->2->3->4->NULL
}
10、运行测试
int main() {
LinkList L;
int i;
InitList(L); //初始化单链表L
printf("请输入单链表的数据个数 \n");
cin >> i;
printf("请输入单链表数据 \n");
ListCreateW(L,i);
printf("成功创建链表：\n");
PrintSqList(L);
int option;
ElemType x;
do {
printf("请输入选项：");
cin >> option;
switch (option)
{
case 1:
{
int i;
printf("请输入插入数据的位置：");
cin >> i;
printf("请输入插入数据的值：");
cin >> x;
ListInsert(L, i, x);
printf("插入后的链表为：");
//打印链表
PrintSqList(L);
break;
}
case 2:
{
int i;
printf("请输入删除的位置\n");
cin >> i;
ListDelete(L, i);
printf("删除后的链表为：");
PrintSqList(L);
break;
}
case 3: {
int i;
printf("请输入查找的数据：");
cin >> i;
int j = GetELem(L,i);
printf("该数据的位置为 %d \n", j);
break;
}
case 0:
break;
default:
printf("输出错误！\n"); break;
}
} while (option > 0);
return 0;
}
11、总体代码
#include<iostream>
#include<malloc.h>
using namespace std;
// 函数结果状态码
#define OK 1 //成功标识
#define ERROR 0 //失败标识
#define MAXSIZE 100 //线性表存储空间的初始分配量
typedef int Status;//Status是函数的类型，其值是函数结果状态代码，如OK等
typedef int ElemType; //ElemType的类型根据实际情况而定，这里假定为int
typedef struct LNode { // 声明结点的类型和指向结点的指针类型
ElemType data; // 结点的数据域
struct LNode *next; // 结点的指针域
}LNode, *LinkList; // LinkList 为指向结构体 Lnode 的指针类型
// 单链表初始化
Status InitList(LinkList &L) {
// 从内存中获得一块空间，将这块空间的地址赋给 L
L = new LNode; // 或者 L = (LinkList) malloc (sizeof(LNode));
if (!L) {
return ERROR;
}
L->next = NULL;
return OK;
}
// 头插法
void ListCreateT(LinkList &L, int n) {
LinkList p;
L = new LNode;
L->next = NULL; // 先建立一个带头结点的单链表
for (int i = n; i > 0; --i) {
p = new LNode; // 生成新结点 p=(LNode*)malloc(sizeof(LNode))
cin >> p->data; // 输入元素值 scanf(&p-> data);
p->next = L->next; // 插入到表头
L->next = p;
}
}
// 尾插法 比较常用
// 正位序输入n个元素的值，建立带表头结点的单链表
void ListCreateW(LinkList &L, int n) {
L = new LNode;
L->next = NULL;
LinkList p, r = L; // 尾指针r指向头结点
for (int i = 0; i < n; ++i) {
p = new LNode;
cin >> p->data; // 生成新结点 ，输入元素值
p->next = NULL;
r->next = p; // 插入到表尾
r = p;//r指向新的尾结点
}
}
// 单链表的销毁
Status DestroyList(LinkList &L) {
LNode *p;// 或者LinkList p;
while (L) {
p = L;
L = L->next;
delete p;
}
return OK;
}
// 单链表的清空
Status ClearList(LinkList &L) { // 将L重置为空表
LNode *p, *q; // 或者LinkList p,q;
p = L->next;
while (p) { // 没到表尾
q = p->next;
delete p;
p = q;
}
L->next = NULL; // 头结点指针域为空
return OK;
}
// 求单链表的表长
int ListLength(LinkList L) {
LinkList p;
p = L->next;
int i = 0;
while (p) {
i++;
p = p->next;
}
return i;
}
// 判断链表是否为空（判断头节点指针域是否为空）
int ListEmpty(LinkList L) { // 若L为空表，则返回1，否则返回0
if (L->next) { // 非空
return 0;
}
else {
return 1;
}
}
//在L中第i个元素之前插入数据元素
Status ListInsert(LinkList& L, int i, ElemType e) {
LinkList p = L,s;
int j = 0;
while (p && j < i - 1) {
p = p->next; // 寻找第i-1个结点，p指向i-1结点
++j;
}
if (!p || j > i - 1) { // i大子表长 + 1或者小于1，插入位置非法
return ERROR;
}
s = new LNode;
s->data = e; // 生成新结点s，将结点s的数据域置为e
s->next = p->next; //将 结点s插入L中
p->next = s;
return OK;
}
// 将线性表L中第i个数据元素删除
Status ListDelete(LinkList &L, int i){
LinkList p = L,q;
int j = 0;
while (p->next && j < i - 1) {
p = p->next;
++j;
}
// 寻找第i个结点，并令p指向其前驱
if (!(p->next) || j > i - 1) {
return ERROR; // 删除位置不合理
}
q = p -> next; // 临时保存被删结点的地址以备释放
p->next = q->next; // 改变删除结点前驱结点的指针域
delete q; // 释放删除结点的空间
return OK;
}
// 单链表的取值
//Status GetElem(LinkList L, int i, ElemType &e) { // 获取单链表中的某个数据元素的内容，通过变量e返回
//// 初始化
//LinkList p;
//p = L->next;
//int j = 1;
//
//while (p && j < i) { // 向后扫描，直到p指向第i个元素或p为空
//p = p->next;
//++j;
//}
//
//if (!p || j > i) {
//return ERROR; // 第i个元素不存在
//}
//e = p->data; // 取第i个元素
//return OK;
//}
// 单链表的查找
// 按位查找（根据指定数据获取该数据所在的位置）（地址）
LNode *LocateELem(LinkList L, ElemType e) {
// 在单链表中查找值为 e 的数据元素
// 找到，返回值为 e 数据元素的地址，查找失败返回NULL
LinkList p;
p = L->next;
while (p && p->data != e) {
p = p->next;
}
return p;
}
// 按值查找（ 根据指定数据获取该数据位置序号）
// 在线性表L中查找值为e的数据元素的位置序号
int GetELem(LinkList L, ElemType e) {
// 返回L中值为e的数据元素的位置序号，查找失败返回0
LinkList p;
p = L->next;
int j = 1;
while (p && p->data != e) {
p = p->next;
j++;
}
if (p) {
return j;
}
else {
return 0;
}
}
// 单链表的遍历
void PrintSqList(LinkList &L)
{
LinkList p = L->next;
while (p)
{
printf("%d -> ", p->data);
p = p->next;
}
printf("NULL");
printf("\n");
//最后打印出来的效果就是 1->2->3->4->NULL
}
int main() {
LinkList L;
int i;
InitList(L); //初始化单链表L
printf("请输入单链表的数据个数 \n");
cin >> i;
printf("请输入单链表数据 \n");
ListCreateW(L,i);
printf("成功创建链表：\n");
PrintSqList(L);
int option;
ElemType x;
do {
printf("请输入选项：");
cin >> option;
switch (option)
{
case 1:
{
int i;
printf("请输入插入数据的位置：");
cin >> i;
printf("请输入插入数据的值：");
cin >> x;
ListInsert(L, i, x);
printf("插入后的链表为：");
//打印链表
PrintSqList(L);
break;
}
case 2:
{
int i;
printf("请输入删除的位置\n");
cin >> i;
ListDelete(L, i);
printf("删除后的链表为：");
PrintSqList(L);
break;
}
case 3: {
int i;
printf("请输入查找的数据：");
cin >> i;
int j = GetELem(L,i);
printf("该数据的位置为 %d \n", j);
break;
}
case 0:
break;
default:
printf("输出错误！\n"); break;
}
} while (option > 0);
return 0;
}
12、运行结果：
13、小结：
单链表的算法时间效率分析
1.查找:
因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。
2.插入和删除:
因线性链表不需要移动元素，只要修改指针一般情况下时间复杂度为 O(1)。
但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为 O(n)。
三、静态链表
1、静态链表的基本概念
静态链表，使用数组连描述指针，首先我们让数组的元素都是由两个数据域组成，data和cur。数据域data，用来存放数据元素；游标cur相当于单链表的next指针，存放该元素的后继在数组中的下标。
为了方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲空间可以便于插入时不至于溢出。
#define MAXSIZE 1000 //假设链表的最大长度是1000
typedef struct{
ElemType data;
int cur; //游标（Cursor），为0时表示无指向
} Component,StaticLinkList[MAXSIZE];
另外我们对数组的第一个和最后一个元素作为特殊元素处理，不存数据。通产把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点的作用，当整个链表为空时，则为0。
此时图示相当于初始化的数组状态，见下面代码：
/**
将一维数组space中各分量链成一备用链表
space[0].cur为头指针。“0”表示空指针
*/
Status InitList(Component *space){
int i;
for(i=0; i<MAXSIZE; i++){
space[i].cur = i+1;
}
space[MAXSIZE-1].cur = 0; //目前静态链表为空，最后一个元素的cur为0
return OK;
}
在前面的动态链表中，节点的申请和释放分别借用malloc()和free()两个函数来实现。在静态链表中，我们需要自己实现这两个函数。
为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新节点。
/**
申请下一个分量的资源，返回下标
*/
int Malloc_SLL(StaticLinkList space){
int i = space[0].cur; //当前数组第一个元素的cur存的值，就是要返回的第一个备用空间的下标
if(space[0].cur){
space[0].cur = space[i].cur; //把下一个分量用来做备用
}
return i;
}
/**
将下标为k的空闲节点收回到备用链表
*/
void Free_SSL(Component *space, int k){
space[k].cur = space[0].cur; //把第一个元素cur值赋值给要删除的分量cur
space[0].cur = k; //把要删除的分量下标赋值给第一个元素的cur
}
2、静态链表的插入操作
例如如果我们需要在“乙”和“丁”之间，插入一个“丙”，操作如图所示：
用代码实现如下：
/**
得到静态列表的长度
初始条件：静态列表L已存在。操作结果：返回L中数据元素的个数
*/
int ListLength(StaticLinkList L){
int j = 0;
int i = L[MAXSIZE-1].cur;
while(i){
i = L[i].cur;
j++;
}
return j;
}
/**
在L中第i个元素之前插入新的元素e
*/
Status ListInsert(Component *L, int i, ElemType e){
int j,k,l;
k = MAXSIZE - 1; //注意k首先是最后一个元素的下标
if(i<1 || i>ListLength(L) + 1){
return ERROR;
}
j = Malloc_SLL(L);
if(j){
L[j].data = e; //将数据赋值给此分量的data
for(l=1; l<= i-1; l++){
k = L[k].cur; //找到第i个元素之前的位置
}
L[j].cur = L[k].cur; //把第i个元素之前的cur赋值给新元素的cur
L[k].cur = j; //把新元素的下标赋值给第i个元素之前元素的cur
return OK;
}
return ERROR;
}
3、静态链表的删除操作
例如如果要删除“甲”元素，如图所示：
用代码实现如下：
/**
删除在L中第i个数据元素e
*/
Status ListDelete(Component *L, int i){
int j,k;
if(i<1 || i>ListLength(L)+1){
return ERROR;
}
k = MAXSIZE - 1;
for(j=1; j<=i-1; j++){
k = L[k].cur; //找到第i个元素之前的位置
}
j = L[k].cur;
L[k].cur = L[j].cur;
OUTPUT(L);
Free_SSL(&L, j);
return OK;
}
四、循环链表
1、循环链表的基本概念
将单链表中终端节点的指针端由空指针改为指向头结点（头尾相连的链表），就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
**优点：**从表中任意结点出发均可找到表中其他结点。
循环链表带有头结点的空链表如下图所示：
对于非空的循环链表则如下图所示：
注意:
由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断 p 或p->next 是否为空，而是判断它们是否等于头指针。
循环条件:
单链表
p != NULL
p->next != NULL
单循环链表
p != L
p->next != L
2、仅设尾指针的循环链表
上述仅设头指针的循环链表有一个弊端，我们可以用O(1)的时间访问第一个节点，但对于最后一个节点，却需要O(n)的时间，于是就有了仅设尾指针的循环链表。
如下图所示：
从上图可以看到，终端节点用尾指针 R 指示，则查找终端节点是O(1)，而开始节点，其实就是 R ->next->next，其时间复杂度也是O(1)。
举个程序的例子，要将两个循环链表合成一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是Ta和Tb。
要想把它们合并，只需要如下操作即可：
Ta的最后一个元素连接到Tb的第一个元素
释放Tb的表头结点，将Tb的最后一个元素与Ta的表头相连
// 第一步：保存A的头结点
p = Ta -> next;
// 第二步：将本是指向B表的第一个元素的指向赋值给 Ta->next，
// 再次注意Tb是尾指针，所以是Tb -> next -> next指向第一个元素
Ta -> next = Tb -> next -> next;
// 第三步：释放Tb表头结点
delete Tb->next;
// 第四步：将原A表的头结点赋值给Tb -> next
// 将Tb的最后一个元素与Ta的表头相连
Tb -> next = p;
伪代码实现：
LinkList Connect(LinkList Ta, LinkList Tb) {
//假设Ta、Tb都是非空的单循环链表
p = Ta->next; // ①p存表头结点
Ta->next = Tb->next->next; // ②Tb表头连结Ta表尾
delete Tb->next; // ③释放Tb表头结点 或者 free(Tb->next)
Tb->next = p; // ④修改指针
return Tb;
}
五、双向链表
1、双向链表的基本概念
双向链表（double linked list）是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
/*双向链表存储结构*/
typedef struct DulNodse{
ElemType data;
struct DulNode *prior;//直接前驱指针
struct DulNode *next;//直接后继指针
} DulNode, *DuLinkList;
双链表示意图如下所示：
双向链表的对称性，对于链表中的某一个结点p，它的后继的前驱以及它的前驱的后继都是它自己，即：
p->prior->next = p = p->next->prior
2、双向链表的插入操作
在双链表中p所指的结点之后插入结点*s，其指针的变化过程如下图所示：
插入操作的代码片段如下：
//第一步：把p的前驱赋值给s的前驱
s->prior = p -> prior;
//第二步：把a的后继指向给s
p->prior->next = s;
//第三步：把s的后继指向给p
s->next = p;
//第四步：把p的前驱指向s
p->prior = s;
注意：体会赋值与指向的含义
伪代码实现：
void Listinsert(DuLinkList& L, Int i, ElemType e) {
//在带头结点的双向循环链表L中第i个位置之前插入元素 e
if (!(p = GetElemP(L, i))) {
return ERROR;
}
s = new DuLNode;
s->date = e; // 赋值插入的元素
p->prior->next = s;
s->prior = p->prior;
s->next = p;
p->prior = s;
return OK;
}
3、双向链表的删除操作
如果要删除q结点，只需下面两步：
代码片段如下：
//第一步
p->prior->next = p->next;
//第二步
p->next->prior = p->prior;
伪代码实现：
void ListDelete(DuLink& L, Int i, ElemType& e) {
// 删除带头结点的双向循环链表L的第i个元素，并用 e 返回。
if (!(p = GetElemP(L, i))) {
return ERROR;
}
e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}
六、单链表、循环链表和双向链表的时间效率比较
4）总结
一、顺序表和链表的比较
（1）顺序存储结构的优缺点：
顺序存储结构优点:
- 存储密度大（结点本身所占存储量 / 结点结构所占存储量）可以随机存取表中任一元素
顺序存储结构缺点:
- 在插入、删除某一元素时，需要移动大量元素
- 浪费存储空间
- 属于静态存储形式，数据元素的个数不能自由扩充
（2）链式存储结构的优缺点：
链式存储结构的优点:
- 结点空间可以动态申请和释放;
- 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素
链式存储结构的缺点：
-
存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。
-
链式存储结构是非随机存取结构。对任一结点的操作都要从头指针依指针链查找到该结点，这增加了算法的复杂度。
存储密度概念：
指结点数据本身所占的数据量和整个结点结构中所占的存储量之比。
一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1(100%)，而链表的存储密度小于1。
（3）比较
二、在实际中应该怎样选取存储结构呢?
1、基于存储的考虑
难以估计线性表的长度或存储规模时,不宜采用顺序表;链表不用事先估计存储规模,但链表的存储密度较低,显然链式存储结构的存储密度是小于1的。
2、基于运算的考虑
在顺序表中按序号访问a1的时间复杂度为O(1)，而链表中按序号访问的时间复杂度为O(n)，因此若经常做的运算是按序号访问数据元素，则显然顺序表优于链表。
在顺序表中进行插入、删除操作时，平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中进行插入、删除操作时，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。
3、基于环境的考虑
通常较稳定的线性表选择顺序存储
而频繁进行插入、删除操作的线性表（即动态性较强）宜选择链式存储。
5）线性表的应用
一、线性表的合并
伪代码实现：
void union(List &La, List Lb) { // 合并后的结果用La来返回
La_len = ListLength(La);
Lb_len = ListLength(Lb);
for(i = 1; i <= Lb_len; i + +) {
GetElem(Lb, i, e); // 获取元素操作
if (!LocateElem(La, e)) { // 查找元素操作
Listinsert(&La, ++La_len, e); // 插入元素操作
}
}
// 上述几个操作我前面已经实现过，这里就不再显示
}
二、有序表的合并
顺序表实现：
伪代码实现：
void MergeList(SqList LA, SqList LB, SqList& LC) {
pa = LA.elem;
pb = LB.elem; // 指针pa和pb的初值分别指向两个表的第一个元素
LC.length = LA.length + LB.length; // 新表长度为待合并两表的长度之和
LC.elem = new ElemType[LC.length]; // 为合并后的新表分配一个数组空间
pc = LC.elem; // 指针pc指向新表的第一个元素
pa_last = LA.elem + LA.length - 1; // 指针pa_last指向LA表的最后一个元素
pb_last = LB.elem + LB.length - 1; // 指针pb_last指向LB表的最后一个元素
while(pa <= pa_last && pb <= pb_last){ // 两个表都非空
if (*pa <= *pb) {
*pc++ = *pa++; // 依次“摘取”两表中值较小的结点
}
else {
*pc++ = *pb++;
}
while (pa <= pa_last) { // LB表已到达表尾，将LA中剩余元素加入LC
*pc++ = *pa++;
}
while (pb <= pb_last) { // LA表已到达表尾，将LB中剩余元素加入LC
*pc++ = *pb++;
}
}
链表实现：
伪代码实现：
void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc) {
pa = La->next; pb = Lb->next;
pc = Lc = la; // 用La的头结点作为Lc的头结点
while (pa && pb) {
if (pa->data <= pb->data) {
pc->next = pa;
pc = pa;
pa = pa->next;
}
else {
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb; // 插入剩余段
delete Lb; // 释放Lb的头结点
}
原文地址：https://blog.csdn.net/2301_80035882/article/details/144142097
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！