当前位置：首页 > java >正文

【C++】全套数据结构算法-线性表讲解（1）

java 2025/7/12 14:29:25

1. 数组

1.1 数组定义

1.2 数组特性

1.3 数组代码输出

1.3.1 内存知识补充：

1.3.2 代码实现

2. 链表

2.1 链表的定义

2.1 单链表

2.1.1 头结点

2.1.2 尾插法代码实现

2.1.3 头插法代码实现

2.1.4 链表结点的删除

2.1.5 代码实现

1. 数组

1.1 数组定义

C/C++中，数组的定义需要使用常量（可以是宏定义的常量）
数组的下标从0开始，arr[0]~arr[9]，arr[10]会出现访问越界
可以使用一个cur来储存数组中的元素个数（同时用来进行末尾的删除和添加）
图中就可以看出，想要在非末尾位置添加/删除一个元素，需要移动元素来腾出/填充位置

【注意】区分什么是查找/搜索？什么是下标/随机访问？

1.2 数组特性

特点：

数组内存是连续的

优点：

下标访问（随机访问）时间复杂度是 $O\left ( 1\right )$

末尾元素删除和添加时间复杂度是 $O\left ( 1\right )$

访问某元素的前后位置的元素很方便

缺点：

非末尾添加和删除元素需要移动大量的数据

搜索的时间复杂度

有序数组-线性搜索 $O\left ( n\right )$

无序数组-二分搜索 $O\left ( \log n\right )$

数组扩容消耗比较大

1.3 数组代码输出

1.3.1 内存知识补充：

C/C++程序运行过程中，内存主要分为.data（数据段）、heap（堆）、stack（栈）。

一般来说，创建一个可扩容的数组，需要将其定义在heap（堆）上
.data的数组大小固定（在编译时确定）
stack的数组大小固定（虽然是在运行时确定，但是后续无法改变）

1.3.2 代码实现

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;//数组实现
class Array
{
public:Array(int size = 10) :mCur(0), mCap(size){mpArr = new int[mCap];}~Array(){delete []mpArr;mpArr = nullptr;}public://末尾增加元素void push_back(int val) {if (mCur == mCap){expand(2 * mCap);}mpArr[mCur++] = val;}//末尾删除元素void pop_back(){if (mCur == 0){return;}mCur--;}//按位置增加元素void insert(int pos, int val){if (pos < 0 || pos > mCur){throw "pos invalid!";}if (mCur == mCap){expand(2 * mCap);}//移动元素for (int i = mCur-1; i >= pos; i--){mpArr[i + 1] = mpArr[i];}mpArr[pos] = val;mCur++;}//元素查询int find(int val){for (int i = 0; i < mCur; i++){if (val == mpArr[i]){return i;}}return -1;}//按元素删除void erase(int pos){if (pos < 0 || pos >= mCur){throw "pos invalid!";}for (int i = pos + 1; i < mCur; i++){mpArr[i-1] = mpArr[i];}mCur--;}//修改指定元素void change(int val,int elem){int pos = find(val);if (pos >= 0){mpArr[pos] = elem;}else{throw "val not exist!";}}void show()const{for (int i = 0; i < mCur; i++){cout << mpArr[i] << " ";}cout << endl;}private://数组扩容接口void expand(int size){int* p = new int[size];	//开辟新的内存memcpy(p, mpArr, sizeof(int) * mCap);	//拷贝数据delete[]mpArr;mpArr = p;mCap = size;}
public:int* mpArr;	//指向可扩容的数组内存int mCap;	//数组的容量int mCur;	//有效元素个数
};int main()
{Array arr;srand(time(0));for (int i = 0; i < 10; i++){arr.push_back(rand() % 100);}arr.show();arr.erase(5);arr.show();arr.insert(2, 108);arr.show();arr.change(108, 100);arr.show();arr.pop_back();arr.show();return 0;
}

2. 链表

数组可以解决很多问题，为什么还需要使用链表呢？这里要结合数组的特性来解释：

假设我们有100MB内存，依次分配掉了30MB、20MB、40MB、10MB，然后因为不同内存对应的业务周期不同，所有释放的时间肯定也不同：

此时有20MB和10MB已经被释放掉，但注意在内存中这空闲的两段内存是不连续的。如果我此时想要定义一个25MB大小的数组，我们根据数组的特性（数组的空间内存是连续的），而很明显图中已经没有连续的25MB的内存了。而这段红色和绿色的就叫做内存碎片。

2.1 链表的定义

链表中的结点都是独立分配出来的
从当前节点能够找到下一个节点
每一个结点由两部分组成data（数据域）、next（地址域）
地址域中储存的是下一个结点的地址
最后一个结点的地址域是nullptr

