数据结构复习课件

数据结构复习11、战争满足了，或曾经满足过人的好斗的本能，但它同时还满足了人对掠夺，破坏以及残酷的纪律和专制力的欲望。——查·埃利奥特12、不应把纪律仅仅看成教育的手段。纪律是教育过程的结果，首先是学生集体表现在一切生活领域——生产、日常生活、学校、文化等领域中努力的结果。——马卡连柯(名言网)13、遵守纪律的风气的培养，只有领导者本身在这方面以身作则才能收到成效。——马卡连柯14、劳动者的组织性、纪律性、坚毅精神以及同全世界劳动者的团结一致，是取得最后胜利的保证。——列宁摘自名言网15、机会是不守纪律的。——雨果数据结构复习数据结构复习11、战争满足了，或曾经满足过人的好斗的本能，但它同时还满足了人对掠夺，破坏以及残酷的纪律和专制力的欲望。——查·埃利奥特12、不应把纪律仅仅看成教育的手段。纪律是教育过程的结果，首先是学生集体表现在一切生活领域——生产、日常生活、学校、文化等领域中努力的结果。——马卡连柯(名言网)13、遵守纪律的风气的培养，只有领导者本身在这方面以身作则才能收到成效。——马卡连柯14、劳动者的组织性、纪律性、坚毅精神以及同全世界劳动者的团结一致，是取得最后胜利的保证。——列宁摘自名言网15、机会是不守纪律的。——雨果数据结构课程目录第一章绪论第二章线性表第三章栈和队列第四章串第五章树第六章图第七章查找第八章排序第九章递归3/24/202121数据结构的基本概念数据结构可描述为Group=（D，R）R反映的是数据的逻辑结构不考虑数据在计算机中的具体存储方式。3/24/20213数据结构复习11、战争满足了，或曾经满足过人的好斗的本能，但数据结构复习课件数据结构复习课件数据结构复习课件数据结构复习课件1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素1

14001346元素4∧…….……..…….

1400

元素21536…….……..…….1536元素31346

链式存储

h12/16/202261536元素21400元素11346元素3∧元素41345

线性表的存储结构—-顺序表、线性链表(单链表)1.顺序存储结构(可用C语言的一维数组实现) 逻辑上相邻—物理地址相邻 实现随机存取在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低特点：只有数据域，存储空间利用率高，做插入、删除时需移动大量元素。空间估计不明时，按最大空间分配。12/16/20227

线性表的存储结构—-顺序表、线性链表(单链表)12/10/2、线性表的链式存储结构

将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。

数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。特点：插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。

2-1单链表的插入运算

2-2单链表的删除运算datalink12/16/202282、线性表的链式存储结构datalink12/10/20∧anaia1a2ai-1xLStatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j};//寻找第i-1个结点if(!pj>i-1)returnERROR;//插入位置错s=(structLNode*)malloc(sizeof(structLNode));//生成新结点

s->data=x;s->next=p->next;p->next=s;returnOK;}babaxPP单链表的插入运算S12/16/20229∧anaia1a2ai-1xLStatusListInseai-1a1aiai+1LpqStatusListDelete_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}//寻找第I个结点，并使p指向其前驱if(!(p->next)j>i-1)returnERROR;//删除错

q=p->next;p->next=q->next;free(q);//删除并释放结点returnOK;}单链表的删除运算12/16/202210ai-1a1aiai+1LpqStatusListDele循环链表(circularlinkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p->link=NULL循环链表p或p->link=Hhh空表12/16/202211循环链表(circularlinkedlist)hh空表双向链表（doublelinkedlist）单链表具有单向性的缺点结点定义typedefstructnode{datatypeelement;structnode*prior,*next;}JD;priorelementnextL空双向循环链表：非空双向循环链表：LABbcapp->prior->next=p=p->next->proir;12/16/202212双向链表（doublelinkedlist）typedebcaPvoiddel_dulist(JD*p){p->prior->next=p->next;

p->next->prior=p->prior;free(p);}删除算法描述p->prior->next=p->next;p->next->prior=p->prior;12/16/202213bcaPvoiddel_dulist(JD*p)删除算法voidins_dulist(JD*p,intx){JD*s;s=(JD*)malloc(sizeof(JD));s->element=x;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;}算法描述算法评价：T(n)=O(1)xSbaP插入12/16/202214voidins_dulist(JD*p,intx)算法线性表的应用：应用最广的数据结构。·高级语言中的数组；··电话号码查询系统（可采用顺序表或单链表结构）；·各种事务处理（各种表格均采用顺序表和线性链表结构）12/16/202215线性表的应用：应用最广的数据结构。12/10/2022153栈和队列3.1栈3.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表

