线性表

线性表总结整理，囊括线性表分类。线性表是最基本、最简单、最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的，但这只适用大部分线性表，而不是全部哦。

线性表

• 线性表
  • 顺序表（顺序存储）
    • 定义
      • 内容
        • 数组存储数据元素，有最大值MAXSIZE
        • 线性表当前长度length
      • 注意
        • 在任意时刻，线性表的长度应该小于数组的长度
        • 数组相当于一个存储器，数据元素在上面顺序存储
      • 例
    • 操作
      • 顺序存储的插入（在线性表L中的第i个位置插入新元素e）
        • 思想
          • 1、如果插入位置不合理，抛出异常
          • 2、如果线性表长度大于等于数组长度，即线性表已达最大容量，抛出异常或者动态增加容量，一般情况抛出异常
          • 3、从最后一个元素开始向前遍历到第i个位置，分部将它们向后移动一个位置
          • 4、将要插入的元素填入第i个位置
          • 5、表长加一
        • 例
      • 顺序存储的删除（删除L的第i个数据元素，并用e返回其值，L的长度减一）
        • 思想
          • 1、如果删除位置不合理，抛出异常
          • 2、取出删除元素
          • 3、从删除元素位置开始遍历到最后一个元素位置，分别将他们都向前移动一个位置
          • 4、表长减一
        • 例
  • 链表（链式存储）
    • 定义
      • 内容
        • 数据域
        • 指针域
      • 例
    • 头指针和头结点
      • 头指针
        • 头指针是链表指向第一个结点的指针，若链表有头结点，则指向头结点
        • 头指针具有标识作用，所以常用头指针冠以链表的名字
        • 无论链表是否为空，头指针均不为空。头指针是链表的必要元素
      • 头结点
        • 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表长度）
        • 有了头结点，对于第一元素 结点前插入结点 和 删除第一结点，和操作与其他结点的操作就统一了
        • 头结点不一定是链表必须要素
    • 单链表
      • 操作
        • 头插法建立单链表
          • 思想
            • 1、创建一个新的结点s
            • 2、将读取到的数据x放入新结点的数据域中s—>data=x
            • 3、将新结点的指针域指向头结点的下一个结点，即新结点的指针域=头结点的指针域， s—>next=L—>next
            • 4、头结点的指针域指向新建的结点s L—>next=s
          • 注意
            • 采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的
            • 每个结点插入的时间为O（1），设单链表长n，则总时间复杂度为O（n）
          • 例
        • 尾插法建立单链表
          • 思想
            • 1、定义两个结点，一个用来标识链表最后一个结点r，一个是新结点s
            • 2、将读取到的数据x放入新结点的数据域中s—>data=x
            • 3、将最后一个结点指向新节点（r—>next=s）
            • 4、将新结点设为尾结点（r=s）
          • 注意
            • 时间复杂度同头插法建立单链表相同
          • 例
        • 单链表的读取（用e返回L中第i个数据元素的值）
          • 思想
            • 1、声明一个结点p指向链表的第一个结点，初始化j从1开始
            • 2、当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
            • 3、若到链表末尾p为空，则说明第i个元素不存在
            • 4、否则查找成功，返回结点p的数据
          • 例
        • 单链表的插入（在L中第i个位置之前插入新的数据元素e，L的长度加一）
          • 思想
            • 1、声明一结点p指向链表头结点，初始化j从1开始
            • 2、当j<i时，遍历链表，让p的指针往后移动，不断指向下一个结点，j累加1
            • 3、若到链表末尾p为空，则说明第i个元素不存在
            • 4、否则查找成功，在系统中生成一个空节点s
            • 5、将数据元素e赋值给s—>data
            • 6、单链表的插入标准语句s—>next=p—>next, p—>next=s
            • 7、返回成功
          • 例
        • 单链表的删除（在L中第i个位置之前删除数据元素，并输出其值e）
          • 思想
            • 1、如果删除位置不合理抛出异常（i<1)
            • 2、声明两个结点，一个标识删除结点的前驱结点prep
            • 3、初始化j从0开始，当（j<i-1并且prep存在）时遍历链表，让prep的指针往后移动，j累加1
            • 4、删除结点p等于prep的下一个结点（p=pre—>next)即确定下p
            • 5、prep的指针域指向p的下一个结点（pre—>next=p—>next）
            • 6、释放p
          • 例
        • 两个有序单链表的合并
          • 思想
            • 已知A、B中元素递增有序，那么只需要从A、B调出最小的元素放到C中，直到其中一个表为空时，再把剩余的元素插入到C即可
          • 例
    • 双链表
    • 循环链表
      • 内容
        • 循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环，从任何一个结点出发都能访问到链表的每一个元素
      • 注意
        • 1、判空条件不是头结点的后继指针是否为空，而是是否等于头指针
        • 2、有时对单链表常做的操作是在表头和表位进行的，此时可对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高
    • 静态链表
      • 定义
        • 静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址（数组下标），又称作游标
        • 例
      • 注意
        • 静态链表以next==-1作为其结束的标志
