课程简介课件

课程简介数据结构深圳大学计算机系

蔡茂国《数据结构》课程简介本课程教材为：《数据结构》(C语言版)严蔚敏，吴伟民清华大学出版社2004年11月（第28次印刷）2主要参考教材《数据结构》课程简介

所有课件、作业及实验，均上传至：深圳大学首页－－课程中心－－输入学生姓名及密码，实现登录－－从《数据结构》课程下下载3课件下载第一章

数据结构绪论数据结构深圳大学计算机系

蔡茂国一、数据5第一节数据结构是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合数值性数据非数值性数据第１章数据结构绪论二、数据元素（DataElement）6第一节数据结构数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(DataItem)组成（此时数据元素被称为记录）数据元素又称为元素、结点、记录第１章数据结构绪论三、数据项（DataItem）7第一节数据结构具有独立含义的最小标识单位。第１章数据结构绪论学号姓名学院专业四、数据对象（DataObject）8第一节数据结构具有相同性质的数据元素的集合。整数数据对象N={0,1,2,…}字母字符数据对象C={‘A’,‘B’,‘C’,…‘F’}。第１章数据结构绪论五、结构（Structure）9第一节数据结构

结构是元素之间的：空间位置关系相互作用和依赖关系第１章数据结构绪论五、结构10第一节数据结构

四种基本结构集合结构线性结构树形结构图形结构第１章数据结构绪论456231125436123456123456六、数据结构（DataStructure）11第一节数据结构1.形式定义：某一数据对象的所有数据成员之间的关系。记为：

Data_Structure={D,S}其中，D是某一数据对象，S是该对象中所有数据成员之间的关系的有限集合。第１章数据结构绪论六、数据结构12第一节数据结构2.线性数据结构举例L={K,R}K={1,2,3,4,5,6}R={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>}第１章数据结构绪论123456六、数据结构13第一节数据结构3.树形数据结构举例T={K,R}K={1,2,3,4,5,6}R={<1,2>,<1,3>,<2,4>,<2,5>,<3,6>}第１章数据结构绪论456231六、数据结构14第一节数据结构4.图形数据结构举例G={K,R}K={1,2,3,4,5,6}R={(1,2),(1,5),(1,6),(2,3),(2,4),(2,6),(3,4),(4,5),(4,6),(5,6)}第１章数据结构绪论123456七、应用举例15第一节数据结构1.线性数据结构举例数据结构学生选课名单（部分）第１章数据结构绪论学号姓名学院专业2004131221黄磊信息工程学院信息工程学院2004131209熊玲玲信息工程学院信息工程学院2004131135彭智俊信息工程学院信息工程学院2004131252徐元庆信息工程学院信息工程学院2004131099吴小池信息工程学院信息工程学院2004131031陈明亮信息工程学院信息工程学院七、应用举例16第一节数据结构2.树形数据结构举例UNIX文件系统结构图（部分）第１章数据结构绪论/

rootbinlibuseretcmathdsswhangxiongpan七、应用举例17第一节数据结构3.图形数据结构举例深圳城市交通示意图（部分）第１章数据结构绪论南山福田罗湖盐田宝安西丽梅林布吉龙华龙岗八、数据结构要解决的问题18第一节数据结构如何为应用程序中涉及到各种各样的数据，建立相应的数据结构（表、树或图），并依此实现软件功能从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现第１章数据结构绪论一、逻辑结构19第二节数据的结构逻辑结构描述数据元素之间的关系线性结构线性表（表，栈，队列，串等）非线性结构树（二叉树，Huffman树，二叉排序树等）图（有向图，无向图等）第１章数据结构绪论456231123456123456二、物理结构（存储结构）20第二节数据的结构物理结构是数据结构在计算机中的表示（或映象）顺序存储表示（可以用C语言中一维数组表示）链接存储表示（可以用C语言中的指针表示）索引存储表示散列存储表示第１章数据结构绪论二、物理结构（存储结构）21第二节数据的结构复数存储结构举例第１章数据结构绪论z1=3.0

-2.3i指针或链(地址)

…041506110613……-2.33.00415z1=3.0

-2.3i

