考研必备~总结严蔚敏教授《数据结构》课程的重要知识点及考点

作者主页：知孤云出岫

总结严蔚敏教授《数据结构》课程的重要知识点及考点，并罗列重要的实操代码如下：

1. 基本概念

1.1 数据结构的定义

• 数据：数据是信息的符号表示，可以是数值、字符、图像等。
• 数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

1.2 抽象数据类型 (ADT)

• 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

2. 线性表

2.1 顺序表

• 定义：顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。
• 操作：插入、删除、查找等。

关键代码：

typedef struct {ElemType *data;int length;
} SqList;void InitList(SqList *L) {L->data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));L->length = 0;
}

2.2 链表

• 定义：链表是通过链式存储结构存储线性表的数据元素。
• 类型：单链表、双链表、循环链表。

关键代码：

typedef struct Node {ElemType data;struct Node *next;
} Node, *LinkList;void InitList(LinkList *L) {*L = (LinkList)malloc(sizeof(Node));(*L)->next = NULL;
}

3. 栈和队列

3.1 栈

• 定义：栈是一种后进先出（LIFO）的线性表。
• 操作：进栈、出栈、取栈顶元素等。

关键代码：

#define MAXSIZE 100
typedef struct {ElemType data[MAXSIZE];int top;
} SqStack;void InitStack(SqStack *S) {S->top = -1;
}

3.2 队列

• 定义：队列是一种先进先出（FIFO）的线性表。
• 类型：顺序队列、链式队列、循环队列。

关键代码：

#define MAXSIZE 100
typedef struct {ElemType data[MAXSIZE];int front;int rear;
} SqQueue;void InitQueue(SqQueue *Q) {Q->front = 0;Q->rear = 0;
}

4. 树和二叉树

4.1 树的基本概念

• 定义：树是n(n>=0)个结点的有限集。
• 类型：二叉树、平衡二叉树、完全二叉树等。

4.2 二叉树

• 遍历：前序遍历、中序遍历、后序遍历、层序遍历。

关键代码：

typedef struct BiTNode {ElemType data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;void PreOrderTraverse(BiTree T) {if(T != NULL) {printf("%c", T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
}

5. 图

5.1 图的基本概念

• 定义：图是由顶点的有穷非空集合和顶点之间边的集合组成。
• 表示：邻接矩阵、邻接表等。

5.2 图的遍历

• 深度优先搜索 (DFS)
• 广度优先搜索 (BFS)

关键代码：

#define MAXVEX 100
typedef struct {char vexs[MAXVEX];int arc[MAXVEX][MAXVEX];int numVertexes, numEdges;
} MGraph;void DFS(MGraph G, int i) {visited[i] = TRUE;printf("%c ", G.vexs[i]);for(int j = 0; j < G.numVertexes; j++) {if(G.arc[i][j] == 1 && !visited[j])DFS(G, j);}
}

6. 查找和排序

6.1 查找

• 顺序查找：适用于线性表。
• 二分查找：适用于有序数组。

关键代码：

int BinarySearch(int *a, int n, int key) {int low = 0, high = n - 1;while(low <= high) {int mid = (low + high) / 2;if(a[mid] == key) return mid;else if(a[mid] > key) high = mid - 1;else low = mid + 1;}return -1;
}

6.2 排序

• 交换排序：冒泡排序、快速排序。
• 选择排序：简单选择排序、堆排序。
• 插入排序：直接插入排序、希尔排序。
• 归并排序：两路归并排序。

关键代码：

void QuickSort(int *a, int low, int high) {if(low < high) {int pivot = Partition(a, low, high);QuickSort(a, low, pivot-1);QuickSort(a, pivot+1, high);}
}int Partition(int *a, int low, int high) {int pivot = a[low];while(low < high) {while(low < high && a[high] >= pivot) high--;a[low] = a[high];while(low < high && a[low] <= pivot) low++;a[high] = a[low];}a[low] = pivot;return low;
}

7. 重点考点

• 各种数据结构的定义和特点。
• 各种数据结构的基本操作及其实现。
• 树和图的遍历算法。
• 常见的排序和查找算法及其时间复杂度分析。
• 通过实际代码理解和掌握数据结构的实现和应用。

这些内容涵盖了《数据结构》课程的重要知识点及其考点，并通过关键代码片段帮助理解和实操。