• 栈
  • 顺序栈（顺序存储）
    • 定义
      • 内容
        • 栈：只允许一段进行插入或者删除操作的线性表
        • 栈顶：栈中允许进行插入和删除的那一端
        • 栈底：固定的，不允许进行插入和删除的另一端
      • 例
      • 分类
        • 根据数组是否可以根据需要增大
          • 静态顺序栈（存储元素的数组+栈顶指针）
            • 采用静态一维数组来存储栈。
            • 注意
              • 栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。 用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。 结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。 当栈满时做进栈运算必定产生空间溢出，简称“上溢”。上溢是一种出错状态，应设法避免。 当栈空时做退栈运算也将产生溢出，简称“下溢”。下溢则可能是正常现象，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件。
            • 图片示例
          • 动态顺序栈（栈顶指针+栈底指针+已分配的空间）
            • 采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。
            • 注意
              • 用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。 用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。 结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;
            • 图片示例
      • 注：
        • 由于栈是受限的线性表，所以顺序栈需要在顺序表的基础上做点修改
        • 栈空条件：top=-1
        • 栈长（栈中数据个数）：top+1
        • 栈满：top=Maxsize-1
        • 数组的0端作为栈底
    • 静态顺序栈操作
      • 判空
      • 进栈
        • 思想
          • 1、判断是否栈满
          • 2、指针加一再入栈
        • 例
      • 出栈
        • 思想
          • 1、判断是否栈空
          • 2、先出栈，指针再减一
        • 例
  • 链式栈（链式存储）
    • 定义
      • 内容（栈中元素data+栈顶指针）
        • 栈是线性表的特例，线性表的存储结构还有链式存储，所以也可以用链表的方式实现栈。栈的链式存储叫做链栈。
        • 每个单链表都有头指针，对于链栈也是必须的，将头指针作为栈顶指针
      • 注意
        • 链栈一般不存在栈满的情况
        • 空栈的判定条件通常定位top==NULL
      • 例
    • 操作
      • 链栈压栈（元素进栈）
        • 思想
          • 1、申请新的栈结点（Stack_Node）p，若申请失败，返回false
          • 2、将值赋给p
          • 3、p—>next=top—>next
          • 4、top—>next=p
        • 例
      • 链栈弹栈（元素出栈）
        • 思想
          • 1、新声明一个栈结点用来记录删除的结点
          • 2、判断是否栈空top—>next=NULL
          • 3、取出栈顶元素赋给p，p=top—>next，e=p—>data
          • 4、修改栈顶指针，top—>next=p—>next，释放p结点
        • 例
  • 栈的应用
    • 进制转换
      • 进制转换数学思想
        • 图片
        • 思想
          • 假设将十进制V转化为二进制，将V除2得余数，再商除2得余数最后一直除到0然后余数倒序输出即是转化的数
      • 算法实现
      • 算法思想
        • 1、分析循环条件：商>0
        • 2、循环体要实现的东西：每次取余，作商
        • 3、循环弹栈
    • 括号匹配问题
      • 算法实现
      • 算法思想
        • 设置一个栈，读到左括号时进栈，读到右括号时弹出元素与读到的右括号配对，若匹配成功，继续读入，否则返回FALSE，最后判断栈是否为空，不为空则返回False，为空返回true
• 队列
  • 特点
    • 先进先出
    • 一端插入一端删除
  • 顺序存储（对头指针+队尾指针+存放队列元素）
    • 定义
      • 设置一个队首指针front，一个对位指针rear，分别指向对首和队尾元素
      • 示意图
    • 操作
      • 初始化：front=rear=0
      • 判断空：front=rear
      • 判断满：rear=MAX_QUEUE_SIZE-1或者front=rear
      • 入队：新元素插入到rear所指的位置，然后rear+1
      • 出队：删去front所指的元素，然后加1并返回删除元素
    • 假溢出：数组中含有可用的存储空间却无法入队
      • 含义
        • 尽管队列中实际元素个数可能远远小于数组大小，但可能由于为指针已超出向量空间的上界而不能做入队操作
      • 原因
        • 因为在入队和出队操作中，头尾指针只增加不减小，致使被删除的元素的空间永远无法重新利用
  • 循环队列（克服“假溢出“）
    • 定义
      • 将队列分配的向量空间看做一个首尾相接的圆环，并将这种队列称为循环队列
    • 操作
      • 初始化：front=rear=0
      • 判断空：front=real
      • 判断满：外层注
  • 链式存储
• 时间复杂度和空间复杂度
  • 空间复杂度
    • int i = 1; int j = 2; ++i; j++; int m = i + j;
    • 如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
    • int[] m = new int[n] for(i=1; i<=n; ++i) { j = i; j++; }
    • 这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)
  • 时间复杂度
• 注：因为入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时都有front=real。所以无法用front=real来判断循环队列队空或队满
  • 解决方法1（了解一下）
    • 设置标志位flag，当flag=0且real=front时为空，flag=1且real=front时为满 当入队是令flag=1，出队时flag=0
  • 解决方法2（关注这种）
    • 我们吧front=real仅作为队空的判定条件。当队满时，令数组中仍保留一个空单元，real指向这个空单元
    • 图例
    • 图例笔记
      • 其中的MaxSize=5