数据结构复习·1 线性表：顺序表
宏定义
1
2
3
4
5
6
7
8
| #include<iostream>
#define MAXSIZE 100
using namespace std;
typedef char ElemType;
typedef struct{
ElemType *data;
int length;
}SqList;
|
顺序表操控函数
1.初始化顺序表L
1
2
3
4
5
6
| bool Initlist_Sq(SqList &L){
L.data = new ElemType[MAXSIZE];
if(!L.data) return 0;
L.length = 0;
return 1;
}
|
2.在顺序表的指定位置插入数据
1
2
3
4
5
6
7
8
9
10
| bool ListInsert_Sq(SqList &L,int i,ElemType e){
if((i<1)||(i>L.length+1)) return 0;
if(L.length==MAXSIZE) return 0;
for(int j=L.length-1;j>=i-1;j--){
L.data[j+1] = L.data[j];
}
L.data[i-1] = e;
++L.length;
return 1;
}
|
时间复杂度
最好情况：在表尾插入(i=n+1) 元素后移语句不执行 时间复杂度O(1)
最坏情况：在表头插入(i=1) 元素后移语句执行n次 时间复杂度O(n)
平均情况：移动结点平均次数为$\frac{n}{2}$
因此 顺序表插入算法平均时间复杂度为O(n)
3.在顺序表指定位置删除数据
1
2
3
4
5
6
7
8
| bool ListDelete_Sq(SqList &L,int i){
if(i<1||i>L.length) return 0;
for(int j=i;j<=L.length-1;j++){
L.data[j-1] = L.data[j];
}
--L.length;
return 1;
}
|
时间复杂度
最好情况：删除表尾元素(i=n) 无须移动元素 时间复杂度O(1)
最坏情况：删除表头元素(i=1) 移动除第一个元素外的所有元素 时间复杂度O(n)
平均情况：移动结点平均次数为$\frac{n-1}{2}$
因此 顺序表删除算法平均时间复杂度为O(n)
4.遍历整个表的数据元素并输出
1
2
3
4
5
6
| int ShowList(SqList L){
for(int i=0;i<L.length;i++){
cout<<L.data[i]<<" ";
}
cout<<endl;
}
|
5.销毁顺序表
1
2
3
4
5
| int DestroyList(SqList &L)
{
if (L.data) delete[]L.data;
return 1;
}
|
所有代码
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
| #include<iostream>
#define 1 1
#define 0 0
#define 0 -2
#define MAXSIZE 100
using namespace std;
typedef int bool;
typedef char ElemType;
typedef struct{
ElemType *data;
int length;
}SqList;
bool Initlist_Sq(SqList &L){
L.data = new ElemType[MAXSIZE];
if(!L.data) exit(0);
L.length = 0;
return 1;
}
bool ListInsert_Sq(SqList &L,int i,ElemType e){
if((i<1)||(i>L.length+1)) return 0;
if(L.length==MAXSIZE) return 0;
for(int j=L.length-1;j>=i-1;j--){
L.data[j+1] = L.data[j];
}
L.data[i-1] = e;
++L.length;
return 1;
}
bool ListDelete_Sq(SqList &L,int i){
if(i<1||i>L.length) return 0;
for(int j=i;j<=L.length-1;j++){
L.data[j-1] = L.data[j];
}
--L.length;
return 1;
}
int CleanList(SqList &L){
L.length = 0;
return 1;
}
int GetLength(SqList L){
return (L.length);
}
int ShowList(SqList L){
for(int i=0;i<L.length;i++){
cout<<L.data[i]<<" ";
}
cout<<endl;
}
int DestroyList(SqList &L)
{
if (L.data) delete[]L.data;
return 1;
}
int main(){
int i,len;
ElemType e;
SqList L;
if (Initlist_Sq(L)) cout<<"顺序表初始化成功"<<endl;
else cout<<"顺序表初始化失败"<<endl;
cout<<"输入相应的数字来进行相应的操作"<<endl;
int c = -1;
while(c!=0){
cout<<"1.提供一个位置插入一个元素 2.删除提供位置的一个元素 3.求表长 4.获取表内所有的元素 5.清空表 0. exit"<<endl;
cin>>c;
switch(c){
case 1:{
cout<<"请输入位置的序号和插入的元素"<<endl;
cin>>i>>e;
if (ListInsert_Sq(L,i,e)) cout<<"插入成功"<<endl;
else cout<<"插入失败"<<endl;
break;
}
case 2:{
cout<<"请输入删除元素的位置序号"<<endl;
cin>>i;
if (ListDelete_Sq(L,i)) cout<<"删除成功"<<endl;
else cout<<"删除失败"<<endl;
break;
}
case 3:{
len = GetLength(L);
cout<<"表的长度为"<<len<<endl;
break;
}
case 4:{
ShowList(L);
break;
}
case 5:{
if (CleanList(L)) cout<<"清空成功"<<endl;
else cout<<"清空失败"<<endl;
break;
}
}
}
if (DestroyList(L)) cout<<"顺序表已销毁"<<endl;
else cout<<"顺序表销毁失败"<<endl;
return 0;
}
|
后记
下一篇准备写单链表
