线性表相关代码（算法命题重点）
线性表作为一种基础且重要的数据结构，在算法领域中占据着关键地位，是众多复杂算法的基石。它能够有序地存储和管理数据元素，为数据的高效处理提供了有力支持。在实际应用场景中，无论是信息管理系统中的数据存储，还是算法竞赛中的数据处理，线性表都发挥着不可或缺的作用。接下来，我们将深入探讨线性表的各种基本操作以及不同存储方式的具体实现。
基本操作：
线性表的基本操作涵盖了初始化、销毁、插入、删除、查找、求表长、判空和输出表等，这些操作构成了线性表功能的核心。
InitList(&L): 初始化链表, 该操作的作用是创建一个空的线性表。
DestroyList(&L): 销毁链表, 用于释放线性表所占用的内存空间，防止内存泄漏，确保系统资源的有效利用。
ListInsert(&L, i, e)：插入操作, 在指定线性表 L 的第 i 个位置上插入指定元素 e，使得线性表的元素序列发生相应变化。
ListDelete(&L, i, &e): 删除操作, 从表 L 中删除第 i 个位置上的元素，并将删除的值通过 e 返回，实现对线性表元素的移除。
GetElem(L, i)：按位查找元素, 获取线性表 L 中第 i 个位置的元素的值，方便根据位置快速获取特定元素。
LocateElem(L, e)：按值查找操作, 在 L 中查找与 e 值相同的元素，为根据元素值定位元素提供了途径。
Length(L): 求表长, 计算线性表 L 中元素的个数，即表的长度，有助于了解线性表的规模。
Empty(L): 判空, 判断线性表 L 是否为空，这在许多操作中是一个重要的前提条件。
PrintList(L): 输出表, 将线性表 L 中的所有元素按照一定格式输出，便于直观查看线性表的内容。
顺序存储
顺序存储是线性表的一种存储方式，它利用一组连续的存储单元依次存储线性表中的数据元素。这种存储方式具有随机访问的特性，能够快速地根据位置获取元素。
#include<stdio.h>
#include<stdlib.h>
// 顺序表的定义（静态分配）
#define Maxsize 50
typedef struct{
int data[Maxsize]; // 顺序表的元素
int length; // 顺序表的当前长度
}SqList;
// 初始化
void initList(SqList &L){
L.length = 0;
}
// 插入
bool ListInsert(SqList &L, int i, int e){
if(i < 1 || i > L.length + 1)
return false;
if(L.length >= Maxsize)
return false;
for(int j = L.length; j >= i; j --) // 将第i个元素及之后的元素后移
L.data[j] = L.data[j - 1];
L.data[i - 1] = e;
L.length ++;
return true;
}
// 删除
bool ListDelete(SqList &L, int i, int &e){
if(i < 1 || i > L.length)
return false;
e = L.data[i];
for(int j = i; j < L.length; j ++)
L.data[j] = L.data[j + 1];
L.length --;
return true;
}
// 按值查找
int LocateElem(SqList &L, int e){
for(int i = 0; i < L.length; i ++)
if(L.data[i] == e)
return i + 1; // 返回位序
return 0;
}
// 按位查找
int GetElem(SqList &L, int i){
return L.data[i - 1];
}
// 判空
bool Empty(SqList L){
return L.length == 0;
}
// 动态分配
#define InitSize 100
typedef struct{
int *data; // 指示动态分配数组的指针
int MaxSize, length; // 数组的最大容量和当前长度
}SqList;
// 初始化
void initList(SqList &L){
L.data = (int*)malloc(sizeiof(int) * InitSize);
L.length = 0;
L,MaxSize = InitSize;
}
在顺序表的静态分配实现中，我们预先定义了一个固定大小的数组 data 来存储元素，通过 length 记录当前表中元素的实际个数。初始化时，将 length 设为 0。插入操作时，首先检查插入位置 i 的合法性以及表是否已满，若满足条件，则将插入位置及之后的元素依次向后移动一位，再将新元素插入指定位置。删除操作同样先检查位置合法性，然后将待删除元素的值赋给 e，并将后续元素依次向前移动一位，同时更新表长。按值查找通过遍历整个表，找到与目标值相等的元素并返回其位序，若未找到则返回 0。按位查找直接返回指定位置的元素值。判空操作只需判断 length 是否为 0。
动态分配的顺序表中，通过 malloc 函数动态分配内存来存储元素，灵活性更高。初始化时，分配一定大小的内存空间给 data 指针，并设置初始长度和最大容量。
链式存储
链式存储是线性表的另一种重要存储方式，它通过指针将各个数据元素链接起来，克服了顺序存储需要连续内存空间的局限性。下面将详细介绍链式存储的不同类型及其实现代码。
单链表
单链表是链式存储的基础形式，每个节点包含数据域和指针域，指针域指向下一个节点。根据是否带有头结点，又分为带头结点和不带头结点两种情况。
带头结点
// 定义单链表的结点
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
// 初始化
bool InitList(LinkList &L){
L = (LNode*)malloc(sizeof(LNode)); // 创建头结点
if(L == NULL) // 没有空间了
return false;
L -> next = NULL;
return true;
}
// 求表长(只有头结点算空表)
int Length(LinkList L){
int len = 0;
LNode* p = L;
while(p -> next != NULL){
p = p -> next;
len ++;
}
return len;
}
// 按序查找 (找到第i个结点，头结点看作第0个)
LNode* GetElem(LinkList L, int i){
if(i < 0)
return NULL;
LNode* p = L;
while(p != NULL && i --){
p = p -> next;
}
return p;
}
// 插入节点(也可以在结点之前插入一个结点，然后交换两个结点的值)
bool ListInsert(LinkList &L, int i, int e){
LNode* p = L; // 表示要插入点之前的一个结点
int j = 0;
while(p != NULL && j < i){ // 循环找到第 i - 1 个结点
p = p -> next;
j ++;
}
if(p == NULL) // i 不合法
return false;
LNode* s = (LNode*)malloc(sizeof(LNode)); // 创建一个新结点
if(s == NULL) return false; // 没有足够的空间了
s -> data = e;
s -> next = p -> next;
p -> next = s;
return true;
}
// 删除结点操作(同样也可以把第i- 1个结点删除，而后使用值覆盖)
bool ListDelete(LinkList &L, int i, int &e){
LNode* p = L; // 表示要删除结点的前一个结点
int j = 0;
while(p != NULL && j < i - 1){
p = p -> next;
j ++;
}
if(p -> next == NULL || j > i - 1) // i 值不合法
return false;
LNode* tmp = p -> next;
e = tmp -> data;
p -> next = tmp -> next;
free(tmp);
return true;
}
// 使用头插法来建立链表
LinkList List_HeadInsert(LinkList &L){ // 逆向建立单链表
LNode *s;
int x;
InitList(L); // 初始化链表
scanf("%d", &x);
while(x != 9999){ // 输入9999代表结束
s = (LNode*)malloc(sizeof(LNode));
if(s == NULL) return false; // 没有足够的空间了
s -> data = x;
s -> next = L -> next;
L -> next = s;
scanf("%d", &x);
}
return L;
}
// 使用尾插法
LinkList List_TailInsert(LinkList &L){
int x;
InitList(L); // 初始化链表
LNode *s, *r = L; // r 表示表尾指针
scanf("%d", &x);
while(x != 9999){
s = (LNode*)malloc(sizeof(LNode));
if(s == NULL) return false; // 没有足够的空间了
s -> data = x;
r -> next = s;
r = s;
scanf("%d", &x);
}
r -> next = NULL;
return L;
}
不带头结点
// 定义单链表的结点
typedef struct LNode{
int data;
struct LNode *next;
}LNode, *LinkList;
// 初始化
bool InitList(LinkList &L){
L = NULL; // 创建空表，无任何结点
return true;
}
// 求表长
int Length(LinkList L){
int len = 0;
LNode* p = L;
while(p != NULL){
len ++;
p = p -> next;
}
return len;
}
// 按序查找
LNode* GetElem(LinkList L, int i){
if(i <= 0)
return NULL;
LNode *p = L;
while(p != NULL && --i){
p = p -> next;
}
return p;
}
// 插入结点
bool ListInsert(LinkList &L, int i, int e){
if(i == 1) {
// 如果要在第一个位置插入元素
LNode* p = (LNode*)malloc(sizeof(LNode));
if(p == NULL) return false; // 没有足够的空间了
p -> data = e;
p -> next = L;
L = p;
return true;
}
LNode* p = L;
int j = 0;
while(p != NULL && j < i - 1){
p = p -> next;
j ++;
}
if(p == NULL)
return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if(s == NULL) return false; // 没有足够的空间了
s -> data = e;
s -> next = p -> next;
p -> next = s;
return true;
}
// 删除结点
bool ListDelete(LinkList &L, int i, int &e){
if(i == 1){ // 删除第一个结点
LNode* p = L;
e = p -> data;
L = p -> next;
free(p);
return true;
}
LNode*p = L;
int j = 0;
while(p -> next != NULL && j < i - 1){
p = p -> next;
j ++;
}
if(p -> next == NULL)
return false;
LNode* tmp = p -> next;
e = tmp -> data;
p -> next = tmp -> next;
free(tmp);
return true;
}
// 使用头插法建立链表
LinkList List_HeadInsert(LinkList &L){
LNode *s;
int x;
InitList(L); // 初始化链表
scanf("%d", &x);
while(x != 9999){
s = (LNode*)malloc(sizeof(LNode));
if(s == NULL) return false; // 没有足够的空间了
s -> data = x;
s -> next = L; // s是第一个结点
scanf("%d", &x);
}
return L;
}
// 使用尾插法建立链表
LinkList List_TailInsert(LinkList &L){
int x;
InitList(L); // 初始化
LNode *s, *r = L;
scanf("%d", &x);
while(x != 9999){
s = (LNode*)malloc(sizeof(LNode));
if(s == NULL) return false; // 没有足够的空间了
s -> data = x;
r -> next = s;
r = s;
scanf("%d", &x);
}
r -> next = NULL;
return L;
}
剩下的会在下一篇博客中呈现，敬请期待！