数据结构笔记2-线性表

注:本人学习数据结构时是以 C++ 为编程语言

概念-名词解释

线性表:线性存储结构,将具有「一对一」关系的数据「线性」地存储到物理空间中,这种存储结构就称为线性存储结构(简称:线性表)。

依据在计算机中的实际存储结构线性存储结构可以细分为一下两种:

  1. 顺序表:将线性表中所有元素按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中;

顺序表

  1. 链表:线性表的元素存储在不连续的屋里空间中,用指针表示结点间的逻辑关系。

单链表

表名、表项、表头、表尾、头结点、首元结点、直接前驱、直接后继、空表、有序表、无序表:会在后面的代码示例中解释

顺序表

实现分析

实现方案

在 C 语言中,顺序表有两种实现方式:

1
2
3
4
5
6
7
8
// 静态存储结构
#define maxSize 100

typedef int T;
typedef struct {
T data[maxSize];
int len;
} SeqList;
1
2
3
4
5
6
 // 动态存储结构
typedef int T;
typedef struct {
T *data;
int maxSize, len;
} SeqList;

在我所用的教科书里选用了在 C++ 中延续动态存储结构,这里我就顺着教科书走,后面的代码实现也是使用 C++ 配合动态存储结构实现顺序表。

常见属性列举

  1. 用来存放数据的数组变量;
  2. 用来存放表容量的整型变量;
  3. 用来存放当前表已占用容量的整型变量;

常见方法列举

  1. 通过传入容量变量构造实例的构造函数;
  2. 复制构造函数;
  3. 析构函数;
  4. 返回表容量的函数;
  5. 返回表当前已占用容量的函数;
  6. 头插 | 尾插 | 任意位置插入;
  7. 搜索 X 在表中的位置;
  8. 获取第 i 项 | 修改第 i 项 | 删除第 i 项
  9. 判空 | 判满
  10. 格式化输出
  11. 动态改变表容量的方法;

代码实现

点击显示/隐藏全部代码
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
//
// Created by ryoma on 2020/11/8.
//

template<class T>
class SeqList {
public:
SeqList(int capacity = 10); // 构造函数
SeqList(SeqList<T> &TheSqlList); // 复制构造函数
~SeqList() { delete[] data_; } // 析构函数
void HeadInsert(T &element); // 头插
void LastInsert(T &element); // 尾插
void Insert(int index, T &element); // 任意位置插入
int Search(T &element); // 搜索 x 在表中的位置
T GetData(int index); // 获取第 i 项的值
void SetData(int index, T &element); // 将第 i 项更新为 x
void DeleteData(int index); // 删除第 i 项
bool IsFull(); // 判满
bool IsEmpty(); // 判空
void FormatOutput(); // 格式化输出
int capacity() const { return capacity_; } // 获取表容量
int size() const { return size_; } // 获取表当前占用容量

protected:
T *data_; // 表成员数组指针
int size_; // 表当前占用容量
int capacity_; // 表容量
void ResetCapacity(int new_capacity); // 重置表容量
};

template<class T>
SeqList<T>::SeqList(int capacity) {
if (capacity > 0) {
capacity_ = capacity;
size_ = 0;
data_ = new T[capacity_];
if (data_ == NULL) {
cerr << "memory allocation failed!" << endl;
exit(1);
}
} else {
cerr << "sequential list capacity set error!" << endl;
exit(1);
}
}

template<class T>
SeqList<T>::SeqList(SeqList<T> &TheSqlList) {
capacity_ = TheSqlList.capacity();
size_ = TheSqlList.size();
T value;
data_ = new T[capacity_];
if (data_ == NULL) {
cerr << "memory allocation failed!" << endl;
exit(1);
}
for (int i = 0; i < size_; i++) {
TheSqlList.GetData(i);
data_[i] = value;
}
}

template<class T>
void SeqList<T>::ResetCapacity(int new_capacity) {
// 判断给出顺序表容量是否合法
if (new_capacity <= capacity_) {
cerr << "sequential list capacity set error!" << endl;
return;
}
// 创建扩容后的数组用来存放顺序表元素
T *new_array = new T[new_capacity];
if (new_array == NULL) {
cerr << "memory allocation failed!" << endl;
return;
}
// 将旧顺序表数组的内容同步到新顺序表中
for (int i = 0; i < size_; ++i) {
new_array[i] = data_[i];
}
// 替换属性
delete[] data_;
data_ = new_array;
capacity_ = new_capacity;
}

template<class T>
void SeqList<T>::HeadInsert(T &element) {
// 判满 | 如果顺序表满则扩容
if (size_ == capacity_) {
ResetCapacity(2 * capacity_);
}
// 将顺序表内所有元素向后移动一位
for (int i = size_; i > 0; --i) {
data_[i] = data_[i - 1];
}
data_[0] = element;
size_++;
}

