线性表_顺序结构

顺序存储结构：

逻辑上相邻的元素，物理上也相邻
表中任一数据元素的存放地址为： LOC ( ai ) = LOC( a0) + L * i

顺序表的实现：

typedef struct
{
    ElemType list[MaxSize]; //MaxSize是最大容量      
    int size;  //size是当前大小
} SequenceList;

顺序表的基本操作：

ListInitialize(L) 初始化线性表

//初始化 
void ListInitialize(SequenceList *L)    /*初始化顺序表L*/
{
    L->size = 0;                /*定义初始数据元素个数*/
}

ListLength(L) 获取当前元素个数

//获取元素个数
int ListLength(SequenceList L)      /*返回顺序表L的当前数据元素个数*/
{
    return L.size;
}

ListInsert(L,i,x) 插入数据元素

//插入数据 
/*在顺序表L的位置i（0 ≤ i ≤ size）前插入数据元素值x*/
/*插入成功返回1，插入失败返回0*/
int ListInsert(SequenceList *L, int i, ElemType x)
{
    int j;
    if(L->size >= MaxSize)
    {
        printf("顺序表已满无法插入! \n");
        return 0;
    }
    else if(i < 0 || i > L->size )
    {
        printf("参数i不合法! \n");
        return 0;
    }
    else
    {
        //从后往前，后退一个位置，直到j等于i的位置
        for(j = L->size; j > i; j--) 
        {
          L->list[j] = L->list[j-1];
        }
        L->list[i] = x;                                 /*插入*/
        L->size ++;                                 /*元素个数加1*/
        return 1;
    }
}

ListDelete(L,i,x) 删除数据元素

//删除数据 
/*删除顺序表L中位置i（0 ≤ i ≤ size - 1）的数据元素值并存放到参数x中*/
/*删除成功返回1，删除失败返回0*/
int ListDelete(SequenceList *L, int i, ElemType *x) 
{
    int j;
    if(L->size <= 0)
    {
        printf("顺序表已空无数据元素可删! \n");
        return 0;
    }
    else if(i < 0 || i > L->size-1)
    {
        printf("参数i不合法");
        return 0;
    }
    else
    {
        *x = L->list[i];                    /*保存删除的元素到参数x中*/
         //从i位置的后一位开始，依次往前移一位，直到最后
        for(j = i+1; j <= L->size-1; j++) 
        { 
          L->list[j-1] = L->list[j];
        }
        L->size--;                      /*数据元素个数减1*/
        return 1;
    }
}

ListGet(L,i,x) 取元素

//取数据 
/*取顺序表L中第i个数据元素的值存于x中，成功则返回1，失败返回0*/
int ListGet(SequenceList L, int i, ElemType *x)
{
    if(i < 0 || i > L.size-1)
    {
        printf("参数i不合法! \n");
        return 0;
    }
    else
    {
        *x = L.list[i];
        return 1;
    }
}

---

例子：
建立一个线性表，先依次输入数据元素1，2，3，4，… 10，然后删除５，最后依次显示当前线性表中的数据元素。假设该线性的数据元素个数最坏情况下不会超过100个。

#include<stdio.h>
#define MaxSize 100
typedef int ElemType;
#include"sequencelist.h"
void main(void)
{
    SequenceList myList; //声明 
    
    int i, x;
    ListInitialize(&myList); //初始化 
    
    for(i = 0; i<10; i++)
    {
        ListInsert(&myList, i, i+1); //插入 
    }
    ListDelete(&myList, 4, &x); //删除5即下标为4 
    
    for(i = 0; i<ListLength(myList); i++)
    {
        ListGet(myList, i, &x); //获取 
        printf("%d ", x);
    }
}

说明：
1.(.h)头文件的处理：先把被包含的文件内容复制到引用头文件的语句处，形成一个新的源程序，再编译成一个目标文件。
2.时间复杂度：在顺序表中插入或删除数据元素时，需要移动大量的元素，所以时间复杂度为O(n)；其余操作的时间复杂度都为O(1)。

算法设计举例:

1、设计一个顺序表的删除函数，把顺序表L中的数据元素x删除。

//成功返回1，不成功返回0
int ListDeleteX(SequenceList *L, ElemType x)
{
    int i, j;
    for(i=0; i<L->size; i++)
    {
        if(x == L->list[i])
        {
            break; //找到x则退出循环 ，此时x下标已被记录
        }
    }
    if(i == L->size) return 0;

    for(j = i; j<L->size; j++)
    {
        L->list[j] = L->list[j+1];  //向前移动一位
    }
    L->size--;
    return 1;           
} 

2、编写算法实现顺序表的逆置，要求把顺序表A中的数据元素序列（a0,a1,a2,…..an-1）逆置为（an-1, ….. a2, a1,a0）存储到顺序表B中。

void Converse(SequenceList la, SequenceList *lb)
{
    int i;
    ListInitialize(lb);
    for(i = 0; i<la.size; i++)
    {
        lb->list[i] = la.list[la.size-i-1];
        lb->size++;
    }
}

自身逆置：

void ConverseSelf(SequenceList *la)
{
    SequenceList lb;
    int i, j;
    ListInitialize(&lb);
    for(i = 0; i<la->size; i++)
    {
        lb.list[i] = la->list[la->size-i-1];
        lb.size++;
    }
    for(j = 0; j<lb.size; j++)
    {
        la->list[j] = lb.list[j];
    }
}

注： .访问普通结构体成员，->访问结构体指针