线性表-顺序存储结构

线性表-顺序存储结构（即数组）

1、定义：零个或多个数据元素组成的有限序列。

　　如果用数学语言来进行定义。可如下：

　　若将线性表记为（a₁,……，a_i-1,a_i,a_i+1,……,an),则表中a_i-1领先于a_i,a_i领先于a_i+i，称a_i-1是a_i的直接前驱元素，a_i+i是a_i的直接后驱元素。         当i=1,2,……,n-1时，ai有且仅有一个直接后继，当i=2,3,……,n时，a_i有且仅有一个直接前驱。第一个无前驱，最后一个无后继，其余元素都有一个直接前驱和直接后继。如图所示：

所以线性表的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。

线性表的抽象数据类型：对数据类型进行抽象，抽取出事务具有的普遍性的本质，是特征的概括，而不是细节。

　　ADT 线性表（List）
　　Data

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

Operation:

    InitList(*L);//构造一个空的线性表 L。
    ClearList(*L);//线性表L已存在。将L重置为空表。
    ListEmpty(L);//线性表L已存在。若L为空返回True，否则返回False。
    ListLength(L);//线性表L已存在。返回L中数据元素的个数。
    GetElem(L, i, *e);//线性表L已存在。用e返回L中第i个数据元素的值。
    LocateElem(L, e);//线性表L已存在。查找元素在线性表中的位置
    ListInsert(*L, i, e);//线性表L已存在。在L中第i个位置之前插入新的数据元素e。
    ListDelete(*L, i, *e);//线性表L已存在。删除L中第i个数据元素，并用e返回其值。

2、线性表的顺序存储结构

　　类似于数组，元素依次排放。顺序结构封装的三个属性：数据起始地址，线性表最大长度，当前线性表长度。线性表是从1开始，而数组是从0开始。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20    /*存储空间初始分配量*/
typedef int ElemType;    /*ElemType 类型根据实际情况而定，这里假设为int*/

typedef struct
{
    ElemType data[MAXSIZE];    /*数组存储数据元素，最大值为MAXSIZE*/
    int length;    /*线性表的当前长度*/
}SqList; /*表名*/

int InitList(SqList *L) //初始化
{
    L->length = 0;
    for (int i = 0;i < MAXSIZE;i++)
        L->data[i] = 0;

    return OK;
}

//清空
int ClearList(SqList *L)
{
    L->length = 0;
    for (int i = 0;i < MAXSIZE;i++)
        L->data[i] = 0;

    return OK;
}

//判断线性表是否为空
int ListEmpty(SqList L)
{
    if (L.length == 0)
        return TRUE;
    else
        return FALSE;
}

//获取线性表的长度
int ListLength(SqList L)
{
    return L.length;
}

/*用e返回L中第i个数据元素的值*/
int GetElem(SqList L, int i, ElemType *e)
{
    if (L.length == 0 || i<1 || i>L.length)
        return ERROR;
    *e = L.data[i - 1]; /*线性表中的数据和正常一样，从1开始，而数组是从0开始*/
    return OK;
}

//获取指定元素的位置
int GetLocate(SqList L, ElemType e)
{
    if (L.length == 0)
        return ERROR;

    int i = 0;
    for (;i < MAXSIZE;i++)
        if (L.data[i] == e)
            break;
    if (i >= MAXSIZE)
        return ERROR;
    
    return (i + 1);
}

/*在L中第i个位置之前插入新的数据元素e，L的长度加1*/
int ListInsert(SqList *L, int i, int e)
{
    if (i < 1 || i > L->length + 1) /*当i不在范围内时*/ // || 前面若为真，则不再判断后面的语句
        return ERROR;                                    // || 前面若为假，则再判断后面的语句是否为真
    if (L->length == MAXSIZE) /*顺序线性表已满*/
        return ERROR;
    
    for (int k = L->length - 1;k >= i - 1;k--) //将要插入位置后数据元素后移
        L->data[k + 1] = L->data[k];
     /*for (int k = L->length;k >= i;k--)
        L->data[k] = L->data[k - 1];  这两种for循环都可以*/ 

    L->data[i - 1] = e;
    L->length++;
    return OK;
}

/*删除L中第i个数据元素，并用e返回其值，L的长度减1*/
int ListDelete(SqList *L, int i, ElemType *e)
{
    if (L->length == 0) /*线性表为空*/
        return ERROR;
    if (i < 1 || i > L->length)/*位置不合理*/
        return ERROR;

    *e = L->data[i - 1];
    for (;i < L->length;i++)
        L->data[i - 1] = L->data[i]; /*将删除位置后继元素前移*/

    L->data[L->length - 1] = 0;
    L->length--;
    return OK;
}

//打印
void PrintList(SqList L)
{
    for (int i = 0;i < L.length;i++)
        printf("%d ", L.data[i]);
    printf("
");
}

void main()
{
    
    SqList L;
    ElemType e;
    printf("1.Initial List
");
    InitList(&L);

    printf("2.Insert Element 1-10 
"); //此时根本未使用for循环
    for (int i = 1;i <= 10;i++)
    {
        ListInsert(&L, i, i); 
        
    }
    PrintList(L);
    std::cout << "Now the length of the LIst : " << ListLength(L)<<std::endl;

    printf("3.Insert 99 at the Location of 5：
");
    ListInsert(&L, 5, 99);
    PrintList(L);

    printf("4A.ListDelete the first: 
");
    ListDelete(&L, 1, &e);
    PrintList(L);
    std::cout << "Now the length of the LIst : " << ListLength(L) << std::endl;

    printf("4B.ListDelete the end: 
");
    ListDelete(&L, ListLength(L), &e);
    PrintList(L);

    printf("5. find element use GetElem by index(6): ");
    GetElem(L, 6, &e);
    printf("%d 
", e);

    printf("6. find element:99 index by LocateElem:");
    printf("%d 
", GetLocate(L, 99));

    printf("7.Get List length:%d
", ListLength(L));

    printf("8.ClearList
");
    ClearList(&L);
    if (ListEmpty(L) == OK)
        printf("Now List is empty
");


    system("pause");
}