z2=-0.7+4.8i…0300030206320634……3.0-2.3-0.74.8顺序存储结构链式存储结构一、数据类型22第三节数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称如C语言中的整型变量(int)，其值集为某个区间上的整数，定义在其上的操作为+,-,x,/等第１章数据结构绪论二、原子数据类型和结构数据类型23第三节数据类型1.原子数据类型是不可分解的数据类型如C语言中的整型(int)，实型(float)，字符型(char)，指针类型(*)和空类型(void)等第１章数据结构绪论二、原子数据类型和结构数据类型24第三节数据类型2.结构数据类型由若干成分（原子类型或结构类型）按某种结构组成的数据类型结构数据类型可以看作是一种数据结构和定义在其上的一组操作组成的整体如数组，由若干分量组成，每个分量可以是整数，也可以是数组（如intA[10]）第１章数据结构绪论三、抽象数据类型（AbstractDataType）25第三节数据类型由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离第１章数据结构绪论三、抽象数据类型（ADT）26第三节数据类型抽象数据类型（ADT）是一个数学模型以及定义在该模型上的一组操作抽象数据类型=数据结构+定义在此数据结构上的一组操作第１章数据结构绪论三、抽象数据类型（ADT表示）27第三节数据类型抽象数据类型可用（D，S，P）三元组表示D是数据对象S是D上的关系集P是对D的基本操作集。第１章数据结构绪论三、抽象数据类型（ADT定义）28第三节数据类型ADT抽象数据类型名{ 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作(函数)的定义〉 }ADT抽象数据类型名第１章数据结构绪论三、抽象数据类型（ADT定义举例）29第三节数据类型ADTTriplet{ 数据对象：D={e1,e2,e3|e1,e2,e3∈ElemSet} 数据关系：R={<e1,e2>,<e2,e3>} 基本操作：Max(T,&e)初始条件：三元组T已存在。

操作结果：用e返回T的3个元素中的最大值。

Min(T,&e)初始条件：三元组T已存在。

操作结果：用e返回T的3个元素中的最小值。

}ADTTriplet第１章数据结构绪论三、抽象数据类型（ADT定义实现）30第三节数据类型抽象数据类型可以通过固有数据类型(C语言中已实现的数据类型)来实现抽象数据类型类class数据对象数据成员基本操作成员函数(方法)第１章数据结构绪论一、算法（Algorithm）31第四节算法分析算法是对特定问题求解步骤的一种描述是一有限长的操作序列第１章数据结构绪论一、算法（特性）32第四节算法分析有穷性：算法在执行有穷步后能结束确定性：每步定义都是确切、无歧义可行性：每一条运算应足够基本(已验算正确)输入：有0个或多个输入输出：有一个或多个输出第１章数据结构绪论一、算法（举例）33第四节算法分析例子：选择排序问题：递增排序解决方案：逐个选择最小数据算法框架：

