考研笔记

板子：五种存储结构的定义

算法题代码的第一部分。真题给了定义就照抄题目的字段名，没给就先写定义再写函数。

代码

#define MaxSize 100
#define MAXV 100                                // 图的最大顶点数（真题写法：「MAXV 为已定义常量」）
typedef int ElemType;
 
// 顺序表
typedef struct {
    ElemType data[MaxSize];
    int length;
} SqList;
 
// 单链表（默认带头结点）
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;
 
// 二叉链表
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
 
// 图：邻接矩阵（字段名和 2021、2023 真题给的一样）
typedef struct {
    int numVertices, numEdges;                  // 顶点数、边数
    char VerticesList[MAXV];                    // 顶点表
    int Edge[MAXV][MAXV];                       // 邻接矩阵：无权图存 0/1，带权图存权值
} MGraph;
 
// 图：邻接表（字段名和教材一样）
typedef struct ArcNode {                        // 边结点
    int adjvex;                                 // 这条边指向的顶点下标
    struct ArcNode *nextarc;                    // 同一个顶点的下一条边
} ArcNode;
typedef struct VNode {                          // 顶点结点
    char data;
    ArcNode *firstarc;                          // 这个顶点的第一条边
} VNode;
typedef struct {
    VNode vertices[MAXV];
    int vexnum, arcnum;                         // 顶点数、边数
} ALGraph;

写法约定（后面所有板子都按这个来）

项约定
语言C 风格，可以用 C++ 的 & 引用和 bool；不用 STL
头文件 / main不写，考场也不要求
数组下标从 0 开始（堆、KMP 这类教材从 1 开始的另外注明）
申请内存(T *)malloc(sizeof(T))，用完 free；要清零用 calloc
顺序表函数写成 int A[], int n；要改长度就写 int &n
链表默认带头结点，L->next 才是第一个数据结点
图邻接矩阵按真题字段名，邻接表按教材字段名；无权图 Edge 存 0/1，带权图没有边存 INF

int A[], int n 和 SqList &L 可以直接互换：A[i] ↔ L.data[i]，n ↔ L.length，只是改名字。

易错点

  • LNode * 和 LinkList 是同一个类型。习惯上用 LinkList 表示「一条链表」（头指针），用 LNode * 表示「一个结点」（工作指针）。
  • 结构体内部的指针在 C 里必须写 struct LNode *next（C++ 可以省掉 struct）。按 C 写，两边都不会错。
  • 无向图的邻接矩阵是对称的，加一条边要同时写 Edge[i][j] 和 Edge[j][i]。
  • 真题的字段名并不统一，比如 2014 年 WPL 题用 left / weight / right，2017 年表达式树用 char data[10]。一律以题目给的为准。

链接

反向链接