线性表和定义特点

• 线性表是具有相同特性的数据元素的有限序列
• 最多只有一个直接前趋，和直接后继
• 元素关系为线性的

案例引入

1. 一元多项式的运算

可以使用数组来实现

• 存储空间分配不灵活z
• 运算空间复杂度高。

  2. 链式存储

  

线性表的类型定义

抽象数据类型

ADT list{
    数据对象: D
  数据关系: R
  基本操作
}ADT List

一、顺序表与链表

二、队列

只能在表尾插入，表头删除的线性表

2.1概述

1. 定义

只能在表的一端进行插入，另一端进行删除

2. 逻辑结构

一对一的关系，和线性表相同

3. 存储结构

顺序对或者链式队列，循环队列更为常见

4. 运算规则

只能在队首和队尾运算，访问依照先进先出原则

5. 实现方式

关键掌握入队出队操作。

3. 队列的存储实现

3.1 队列顺序存储实现

#define MAXQSIZE 100
typedef struct{
     QElemType *base;//初始化动态分配存储空间
    int front;//首节点
    int rear; //尾节点
}SqQueue;

普通实现

• 初始化: front=rear=0;
• 入队: base[rear]=x ;rear++;
• 出队: x=base[front];front++;
• 空判断: front==rear;
• 溢出判断
  • 真溢出
    • 若front==0,rear==MAXQSIZE
  • 假溢出
    • 若front!=0,rear=MAXQSIZE

循环队列

循环队列可以解决队列假溢出的问题

• base[0]接在[MAXQSIZE-1]之后，若rear+1=M,则让rear=0
• 入队: base[rear] = x; rear=(rear+1)%MAXQSIZE
• 出队: x=base[front] ;front = (front+1)%MAXQSIZE

• ?如何判断队空队列满
  1. 另外设置标志，却别队空对满
  2. 另外设置变量记录元素个数
  3. 少用一个空间元素
     1. (rear+1)%MAXQSIZE==front为满!

        *代码实现

        ```c //初始化分配空间 Status InitQueue( ){ //分配内存 //头尾指针置0 }

//求队列的长度 int getLength(){ //(rear-front+MAXQSIZE)%MAXSIZE }

//入队 int EnQueue(){ } //出队 int DeQueue(){

} //取出队头元素 int getHead(){

}

<a name="td4eA"></a>
### 3.2 队列的链式存储
```c
#define MAXQSIZE 100
typedef struct{
     QElemType data;
    struct Qnode *next;
}QNode,*QuenePtr;

如果用户无法预估队列的长度，则适合采用链式队列

• 链队列的类型定义