1. 线性表

  • 同类型数据结构的有序数列
  • 每个元素仅有一个直接前驱和直接后继（除了表头和表尾）

1.1 线性表数组存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class LinearList{
	private:
	int *data[MAXSIZE];
	int size;
	public:
	LinearList(int initialCapacity=MAXSIZE){
		data=new int[innitialCapacity];
		//new分配的内存在堆上，用于动态管理
		int size=0;
		int capacity=MAXSIZE;
	}
	~LinearList(){
		delete []data;
	}
	
	int find_pos(int index){
		if(inidex<0 || index>=size) return NULL;
		else return data[index];
	}
	int find_value(int value){
		result=-1;
		for(int i=0;i<size;i++){
			if(value==data[i]){
				result=i;
				break;
			}
		}
		return result;
	}
	
	// 插入：先挪后放
	void insert(int index, const int& value){
		if(index<0 || index>size || size==MAXSIZE){
			cout<<"error"<<endl;
			return 0;
		}
		for (int i=size;i>index;--i) data[i]=data[i-1];
		data[index]=value;
		size++;
		return;
	}
	// 时间复杂度：o(n)
	
	void doublespace{
		newcapacity=capacity*2;
		int *newData = new int[newcapacity];
		for(int i=0;i<size;i++) newData[i]=data[i];
		delete[] data;
		data=newData;
		capacity=newcapacity;
	}
	
	void remove(int index){
		if(index<0 || index>=size){
			cout<<"error"<<endl;
			return;
		}
		for(int i=index;i<size-1;i++) data[i]=data[i+1];
		size--;
		return;
	}
	
}

1.2 线性表的链表存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class Node{
	public:
	int data;
	Node *next;
	
	Node(int val){
		data=val;
		next=NULL;
		return;
	}
}

class LinkedList{
	public:
	Node*head;
	
	LinkedList(){
		head=NULL;
	}
	~LinkedList(){
		while (head!=NULL){
			Node *temp=head;
			head=head->next;
			delete temp;
		}
	}//o(n)
	
	bool search(int val){
		Node *current=head;
		while(current!=NULL){
			if(current->data==val) return true
			current=current->next;
		}
		return false;
	}//o(n)
	int get(int pos){
		if(pos<0 || head=NULL){
			cout<<"error"<<endl;
			return -1;
		}
		Node *current=head;
		int count=0;
		while(current!=NULL && count<pos){
			current=current->next;
			count++;
		}
		if(current==NULL){
			cout<<"Position is out of range!"<<endl;
			return -1;
		}
		return current->data;
	}
	
	void insert(int pos, int val){
		if (pos<0){
			cout<<"invalid position"<<endl;
			return;
		}
		Node *newNode = new Node(val);
		if(pos==0){
			newNode->next=head;
			head=newNode;
		}
		else{
			Node *current=head;
			int count=0;
			while(current!=NULL && count<pos-1){
				current=current->next;
				count++;
			}
			if (current==NULL){
				cout<<"Position is out of range!"<<endl;
				delete newNode;
				return;
			}
			newNode->next=current->next;
			current->next=newNode;
		}
	}
	
	void remove(int pos){
		if(pos<0 || head=NULL){
			cout<<"invalid position or list is empty"<<endl;
			return;
		}
		Node *temp;
		if(pos==0){
			temp=head;
			head=head->next;
			delete temp;
		}
		else{
			Node *current=head;
			int count=0;
			while(current!=NULL && count<pos-1){
				current=current->next;
				count++
			}
			if(current==NULL || current->next==NULL){
				cout<<"position is out of range"<<endl;
				return;
			}
			temp=current->next;
			current->next=temp->next;
			delete temp;
		}
	}
}

反转链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void reverse(Node *head){
	Node *prev=NULL;
	Node *cur=head;
	Node *next=NULL;
	
	while(current!=NULL){
		next=cur->next;
		cur->next=prev;
		prev=cur;
		cur=next;
	}
	head=prev;
}
//o(n)

1.3 链表变体

  1. 单循环链表：末节点的next指向头结点，从表中任意一个节点出发，都可以沿next指针遍历所有节点
    应用：约瑟夫环
  2. 双向链表：每个节点有prior和next两个指针，分别指向直接前驱和直接后继结点。空双向链表只有头尾结点。可以根据待查元素在前半段还是后半段决定自head向后还是自tail向前，可通过参数length辅助判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//双向链表
class Node{
	public:
	int data;
	Node *next;
	Node *prev;
	
	Node(int val){
		data=val;
		next=NULL;
		prev=NULL;
	}
}

