2. 线性表

2.1 线性表的定义&基本操作

• 线性表：是具有相同数据类型的n（n≥0）个数据元素的有限 序列，其中n为表长，当n = 0时线性表是一个空表。若用L命名线性表，则其一般表示为 L = (a1, a2, … , ai, ai+1, … , an)
• 线性表的特点：
  • 表中元素个数有限
  • 表中元素具有逻辑上的顺序性，在序列中哥哥元素排序有其先后次序
  • 表中元素都是数据元素，每个元素都是单个元素
  • 表中元素的数据类型都相同，这意味着每隔元素占有相同大小的存储空间
  • 表中元素具有抽象性，即讨论元素间一对一的逻辑关系，而不考虑元素究竟表示的内容
  • 线性表是一种逻辑结构，表示元素之间一对一相邻的关系
• 线性表的九种基本操作：
  • InitList(&L)：初始化表。构造一个空的线性表。
  • DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占的内存空间。
  • LocateElem(L, e)：按值查找操作。在表L中查找具有给定关键字值的元素。
  • GetElem(L, i)：按位查找操作。获取表L中第i个位置上的元素的值。
  • ListInsert(&L, i, e)：插入操作。在表L中的第i个位置上插入指定元素e。
  • ListDelete(&L, i, &e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
  • PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
  • Empty(L)：判空操作。若L为空表，则返回True，否则返回False。
  • Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。

    Tips：
    ①对数据的操作（分析思路） —— 创销、增删改查
    ②C语言函数的定义 —— <返回值类型> 函数名 (<参数1类型> 参数1，<参数2类型> 参数2，……)
    ③实际开发中，可根据实际需求定义其他的基本操作
    ④函数名和参数的形式、命名都可改变（Reference：严蔚敏版《数据结构》）
    ⑤什么时候要传入参数的引用“&” —— 对参数的修改结果需要“带回来”——C++

2.2 顺序表

• 顺序表的定义：
  • 线性表的顺序存储又称为顺序表，顺序表是指一组地址连续存储的存储单元依次存放线性表的元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

顺序表	内存地址
a1	LOC(A)
a2	LOC(A)+sizeof(ElemType)
a3	LOC(A)+2*sizeof(ElemType)
...	...
an	LOC(A)+(n-1)*sizeof(ElemType)

• 数组静态分配：

  #define MaxSize 10 //定义最大长度
  typedef struct
  {
     ElemType data[MaxSize]; //
     int length;     //顺序表当前长度
  }SqList;    //顺序表的类型定义（静态分配方式）
  

• 数组动态分配：

  #define MaxSize 50
  typedef struct
  {
     ElemType * data;
     int length;
  }SqList;
  

• 顺序表基本操作：

  • 插入操作：

    bool ListInsert(SqList &L, int i, ElemType e)
    {
        if (i<1 || i>L.length+1)  //判断插入数据位置是否合法
            return false;
        if (L.length >= MaxSize)
            return false;
        for (int j=L.length; j>=i; j--)  
        {
            L.data[j] = L.data[j-1];   //把每一个数据元素往后移一位
        }
        L.data[i-1] = e;    //赋值
        L.length++; //顺序表长度增加
    
        return true;
    }
    //最好时间复杂度O(1)
    //平均时间复杂度O(n)
    //最坏时间复杂度O(n)
    

  • 删除操作：

    bool ListDelete(SqList &L, int i, ElemType &e)
    {
        if (i<1 || i>L.length+1)  //判断删除数据位置是否合法
            return false;
        e = L.data[i-1];    //保存删除的数据
        for (int j=i; j<L.length; j++)  
        {
            L.data[j-1] = L.data[j];   //把每一个数据元素往前移一位
        }
        L.length--; //顺序表长度减1
    
        return true;
    }
    //最好时间复杂度O(1)
    //平均时间复杂度O(n)
    //最坏时间复杂度O(n)
    

  • 按值查找操作：

    int LocateElem(SqList L, ElemType e)    //参数：查找的表，查找的参数
    {
        int i;
        for (i=0; i<L.length; i++)
        {
            if(L.data[i] == e)  //判断此时位置元素的值是否与需要查询的值相等
                return i+1; //返回物理地址
        }
    
        return 0;   //表示没有查找到
        }
    //最好时间复杂度O(1)
    //平均时间复杂度O(n)
    //最坏时间复杂度O(n)
    

2.3 单链表：

地址	单链表	指针域
addr0	a1	addr4
addr4	a2	addr6
addr6	a3	addr9
...	...	...
addr	an	null

• 单链表的定义：

  • 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。
  • 优点：链表的第一个位置和其它位置的操作统一，空表和非空表的操作统一。

    typedef struct LNode
    {
    ElemType data;
    struct LNode *next;
    }LNode, *LinkList;
    

• 单链表的基本操作：

  • 头插法建立单链表：

    LinkList List_HeadInsert(LinkList &L)   //当我们对传入的参数修改时,往往需要传入一个引用类型的变量
    {
        LNode *s;   //插入的节点
        int x;  //插入的数据,数据可以任意类型
    
        L = (LinkList)malloc(sizeof(LNode));    //初始化头结点，用malloc函数分配节点大小的空间
        L->next = NULL;
        scanf("%d", &x);
        while(x != 9999)
        {
            s = (LNode*)malloc(sizeof(LNode));  //初始化新节点
            s->data = x;    //赋值
            s->next = L->next;  //将新节点的next指针指向头结点
            L->nest = s;    
            scanf("%d", &x);
        }
        return L;
    }
    //最坏时间复杂度O(n)
    

  • 尾插法建立单链表：

    LinkList List_TailInsert(LinkList &L)
    {
        int x;  //所插入的数据
        L = （LinkList）malloc(sizeof(LNode));    //初始化头结点
        LNode *s, *r = L;   //s：插入节点指针，r：尾结点指针，初始化为头结点
        scanf("%d", &x);
        while(x != '\n')
        {
            s = (LNode*)malloc(sizeof(LNode));  //初始化插入节点
            s->data = x;    
            r->next = s;    //将原先最后一个节点指针指向新节点
            r = s;  //将尾指针指向插入节点
            scanf("%d", &x);
        }
        r->next = NULL; //最后一个节点指向为空
        return L;   //返回单链表
    }
    //最坏时间复杂度：O(n)
    

  • 按序号查找操作：

    LNode *GetElem(LinkList L, int i)   //查找的表以及查找的序号
    {
        int j = 1;
        LNode *p = L->next;
        if (i == 0) //表示头结点，直接返回L
        {
            return L;
        }
        if (i < 1)  //不合法，返回空
        {
            return NULL;
        }
        while(p && j<i) //遍历链表当前节点不能为空，当前遍历是否到了寻找的位置        
        {
            p = p->next;
            j++;
        }
        return p;
    }
    //最坏时间复杂度：O(n)
    

  • 按值查找操作：

    LNode *LicateElem(LinkList L, ElemType e)
    {
        LNode *p = L->next;
        while(p!=NULL && p->data!=e)    //当前节点是否为空且当前节点的值不为查找的值
        {
            p = p->next;
        }
        return p;
    }
    //最坏时间复杂度O(n)
    

  • 插入节点：