for(inti=0;i<n-1;i++){//n-1趟 从a[i]检查到a[n-1]，找到最小数; 若最小整数在a[k],交换a[i]与a[k]; }第１章数据结构绪论二、算法设计的要求34第四节算法分析正确性：满足具体问题的需求可读性：便于理解和修改健壮性：当输入数据非法时，也能适当反应效率高：执行时间少空间省：执行中需要的最大存储空间第１章数据结构绪论三、时间复杂度35第四节算法分析衡量算法的效率，主要依据算法执行所需要的时间，即时间复杂度事后统计法：计算算法开始时间与完成时间差值事前统计法：依据算法选用何种策略及问题的规模n，是常用的方法第１章数据结构绪论三、时间复杂度36第四节算法分析时间复杂度是问题规模n的函数f(n)，即：

T(n)=O(f(n))一般地，时间复杂度用算法中最深层循环内的语句中的原操作的重复执行次数表示第１章数据结构绪论三、时间复杂度37第四节算法分析a.{y*=x;}b.for(i=1;i<=n;i++}{y*=x;}c.for(j=1;j<=n;j++}for(i=1;i<=n;i++}{y*=x;}a,b,c三个算法中，“y*=x;”程序段的时间复杂度分别为O(1),O(n),O(n2)，分别称为常量阶，线性阶，平方阶第１章数据结构绪论三、时间复杂度38第四节算法分析时间复杂度除常量阶[O(1)],

线性阶[O(n)],平方阶[O(n2)]外，还有对数阶[O(logn)]，排列阶[O(n!)]，指数阶[O(2n)]等，是相对于问题规模n的增长率的表示方法指数阶随问题规模增长过快，一般不宜使用第１章数据结构绪论三、时间复杂度39第四节算法分析如果算法的执行有多种可能的操作顺序，则求其平均时间复杂度如果无法求取平均时间复杂度，则采用最坏情况下的时间复杂度时间复杂度是衡量算法好坏的一个最重要的标准第１章数据结构绪论四、空间复杂度40第四节算法分析空间复杂度指算法执行时，所需要存储空间的量度，它也是问题规模的函数，即：

S(n)=O(f(n))第１章数据结构绪论第二章

线性表数据结构深圳大学计算机系

蔡茂国一、线性数据结构的特点42第一节线性表在数据元素的非空有限集中１、存在惟一的一个被称作“第一个”的数据元素(如“１”)２、存在惟一的一个被称作“最后一个”的数据元素(如“６”)３、除第一个元素外，每个数据元素均只有一个前驱４、除最后一个元素外，每个数据元素均只有一个后继(next)(如“1”的next是“2”,“2”的next是“3”)第２章线性表123456二、线性表43第一节线性表线性表是最简单的一类线性数据结构线性表是由n个数据元素组成的有限序列，相邻数据元素之间存在着序偶关系，可以写为：(a1,a2,…ai-1,ai,ai+1,…an-1,an)其中,ai是表中元素,i表示元素ai的位置,n是表的长度第２章线性表二、线性表44第一节线性表线性表中的元素具有相同的特性，属于同一数据对象，如：1.26个字母的字母表:(A,B,C,D,…,Z)2.近期每天的平均温度:(30℃,28℃,29℃,…)第２章线性表一、顺序表45第二节顺序表顺序表是线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素第２章线性表ABCDE…YZ

bb+1b+2b+3b+4…b+24b+25一、顺序表（元素位置）46第二节顺序表顺序表数据元素的位置：

LOC(a

i)=LOC(ai-1)+l

LOC(ai)=LOC(a1)+(i-1)*l

l表示元素占用的内存单元数第２章线性表a1

a2

…ai………an

12…i………n

bb+l…b+(i-1)*l………b+(n-1)*lidle二、顺序表的定义47第二节顺序表采用C语言中动态分配的一维数组表示顺序表第２章线性表#defineLIST_INIT_SIZE100 //线性表存储空间的初始分配量#defineLISTINCREMENT10 //线性表存储空间的分配增量Typedefstruct{

ElemType *elem; //存储空间基址

int length; //当前长度

int listsize; //当前分配的存储容量(元素数)}Sqlist;三、顺序表的初始化48第二节顺序表创建一个顺序表L第２章线性表StatusInitList_Sq(Sqlist&L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW); //存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE; //初始存储容量 returnOK;}//InitList_Sq三、顺序表的插入49第二节顺序表顺序表的插入操作是指在顺序表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，即将长度为n的顺序表：(a1,…ai-1,ai,…,an)

变成长度为n+1的顺序表：(a1,…ai-1,e,ai,…,an)第２章线性表三、顺序表的插入50第二节顺序表在第3个元素与第4个元素之间插入新元素b需要将最后元素n至第4元素(共7-4+1)都向后移一位置第２章线性表253457164809630123456725345750164809635050插入ei=401234567三、顺序表的插入51第二节顺序表第２章线性表StatusListInsert_Sq(Sqlist&L,inti,ElemTypee){if(i<1||i>L.length+1)returnERROR;if(L.length>=L.listsize){

newbase=realloc(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCRMENT;} //以上皆为准备阶段q=&(L.elem[i-1]); //找到插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p; //右移*q=e;++L.length;returnOK;}//ListInsert_Sq //请注意元素位置数值较元素序号少1三、顺序表的插入52第二节顺序表在顺序表中插入一个元素，需要向后移动元素个数为：n-i+1平均移动元素数为：n+1

Eis=∑pix(n-i+1)i=1第２章线性表三、顺序表的插入53第二节顺序表当插入位置等概率时，pi=1/(n+1)，因此：n+1

Eis=∑[1/(n+1)]x(n-i+1)=n/2i=1顺序表插入操作的时间复杂度为O(n)第２章线性表四、顺序表的删除54第二节顺序表顺序表的删除操作是指将顺序表的第i个数据元素删除，即将长度为n的顺序表：(a1,…ai-1,ai,ai+1,…,an)

变成长度为n-1的顺序表：(a1,…ai-1,ai+1,…,an)第２章线性表四、顺序表的删除55第二节顺序表将第4个元素删除需要将最后元素n至第5元素(共7-4)都向前移一位置第２章线性表2534574809630123456725345748096316删除16i=401234567四、顺序表的删除56第二节顺序表第２章线性表StatusListDelete_Sq(Sqlist&L,inti,ElemTypee){if(i<1||i>L.length)returnERROR;p=&(L.elem[i-1]); //找到要删除的元素位置e=*p;q=L.elem+L.length–1; //找到最后一个元素位置for(++p;p<=q;++p)*(p-1)=*p; //左移--L.length; //表长减1returnOK;}//ListDelete_Sq四、顺序表的删除57第二节顺序表在顺序表中删除一个元素，需要向前移动元素个数为：n-i平均移动元素数为：n

Edl=∑

qix(n-i)i=1第２章线性表四、顺序表的删除58第二节顺序表当插入位置等概率时，qi=1/n，因此：n

Edl=∑[1/n]x(n-i)=(n-1)/2i=1顺序表删除操作的时间复杂度为O(n)第２章线性表五、顺序表的优缺点59第三节链表

优点：元素可以随机存取元素位置可用一个简单、直观的公式表示并求取

缺点：在作插入或删除操作时，需要移动大量元素第２章线性表一、链表60第二节线性链表链表是线性表的链式存储表示链表中逻辑关系相邻的元素不一定在存储位置上相连，用一个链(指针)表示元素之间的邻接关系线性表的链式存储表示主要有三种形式：线性链表循环链表双向链表第２章线性表二、线性链表61第二节线性链表线性链表的元素称为结点(node)结点除包含数据元素信息的数据域外，还包含指示直接后继的指针域每个结点，在需要时动态生成，在删除时释放第２章线性表datanext二、线性链表62第二节线性链表动态单独生成结点的线性链表也称单链表线性链表可由头指针惟一确定为了操作方便，有时在线性链表的第一个结点之前附设一个头结点，其数据域可以为空，也可以为线性链表的长度信息。第２章线性表4a1a2a3a4L三、线性链表的定义63第二节线性链表定义一个结点typedef

struct

LNode{

ElemType data; //数据域

struct

LNode *next; //后继指针}LNode,*LinkList;第２章线性表datanext四、找指定元素64第二节线性链表在线性链表中找第i个元素由于线性链表中元素的存储位置具有随机性，因此，只有从头结点开始，顺链一步步查找第２章线性表na1aianL……四、找指定元素65第二节线性链表StatusGetElem_L(LinkList&L,inti,ElemType&e){ //L为带头结点的单链表的头指针，e为返回值

p=L->next;j=1; //p指向第一个结点 while(p&&j<i){p=p->next;j++;} //顺指针查指 if(!p||j>i)returnERROR; //第i元素不存在 e=p->data; //取第i元素值 returnOK;}//GetElem_L第２章线性表na1aianL……四、找指定元素66第二节线性链表算法时间复杂度主要取决于while循环中的语句频度频度与被查找元素在单链表中的位置有关若1≤i≤n，则频度为i-1，否则为n因此时间复杂度为O(n)第２章线性表na1aianL……五、线性链表的插入67第二节线性链表在线性链表的第i-1元素与第i元素之间插入一个新元素第２章线性表ai-1ais……e插入前p…ai-1ais…e插入后ps->next=p->next;p->next=s;五、线性链表的插入68第二节线性链表StatusListInsert_L(LinkList&L,inti,ElemTypee){ //在带头结点的单链表L中第i个位置之前插入元素e p=L;j=0; while(p&&j<i-1){p=p->next;j++;} //寻找i-1结点 if(!p||j>i-1)returnERROR; s=(LinkList)malloc(sizeof(LNode); //生成新结点 s->data=e;s->next=p->next;p->next=s; //插入L中 returnOK;}//ListInsert_L第２章线性表五、线性链表的插入69第二节线性链表同样，算法时间复杂度主要取决于while循环中的语句频度频度与在线性链表中的元素插入位置有关因此线性链表插入的时间复杂度为O(n)第２章线性表六、线性链表的删除70第二节线性链表将线性链表的第i元素删除第２章线性表pai-1ai+1ai删除前ai-1aiai+1pq删除后p->next=p->next->next六、线性链表的删除71第二节线性链表StatusListDelete_L(LinkList&L,inti,ElemType&e){ //在带头结点的单链表L中，删除第i个位置的元素 p=L;j=0; while(p->next&&j<i-1){p=p->next;j++;} //寻找i结点 if(!p->next||j>i-1)returnERROR; q=p->next;p->next=q->next; //删除i结点

e=q->data;free(q); //取值并释放结点 returnOK;}//ListDelete_L第２章线性表六、线性链表的删除72第二节线性链表同样，算法时间复杂度主要取决于while循环中的语句频度频度与被删除元素在线性链表中的位置有关因此线性链表删除元素的时间复杂度为O(n)第２章线性表七、静态链表73第二节线性链表线性链表也可以采用静态数组实现与顺序表有两点不同：１、每个元素包括数据域和指针域２、元素的逻辑关系由指针确定第２章线性表DCFBAE…7592^83610411012345678910…数据指针七、静态链表74第二节线性链表与单链表区别：１、静态链表暂时不用结点，链成一个备用链表２、插入时，从备用链表中申请结点３、删除结点时，将结点放入备用链表第２章线性表一、循环链表75第三节循环链表循环链表是一种特殊的线性链表循环链表中最后一个结点的指针域指向头结点，整个链表形成一个环。第２章线性表na1aianL……二、查找、插入和删除76第三节循环链表在循环链表中查找指定元素，插入一个结点或删除一个结点的操作与线性链表基本一致差别仅在于算法中的循环条件不是p->next或p是否为空(^)，而是它们是否等于头指针(L)第２章线性表na1aianL……一、双向链表77第四节双向链表双向链表也是一种特殊的线性链表双向链表中每个结点有两个指针，一个指针指向直接后继(next)，另一个指向直接前驱(prior)第２章线性表priordatanext指向直接前驱指向直接后继二、双向循环链表78第四节双向链表双向循环链表中存在两个环(一个是直接后继环(红)，另一个是直接前驱环(蓝))第２章线性表非空表空表LL三、双向链表的定义79第四节双向链表定义一个双向链表的结点Typedef

struct

DuLNode{

ElemType data;

struct

DuLNode *prior;

struct

DuLNode *next;}DuLNode,*DuLinkList;第２章线性表priordatanext指向直接前驱指向直接后继对于任何一个中间结点有：p=p->next->priorp=p->prior->next四、双向链表的插入80第四节双向链表双向链表的插入操作需要改变两个方向的指针第２章线性表L314815pL31482515pss->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;四、双向链表的删除81第四节双向链表双向链表的删除操作需要改变两个方向的指针第２章线性表L314815pL3115p->prior->next=p->next;p->next->prior=p->prior;一、基于空间的比较82第五节顺序表与链表的比较存储分配的方式顺序表的存储空间是静态分配的链表的存储空间是动态分配的存储密度=结点数据本身所占的存储量/结点结构所占的存储总量顺序表的存储密度=1链表的存储密度<1第２章线性表二、基于时间的比较83第五节顺序表与链表的比较存取方式顺序表可以随机存取，也可以顺序存取链表必须顺序存取插入/删除时移动元素个数顺序表平均需要移动近一半元素链表不需要移动元素，只需要修改指针第２章线性表三、基于应用的比较84第五节顺序表与链表的比较如果线性表主要是存储大量的数据，并主要用于查找时，采用顺序表较好，如数据库如果线性表存储的数据元素经常需要做插入与删除操作，则采用链表较好，如操作系统中进程控制块(PCB)的管理，内存空间的管理等第２章线性表第三章

栈和队列数据结构深圳大学计算机系

蔡茂国一、栈86第一节栈栈是限定仅在表尾(top)进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top，表尾)，另一端称为栈底(bottom，表头)特点：后进先出(LIFO)第３章栈和队列a1topbottoman...进栈出栈二、栈的实现87第一节栈栈的存储结构主要有两种：1.顺序栈2.链式栈第３章栈和队列a1topbasean...进栈出栈top

^datanext…栈底栈顶一、顺序栈88第二节顺序栈顺序栈是栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。第３章栈和队列a1topbasean...进栈出栈二、顺序栈的定义89第二节顺表栈采用C语言中动态分配的一维数组表示顺序表第３章栈和队列#defineSTACK_INIT_SIZE100 //栈存储空间的初始分配量#defineSTACKINCREMENT10 //栈存储空间的分配增量Typedefstruct{

SElemType *base //存储空间基址

SElemType *top; //当前长度

int stacksize; //当前分配的存储容量(元素数)}SqStack;三、顺序栈的特性90第二节顺序栈top=0或top=base表示空栈base=NULL表示栈不存在当插入新的栈顶元素时,指针top+1删除栈顶元素时，指针top-1当top>stacksize时，栈满，溢出第３章栈和队列a1topbasean...进栈出栈四、顺序栈的主要操作91第二节顺序栈第３章栈和队列ADTStack{ 数据对象：D={ai|ai∈ElemSet,i=1,2,3,…,n} 数据关系：R={<ai-1,ai>|ai-1,ai∈D} 基本操作：InitStack(&S) //构造空栈

Push(&S,e) //进栈

Pop(&S,&e) //出栈

GetTop(S,&e) //取栈顶元素值

StackEmpty(S) //栈是否为空

}ADTStack五、创建顺序栈92第二节顺序栈第３章栈和队列StatusInitStack(SqStack&S){

S.base=(SElemType*)malloc(STACK_INIT_SIZE*

sizeof(SElemType)); if(!S.base)exit(OVERFLOW); //存储分配失败

S.top=S.base;

S.stacksize=STACK_INIT_SIZE; returnOK;}//InitStacktopbase

空栈六、进栈（插入新元素）93第二节顺序栈第３章栈和队列StatusPush(SqStack&S,SElemTypee){ if(S.top–S.base>=S.stacksize){ //栈满，追加存储空间

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCRMENT*sizeof(SElemType)); if(!S.base)exit(OVERFLOW);

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCRMENT;} *S.top++=e; returnOK;}//Pushtopbaseebae进栈topbaseba操作前七、出栈（删除元素）94第二节顺序栈第３章栈和队列StatusPop(SqStack&S,SElemType&e){

if(S.top==S.base)returnERROR; e=*--S.top; returnOK;}//Poptopbaseebae出栈topbaseeba操作前八、取栈顶元素95第二节顺序栈第３章栈和队列StatusGetTop(SqStackS,SElemType&e){

if(S.top==S.base)returnERROR; e=*(S.top-1); returnOK;}//GetToptopbaseebae进栈topbaseeba操作前一、数值转换96第三节栈的应用举例将十进制转换为其它进制(d)，其原理为：N=(N/d)*d+Nmodd例如：（1348)10=(2504)8，其运算过程如下：