class LinkedList{
	private:
	Node *head;
	Node *tail;
	public:
	LinkedList(){
		head=new Node(0);
		tail=new Node(0);
		head->next=tail;
		tail->next=head;
	}
	
	//插入元素
	void insert(){
		Node *tmp=new Node();
		tmp->data=x;
		
		tmp->prev=p;
		tmp->next=p->next;
		tmp->prev->next=tmp;
		tmp->next->prev=tmp;
	}
}
  1. 双向循环链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Node{
	public:
	int data;
	Node *next;
	Node *prev;
	
	Node(int val){
		data=val;
		next=NULL;
		prev=NULL;
	}
}

class LinkedList{
	private:
	Node *head;
	public:
	LinkedList(){
		head=NULL;
	}
}

2. 广义表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template<typename T>
class GNode{
	protected:
	union{
		T data;
		GNode<T> *sublist;
	}u_region;
	GNode<T> *next;
};

template<typename T>
calss GCommonNode : public GNode<T>{
	public:
	GCommonNode(T value){
		this->u_region.data=value;
		this->next=NULL;
	}
};

template <typename T>
class GSublistNode : public GNode<T>{
	public:
	GSublistNode(GNode<T> *sublist){
		this->u_region.sublist=sublist;
		this->next=NULL;
	}
}

2.1 多重链表

结点有多个指针域

2.2 稀疏矩阵存储

使用十字链表：定义head结点和term结点。head结点管理矩阵的每一行每一列，term结点管理矩阵的每个值。每一行每一列均构造成循环链表形式。

3. 字符串

  • 字符串由零个或多个字符串组成的有限序列
  • 串名，串值，串长
  • 空字符串：字符串长度为0，仍然是一个字符串
  • 空格字符串：有一个或一个以上的空格组成的字符串，长度为空格个数
  • 单字符串：只有一个字符
  • 字符串相等：长度相同+对应位置字符完全相同
  • 子串：任意连续字符组成的子序列，位置用子串第一个字符在主串中的位置表示
  • 主串：包含子串的字符串

仅考虑字符串的顺序存储

  • 静态存储：容易引发截断
  • 动态数组：==常见错误：如对字符串”cjy”的存储，3个字符加上结束标志符”\0” ，共占用4个字节。但是字符串长度仍为3，结束符不算入内。==
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class sstring{
	private:
	char *str;
	int maxSize;
	
	public:
	sstring(int size){
		if(size<0){
			cout<<"error"<<endl;
			return;
		}
		str=new char[size];
		maxSize=size;
		str[0]='\0';
	}
	
	//求字符串中从pos开始，长度为len的子串
	 sstring subString(int pos, int len) const{
		if(pos<0){
			cout<<"error"<<endl;
			return;
		}
		
		int i=0;
		sstring *tmp = new sstring(len+1);
		for(; i<len && str[pos+i]!='\0';i++){
			tmp->str[i]=str[pos+i];
		}
		tmp->str[i]='\0';
		return *tmp;
	}
	
	//判断两个对象中存储的字符串内容是否一样
	bool equal(const sstring &t) const{
		int i=0;
		if(this->length()!=t.length()) return false;
		while(str[i]!='\0'){
			if(str[i]!=t.str[i]) return false;
			else i++;
		}
		return true;
	}
}


注意：
字符串s和t相互赋值时，可能使用s.str=t.str，但是导致这连个数组在后续操作中同步变化，即对s操作时，t也会动，正确方法是s.str[i]=t.str[i]

模式匹配：
s为主串，匹配串称为模式

BF算法：暴力匹配，分别将主串的每一个位置认作匹配的开始，然后逐一匹配，若不成功，继续下一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//从字符串第start个字符开始，向后查找t第一次在字符串中出现的序号
int sstring::BF_Find(const sstring &t, int start){
	int i=0,j=0;
	int pos=-1;
	int n=this->length();
	int m=t.length;
	int curStart=start;
	
	while(curStart<=n-m){
		i=curStart;
		while((j<m)&&(str[i]==t.str[j])){
			i++;
			j++;
		}
		if(j==m){
			pos=curStart;
			break;
		}
		curStart++;
		j=0;
	}
	return pos;
}

时间复杂度分析：
最好情况：

  1. 一次匹配成功，o(m)
  2. 全部第一个字符匹配不成功，o(n)
    最坏情况：
    每次都是模式的最后一个字符匹配失败，导致不成功，时间为o((n-m)m)
http://chenjiayi0505.github.io/2026/07/02/数据结构 第二章 线性表/
作者
Jiayi Chen
发布于
2026年7月2日
更新于
2026年5月31日
许可协议