顺序表的定义
顺序表（SqList）用顺序存储的方式实现线性表的顺序存储
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现
很显然通常使用数组 
数据类型是相同的所以每个数据元素占的空间是一样大的。
数据元素的大小可以在C++中用 sizeof() 函数获取，多用于获取自定义结构体的空间大小。
顺序表的实现
静态分配
#define N 10 //顺序表最大长度
typedef struct {
size_t data[N]; //分出一个最大长度的静态数组用来存放元素
int length; //当前的顺序表长度
} SqList; //sequence序列
声明顺序表的方法
#include <iostream>
using namespace std;
#define N 10;
typedef struct {
int d[N];
int length;
} SqList;
int main {
SqList L; //声明一个顺序表L；
}
初始化顺序表的方法
#include <iostream>
using namespace std;
#define N 10;
typedef struct {
int d[N];
int length;
} SqList;
void initSqList(SqList &L) {
for (int i = 0; i < N; i++) {
L.d[i] = 0; //所有数据元素默认初始值（可省略）
}
L.length = 0; //初始长度为0
}
int main {
SqList L; //声明一个顺序表L；
}
不设置默认值在遍历到最大值时会导致数组中有脏数据；但这是违规操作，我们使用length定义了这个顺序表的长度如果没有数据进入length不会进行增加 循环自然不会执行也自然没有脏数据产生
下面是正确的输出，但最好的方式是实现一个GetElement函数进行访问各项数据元素
for (int i = 0; i < L.length(); i++) {
cout << L.d[i] << ' ';
}
重点：
问题：静态分配的数据存满了怎么办？
答案：放弃 无法更改，数组的长度都是分配好的，C++可以使用vector解决这个问题 或者手动动态分配 如下
动态分配
#include <stdlib.h>
#define InitSize 10 // 初始默认长度
typedef struct {
int *data; // 指向动态分配数组的指针
int MaxSize; // 顺序表的最大容量
int length; // 顺序表的当前长度
} SeqList;
// 初始化顺序表
void InitList(SeqList &L) {
// 使用 malloc 申请初始空间
L.data = (int *)malloc(InitSize * sizeof(int));
//可以使用string.h中的memset给这一段空间赋初始值
//memset(L.data, 0, InitSize * sizeof(int));
L.length = 0;
L.MaxSize = InitSize;
}
// 增加动态数组的长度
void IncreaseSize(SeqList &L, int len) {
int *p = L.data; // 暂存原数据指针
// 申请一片更大的新空间
L.data = (int *)malloc((L.MaxSize + len) * sizeof(int));
// 将原有数据复制到新区域
for (int i = 0; i < L.length; i++) {
L.data[i] = p[i];
}
L.MaxSize = L.MaxSize + len; // 更新最大容量
free(p); // 释放旧的内存空间
}
int main() {
int len;
cin >> len;
SeqList L;
init_seqlist(L);
increasesize(L, len);
for (int i = 0; i < initlength + len; i++) {
cout << L.data[i] << ' ';
}
return 0;
}
L.data 扩容的本质不是“把旧房子变大”，而是“搬到了一个更大的新家”
而此时指针 *p还指向换位前的老地址 所以可以使用free直接清楚老地址的内存
重点：
C++ STL 提供了
std::vector，可以自动管理动态数组。为什么不用？因为学的就是底层怎么实现的。。。。。
重点：
malloc: 申请一块指定大小的内存。free: 释放内存，防止内存泄漏。realloc(扩容核心): 尝试在原地址基础上扩容。如果后面没空位了，它会自动找块新地盘，把数据拷过去，并把旧地盘释放掉。
提示：
既然realloc可以扩容 那么我们为什么要用malloc 分一块新空间然后拷贝过去呢？
下面一段是来自于Gemini的答案：
realloc的“暴力”拷贝
realloc扩容时，如果原地址后面没空间，它会申请新空间并使用memcpy（按字节拷贝）把数据搬过去。
- 对于简单类型（如
int,double），这没问题。- 对于复杂对象，
memcpy会直接破坏对象的内部结构（比如指向自身的指针、虚函数表等）。在 C++ 中，搬移对象应该使用拷贝构造函数或移动构造函数。应该使用realloc的场景：
- 纯 C 语言环境：C 语言没有
new/delete，realloc是实现动态数组（顺序表）的唯一正统写法。- 处理 POD 类型：POD（Plain Old Data）指的是像
int、char或只包含基本类型的简单结构体。对于这些类型，realloc的字节拷贝性能极高。- 嵌入式底层：在内存极度受限、不使用 C++ 特性的底层驱动开发中。
C++环境强推面向对象new的实现方法
重点：
顺序表特点：
- 随机访问可以在O(1)的时间复杂度下找到第i个元素即d[i-1]
- 存储密度高，每个节点只存储数据元素
- 拓展容量不方便（动态拓展时间复杂度也很高）
- 插入删除不方便需要移动大量元素
面向对象实现顺序表
#include <iostream>
#include <vector>
#include <algorithm> // 用于 std::find
template <typename T>
class SeqList {
private:
std::vector<T> data; // 使用 vector 作为底层存储
public:
// 1. 插入：在末尾添加
void pushBack(const T& value) {
data.push_back(value);
}
// 2. 插入：在指定索引处插入
bool insert(int index, const T& value) {
if (index < 0 || index > data.size()) return false;
data.insert(data.begin() + index, value);
return true;
}
// 3. 删除：按索引删除
bool removeAt(int index) {
if (index < 0 || index >= data.size()) return false;
data.erase(data.begin() + index);
return true;
}
// 4. 查找：返回第一个匹配项的索引，找不到返回 -1
int find(const T& value) {
auto it = std::find(data.begin(), data.end(), value);
if (it != data.end()) {
return std::distance(data.begin(), it);
}
return -1;
}
// 5. 修改
bool update(int index, const T& value) {
if (index < 0 || index >= data.size()) return false;
data[index] = value;
return true;
}
// 6. 打印顺序表
void display() const {
std::cout << "SeqList: [ ";
for (const auto& item : data) {
std::cout << item << " ";
}
std::cout << "]" << " (Size: " << data.size() << ")" << std::endl;
}
// 获取当前长度
size_t size() const { return data.size(); }
};
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。