线性表(List):零个或多个数据元素的有限序列

• 序列: 元素之间是有顺序的,第一个元素无前驱最后一个元素无后继，其他元素都有一个前驱和一个后继

• 有限: 元素个数是有限的
  在较复杂的线性表中，一个数据元素可以由若干个数据项组成，每个数据元素具有相同类型的数据项。

线性表的基本操作

• 线性表的创建和初始化
• 线性表重为空表
• 根据位序得到数据元素
• 查找某个元素是否存在
• 获取线性表长度
• 插入和删除数据

ADT 线性表(List)
Data
      线性表的数据对象集合为{a1,a2,..........an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每个元素有且只有一个直接前驱元素，除最后一个元素an外，每个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
       InitList(*L):   初始化操作，建立一个空的线性表L。
       ListEmpty(L): 若线性表为空，返回true，否则返回false。
       ClearList(*L): 将线性表清空
       GetElem(L,i,*e): 将线性表L中的第i个位置元素返回给e
       LocateElem(L,e):在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败
       ListInsert(*L,i,e): 在线性表L中的第i个位置插入新元素e
       ListDelete(*L,i,*e): 删除线性表L中第i个位置元素，并用e返回其值
       ListLength(L):   返回线性表L的元素个数

endADT

• 线性表预定义常量和类型

数据结构的表示(存储结构)用类型定义(typedef)描述。数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。

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

#define MAXSIZE 20 /* 存储空间初始化分配量 */

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

• 线性表数据结构类型定义

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

• 顺序线性表初始化

Status InitList(SqList *L) 
{ 
    L->length=0;
    return OK;
}
i=InitList(&L);
printf("初始化L后: L.length=%d\n",L.length);

初始化L的长度为0，接下来在表头插入五个元素

• 插入元素到顺序线性表中

Status ListInsert(SqList *L, int i, ElemType e)
{ 
    int k;
    if (L->length==MAXSIZE)  /* 顺序线性表已经满 */
        return ERROR;
    if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置还要大时 */
        return ERROR;

    if (i<=L->length)        /*  若插入数据位置不在表尾 */
    {
        for(k=L->length;k>=i;k--)  /* 将要插入位置之后的数据元素向后移动一位，给欲插入元素腾出位置 */
            L->data[k]=L->data[k-1];
    }
    L->data[i-1]=e;          /* 将新元素插入 */
    L->length++;

    return OK;
}
//测试数据
for(j=1;j<=5;j++)
        i=ListInsert(&L,1,j);
printf("在L的表头依次插入1~5后:L.data=");
ListTraverse(L); //输出元素 

插入元素后输出

for(j=1;j<=10;j++)
        ListInsert(&L,j,j);
printf("在L的表尾依次插入1~10后: L.data=");
ListTraverse(L); 

在表尾插入数据

这样每次插入的数据就是data[j-1], 就是在尾部插入。

• 判断顺序线性表是否为空

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

• 将顺序线性表清空

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

• 查找顺序线性表中元素

Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length==0 || i<1 || i>L.length)
        return ERROR;
    *e=L.data[i-1];//第i个位置的元素在数组的i-1位置 

    return OK;
}

• 查找某个元素是否存在顺序线性表中

int LocateElem(SqList L,ElemType e)
{
    int i;
    if (L.length==0)
        return 0;
    for(i=0;i<L.length;i++)
    {
        if (L.data[i]==e)
            break;        // 跳出for
    }

    if(i>=L.length)
        return 0;

    return i+1;//元素的位序要加一 
}

• 从顺序线性表中删除元素

/* 初始条件:顺序线性表L已存在 1<=i<=ListLength(L) */
/* 操作结果: 删除L的第i个数据元素，并用e返回其值，L的长度减一 */
Status ListDelete(SqList *L, int i, ElemType *e) 
{ 
    int k;
    if (L->length==0)               /* 线性表为空  */
        return ERROR;
    if (i<1 || i>L->length)         /* 删除位置不正确 */
        return ERROR;
    *e=L->data[i-1];
    if (i<L->length)                /* 如果删除不是最后位置 */
    {
        for(k=i-1;k<L->length-1;k++)/* 将删除位置后继元素前移*/
            L->data[k]=L->data[k+1];
    }
    L->length--;
    return OK;
}

• 顺序输出元素

