数据结构基础--线性表顺序存储

线性表是一对一的逻辑结构，对于非空的线性表和线性结构，特点如下：

• 存在唯一的一个被称作‘第一个’的数据元素；
• 存在唯一的一个被称作‘最后一个’的数据元素；
• 除了第一个之外，结构中的每一个数据元素均有一个前驱；
• 除了最后一个之外，结构中的每一个数据元素均有一个后继。
  注意：线性表的顺序存储，逻辑相邻，物理存储地址相邻
  下面我们来用代码对线性表进行针对性说明
  1.定义一个结构体,为了习惯使用，我们先起一些别名，代码如下

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;

/*线性结构使用顺序表的方式存储*/

//顺序表结构设计
typedef struct {
    ElemType *data;
    int length;
}Sqlist;

2.顺序表的初始化

//顺序表的初始化
Status InitSqlist(Sqlist *L){
    //为顺序表分配一个大小为MAXSIZE的数组空间
    L->data = malloc(sizeof(ElemType)*MAXSIZE);
    //判断分配空间是否成功
    if (!L->data) {
        exit(ERROR);
    }
    //空表长度 为0
    L->length = 0;
    return OK;
}

3.顺序表的插入，假设条件为：顺序表已经存在，并且1≤i≤L.lenght；在表的第i个位置之前插入新元素e,注意：插入元素表的长度lenght需要加1。

Status InsertSqList(Sqlist *L,int i, ElemType e){
    //需要先判断i的合法性，如果i的值大于表的长度或者是i小于1，已经超出表的范围则不能再插入数据
    if (i<1 || i > L->length +1) {
        return ERROR;
    }
    //如果表的存储空间已经满了，同样不能再插入数据
    if (L->length == MAXSIZE) {
        return ERROR;
    }
    //插入的数据不在表的最后
    if (i <= L->length) {
        for (int j = L->length; j < L->length -1; j--) {
            //将i以及之后的位置向后移动1位
            L->data[j+1] = L->data[j];
        }
    }
    //赋值
    L->data[i-1] = e;
    //长度+1
    ++L->length;
    return OK;
}

4.取出顺序表固定位置i上存储的数据

//使用指针将指定位置的值传出去
Status GetPositionElem(Sqlist L,int i, ElemType *e){
    //i值不合法判断
    if((i<1) || (i>L.length)) return ERROR;
    //找到存储的第i个数据元素data[i -1]
    *e = L.data[i-1];
    return OK;
}

5.删除顺序表上指定位置的数据,前提条件，顺序表存在，并且删除的位置在顺序表的长度范围1≤i≤lenght，注意删除成功之后，一定要将表长度length-1。

Status  deleteSqList(Sqlist *L,int i){
    //判断线性表是否为空，如果为空没有必要再删除操作
    if (L->length==0) {
        return ERROR;
    }
    //i值不合法判断
    if((i<1) || (i>L->length)) return ERROR;
    for (int j = i; j < L->length; j++) {
        //删除操作：将删除之后的元素向前移动1位
        L->data[j-1] = L->data[j];
    }
    //长度减1
    L->length--;
    return OK;
}

6.顺序表的清空，这个时候需要明白什么叫清空，删除数据？要怎么删除数据，全部置为0也不行，所以无论怎么设置删除操作，内存中都会有残留的数据，这个空间会一直存在，所以这时候我们做的的清空顺序表只需要将表的长度置为0即可。

Status ClearList(Sqlist *L)
{
    L->length=0;
    return OK;
}

7.判断顺序表是否已经被清空，同第6步操作相同，我们只需要判断顺序表的长度是否为0，只要满足了长度lenght==0，那么表就是空表了。

Status ListEmpty(Sqlist L)
{
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}

8.获取顺序表的长度，只需要根据结构体中的数据项lenght的值即可。

int ListLength(Sqlist L)
{
    return L.length;
}

9.遍历顺序表，假设表存在，依次对顺序表中的data输入就完成了。

Status TraverseSqlist(Sqlist L)
{
    int i;
    for(i=0;i<L.length;i++)
        printf("%d\n",L.data[i]);
    printf("\n");
    return OK;
}

验证结果

    
    Sqlist L;
    Sqlist Lb;
    ElemType e;
    Status iStatus;
    
    //1.1 顺序表初始化
    iStatus = InitSqlist(&L);
    printf("初始化L后: L.Length = %d\n", L.length);
    
    //1.2 顺序表数据插入
    for(int j=1; j <= 5;j++){
        iStatus = InsertSqList(&L, 1, j);
    }
    printf("插入数据L长度: %d\n",L.length);
    
    //1.3 顺序表取值
    GetPositionElem(L, 5, &e);
    printf("顺序表L第5个元素的值为:%d\n",e);
    
    //1.4 顺序表删除第2个元素
    deleteSqList(&L, 2);
    printf("顺序表删除第%d元素,长度为%d\n",2,L.length);
    
    //1.5 清空顺序表
    iStatus = ClearList(&L);
    printf("清空后,L.length = %d\n",L.length);
    
    //1.6 判断List是否为空
    iStatus= ListEmpty(L);
    printf("L是否空：i=%d(1:是 0:否)\n",iStatus);
    
    //1.8 TraverseList
    for(int j=1; j <= 5;j++){
        iStatus = ListInsert(&L, 1, j);
    }
    TraverseList(L);

以上程序运行后的结果： 程序运行结果