抽象数据类型 | ADT

Objects

item0 , item1 , … , itemN-1

Operations

  1. Finding the length, N, of a list.
  2. Printing all the items in a list.
  3. Making an empty list.
  4. Finding the k-th item from a list, 0 <= k < N.
  5. Inserting a new item after the k-th item of a list, 0 <= k < N.
  6. Deleting an item from a list.
  7. Finding next of the current item from a list.
  8. Finding previous of the current item from a list.


List

数组 | Array

链表 | LinkedList

单向链表

双向环形链表 | Doubly Linked Circular List

image.png
image.png
/应用/
多项式加减乘除法

  1. typedef  struct  poly_node   *poly_ptr;
  2. struct  poly_node  {
  3.       int       Coefficient ;  /* assume coefficients are integers */
  4.       int       Exponent;
  5.       poly_ptr    Next ;
  6. } ;
  7. typedef  poly_ptr   a ;    /* nodes sorted by exponent */

多链表 | Multilists

image.png

链表的游标实现 | Cursor Implementation

实现要点在于用结构体数组模拟链表，同时用一个freelist(freelist总以CursorSpace[0]为头)来记录还没使用的空间。
image.png
两个重要的操作——分配内存和释放内存
malloc
image.png
p = CursorSpace[0].Next;
CursorSpace[0].Next = CursorSpace[p].Next;
free(p)
image.png
CursorSpace[p].Next = CursorSpace[0].Next;
CursorSpace[0].Next = p;
/释放的空间总插入到freelist头结点后也即CursorSpace[0]后/

此外注意游标实现下的链表均为带虚拟头结点的链表
image.png

Stack

FILO(First In Last Out)
image.png
这里的指针实际上是pre指针，从尾部开始建立链表。
Push为插入结点，Pop为删除结点。

Queue

FIFO(FIrst In First Out)

循环队列 | Circular Queue

image.png
队列已满，此时实际上还有一个空间。
image.png
队列为空，Front指针指向[1]。