N N/8Nmod8 1348 1684 168 21 0 21 2 5 2 0 2第３章栈和队列输出顺序计算顺序一、数值转换97第三节栈的应用举例voidconversion(){

InitStack(S); //创建新栈S

scanf(“%d”,N); //输入一个十进制数Nwhile(N){

Push(S,N%8); //将余数送入栈中N=N/8; //求整除数}while(!StackEmpty(S)){ //如果栈不空

Pop(S,e); //将栈中数出栈

printf("%d",e);}}//conversion第３章栈和队列二、行编辑程序98第三节栈的应用举例用户输入一行字符允许用户输入出差错，并在发现有误时，可以用退格符“#”及时更正假设从终端接受两行字符：

whli##ilr#e（s#*s)实际有效行为：

while(*s)第３章栈和队列二、行编辑程序99第三节栈的应用举例对用户输入的一行字符进行处理，直到行结束(“\n”)

ch=getchar(); //从终端输入一个字符 while(ch!=’\n’){

switch(ch){ case’#’:Pop(S,c); break; //仅当栈非空时退栈 default:Push(S,ch); break; //有效字符进栈 }

ch=getchar(); //从终端输入一个字符 }

将从栈底到栈顶的栈内字符传送到调用过程的数据区;第３章栈和队列三、迷宫求解100第三节栈的应用举例迷宫求解一般采用“穷举法”逐一沿顺时针方向查找相邻块（一共四块－东(右)、南(下)，西(左)、北(上)）是否可通，即该相邻块既是通道块，且不在当前路径上用一个栈来记录已走过的路径第３章栈和队列三、迷宫求解101第三节栈的应用举例举例第３章栈和队列#############三、迷宫求解（算法）第三节栈的应用举例设定当前位置为入口位置

do{若当前位置可通，则{

将该位置插入栈顶(Push)；若该位置是出口，则结束 否则切换当前位置的东邻方块为当前位置； }否则{ 若栈不空则｛ 如果栈顶位置的四周均不可通,则删除栈顶位置(Pop) 并重新测试新的栈顶位置 如果找到栈顶位置的下一方向未经探索，则将该方向 方块设为当前位置}}}while(栈不空)；找不到路径；第３章栈和队列四、表达式求值103第三节栈的应用举例表达式由操作数、运算符和界限符组成，它们皆称为单词操作数：常数或变量运算符：+,-,*,/等界限符：(,),#(表达式开始及结束符)第３章栈和队列四、表达式求值104第三节栈的应用举例设置两个栈：操作数栈（OPND）运算符栈（OPTR）第３章栈和队列四、表达式求值105第三节栈的应用举例运算符的优先级关系第３章栈和队列+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=出错)>>>>出错>>#<<<<<出错=新运算符运算符栈顶元素四、表达式求值（算法）第三节栈的应用举例置运算符栈(OPTR)和操作数栈(OPND)为空 ’#’插入OPTR栈； 取表达式第一个单词；

