【软考】9.1 顺序表/链表/栈和队列

《线性结构》

• 顺序存储和链表存储

• 每个元素最多只有一个出度和一个入度表现为一条线状
• 链表存储结构每个节点有两个域即数据指针域指向下一个逻辑上相邻的节点
  

• 时间复杂度与其数量级成正比
• 空间链表浪费空间
• 时间增删改查链表效率更高
• 不改变结构操作时即读取查找顺序表效率更高
  

• 栈和队列

• 栈先进后出分队头和队尾
• 队列先进先出只有栈顶能进出
  

• 循环队列

• 入队时修改队尾
  Q.rear = Q.rear +1% MAXSIZE
• 出队时修改队头
  Q.front= Q.front +1% MAXSIZE
• 队列为空时则Q.rear == Q.front
• 队列为满时则Q.rear == Q.front
  

• 区别队列空和队列满的情况

• 队列满队列的尾指针所指位置的下一个位置是队头指针即
  Q.rear +1% MAXSIZE = Q.front
• 队列空头、尾指针的值相同即
  Q.rear = Q.front
  

• 出栈时没有声明是否有入栈则输出元素序列不确定
  
• 全部所有元素一次性进入队列
• A中入栈顺序必须是e1e2B中必须是e3e4由于A和B是相互独立的则出栈顺序可自由组合
  

• 队尾的指针Z所在的指针
• 队尾元素的指针Z指向的下一个元素所在的指针