数据结构：线性表的基本操作与链式表达
个人主页
文章专栏
成名之作——赛博算命之梅花易数的Java实现
陆续回三中，忘回漏回滴滴~感谢各位大佬的支持
一.线性表的定义和基本操作
1.1定义
线性表是具有相同数据类型的n个数据元素的有序数列，n为表长
第一个元素叫表头元素，除了他，每个元素有且仅有一个直接前驱
最后一个元素叫表尾元素，除了他，每个元素有且仅有一个直接后继
1.2特点
- 个数有限
- 逻辑上有顺序性
- 每个元素都是数据元素，且数据类型都相同，占用空间相同
- 有抽象性
注：线性表是逻辑结构，顺序表和链表是存储结构
1.3基本操作
● InitList(&L): 初始化表。构造一个空的线性表。
● Length(L):求表长。返回线性表L 的长度，即L 中数据元素的个数。
● LocateElem(L,e): 按值查找操作。在表工中查找具有给定关键字值的元素。
● GetElem(L,i): 按位查找操作。获取表L 中 第i 个位置的元素的值。
● ListInsert(&L,i,e): 插入操作。在表L 中的第i 个位置上插入指定元素e。
● ListDelete(&L,i,&e):删除操作。删除表L 中第i 个位置的元素，并用e 返回删除元素的值。
● PrintList(L): 输出操作。按前后顺序输出线性表L 的所有元素值。
● Empty(L): 判空操作。若L 为空表，则返回true, 否则返回false。
● DestroyList(&L): 销毁操作。销毁线性表，并释放线性表L 所占用的内存空间。
二.线性表的顺序表示
2.1定义
线性表的顺序存储称为顺序表，逻辑顺序与物理存储顺序相同，是一种随机存取的存储结构
位序：就是第几个，相当于下标但不是下标，数组的下标从0开始，位序从1开始
2.2静态分配与动态分配
一维数组可以静态分配也可以动态分配。
静态分配：空间是固定的，多于最大值时，新数据就会溢出，导致数据崩溃
#define MaxSize 50//定义线性表的最大长度
typedef struct {
ElemType data [MaxSize];//顺序表的元素
int length;//顺序表的当前长度
}SqList;//顺序表的类型定义
动态分配：不是一次性划分所有空间，多余最大值时，会重新开辟更大的新空间，并且把原来的数据copy到新的空间中（不是链式存储，仍是顺序存储结构）
#define IntSize 100//表长度的初始定义
typedef struct{
ElemType *data;//指示动态分配数组的指针
int MaxSize , length;//数组的最大容量和当前个数
}SeqList;//动态分配数组顺序表的类型定义
C的初始动态分配语句为：
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
2.3顺序表的优缺
优点：可以随机访问，存储密度高
缺点：不方便变动，不够灵活
2.4基本操作实现
顺序表的初始化
静态分配
void InitList(SqList *L) {
L->length = 0;//顺序表初始长度为0
}
动态分配
void InitList(SqList *L) {
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);//分配动态存储空间
L->length = 0;//顺序表初始长度为0
L->MaxSize=IntSize;//初始存储容量
}
插入操作
//在指定位置插入元素
bool ListInsert(SqList *L, int i, ElemType e) {
//判断位序i是否合法
if (i<1 || i>L->length+1) {
return false;
}
//判断顺序表是否已满
if (i>L->length+1) {
return false;
}
//将第i个位置及之后的元素后移
for (int j=L->length; j>i; j--) {
L->data[j] = L->data[j-1];
}
//在第i个位置插入元素
L->data[i-1] = e;
L->length++;
return true;
}
顺序表插入元素的平均时间复杂度是O(n)
删除操作
//删除指定位置的元素
bool ListDelete(SqList *L, int i, ElemType *e) {
//判断位序i是否合法
if (i<1 || i>L->length) {
return false;
}
//保存被删除的元素
*e = L->data[i-1];
//将第i个位置及之后的元素前移
for (int j=i; j<L->length; j++) {
L->data[j-1] = L->data[j];
}
//顺序表长度减1
L->length--;
return true;
}
顺序表删除元素的平均时间复杂度是O(n)
按位查找
//按位查找
bool GetElem(SqList L, int i, ElemType *e) {
//判断位序i是否合法
if (i<1 || i>L.length) {
return false;
}
*e = L.data[i-1];
return true;
}
顺序表按位查找的平均时间复杂度是O(1)
按值查找（顺序查找）
//按值查找
int LocateElem(SqList L, ElemType e) {
for (int i=0; i<L.length; i++) {
if (L.data[i] == e) {
return i+1;
}
}
return 0;
}
顺序表按值查找的平均时间复杂度是O(n)
以上是基于c语言的代码实现，以下是java的代码实现
public class SequentialList {
// 定义常量和数据类型
private static final int MAX_SIZE = 100;
private int[] data;
private int length;
// 构造函数：初始化顺序表
public SequentialList() {
data = new int[MAX_SIZE];
length = 0;
}
// 在指定位置插入元素
public boolean insert(int index, int element) {
// 判断索引是否合法（1~length+1）
if (index < 1 || index > length + 1) {
return false;
}
// 判断顺序表是否已满
if (length >= MAX_SIZE) {
return false;
}
// 将第index个位置及之后的元素后移
for (int j = length; j >= index; j--) {
data[j] = data[j-1];
}
data[index-1] = element; // 在第index个位置插入元素
length++; // 顺序表长度加1
return true;
}
// 删除指定位置的元素
public boolean delete(int index, int[] element) {
// 判断索引是否合法（1~length）
if (index < 1 || index > length) {
return false;
}
element[0] = data[index-1]; // 保存被删除的元素
// 将第index+1个位置及之后的元素前移
for (int j = index; j < length; j++) {
data[j-1] = data[j];
}
length--; // 顺序表长度减1
return true;
}
// 按位查找：获取顺序表中第index个位置的元素
public boolean getElement(int index, int[] element) {
// 判断索引是否合法（1~length）
if (index < 1 || index > length) {
return false;
}
element[0] = data[index-1]; // 将第index个位置的元素赋值给element
return true;
}
// 打印顺序表中的所有元素
public void printList() {
System.out.print("顺序表中的元素: ");
for (int i = 0; i < length; i++) {
System.out.print(data[i] + " ");
}
System.out.println("
顺序表长度: " + length);
}
三.线性表的链式表示
3.1单链表
3.1.1 定义
单链表是一种链式存储结构，通过节点（Node）连接而成。每个节点包含：
- 数据域：存储数据元素的值
- 指针域：存储下一个节点的地址（
null表示无后继节点）
逻辑结构：
head -> Node1 -> Node2 -> ... -> Node(n) -> null
（head为头指针，指向链表第一个节点；最后一个节点的指针域为null）
3.1.2 节点定义
typedef int ElemType;
// 单链表节点结构体
typedef struct LNode {
ElemType data; // 数据域
struct LNode *next; // 指针域，指向下一个节点
} LNode, *LinkList; // LinkList为指向结构体的指针类型
3.1.3 核心操作实现
（1）初始化空链表
// 初始化空链表（带头节点）
bool InitList(LinkList *L) {
*L = (LNode *)malloc(sizeof(LNode)); // 分配头节点
if (*L == NULL) return false; // 内存分配失败
(*L)->next = NULL; // 头节点指针域置空
return true;
}
（2）按位序插入节点
// 在第i个位置插入元素e（带头节点）
bool ListInsert(LinkList L, int i, ElemType e) {
if (i < 1) return false; // 位序i不能小于1
LNode *p = L; // p指向头节点，从第0个位置开始遍历
int j = 0; // 当前位置j=0（头节点位置）
// 找到第i-1个节点
while (p != NULL && j < i-1) {
p = p->next;
j++;
}
if (p == NULL) return false; // i超过链表长度+1
// 创建新节点
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next; // 新节点指向p的后继节点
p->next = s; // p的后继节点改为新节点
return true;
}
（3）按位序删除节点
// 删除第i个位置的元素，并用e返回值（带头节点）
bool ListDelete(LinkList L, int i, ElemType *e) {
if (i < 1) return false;
LNode *p = L;
int j = 0;
// 找到第i-1个节点
while (p != NULL && j < i-1) {
p = p->next;
j++;
}
if (p == NULL || p->next == NULL) return false; // i不合法或链表为空
LNode *q = p->next; // q指向待删除节点
*e = q->data; // 保存删除元素的值
p->next = q->next; // 跳过待删除节点
free(q); // 释放内存
return true;
}
（4）按位序查找节点
// 按位序i查找节点（返回节点指针）
LNode* GetElem(LinkList L, int i) {
if (i < 0) return NULL; // i=0时返回头节点
LNode *p = L;
int j = 0;
while (p != NULL && j < i) {
p = p->next;
j++;
}
return p; // 找到返回节点，否则返回NULL
}
3.1.4 特点
- 优点：
- 动态分配内存，无需预先确定长度
- 插入 / 删除操作无需移动大量元素，时间复杂度为 (O(1))（找到前驱节点后）
- 缺点：
- 无法随机访问元素，按位查找需遍历链表（时间复杂度 (O(n))）
- 存储密度低（每个节点需额外存储指针域）
3.2 双链表
3.2.1 定义
双链表的节点包含两个指针域：
- prior：指向前驱节点
- next：指向后继节点
逻辑结构： head <-> Node1 <-> Node2 <-> ... <-> Node(n) （头节点的prior为null，尾节点的next为null）
3.2.2 节点定义
typedef struct DNode {
ElemType data;
struct DNode *prior; // 前驱指针
struct DNode *next; // 后继指针
} DNode, *DLinkList;
3.2.3 核心操作实现（插入与删除）
（1）插入节点（在 p 节点后插入 s 节点）
void InsertAfter(DNode *p, DNode *s) {
s->next = p->next; // s的后继指向p的后继
if (p->next != NULL) { // 若p不是尾节点，更新后继的前驱
p->next->prior = s;
}
p->next = s; // p的后继指向s
s->prior = p; // s的前驱指向p
}
（2）删除节点（删除 p 节点的后继节点 q）
bool DeleteNext(DNode *p) {
if (p == NULL || p->next == NULL) return false;
DNode *q = p->next; // q为p的后继节点
p->next = q->next; // p的后继改为q的后继
if (q->next != NULL) { // 若q不是尾节点，更新后继的前驱
q->next->prior = p;
}
free(q); // 释放内存
return true;
}
3.2.4 特点
- 优点：
- 支持双向遍历，可快速找到前驱节点
- 插入 / 删除操作更安全（避免单向链表的 “断链” 风险）
- 缺点：
- 结构更复杂，占用内存更多
- 操作需同时维护两个指针域
3.3 循环链表
3.3.1 定义
循环链表是首尾相连的链表，分为单循环链表和双循环链表：
- 单循环链表：尾节点的
next指向头节点 - 双循环链表：头节点的
prior指向尾节点，尾节点的next指向头节点
逻辑结构（单循环链表）： head -> Node1 -> Node2 -> ... -> Node(n) -> head
3.3.2 核心特点
- 判空条件：头节点的
next是否指向自身（单循环链表） - 遍历终止条件：是否回到头节点
- 合并操作：可通过修改首尾节点的指针实现 (O(1)) 时间复杂度合并
3.3.3 单循环链表初始化
// 初始化单循环链表（带头节点）
bool InitCircList(LinkList *L) {
*L = (LNode *)malloc(sizeof(LNode));
if (*L == NULL) return false;
(*L)->next = *L; // 头节点指针指向自身
return true;
}
3.3.4 遍历操作（单循环链表）
void TraverseCircList(LinkList L) {
LNode *p = L->next; // p指向第一个节点
while (p != L) { // 未回到头节点时继续遍历
printf("%d ", p->data);
p = p->next;
}
printf("
");
}
4. 顺序表 vs 链表 对比
| 特性 | 顺序表 | 链表 |
|---|---|---|
| 存储方式 | 连续内存空间 | 离散内存空间，指针连接 |
| 随机访问 | 支持（时间复杂度 (O(1))） | 不支持（需遍历，(O(n))） |
| 插入 / 删除 | 平均 (O(n))（移动元素） | 平均 (O(n))（查找节点） |
| 内存利用率 | 高（无额外指针） | 低（指针占用空间） |
| 适用场景 | 频繁访问、固定长度场景 | 频繁插入 / 删除、动态长度场景 |
总结：
- 若需要高效查询，选顺序表；
- 若需要灵活增删，选链表；
- 循环链表适合环形结构场景（如约瑟夫环问题）；
- 双链表适合双向遍历需求（如文件历史记录）。
------- | --------------------------- | ----------------------------- |
| 存储方式 | 连续内存空间 | 离散内存空间，指针连接 |
| 随机访问 | 支持（时间复杂度 (O(1))） | 不支持（需遍历，(O(n))） |
| 插入 / 删除 | 平均 (O(n))（移动元素） | 平均 (O(n))（查找节点） |
| 内存利用率 | 高（无额外指针） | 低（指针占用空间） |
| 适用场景 | 频繁访问、固定长度场景 | 频繁插入 / 删除、动态长度场景 |
总结：
- 若需要高效查询，选顺序表；
- 若需要灵活增删，选链表；
- 循环链表适合环形结构场景（如约瑟夫环问题）；
- 双链表适合双向遍历需求（如文件历史记录）。