(LIFO/FILO)。栈顶（top)：允许插入和删除的一端；栈底（bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底12/16/2022163栈和队列a1a2….an进栈出栈栈栈的存储结构顺序栈实现：一维数组s[M]入栈算法出栈算法s[top]=x;return(++top);*q=s[--top];12/16/202217栈的存储结构入栈算法出栈算法s[top]=x;*q=s[--入栈算法出栈算法^…...栈底toptopxptop^…...栈底topq链栈p->data=x;p->link=top;top=p;q=top;*p=top->data;top=top->link;free(q);12/16/202218入栈算法出栈算法^…...栈底toptop栈的应用(1)

过程的嵌套

(2)

递归算法

(3)表达式的计算(4)地图四染色问题12/16/202219栈的应用(2)

递归算法(3)表达式的计队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；4队列（一种特殊的线性结构，限定在一端插入，一端删除）4.1队列的定义与运算

a1,

a2,

a3,

a4,…………

an-1,

an队列示意图队头队尾先进先出FIFO12/16/202220队列的主要运算（1）设置一个空队列；4队列（一种特殊的4.2队列的存储结构（1）顺序存储结构(a)线性队列e4e3

e3e2e1

3210(a)(b)(c)rear=front（队空）rearfront

队满rear=4front12/16/2022214.2队列的存储结构（1）顺序存储结构(a)线性队列(b)循环队列

rearfront

0123(3)队空

rear(1)一般情况front

0123e4e3

(2)队满reare3

e40123fronte5队满条件：(Q.rear+1)%MAX=Q.front显示循环队列中入队和出队时的指针变换过程12/16/202222(b)循环队列rearfront入队算法：出队算法：rear=(rear+1)%M;sq[rear]=x;front=(front+1)%M;*q=sq[front];12/16/202223入队算法：出队算法：rear=(rear+1)%M;fron链队列入队算法出队算法p->data=x;p->link=NULL;rear->link=p;s=front->link;front->link=s->link;if(s->link==NULL)rear=front;x=s->data;

free(s);12/16/202224链队列入队算法出队算法p->data=x;s=front->3.写出下列程序段的输出结果Voidmain(){SqStackS;//定义栈charx,y;InitStack(S);//初始化栈x=‘c’;y=‘k’;Push(S,x);Push(S,‘a’);Push(S,y);Pop(S,x);Push(S,‘t’);Push(S,x);Pop(S,x);Push(S,‘s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};

….....…..…cakprintf(x);}…..…ca

…ca

tk...ca

t

...….ca

tsstack12/16/2022253.写出下列程序段的输出结果….....…..…ca4.Voidalgo(SqQueue&Q){StackS;intd;InitStack(S);while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);}while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);}}...0123abQ.front Q.rear...0123Q.front Q.rearab...0123

baQ.front Q.rear12/16/2022264....0123abQ.front Q.rear..5数组（线性表的推广）5．1二维数组的定义a1a11a12……..a1n

a2a21a22……..a2n

amam1am2……..amn

….ai=(ai1,

ai2,

……..

,

ain)(1<=i<=n)数组的运算主要是存取元素、修改相应的元素。12/16/2022275数组（线性表的推广）5．1二维数（1）

按行优先顺序存放（2）

按列优先顺序存放5．3矩阵的压缩存储1、

特殊矩阵：值相同元素或非零元素的分布具有一定规律。（1）

下三角阵（2）

三对角阵2、

稀疏矩阵：元素分布无规律。（1）

顺序存储结构——三元组表示法（3）

数组的链接存储结构——十字链表结构5．2数组的顺序存储结构12/16/2022285．2数组的顺序存储结构12/10/202228

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0A=按行优先存放{a11,

a21,

a22,

a31,

a32,…,

an1,

an2,…,

ann}