2.1 单链表

struct Node
{int data;Node* next;
};
单链表中只储存了下一个结点的地址，所以并不能找到前一个结点的数据。

2.1.1 头结点

头结点存在的意义，是简化链表操作逻辑，尤其是在插入、删除或处理边界条件时。它牺牲了少量空间（一个额外结点），但显著提升了代码的简洁性和健壮性。

2.1.2 尾插法代码实现

如上是一个已经有结点存在的单链表，尾插法顾名思义就是将新结点在链表的末尾处插入，所以关键的步骤就是要找到最后一个结点。而链表相较于数组不同的地方就在于，不能够随机访问，所以应该采取从头结点遍历链表的方式找到，遍历结束的条件也就是尾结点的特征（地址域为空）：
Node* p =head;    //从头结点开始
while(p-> next != nullptr)p = p->next;    //最后找到尾结点
找到了尾结点之后，将新结点连接到尾结点后面：
Node* node = new Node(val);
p->next_ = node;
同理可以知道，就算原来链表是空的，这段代码也同样成立，因为循环会在头结点就结束。

2.1.3 头插法代码实现

相较于尾插法，头插法是将新结点始终放在头结点的后面（也就是头结点和原来第一个结点之间），这里我们思考一下，我需要通过改变头结点、新结点、原第一个结点（如果有的话）之间的连接来实现头插法。

如果我很直接地，将头结点的地址域指向新结点，然后再将新结点的地址域指向原第一个结点，就会出现一个问题，那就是我怎么找到原第一个结点的地址呢？

有人会说，我的头结点不是存放了吗，但是注意的是，此时你已经头结点的地址域指向了新结点，所以已经丢失了原第一个结点的地址，所以这个连接顺序是不可取的。

我们试着换一个顺序，先将新结点的地址域指向原第一个结点的地址，然后再将头结点的地址域指向新结点的地址：
Node* node = new Node(val);
node->next_ = head_->next_;
head_->next_ = node;

2.1.4 链表结点的删除

这里给出一个单链表：

现在我的目的是删除数据域为52的结点，我应该怎么做呢？

从头结点开始遍历
找到数据域为52的结点
然后删除这个结点

我们逐步来完成：

从头结点开始
Node* p = head->next;
找到数据域为52的结点
while(p!=nullptr)
{if(p->data==val){}else{}
}
删除结点

我们思考一下怎样才能做到删除结点呢？

直观上来讲，我们需要将52这个结点给挖掉，但是为了整个链表的有效性，我们需要将断开后的链表连接上。但是会发现一个问题，就是当指针p逐步移动找到数据域为52的结点时，我们就已经丢失前一个结点地址域中的信息了，因为单链表是不能逆向访问的。

我们想到的解决办法是，既然一个指针不够，我们就使用两个指针p、q（是的p永远跟在q的后面）来解决这个问题：
Node* q = head;
Node* p = head->next;
然后进行删除操作：
if(p->data==val)
{q->next=p->next;delete p;
}
else
{q=p;    //q=q->next;p=p->next;
}

2.1.5 代码实现

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;//结点类型
struct Node
{Node(int data = 0) :data_(data), next_(nullptr){}int data_;Node* next_;
};//单链表代码实现
class Clink
{
public:Clink(){//初始化头结点head_ = new Node();}~Clink(){//结点的释放}public://链表尾插法void InsertTail(int val){//找到当前链表的末尾结点Node* p = head_;while (p->next_ != nullptr){p = p->next_;}Node* node = new Node(val);p->next_ = node;}//链表头插法void InsertHead(int val){Node* node = new Node(val);node->next_ = head_->next_;head_->next_ = node;}//打印链表void show(){Node* p = head_->next_;while (p != nullptr){cout << p->data_ << " ";p = p->next_;}cout << endl;}void Remove(int val){Node* q = head_;Node* p = head_->next_;while (p != nullptr){if (p->data_ == val){q->next_ = p->next_;delete p;return;}else{q = p;    //q=q->next;p = p->next_;}}}
private:Node* head_;
};int main()
{Clink link;srand(time(0));for (int i = 0; i < 10; i++){int val = rand() % 100;link.InsertTail(val);cout << val << " ";}cout << endl;link.InsertTail(200);link.show();link.Remove(200);link.show();return 0;
}

2.1.6 思考题

将Remove()代码改进为能够删除多个相同值？
while (p != nullptr)
{if (p->data_ == val){q->next_ = p->next_;delete p;p = q->next_;}else{q = p;    //q=q->next;p = p->next_;}
}

（本篇完）

查看全文

http://www.xdnf.cn/news/15112.html