搜索
数据结构教材李春葆数据结构教程清华大学出版社严蔚敏数据结构清华大学出版社参考书李春葆数据结构习题与解析(第2版或第3版)清华大学出版社概述模块1：线性表模块2：树型结构模块3：图型结构模块4：其他1.数据结构的定义数据→数据元素→数据项数据结构是指数据以及相互之间的联系（或关系）。包括：（1）数据的逻辑结构。（2）数据的存储结构（物理结构）。（3）施加在该数据上的运算。概述数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。但运算的实现与数据的存储结构有关。程序＝数据结构＋算法概述（1）线性结构（2）树形结构（3）图形结构概述逻辑结构主要有三大类：存储结构分为如下四种：（1）顺序存储方法（2）链式存储方法（3）索引存储方法（4）散列存储方法概述2.算法算法是对特定问题求解步骤的一种描述，它是指令的有限序列。概述算法的五个重要的特性：（1）有穷性（2）确定性（3）可行性（4）有输入（5）有输出概述算法的时间复杂度：是指其基本运算在算法中重复执行的次数。算法中基本运算次数T(n)是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))记号“O”读作“大O”，它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同。概述例分析以下程序段的时间复杂度。i=1;while(i=n)i=i*2;解：上述算法中基本操作是语句i=i*2，设其频度为T(n)，则有：2T(n)≤n即T(n)≤log2n=O(log2n)。所以，该程序段的时间复杂度为O(log2n)。算法空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度。对于空间复杂度为O(1)的算法称为原地工作或就地工作算法。概述■递归定义3.算法设计方法：递归在定义一个算法时出现调用本算法的成分，称之为递归。概述■递归模型由递归出口和递归体组成例如，求二叉树所有结点个数：f(b)=0b=NULLf(b)=f(b-lchild)+f(b-rchild)+1b≠NULL概述■递归算法设计①对原问题f(s)进行分析，假设出合理的“较小问题”f(s');②假设f(s')是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s')之间的关系；③确定一个特定情况（如f(1)或f(0)）的解，由此作为递归出口.概述bb-rchildb-lchild①假设出合理的“较小问题”：假设左右子树的结点个数可求②求出f(s)与f(s‘)之间的关系：f(b)=f(b-lchild)+f(b-rchild)+1③确定递归出口：f(NULL)=0概述intf(BTNode*b){if(b==NULL)return(0);elsereturn(f(b-lchild)+f(b-rchild)+1);}求解算法：概述例设计求f(n)=1+2+...+n的递归算法解：f(n)为前n项之和，则f(n-1)=1+2+...+(n-1)假设f(n-1)可求，则f(n)=f(n-1)+n，所以：f(n)=1当n=1f(n)=f(n-1)+n当n1对应的递归算法如下：intf(intn){if(n==1)return(1);elsereturn(f(n-1)+n));}1.一般线性表线性表：具有相同特性的数据元素的一个有限序列。不是集合。模块1：线性结构逻辑结构（1）顺序表typedefstruct{ElemTypeelem[MaxSize];/*存放顺序表元素*/intlength;/*存放顺序表的长度*/}SqList;存储结构之一模块1：线性结构顺序表基本运算的实现插入数据元素算法：元素移动的次数不仅与表长n有关；插入一个元素时所需移动元素的平均次数n／2。平均时间复杂度为O(n)。模块1：线性结构删除数据元素算法:元素移动的次数也与表长n有关。删除一个元素时所需移动元素的平均次数为(n-1)/2。删除算法的平均时间复杂度为O(n)。模块1：线性结构（2）链表定义单链表结点类型:typedefstructLNode{ElemTypedata;structLNode*next;/*指向后继结点*/}LinkList;存储结构之二模块1：线性结构定义双链表结点类型:typedefstructDNode{ElemTypedata;structDNode*prior;/*指向前驱结点*/structDNode*next;/*指向后继结点*/}DLinkList;模块1：线性结构■单链表基本运算的实现重点：（1）头插法建表和尾插法建表算法，它是很多算法设计的基础；（2）查找、插入和删除操作。模块1：线性结构头插法建表该方法从一个空表开始,读取字符数组a中的字符,生成新结点,将读取的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止。采用头插法建表的算法如下:模块1：线性结构voidCreateListF(LinkList*&L,ElemTypea[],intn){LinkList*s;inti;L=(LinkList*)malloc(sizeof(LinkList));/*创建头结点*/L-next=NULL;for(i=0;in;i++){s=(LinkList*)malloc(sizeof(LinkList));/*创建新结点*/s-data=a[i];s-next=L-next;/*将*s插在原开始结点之前,头结点之后*/L-next=s;}}模块1：线性结构adcbi=0i=1i=2i=3∧head采用头插法建立单链表的过程heada∧headda∧headcda∧headbcda∧第1步:建头结点第2步:i＝0,新建a结点,插入到头结点之后第3步:i＝1,新建d结点,插入到头结点之后第4步:i＝2,新建c结点,插入到头结点之后第5步:i＝3,新建b结点,插入到头结点之后尾插法建表头插法建立链表虽然算法简单,但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致,可采用尾插法建立。该方法是将新结点插到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。采用尾插法建表的算法如下:模块1：线性结构voidCreateListR(LinkList*&L,ElemTypea[],intn){LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList));/*创建头结点*/L-next=NULL;r=L;/*r始终指向终端结点,开始时指向头结点*/for(i=0;in;i++){s=(LinkList*)malloc(sizeof(LinkList));/*创建新结点*/s-data=a[i];r-next=s;/*将*s插入*r之后*/r=s;}r-next=NULL;/*终端结点next域置为NULL*/}adcbi=0i=1i=2i=3head头结点adcbb∧采用尾插法建立单链表的过程模块1：线性结构例设C={a1,b1,a2,b2,…,an,bn}为一线性表,采用带头结点的hc单链表存放,编写一个算法,将其拆分为两个线性表,使得:A={a1,a2,…,an},B={b1,b2,…,bn}模块1：线性结构解:设拆分后的两个线性表都用带头结点的单链表存放。先建立两个头结点*ha和*hb,它们用于存放拆分后的线性表A和B,ra和rb分别指向这两个单链表的表尾,用p指针扫描单链表hc,将当前结点*p链到ha未尾,p沿next域下移一个结点,若不为空,则当前结点*p链到hb未尾,p沿next域下移一个结点,如此这样,直到p为空。最后将两个尾结点的next域置空。对应算法如下:模块1：线性结构voidfun(LinkList*hc,LinkList*&ha,LinkList*&hb){LinkList*p=hc-next,*ra,*rb;ha=hc;/*ha的头结点利用hc的头结点*/ra=ha;/*ra始终指向ha的末尾结点*/hb=(LinkList*)malloc(sizeof(LinkList));/*创建hb头结点*/rb=hb;/*rb始终指向hb的末尾结点*/模块1：线性结构while(p!=NULL){ra-next=p;ra=p;/*将*p链到ha单链表未尾*/p=p-next;rb-next=p;rb=p;/*将*p链到hb单链表未尾*/p=p-next;}ra-next=rb-next=NULL;/*两个尾结点的next域置空*/}模块1：线性结构例已知线性表元素递增有序，并以带头结点的单链表作存储结构，设计一个高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）。并分析所写算法的时间复杂度。模块1：线性结构解：先在单链表中找到其data值则好大于mink的结点*p，其前驱结点为*pre。继续沿next链查找其值大于maxk的结点，在这个过程中删除*p结点。算法如下：voiddelnode(SNode*h,ElemTypemaxk,ElemTypemink){SNode*p,*pre;if(maxk=mink){pre=h;p=pre-next;模块1：线性结构while(p!=NULL&&p-data=mink){pre=p;p=p-next;}while(p!=NULL&&p-datamaxk)//删除*p{pre-next=p-next;free(p);p=pre-next;}}}模块1：线性结构■双链表基本运算的实现重点：插入和删除结点的算法。模块1：线性结构■循环链表基本运算的实现重点：判断最后一个结点。模块1：线性结构例某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用存储方式最节省运算时间。A.单链表B.仅有头结点的单循环链表C.双链表D.仅有尾指针的单循环链表模块1：线性结构例设计一个算法在单链表中查找元素值为e的结点序号的算法LocateElem(L,e)。思路：在单链表L中从头开始找第1个值域与e相等的结点,若存在这样的结点,则返回位置,否则返回0。intLocateElem(LinkList*L,ElemTypee){LinkList*p=L-next;intn=1;while(p!=NULL&&p-data!=e){p=p-next;n++;}if(p==NULL)return(0);elsereturn(n);}解：本题答案为D。在有尾指针r的单循环链表中在最后一个结点之后插入结点*s的操作是：s-next=r-next;r-next=s;r=s。删除第一个结点的操作是：p=r-next;r-next=p-next;free(p)。其时间复杂度均为O(1)。模块1：线性结构2.栈(1)栈的定义栈是一种先进后出表栈的基本运算:进栈，出栈。逻辑结构模块1：线性结构例已知一个栈的进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=n,则pi的值。(A)i(B)n-i(C)n-i+1(D)不确定答:当p1=n时,输出序列必是n,n-1,…,3,2,1,则有:p2=n-1,p3=n-2,…,pn=1推断出pi=n-i+1,所以本题答案为C。例设n个元素进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=3,则p2的值。(A)一定是2(B)一定是1(C)不可能是1(D)以上都不对答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,…,n,但一定不能是1。所以本题答案为C。模块1：线性结构（2）顺序栈typedefstruct{ElemTypeelem[MaxSize];inttop;/*栈指针*/}SqS