while(单词或OPTR栈顶元素不为’#’){ 若单词是操作数，则插入OPND栈顶，且取下一个单词 否则｛OPTR栈顶元素优先级与新运算符优先级关系为： 小于，则插入OPTR栈顶，取下一单词 等于，则删除OPTR栈顶元素，取下一单词 大于，则从OPND栈顶依次取出两个操作数，用从OPTR 栈顶取出的元素进行计算，结果插入OPND栈顶}}第３章栈和队列从栈顶取出元素，包括取值及删除栈顶元素两个过程一、队列107第四节队列队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。在队列中，允许插入的一端叫队尾（rear），允许删除的一端称为对头(front)。特点：先进先出(FIFO)第３章栈和队列a1

a2

a3

an出队入队队头队尾二、顺序队列108第四节队列顺序队列：采用一组地址连续的存储单元依次存储从队列头到队列尾的元素顺序队列有两个指针：队头指针front和队尾指针rear第３章栈和队列三、顺序队列的进队和出队原则109第四节队列进队时，新元素按rear指针位置插入，然后队尾指针增一，即rear=rear+1出队时，将队头指针位置的元素取出，然后队头指针增一，即front=front+1队头指针始终指向队列头元素队尾指针始终指向队列尾元素的下一个位置第３章栈和队列四、顺序队列的进队和出队举例110第四节队列第３章栈和队列frontrear空队列frontrearA,B,C,D进队ABCDfrontrearA退队BCDfrontrearB退队CDfrontrearE,F,G进队CDEFGCDEFGfrontrearH进队,溢出五、顺序队列存在的问题111第四节队列当队尾指针指向队列存储结构中的最后单元时，如果再继续插入新的元素，则会产生溢出当队列发生溢出时，队列存储结构中可能还存在一些空白位置（已被取走数据的元素）解决办法之一：将队列存储结构首尾相接，形成循环(环形)队列第３章栈和队列一、循环队列112第五节循环队列循环队列采用一组地址连续的存储单元将整个队列的存储单元首尾相连第３章栈和队列C0123456frontMAXQSIZE-1DEABCrear二、循环队列空与满113第五节循环队列front=rear，循环队列空(rear+1)%MAXQSIZE=front，循环队列满第３章栈和队列C0123456frontMAXQSIZE-1rear队列空CDEFGBCH0123456frontMAXQSIZE-1rear队列满三、循环队列定义114第五节循环队列#defineMAXQSIZE100Typedef

struct{

QElemType*base;

int front;

int rear;}SqQueue;第３章栈和队列CDEFC0123456frontbaserear三、循环队列插入元素115第五节循环队列StatusEnQueue(SqQueue&Q,QElemTypee){ if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队满

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE; returnOK;}第３章栈和队列CDEFGBCH0123456frontMAXQSIZE-1rear三、循环队列删除元素116第五节循环队列StatusDeQueue(SqQueue&Q,QElemTypee){ if(Q.rear==Q.front)returnERROR;//队空 e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE; returnOK;}第３章栈和队列C0123456frontrear一、链队列117第六节链队列链队列采用链表存储单元链队列中，有两个分别指示队头和队尾的指针。链式队列在进队时无队满问题，但有队空问题。第３章栈和队列datanextfrontrear二、链队列指针变化状况118第六节链队列链队列是链表操作的子集第３章栈和队列frontrearxy^元素y入队frontrearx^y元素x出队frontrear^空队列^第四章

串数据结构深圳大学计算机系

蔡茂国一、字符串（string）120第一节字符串字符串是n(≥0)个字符的有限序列，记作：

S=‘a1a2a3…an’其中，S是串名字‘a1a2a3…an’是串值

ai

是串中字符

n是串的长度(串中字符的个数)例如,S=“ShenzhenUniversity”第４章串二、字符串术语121第一节字符串空串：不含任何字符的串，串长度=0空格串：仅由一个或多个空格组成的串子串：由串中任意个连续的字符组成的子序列。主串：包含子串的串。如：A=’ShenzhenUniversity’B=’University’A为主串，B为子串。第４章串二、字符串术语122第一节字符串位置：字符在序列中的序号。子串在主串中的位置以子串第一个字符在主串中的位置来表示。串相等的条件：当两个串的长度相等且各个对应位置的字符都相等时才相等。模式匹配：确定子串在主串中首次出现的位置的运算

第４章串三、字符串与线性表的关系123第一节字符串串的逻辑结构和线性表极为相似，它们都是线性结构串中的每个字符都仅有一个前驱和一个后继第４章串三、字符串与线性表的关系124第一节字符串串与线性表又有区别，主要表现为：串的数据对象约定是字符集在线性表的基本操作中，以“单个元素”作为操作对象在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、在串的某个位置上插入一个子串等。第４章串一、定长顺序存储表示125第二节串的表示和实现用一组地址连续的存储单元存储字符序列如C语言中的字符串定义(以“\0”为串结束标志)charStr[MAXSTRLEN+1];定义了长度为MAXSTRLEN字符存储空间字符串长度可以是小于MAXSTRLEN的任何值（最长串长度有限制，多余部分将被截断）第４章串二、堆分配存储表示126第二节串的表示和实现在程序执行过程中，动态分配（malloc）一组地址连续的存储单元存储字符序列在C语言中，由malloc()和free()动态分配与回收的存储空间称为堆堆分配存储结构的串既有顺序存储结构的特点，处理方便,操作中对串长又没有限制,更显灵活第４章串三、链存储表示127第二节串的表示和实现采用链表方式存储串值每个结点中，可以存放一个字符，也可以存放多个字符第４章串Hell0^SSShend^a##一、求子串位置函数Index()128第三节串的匹配算法子串的定位操作通常称做串的模式匹配算法（穷举法）：从主串的指定位置开始，将主串与模式（要查找的子串）的第一个字符比较，1.若相等，则继续逐个比较后续字符；2.若不等，从主串的下一个字符起再重新和模式的字符比较第４章串一、求子串位置函数Index()129第三节串的匹配算法Int

Index(SstringS,SstringT,intpos){ //S为主串，T为模式，串的第0位置存放串长度；串采用顺序存储结构 i=pos;j=1; //从第一个位置开始比较 while(i<=S[0]&&j<=T[0]){ if(S[i]==T[j]){++i;++j;} //继续比较后继字符 else{i=i–j+2;j=1;} //指针后退重新开始匹配 } if(j>T[0])returni-T[0]; //返回与模式第一字符相等 elsereturn0; //匹配不成功 //的字符在主串中的序号}第４章串一、求子串位置函数Index()130第三节串的匹配算法在最好的情况下，除比较成功的位置外，其余位置仅需比较一次（模式第一个字符），其时间复杂度为：O(n+m)(n，m分别为主串和模式的长度)但在最坏的情况下，如模式为‘00000001’，主串为‘0000000000000000000000000000000001’,则每次模式的前7个0都要与主串逐一比较，因此，其时间复杂度为：O(n*m)第４章串二、KMP算法131第三节串的匹配算法是index函数的一种改进,由D.E.Knuth(克努特)－J.H.Morris(莫里斯)－V.R.Pratt(普拉特)发现当一趟匹配过程中出现字符比较不等(失配)时1.不需回溯i指针2.利用已经得到的“部分匹配”的结果3.将模式向右“滑动”尽可能远的一段距离(next[j])后，继续进行比较第４章串二、KMP算法(举例)132第三节串的匹配算法假设主串ababcabcacbab,模式abcac,改进算法的匹配过程如下 ↓i=3第一趟匹配 ababcabcacbab abc ↑j=3 ↓i=3----7第二趟匹配ababcabcacbab abcac ↑j=1 ↓i=7--10第三趟匹配 ababcabcacbab abcac ↑j=2第４章串二、KMP算法133第三节串的匹配算法假设主串为‘s1s2s3…sn’,模式串为‘p1p2p3…pm’若主串中第i个字符与模式串中第j个字符“失配”(si!=pj),需要与模式串中第k(k<j)个字符比较,则有以下关系成立：

‘p1p2…pk-1’=‘si-k+1si-k+2…si-1’而已经得到的“部分匹配”结果为：

‘pj-k+1pj-k+2…pj-1’=‘si-k+1si-k+2…si-1’第４章串二、KMP算法134第三节串的匹配算法从而有下式成立：

‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’上式是只依赖于模式串的关系式上式说明,在主串中第i个字符“失配”时,仅需与模式串中的第k个字符再开始比较（不需要回溯）第４章串二、KMP算法135第三节串的匹配算法或者换言之,在模式串中第j个字符“失配”时,模式串第k个字符再同主串中对应的失配位置(i)的字符继续进行比较

‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’k值可以在作串的匹配之前求出一般用next函数求取k值第４章串二、KMP算法(next函数)136第三节串的匹配算法next函数定义为： 0 当j=1时next[j]=max{k|1<k<j且‘p1…pk-1’=‘pj-k+1…pj-1’ 1 其它情况如k=2,则p1=pj-1(有1个字符相同)[除j=2外];k=3,则p1p2=pj-2pj-1(有2个字符相同);第４章串二、KMP算法(next函数举例)137第三节串的匹配算法现有模式串abcac,求其next值第４章串j12345模式串abcacnext[j]01112二、KMP算法(next函数举例)138第三节串的匹配算法现有模式串abaabacaca,求其next值第４章串j12345678910模式串abaabacacanext[j]0112234121二、KMP算法(利用next函数)139第三节串的匹配算法利用next函数,可写出KMP算法如下：1.令i的初值为pos,j的初值为12.While((i<主串长度)且(j<模式串长度)){(1).若j=0或者si=pj,则i++,j++(2).否则,j=next[j]} j=0表示第一个字符失配第４章串二、KMP算法(C语言实现)140第三节串的匹配算法Int

Index_KMP(SstringS,SstringT,intpos){

//S为主串，T为模式，串的第0位置存放串长度；串采用顺序存储结构 i=pos;j=1; //从第一个位置开始比较 while(i<=S[0]&&j<=T[0]){ if((j==0)||S[i]==T[j])){++i;++j;}//继续比较后继字符 elsej=next[j]; //模式串向右移 } if(j>T[0])returni-T[0]; //返回与模式第一字符相等 elsereturn0; //匹配不成功 //的字符在主串中的序号}第４章串二、KMP算法(时间复杂度)141第三节串的匹配算法Index_KMP()函数的时间复杂度为O(n)为了求模式串的next值,其算法与Index_KMP很相似,其时间复杂度为O(m)因此,KMP算法的时间复杂度为O(n+m)第４章串第六章

树与二叉树数据结构深圳大学计算机系

蔡茂国一、树的定义(Tree)143第一节树的概念与基本术语树是有n(n≥0)个结点的有限集合。如果n=0，称为空树；如果n>0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前驱)如果n>1，则除根以外的其它结点划分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。每个结点都有唯一的直接前驱，但可能有多个后继第６章树与二叉树一、树的定义(举例)144第一节树的概念与基本术语其中：A是根；其余结点分成三个互不相交的子集，T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树第６章树与二叉树A只有根结点的树ACGBDEFKLHMIJ有13个结点的树二、树的基本术语145第一节树的概念与基本术语结点：包含一个数据元素及若干指向其子树的分支结点的度：结点拥有的子树数叶结点：度为0的结点[没有子树的结点]分支结点：度不为0的结点[包括根结点]，也称为非终端结点。除根外称为内部结点第６章树与二叉树1层2层4层3层Height=4ACGBDEFKLHMIJ二、树的基本术语146第一节树的概念与基本术语孩子：结点的子树的根[直接后继，可能有多个]双亲：孩子的直接前驱[最多只能有一个]兄弟：同一双亲的孩子子孙：以某结点为根的树中的所有结点祖先：从根到该结点所经分支上的所有结点第６章树与二叉树1层2层4层3层Height=4ACGBDEFKLHMIJ二、树的基本术语147第一节树的概念与基本术语层次：根结点为第一层，其孩子为第二层，依此类推深度：树中结点的最大层次森林：互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林第６章树与二叉树1层2层4层3层Height=4ACGBDEFKLHMIJ一、二叉树(BinaryTree)148第二节二叉树二叉树是一种特殊的树每个结点最多有２棵子树二叉树的子树有左右之分第６章树与二叉树LLRR空树只有根只有左子树只有右子树有左右子树二、二叉树性质１149第二节二叉树在二叉树的第i层上至多有2i-1个结点证明：1.i=1,只有一个根节点，因此2i-1=20=12.设第i-1层上，以上性质成立，即第i-1层至多有2(i-1)-1结点。由二叉树的定义可知，任何结点的度小于2，因此，第i层上的结点数最多为第i-1层上的两倍，即2*2i-2=2i-1第６章树与二叉树三、二叉树性质２150第二节二叉树深度为k的二叉树至多有2k-1个结点证明：1.由性质１，已知第i层上结点数最多为2i-1

k2.∑2i-1=2k-1

i=1第６章树与二叉树四、二叉树性质３151第二节二叉树如果二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1证明：1.设n1为度为1的结点，则总结点数=n0+n1+n22.设B为二叉树的分支数，除根结点外，每个结点有且只有一个分支，因此n=B+13.每个分支皆由度为1或2的结点发出，B=n1+2n24.n=B+1=(n1+2n2)+1=n0+n1+n2，因此n0=n2+1第６章树与二叉树五、满二叉树152第二节二叉树一个深度为k且有2k-1个结点的二叉树每层上的结点数都是最大数可以自上而下、自左至右连续编号第６章树与二叉树621754389101113141512六、完全二叉树153第二节二叉树当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树叶子结点只在最大两层上出现左子树深度与右子树深度相等或大１第６章树与二叉树621754389101112六、完全二叉树(性质４)154第二节二叉树具有n个结点的完全二叉树,其深度为log2n+1设k为深度，由二叉树性质２，已知2k-1-1

<n≤2k-1即2k-1≤n<2k即k=log2n+1第６章树与二叉树621754389101112六、完全二叉树(性质５)155第二节二叉树在完全二叉树中，结点i的双亲为i/2结点i的左孩子LCHILD(i)=2i结点i的右孩子RCHILD(i)=2i+1第６章树与二叉树6217543891011122i+2i2i+32i+12ii+1i/2七、二叉树的顺序存储结构156第二节二叉树用一组连续的存储单元依次自上而下,自左至右存储结点第６章树与二叉树完全二叉树的顺序表示一般二叉树的顺序表示123456789101234056780091012489105673912364789105七、二叉树的链式存储结构157第二节二叉树1.二叉链表采用数据域加上左、右孩子指针第６章树与二叉树datalChildrChildlChilddatarChild七、二叉树的链式存储结构158第二节二叉树1.二叉链表(举例)二叉树（左）及其二叉链表（右）第６章树与二叉树ABCDFErootABCDFEroot