前i-1行非零元素个数∑R=i(i-1)2loc(aij)=loc(a11)+[(+(j-1)]S

i(i-1)2i-1R=1下三角阵12/16/202229a1100

a11

a120

…………..0

a21a22

a23

0

………...00

0

……an-1,n-2an-1.n-1an-1,n………..A=

0

a21a22

a23

0

…..00

0

…………….an,n-1ann.按行优先存放{a11,

a12,

a21,

a22,

a23,a32,a34,

…an,n-1,

ann}

loc(aij)=loc(a11)+2(i-1)+(j-1)

三对角阵12/16/202230a11a120

7000150

0-40000

-2000021000-100M=2164-214-143-4221551711列行值顺序存储结构——三元组表示法12/16/2022317000

7000150

0-40000

-2000021

000-100M=22-4∧∧1515∧∧41-2∧4621∧∧11734-1∧∧^ijedownright12/16/2022327000结点（Node）：树中的元素，包含数据项及若干指向其子树的分支。结点的度（Degree）：结点拥有的子树数。叶子（Leaf）：度为零的结点，也称端结点。孩子（Child）：结点子树的根称为该结点的孩子结点。兄弟（Sibling）：同一双亲的孩子。双亲（Parent）：孩子结点的上层结点，称为这些结点的双亲深度（Depth)：树中结点的最大层次数。森林（Forest）：M棵互不相交的树的集合。6树12/16/2022336树12/10/2022336.2二叉树（BinaryTree）1、二叉树的定义及其性质

(1)二叉树的定义(a)空二叉树(b)仅有跟结点(c)(d)(e)(2)二叉树的性质

二叉树的基本性质：A、

二叉树的第i层上至多有2i-1（i1）个结点。B、

深度为h的二叉树中至多含有2h-1个结点。C、

若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1二叉数的五种基本形态ABCDEF一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。12/16/2022346.2二叉树（BinaryTree）1、二叉树的定（3）满二叉树423156789101112131415（4）完全二叉树842315679101112完全二叉树423156789101112非完全二叉树特点：每一层上的结点数都是最大结点数。完全二叉树：指深度为k的，有n个结点的，且每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。12/16/202235（3）满二叉树423156789101112131415（42、二叉树的存储结构

(2)链式存储结构FEDCBA1514131211109876543210T[16]若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。ABcFED

●●●●●●●●●124

8

91011563712131415(1)顺序存储结构(1)顺序存储结构2h-1=24-1=15用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。12/16/2022362、二叉树的存储结构(2)链式存储结构FEDCBA1(2)链式存储结构：每个结点由数据域、左指针域和右指针域组成。rchildDatalchild^ADB^C^^E^^F^图2-5一般二叉树的二叉链表结构12/16/202237(2)链式存储结构：每个结点由数据域、左指针域和6.3树的存储结构双亲表示法孩子表示法带双亲的孩子链表孩子兄弟表示法（二叉树表示法）多重链表表示法12/16/2022386.3树的存储结构12/10/2022383、将树和森林转换为二叉树（1）树转换为二叉树方法：·对每个孩子进行自左至右的排序；·在兄弟之间加一条连线；·对每个结点，除了左孩子外，去除其与其余孩子之间的联系；·以根结点为轴心，将整个树顺时针转45度。

12/16/2022393、将树和森林转换为二叉树12/10/202239

I

A

B

C

DEF

G

H(b)

A

B

CDE

G

HFI(a)树转换为二叉树ABEFCDGHI(d)ABCDEFGHI(c)12/16/202240IABCDEFGH(b)ABCDE

（2）

森林转换为二叉树ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：·将各棵树分别转成二叉树；·把每棵数的根结点用线连起来；·以第一棵数的根结点作为二叉树的根结点，按顺时针方向旋转。12/16/202241（2）

森林转换为二叉树ADCBEFHIGJEFAD将二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI12/16/202242将二叉树转换成树ABCDEFGHIABCDEFGHIABCD5.4树和二叉树的遍历树的遍历遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列常用方法先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点12/16/2022435.4树和二叉树的遍历12/10/202243ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO12/16/202244ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：二叉树的遍历方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL12/16/202245二叉树的遍历DLRLDR、LRD、DLR12/10/2022（2）给定先（后）序遍历和中序遍历，可唯一的得到一棵二叉树ADBCT1T2T3ABDCBDACDBCA12/16/202246（2）给定先（后）序遍历和中序遍历，可唯一的得到一棵二叉2.5.3哈夫曼树及其应用1、哈夫曼树（最优树）

