《数据结构》考研复习精编

《数据结构》考研复习精编 黄明 ming_huang@126.com 《数据结构》《数据结构》《数据结构》《数据结构》 考研复习精编考研复习精编考研复习精编考研复习精编 黄明黄明黄明黄明 编编编编 《数据结构》考研复习精编 黄明 ming_huang@126.com 前言前言前言前言 本资料，是编者考研复习过程中整理的一个复习笔记，本资料，是编者考研复习过程中整理的一个复习笔记，本资料，是编者考研复习过程中整理的一个复习笔记，本资料，是编者考研复习过程中整理的一个复习笔记， 经一个多月，悉心总结而成，融合了很多网上的资料和编经一个多月，悉心总结而成，融合了很多网上的资料和编经一个多月，悉心总结而成，融合了很多网上的资料和编经一个多月，悉心总结而成，融合了很多网上的资料和编者者者者 的复习成果。严格按照考研大纲整理，整理过程漫长而艰的复习成果。严格按照考研大纲整理，整理过程漫长而艰的复习成果。严格按照考研大纲整理，整理过程漫长而艰的复习成果。严格按照考研大纲整理，整理过程漫长而艰难，难 ，难 ，难 ， 相信认真看完的同学，应该能体会编者的辛苦。简简单单相信认真看完的同学，应该能体会编者的辛苦。简简单单相信认真看完的同学，应该能体会编者的辛苦。简简单单相信认真看完的同学，应该能体会编者的辛苦。简简单单几几几几 十页，把所有的考点都罗列出来，由于篇幅的限制，有些十页，把所有的考点都罗列出来，由于篇幅的限制，有些十页，把所有的考点都罗列出来，由于篇幅的限制，有些十页，把所有的考点都罗列出来，由于篇幅的限制，有些算算算算 法并未作详细解释，但这也恰恰是精编的含义，一根主线，法并未作详细解释，但这也恰恰是精编的含义，一根主线，法并未作详细解释，但这也恰恰是精编的含义，一根主线，法并未作详细解释，但这也恰恰是精编的含义，一根主线， 帮你把数据结构的考点，从头到尾穿成一串。帮你把数据结构的考点，从头到尾穿成一串。帮你把数据结构的考点，从头到尾穿成一串。帮你把数据结构的考点，从头到尾穿成一串。 我给同学们的复习建议是：仔细研读精编里的，有我给同学们的复习建议是：仔细研读精编里的内容，有我给同学们的复习建议是：仔细研读精编里的内容，有我给同学们的复习建议是：仔细研读精编里的内容，有 不懂的地方去查书或与同学讨论，精编之外的东西，即是不懂的地方去查书或与同学讨论，精编之外的东西，即是不懂的地方去查书或与同学讨论，精编之外的东西，即是不懂的地方去查书或与同学讨论，精编之外的东西，即是考考考考 纲之外的东西，完全没必要去看，看了只会浪费时间，精纲之外的东西，完全没必要去看，看了只会浪费时间，精纲之外的东西，完全没必要去看，看了只会浪费时间，精纲之外的东西，完全没必要去看，看了只会浪费时间，精编编编编 中配备的都是真和大纲的样题，权威性是任何模拟题无中配备的都是和大纲的样题，权威性是任何模拟题无中配备的都是真题和大纲的样题，权威性是任何模拟题无中配备的都是真题和大纲的样题，权威性是任何模拟题无法法法法 比拟的，值得同学们仔细研究，认真揣摩出题意图，结合比拟的，值得同学们仔细研究，认真揣摩出题意图，结合比拟的，值得同学们仔细研究，认真揣摩出题意图，结合比拟的，值得同学们仔细研究，认真揣摩出题意图，结合考考考考 点有针对性的复习，待到临场应战时一定会游刃有余。点有针对性的复习，待到临场应战时一定会游刃有余。点有针对性的复习，待到临场应战时一定会游刃有余。点有针对性的复习，待到临场应战时一定会游刃有余。 由于作者水平有限，时间又很仓促，复习精编肯定会存由于作者水平有限，时间又很仓促，复习精编肯定会存由于作者水平有限，时间又很仓促，复习精编肯定会存由于作者水平有限，时间又很仓促，复习精编肯定会存 在这样或那样的问题，欢迎同学来信指正。在这样或那样的问题，欢迎同学来信指正。在这样或那样的问题，欢迎同学来信指正。在这样或那样的问题，欢迎同学来信指正。 邮箱：邮箱：邮箱：邮箱：ming_huang@126.com 编者 2009年 10 月 《数据结构》考研复习精编 黄明 ming_huang@126.com 数据结构 2010201020102010考研大纲 【考查目标】 1.1.1.1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各 种基本操作的实现。 2.2.2.2.掌握基本的数据处理原理和方法的基础上，能够对算法时间复杂度与空间复杂 度进行设计与。 3.3.3.3.能够选择合适的数据结构和方法进行问题求解，具备采用 CCCC或 C++C++C++C++或 JAVAJAVAJAVAJAVA 语言设计与实现算法的能力。 一、线性 （一）线性表的定义和基本操作 （二）线性表的实现 1.1.1.1.顺序存储结构 2.2.2.2.链式存储结构 3.3.3.3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.1.1.1.二叉树的定义及其主要特征 2.2.2.2.二叉树的顺序存储结构和链式存储结构 3.3.3.3.二叉树的遍历 4.4.4.4.线索二叉树的基本概念和构造 5.5.5.5.二叉排序树 6.6.6.6.平衡二叉树 （三）树、森林 1.1.1.1.书的存储结构 2.2.2.2.森林与二叉树的转换 3.3.3.3.树和森林的遍历 （四）树与二叉树的应用 1.1.1.1.二叉排序树等价类问题 2.2.2.2.平衡二叉树 3.3.3.3.哈夫曼（HuffmanHuffmanHuffmanHuffman）树和哈夫曼编码 四、 图 （一） 图的概念 《数据结构》考研复习精编 黄明 ming_huang@126.com （二） 图的存储及基本操作 1.1.1.1. 邻接矩阵法 2.2.2.2. 邻接表法 （三） 图的遍历 1.1.1.1. 深度优先搜索 2.2.2.2. 广度优先搜索 （四） 图的基本应用及其复杂度分析 1.1.1.1. 最小（代价）生成树 2.2.2.2. 最短路径 3.3.3.3. 拓扑排序 4.4.4.4. 关键路径 五、 查找 （一） 查找的基本概念 （二） 顺序查找法 （三） 折半查找法 （四） B-B-B-B-树及其基本操作、B+B+B+B+树的基本概念 （五） 散列（HashHashHashHash）表 （六） 查找算法的分析及应用 六、 内部排序 （一） 排序的基本概念 （二） 插入排序 1.1.1.1. 直接插入排序 2.2.2.2. 折半插入排序 （三） 气泡排序（bubblebubblebubblebubble sortsortsortsort） （四） 简单选择排序 （五） 希尔排序（shellshellshellshell sortsortsortsort） （六） 快速排序 （七） 堆排序 （八） 二路归并排序（mergemergemergemerge sortsortsortsort） （九） 基数排序 （十） 各种内部排序算法的比较 （十一） 内部排序算法的应用 《数据结构》考研复习精编 黄明 ming_huang@126.com 第一部分 线性存储结构 复习策略：线性表部分由于比较简单，又是整个数据结构的基础，所以考察的内 容会比较细致。对于线性表灵活运用的程度要求较高。复习时，应充分理解线性 表的顺序存储，链式存储（单链表、静态链表、循环链表、双向链表）。熟练掌 握初始化、插入、删除等，这些基本操作。此部分，有可能出大题的地方：集合 求并、一元多项式求和。 09090909年真题分值比例：综合题 1 道（15 分） 33.3%33.3%33.3%33.3% 一、 线性表 （一） 线性表的定义和基本操作 线性表是 n 个数据元素的有限序列。 基本操作： ① 结构初始化： InitList（&L）//初始化 ② 结构销毁 DestroyList（&L）//销毁 ③ 引用型操作 ListEmpty(L)//判空 ListLength(L)//返回元素个数 GetElem(L,I,&e)//返回 i 元 LocateElem(L,e,compare()) //返回第一个与 e compare 的元素 PriorElem(L,cur_e,&pre_e)//返回前驱 NextElem(L,cur_e,&next_e)//返回后继 ListTraverse(L,visit( ))//遍历 ④ 加工型操作 ClearList( &L )//置空 PutElem( &L, i,&e )//i 元赋 e ListInsert( &L, i, e )//插入 ListDelete( &L, i, &e )//删除 （二） 线性表的实现 1. 顺序存储 //----- 顺序存储结构 ------ 结构定义: ＃define LIST_MAX_LENGTH 100 ＃define LISTINCREMENT 10 typedef struct { ElemType *item; int length; 《数据结构》考研复习精编 黄明 ming_huang@126.com int listsize； }SqList； 基本操作： ①初始化 Status InitList_Sq( SqList& L ) { // 构造一个空的线性表 L.elem = (ElemType*) malloc (LIST_ INIT_SIZE∗sizeof (ElemType)); if (!L.elem) exit (OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE return OK; } // InitList_Sq ②插入 Status ListInsert_Sq(SqList &L, int i, ElemType e) { //在顺序表 L 的第 i 个元素之前插入新的元素 e, // i 的合法范围为 1≤i≤L.length+1 …… q = &(L.elem[i-1]); // q 指示插入位置 for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p; *q = e; // 插入 e ++L.length; // 表长增 1 return OK; } // ListInsert_Sq ③删除 Status ListDelete_Sq( SqList &L,int i, ElemType &e) { if ((i < 1) || (i > L.length)) return ERROR; //删除位置不合法 p = &(L.elem[i-1]); // p 为被删除元素的位置 e = *p; //被删除元素的值赋给 e q = L.elem+L.length-1; //表尾元素的位置 for (++p; p <= q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移 --L.length; //表长减 1 return OK; } // ListDelete_Sq 2.链式存储 //------ 2.1 基本链式存储结构 ------ 结构定义: 《数据结构》考研复习精编 黄明 ming_huang@126.com typedef struc LNode{ // 定义单链表结点 ElemType data; //数据域 struct LNode *next //指针域 }LNode, *LinkList； 基本操作： ①插入 Status ListInsert_L(LinkList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第 i 个结点之前插入新的元素 p = L; j = 0; while (p && j < i-1) { p = p->next; ++j; } // 寻找第 i-1 个结点 if (!p || j > i-1) return ERROR; // i 大于表长或者小于 1 …… } // LinstInsert_L ②删除 Status ListDelete_L(LinkList L, int i, ElemType &e) { //删除以 L 为头指针(带头结点)的单链表中第 i 个结点 p = L; j = 0; while (p->next && j < i-1) { p = p->next; ++j; } // 寻找第 i 个结点，并令 p 指向其前趋 if (!(p->next) || j > i-1) return ERROR; // 删除位置不合理 q = p->next; p->next = q->next; // 删除并释放结点 e = q->data; free(q); return OK; } // ListDelete_L //----- 2.2 静态单链表存储结构 ------ 结构定义: ＃define MAXSIZE 1000 Typedef struct { ElemType data; Int cut; }component,SLinkList[MAXSIZE]; 基本操作： ①查找置 Int LocateElem_SL(SLinkList S,ElemType e){ //返回第一个与 e 相等的元素位置 《数据结构》考研复习精编 黄明 ming_huang@126.com i=S[0].cur; while(i&&S[i].data!=e) i=S[i].cur; return I; }//LocateElem_SL //----- 2.3 循环链表 ------ 与单链表的区别：最后结点的指针与指向头结点，所以循环的结束条件是 p 或 p- >next 是否为空。 //----- 2.4 双向链表储 ----- 结构定义: typedef struct DuLNode { ElemType data; // 数据域 struct DuLNode *prior; //前驱指针 struct DuLNode *next; //后继指针 } DuLNode, *DuLinklist; （三）线性表的应用 1.集合求并 2.一元多项式求和 试题： 【09090909年真题】 参考答案： 《数据结构》考研复习精编 黄明 ming_huang@126.com 《数据结构》考研复习精编 黄明 ming_huang@126.com 第二部分 栈、队列和数组 复习策略：栈、队列和数组是数据结构的重要工具，考察重点偏向于应用。对于 具体的定义的方式简单清楚就可以，重点是理解栈、队列的特点，熟练掌握栈、 队列一些经典的应用，在编程题中，常常会用到栈队列数组作为工具。 09090909年真题分值比例：选择题 2 道 （2*2=4 分） 8.9%8.9%8.9%8.9% 一、 栈 （一） 基本概念 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底， 不含元素的空表称空栈。 基本操作： InitStack(&S) DestroyStack(&S) StackLength(S) StackEmpty(s) GetTop(S, &e) ClearStack(&S) Push(&S, e) Pop(&S, &e) StackTravers(S, visit()) （二）栈的顺序存储结构 //----- 顺序存储结构 ------ 结构定义: #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct { SElemType *base; SElemType *top; int stacksize; } SqStack; 基本操作： ①初始化： Status InitStack (SqStack &S) {// 构造一个空栈 S S.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType)); if (!S.base) exit (OVERFLOW);//分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; 《数据结构》考研复习精编 黄明 ming_huang@126.com return OK; } ②入栈： Status Push (SqStack &S, SElemType e) { if (S.top - S.base >= S.stacksize) { //栈满，追加存储空间 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++ = e; return OK; } ③出栈： Status Pop (SqStack &S, SElemType &e) { // 若栈不空，则删除 S 的栈顶元素， // 用 e 返回其值，并返回 OK； // 否则返回 ERROR if (S.top == S.base) return ERROR; e = *--S.top; return OK; } （三）栈的链式存储结构 栈的链式存储结构。栈顶指针就是链表的头指针。 ①入栈操作 p->next=top ; top=p ②出栈操作 q=top ; top=top->next （四）栈的应用 1. 数制转换 void conversion( ) { initstack(S); scanf (“%d”,N); while(N){ push(S，N%8); N=N/8; 《数据结构》考研复习精编 黄明 ming_huang@126.com } while(! Stackempty(s)){ pop(S,e); printf(“%d”,e); } }//conversion 2. 括号匹配的检验 检验括号是否匹配的思想：“期待的急迫程度” 3.2.3 行编辑程序问题 Void LineEdit（）｛ InitStack(S); ch=getchar(); while (ch != EOF) { //EOF 为全文结束符 while (ch != EOF && ch != '\n') { switch (ch) { case '#' : Pop(S, c); break; case '@': ClearStack(S); break;// 置空 default : Push(S, ch); break; } ch = getchar();// 从终端接收下一个字符 } ClearStack(S); // 重置 S 为空栈 if (ch != EOF) ch = getchar(); } DestroyStack(S); }//LineEdit 3.2.4 迷宫求解 求迷宫路径算法的基本思想是： 若当前位置“可通”，则纳入路径， 继续前进; 若当前位置“不可通”，则后退，换方向继续探索; 若四周“均无通路”，则将当前位置从路径中删除出去。 3.2.5 表达式求值 OperandType EvaluateExpression() { // 设 OPTR 和 OPND 分别为运算符栈和运算数栈，//OP 为运算符集合。 InitStack (OPTR); Push (OPTR, '#'); initStack (OPND); c = getchar(); while (c!= '#' || GetTop(OPTR)!= '#') { if (!In(c, OP)) { Push((OPND, c); c = getchar(); } // 不是运算符则进栈 《数据结构》考研复习精编 黄明 ming_huang@126.com 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; } // switch } // while return GetTop(OPND); } // EvaluateExpression 二、 队列 （二） 基本概念 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。 基本操作： InitQueue(&Q) DestroyQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q, &e) ClearQueue(&Q) EnQueue(&Q, e) DeQueue(&Q, &e) QueueTravers(Q, visit()) （二）队列的链式存储结构 //----- 链式存储结构 ------ 结构定义: typedef struct QNode{// 结点类型 QElemType data ; struct QNode *next ; }QNode, *QueuePtr; typedef struct{ //链队列类型 QueuePtr front ; //队头指针 QueuePtr rear ; //队尾指针 《数据结构》考研复习精编 黄明 ming_huang@126.com } LinkQueue; 基本操作： ①初始化： Status InitQueue (LinkQueue &Q) { // 构造一个空队列 Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front->next = NULL; return OK; } ②入队： Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素 e 为 Q 的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存储分配失败 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } ③出队： Status DeQueue (LinkQueue &Q, QElemType &e) { // 若队列不空，则删除 Q 的队头元素， //用 e 返回其值，并返回 OK；否则返回 ERROR if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free (p); return OK; } （三）队列的顺序存储结构 //----- 顺序存储结构（循环队列）------ 结构定义: #define MAXQSIZE 100 //最大队列长度 typedef struct { QElemType *base; // 动态分配存储空间 int front; // 头指针，若队列不空， //指向队列头元素 int rear; // 尾指针，若队列不空，指向 // 队列尾元素 的下一个位置 《数据结构》考研复习精编 黄明 ming_huang@126.com } SqQueue; 基本操作： ①初始化： Status InitQueue (SqQueue &Q) { // 构造一个空队列 Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType)); if (!Q.base) exit (OVERFLOW); // 存储分配失败 Q.front = Q.rear = 0; return OK; } ②入队： Status EnQueue (SqQueue &Q, QElemType e) { // 插入元素 e 为 Q 的新 的队尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; } ③出队： Status DeQueue (SqQueue &Q, QElemType &e) { // 若队列不空，则删除 Q 的 队头元素， // 用 e 返回其值，并返回 OK; 否则返回 ERROR if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK; } 三 特殊矩阵的压缩存储 定义：特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。 对称矩阵： 元素满足条件 aij=aji 1=0）个互不相交的有限集 合 T1,T2,… ,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。 结点的度：结点所拥有的子树的个数。 树的度：树中各结点度的最大值。 叶子：度为 0 的结点，也称为终端结点。 分支结点（非终端结点）：度不为 0 的结点，也称为非终端结点。 孩子、双亲、兄弟、祖先、子孙、堂兄弟的概念参考家谱形象记忆 层次：根结点的层数为 1；对其余任何结点，若某结点在第 k 层，则其孩子 结点在第 k+1层。 深度（高度）：树中所有结点的最大层数，也称高度。 层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以 从 1 开始的连续自然数。 有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为 有序树；反之，称为无序树。 森林：m (m≥0)棵互不相交的树的集合。 基本操作： InitTree(&t); destroyTree(&T); CreateTree(&T,definition); ClearTree(&T); TreeEmpty(T); TreeDepth(T); Root(T); Value(T,cur_e); Assign(T,cur_e,value); Parent(T,cur_e); LeftChild(T,cur_e); RightSibling(T,cur_e); 《数据结构》考研复习精编 黄明 ming_huang@126.com InsertChild(&T,&P,I,c); Deletechild(&T,&p,i); TraverseTree(t,Visit(()); （四） 二叉树 1. 二叉树的定义及其主要特性 二叉树是 n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树）， 或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉 树组成。 2.主要特性（选择题必出一道） 性质 1：二叉树的第 i 层上最多有 2i-1个结点（i≥1）。 性质 2：一棵深度为 k 的二叉树中，最多有 2k-1 个结点，最少有 k 个结点。 性质 3：在一棵二叉树中，如果叶子结点数为 n0，度为 2 的结点数为 n2，则有: n0 ＝n2＋1。 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所 有叶子都在同一层上。 完全二叉树：对一棵具有 n 个结点的二叉树按层序编号，如果编号为 i（1≤i≤ n）的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中的位置完全相同。 性质 4：具有 n 个结点的完全二叉树的深度为 log2n +1。 性质 5：对一棵具有 n 个结点的完全二叉树中从 1 开始按层序编号，则对于任意 的序号为 i（1≤i≤n）的结点（简称为结点 i），有： （1）如果 i＞1，则结点 i 的双亲结点的序号为 i/2；如果 i＝1，则结点 i 是 根结点，无双亲结点。 (2)如果 2i≤n，则结点 i 的左孩子的序号为 2i； 如果 2i＞n，则结点 i 无左孩子。 (3)如果 2i＋1≤n，则结点 i 的右孩子的序号为 2i＋1；如果2i＋1＞n，则结点 i 无右孩子。 2. 二叉树的顺序存储结构和链式存储结构 2.1顺序存储结构 //-------二叉树的顺序存储表示 ＃define MAN_TREE_SIZE 100 Typedef TElemType SqBiTree[MAX_TREE_SIZE]; SqBiTree 2.2链式存储结构 //-------二叉树的二叉链表表示----- Typedef struct BiTNode { TelemType data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; 《数据结构》考研复习精编 黄明 ming_huang@126.com 3. 二叉树的遍历 3.1先序遍历（递归） Status PreOrderTraverse(BiTree T, Status (* Visit)(TelemType e)); { if(t){ if(visit(T->data)) if(PreOrderTraverse(T->lchild,Visit)) if(PreOrderTraverse(T->rchild,visit)) return ok; return ERROR; }else return ok; }//PreOrderTraverse 3.2 中序遍历（非递归） Status InOrderTraverse(BiTree t,Status(* Visit)(TelemType e)){ //采用二叉树的二叉链表存储结构，Visit 是对数据元素操作的应用函数。 //中序遍历二叉树 T 的非递归算法，对每个数据元素调用函数 Visit. InitStack(S); Push(s,t);//根指针进 While(!StackEmpty(s)){ While(GetTop(s,p)&&p) Push(s,p->lchild); Pop(s,p); If(!StackEmpty(S)){ Pop(s,p); if(!Visit(p->data)) return Error; Push(S,p->rchild); }//if }//While return ok; }//InOrderTraverse Status InOrder Traverse(BiTree T, Status(*Visit)(TelemType e)){ // // InitStack(s); p=t; While(p||!StackEmpty(s)){ If(p) {push(S,p);p=p->lchild;} Else{ Pop(s,p); if(!visit(p->data)) return ERROR; P=p->rchild; }//else }//While return ok; }//InorderTravers 4 线索二叉树 《数据结构》考研复习精编 黄明 ming_huang@126.com //---二叉树的二叉线索存储表示--- typedef enum PointerTag{ link ,Thread}； typedef Struc BithrNode{ TelemType data; struct Bithrnode *lchild, *rchild;// PointerTag Ltag, Rtag; }BiThrNode, *BiThrTree; Status InOrderTraverse_Thr(BiThrTree t,Status(*visit)(TelemType e)){ //T // p=T-.lchild; while(p!=t){ while(p->Ltag==Link) p=p->lchild; if(!Visit(p->Rtag==Thread&&p->rchild!T){ while(p->Rtag==Thread&&p->rchild!=T){ p=p->rchild; visit(p->data); } p=p->rchild; }return ok; }//InOrderTraverse_Thr Status InOrderThreading(BiThrTree &Thrt, BithrTree t){ //中序遍历二叉树 T，并将其中序线索化，Thrt 指向头结点。 If(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit (OVERFLOw); Thrt->Ltag=Link; Thrt->Rtag=Thead; Thrt->rchild=Thrt; If(!T) Thrt->lchild=Thrt; InThreading(T0; Pre->lchild=T; pre=Thrt; Thrt->rchild=pre; } return ok; }//InOrderThreading Void InThreading(BiThrTree p){ if(p) { InThreading(p->Ltag=Thread; p->lchild=pre;) If(!p->child){ p->Rtag=Thread;pre->rchild=p;} if(!pre->rchild){pre->Rtag==Thread; pre->rchild=p;} pre=p; InThreading)p->rchild); 《数据结构》考研复习精编 黄明 ming_huang@126.com } }//InThreading （三）树和森林 1 树的存储结构 1.1 双亲表示法 #define MAX_Tree_SiZE 100 typedef struct PTNode{ TelemType data; Int parent; }PTNode; typedef struct{ PTNode nodes[MAXTREE_SIZE]; Int r,n; }Ptree; 1.2 孩子表示法 //树的孩子链存储表示 typedef struct CTNode{ int child; struct CTNode *next; } *Childptr; typedef struct{ TelemType data; ChildPtr firstchild; }CtBox; typedef struct{ CTBox nodes[MAX-TREE_SIZE]; Int n,r; }Ctree; 1.3 孩子兄弟表示法 又称二叉树表法或二叉链表表示法。 // 树的二叉链表存储表示 typedef struct CSNode{ ElemType data; struct CSNode *firstchild, *nextsibling; }CSNode, *CSTree; 2.森林与二叉树的转换 森林 二叉树 第一个颗树的根结点 二叉树的根结点 第一个孩子 左子树 其余的孩子 左子树的右子树 《数据结构》考研复习精编 黄明 ming_huang@126.com 其余各树 右子树 3.树和森林的遍历 树（2 种 ）： 先根：访问根结点，先跟遍历每颗子树。 后根：后根遍历各颗子树，访问根结点。 森林（2 种 ）： 先序： 1.访问第一颗树的根结点。 2.先序遍历第一颗树的根结点。 3.先序遍历其余各树构成的森林。 中序： 1.中序遍历第一颗树的根结点的子树森林。 2.访问第一颗树的根结点。 3.中序遍历其余各树构成的子树森林。 对应关系： 树 二叉树 森林 先根 先序 先序 后根 中序 中序 后序 【记】树因无中序，后序来顶替。 （四）树与二叉树的应用 1.二叉排序树 定义： 二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质 的二叉树： ⑴ 若它的左子树不空，则左子树上所有结点的值均小于根结点的值； ⑵ 若它的右子树不空，则右子树上所有结点的值均大于根结点的值； ⑶ 它的左右子树也都是二叉排序树。 【记】左小于右（左子树<根<右子树）。 二叉排序树删除结点： � 被删除的结点是叶子； � 被删除的结点只有左子树或者只有右子树； � 被删除的结点既有左子树，也有右子树。 2.平衡二叉树 平衡二叉树：或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树： ⑴ 根结点的左子树和右子树的深度最多相差 1; ⑵ 根结点的左子树和右子树也都是平衡二叉树。 【记】左右高，（最）多差一。 平衡化方法： 1.LL型：右旋一次 2.RR型：左旋一次 3.LR型：左旋一次右旋一次 4.RL型：右旋一次左旋一次 《数据结构》考研复习精编 黄明 ming_huang@126.com 3.哈夫曼树和哈夫曼编码 叶子结点的权值：对叶子结点赋予的一个有意义的数值量。 二叉树的带权路径长度：设二叉树具有 n 个带权值的叶子结点，从根结点到各个 叶子结点的路径长度与相应叶子结点权值的乘积之和。 哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。 【记】带权路径最小的树。 哈夫曼算法基本思想： ⑴ 初始化：由给定的 n 个权值{w1，w2，…，wn}构造 n 棵只有一个根结点的二 叉树，从而得到一个二叉树集合 F＝{T1，T2，…，Tn}； ⑵ 选取与合并：在 F 中选取根结点的权值最小的两棵二叉树分别作为左、右子 树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的 权值之和； ⑶ 删除与加入：在 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉 树加入到 F 中； ⑷ 重复⑵、⑶两步，当集合 F 中只剩下一棵二叉树时，这棵二叉树便是哈夫曼 树。 试题： 【09090909年真题】 答案：D 答案：B 《数据结构》考研复习精编 黄明 ming_huang@126.com 答案：C 答案：B 【09090909年大纲样题】 42.(15 分 )已知 一 棵 二 叉 树 采 用 二 叉 链 表 存 储 , 结点 构 造 为 : LeftChild Data RightChild ,root 指向根结点。现定义二叉树中结点 X0 的根 路径为从根结点到 X0 结点 的一条路径，请编写算法输出该二叉树中最长的根路径（多条最长根路径中只输出一条即可 。 算法可使用 C 或 C + +或 JAVA 语言实现）。 参考答案： 解：C++代码实现如下。在Ubuntu 8.10下实现通过。 #include #include using namespace std; 结点结构// struct Node { int data; struct Node* left; struct Node* right; }; void printPath( vector& path ) { for ( int i = 0, n = path.size(); i < n; i++ ) { cout<<" "<data; } cout<& path, vector& longest) { if ( pNode == theNode) 《数据结构》考研复习精编 黄明 ming_huang@126.com { if ( longest.size() < path.size() ) { longest = path; } else { longest.push_back(theNode); return ; } } else if (pNode != NULL) { path.push_back( pNode ); postorder( pNode->left, theNode, path, longest); postorder( pNode->right,theNode, path, longest); path.pop_back(); } else return ; } //find the longest path from root to theNode. void GetLongestPath( Node* root, Node* theNode) { vector path; vector longest; postorder( root, theNode, path, longest); cout<<"longest path:"; printPath( longest ); } 下面是测试代码（树的结构如右图所示）： int main() { //为树的每个结点分配内存 Node* nodA = new Node; Node* nodB = new Node; Node* nodC = new Node; Node* nodD = new Node; Node* nodE = new Node; Node* nodF = new Node; Node* nodG = new Node; Node* nodH = new Node; 给每个结点赋值，其中值域作为该结点的编号。 //data nodH->data = 8; nodH->left =NULL; nodH->right =NULL; nodG->data = 7; nodG->left =NULL; nodG->right =NULL; nodF->data = 6; nodF->left =NULL; nodF->right =NULL; nodE->data = 5; nodE->left =nodG; nodE->right =nodH; nodD->data = 4; nodD->left =NULL; nodD->right =nodF; nodC->data = 3; nodC->left =NULL; nodC->right =NULL; nodB->data = 2; nodB->left =nodD; nodB->right =nodE; 《数据结构》考研复习精编 黄明 ming_huang@126.com nodA->data = 1; nodA->left =nodB; nodA->right =nodC; GetLongestPath(nodA, nodG); return 0; } 【10101010年大纲样题】 《数据结构》考研复习精编 黄明 ming_huang@126.com 第四部分 图 复习策略： 图的概念比较多，值得同学们认真研究下，没有基本概念的基础， 就相当于没有单词的英语，是很难把知识掌握清楚的。对于图，是承接着树而衍 生出来的，在实际应用中，图更为广泛。所有问题都是化未知为已知，解决图的 问题，很多时候是借助树和二叉树来实现的，同学们应注意树、二叉树和图之间 的对应关系。考研复习中，图无疑是另一个重点，此部分出大题的可能性很高， 09 年真题的第一道，既是如此。此部分，同学们要重视由人名来命名的算法， 这类算法是为了纪念作者而命名的，可见其经典性，这类算法也相当有难度，考 试时，仅仅只会就此算法稍加改动，或应用算法的思想来命题。 09090909年真题分值比例：选择题 1 道（2 分） 综合题 1 道（10分） 26.7%26.7%26.7%26.7% （五） 图的基本概念 图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E) 其中：G 表示一个图，V是图 G 中顶点的集合，E是图 G 中顶点之间边的集合。 若顶点 vi 和 vj 之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。 如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。 若从顶点 vi到 vj的边有方向，则称这条边为有向边，表示为。 如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。 简单图：【释：无环，无回弧】在图中，若不存在顶点到其自身的边，且同一条 边不重复出现。 邻接、依附【释：挨着】 无向图中，对于任意两个顶点 vi和顶点 vj，若存在边(vi，vj)，则称顶点 vi和顶 点 vj互为邻接点，同时称边(vi，vj)依附于顶点 vi和顶点 vj。 有向图中，对于任意两个顶点 vi 和顶点 vj，若存在弧，则称顶点 vi邻接 到顶点 vj，顶点 vj邻接自顶点 vi，同时称弧依附于顶点 vi和顶点 vj 。 无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完 全图。【释：无箭头】 有向完全图：在有向图中，