【转】基础知识系列1--线性表之顺序表

原文地址：http://www.cnblogs.com/mcgrady/p/3181073.html

这个系列包括了C和C#两个版本的代码，我这里只取其中的C语言代码学习，另外我根据我的需要可能会打乱学习的顺序，对于源代码可能稍作修改，需要学习的博友们可以去原地址查看。

这一篇主要总结线性表之顺序表的相关操作，主要分以下几个部分来总结。

1，什么是线性表？
2，线性表的两种存储结构？
3，顺序表的存储结构表示？
4，顺序表的常见操作和代码实现？

1.什么是线性表

线性表就是关系中的一对一的关系，如果是一对多就用树来表示，如果多对多就用网状来表示。

线性表具有以下四个特征：

1> 有且只有一个“首”元素
2> 有且只有一个“尾”元素
3> 除“首”元素外，其余元素都有唯一的后继元素。
4> 除“尾”元素外，其余元素都有唯一的前驱元素。

2.线性表的两种存储结构

1> 顺序表，即线性表用顺序存储结构保存数据，数据是连续的。这一篇文章总结的就是顺序表
2> 链表，即线性表用链式存储结构保存数据，数据不连续。

3.顺序表的存储结构表示

4.顺序表的常见操作和代码实现

顺序表主要有以下常见操作，我们一般用数组来保存数据

1，初始化

思路：将数组的长度length设为0，时间复杂度为O(1)。

2，求顺序表的长度

思路：获取数组的length值，时间复杂度为O(1)。

3，插入元素

思路：分两种情况，一种是插入位置在数组的末尾，这种情况与添加元素相同。另一种情况是插入位置在数组的开始，这时候被插入元素的后续元素都要依次向后移动一位，也就是说整个数组都会移动，所以时间复杂度为O(n)。

4，删除元素

思路：同样分两种情况，一种是删除位置在数组的末尾，不用移动任何元素，因此时间复杂度为O(1);另一种情况是删除位置在数组的开始，这时被删除元素的后续元素都要依次向前移动一位，因此时间复杂度为O(n)。

5，按序号查找元素

思路：因为顺序表的存储地址是连续的，所以第n个元素的地址公式为：(n-1)*单元存储长度，不用移动任何元素，因此时间复杂度为O(1)。

6，按关键字查找元素

思路：一般用for循环，因此时间复杂度为O(n)。

代码实现：

  1 #include "stdio.h"
  2 
  3 #define OK    0
  4 #define ERROR -1
  5 #define MAXSIZE 5
  6 
  7 typedef int Status;
  8 typedef int ElemType;
  9 typedef struct　　//定义顺序表
 10 {
 11     ElemType data[MAXSIZE];
 12     int length;
 13 }SeqList;
 14 /*初始化*/
 15 Status InitSeqList(SeqList *seqList)
 16 {
 17     seqList->length = 0;
 18     return OK;
 19 }
 20 /*求顺序表的长度*/
 21 int GetSeqListLen(SeqList *seqList)
 22 {
 23     return seqList->length;
 24 }
 25 /*插入数据（在第n个元素之前的位置插入新元素）*/
 26 Status Insert(SeqList *seqList,int n,ElemType e)
 27 {
 28     int k;
 29 　　
 30     if(seqList->length>=MAXSIZE)　　//检查数组是否已满
 31         return ERROR;
 32 
 33     if((n<1)||(n>seqList->length+1))　　//检查n是否超出范围
 34         return ERROR;
 35 
 36     if(n<=seqList->length)　　//若插入位置不在表尾
 37     {　　
 38         for(k=seqList->length-1;k>=n-1;k--)
 39         {
 40             seqList->data[k+1] = seqList->data[k];　　//将要插入位置之后的元素依次向后移动一位
 41         }
 42     }
 43 　　//将新元素插入到腾出的位置，表长加一
 44     seqList->data[n-1] = e;
 45     seqList->length++;
 46     
 47     return OK;
 48 }
 49 /*删除元素*/
 50 Status Delete(SeqList *seqList,int n,ElemType *e)
 51 {
 52     int k;
 53 
 54     if(seqList->length == 0)　　//判断数组是否为空
 55         return ERROR;
 56     if((n<1)||(n>seqList->length))　　//判断n的位置是否合法
 57         return ERROR;
 58 
 59     *e = seqList->data[n-1];　　//保存删除的数字
 60 　
 61     if(n<seqList->length)
 62     {
 63         for(k=n;k<seqList->length;k++)
 64         {
 65             seqList->data[k-1] = seqList->data[k];　　//将删除位置后继元素依次前移
 66         }
 67     }
 68     
 69     seqList->length--;
 70     
 71     return OK;
 72 }
 73 /*查找元素*/
 74 int GetDataByIndex(SeqList *seqList,int n)
 75 {
 76     if((n<1)||(n>seqList->length))　　//检查是否超出范围
 77         return ERROR;
 78     return seqList->data[n-1];
 79 }
 80 /*打印顺序表*/
 81 void Display(SeqList *seqList)
 82 {
 83     int i;
 84     for(i=0;i<seqList->length-1;i++)
 85         printf("%d--",seqList->data[i]);
 86     printf("%d
",seqList->data[i]);
 87 }
 88 
 89 int main(void)
 90 {
 91     SeqList seqList;
 92     int j,k;
 93     Status i;
 94     ElemType elem;
 95 
 96     InitSeqList(&seqList);
 97 
 98     for(j=1;j<=5;j++)
 99     {
100         if(Insert(&seqList,j,j))
101         {
102             printf("Insert error.
");
103             return 0;
104         }
105     }
106     Display(&seqList);
107     
108     if(Delete(&seqList,3,&elem))
109     {
110         printf("Delete error.
");
111         return 0;
112     }
113     Display(&seqList);
114 
115     k=GetDataByIndex(&seqList,2);
116     if(k == -1)
117         printf("get data error.
");
118     else
119         printf("2th is %d
",k);
120 
121     printf("length is %d
",GetSeqListLen(&seqList));
122     return 0;
123 }