文章目录
  1. 1. 概述
  2. 2. 代码实现
  3. 3. 顺序表的特点
    1. 3.1. 顺序表优点
    2. 3.2. 顺序表缺点
  4. 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
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
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
<?php
/**
*
* @authors Your Name (you@example.org)
* @date 2017-09-12 14:58:55
* @version $Id$
*/

class OrderList {
public $data;
public $max_size;
public static $len;

public function __construct($size) {
$this->initList($size);
}

/**
* [initList 初始化顺序表]
* @param [int] $size [顺序表长度]
*/
public function initList($size) {
$this->data = array();
self::$len = 0;
$this->max_size = $size;
}

/**
* [getElement 获取顺序表元素]
* @param [int] $index [索引位置]
* @return [boolean] [成功获取元素返回元素的值,失败则返回元素值]
*/
public function getElement($index) {
// 判断索引位置是否合法
if ($index < 1 || $index > self::$len) {
return false;
}

// 判断顺序表长度,长度为0,则不能获取元素
if (self::$len == 0) {
return false;
}

return $this->data[$index - 1];
}

/**
* [insertElement 顺序表插入元素]
* @param [int] $index [索引位置]
* @param [all] $element [元素值]
* @return [boolean] [插入成功返回true, 插入失败返回false]
*/
public function insertElement($index, $element) {
// 判断索引位置是否合法
if ($index < 1 || $index > self::$len + 1) {
return false;
}

// 判断顺序表是否已满
if (self::$len == $this->max_size) {
return false;
}

// 在指定位置插入新元素,插入位置处的所有元素后移
// 如果插入位置在顺序表表尾,则直接插入
if ($index <= self::$len) {
for ($i = self::$len - 1; $i >= $index - 1; $i--) {
$this->data[$i+1] = $this->data[$i];
}
}

$this->data[$index-1] = $element;
self::$len++;

return true;
}

/**
* [deleteElement 删除元素]
* @param [index] $index [索引位置]
* @return [boolean] [删除成功返回true, 失败返回false]
*/
public function deleteElement($index) {
// 判断索引位置是否合法
if ($index < 1 || $index > self::$len) {
return false;
}

// 顺序表为空,不能删除元素
if (self::$len == 0) {
return false;
}

if ($index < self::$len) {
for ($i = $index; $i < self::$len; $i++) {
$this->data[$i-1] = $this->data[$i];
}
}

unset($this->data[self::$len-1]);
self::$len--;

return false;
}

/**
* [getPrevElement 获取前驱元素]
* @param [index] $index [索引位置]
* @return [boolean] [获取成功返回元素值, 失败返回false]
*/
public function getPrevElement($index) {
// 判断索引位置是否合法
if ($index < 1 || $index > self::$len) {
return false;
}

// 判断顺序表长度,长度为0,则不能获取元素
if (self::$len == 0) {
return false;
}

// 第一个元素没有前驱元素
if ($index == 1) {
return false;
}

return $this->data[$index - 2];
}

/**
* [getNextElement 获取后继元素]
* @param [index] $index [索引位置]
* @return [boolean] [获取成功返回元素值, 失败返回false]
*/
public function getNextElement($index) {
// 判断索引位置是否合法
if ($index < 1 || $index > self::$len) {
return false;
}

// 判断顺序表长度,长度为0,则不能获取元素
if (self::$len == 0) {
return false;
}

// 最后一个元素没有后继元素
if ($index == $len) {
return false;
}

return $this->data[$index + 1];
}

/**
* [locateElement 获取元素索引位置]
* @param [all] $element [元素值]
* @return [int] [元素索引位置]
*/
public function locateElement($element) {
$pos = 0;
for ($i = 0; $i < self::$len; $i++) {
if ($this->data[$i] == $element) {
$pos = $i + 1;
}
}

return $pos;
}

/**
* [isEmpty 顺序表是否为空]
* @return boolean [为空返回true, 否则返回false]
*/
public function isEmpty() {
if (self::$len == 0) {
return true;
}

return false;
}

/**
* [destoryList 销毁顺序表]
* @return [boolean] [销毁成功返回true, 失败返回flase]
*/
public function destoryList() {
$this->data = null;
self::$len = 0;

return true;
}

/**
* [destoryList 清空顺序表]
* @return [boolean] [清空成功返回true, 失败返回flase]
*/
public function clearList() {
$this->data = array();
self::$len = 0;

return true;
}
}

$order_list = new OrderList(5);

// 插入数据
$order_list->insertElement(1, 'a');
$order_list->insertElement(2, 'b');
$order_list->insertElement(3, 'c');

// 删除数据
$order_list->deleteElement(2);

顺序表的特点

顺序表优点

  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
  • 可以快速的存取表中任一位置的元素

顺序表缺点

  • 插入和删除操作需要移动大量元素
  • 当线性表长度变化较大时,难易确定存储空间的容量
  • 造成存储空间的“碎片”

总结

代码实现顺序表的增删改查定位等操作。