1.定义

线性表:是具有相同数据类型的n(n>=0)个数据元素的有限序列

顺序表：用顺序存储的方式实现的线性表

2.顺序表的实现可以使用静态分配和动态配分两种方式

 

 

 

 由于使用静态分配的方式，所能存储的数据有限，所以后面实现顺序表时使用动态分配方式

3.顺序表的实现

头文件：

 1 #ifndef _SQLIST_H
 2 #define _SQLIST_H
 3 
 4 class SqList
 5 {
 6 public:
 7     SqList(int capacity = 15);
 8     ~SqList();
 9     bool insert_data(int pos, int data);
10     int delete_data(int pos);
11     void show();
12 
13 private:
14     void increase_memory();
15 
16 private:
17     int *m_data;
18     int m_capacity;
19     int m_length;
20 };
21 
22 #endif

源文件:

 1 #include "sqlist.h"
 2 #include <iostream>
 3 
 4 /*
 5  *@brief:构造函数 实现顺序表的初始化
 6  *@params: capacity:容量
 7  *@return:
 8 */
 9 SqList::SqList(int capacity) : m_capacity(capacity)
10 {
11     m_data = new int[m_capacity];
12     m_length = 0;
13 }
14 
15 /*
16  *@brief:析构函数 实现顺序表的销毁操作
17  *@params:
18  *@return:
19 */
20 SqList::~SqList()
21 {
22     delete[] m_data;
23     m_capacity = m_length = 0;
24 }
25 
26 /*
27  *@brief:增加内存
28  *@params:void
29  *@return:void
30 */
31 void SqList::increase_memory()
32 {
33     m_capacity *= 2;
34     int *new_data = new int[m_capacity];
35 
36     for (int i = 0; i < m_length; i++)
37         new_data[i] = m_data[i];
38 
39     delete[] m_data;
40     m_data = new_data;
41 }
42 /*
43  *@brief:在指定位置插入一个数据元素
44  *@params: pos:待插入的位置
45            data:插入的数据
46  *@return: 成功:true
47            失败:false
48 */
49 bool SqList::insert_data(int pos, int data)
50 {
51     if (pos < 1 || pos > m_length + 1) //插入位置不合法
52         return false;
53     if (m_length == m_capacity) //先有的内存已经使用完毕，需要重新分配内存
54         increase_memory();
55 
56     for (int i = m_length; i >= pos; i--)
57         m_data[i] = m_data[i - 1];
58 
59     m_data[pos - 1] = data;
60     m_length++;
61 
62     return true;
63 }
64 
65 /*
66  *@brief:删除指定位置的元素
67  *@params: pos:待删除位置
68  *@return:  成功:删除的元素值
69  *          失败:-1
70 */
71 int SqList::delete_data(int pos)
72 {
73     if (pos < 1 || pos > m_length)
74         return -1;
75 
76     int data = m_data[pos - 1];
77     for (int i = pos - 1; i < m_length - 1; i++)
78         m_data[i] = m_data[i + 1];
79 
80     m_length--;
81     return data;
82 }
83 /*
84  *@brief:显示数据内容 测试使用
85  *@params:void
86  *@return:void
87 */
88 void SqList::show()
89 {
90     for (int i = 0; i < m_length; i++)
91         std::cout << m_data[i] << ' ';
92     std::cout << std::endl;
93 }

4.顺序表的特点：

a.随机访问：可以在O(1)的时间复杂度内找到第i个元素

b.存储密度高，每个节点只存储数据元素

c.扩展容量不方便

d.插入 删除操作不方便，需要移动大量元素