第2章：顺序表

本章目标

  1. 了解线性表的概念

  2. 掌握线性表顺序存储结构的特点

  3. 掌握顺序表的基本操作

本章内容

了解线性结构

线性结构的特点：

  • 存储唯一的开始结点
  • 存储唯一的终端结点
  • 除第一个外，每个数据元素均有一个前驱
  • 除最后一个外，每个数据元素均只有一个后继

提示：

线性结构是最常用、最简单的一种数据结构

线性表

  • 一种线性结构
  • 允许在任意位置进行插入和删除数据元素的操作
  • 由n(n>=0)个相同类型数据元素a1,a2,….,an构成的有限序列

线性表的逻辑结构：

  • a1:首元素
  • an:尾元素
  • ai:第i个数据元素，i为数据在线性表中的顺序
  • n:线性表中的数据元素的个数，称为表长

线性表的热证：

  • 均匀性：同一线性表的各数据元素数据类型相同
  • 有序性：数据元素在线性表的位置只取决于序列
  • 1<i<n 时：ai仅有一个直接前驱和一个直接后继
  • a1没有前驱
  • an没有后继

线性表的存储结构：

  • 顺序存储结构
  • 链式存储结构

顺序存储结构

  • 用一组地址连续的存储单元，依次存储 线性表中的各个数据元素。

  • 用顺序存储结构存储的线性表称为顺序表

  • 特点：

    • 逻辑相邻，物理相邻
    • 实现随机存取

顺序表的基本操作

  • 初始化
  • 判断 是否为空
  • 获取长度
  • 插入元素
  • 移除元素
  • 修改指定位置的对象
  • 查找 数据元素的位置
  • 查询指定索引的对象

初始化

问题 ：

如何构造 一个指定容量的顺序表

分析:

  1. 判断传入容量的有效性，如果无效，指定 默认容量
  2. 初始化顺序表
  3. 设置数据个数为0

示例：

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
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH02Demo
{
    /// <summary>
    /// 自定义顺序表
    /// </summary>
    /// <typeparam name="T"></typeparam>
    internal class MyArray<T>
    {
        /// <summary>
        /// 数据容器
        /// </summary>
        private T[] array;

        /// <summary>
        /// 表长度
        /// </summary>
        private int length;

        /// <summary>
        /// 初始化MyArray
        /// </summary>
        public MyArray(){
            this.length = 0;
            this.array = new T[10];
        }

        /// <summary>
        /// 初始化MyArray
        /// </summary>
        /// <param name="capacity">初始大小</param>
        public MyArray(int capacity)
        {
            this.length = 0;

            if (capacity <= 0)
            {
                this.array = new T[10];
            }
            else
            {
                this.array=new T[capacity];
            }
            
        }
    }
}

验证是否为空

问题 ：

如何判断顺序表是否为空

分析:

  1. 如何数据表长度为0，则为空

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/// <summary>
/// 是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
    return this.length == 0; 
}

/// <summary>
/// 元素数量
/// </summary>
/// <returns></returns>
public int Count()
{
    return this.length;
}

插入元素

问题 ：

如何实现在线性表的第i (1≤i≤n)个位置上，插入一个新元素x , 使长度为n的线性表变成长度为n+1的线性表

分析:

  1. 判断索引位置是否有效，无效不允许插入
  2. 如果索引位置有效，将线性表L中的第i个至第n个结点后移一个位置
  3. 将元素x插入
  4. 线性表长度加1

提示：

数组索引从0开始

示例：

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
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading.Tasks;

namespace CH02Demo
{
    /// <summary>
    /// 自定义顺序表
    /// </summary>
    /// <typeparam name="T"></typeparam>
    internal class MyArray<T>
    {
        /// <summary>
        /// 数据容器
        /// </summary>
        private T[] array;

        /// <summary>
        /// 表长度
        /// </summary>
        private int length;

        /// <summary>
        /// 初始化MyArray
        /// </summary>
        public MyArray(){
            this.length = 0;
            this.array = new T[10];
        }

