列表

ADT：

• 对象：\((item_0,\cdots,item_{N-1})\)
• 操作：
  1. Find length
  2. Print
  3. Make empty
  4. Find k-th
  5. Insert
  6. Delete
  7. Find next
  8. Find previous

实现：

1. 数组：array[i] = item_i 顺序映射

   问题：1. 需估计MaxSize 2. 插入删除\(O(N)\)

   优势：找k-th为\(O(1)\)

2. 链表

链表

初始化：

typedef struct list_node *list_ptr;
typedef struct list_node {
    element data;
    list_ptr next;
};
list_ptr ptr;

插入 \(O(1)\)

 temp->next = node->next
 node->next = temp

删除：

 pre->next = node->next
 free(node)

遍历：

 p = h;
 while (p != NULL) {
     printf("%d", p->data);
     p = p->next;
 }

例 链表反转

思路：寻找状态之间的转移

边界：q = h, p = NULL;

转移：t = q->next, q->next = p, p = q, q = t;

双向链表

定义：

typedef struct node *node_ptr;
typedef struct node {
    node_ptr llink;
    element item;
    node_ptr rlink;
}

应用：多项式

• ADT：
  • 对象：\(P(x)=a_1x^{e_1}+\cdots+a_nx^{e_n}\)
  • 操作：
    1. Find degree
    2. Addition
    3. Subtraction
    4. Multiplication
    5. Differentiation
• 表示：
  • 数组：

    typedef struct {
        int CoeffArray[MaxDegree + 1];
        int HighPower;
    } *Polynomial;
    

  • 链表：

    typedef struct poly_node *poly_ptr;
    struct poly_node {
        int Coefficient;
        int Exponent;
        poly_ptr Next;
    };
    typedef poly_ptr a;
    

多重链表

处理稀疏数据

静态链表

定义：data CursorSpace[] struct data {ElementType Element, int Next}

应用：内存管理

思路：将空闲区域串在静态链表上

malloc：

p = CursorSpace[0].Next;  // 获取头节点后的第一块可用区间
CursorSpace[0].Next = CursorSpace[p].Next  // 更新第一块可用区间

free(p)：

CursorSpace[p].Next = CursorSpace[0].Next;  // 将待free空间插在头节点后
CursorSpace[0].Next = p;