顺序表是线性表的实现方式之一，其特点是逻辑上相邻的元素在物理上也相邻。顺序表一般使用数组实现。因此顺序表可以随机访问，时

间复杂度为O(1)。但插入和删除元素时，由于线性表的有序性，要移动大量元素，时间复杂度为O(n).

本代码拟使用动态分配空间的方式存储顺序表元素。

一个顺序表结构类型如下：

1 struct SqList {
2     Elem* data;
3     int length;
4     int MaxSize;
5 };

其中length标记表中目前的元素个数；MaxSize标记这个顺序表可容纳的最大元素个数，data为顺序表首元素的地址。顺序表中第i个元素

为data[i-1].  可以使用如下代码初始化一个顺序表：

1 SqList L;
2 L.data = new ElemType;
3 L.length = 0;
4 L.MaxSize = MaxSize;    //MaxSize可以指定

 

 

 1 /*      顺序表
 2     实现操作：
 3      *1 按位插入
 4      *2 按位删除
 5      *3 按值查找
 6      *4 增加表长
 7                 */
 8 #include <iostream>
 9 #include <cstdio>
10 using namespace std;
11 
12 typedef int Elem;
13 
14 struct SqList {
15     Elem* data;
16     int length;
17     int MaxSize;
18 };
19 
20 //初始化传入的SqList 类型的变量L
21 bool InitList(SqList& L,int MaxSize)
22 {
23     L.data = new ElemType;
24     L.length = 0;
25     L.MaxSize = MaxSize;
26     return true;
27 }
28 
29 //按位插入:在位序i插入元素e  插入后元素e的位序为i
30 bool InsertList( SqList &L, int i,Elem e )
31 {
32     if( i < 1 || i > L.length + 1 )
33         return false;
34     if( L.length >= L.MaxSize )
35         return false;
36     for( int j=L.length; j>=i; j-- ) {
37         L.data[j] = L.data[j-1];
38     }
39     L.data[i-1] = e;
40     L.length++;
41     return true;
42 }
43 
44 //按位删除:删除位序为i的元素并用e将其值带回
45 bool deleteList( SqList& L, int i, Elem& e )
46 {
47     if( i < 1 || i > L.length )
48         return false;
49     e = L.data[i-1];
50     for( int j=i; j<L.length; j++ ) {
51         L.data[j-1] = L.data[j];
52     }
53     L.length--;
54     return true;
55 }
56 
57 //按值查找:返回表中第一个等于e的元素的位序
58 int locateElem( SqList& L, Elem e )
59 {
60     for( int i=0; i<L.length; i++ ) {
61         if( L.data[i] == e ) {
62             return i+1;
63         }
64     }
65     return -1;
66 }
67 
68 //增加长度:将顺序表的最大长度增加len
69 void increaseSize( SqList& L,int len )
70 {
71     Elem* p = L.data;
72     Elem* np = new Elem[L.length+len];
73     for( int i=0; i<L.length; i++ ) {
74         np[i] = p[i];
75     }
76     L.MaxSize += len;
77     delete p;
78 }
79 
80 int main()
81 {
82     SqList L;
83     InitList(L,100);
84     for( int i=1; i<100; i++ ) {
85         InsertList(L,i,i);
86     }
87     return 0;
88 }