        /// <summary>
        /// 初始化MyArray
        /// </summary>
        /// <param name="capacity">初始大小</param>
        public MyArray(int capacity)
        {
            this.length = 0;

            if (capacity <= 0)
            {
                this.array = new T[10];
            }
            else
            {
                this.array=new T[capacity];
            }
            
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.length == 0; 
        }

        /// <summary>
        /// 元素数量
        /// </summary>
        /// <returns></returns>
        public int Count()
        {
            return this.length;
        }

        /// <summary>
        /// 插入
        /// </summary>
        /// <param name="index">索引</param>
        /// <param name="item">数据项</param>
        /// <returns></returns>
        public bool  Insert(int index,T item)
        {
            //索引检测
            if (index < 0 || index > this.length) return false;

            //容量检测
            if (this.length == this.array.Length)
            {
                //扩大为2倍
                T[] newArray = new T[this.length*2];

                //复制数据
                for (int i = 0; i < this.length; i++)
                {
                    newArray[i] = this.array[i];
                }

                //覆盖原始容器
                this.array = newArray;
            }

            //移动数据
            for (int i = this.length;i>index;i--)
            {
                this.array[i]=this.array[i-1];
            }

            //插入数据
            this.array[this.length++] = item;

            return true;
        }
        
        /// <summary>
        /// 新增
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            this.Insert(this.length, item);
        }

        /// <summary>
        /// 索引器
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T this[int index]
        {
            get
            {
                return this.array[index];
            }
            set
            {
                this.Insert(index,value);
            }
        }   
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void button2_Click(object sender, EventArgs e)
{
    MyArray<int> list = new MyArray<int>();

    Random r= new Random();
    for (int i = 0; i < 10; i++)
    {
        //list.Insert(i, r.Next(10,100));
        list.Add(r.Next(10, 100));
    }

    this.listBox1.Items.Clear();
    for (int i = 0;i < list.Count(); i++)
    {
        this.listBox1.Items.Add(list[i]);
    }
}

删除元素

问题 ：

将长度为n的线性表中第i(1≤i≤n)个元素删除，使得变成长度为n-1的线性表

分析:

  1. 判断索引位置是否有效，无效不允许删除
  2. 如果索引位置有效，将线性表L中的第i+1个至第n个结点依次向前移动一个位置
  3. 线性表长度减1

提示：

数组索引从0开始

示例：

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
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Reflection.Emit;
using System.Text;
using System.Threading.Tasks;

namespace CH02Demo
{
    /// <summary>
    /// 自定义顺序表
    /// </summary>
    /// <typeparam name="T"></typeparam>
    internal class MyArray<T>
    {
        /// <summary>
        /// 数据容器
        /// </summary>
        private T[] array;

        /// <summary>
        /// 表长度
        /// </summary>
        private int length;

        /// <summary>
        /// 初始化MyArray
        /// </summary>
        public MyArray(){
            this.length = 0;
            this.array = new T[10];
        }

        /// <summary>
        /// 初始化MyArray
        /// </summary>
        /// <param name="capacity">初始大小</param>
        public MyArray(int capacity)
        {
            this.length = 0;

            if (capacity <= 0)
            {
                this.array = new T[10];
            }
            else
            {
                this.array=new T[capacity];
            }
            
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.length == 0; 
        }

        /// <summary>
        /// 元素数量
        /// </summary>
        /// <returns></returns>
        public int Count()
        {
            return this.length;
        }

        /// <summary>
        /// 插入
        /// </summary>
        /// <param name="index">索引</param>
        /// <param name="item">数据项</param>
        /// <returns></returns>
        public bool  Insert(int index,T item)
        {
            //索引检测
            if (index < 0 || index > this.length) return false;

            //容量检测
            if (this.length == this.array.Length)
            {
                //扩大为2倍
                T[] newArray = new T[this.length*2];

                //复制数据
                for (int i = 0; i < this.length; i++)
                {
                    newArray[i] = this.array[i];
                }

                //覆盖原始容器
                this.array = newArray;
            }

            //移动数据
            for (int i = this.length;i>index;i--)
            {
                this.array[i]=this.array[i-1];
            }

            //插入数据
            this.array[this.length++] = item;

            return true;
        }
        