带权路径长度最短的树结点带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中叶子结点带权路径长度之和。记作：其中：Wk为树中每个叶子结点的权；

Lk为每个叶子结点到根的路径长度WPL最小的二叉树就称作最优二叉树或哈夫曼树。12/16/2022472.5.3哈夫曼树及其应用12/10/2022abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=351、哈夫曼树（最优树）

公式：12/16/202248abcd7524WPL=7*2+5*2+2*2+4*2=36675cd(b)11b57cd(c)18a711cdb5624(d)abcd7524(a)2、哈夫曼树的构造12/16/202249675cd(b)11b57cd(c)18a711cdb562146833442200001111T;ACS例2：哈夫曼树用于电文编码要传输的电文是{CAS；CAT；SAT；AT}要传输的字符集是D={C，A，S，T，；}每个字符出现的频率是W={2，4，2，3，3}各字符编码是T；ACS

000110110111上述电文编码：1101011101110100001111100001100012/16/202250146833442200001111T;ACS例2：哈夫曼树线索二叉树定义：前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~线索：指向前驱或后继结点的指针称为~线索二叉树：加上线索的二叉链表表示的二叉树叫~线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~实现在有n个结点的二叉链表中必定有n+1个空链域在线索二叉树的结点中增加两个标志域lt:若lt=0,lc域指向左孩子；若lt=1,lc域指向其前驱rt:若rt=0,rc域指向右孩子；若rt=1,rc域指向其后继结点定义：typedefstructnode{intdata;intlt,rt;structnode*lc,*rc;}JD;lcltdatartrc12/16/202251线索二叉树typedefstructnodelcABCDEABDCET先序序列：ABCDE先序线索二叉树00001111^1112/16/202252ABCDEAB二叉排序树定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值它的左、右子树也分别为二叉排序树12/16/202253二叉排序树12/10/202253插入算法例{10，18，3，8，12，2，7，3}1010181018310183810183812101838122101838122710183812273中序遍历二叉排序树可得到一个关键字的有序序列12/16/202254插入算法例{10，18，3，8，12，2，72.6图图是一种非线性的数据结构，结点之间的关系可以是任意的。图中任意两个元素之间都可能相关。图的存储结构（1）图的邻接矩阵表示法表示顶点间相邻关系的矩阵。有向：从一个结点到另一个结点有弧为1，否则为0。无向：有边连接则为1，否则为0。（2）图的邻接表表示法在边少的情况下，用邻接表比邻接矩阵节省存储空间。12/16/2022552.6图12/10/202255V1V3V2V4V1V3V2V4

V1V2V3V4

V1

0010

V20001

V30101

V41000

V1V2V3V4

V1

0111

V21011

V31100

V41100图的邻接矩阵表示法无向图中某顶点的度数为矩阵中对应该顶点的行或列的1的个数有向图中某顶点的出度为矩阵中对应该顶点的行的1的个数有向图中某顶点的入度为矩阵中对应该顶点的列的1的个数12/16/202256V1V3V2V4V1V3V2V4V1V1V3V2V4V1V3V2V4432121∧113∧4∧4∧2∧1∧3∧44321图的邻接表表示法∧412/16/202257V1V3V2V4V1V3V2V4432121∧11V1V3V2V4∧2∧4∧343∧1∧1有向图的逆邻接表表示法12/16/202258V1V3V2V4∧2∧4∧343∧1∧1有向图的逆邻无向图的邻接多重表表示法V1V3V2V44321221231241∧∧242∧∧12/16/202259无向图的邻接多重表表示法V1V3V2V443212深度优先遍历(DFS)V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1V2V4V8V5V6V3V7深度遍历：V1V2V4V8V5V6V3V712/16/202260深度优先遍历(DFS)V1V2V4V5V3V7V6V8例例V广度优先遍历(BFS)V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1V2V3V4V5V6V7V8广度遍历：V1V2V3V4V5V6V7V812/16/202261广度优先遍历(BFS)V1V2V4V5V3V7V6V8例例V构造最小生成树方法普里姆(Prim)算法算法思想：设N=(V,{E})是连通网，TE是N上最小生成树中边的集合从任一顶点出发，将此点包含在生成树里在这些一个顶点已在生成树里而另一顶点未在生成树里的边中，找一条代价最小的边将此边和那个顶点包含进生成树重复上述操作，每次加一个顶点和一个代价最小的边。直至所有的顶点包含进去，则得到最小生成树拓扑排序:一个AOV网的拓扑序列不是唯一的12/16/202262构造最小生成树方法拓扑排序:一个AOV网的拓扑序列不是唯一的13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329最短路径迪杰斯特拉(Dijkstra)算法12/16/2022631313终点2.7查找2．7．1顺序查找思想：对给定的一关键字K，从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到其关键字等于K的记录或到达表的另一端。12/16/2022642.7查找思想：对给定的一关键字K，从线性表的一端开始，逐顺序查找的算法：intseqsrch(JDr[],intn,intk){inti=n;r[0].key=k;while(r[i].key!=k)i--;return(i);}2560308040201080012345672560308040201001234567256030804020109001234567（a）初态(b)K=80(c)K=90(returni=0)length=7(returni=4)12/16/202265顺序查找的算法：intseqsrch(JDr[],int2．7．2折半查找思想：先确定待查找记录所在的范围，然后逐步缩小范围，直到找到或确认找不到该记录为止。必须在具有顺序存储结构的有序表中进行。12/16/2022662．7．2折半查找12/10/202266(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowmidhigh(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowmidhighmidlowhighmidmidlowhigh

折半查找例：highlow(08,14,23,37,46,55,68,79,91)midlowhigh12/16/202267(08,14,23,IntSearch_Bin(SSTableST,KeyTypek){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(ST.elem[mid]==k)returnmid;elseif(k<ST.elem[mid])high=mid-1;//在前半区间继续查找elselow=mid+1;}return0;}12/16/202268IntSearch_Bin(SSTableST,K2.7.3散列（HSAE）查找

根据关键字的值，利用某个函数直接计算出元素所在的位置。这函数称为“哈希函数”，能用散列技术进行查找的表称为散列表（哈希表）。1、

基本概念——哈希函数，冲突哈希表技术的主要目标是提高查找效率，即缩短查表和填表的时间。冲突是指存在多个关键字，能计算出相同的存储位置。312726211916130911050102H(K)=int(K/3)+1121110987654321表项序号12/16/2022692.7.3散列（HSAE）查找312726211916133、

处理冲突的方法

（1）

开放定址法

设散列函数H（k）=kMODm（m为表长,若发生冲突，设发生冲突的地址为p

,则沿着一个探查序列逐个探查，那么，探查的地址序列为P+1,P+2,P+3,…,m-1,0,1,…,P-1.

38291760012345678910m=11)(2)链地址法链地址法解决冲突的方法：把具有相同散列地址的键值存放在同一个链表中，称为同义词链表。12/16/2022703、

处理冲突的方法设散列函数H（k）=kMODm例一组关键字为（21，14，19，58，65，32，72）

H(K)=KMOD11∧

∧

∧∧∧∧∧0123456789102165∧32∧19∧7214∧5812/16/202271例一组关键字为（21，14，19，58，排序的重点是各种排序方法的各趟排序结果以及比较次数和移动次数12/16/202272排序的重点是各种排序方法的各趟排序结果以及比较次数和移动次数待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

直接插入排序示例2.8.2插入排序直接插入、折半插入1、直接插入排序思想:从数组中的第2号元素开始,顺序从数组中抽取元素并将该元素插入到其左端已排好序的数组的适当位置上.12/16/202273待排元素序列：[53]2736156例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42

lowmidhigh[1527365369]42

lowhigh

mid[1527365369]42

highlow[152736425369]2、折半插入排序折半插入排序在寻找插入位置时，利用折半查找的原理寻找插入位置,不是逐个比较。12/16/202274例：有6个记录，前5个已排序的基础上，对第6个记录排序。2voidBinsertSort(Sqlist&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//r[0]作为监视哨low=1;high=i-1;

While(low<=high){m=(low+high)/2;if(L.r[0].key<L.r[m].key)high=m-1;//插入点在低半区elselow=m+1;}//whilefor(j=i-1;j>=high+1;

j)L.i[j+1]=L.r[j];//记录后移L.r[low]=L.r[0];//插入}for}//折半插入排序12/16/202275voidBinsertSort(Sqlist&L){12取d3=1三趟分组：1327485544938659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分组：49

38

65

97

76

13

27

48

55

4取d2=3二趟分组：13

27

48

55

4

49

38

65

97

76希尔排序(缩小增量法)12/16/202276取d3=11327485542.8.3选择排序

简单选择排序、堆排序。1、简单选择排序思想：首先从1-n个元素中选出关键字最小的记录交换到第一个位置上。然后从第2个到第n个元素中选出次小的记录交换到第2个位置上，依次类推。初态83916839168391683916ijkijkijkijk1

3986互换ijk1

3986ikj1

3986ikj第一趟第二趟1

3986ikj第三趟12/16/2022772.8.3选择排序初态8

2

堆排序也是一种选择排序。是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。

A、堆的示例

897624331510112536497856(a):堆顶元素取最大值(b):堆顶元素取最小值B、实现堆排序需解决两个问题：

（1）如何由一个无序序列建成一个堆？（2）输出堆顶元素后，如何将剩余元素调整成一个新的堆？12/16/202278

2

堆排序也是一种选择排序。是具有特定条件的顺序2.8.4交换排序1、冒泡排序4936416511第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始关键字783665364156364165413641561178363641491156492525251149495611111125252525思想：小的浮起，大的沉底。12/16/2022792.8.4交换排序4936416511第第第第第第2、快速排序三次交换[186]23[6752]//完成一趟排序后分别进行快速排序有序序列618235267初始序列235266718一次交换1852667２３二次交换18２３66752keylowhighlowhighlowhighhigh12/16/2022802、快速排序三次交换[12.8.5归并排序初始序列[23][52][67][6][18][10]一趟归并后[2352][667][1018]二趟归并后[6235267][1018]三趟归并后[61018235267]归并排序示例12/16/2022812.8.5归并排序初始序列51、天下之事常成于困约，而败于奢靡。——陆游

52、生命不等于是呼吸，生命是活动。——卢梭

53、伟大的事业，需要决心，能力，组织和责任感。——易卜生

54、唯书籍不朽。——乔特

55、为中华之崛起而读书。——周恩来谢谢！51、天下之事常成于困约，而败于奢靡。——陆游

52、数据结构复习11、战争满足了，或曾经满足过人的好斗的本能，但它同时还满足了人对掠夺，破坏以及残酷的纪律和专制力的欲望。——查·埃利奥特12、不应把纪律仅仅看成教育的手段。纪律是教育过程的结果，首先是学生集体表现在一切生活领域——生产、日常生活、学校、文化等领域中努力的结果。——马卡连柯(名言网)13、遵守纪律的风气的培养，只有领导者本身在这方面以身作则才能收到成效。——马卡连柯14、劳动者的组织性、纪律性、坚毅精神以及同全世界劳动者的团结一致，是取得最后胜利的保证。——列宁摘自名言网15、机会是不守纪律的。——雨果数据结构复习数据结构复习11、战争满足了，或曾经满足过人的好斗的本能，但它同时还满足了人对掠夺，破坏以及残酷的纪律和专制力的欲望。——查·埃利奥特12、不应把纪律仅仅看成教育的手段。纪律是教育过程的结果，首先是学生集体表现在一切生活领域——生产、日常生活、学校、文化等领域中努力的结果。——马卡连柯(名言网)13、遵守纪律的风气的培养，只有领导者本身在这方面以身作则才能收到成效。——马卡连柯14、劳动者的组织性、纪律性、坚毅精神以及同全世界劳动者的团结一致，是取得最后胜利的保证。——列宁摘自名言网15、机会是不守纪律的。——雨果数据结构课程目录第一章绪论第二章线性表第三章栈和队列第四章串第五章树第六章图第七章查找第八章排序第九章递归3/24/202121数据结构的基本概念数据结构可描述为Group=（D，R）R反映的是数据的逻辑结构不考虑数据在计算机中的具体存储方式。3/24/20213数据结构复习11、战争满足了，或曾经满足过人的好斗的本能，但数据结构复习课件数据结构复习课件数据结构复习课件数据结构复习课件1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素1

14001346元素4∧…….……..…….

1400

元素21536…….……..…….1536元素31346

链式存储

h12/16/2022881536元素21400元素11346元素3∧元素41345

线性表的存储结构—-顺序表、线性链表(单链表)1.顺序存储结构(可用C语言的一维数组实现) 逻辑上相邻—物理地址相邻 实现随机存取在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低特点：只有数据域，存储空间利用率高，做插入、删除时需移动大量元素。空间估计不明时，按最大空间分配。12/16/202289

线性表的存储结构—-顺序表、线性链表(单链表)12/10/2、线性表的链式存储结构

将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。

数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。特点：插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的值即可。

2-1单链表的插入运算

2-2单链表的删除运算datalink12/16/2022902、线性表的链式存储结构datalink12/10/20∧anaia1a2ai-1xLStatusListInsert_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p&&j<i-1){p=p->next;++j};//寻找第i-1个结点if(!pj>i-1)returnERROR;//插入位置错s=(structLNode*)malloc(sizeof(structLNode));//生成新结点

s->data=x;s->next=p->next;p->next=s;returnOK;}babaxPP单链表的插入运算S12/16/202291∧anaia1a2ai-1xLStatusListInseai-1a1aiai+1LpqStatusListDelete_L(LinkList&L,inti,ElemTypex){p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}//寻找第I个结点，并使p指向其前驱if(!(p->next)j>i-1)returnERROR;//删除错

q=p->next;p->next=q->next;free(q);//删除并释放结点returnOK;}单链表的删除运算12/16/202292ai-1a1aiai+1LpqStatusListDele循环链表(circularlinkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p->link=NULL循环链表p或p->link=Hhh空表12/16/202293循环链表(circularlinkedlist)hh空表双向链表（doublelinkedlist）单链表具有单向性的缺点结点定义typedefstructnode{datatypeelement;structnode*prior,*next;}JD;priorelementnextL空双向循环链表：非空双向循环链表：LABbcapp->prior->next=p=p->next->proir;12/16/202294双向链表（doublelinkedlist）typedebcaPvoiddel_dulist(JD*p){p->prior->next=p->next;

p->next->prior=p->prior;free(p);}删除算法描述p->prior->next=p->next;p->next->prior=p->prior;12/16/202295bcaPvoiddel_dulist(JD*p)删除算法voidins_dulist(JD*p,intx){JD*s;s=(JD*)malloc(sizeof(JD));s->element=x;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;}算法描述算法评价：T(n)=O(1)xSbaP插入12/16/202296voidins_dulist(JD*p,intx)算法线性表的应用：应用最广的数据结构。·高级语言中的数组；··电话号码查询系统（可采用顺序表或单链表结构）；·各种事务处理（各种表格均采用顺序表和线性链表结构）12/16/202297线性表的应用：应用最广的数据结构。12/10/2022153栈和队列3.1栈3.1.1栈的定义栈：限定只能在表的一端进行插入和删除的特殊的线性表

(LIFO/FILO)。栈顶（top)：允许插入和删除的一端；栈底（bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底12/16/2022983栈和队列a1a2….an进栈出栈栈栈的存储结构顺序栈实现：一维数组s[M]入栈算法出栈算法s[top]=x;return(++top);*q=s[--top];12/16/202299栈的存储结构入栈算法出栈算法s[top]=x;*q=s[--入栈算法出栈算法^…...栈底toptopxptop^…...栈底topq链栈p->data=x;p->link=top;top=p;q=top;*p=top->data;top=top->link;free(q);12/16/2022100入栈算法出栈算法^…...栈底toptop栈的应用(1)

过程的嵌套

(2)

递归算法

(3)表达式的计算(4)地图四染色问题12/16/2022101栈的应用(2)

递归算法(3)表达式的计队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；4队列（一种特殊的线性结构，限定在一端插入，一端删除）4.1队列的定义与运算

a1,

a2,

a3,

a4,…………

an-1,

an队列示意图队头队尾先进先出FIFO12/16/2022102队列的主要运算（1）设置一个空队列；4队列（一种特殊的4.2队列的存储结构（1）顺序存储结构(a)线性队列e4e3

e3e2e1

3210(a)(b)(c)rear=front（队空）rearfront

队满rear=4front12/16/20221034.2队列的存储结构（1）顺序存储结构(a)线性队列(b)循环队列

rearfront

0123(3)队空

rear(1)一般情况front

0123e4e3

(2)队满reare3

e40123fronte5队满条件：(Q.rear+1)%MAX=Q.front显示循环队列中入队和出队时的指针变换过程12/16/2022104(b)循环队列rearfront入队算法：出队算法：rear=(rear+1)%M;sq[rear]=x;front=(front+1)%M;*q=sq[front];12/16/2022105入队算法：出队算法：rear=(rear+1