线性表（Linear List）

基本概念

线性表是由n（n>=0）个类型相同数据元素组成的有限序列。数据元素可由若干个数据对象组成，且一个线性表中的数据元素必须属于同一数据对象。

线性表示n个类型相同数据元素的有限序列，对n>0,除第一个元素无直接前驱，最后一个元素无直接后继外，其余的每个数据元素只有一个直接前驱和直接后继。

线性表的逻辑结构如图：

线性表具有如下特点：

同一性：线性表由同类数据元素组成，每个元素必须属于同一数据类型。

有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。

线性表中相邻数据元素之间存在着序偶关系。

? ?

线性表的顺序存储

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中，即通过数据元素物理存储的连续性来反映数据元素逻辑上的相邻关系。

采用顺序存储结构存储的线性表通常简称为顺序表。可将顺序表归纳为：关系线性化，结点顺序化。

顺序存储表示

定义

用c语言定义线性表的顺序存储结构：

typedef struct{
    char data[MAXSIZE];    
    int len;    //数据长度 
}List;

那么线性表的存储地址是如何计算的呢？

假设线性表中有n个元素,每个元素占?sizeof(ElemType)个单元,则第一个元素的地址为?LOC(A)?,则第n个元素的地址为：?LOC(n) = LOC(A) + (n-1)* sizeof(ElemType)?。

顺序表的存储结构如下：

? ?

我们只是定义了顺序表，还没有创建呢！

创建

//初始化顺序表 
List* initList(List *L){
    int num,i;
    char ch;
    //输入顺序表长度
    printf("请输入顺序表长度（0<len<100): ");
    scanf("%d",&num);
    L->len = num;
    
    //输入数据 
    for(i = 0; i < L->len; i++){
        getchar();
        printf("请输入第 %d 个数：",i);
        scanf("%c",&ch);
        L->data[i] = ch;
    }
    return L;
}

基本操作

线性表的基本操作有查找，插入，删除。

查找

查找分为两种：1.可以按序号查找?getAsNum(L,i)?:查找线性表L中第i个数据元素。2.按内容查找?getAsContent(L,content)?:查找顺序表L中的和Content相等的数据元素

【算法思想】：按内容查找运算可采用顺序查找，即从第一个元素开始，依次将表中元素content相比较，若想等，则查找成功，返回该元素在表中的序号；若都不想等，则查找失败，返回-1

【算法描述】按内容查找算法

//按内容查找
int getAsContent(List L,char content){
    unsigned int i = 0; 
    while(i >= 0 || i <= L.len - 1){
        //顺序扫描表，找到对应元素，或者扫描完则退出 
        if(L.data[i] != content){
            i++;
        }else{ 
            break;
        }
    }
    if(i <= L.len - 1){
        //找到则输出并返回序号 
        printf("按内容查找成功，第 %d 个位置元素为 %c \n\n",i,L.data[i]);
        return i;
    }else{
        //未找到 
        printf("查找失败，没有你所找的元素！\n\n");
        return ERROR; 
    }
}

小结：查找时要注意判断表中没有你要查找的元素的情况，此算法时间复杂度为O(n)。

插入

插入操作指在第i个元素之前插入一个新的元素，这时线性表的长度就变成了n+1了。

【算法思想】：用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将原表位置的n，n-1，……，i上的结点依次后移一个位置（此时原表移动对应得位置为n+1，n，……，i+1），空出第i个位置，然后在该位置插入新结点。注意插入的位置为表尾时的情况。

【算法描述】顺序表的插入运算

int insertList(List *L,int i,char content){
    int k;
    
    //插入的位置不在表的范围 
    if(i < 0 || i >= L->len){
        printf("插入位置不合法！\n\n");
        return ERROR;
    }
    
    //考虑表满的情况 
    if(L->len == MAXSIZE){
        printf("表已满！无法插入！\n\n");
        return ERROR;
    }else if(i >= 0 && i <= L->len - 1){
        
        //插入位置后的元素向后移动 
        for(k = L->len - 1; k >= i; k--){
            L->data[k+1] = L->data[k];
        }
        L->data[i] = content;
        //表长度加一 
        L->len++;
        printf("插入成功！\n\n");
        print(L);
        return OK;
    }
} ?

小结：设E为在长度为n的表中插入一元素所需移动元素的平均次数，假设为在第i个元素之前插入元素的概率，并假设在任何位置上插入的概率相等，即,i = 1,2,……,n+1,则有：

?

删除

线性表的删除操作指的是将表的第i个（1<=i<=n）个元素删去，使长度为n的线性表变成长度为n-1的线性表

【算法思想】：类似于插入操作，用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，空出第i个位置就要将原表位置的上的结点依次前移一个位置。

（编辑：ASP站长网）