Status ListTraverse(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        visit(L.data[i]);//输出函数 
    printf("\n");
    return OK;
}

• 在La中合并Lb中的元素

现实生活中涉及关于线性表更复杂操作，可以用基本操作的组合来实现。比如:实现两个线性表集合A和B的并集操作，就是把存在集合B中但并不存在A中的数据元素插入到A中
仔细分析这个操作会发现只要循环集合B中的每个元素，判断当前元素是否存在A中，若不存在，则插入到A中即可。即从线性表Lb中依次取得每个数据元素，并依值在线性表La中进行查访，若不存在，则插入之。
实现代码如下:

// 在La中合并Lb中的元素  
void unionL(SqList *La,SqList Lb)
{
    int La_len,Lb_len,i;
    ElemType e;
    La_len=ListLength(*La);
    Lb_len=ListLength(Lb);
    for (i=1;i<=Lb_len;i++)
    {
        GetElem(Lb,i,&e);      // 依次返回Lb线性表中的值 依次取出Lb中的元素 
        if (!LocateElem(*La,e))  //与La中的对所有元素做对比 
            ListInsert(La,++La_len,e); //若不存在La中，则插入La中 
    }
}

• 把La和Lb线性表中的元素归并为一个新的线性表Lc

因为Lc中的值需要改变，所以只能传地址进来。在此函数中Lc是指针变量，所以进入ListInsert()时直接是ListInsert(Lc,++k,ai)。在调用GetElem()时变量e是指针类型，是因为变量e在子函数中做出的改变是永久的，并不会随着子函数运行完毕改变就会消失。因为子函数中的变量都是临时变量随着子函数的结束而结束，所以出现指针变量可以在子函数中做出改变使其不随子函数的结束而结束。

// 将两个非递减有序线性表La和Lb归并为一个新的线性表Lc 
void MergeList(SqList La,SqList Lb,SqList *Lc)
{
    //InitList(Lc);
    int i,j,La_len,Lb_len,ai,bj;
    int k = 0;
    i = j = 1;
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    while((i<=La_len) && (j<= Lb_len))
    { //
        GetElem(La,i,&ai);
        GetElem(Lb,j,&bj);
        if(ai<=bj)
        {
            ListInsert(Lc,++k,ai);
            ++i;
        }else{
            ListInsert(Lc,++k,bj);
            ++j;
        }   
    }
    
    while(i<=La_len)
    {
        GetElem(La,i++,&ai);
        ListInsert(Lc,++k,ai);
    }
    while(j<=Lb_len)
    {
        GetElem(Lb,j++,&bj);
        ListInsert(Lc,++k,bj);
    }
}

线性表的顺序存储结构

线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素
数组长度和线性表长度的区别
数组长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。
线性表长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。
地址计算方法

存储位置的地址

线性表顺序存储结构的优缺点

优点

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素
  缺点
• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的“碎片”

题外话

最近看链表遇到了指针，这可是我一直的痛点。又翻出来看了看，发现自己的问题确实还挺严重。

int *b = &a;

在上面这行代码上纠结了很久，最后发现其实应该这么理解。

int* b; 
b = &a;

也就是说b是一个指针变量，b指向a变量对应的地址，*b指向a变量对应的值
&: 取地址符， * : 取值符，二者互为逆运算。

#include <stdio.h>

int main()
{
   int a = 1;
   int* b; 
   b = &a; //b指针所指向的数据等于a的地址 
   //int *b = &a;
   printf("a = %d, b = %d\n", a, *b);
   //a = 1, b = 1
   a = 6;
   printf("a = %d, b = %d\n", a, *b);
   // a = 6, b = 6
   *b = 9;
   printf("a = %d, b = %d\n", a, *b);
   // a = 9, b = 9
   return 0;
}

经典的swap()

void swap(int *p1, int *p2)
{
    int temp;
    temp = *p1;
    *p1 = *p2;
    *p2 = temp;
}

int main()
{
   int a = 1;
   int b = 2;
   
   // 指针传参数会在子函数改变 a, b 数值
   swap(&a, &b);
   printf("a= %d, b = %d\n", a, b);
   
   return 0;
}

swap传入的是a和b的地址，p1=&a，p2=&b，temp =* p1= * (&a) = a。即交换的是地址中的值，地址不变。

截图以证清白