template<class T>
void SeqList<T>::LastInsert(T &element) {
// 判满 | 如果顺序表满则扩容
if (size_ == capacity_) {
ResetCapacity(2 * capacity_);
}
data_[size_] = element;
size_++;
}

// 将给出的元素值插入到当前顺序表的第 index 个元素前
template<class T>
void SeqList<T>::Insert(int index, T &element) {
// 判断 index 是否正确
if (index > size_ || index < 1) {
cerr << "index input error!" << endl;
return;
}
// 判满 | 如果顺序表满则扩容
if (size_ == capacity_) {
ResetCapacity(2 * capacity_);
}
// 将顺序表 index 之后的全部元素向后平移一位
for (int i = size_; i > index; --i) {
data_[i] = data_[i - 1];
}
data_[index - 1] = element;
size_++;
}

// 从当前顺序表搜索给出的元素值
// 如果元素值存在,返回元素值第一次出现在当前顺序表的第几个元素
// 如果不存在返回 0
template<class T>
int SeqList<T>::Search(T &element) {
for (int i = 0; i < size_; ++i) {
if (data_[i] == element) {
return i + 1;
}
}
return 0;
}

// 获取当前顺序表的第 index 个元素
template<class T>
T SeqList<T>::GetData(int index) {
if (index > size_ || index < 1) {
cerr << "index input error!" << endl;
exit(1);
}
return data_[index - 1];
}

// 将当前顺序表的第 index 个元素修改为给出的元素值
template<class T>
void SeqList<T>::SetData(int index, T &element) {
if (index > size_ || index < 1) {
cerr << "index input error!" << endl;
return;
}
data_[index - 1] = element;
}

template<class T>
void SeqList<T>::DeleteData(int index) {
if (size_ == 0 || index > size_ || index < 1) {
cerr << "index input error!" << endl;
return;
}
for (int i = index - 1; i < size_; ++i) {
data_[i] = data_[i + 1];
}
size_--;
}

template<class T>
void SeqList<T>::FormatOutput() {
if (size_ == 0) {
return;
}
for (int i = 0; i < size_; ++i) {
cout << data_[i] << ' ';
}
cout << endl;
}

template<class T>
bool SeqList<T>::IsFull() {
return size_ == capacity_;
}

template<class T>
bool SeqList<T>::IsEmpty() {
return size_ == 0;
}

效率分析

1
2
3
4
5
6
7
8
9
void HeadInsert(T &element);                // O(n)
void LastInsert(T &element); // O(1)
void Insert(int index, T &element); // O(n)
int Search(T &element); // O(n)
T GetData(int index); // O(n)
void SetData(int index, T &element); // O(n)
void DeleteData(int index); // O(n)
void FormatOutput(); // O(n)
void ResetCapacity(int new_capacity); // O(n)

单链表

实现分析

根据链表的组成,通常会使用结点类和链表类协同表示链表。

一个链表包含零个或多个结点,因此一个类型为 List 的对象包括零个或多个类型为 LinkNode 的对象。这种关系在面向对象方法中叫做「聚合关系」,或者叫做「整体-部分关系」。

为了简化问题,设一个单链表的每一个结点中的数据元素为一个整型数据,有4 种方法设计数据结构。

实现方案

方案一:复合类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class List;         // List 类的前视声明

class LinkNode { // 结点类定义
friend class List; // 声明 List 类为友元类
private:
int data; // 数据元素域
LinkNode *link; // 链指针域
};

class List { // List 类定义
public:
// 链表操作
...
private:
LinkNode *first; // 链表头指针
};
方案二:嵌套类
1
2
3
4
5
6
7
8
9
10
11
12
class List {
public:
// 链表操作
...
private:
class LinkNode {
public:
int data;
LinkNode *link;
};
LinkNode *first;
};
方案三:基类和派生类
1
2
3
4
5
6
7
8
9
10
11
12
13
class LinkNode {
protected:
int data;
LinkNode *link;
};

class List: public class LinkNode {
private:
LinkNode *first;
public:
//链表操作
...
}
方案四:用 struct 定义 LinkNode 类
1
2
3
4
5
6
7
8
9
10
11
12
struct LinkNode {
int data;
LinkNode *link;
};

class List {
private:
LinkNode *first;
public:
// 链表操作
...
};

后面我将采用「方案四:用 struct 定义 LinkNode 类」来实现链表以及其一些列变种。

常见属性列举

  1. 结点类中存放数据的变量;
  2. 结点类中存放此结点所指向的下一结点的指针变量;
  3. 带头指针的链表类所包含的指向头结点的指针变量;

常见方法列举

  1. 构造函数
  2. 复制构造函数
  3. 析构函数
  4. 置空函数
  5. 返回链表当前大小的函数
  6. 头插 | 尾插 | 任意位置插入
  7. 搜索 X 在表中的位置
  8. 获取第 i 项 | 修改第 i 项 | 删除第 i 项
  9. 判空
  10. 格式化输出

代码实现

1
2


效率分析