数据结构与算法：线性表之顺序存储

一、了解线性表

线性表是什么数据结构？

线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType， 其中除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每个元素有且只有一个后继元素。数据元素之间的关系是一对一的关系。

对于非空线性表和线性结构，特点总结如下：

• 存在唯一的一个被称作第一个的数据元素
• 存在唯一一个被称作最后一个的数据元素
• 除了第一个之外，结构中的每一个数据元素均有一个前驱
• 除了最后一个之外，结构中的每一个数据元素都有一个后继

二、线性表操作

InitList(&L);
操作结果：初始化操作，建立一个空的线性表L

DestoryList(&L);
初始条件：线性表L已存在
操作结果：销毁线性表L

ClearList(&L);
初始条件：线性表L已存在
操作结果：将L置为空表

ListEmpty(L);
初始条件：线性表L已存在
操作结果：若L为空表，则返回true，否则返回false

ListLength(L);
初始条件：线性表L已存在
操作结果：返回L表数据元素的个数

GetElem(L,i,&e);
初始条件：线性表L已存在，且1<=i<ListLength(L)
操作结果：用e返回L中第i个数据元素的值

LocateElem(L,e);
初始条件：线性表L已存在
操作结果：返回L中第1个值与e相同的元素在L中的位置，若数据不存在则返回0

PriorElem(L，cur_e, &pre_e);
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回其前驱，否则操作失败

NextElem(L,cur_e,&next_e);
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回其后继，否则操作失败

ListInsert(L,i,e);
初始条件：线性表L已存在，且插入的位置i满足 1<= i <= listLength(L)
操作结果：在L中第i个位置之前插入新的元素e，L长度加1

ListDelete(L,i);
初始条件：线性表L已存在，且 1<= i <= listLength(L)
操作结果：删除L的第i个元素，L长度减1

TraverseList(L);
初始条件：线性表L已存在
操作结果：对线性表L进行遍历，在遍历的时候对L的每个结点访问1次

...

三、线性表的顺序存储 操作代码案例

//
//  main.m
//  LineChart
//  数据结构与算法 - 线性表（顺序结构实现）
//  Created by battleMage on 2020/6/17.
//  Copyright © 2020 battleMage. All rights reserved.
//

#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"

//定义部分
#define ERROR 0
#define OK 1
#define MAXSIZE 100

typedef int ElementType;
typedef int Status;

//定义一个结构体
typedef struct {
    ElementType *data;
    int length;
}sqlite;

//1、顺序存储-线性表的初始化
Status InitList(sqlite *L) {
    L->data = malloc(sizeof(ElementType) * MAXSIZE);
    if (!L->data)return ERROR;
    L->length = 0;
    return OK;
}

//2、顺序存储-线性表插入元素
//在L中第i个位置前插入元素e
Status ListInsert(sqlite *L, int i, ElementType e) {
    //判断线性表是否存在，插入的位置是否合法，找到位置进行位移，线性表长度加1
    //i值不合法判断
    if ((i < 1) || (i > L->length + 1)) return ERROR;
    //存储空间满了
    if (L->length == MAXSIZE) return ERROR;
    //插入数据不在表尾，则需要挪动位置,把i之后的元素都往后挪一位
    if (i <= L->length) {
        for (int j = L->length - 1; j > i+1; j--) {
            //插入位置以及之后的位置都往后挪一位
            L->data[j+1] = L->data[j];
        }
    }

    //将新元素e放到第i个位置,第i个位置前一个的下标为i-1
    L->data[i-1] = e;
    
    //表长度加1
    L->length++;
    return OK;
}

//3、顺序存储-线性表删除元素
//删除L中第i个元素
Status ListDelete(sqlite *L, int i) {
    //判断线性表是否为空
    if(L->length == 0)return ERROR;
    //i值不合法判断
    if ((i<1) ||(i>L->length + 1)) return ERROR;
    
    //删除元素之后的往前挪一位,顺序存储只需要把元素往前挪，把前面元素的空间占住就行了
    for (int j = i; j < L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    //表长度减1
    L->length--;
    return OK;
}


//4、遍历线性表的元素并打印
Status TraverseList(sqlite *L) {
    for (int i = 0; i < L->length; i++) {
        printf("%d\n", L->data[i]);
    }
    return OK;
}


//5、清空顺序表
Status ClearList(sqlite *L) {
    L->length = 0;
    return OK;
}





int main(int argc, const char * argv[]) {
    
    sqlite L;
    sqlite Lb;
    ElementType e;
    Status iStatus;
    
    //线性表初始化
    iStatus  = InitList(&L);
    printf("1、线性表初始化%s\n", iStatus == 1 ? "OK" : "ERROR");
    
    //插入元素
    ListInsert(&L, 1, 6);
    ListInsert(&L, 2, 5);
    ListInsert(&L, 3, 4);
    
    
    //遍历打印
    iStatus = TraverseList(&L);
    printf("2、插入元素后打印%s\n", iStatus == 1 ? "OK" : "ERROR");
    
    //删除
    ListDelete(&L, 1);
    
    //遍历打印
    iStatus = TraverseList(&L);
    printf("3、删除元素后打印%s\n", iStatus == 1 ? "OK" : "ERROR");
    
    //清空
    ClearList(&L);
    
    //遍历打印
    iStatus = TraverseList(&L);
    printf("4、清空数组后打印\n");
    
    return 0;
}

溪浣双鲤的技术摸爬滚打之路