数据结构顺序表思想以及完整代码实现
本文转载自趣学算法，方便个人学习参考使用 http://blog.csdn.net/rainchxy/article/details/77946835
数据结构 第3讲 顺序表
顺序表是最简单的一种线性结构，逻辑上相邻的数据在计算机内的存储位置也是相邻的，可以快速定位第几个元素，中间不允许有空，所以插入、删除时需要移动大量元素。
顺序表可以分配一段连续的存储空间Maxsize，用elem记录基地址，用length记录实际的元素个数，即顺序表的长度，
结构体的定义：
结构体定义后，如果要定义个顺序表L，就可以写：
SqList L;
1. 顺序表初始化
初始化是指给顺序表分配一个预定义大小的空间，用基地址elem记录这段空间的首地址，里面什么都没用，元素个数为0。前面我们已经预定义好了一个最大空间数Maxsize，那么就用new分配这么大的空间，分配成功会返回空间的首地址。假设顺序表里面需要存储整型数，那么就可以这样初始化：
boolInitList(SqList &L) //构造一个空的顺序表L
{ //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效
//不加&内部改变，跳出函数后无效
L.elem=new int[Maxsize]; //为顺序表分配Maxsize个空间
if(!L.elem) return false; //存储分配失败
L.length=0; //空表长度为0
return true;
}
2. 顺序表创建
顺序表创建是向顺序表中输入数据，输入数据的类型要与类型定义中的类型一致。假设顺序表里面需要存储整型数，那么就可以这样创建：
boolCreateList(SqList &L) //创建一个顺序表L
{ //L加&表示引用类型参数，函数内部的改变跳出函数仍然有效
//不加&内部改变，跳出函数后无效
int a,i=0；
while(a!=-1)
{
cin>>a;
if(L.length==Maxsize)
{
cout<<”顺序表已满！”
return false;
}
L.elem[i++]=a;
L.length++;
}
return true;
}
3. 顺序表取值
顺序表中的任何一个元素都可以立即找到，称为随机存取方式，例如我们我取第i个元素，只要i值是合理的（1≤i≤L.length），那么立即就可以找到该元素L.elem[i-1]：
bool GetElem(SqList L,int i,int &e)
{
if (i<1||i>L.length) return false;
//判断i值是否合理，若不合理，返回false
e=L.elem[i-1]; //第i-1的单元存储着第i个数据
return true;
}
4. 顺序表查找
在顺序表中查找一个元素e，需要从第一个元素开始顺序查找，依次比较每一个元素值，如果相等，则返回元素位置(第几个元素)，如果查找整个顺序表都没找到，则返回-1：
int LocateELem(SqList L,int e)
{
for (i=0;i< L.length;i++)
if (L.elem[i]==e) return i+1; //第几个元素，例如第5个元素，下标其实为4
return -1;
}
时间复杂性分析：
最好情况：如果元素正好在第一个位置，一次比较成功；时间复杂度为O(1);
最坏情况：如果元素正好在最后一个位置，需要比较n次成功，时间复杂度为O(n);
平均情况：假设每个元素查找概率均等，在第一个位置需要比较1次，第二个位置需要比较2次，…，最后一个位置，需要比较n次，把n种情况加起来平均，平均时间复杂度也为O(n)：
5. 顺序表插入
在顺序表中第i个位置之前插入一个元素e，需要从最后一个元素开始后移，…，直到把第i个元素也后移一位，然后把e放入第i个位置。
（1）判断插入位置i是否合法（1≤i≤L.length+1），可以在第n+1个元素之前插入。
（2）判断顺序表的存储空间是否已满。
（3）将第n至第i 位的元素依次向后移动一个位置，空出第i个位置。
（4）将要插入的新元素e放入第i个位置。
（5）表长加1，插入成功返回true。
bool ListInsert_Sq(SqList &L,int i ,int e)
{
if(i<1 || i>L.length+1) return false; //i值不合法
if(L.length==Maxsize) return false; //存储空间已满
for(j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j]; //从最后一个元素开始后移，直到第i个元素后移
L.elem[i-1]=e; //将新元素e放入第i个位置
L.length++; //表长增1
return true;
}
时间复杂性分析：
假设每个位置插入的概率均等，可以在第一个位置之前插入，第二个位置之前插入，…，最后一个位置之前，第n+1个位置之前，一共有n+1种情况，每种情况移动元素的个数是n-i+1，把所有情况加起来平均，平均时间复杂度为O(n)：
6. 顺序表删除
在顺序表中删除第i个元素，需要把该元素暂存到变量e，然后从i+1个元素开始前移，…，直到把第n个元素也前移一位，然后把e放入第i个位置。
（1）判断插入位置i是否合法（1≤i≤L.length）。
（2）将欲删除的元素保留在e中。
（3）将第i+1至第n 位的元素依次向前移动一个位置。
（4）表长减1，删除成功返回true。
bool ListDelete_Sq(SqList &L,int i, int &e)
{
if((i<1)||(i>L.length)) return false; //i值不合法
e=L.elem[i-1]; //将欲删除的元素保留在e中
for (j=i;j<=L.length-1;j++)
L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
L.length--; //表长减1
return true;
}
时间复杂性分析：
假设删除每个元素的概率均等，一共有n种情况，每种情况移动元素的个数是n-i，把所有情况加起来平均，平均时间复杂度为O(n)：
完整代码
1 #include <iostream>
2 using namespace std;
3 #define Maxsize 100//最大空间
4 typedef struct{
5 int *elem;
6 int length;//顺序表长度
7 }SqList;
8
9 bool InitList(SqList &L) //构造一个空的顺序表L
10 {//L加&表示引用类型参数，函数内部的改变跳出函数依然有效
11 //不加&表示内部改变，跳出函数后无效
12 L.elem=new int[Maxsize];//为顺序表分配Maxsize 个空间
13 if(!L.elem) return false;//存储分配失败
14 L.length=0;
15 return true;
16 }
17
18 bool CreateList(SqList &L)//创建一个顺序表L
19 {
20 int a,i=0;
21 cin>>a;
22 while(a!=-1){
23 if(L.length==Maxsize){
24 cout<<"顺序表已满！ ";
25 return false;
26 }
27 L.elem[i++]=a;
28 L.length++;
29 cin>>a;
30 }
31 return true;
32 }
33
34 bool GetElem(SqList L,int i,int &e){
35 if(i<1||i>L.length) return false;
36 //判断i值是否合理，若不合理，返回false
37 e=L.elem[i-1];//第i-1的单元存储着第i个数据
38 return true;
39 }
40
41 int LocateElem(SqList L,int x){
42 for(int i=0;i<L.length;i++)
43 if(L.elem[i]==x) return i+1;//第几个元素，例如第五个元素，下标其实为4
44 return -1;
45 }
46
47 bool ListInsert_Sq(SqList &L,int i,int e)
48 {
49 if(i<1||i>L.length+1) return false;//i值不合法
50 if(L.length == Maxsize) return false;//存储空间已满
51 for(int j=L.length-1;j>=i-1;j--)
52 L.elem[j+1]=L.elem[j];//从最后一个元素开始后移，直到第i个元素后移
53 L.elem[i-1]=e;//将新元素e放入第i个位置
54 L.length++;//表长加1
55 return true;
56 }
57
58 bool ListDelete_Sq(SqList &L,int i,int &e)
59 {
60 if((i<1)||(i>L.length)) return false;//i值不合法
61 e=L.elem[i-1];//将欲删除的元素保留在e中
62 for(int j=i;j<=L.length-1;j++)
63 L.elem[j-1]=L.elem[j];//被删除元素之后的元素后移
64 L.length--;//表长减少1
65 return true;
66 }
67
68 void print(SqList L)
69 {
70 cout<<"输出顺序表"<<endl;
71 for(int j=0;j<=L.length-1;j++)
72 cout<<L.elem[j]<<" ";
73 cout<<endl;
74 }
75
76 void DestroyList(SqList &L){
77 if(L.elem) delete []L.elem;//释放存储空间
78 }
79
80 int main()
81 {
82 SqList myL;
83 int i,e,x;
84 cout<<"1.初始化\n";
85 cout<<"2.创建\n";
86 cout<<"3.取值\n";
87 cout<<"4.查找\n";
88 cout<<"5.插入\n";
89 cout<<"6.删除\n";
90 cout<<"7.输出\n";
91 cout<<"8.销毁\n";
92 cout<<"0.退出\n";
93
94 int choose = -1;
95 while(choose != 0){
96 cout<<"请选择:";
97 cin>>choose;
98 switch(choose){
99 case 1://初始化顺序表
100 cout<<"顺序表初始化·····"<<endl;
101 if(InitList(myL))
102 cout<<"顺序表初始化成功！"<<endl;
103 else
104 cout<<"顺序表初始化失败！"<<endl;
105 break;
106 case 2://创建顺序表
107 cout<<"顺序表创建····"<<endl;
108 cout<<"输入整型数，输入-1结束"<<endl;
109 if(CreateList(myL))
110 cout<<"顺序表创建成功！"<<endl;
111 else
112 cout<<"顺序表创建失败！"<<endl;
113 break;
114 case 3://取值
115 cout<<"输入整型数i,取第i个元素输出"<<endl;
116 cin>>i;
117 if(GetElem(myL,i,e))
118 cout<<"第i个元素是："<<e<<endl;
119 else
120 cout<<"顺序表取值失败！"<<endl;;
121 cout<<"第i个元素是："<<e<<endl;
122 break;
123 case 4://查找
124 cout<<"请输入要查找的数x：";
125 cin>>x;
126 if(LocateElem(myL,x)==-1)
127 cout<<"查找失败！"<<endl;
128 else
129 cout<<"查找成功！"<<endl;
130 break;
131 case 5://插入
132 cout<<"请输入要插入的位置和要插入的数据元素e：";
133 cin>>i>>e;
134 if(ListInsert_Sq(myL,i,e))
135 cout<<"插入成功！"<<endl;
136 else
137 cout<<"插入失败!"<<endl;
138 break;
139 case 6://删除
140 cout<<"请输入要删除的位置i:";
141 cin>>i;
142 if(ListDelete_Sq(myL,i,e))
143 cout<<"删除成功！"<<endl;
144 else
145 cout<<"删除失败！"<<endl;
146 break;
147 case 7://输出
148 print(myL);
149 break;
150 case 8://销毁
151 cout<<"顺序表销毁·····"<<endl;
152 DestroyList(myL);
153 break;
154 }
155 }
156 return 0;
157 }
158