《数据结构精讲与习题详解（C语言版第2版）/清华大学计算机系列教》

书海网短评：
　　本书是清华大学出版社出版的《数据结构(C语言版)》(第2版)的配套教材，对“数据结构”课程常用习题进行了解析，对许多不易通过自学理解的概念和知识做了深入讲解，并针对“数据结构”课程的学习给出了指导性建议。本书覆盖了数据结构与算

内容简介

　　《数据结构精讲与习题详解（C语言版第2版）/清华大学计算机系列教材》是清华大学出版社出版的《数据结构(C语言版)》(第2版)的配套教材，对“数据结构”课程常用习题进行了解析，对许多不易通过自学理解的概念和知识做了深入讲解，并针对“数据结构”课程的学习给出了指导性建议。《数据结构精讲与习题详解（C语言版第2版）/清华大学计算机系列教材》覆盖了数据结构与算法的主要知识点，共分为8章，包括数据结构绪论，线性表，栈和队列，多维数组、字符串与广义表，树与二叉树，图，查找以及排序。每章划分为多个知识点，首先给出知识点提要，归纳有关要点和容易忽略的细节；然后给出选择题、判断题、简答题和算法题4种题型的典型习题。《数据结构精讲与习题详解（C语言版第2版）/清华大学计算机系列教材》的题量为2840题。
　　《数据结构精讲与习题详解（C语言版第2版）/清华大学计算机系列教材》既可以作为大学计算机科学与技术、软件工程等专业的本科生学习“数据结构”课程的辅助教材，也可供考研人员自学参考。

作者简介

　　殷人昆，清华大学计算机系教授，1985年赴日本国东京理科大学做访问学者，研究方向为软件工程过程的质量管理和软件产品的质量评价。主要教学工作为计算机系大学本科“数据结构”、“软件工程”和研究生“软件工程设计与技术”、“软件项目管理”课程负责人，主持教育部-微软精品课程“数据结构”的建设。曾与人合作或单独编写和出版教材20余部，其中，《数据结构》教材被评为教育部普通高等教育“十一五”国家级规划教材，并于2005年获“北京市精品教材”。曾在核心刊物和专业会议发表论文多篇，并参加或主持多项科研项目。

精彩书摘

　　第3章栈和队列〖1〗本章的知识结构图栈和队列的知识结构图如图31所示。本章的主要知识点有六个，即栈的概念与存储表示、队列的概念与存储表示、栈的应用、队列的应用、栈和递归、特殊队列(包括双端队列和优先级队列)。
　　图31栈和队列的知识结构图
　　3.1栈〖*4/5〗3.1.1知识点提要1.栈的定义及基本运算
　　(1)栈(stack)可定义为只允许在表的末端进行插入和删除的线性表。允许插入和删除的一端叫做栈顶(top)，而不允许插入和删除的另一端叫做栈底(bottom)。当栈中没有任何元素时则成为空栈。
　　(2)栈只能通过栈顶进行访问，故栈叫做后进先出(LastInFirstOut,LIFO)或先进后出(FirstInLastOut,FILO)的线性表。
　　(3)栈的基本运算包括以下5种:
　　栈初始化voidinitStack(Stack&S):创建一个空栈S并使之初始化。
　　判栈空否intStackEmpty(Stack&S):当栈S为空时函数返回1，否则返回0。
　　进栈intPush(Stack&S,typex):当栈S未满时，函数将元素x加入并使之成为新的栈顶。若操作成功，则函数返回1，否则函数返回0。
　　出栈intPop(Stack&S,type&x):当栈S非空时，函数将栈顶元素从栈中退出并通过引用参数x返回退出元素的值。若操作成功，则函数返回1，否则函数返回0。
　　读栈顶元素intgetTop(Stack&S,type&x):当栈S非空时，函数将通过引用参数x返回栈顶元素的值(但不退出)。若操作成功，则函数返回1，否则函数返回0。
　　利用上述5种基本运算，可以实现基于栈结构的应用问题的求解。
　　注意，栈操作Pop(S,x)与getTop(S,x)是有区别的。前者退出栈顶的元素；后者仅复制出一份栈顶元素，栈中元素个数不发生变化。
　　2.栈的混洗(shuffle)
　　(1)当一串元素通过栈时，出栈元素的次序如何排列，与进栈和出栈操作的排列组合有关。如果每个元素进栈后立即出栈，所有出栈元素的排列与进栈顺序完全相同；如果所有元素都进栈后才开始出栈，所有出栈元素的排列与进栈顺序完全颠倒。
　　(2)栈的进出规则:利用铁路调车轨道的栈式结构分析，当列车车厢按照1,2,…,n的编号进栈时，可能的不同出栈序列数目可利用catalan函数算出:1n+1Cn2n=1n+1×(2n)!n!×n!3.栈的顺序存储结构
　　栈的顺序存储，简称顺序栈，是指用一组地址连续的存储单元依次存储栈中元素，同时附设指针top指示栈顶元素。
　　(1)顺序栈的存储分配有两种:
　　①顺序栈的静态存储分配，它的存储数组采用静态方式定义。#definemaxSize100
　　typedefcharSElemType;
　　typedefstruct{
　　SElemTypeelem\[maxSize\];
　　inttop;
　　}SeqStack;顺序栈的静态存储结构预先定义或申请栈的存储空间，一旦装满就不能扩充。因此在顺序栈中，当一个元素进栈之前，需要判断是否栈满，若栈满，则元素进栈会发生上溢现象。
　　②顺序栈的动态存储分配，它的存储数组在使用时动态存储分配，其好处是一旦栈满可以扩充。顺序栈的动态存储结构定义如下(保存于SeqStack.h):#defineinitSize100
　　typedefcharSElemType;
　　typedefstruct{
　　SElemTypeelem;
　　intmaxSize,top;
　　}SeqStack;在初创基于动态存储分配的顺序栈时必须立即为它动态分配存储空间:elem=(SElemType)malloc(initSizesizeof(SELemType))并以initSize作为最初的maxSize。在扩充时需要申请一个新的具有2×maxSize的连续的存储空间取代原来的存储空间，把原来存储空间内存放的所有栈元素转移到新的存储空间后释放原来的存储空间，再让elem指针指示新的存储空间，并让maxSize=2×maxSize。
　　(2)进栈和出栈的处理。有两种进栈和出栈的处理方式。
　　先让栈顶指针进一，再按栈顶指针所指位置把进栈元素加入。这样，栈顶是最后加入元素所处的位置。它的示意图参看图32。
　　图32顺序栈的示意图之一
　　按照这种处理方式，在使用栈之前需要做初始化工作，即置空栈。因为一维数组下标从0开始，栈空时应该top