线性表
线性表是一种数据结构，表示由同一类型的元素按顺序排列的有限集合。线性表中的元素有顺序关系，可以通过顺序号访问。它是最常用的结构之一，常用于实现数据的顺序存储和查找操作。
线性表的定义
一个线性表 $( L )$ 可以定义为一个具有相同类型的元素集合，其中第一个元素为 $( a_1 )$，第二个元素为 $( a_2 )$，依次排列，直到第 $( n )$ 个元素 $( a_n )$。线性表的长度是元素的个数，当长度为 0 时，称其为空表。
在数学上可以表示为：
$[ L = { a_1, a_2, \dots, a_n } ]$
线性表的基本操作
线性表的基本操作主要包括以下几个：
初始化（Initialization）
插入（Insert）
- 将一个新元素插入到线性表的指定位置。插入时，需要将插入位置后的所有元素向后移动。
删除（Delete）
- 删除线性表中的指定位置的元素。删除时，需要将删除位置后的所有元素向前移动。
查找（Find/Search）
- 根据元素的值查找其在表中的位置，或根据位置查找对应的元素值。
更新（Update）
遍历（Traverse）
- 顺序访问线性表中的每一个元素，通常用于打印或处理每个元素。
获取长度（Length）
线性表的实现方式
线性表的实现通常有两种存储结构：
- 顺序存储结构：使用数组存储元素，适合顺序访问，但插入和删除操作的效率较低。
- 链式存储结构：使用链表存储元素，适合频繁的插入和删除操作，常见的链表类型包括单链表、循环链表和双向链表。
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
| #include <iostream>
#define MAX_SIZE 100
class SeqList {
private:
int data[MAX_SIZE];
int length;
public:
SeqList() : length(0) {}
bool insert(int pos, int value) {
if (pos < 0 || pos > length || length >= MAX_SIZE) return false;
for (int i = length; i > pos; --i) data[i] = data[i - 1];
data[pos] = value;
length++;
return true;
}
bool remove(int pos) {
if (pos < 0 || pos >= length) return false;
for (int i = pos; i < length - 1; ++i) data[i] = data[i + 1];
length--;
return true;
}
int find(int value) {
for (int i = 0; i < length; ++i)
if (data[i] == value) return i;
return -1;
}
void display() {
for (int i = 0; i < length; ++i) std::cout << data[i] << " ";
std::cout << std::endl;
}
};
|
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
| #include <iostream>
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class SinglyLinkedList {
private:
Node* head;
public:
SinglyLinkedList() : head(nullptr) {}
void insert(int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}
bool remove(int value) {
Node *prev = nullptr, *curr = head;
while (curr && curr->data != value) {
prev = curr;
curr = curr->next;
}
if (!curr) return false;
if (prev) prev->next = curr->next;
else head = curr->next;
delete curr;
return true;
}
Node* find(int value) {
Node* curr = head;
while (curr) {
if (curr->data == value) return curr;
curr = curr->next;
}
return nullptr;
}
void display() {
Node* curr = head;
while (curr) {
std::cout << curr->data << " ";
curr = curr->next;
}
std::cout << std::endl;
}
};
|
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <iostream>
struct CNode {
int data;
CNode* next;
CNode(int val) : data(val), next(nullptr) {}
};
class CircularLinkedList {
private:
CNode* tail;
public:
CircularLinkedList() : tail(nullptr) {}
void insert(int value) {
CNode* newNode = new CNode(value);
if (!tail) {
tail = newNode;
tail->next = tail;
} else {
newNode->next = tail->next;
tail->next = newNode;
tail = newNode;
}
}
bool remove(int value) {
if (!tail) return false;
CNode *curr = tail->next, *prev = tail;
do {
if (curr->data == value) {
if (curr == tail) tail = (tail->next == tail) ? nullptr : prev;
prev->next = curr->next;
delete curr;
return true;
}
prev = curr;
curr = curr->next;
} while (curr != tail->next);
return false;
}
CNode* find(int value) {
if (!tail) return nullptr;
CNode* curr = tail->next;
do {
if (curr->data == value) return curr;
curr = curr->next;
} while (curr != tail->next);
return nullptr;
}
void display() {
if (!tail) return;
CNode* curr = tail->next;
do {
std::cout << curr->data << " ";
curr = curr->next;
} while (curr != tail->next);
std::cout << std::endl;
}
};
|
4. 双向链表的实现
双向链表每个节点有前驱和后继指针，方便双向遍历。
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
| #include <iostream>
struct DNode {
int data;
DNode* prev;
DNode* next;
DNode(int val) : data(val), prev(nullptr), next(nullptr) {}
};
class DoublyLinkedList {
private:
DNode* head;
public:
DoublyLinkedList() : head(nullptr) {}
void insert(int value) {
DNode* newNode = new DNode(value);
newNode->next = head;
if (head) head->prev = newNode;
head = newNode;
}
bool remove(int value) {
DNode* curr = head;
while (curr && curr->data != value) curr = curr->next;
if (!curr) return false;
if (curr->prev) curr->prev->next = curr->next;
else head = curr->next;
if (curr->next) curr->next->prev = curr->prev;
delete curr;
return true;
}
DNode* find(int value) {
DNode* curr = head;
while (curr) {
if (curr->data == value) return curr;
curr = curr->next;
}
return nullptr;
}
void display() {
DNode* curr = head;
while (curr) {
std::cout << curr->data << " ";
curr = curr->next;
}
std::cout << std::endl;
}
};
|
这些代码分别实现了顺序表、单链表、循环链表和双向链表的数据结构及其基本操作，适合考试和项目中的线性表应用。
