线性表的定义及逻辑结构

线性表就是零个或多个类型相同的数据元素，组成有限序列线性表抽象的记为:a1,a2,a3,a4,a5…an
一个线性表中的数据元素属于同一个数据对象
线性表的数据元素的个数为n（n>0）线性表的长度
当线性表数据元素的个数n=o 时，为空表

线性表的基本操作

初始化InitList(L),构造一个空表的线性表
判断线性表是否为空表,EmptyList(L):如果线性表为空，返回真，否则返回假
返回线性表的长度lengthList(L):返回线性表中所含元素的个数
获取线性表中第I个元素操作GetList(L，i),i是数据元素在线性表中的位序，i位置的要求 ,1<=i <= lengthList(L),返回线性表L中第I个元素的值或地址
按值查找操作LocalList(L,x)在线性表L(a1,a2…ai,…an)中查找X,如果线性表L中存在值和X相等的数据元素，函数返回这个数据元素在线性表中的位序，否则返回-1
插入操作InsertList(L,I,X)在线性表L(a1,a2…ai…,an)中第I个数据元素I之前插入一个新的数据元素x插入位置，1<= i <= lengthList(L)+1，插入I之后的线性表L的表长等于原线性表长度+1
删除操作，DeleteList(L,i)在给定的线性表L(a1,a2…ai,…an)中删除序号为I的数据元素删除位置I要求 1<=i <= lengthList(L)删除之后：L的长度等于原表长-1

思考题

将两个或两个以上的线性表合并成一个线性表
把一个线性表拆分成两个或两个以上的线性表
复制一个线性表
对线性表中的数据元素按照某个数据项进行排序

线性表的顺序结构

用一组地址连续的存储单元，依次存储线性表的数据元素

存放位置从起始地址为b的一段连续的存储单元中，逻辑上相邻的两个元素在物理上也相邻

线性表中的数据元素的类型都是相同的，所以每个数据元素所占空间大小一样，假设为L
第一个数据元素位置为a,地址为b
第i个数据元素的地址为b+(i-1)L

顺序表具有按数据元素的位序随机存取的特点
在这里插入图片描述

一维数据来表示顺序表的数据存储区域

数组的空量，需设计的足够大，根据实际问题定义的足够大的MAXSIZE作为上界。
线性表中的数据从数组的零位置，开始依次顺序存放

一般情况下线性表中的实际元素个数少于MAXSIZE个，因此用一个变量Last记录线性表中最后一个元素在线性表中的位置，空表last = -1

# define MAXSIZE 100
typedef struct Linear_List
{
    detatype elem[MAXSIZE];
    int list;

}SeqList

数据的长度，顺序表的存储空间大小，我们用MAXSIZE定义，分配后值不变

顺序表的长度是顺序表中数据元素的个数，也就是last+1
它随着顺序表的插入和删除操作会有变化

任何一个时刻，顺序表的长度应该小于等于数组的长度

SeqList L;
将初始值赋值给L的elem数组，last指针指向最后一个数据元素下标

练习

线性表–按值查找

typedef int datatype; 
int LocatList(SeqList *L,datatype x)
{
    int i = 0;
    #数组中没有元素，直接返回-1
    if(L->last <0 ) return -1; 
    # 如果i 的值小于数组的最后一位，且elem[i] 不等于x,i自增
    while(i< L->last &&  L->elem[i] != x ) i++;
    # 数组中的最后一位都没有找到，返回-1,否则返回i
    if (i > L->Last){
        return -1;
    }else{
        return i;
    }
}

线性表–插入删除
在这里插入图片描述

在顺序表中由于逻辑上的相邻数的数据元素在物理位置上也是相邻的，需要实现在第i个位置插入数据元素X，需要依次将ai-an往后移动,给X空出I位置

int insert(Seqlist *sq, int i , datatype x )
{
    int j;
    if(sq -> last == MAXSIZE -1)
    {
        printf("表满");
        return -1;
    }
    if(i <1 || i > sq->last +2)
    {
        printf("位置不对");
        return -1;
    }
    for(j = sq->last;j>i-1;j--)
        sq->elem[j+1]=sq->elem[j];
        sq->elem[i-1]=x;
        sq->last++;
        return -1
}