线性是一种逻辑结构，表示元素与元素之间一对一的相邻关系。顺序表和链表是指存储结构。
本文首先讨论的是顺序表。要构造顺序表首先要了解其结构。
顺序表用一组连续地址一次存放线性表中元素，使得逻辑上相邻的元素物理上也相邻。
顺序表使用数组来描述顺序存储结构。而数组又分为动态分配和静态分配。
接下来结合代码来了解动态分配和静态分配以及关于顺序表的种种操作。为方便代码上机运行练习，表中元素定义为int.
静态分配
定义
从一开始，数组的空间和大小已经固定，不能更改。如果空间已满再加入数据，会产生溢出。
复制代码
1
2
3
4
5#define MaxSize 10 //定义最大长度 typedef struct{ int data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表的当前长度 }SqList; //顺序表的类型定义
顺序表包括两项内容：1.表中数据；2.表的长度。由于顺序表长度固定，最开始需要定义一个最大长度，来表示顺序表中最多能存放多少元素。
初始化
定义一个顺序表后，需要对其进行初始化。初始表中无元素，需要将其长度设为0.
复制代码
1
2
3
4
5
6//初始化一个静态顺序表 void InitList(SqList &L){ for(int i = 0; i < MaxSize; i++) L.data[i] = 0; //将所有数据元素设置为默认初始值 L.length = 0; //顺序表初始长度为0 }
定义一个函数，获取顺序表的长度：
复制代码
1
2
3
4//返回顺序表长度 int Length(SqList &L){ return L.length; }
查找
顺序表具有随机存取的特点。查找时，即可按值查找，也可按位置查找。
按值查找
按值查找时，需要传入两个参数：1.顺序表 2.数值
按值查找需顺序遍历整个顺序表。由于数组下标从0开始，位序从1开始，返回值需+1.当顺表中找不到此值时，返回-1表示表中无此数据。
复制代码
1
2
3
4
5
6
7
8//按值查找 int LocateElem(SqList &L,int e){ for(int i = 0;i < L.length;i++){ if(L.data[i] == e) return i+1; } return -1; }
按位查找
按位查找时，需要传入两个参数：1.顺序表 2.位序
对位序需要验证其合法性。顺序表的大小范围为0~MaxSize，若位序值不在此区间即为不合法值。
使用位序求对应数据值只需直接使用下标索值。
复制代码
1
2
3
4
5
6
7//按位查找 bool GetElem(SqList &L,int i,int& e){ if(i > L.length||i < 1||L.length == MaxSize) return false; e = L.data[i-1]; return true; }
插入
向一个顺序表中插入数据时，需要传入顺序表、位序以及数据值。
向表中添加数据需要多考虑到一个问题，此时表是否已满。
顺序表的数据为线性存放，插入一个数据前需要将其后所有数据后移一位。插入后列表长度+1.
复制代码
1
2
3
4
5
6
7
8
9
10//插入操作 bool Insert_List(SqList &L,int i,int e){ if(i > L.length+1||i < 1||L.length == MaxSize) return false; for(int j = L.length;j > i-1;j--) L.data[j] = L.data[j-1]; L.data[i-1] = e; L.length++; return true; }
删除
与插入类似，将需要删除的数据删除后，需要将其后所有数据前移一位，并将顺序表长度-1.
复制代码
1
2
3
4
5
6
7
8
9
10bool Delete_List(SqList &L,int i,int &e){ if(i > L.length||i < 1||L.length == MaxSize) return false; e = L.data[i-1]; for(int j = i-1;j < L.length-1;j++){ L.data[j] = L.data[j+1]; } L.length--; return true; }
输出
当顺序表不为空是，顺序遍历表中所有数据并输出。
复制代码
1
2
3
4
5
6
7
8
9//输出操作 void PrintList(SqList &L){ if(L.length == 0) cout<<"此表为空表！"<<endl; else for(int i = 0;i < L.length;i++) cout<<"data["<<i<<"]="<<L.data[i]<<endl; }
判空
顺序表可直接使用顺序表长度判空。
复制代码
1
2
3
4
5
6
7//判空 bool isEmpty(SqList &L){ if(L.length == 0) return true; else return false; }
销毁
静态分配，系统会自动回收空间，销毁顺序表只需将顺序表长度置为0.
复制代码
1
2
3
4//销毁操作 bool DestroyList(SqList &L){ L.length = 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
59int main(){ SqList L; //声明一个顺序表 InitList(L); //初始化顺序表 cout<<"顺序表长度为"<<Length(L)<<endl; int num; cout<<"请输入要添加元素的个数："; cin>>num; cout<<endl; for(int i = 0;i < num;i++){ int e; cout<<"请输入第"<<i+1<<"个元素："; cin>>e; if(Insert_List(L,i+1,e) == false) cout<<"表中元素已达到最大数量！不能再继续添加！"<<endl; cout<<Length(L)<<endl; } cout<<Length(L)<<endl; PrintList(L); int i,e; cout<<"请输入要插入元素的位置："; cin>>i; cout<<endl; cout<<"请输入插入的元素："; cin>>e; cout<<endl; Insert_List(L,i,e); PrintList(L); cout<<"请输入要删除元素的位置："; cin>>i; cout<<endl; Delete_List(L,i,e); cout<<"所删元素的值为："<<e<<endl; PrintList(L); //按值查找 cout<<"请输入要查找的元素的值："; cin>>e; cout<<endl; i = LocateElem(L,e); if(i == -1) cout<<"此值不在顺序表中！"<<endl; else cout<<e<<"在顺序表第"<<i<<"个位置。"<<endl; //按位查找 cout<<"请输入要查找的元素在顺序表中的位置："; cin>>i; cout<<endl; if(GetElem(L,i,e)) cout<<"第"<<i<<"个位置的元素是："<<e<<endl; else cout<<"输入的位置不合法！"<<endl; //……后续操作 return 0; }
动态分配
动态分配与静态分配的主要区别是可以改变顺序表的长度，存储数组的空间是通过动态存储分配语句分配的。当原有空间已满时，就另外开辟一块更大的空间，用以替换原来的空间。从而达到扩充存储空间的目的。动态分配的顺序表基本操作原理和静态分配大致相同，不做详细阐述。
定义
复制代码
1
2
3
4
5
6#define InitSize 100 typedef struct{ int *data; //动态分配数组的指针 int length; //顺序表的长度 }SqList;
注：动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式。
初始化
复制代码
1
2
3
4
5
6//初始化表 void Init_list(SqList &L){ //L.data = (int*)malloc(sizeof(int)*InitSize); //c语言的分配方式 L.data = new int[InitSize]; L.length = 0; }
插入
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//向表中插入元素 bool ListInsert(SqList &L,int i,int e){ //判断插入元素的位置以及插入后顺序表的长度是否合法 if(i > L.length+1||i < 1||L.length == InitSize) return false; //插入数据前需要将包括插入位置的元素后移一位 for(int j = L.length; j >= i; j--) L.data[j] = L.data[j-1]; //插入数据并修改顺序表的长度 L.data[i-1] = e; L.length++; return true; }
删除
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15//删除并返回删除元素的值 bool ListDelete(SqList &L,int i,int &e){ //判断要删除的元素所在位置是否合法 if(i > L.length||i < 1) return false; //获取要删除元素的值 e = L.data[i-1]; //从删除的位置开始对后面的元素前移，修改顺序表的长度 for(int j = i;j < L.length;j++) L.data[j-1] = L.data[j]; L.length--; return true; }
查找
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18//返回指定元素的位置 int LocateElem(SqList L,int e){ for(int i = 0; i < L.length; i++) //顺序遍历整个表 if(L.data[i] == e){ return i+1; } return -1; //如果没有在表中找到此元素，返回-1 } //返回表中对应位置的元素 int GetElem(SqList L,int i){ if(i > L.length||i < 1) return -1; else return L.data[i-1]; }
打印
复制代码
1
2
3
4
5
6
7
8//打印整个表 void PrintList(SqList L){ if(L.length < 1) cout<<"此表为空！"<<endl; else for(int i = 0; i < L.length; i++) cout<<"data["<<i+1<<"] = "<<L.data[i]<<endl; }
判空
复制代码
1
2
3
4
5
6
7
8//判断此表是否为空 void Empty(SqList L){ if(L.length == 0) cout<<"此表为空！"<<endl; else cout<<"此表不为空！"<<endl; }
销毁
复制代码
1
2
3
4
5
6
7
8
9
10//销毁整个表 void DestroyList(SqList &L){ if(L.data){ delete[] L.data; L.data = NULL; } L.length = 0; cout<<"销毁成功！"<<endl; }
测试代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24int main(){ SqList test; Init_list(test); int list_Count; cout<<"请输入要添加的元素的个数！"<<endl; cin>>list_Count; for(int i = 0; i < list_Count; i++){ int elem; cout<<"请输入第"<<i+1<<"个元素："<<endl; cin>>elem; if(ListInsert(test,i+1,elem)) cout<<"添加成功！"<<endl; else cout<<"添加失败！"<<endl; } PrintList(test); //int length = Length(test); //cout<<length<<endl; return 0; }
最后
以上就是冷傲老师最近收集整理的关于线性表——顺序表（含代码）静态分配动态分配的全部内容，更多相关线性表——顺序表（含代码）静态分配动态分配内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复