数据结构是计算机存储，组织数据的方式
空间占用尽量少，以节省计算机内存。数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。提供简洁的数据表示和逻辑信息，以便算法高效运行。链表相较于数组，在数据添加和删除操作上更加便捷，但牺牲了数据访问速度。图相较于链表，提供了更丰富的逻辑信息，但需要占用更大的内存空间。可以看出：数据结构的设计是一个充满权衡的过程
其实数组就是简单的数据结构，一个数组就可以去维护同类型的n个数据，顺序表的底层就是数组，顺序表是对数组的封装
顺序表的概念与结构：
线性表：
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
顺序表的物理结构是连续的，逻辑结构一定是连续的
顺序表的分类：
顺序表的底层是数组，那么顺序表和数组有什么区别呢？
顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝（升级了，也方便了对数组的功能使用）
静态顺序表
静态顺序表(在栈上开空间)缺陷：空间给少了不够⽤，给多了造成空间浪费
其实C++提供了array（静态数组），与C语言的a[]有着区别：
#include
using namespace std;
int main()
{
array
int a2[10];
//区别于越界检查的问题：
//对于静态数组，抽查，正常是在数组后面设置两个标志位
//越界读不检查，越界写检查
cout << a2[10] << endl;
a2[10] = 10;
a2[20] = 10;
//array越界读写都可以检查
//原因是array底层的operator[]加了检查
a1[10];
a1[12] = 10;;
return 0;
}
动态顺序表
动态内存管理，开辟空间：按需申请空间（在堆上开空间）
顺序表带来的问题：
中间/头部的插⼊删除，时间复杂度为O(N) 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。
如何保证程序结束后，历史通讯录信息不会丢失？
为了更直接的体现问题以及思考，下面基于动态顺序表来实现通讯录进而更好的解决问题：
功能要求：
⾄少能够存储100个⼈的通讯信息 能够保存⽤⼾信息：名字、性别、年龄、电话、地址等 增加联系⼈信息 删除指定联系⼈ 查找制定联系⼈ 修改指定联系⼈ 显⽰联系⼈信息历史数据不丢失，要注意指针（传址调用，而不是传值调用），引用便是很好的解决方法(4)
顺序表（例如数组）确实存在一些性能问题，特别是在进行中间或头部的插入和删除操作时，因为这些操作通常需要移动大量元素以维持顺序表的连续性，导致时间复杂度为O(N)。此外，顺序表的增容操作也可能导致性能问题，因为需要申请新空间、复制数据和释放旧空间，这个过程同样需要时间，并且可能会造成空间浪费。
针对这些问题，可以考虑以下几种解决方案：
使用动态数组：动态数组（如C++中的`std::vector`或Java中的`ArrayList`）可以在一定程度上解决增容问题。它们会在需要时自动增加容量，并且通常会使用一种非线性增长策略（例如，每次增加50%的容量），以减少增容操作的频率和空间浪费。使用链表：链表可以提供更灵活的插入和删除操作，因为它们不需要移动其他元素。链表的插入和删除操作的时间复杂度为O(1)，前提是你已经有了要操作的节点的引用。使用平衡树结构：如红黑树、AVL树等，它们可以在保持元素有序的同时，提供对数级别的插入、删除和查找操作。使用哈希表：哈希表提供了平均情况下常数时间的插入、删除和查找操作，但它们不保持元素的顺序。使用跳表：跳表是一种概率型数据结构，它可以提供快速的查找、插入和删除操作，并且保持了有序性。
关于如何保证程序结束后，历史通讯录信息不会丢失，可以采取以下措施：
持久化存储：将通讯录信息存储在文件系统或数据库中，这样即使程序关闭，信息也不会丢失。定期备份：定期将通讯录信息备份到其他存储介质，如外部硬盘或云存储服务。事务日志：使用事务日志记录所有的修改操作，以便在程序崩溃或数据损坏时可以从日志中恢复数据。数据同步：如果通讯录信息分布在多个设备或服务上，确保它们之间定期同步，以防止单点故障导致数据丢失。选择合适的数据结构和存储策略，可以有效地解决顺序表带来的问题，并确保数据的安全性和可靠性。
通讯录的实现代码：
插入操作：
铺垫：
bool IsFull()
{
return _size == _capacity;
}
size_t size()
{
return _size;
}
// 开空间
void reserve(size_t n)
{
size_t old_size = size();
T* tmp = new T[n];
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _arr[i];// 调用赋值：释放旧空间，拷贝新空间
}
delete[] _arr;
_arr = tmp;
_capacity = n;
}
尾插// 尾插一个数据
void push_back(const T& x)
{
if (IsFull())
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
_arr[_size] = x;
_size++;
}
头插//头插一个数据
void push_front(const T& x)
{
if (IsFull())
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
for (int i = size(); i > 0; i--)
{
_arr[i] = _arr[i - 1];
}
_arr[0] = x;
_size++;
}
指定位置前插入 //在指定位置之前插入数据
void insert(size_t pos, const T& x)
{
assert(pos <= size() && pos >= 0);
if (IsFull())
{
reserve(_capacity == 0 ? 4 : _capacity * 2);
}
for (int i = size(); i > pos; i--)
{
_arr[i] = _arr[i - 1];
}
_arr[pos] = x;
_size++;
}
删除操作：
尾删//尾删
void pop_back()
{
assert(_arr && _size > 0);
_size--;
}
头删//头删
void pop_front()
{
assert(_arr && _size > 0);
for (int i = 0; i { _arr[i] = _arr[i + 1]; } _size--; } 在指定位置删除数据//指定位置删除 void erase(size_t pos) { assert(pos >= 0 && pos < size()); for (int i = pos; i < size() - 1; i++) { _arr[i] = _arr[i + 1]; } _size--; } 顺序表实现代码： #pragma once #include #include using namespace std; namespace home { // 动态顺序表 template class SeqList { public: // 全缺省构造函数 SeqList(T* arr = nullptr, size_t size = 0, size_t capacity = 0) :_arr(arr) , _size(size) , _capacity(capacity) {} // 析构函数 ~SeqList() { delete[] _arr; _arr = nullptr; _size = _capacity = 0; } const T& operator[](size_t pos) const { assert(pos < _size);//防止越界 return _arr[pos]; } bool IsFull() { return _size == _capacity; } bool empty() { return _size == 0; } size_t size() { return _size; } // 开空间 void reserve(size_t n) { size_t old_size = size(); T* tmp = new T[n]; for (size_t i = 0; i < old_size; i++) { tmp[i] = _arr[i];// 调用赋值：释放旧空间，拷贝新空间 } delete[] _arr; _arr = tmp; _capacity = n; } // 尾插一个数据 void push_back(const T& x) { if (IsFull()) { reserve(_capacity == 0 ? 4 : _capacity * 2); } _arr[_size] = x; _size++; } //头插一个数据 void push_front(const T& x) { if (IsFull()) { reserve(_capacity == 0 ? 4 : _capacity * 2); } for (int i = size(); i > 0; i--) { _arr[i] = _arr[i - 1]; } _arr[0] = x; _size++; } //尾删 void pop_back() { assert(_arr && _size > 0); _size--; } //头删 void pop_front() { assert(_arr && _size > 0); for (int i = 0; i < size() - 1; i++) { _arr[i] = _arr[i + 1]; } _size--; } //在指定位置之前插入数据 void insert(size_t pos, const T& x) { assert(pos <= size() && pos >= 0); if (IsFull()) { reserve(_capacity == 0 ? 4 : _capacity * 2); } for (int i = size(); i > pos; i--) { _arr[i] = _arr[i - 1]; } _arr[pos] = x; _size++; } //指定位置删除 void erase(size_t pos) { assert(pos >= 0 && pos < size()); for (int i = pos; i < size() - 1; i++) { _arr[i] = _arr[i + 1]; } _size--; } //通通删掉 void clear() { for (int i = 0; i < size(); i++) { pop_back(); } _size = 0; } //查找 int find(const T& x) { assert(_arr); for (int i = 0; i < size(); i++) { if (x == _arr[i]) { return i; } } return -1; } //打印 void Print() { assert(_arr); for (int i = 0; i < size(); i++) { cout << _arr[i] << " "; } cout << endl; } private: T* _arr; size_t _size;// 顺序表当前有效的数据个数 size_t _capacity;// 当前顺序表的容量 }; } 通讯录项目： #include"SeqList.h" #include struct character_information { string _name; string _gender; size_t _age; string _phone_code; string _address; }; int main() { cout << "---------通讯录----------" << endl; home::SeqList int n = 0; cin >> n; while (n--) { struct character_information infor; cout << "name:" << endl; cin >> infor._name; cout << "gender:" << endl; cin >> infor._gender; cout << "age:" << endl; cin >> infor._age; cout << "phone_code:" << endl; cin >> infor._phone_code; cout << "address:" << endl; cin >> infor._address; sl.push_back(infor); } //sl.Print();原有不可用 //... return 0; }