        /// <summary>
        /// 新增
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            this.Insert(this.length, item);
        }

        /// <summary>
        /// 索引器
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T this[int index]
        {
            get
            {
                return this.array[index];
            }
            set
            {
                this.Insert(index,value);
            }
        }

        /// <summary>
        /// 清空所有元素
        /// </summary>
        public void Clear()
        {
            this.array=new T[10];
            this.length=0;
        }

        /// <summary>
        /// 移除元素
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public bool Remove(int index)
        {
            //索引检测
            if (index < 0 || index >= this.length) return false;

            //后半部分元素前移
            for (int i = index; i < this.length-1; i++)
            {
                this.array[i] = this.array[i + 1];
            }

            //末尾清空
            this.array[this.length - 1] = default(T);

            //更新长度
            this.length--;

            return true;
        }
        
    }
}

1
2
3
4
5
6
7
8
9
10
private void button4_Click(object sender, EventArgs e)
{
    this.list.Remove(3);

    this.listBox1.Items.Clear();
    for (int i = 0; i < list.Count(); i++)
    {
        this.listBox1.Items.Add(list[i]);
    }
}

查找元素

问题 ：

如何在长度为n的线性表L中查找第i (1≤i≤n)个元素ai

分析:

  1. 判断索引位置是否有效，无效不允许查询
  2. 按照给定的位置查找线性表成员

提示：

数组索引从0开始

示例：

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
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Reflection.Emit;
using System.Text;
using System.Threading.Tasks;

namespace CH02Demo
{
    /// <summary>
    /// 自定义顺序表
    /// </summary>
    /// <typeparam name="T"></typeparam>
    internal class MyArray<T>
    {
        /// <summary>
        /// 数据容器
        /// </summary>
        private T[] array;

        /// <summary>
        /// 表长度
        /// </summary>
        private int length;

        /// <summary>
        /// 初始化MyArray
        /// </summary>
        public MyArray(){
            this.length = 0;
            this.array = new T[10];
        }

        /// <summary>
        /// 初始化MyArray
        /// </summary>
        /// <param name="capacity">初始大小</param>
        public MyArray(int capacity)
        {
            this.length = 0;

            if (capacity <= 0)
            {
                this.array = new T[10];
            }
            else
            {
                this.array=new T[capacity];
            }
            
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.length == 0; 
        }

        /// <summary>
        /// 元素数量
        /// </summary>
        /// <returns></returns>
        public int Count()
        {
            return this.length;
        }

        /// <summary>
        /// 插入
        /// </summary>
        /// <param name="index">索引</param>
        /// <param name="item">数据项</param>
        /// <returns></returns>
        public bool  Insert(int index,T item)
        {
            //索引检测
            if (index < 0 || index > this.length) return false;

            //容量检测
            if (this.length == this.array.Length)
            {
                //扩大为2倍
                T[] newArray = new T[this.length*2];

                //复制数据
                for (int i = 0; i < this.length; i++)
                {
                    newArray[i] = this.array[i];
                }

                //覆盖原始容器
                this.array = newArray;
            }

            //移动数据
            for (int i = this.length;i>index;i--)
            {
                this.array[i]=this.array[i-1];
            }

            //插入数据
            this.array[this.length++] = item;

            return true;
        }
        
        /// <summary>
        /// 新增
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            this.Insert(this.length, item);
        }

        /// <summary>
        /// 索引器
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T this[int index]
        {
            get
            {
                return this.array[index];
            }
            set
            {
                this.Insert(index,value);
            }
        }

        /// <summary>
        /// 清空所有元素
        /// </summary>
        public void Clear()
        {
            this.array=new T[10];
            this.length=0;
        }

        /// <summary>
        /// 移除元素
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public bool Remove(int index)
        {
            //索引检测
            if (index < 0 || index >= this.length) return false;

            //后半部分元素前移
            for (int i = index; i < this.length-1; i++)
            {
                this.array[i] = this.array[i + 1];
            }

            //末尾清空
            this.array[this.length - 1] = default(T);

            //更新长度
            this.length--;

            return true;
        }

