课程进度 13% · 第2/10章第2/10章 · 标签 1/4
— 1 —
线性表抽象与存储
线性表是一种元素线性排列的数据结构，分为顺序存储（数组）和链式存储（链表）。
- ADT定义：支持插入、删除、查找、遍历、逆置等操作
- 顺序存储：内存连续，支持O(1)随机访问
- 链式存储：节点分散，插入/删除高效，不支持随机访问
📖线性表是数组、链表、栈、队列等结构的基础，选择存储方式需结合实际应用场景。
数组与顺序表
数组是最常用的顺序存储结构，C++ STL的vector底层即为动态数组。下面是一个支持插入、删除、查找、扩容的顺序表完整实现：
cpp
1
// 顺序表类（支持插入、删除、查找、扩容）
2
class SeqList {
3
int* data; int cap, len;
4
public:
5
SeqList(int c=8):cap(c),len(0){data=new int[cap];}
6
~SeqList(){delete[] data;}
7
void push_back(int x){
8
if(len==cap){ // 扩容
9
int* nd=new int[cap*2];
10
for(int i=0;i<len;++i)nd[i]=data[i];
11
delete[] data; data=nd; cap*=2;
12
}
13
data[len++]=x;
14
}
15
void insert(int pos, int x){
16
if(pos<0||pos>len) return;
17
if(len==cap){int* nd=new int[cap*2];for(int i=0;i<len;++i)nd[i]=data[i];delete[] data;data=nd;cap*=2;}
18
for(int i=len;i>pos;--i)data[i]=data[i-1];
19
data[pos]=x; ++len;
20
}
21
void erase(int pos){
22
if(pos<0||pos>=len) return;
23
for(int i=pos;i<len-1;++i)data[i]=data[i+1];
24
--len;
25
}
26
int find(int x){
27
for(int i=0;i<len;++i)if(data[i]==x)return i;
28
return -1;
29
}
30
int& operator[](int i){return data[i];}
31
int size(){return len;}
32
};
33
// 使用
34
SeqList sl; sl.push_back(1); sl.insert(1,2); sl.erase(0); int idx=sl.find(2);
— 2 —
典型例题：二分查找
cpp
1
// 二分查找（有序数组）
2
int binarySearch(vector<int>& arr, int target) {
3
int l=0, r=arr.size()-1;
4
while(l<=r){
5
int m=l+(r-l)/2;
6
if(arr[m]==target) return m;
7
else if(arr[m]<target) l=m+1;
8
else r=m-1;
9
}
10
return -1;
11
}
线性表顺序存储链式存储ADT二分查找