前言：
这份笔记，是我在学习数据结构过程中记下的笔记，并未完全遵循专业课的既定顺序与讲授逻辑。
于数据结构而言，这门学科从无捷径可走 —— 若想真正学懂吃透，核心唯有 “多练、多敲”。在此必须坦诚：我并不认同所谓的 “四件套速通课”，这类课程往往只能带你浅尝皮毛，难以触及知识的核心与本质。
如果你想要紧跟课堂进度，那么匹配课程的幻灯片会是更直接的参考（当然，前提是你能沉下心去研读）。不过市面上多数数据结构相关的书籍与幻灯片，存在一个共性问题：伪代码占比过高。若盲目照着这些伪代码直接编写，最终能成功运行的概率恐怕不足 10%。
正因如此，若你不嫌弃这份笔记的随性与朴实，我十分欢迎你将其作为学习参考。希望这些基于我个人实践的记录，能帮你更轻松地理解数据结构的逻辑，辅助你的学习之路。实现代码分为C语言描述与C++语言描述，各位按需获取。
最后说下这份笔记的使用建议：文中并未设置严格的章节划分，你大可以像读小说一样轻松浏览。唯独遇到具体的代码实现部分时，建议你停下脚步 —— 先完整读懂代码逻辑，再关掉笔记，试着独立敲写出属于自己的版本。唯有亲手实践，才能将知识真正内化为自己的能力。
By：ItsJiale
2025.10.1
第三章 线性表
线性表
由 n（ n ⩾0 ）个数据特性相同的元素构成的有限序列，称为线性表。
线性表是 n 个数据元素的有限序列，其中 n 个数据是相同数据类型的。
线性表中元素的个数 n（ n ⩾0 ）定义为线性表的长度，当 n=0 时称之为空表。
对于非空的线性表或线性结构，其特点是：
存在唯一的一个被称作“第一个”的数据元素；
存在唯一的一个被称作“最后一个”的数据元素；
除第一个元素外，结构中的每个数据元素均只有一个前驱；
除最后一个元素外，结构中的每个数据元素均只有一个后继。
顺序表
用一组连续的内存单元依次存储线性表的各个元素，也就是说，逻辑上相邻的元素，实际的物理存储空间也是连续的。
注意：顺序表的内存连续！！！
顺序表需要实现增删插遍历
这时候就有可爱的小朋友问了：为什么要做这么复杂？C++里面不是有vector/STL能够直接实现吗？
可是我们现在是用C实现呀，尽管C++本身就有但总得知道底层是怎么来的吧？C++有vector，Java有ArrayList，都实现了动态数组，但是C只有静态数组，所以在基础学习阶段知其所以然更重要
顺序表——定义
#include <stdio.h>
#define MAXSIZE 100
typedef int ElemType;
//顺序表定义
typedef struct{
ElemType data[MAXSIZE];
int length;
}SeqList;解读：为什么要用typedef给int取别名？
因为你不知道真实的情况到底使用int还是用double或者其他，如果每次都要写int，以后改double的时候每处int都要改，增大了工作量，所以为了规范，一般都会写别名，如果需要直接把int改成double
顺序表——初始化
//顺序表初始化
void initList(SeqList *L)
{
L->length = 0;
}解读：传入一个指针，使用L->length = 0;初始化顺序表列表为0
顺序表——在尾部添加元素
//尾部添加元素
int appendElem(SeqList *L, ElemType e)
{
if (L->length>=MAXSIZE)
{
printf("顺序表已满\n");
return 0;
}
L->data[L->length] = e;
L->length++;
return 1;
}解读：传入一个指针，判断长度是否大于容量，然后将e赋值给L->data[L->length]（这里是数组下标L->data[？]），最后length++自增，返回一个1表示成功添加
顺序表——遍历
//遍历
void listElem(SeqList *L)
{
for (int i = 0; i < L->length; i++)
{
printf("%d ", L->data[i]);
}
printf("\n");
}解读：用for循环遍历data
顺序表——插入数据
插入的过程，插入位置后面的元素集体依次移后一位，再将新元素插入到pos上
//插入数据
int insertElem(SeqList *L, int pos, ElemType e)
{
if(L->length >= MAXSIZE)
{
printf("表已经满了\n");
return 0;
}
if (pos < 1 || pos > L->length)
{
printf("插入位置错误\n");
return 0;
}
if (pos <= L->length)
{
for (int i = L->length-1; i >= pos-1; i--)
{
L->data[i+1] = L->data[i];
}
L->data[pos-1] = e;
L->length++;
}
return 1;
}解读：传入一个指针、位置和插入的数据。进行相关判断，从后往前遍历（提问：从前往后不行吗？不行！因为从前往后会把后一个数据覆盖掉，造成数据丢失！！），将前一个元素赋值给后一个元素，直到pos-1为止（提问：为什么是pos-1？因为pos是位置，下标是从0开始的，所以必须要-1；length-1也是如此）。最后将e的值赋给data[pos-1]，length++自增
顺序表——删除数据
//删除数据
int deleteElem(SeqList *L, int pos, ElemType *e)
{
if(L->length == 0)
{
printf("空表\n");
return 0;
}
if (pos < 1 || pos > L->length)
{
printf("删除数据位置有误\n");
return 0;
}
*e = L->data[pos-1];
if (pos < L->length)
{
for (int i = pos; i < L->length; i++)
{
L->data[i-1] = L->data[i];
}
}
L->length--;
return 1;
}解读：传入一个指针，pos位置，以及指针e（为什么？因为可能会有展示所删除数据的需求，所以先用指针接）。进行相关判断，将要删除的元素用*e去接取，用for循环从前遍历，将后一个元素赋值给前一个元素，最后length--自减
顺序表——查找元素
//查找数据位置
int findElem(SeqList *L, ElemType e)
{
if (L->length == 0)
{
printf("空列表\n");
return 0;
}
for (int i = 0; i < L->length; i++)
{
if(L->data[i] == e)
{
return i + 1;
}
}
return 0;
}解读：没什么好说的，用for循环查找匹配的元素，返回一个i+1（为什么不是返回i，因为i是下标，i+1是位置）
主函数如下：
int main(int argc, char const *argv[])
{
//声明一个线性表并初始化
SeqList list;
initList(&list);
printf("初始化成功，目前长度占用%d\n",list.length);
printf("目前占用内存%zu字节\n", sizeof(list.data));
appendElem(&list, 88);
appendElem(&list, 67);
appendElem(&list, 40);
appendElem(&list, 8);
appendElem(&list, 23);
listElem(&list);
insertElem(&list, 1, 18);
listElem(&list);
ElemType delData;
deleteElem(&list, 2, &delData);
printf("被删除的数据为：%d\n", delData);
listElem(&list);
printf("%d\n", findElem(&list, 40));
return 0;
}
C语言无动态内存分配——完整版本（栈内存）
#include <stdio.h>
#define MAXSIZE 100
typedef int ElemType;
//顺序表定义
typedef struct{
ElemType data[MAXSIZE];
int length;
}SeqList;
//顺序表初始化
void initList(SeqList *L)
{
L->length = 0;
}
//尾部添加元素
int appendElem(SeqList *L, ElemType e)
{
if (L->length>=MAXSIZE)
{
printf("顺序表已满\n");
return 0;
}
L->data[L->length] = e;
L->length++;
return 1;
}
//遍历
void listElem(SeqList *L)
{
for (int i = 0; i < L->length; i++)
{
printf("%d ", L->data[i]);
}
printf("\n");
}
//插入数据
int insertElem(SeqList *L, int pos, ElemType e)
{
if(L->length >= MAXSIZE)
{
printf("表已经满了\n");
return 0;
}
if (pos < 1 || pos > L->length)
{
printf("插入位置错误\n");
return 0;
}
if (pos <= L->length)
{
for (int i = L->length-1; i >= pos-1; i--)
{
L->data[i+1] = L->data[i];
}
L->data[pos-1] = e;
L->length++;
}
return 1;
}
//删除数据
int deleteElem(SeqList *L, int pos, ElemType *e)
{
if(L->length == 0)
{
printf("空表\n");
return 0;
}
if (pos < 1 || pos > L->length)
{
printf("删除数据位置有误\n");
return 0;
}
*e = L->data[pos-1];
if (pos < L->length)
{
for (int i = pos; i < L->length; i++)
{
L->data[i-1] = L->data[i];
}
}
L->length--;
return 1;
}
//查找数据位置
int findElem(SeqList *L, ElemType e)
{
if (L->length == 0)
{
printf("空列表\n");
return 0;
}
for (int i = 0; i < L->length; i++)
{
if(L->data[i] == e)
{
return i + 1;
}
}
return 0;
}
int main(int argc, char const *argv[])
{
//声明一个线性表并初始化
SeqList list;
initList(&list);
printf("初始化成功，目前长度占用%d\n",list.length);
printf("目前占用内存%zu字节\n", sizeof(list.data));
appendElem(&list, 88);
appendElem(&list, 67);
appendElem(&list, 40);
appendElem(&list, 8);
appendElem(&list, 23);
listElem(&list);
insertElem(&list, 1, 18);
listElem(&list);
ElemType delData;
deleteElem(&list, 2, &delData);
printf("被删除的数据为：%d\n", delData);
listElem(&list);
printf("%d\n", findElem(&list, 40));
return 0;
}顺序表——动态内存分配
//顺序表初始化－动态分配内存
SeqList* initList()
{
SeqList *L = (SeqList*)malloc(sizeof(SeqList));
L->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
L->length = 0;
return L;
}解读：其实动态内存分配就是在初始化的时候用malloc开辟了一个指向堆内存的顺序表，(SeqList*)malloc(sizeof(SeqList));指的是用malloc方法开辟了个大小为（sizeof(SeqList)）的(SeqList)的顺序表，malloc（）后面参数是大小，因为sizeof就是字节大小的方法，所以就这么写，前面(SeqList)是一个明确开辟什么类型的堆内存，最后用SeqList *L来接取。其他方法与先前无差别
C语言动态内存分配——完整版本（堆内存）
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef int ElemType;
//顺序表定义
typedef struct{
ElemType *data;
int length;
}SeqList;
//顺序表初始化－动态分配内存
SeqList* initList()
{
SeqList *L = (SeqList*)malloc(sizeof(SeqList));
L->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
L->length = 0;
return L;
}
//尾部添加元素
int appendElem(SeqList *L, ElemType e)
{
if (L->length>=MAXSIZE)
{
printf("顺序表已满\n");
return 0;
}
L->data[L->length] = e;
L->length++;
return 1;
}
//遍历
void listElem(SeqList *L)
{
for (int i = 0; i < L->length; i++)
{
printf("%d ", L->data[i]);
}
printf("\n");
}
//插入数据
int insertElem(SeqList *L, int pos, ElemType e)
{
if(L->length >= MAXSIZE)
{
printf("表已经满了\n");
return 0;
}
if (pos < 1 || pos > L->length)
{
printf("插入位置错误\n");
return 0;
}
if (pos <= L->length)
{
for (int i = L->length-1; i >= pos-1; i--)
{
L->data[i+1] = L->data[i];
}
L->data[pos-1] = e;
L->length++;
}
return 1;
}
//删除数据
int deleteElem(SeqList *L, int pos, ElemType *e)
{
if(L->length == 0)
{
printf("空表\n");
return 0;
}
if (pos < 1 || pos > L->length)
{
printf("删除数据位置有误\n");
return 0;
}
*e = L->data[pos-1];
if (pos < L->length)
{
for (int i = pos; i < L->length; i++)
{
L->data[i-1] = L->data[i];
}
}
L->length--;
return 1;
}
//查找数据位置
int findElem(SeqList *L, ElemType e)
{
if (L->length == 0)
{
printf("空列表\n");
return 0;
}
for (int i = 0; i < L->length; i++)
{
if(L->data[i] == e)
{
return i + 1;
}
}
return 0;
}
int main(int argc, char const *argv[])
{
//声明一个线性表并初始化
SeqList *list = initList();
printf("初始化成功，目前长度占用%d\n",list->length);
printf("目前占用内存%zu字节\n", sizeof(list->data));
appendElem(list, 88);
appendElem(list, 67);
appendElem(list, 40);
appendElem(list, 8);
appendElem(list, 23);
listElem(list);
insertElem(list, 1, 18);
listElem(list);
ElemType delData;
deleteElem(list, 2, &delData);
printf("被删除的数据为：%d\n", delData);
listElem(list);
printf("%d\n", findElem(list, 40));
return 0;
}注意发现main函数中，似乎发生了点变化，【&】取地址符不见了，为什么不见，留给各位思考。
骗你们的，能看到这里的人不超过五个，还想让你们思考？比登天都难。因为用malloc的list是指针变量（指向动态分配的结构体），因此函数参数直接传递 list（本身就是地址）；而无动态内存分配的版本list是结构体变量（在栈上分配），因此函数参数需要传递 &list（取地址得到指针）
下面是C++语言版的线性表，方法也一样，就不一一讲解了
//顺序表+动态内存分配（c++语言版）
#include<iostream>
using namespace std;
typedef int Element;
class SeqList{
private:
Element *data;
int length;
int capacity;
void expand(){
if (length < capacity) {
return;
}
int newCapacity;
if (capacity == 0) {
newCapacity = 10;
} else {
newCapacity = capacity * 2;
}
Element *newData = new Element[newCapacity];
for (int i = 0; i < length; i++) {
newData[i] = data[i];
}
if (data !=nullptr)
{
delete[] data;
}
data = newData;
capacity = newCapacity;
cout<<"顺序表已扩容，新容量为："<<capacity<<endl;
}
public:
SeqList(){
data = nullptr;
length = 0;
capacity = 0 ;
expand();
}
~SeqList(){
if (data !=nullptr)
{
delete[] data;
data = nullptr;
}
}
int append(Element e){
expand();
data[length] = e;
length++;
return 1;
}
void show(){
for (int i = 0; i < length; i++)
{
cout<< data[i] <<" ";
}
}
int deleteEle(int pos,Element &e){
if (pos > length || pos<=0)
{
cout<<"位置错误"<<endl;
return 0;
}
if (length == 0)
{
cout<< "为空表，无法删除"<<endl;
return 0;
}
e = data[pos-1];
for (int i = pos; i < length; i++)
{
data[i-1] = data[i];
}
length--;
return 1;
}
int insertEle(int pos, Element e){
if (pos<1 || pos>length)
{
cout<<"插入位置错误"<<endl;
return 0;
}
expand();
for (int i = length-1 ;i >= pos-1; i--)
{
data[i+1] = data [i];
}
data[pos-1] =e;
length++;
return 1;
}
int findEle(Element e){
if (length==0)
{
cout<<"为空表"<<endl;
return 0;
}
for (int i = 0; i < length-1; i++)
{
if(data[i]==e)
return i+1;
}
return 0;
}
int getLength(){
return length;
}
int getCapacity(){
return capacity;
}
int getMemorySize(){
return capacity * sizeof(Element);
}
};
int main() {
SeqList list; // 创建对象（自动调用构造函数初始化）
cout << "初始化成功，目前长度：" << list.getLength()
<< "，当前容量：" << list.getCapacity() << endl;
cout << "目前占用内存：" << list.getMemorySize() << "字节" << endl;
// 添加元素
list.append(88);
list.append(67);
list.append(40);
list.append(8);
list.append(23);
list.append(99); // 触发扩容
// 显示当前元素
cout << "添加元素后：";
list.show();
cout << endl;
// 插入元素
list.insertEle(1, 18);
cout << "插入元素后：";
list.show();
cout << endl;
// 删除元素
Element delData;
if (list.deleteEle(2, delData)) {
cout << "被删除的数据为：" << delData << endl;
}
cout << "删除元素后：";
list.show();
cout << endl;
// 查找元素
int pos = list.findEle(40);
if (pos != 0) {
cout << "元素40的位置是：" << pos << endl;
} else {
cout << "未找到元素40" << endl;
}
cout << "最终容量：" << list.getCapacity()
<< "，占用内存：" << list.getMemorySize() << "字节" << endl;
// 对象销毁时自动调用析构函数释放内存，无需手动操作
return 0;
}
算了，还是讲一下吧，毕竟各位还有C++的基础（真的吗？）。只讲解不同的方面。
class SeqList{
private:
Element *data;
int length;
int capacity;解读：这里用了类，采用了封装的思想，本质跟C的结构体一致
void expand(){
if (length < capacity) {
return;
}
int newCapacity;
if (capacity == 0) {
newCapacity = 10;
} else {
newCapacity = capacity * 2;
}
Element *newData = new Element[newCapacity];
for (int i = 0; i < length; i++) {
newData[i] = data[i];
}
if (data !=nullptr)
{
delete[] data;
}
data = newData;
capacity = newCapacity;
cout<<"顺序表已扩容，新容量为："<<capacity<<endl;
}解读：这里新增了一个扩容的思路，当调用这个函数的时候会将容量扩展为原来的两倍。Element *newData = new Element[newCapacity];可以看到，这里采用了动态内存分配，使用new关键字在堆内存开辟
public:
SeqList(){
data = nullptr;
length = 0;
capacity = 0 ;
expand();
}
~SeqList(){
if (data !=nullptr)
{
delete[] data;
data = nullptr;
}
}解读：初始化构造函数，将data的值为空指针，长度为0，容量为0，最后使用expand（）容量变成10；析构函数，在调用析构函数时，如果data不为空，就用delete关键字将data的内容删除，使data指向空指针
需要说明的一点是，方法全在类中，可以相互调用，这样就不用在形参列表中传入指针/数组了。