        /// <summary>
        /// 获取值
        /// </summary>
        /// <param name="index">索引</param>
        /// <returns></returns>
        public T GetValue(int index)
        {
            //验证索引
            if (index < 0 || index >= this.length) return default(T);

            return this.array[index];
        }  
    }
}

1
2
3
4
private void button5_Click(object sender, EventArgs e)
{
    MessageBox.Show(this.list.GetValue(3).ToString());
}

修改元素

问题 ：

将长度为n的线性表中，结点ai(1≤i≤n)的值修改为x

分析:

  1. 判断索引位置是否有效，无效不允许修改
  2. 按照给定的位置修改线性表成员内容

提示：

数组索引从0开始

示例：

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
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Reflection.Emit;
using System.Text;
using System.Threading.Tasks;

namespace CH02Demo
{
    /// <summary>
    /// 自定义顺序表
    /// </summary>
    /// <typeparam name="T"></typeparam>
    internal class MyArray<T>
    {
        /// <summary>
        /// 数据容器
        /// </summary>
        private T[] array;

        /// <summary>
        /// 表长度
        /// </summary>
        private int length;

        /// <summary>
        /// 初始化MyArray
        /// </summary>
        public MyArray(){
            this.length = 0;
            this.array = new T[10];
        }

        /// <summary>
        /// 初始化MyArray
        /// </summary>
        /// <param name="capacity">初始大小</param>
        public MyArray(int capacity)
        {
            this.length = 0;

            if (capacity <= 0)
            {
                this.array = new T[10];
            }
            else
            {
                this.array=new T[capacity];
            }
            
        }

        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {

            return this.length == 0; 
        }

        /// <summary>
        /// 元素数量
        /// </summary>
        /// <returns></returns>
        public int Count()
        {
            return this.length;
        }

        /// <summary>
        /// 插入
        /// </summary>
        /// <param name="index">索引</param>
        /// <param name="item">数据项</param>
        /// <returns></returns>
        public bool  Insert(int index,T item)
        {
            //索引检测
            if (index < 0 || index > this.length) return false;

            //容量检测
            if (this.length == this.array.Length)
            {
                //扩大为2倍
                T[] newArray = new T[this.length*2];

                //复制数据
                for (int i = 0; i < this.length; i++)
                {
                    newArray[i] = this.array[i];
                }

                //覆盖原始容器
                this.array = newArray;
            }

            //移动数据
            for (int i = this.length;i>index;i--)
            {
                this.array[i]=this.array[i-1];
            }

            //插入数据
            this.array[this.length++] = item;

            return true;
        }
        
        /// <summary>
        /// 新增
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            this.Insert(this.length, item);
        }

        /// <summary>
        /// 索引器
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T this[int index]
        {
            get
            {
                return this.array[index];
            }
            set
            {
                this.Insert(index,value);
            }
        }

        /// <summary>
        /// 清空所有元素
        /// </summary>
        public void Clear()
        {
            this.array=new T[10];
            this.length=0;
        }

        /// <summary>
        /// 移除元素
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public bool Remove(int index)
        {
            //索引检测
            if (index < 0 || index >= this.length) return false;

            //后半部分元素前移
            for (int i = index; i < this.length-1; i++)
            {
                this.array[i] = this.array[i + 1];
            }

            //末尾清空
            this.array[this.length - 1] = default(T);

            //更新长度
            this.length--;

            return true;
        }

        /// <summary>
        /// 获取值
        /// </summary>
        /// <param name="index">索引</param>
        /// <returns></returns>
        public T GetValue(int index)
        {
            //验证索引
            if (index < 0 || index >= this.length) return default(T);

            return this.array[index];
        }

        /// <summary>
        /// 设置值
        /// </summary>
        /// <param name="index">索引</param>
        /// <returns></returns>
        public bool SetValue(int index,T item)
        {
            //验证索引
            if (index < 0 || index >= this.length) return false;

            this.array[index]=item;

            return true;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
private void button6_Click(object sender, EventArgs e)
{
    this.list.SetValue(3, 100);

    this.listBox1.Items.Clear();
    for (int i = 0; i < list.Count(); i++)
    {
        this.listBox1.Items.Add(list[i]);
    }
}

本章总结

略

课后作业

略