数据结构（C语言版）课后习题解析与实战演练

1. 数据结构基础概念精讲1.1 数据结构核心术语解析数据是计算机程序处理的符号集合比如学生管理系统中的学号、姓名、成绩等。数据元素是数据的基本单位在C语言中通常用结构体表示。例如一个学生记录可以定义为struct Student { int id; // 数据项学号 char name[20];// 数据项姓名 float score; // 数据项成绩 };逻辑结构分为四种基本类型集合结构元素间没有明确关系比如班级花名册线性结构元素一对一关系如数组、链表树形结构元素一对多关系如文件目录图状结构元素多对多关系如城市交通网存储结构物理结构的两种主要实现方式顺序存储用连续的存储单元存放数据元素比如用数组实现线性表链式存储通过指针链接非连续的存储单元如单链表1.2 抽象数据类型(ADT)实战抽象数据类型由数据对象、数据关系和基本操作三部分组成。以栈为例其ADT描述如下// 栈的抽象数据类型定义 typedef struct { int *base; // 栈底指针 int *top; // 栈顶指针 int stacksize; // 栈容量 } SqStack; // 基本操作 void InitStack(SqStack S); // 初始化栈 void Push(SqStack S, int e); // 入栈 void Pop(SqStack S, int e); // 出栈2. 线性表算法实现2.1 顺序表操作详解顺序表插入操作需要考虑元素移动。在第i个位置插入元素e的算法#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SqList; Status ListInsert(SqList L, int i, int e) { if (i 1 || i L.length1) return ERROR; // 位置不合法 if (L.length MAXSIZE) return ERROR; // 存储空间已满 for (int j L.length; j i; j--) L.data[j] L.data[j-1]; // 元素后移 L.data[i-1] e; // 插入新元素 L.length; // 表长增1 return OK; }顺序表查找有按位置和按值两种方式。按值查找的平均时间复杂度为O(n)int LocateElem(SqList L, int e) { for (int i 0; i L.length; i) if (L.data[i] e) return i1; // 返回位序 return 0; // 查找失败 }2.2 链表算法精解单链表逆置是经典面试题采用头插法实现void ReverseList(LinkList L) { LNode *p L-next, *q; L-next NULL; // 摘掉头结点 while (p) { q p-next; // 保存后继 p-next L-next; // 头插 L-next p; p q; // 处理下一结点 } }双向链表删除结点时需要注意前后结点的指针修改Status ListDelete_DuL(DuLinkList L, int i) { DuLNode *p GetElemP_DuL(L, i); // 找到第i个结点 if (!p) return ERROR; p-prior-next p-next; // 前驱的后继指向后继 p-next-prior p-prior; // 后继的前驱指向前驱 free(p); // 释放结点 return OK; }3. 树结构深度剖析3.1 二叉树遍历实战非递归中序遍历需要借助栈void InOrder2(BiTree T) { SqStack S; InitStack(S); BiTree p T; while (p || !StackEmpty(S)) { if (p) { // 走到最左边 Push(S, p); p p-lchild; } else { Pop(S, p); // 退栈访问 visit(p); p p-rchild; // 转向右子树 } } }层次遍历需要队列辅助算法如下void LevelOrder(BiTree T) { LinkQueue Q; InitQueue(Q); EnQueue(Q, T); // 根结点入队 while (!QueueEmpty(Q)) { DeQueue(Q, p); // 出队访问 visit(p); if (p-lchild) // 左孩子入队 EnQueue(Q, p-lchild); if (p-rchild) // 右孩子入队 EnQueue(Q, p-rchild); } }3.2 哈夫曼编码实现哈夫曼树构建过程将n个结点作为n棵仅含根节点的二叉树构成森林F选取两棵根节点权值最小的树合并新树根权值为两者之和重复步骤2直到只剩一棵树哈夫曼编码实现代码框架typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; } HTNode, *HuffmanTree; void CreateHuffmanTree(HuffmanTree HT, int *w, int n) { if (n 1) return; m 2 * n - 1; // 总结点数 HT (HuffmanTree)malloc((m1)*sizeof(HTNode)); // 初始化前n个结点 for (i 1; i n; i) HT[i] {w[i-1], 0, 0, 0}; // 构建哈夫曼树 for (i n1; i m; i) { Select(HT, i-1, s1, s2); // 选择两个最小权值的结点 HT[s1].parent HT[s2].parent i; HT[i] {HT[s1].weight HT[s2].weight, 0, s1, s2}; } }4. 图算法专题4.1 图的遍历算法深度优先搜索(DFS)递归实现bool visited[MAX_VERTEX_NUM]; // 访问标记数组 void DFS(Graph G, int v) { visit(v); visited[v] true; for (w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w)) if (!visited[w]) DFS(G, w); }广度优先搜索(BFS)需要队列辅助void BFS(Graph G, int v) { InitQueue(Q); visit(v); visited[v] true; EnQueue(Q, v); while (!isEmpty(Q)) { DeQueue(Q, v); for (w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w)) if (!visited[w]) { visit(w); visited[w] true; EnQueue(Q, w); } } }4.2 最短路径算法Dijkstra算法求单源最短路径void Dijkstra(Graph G, int v0, int dist[], int path[]) { bool final[MAX_VERTEX_NUM] {false}; for (int i 0; i G.vexnum; i) { dist[i] G.arcs[v0][i]; path[i] (G.arcs[v0][i] ! INF) ? v0 : -1; } final[v0] true; for (int i 1; i G.vexnum; i) { int min INF, v; for (int w 0; w G.vexnum; w) if (!final[w] dist[w] min) { v w; min dist[w]; } final[v] true; for (int w 0; w G.vexnum; w) if (!final[w] (min G.arcs[v][w] dist[w])) { dist[w] min G.arcs[v][w]; path[w] v; } } }5. 查找算法精要5.1 二叉排序树操作二叉排序树的查找递归实现BSTNode *BST_Search(BSTree T, int key) { if (!T || key T-key) return T; else if (key T-key) return BST_Search(T-lchild, key); else return BST_Search(T-rchild, key); }二叉排序树插入新结点Status BST_Insert(BSTree T, int k) { if (!T) { // 原树为空 T (BSTree)malloc(sizeof(BSTNode)); T-key k; T-lchild T-rchild NULL; return true; } else if (k T-key) // 已存在相同关键字 return false; else if (k T-key) return BST_Insert(T-lchild, k); else return BST_Insert(T-rchild, k); }5.2 平衡二叉树调整LL型平衡旋转右旋void R_Rotate(AVLTree p) { AVLTree lc p-lchild; p-lchild lc-rchild; lc-rchild p; p lc; // p指向新的根结点 }LR型平衡旋转先左旋后右旋void LR_Rotate(AVLTree p) { AVLTree lc p-lchild; AVLTree rd lc-rchild; // 对lc左旋 lc-rchild rd-lchild; rd-lchild lc; // 对p右旋 p-lchild rd-rchild; rd-rchild p; p rd; // p指向新的根结点 }6. 排序算法全解6.1 快速排序优化快速排序基本实现void QuickSort(int A[], int low, int high) { if (low high) { int pivotpos Partition(A, low, high); QuickSort(A, low, pivotpos - 1); QuickSort(A, pivotpos 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; }优化策略三数取中法选择枢轴小数组时改用插入排序尾递归优化减少栈深度6.2 堆排序实现建立大根堆的调整算法void HeapAdjust(int A[], int k, int len) { A[0] A[k]; // 暂存子树的根结点 for (int i 2*k; i len; i * 2) { if (i len A[i] A[i1]) i; // 取较大的子结点 if (A[0] A[i]) break; else { A[k] A[i]; // 将A[i]调整到双亲结点 k i; // 修改k值继续向下筛选 } } A[k] A[0]; // 被筛选结点放入最终位置 } void BuildMaxHeap(int A[], int len) { for (int i len/2; i 0; i--) // 从最后一个非终端结点开始 HeapAdjust(A, i, len); }堆排序主算法void HeapSort(int A[], int len) { BuildMaxHeap(A, len); // 初始建堆 for (int i len; i 1; i--) { swap(A[i], A[1]); // 输出堆顶元素 HeapAdjust(A, 1, i-1); // 调整剩余元素为新堆 } }7. 综合应用案例7.1 表达式求值系统利用栈实现表达式求值int EvaluateExpression() { InitStack(OPTR); Push(OPTR, #); // 运算符栈 InitStack(OPND); // 操作数栈 c getchar(); while (c ! # || GetTop(OPTR) ! #) { if (!In(c, OP)) { // 不是运算符则进操作数栈 n 0; while (!In(c, OP)) { n n * 10 (c - 0); c getchar(); } Push(OPND, n); } else { switch (Precede(GetTop(OPTR), c)) { case : // 栈顶优先级低 Push(OPTR, c); c getchar(); break; case : // 脱括号 Pop(OPTR, x); c getchar(); break; case : // 退栈计算 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b)); break; } } } return GetTop(OPND); }7.2 文件目录管理系统采用树形结构实现文件目录管理typedef struct TreeNode { char name[100]; // 文件/目录名 bool isDir; // 是否为目录 struct TreeNode *firstChild; // 第一个孩子 struct TreeNode *nextSibling; // 下一个兄弟 } FileNode; // 创建新目录 FileNode* CreateDir(char *name) { FileNode *node (FileNode*)malloc(sizeof(FileNode)); strcpy(node-name, name); node-isDir true; node-firstChild node-nextSibling NULL; return node; } // 添加子目录或文件 void AddChild(FileNode *parent, FileNode *child) { if (!parent-firstChild) { parent-firstChild child; } else { FileNode *p parent-firstChild; while (p-nextSibling) p p-nextSibling; p-nextSibling child; } } // 递归遍历目录 void ListDir(FileNode *dir, int depth) { for (int i 0; i depth; i) printf( ); printf(%s\n, dir-name); FileNode *p dir-firstChild; while (p) { if (p-isDir) ListDir(p, depth 1); else { for (int i 0; i depth 1; i) printf( ); printf(%s\n, p-name); } p p-nextSibling; } }