【文档说明】C语言数据结构课件.ppt，共(94)页，1.580 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-44605.html

以下为本文档部分文字说明：

ITEducation&TrainingDate:24November2022数据结构ITEducation&TrainingDate:24November2022第一部分数据结构基础知识ITEducati

on&TrainingDate:24November2022数据结构•数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等等的学科。ITEducation&Train

ingDate:24November2022基本概念•数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。•数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处

理。•数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。ITEducation&TrainingDate:24November2022数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性

结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：ITEducation&TrainingDate:24November2022主要内容•1.1线性表以及其应用•1.2栈、队列•1.3排序、查找ITEducation&Trai

ningDate:24November20221.1线性表以及其应用（1）•线性表–分为静态线性表和动态线性表–静态线性表•特征：表中节点的存储是连续的，占用一块连续存储区，一般节点的数量是固定的；•存储表示如下图

•数据结构如下图数据1后继:2数据2后继:3数据3后继:4…………数据n-1后继:n数据nendtypedefstruct{Data_tdata;//数据域intnext;//后继域}Node_t,*PNode_t;/

/提供的操作有：初始化、插入、删除等。ITEducation&TrainingDate:24November2022线性表•顺序存储结构特定：借助元素在存储器中的相对位臵（即，物理位臵相邻）来表示数据元素之间的逻辑关系。缺点：插入、删除时，需移动大量数据。

一次性分配内存空间。表的容量难以扩充。ITEducation&TrainingDate:24November2022图顺序存储结构内存结构示意图ITEducation&TrainingDate:24November20221.

1线性表以及其应用（2）–动态线性表•特征：表中节点的存储是不连续的，一般节点的数量是不固定的；•存储表示如下图•数据结构如下图typedefstruct{Data_tdata;//数据域Node_t*next;//后继域}Node_t,*PNode_t;//提供的操作

有：初始化、插入、删除等。数据1后继数据2后继数据3后继…………数据n-1后继数据nendITEducation&TrainingDate:24November2022链式存储结构•链式存储结构是计算机中的另一种最基本和最主要的数据存储结构。和顺序存储结构不同，初始时链式存储

结构为空链，每当有新的数据元素需要存储时用户向系统动态申请所需的存储空间插入链中。ITEducation&TrainingDate:24November2022链式存储结构•每个结点有两个域，其中存储数据元素信息的域称为整数域

；存储直接后继存储位臵的域称为指针域。structNode{intdata;structNode*Next;};typedefstructNodeNode_t;ITEducation&TrainingDate:24

November2022•链式存储结构存储线性结构数据元素集合的方法是用结点（Node）构造链。线性结构数据元素的特点是：除第一个和最后一个元素外，每个元素只有一个惟一的前驱和一个惟一的后继。链式结构中每个结点除数据域外还有一个

或一个以上的指针域，数据域用来存放数据元素，指针域用来构造数据元素之间的关系。只有一个指针域的结点结构如图所示。ITEducation&TrainingDate:24November2022图只有一个指针域的结点结构数据域指针域datanext或ITEduca

tion&TrainingDate:24November2022•根据指针域的不同和结点构造链的方法不同，链式存储结构存储线性结构数据元素的方法主要有单链、单循环链和双向循环链等三种。这三种结构中每一种又有带头结点结构和不带头结点结构两种。头结点是指头指针所指

的不存放数据元素的结点。其中，带头结点的链式结构在表的存储中更为常用，不带头结点的链式结构在堆栈和队列的存储中更为常用。ITEducation&TrainingDate:24November2022•我们把图中头结点的数据域部分涂上阴影，以明显表示该结点为头结点。图2和图3中的指针域为指

向下一个结点的指针。图4中结点右部的指针域为指向下一个结点的指针，结点左部的指针域为指向上一个结点的指针。在以后的图示中，头指针将用head表示。ITEducation&TrainingDate:24Novem

ber2022图2带头结点的单链结构(a)空链；(b)非空链头指针头指针a0a1…an－1(a)(b)ITEducation&TrainingDate:24November2022图3带头结点的单循环链结构(a)空链；(b)非空链头指针头指针a0a1…an

－1(a)(b)ITEducation&TrainingDate:24November2022图4带头结点的双循环链结构(a)空链；(b)非空链头指针头指针a0a1…an－1(a)(b)ITEducation&TrainingDate:24November2022•图中的符号“∧”

表示空指针，空指针在算法描述中用NULL表示。空指针是一个特殊标识，用来标识链的结束。NULL在C中宏定义为0，因此空指针在C中也就是0地址。为与顺序表中数据元素从a0开始相一致，讨论链表时数据元素也从

a0开始。•链式存储结构也可以方便地存储非线性结构的数据元素。链式存储结构存储非线性结构数据元素的最典型的例子是链式结构的二叉树。ITEducation&TrainingDate:24November2022•添加•插入•删除ITEducation&TrainingDate

:24November2022图单链表在第一个位置删除结点过程heada0a1…an－1p=a.next;a.next=a.next.next;dispose(p);ITEducation&TrainingDate:24November2022图单链表在第一个位置插入结点过程（a）插入前；（b）插

入后new(s);s.data=x;s.next=a.next;a.next=s;heada0a1…an£1xs(a)heada0a1…an£1x(b)ITEducation&TrainingDate:24November2022循环链表(circul

arlinkedlist)–循环链表是表中最后一个结点的指针指向头结点，使链表构成环状–特点：从表中任一结点出发均可找到表中其他结点，提高查找效率–操作与单链表基本一致,循环条件不同•单链表p或p->next=NULL•循环链表p或p->next=Hhh

空表ITEducation&TrainingDate:24November2022双向链表–双向链表(Doublelinkedlist):–在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表

。ITEducation&TrainingDate:24November2022•双向链表（doublelinkedlist）–结点定义TypedetstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuL

Node,*DuLinkList;priorelementnextL空双向循环链表：非空双向循环链表：LABbcapp->prior->next=p=p->next->proir;ITEducation&TrainingDate:24Novem

ber2022栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表栈（stack）一、栈的定义和特点•定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈•特点：先

进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)ITEducation&TrainingDate:24November2022栈的表示和实现栈有两种存储表示方法:•顺序栈•链栈ITEducation&TrainingDat

e:24November2022顺序栈–实现：top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF栈的初始空间为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（o

verflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空ITEducation&TrainingDate:24November2022•链栈栈顶^…...topdatalink栈底–入栈

算法–出栈算法^…...栈底toptopxptop^…...栈底topqITEducation&TrainingDate:24November2022•栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中

常用的工具。数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)ITEducation&TrainingDate:24Nove

mber2022例如(159)10=(237)8，其运算过程如下:nndiv8nmod81591971923202实际情况:(159)10=(237)81598198280237余7余3余2toptop7top73top7

32ITEducation&TrainingDate:24November2022•队列–队列的定义及特点•定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表–队尾(rear)——允许插入的一端–队头(front)——允

许删除的一端•队列特点：先进先出(FIFO)a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)ITEducation&TrainingDate:24November2022–队列的顺序存储结构•

实现：用一维数组实现sq[M]front=0rear=0123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：r

ear指示队尾元素后一位置；front指示队头元素位置初值front=rear=0空队列条件：front==rear入队列：sq[rear++]=x;出队列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfrontIT

Education&TrainingDate:24November2022•存在问题设数组长度为M，则：–当front=0,rear=M时，再有元素入队发生溢出——真溢出–当front0,rear=M时，再有元素入队发生溢出——假溢出•解决方案–队首固定，每次出队剩余元素向下移

动——浪费时间–循环队列»基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;0M-11frontrear»实现：利用“模”运算»入队：rear=(rear+1)%M;sq[rear]=x;»出队：front=(

front+1)%M;x=sq[front];»队满、队空判定条件ITEducation&TrainingDate:24November2022循环队列上的插入操作（进队列）StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MXASIZE==

Q.front)returnERROR;//队列满Q.base[Q.rear]=e;//新元素存放到队尾Q.rear=(Q.rear+1)%MAXQSIZE;//修改队为指示器returnOK;}0101C01727272C636363545454ABABDDEFEG图3-13循环队列上的插入Q.

rearQ.rearQ.rearQ.frontQ.frontQ.front满队列空队列ITEducation&TrainingDate:24November20223）循环队列的删除把队头元素删除StatusDeQueue(Sq

Queue&Q,QElemTypee){if(Q.front==Q.rear)returnERROR;//队列空e=Q.base[Q.front];//删除当前队头元素Q.front=(Q.front+1)%MAXQSIZE;//修改队头指示器retur

nOK;}GABCCDGDFEFE图3-14循环队列的删除过程Q.rearQ.rearQ.rearQ.front（1）满（2）删除A、B后的队列（3）删除最后一个元素空队列Q.frontQ.frontITEd

ucation&TrainingDate:24November2022–链队列•结点定义typedefstructQnode{QElemTypedata;structQnode*next;}Qnode,*QueuePtr;头结点^…...front队头队尾rear设队首、队尾指针f

ront和rear,front指向头结点，rear指向队尾typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;ITEducation&TrainingDa

te:24November2022frontrearx入队^xfrontreary入队x^yfrontrearx出队x^yfrontrear空队^frontreary出队^ITEducation&TrainingDate:24November20221.1线性表以及其应用（3）•线性表

的应用－－索引表–引出•为便于对数据（线性数据和非线性数据）进行检索和更新；–定义•对数据进行索引的线性表；–分类•索引可以分为单级索引和多级索引•单级索引的图示（如下图）数据1数据2数据3数据4……数据n数据n-1数据

1的地址数据1的Key值数据2的地址数据2的Key值…………数据n-1的地址数据n-1的Key值数据n的地址数据n的Key值原始数据：索引表：ITEducation&TrainingDate:24November20221.1线性表以及其应用（4）•多级

索引(以2级为例)的图示数据1数据2数据3数据4……数据n-2数据n-1数据1的地址数据1的Key值数据4的地址数据4的Key值数据组1的地址数据组1的key值数据n-3的地址数据n-3的Key值数据n的地址数据n的Key值原始数据：一级索引表：数据n-3数据n…………二级索引

表：…………数据组2的地址数据组2的key值ITEducation&TrainingDate:24November20221.1线性表以及其应用（5）–使用索引表的好处•可以将一些非线性的问题转换为了线性问题加以解决•

提高数据检索的效率•便于数据的更新ITEducation&TrainingDate:24November20221.2栈、队列•栈–栈的数据结构有什么特点–栈有什么样的应用•队列–队列的数据结构有什么特点–队列有什么样的用

途ITEducation&TrainingDate:24November2022查找–查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素–关键字——是数据元素中某个数据项的值，它可以标识一个数据元素–查找

方法评价•查找速度•占用存储空间多少•算法本身复杂程度•平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位臵，需和给定值进行比较的关键字的个数的期望值叫查找算法的~个元素所需比较次数为找到表中第个元素的概率，为

查找表中第其中：个记录的表，对含有icpipcpASLniniiiniii111ITEducation&TrainingDate:24November2022•顺序查找–查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较

–算法描述Ch7_1.ci例01234567891011513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1ITEduc

ation&TrainingDate:24November2022–顺序查找方法的ASL212)1(11111nnnnincpASLnpniniiii则概率相等设表中每个元素的查找niiicpASLn1个记录的表

，对含有ITEducation&TrainingDate:24November2022•折半查找–查找过程：每次将待查记录所在区间缩小一半–适用条件：采用顺序存储结构的有序表–算法实现•设表长为n，low、high和mid分别指向待查元

素所在区间的上界、下界和中点,k为给定值•初始时，令low=1,high=n,mid=(low+high)/2•让k与mid指向的记录比较–若k==r[mid].key，查找成功–若k<r[mid].key，则high=mid-1

–若k>r[mid].key，则low=mid+1•重复上述操作，直至low>high时，查找失败ITEducation&TrainingDate:24November2022–算法描述lowhighmid例1234567891

011513192137566475808892找211234567891011513192137566475808892lowhighmid123456789101151319213756647580889

2lowhighmidCh7_2.cITEducation&TrainingDate:24November2022例1234567891011513192137566475808892lowhighmid找70

1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmidITEducation&T

rainingDate:24November20221234567891011513192137566475808892lowhigh1185210741936判定树：123456789101151319213

7566475808892ITEducation&TrainingDate:24November2022•分块查找–查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找–适用条件：分块有序表–

算法实现•用数组存放待查记录,每个数据元素至少含有关键字域•建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针–算法描述Ch7_3.cITEducation&TrainingDate:24November202212345678

910111213141516171822121389203342443824486058745786532248861713索引表查38ITEducation&TrainingDate:24November2022ASL最大最小两者之间

表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找ITEducation&TrainingDate:24November

2022•哈希查找–基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法–定义•哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~–哈希函数是一种映象，是从关键字

空间到存储地址空间的一种映象–哈希函数可写成：addr(ai)=H(ki)»ai是表中的一个元素»addr(ai)是ai的存储地址»ki是ai的关键字关键字集合存储地址集合hashITEducation&TrainingDate:24November2022•哈希表——

应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~•哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~例30个地区的各民族人口统计表编号地区别总人口汉族回族…...1北京2上海…...…...以编号作关

键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19ITEducation&TrainingDate:24November2022从例

子可见：–哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可–冲突：key1key2，但H(key1)=H(key2)的现象叫~–同义词：具有相同函数值的两个关键字，叫该哈希函

数的~–哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法–哈希函数的构造方法•直接定址法–构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=a·key+b–特点ITEducatio

n&TrainingDate:24November2022•数字分析法–构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址–适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况例有80个记录，关键字为8位十进制数，哈希地址为2位十

进制数8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5数字分布近乎随机所以：取任意两位或两位与另两位的叠加作哈

希地址ITEducation&TrainingDate:24November2022•平方取中法–构造：取关键字平方后中间几位作哈希地址–适于不知道全部关键字情况•折叠法–构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址–种类»移位叠加

：将分割后的几部分低位对齐相加»间界叠加：从一端沿分割界来回折送，然后对齐相加–适于关键字位数很多，且每一位上数字分布大致均匀情况例关键字为：0442205864，哈希地址位数为4586442200410088H

(key)=0088移位叠加58640224046092H(key)=6092间界叠加ITEducation&TrainingDate:24November2022•除留余数法–构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=keyMO

Dp，pm–特点»简单、常用，可与上述几种方法结合使用»p的选取很重要；p选的不好，容易产生同义词•随机数法–构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)–适于关键字长度不等的情况•选取哈希函数，考虑以下因素：–计算哈希函数所需时间–关键字长度ITEd

ucation&TrainingDate:24November2022–处理冲突的方法•开放定址法–方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位臵（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)

MODm，i=1,2,……k(km-1)其中：H(key)——哈希函数m——哈希表表长di——增量序列–分类»线性探测再散列：di=1,2,3,……m-1»二次探测再散列：di=1²,-1²,2²,-2²,3²,……±k²(km/2)»伪随机

探测再散列：di=伪随机数序列ITEducation&TrainingDate:24November2022例表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=keyMOD11,现有第4个记录，其关键字为38，按三种处理冲突的方法

，将它填入表中012345678910601729(1)H(38)=38MOD11=5冲突H1=(5+1)MOD11=6冲突H2=(5+2)MOD11=7冲突H3=(5+3)MOD11=8不冲突38(

2)H(38)=38MOD11=5冲突H1=(5+1²)MOD11=6冲突H2=(5-1²)MOD11=4不冲突38(3)H(38)=38MOD11=5冲突设伪随机数序列为9，则：H1=(5+9)MOD11=3不冲突

38ITEducation&TrainingDate:24November2022•再哈希法–方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key)i=1,2,……k其中：Rhi——不同的哈希函数

–特点：计算时间增加•链地址法–方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针ITEducation&TrainingDate:24November2022例已知一组关键字(19,14,23,1,68

,20,84,27,55,11,10,79)哈希函数为：H(key)=keyMOD13,用链地址法处理冲突012345678910111214^127796855198420231011^^^^^^^^^^^^ITEducation&TrainingDate:24Nove

mber2022–哈希查找过程及分析•哈希查找过程给定k值计算H(k)此地址为空关键字==k查找失败查找成功按处理冲突方法计算HiYNYNITEducation&TrainingDate:24November2022•哈希查找分析–哈希查找过程仍是

一个给定值与关键字进行比较的过程–评价哈希查找效率仍要用ASL–哈希查找过程与给定值进行比较的关键字的个数取决于：»哈希函数»处理冲突的方法»哈希表的填满因子=表中填入的记录数/哈希表长度ITEducation&TrainingDate:24November2022

例已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=keyMOD13,哈希表长为m=16，设每个记录的查找概率相等(1)用线性探测再散列处理冲突，即Hi=(H(key)+di)MODmH

(55)=3冲突，H1=(3+1)MOD16=4冲突，H2=(3+2)MOD16=5H(79)=1冲突，H1=(1+1)MOD16=2冲突，H2=(1+2)MOD16=3冲突，H3=(1+3)MOD16=4冲突，H4=(1+4)MOD16=

5冲突，H5=(1+5)MOD16=6冲突，H6=(1+6)MOD16=7冲突，H7=(1+7)MOD16=8冲突，H8=(1+8)MOD16=90123456789101112131415ASL=(1*6+2+3*3+4+9)/12=

2.514168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1冲突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6冲突，H1=(6+1)MOD16=7冲突

，H2=(6+2)MOD16=8H(27)=1冲突，H1=(1+1)MOD16=2冲突，H2=(1+2)MOD16=3冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10冲突，H1=(10+1)MOD16=11冲

突，H2=(10+2)MOD16=12ITEducation&TrainingDate:24November2022(2)用链地址法处理冲突012345678910111214^127796855198420231011^^^^^^^^^^^^ASL=(1*6+2*4+3+4

)/12=1.75关键字(19,14,23,1,68,20,84,27,55,11,10,79)ITEducation&TrainingDate:24November2022–哈希查找算法实现•用线性探测再散列法处理冲突–实现»查找过程：同前»删

除：只能作标记，不能真正删除»插入：遇到空位臵或有删除标记的位臵就可以插入–算法描述：•用外链表处理冲突算法Ch7_4.cCh7_5.cITEducation&TrainingDate:24November2022排序–排序定义——将一个数据元素（

或记录）的任意序列，重新排列成一个按关键字有序的序列叫~–排序分类•按待排序记录所在位臵–内部排序：待排序记录存放在内存–外部排序：排序过程中需对外存进行访问的排序•按排序依据原则–插入排序：直接插入排序、折半插入排

序、希尔排序–交换排序：冒泡排序、快速排序–选择排序：简单选择排序、堆排序–归并排序：2-路归并排序ITEducation&TrainingDate:24November2022插入排序–直接插入排序•排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记

录开始，逐个进行插入，直至整个序列有序•算法描述ITEducation&TrainingDate:24November2022例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38

496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：ITEducatio

n&TrainingDate:24November2022–折半插入排序•排序过程：用折半查找方法确定插入位臵的排序叫~例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(61330394

27085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sjmi=820(6133039427085)20sji=820(613203039427085)ITEducation&TrainingDate:24Nov

ember2022•算法描述•算法评价–时间复杂度：T(n)=O(n²)–空间复杂度：S(n)=O(1)Ch8_2.cITEducation&TrainingDate:24November2022希尔排序(缩小增量法)•排序过程：先取一个正整数

d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止ITEducation&TrainingDate:24November202

21.3排序、查找(1)•排序–常用的排序方法－－冒泡排序–程序:voidBubbleSort(inta[],n){inti,j;intx;for(i=1;i<n;i++){for(j=0;j<n-i;j++){//找到一组中最大的if(a[j]>a[j+1]){//进行交换x=

a[j];a[j]=a[j+1];a[j+1]=x;}};}}ITEducation&TrainingDate:24November20221.3排序、查找(2)–常用的排序方法－－选择排序–程序:voidSelectSort(inta[],intn){

inti,j,k;intxfor(i=1;i<n;i++){//进行n-1次选择和交换k=i-1;for(j=i;j<n;j++){if(a[j]<a[k])k=j;}x=a[i-1];a[i-1]=a[k];a[k]=x;}}ITEducation&Tr

ainingDate:24November20221.3排序、查找(3)•查找–常用的查找方法－－折半查找–折半查找的前提－－线性表是有序的–程序intBinarySearch(inta[],intN,intx){intlow

=0,high=N-1;//定义并初始化区间下界和上界变量intmid;//定义保存中点元素下标的变量while(low<=high){mid=(low+high)/2;if(x==a[mid])returnmid

;elseif(x<a[mid])high=mid-1;//在左半侧elselow=mid+1;//在右半侧}return-1;}ITEducation&TrainingDate:24November2022取d3=1三趟分组：1

327485544938659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：1327485544938659776二趟排序：134483827495565977

6取d1=5一趟分组：4938659776132748554取d2=3二趟分组：1327485544938659776ITEducation&TrainingDate:24November2022•算法描述Ch8_3.c例4938659776132748554#defineT3intd[]={5,

3,1};ji49133827一趟排序：1327485544938659776jiji274jiji55ji38jijiji二趟排序：1344838274955659776jiji6548ji9755ji764ITE

ducation&TrainingDate:24November2022•希尔排序特点–子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列–希尔排序可提高排序速度，因为»分组后n值减小，n²更小，而T(n)=O(n²),所以T(n)从总体上看是减小了»关键

字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序–增量序列取法»无除1以外的公因子»最后一个增量值必须为1ITEducation&TrainingDate:24November2022交换排序–冒泡排序•排序过程–将第一个记录的关键字

与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安臵在最后一个记录上–对前n-1个记录进行第二趟冒泡排序

，结果使关键字次大的记录被安臵在第n-1个记录位臵–重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止ITEducation&TrainingDate:24November2022例4938659776132730初始关键字3849657613273097第一趟38496513

273076第二趟384913273065第三趟3813273049第四趟13273038第五趟132730第六趟38497697139727973097137676762730136527653065131349493049273827383038ITE

ducation&TrainingDate:24November2022•算法描述•算法评价–时间复杂度»最好情况（正序）比较次数：n-1移动次数：0»最坏情况（逆序）比较次数：)(21)(211nninni移动次数：)(23)(321nninni–空间复杂度：S(n

)=O(1)T(n)=O(n²)Ch8_4.cITEducation&TrainingDate:24November2022–快速排序•基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录

的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序•排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key–初始时令i=s,j=t–首先从j所指位臵

向前搜索第一个关键字小于x的记录，并和rp交换–再从i所指位臵起向后搜索，找到第一个关键字大于x的记录，和rp交换–重复上述两步，直至i==j为止–再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止ITEducation&TrainingDate:24November202

2例初始关键字：4938659776132750ijxji完成一趟排序：(273813)49(76976550)分别进行快速排序：(13)27(38)49(5065)76(97)快速排序结束：13273849506576974927ijijij4965ji1349ij4997ijITEdu

cation&TrainingDate:24November2022•选择排序–简单选择排序•排序过程–首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换–再通过n-2次比较，从剩余的n-1个记录中找出关

键字次小的记录，将它与第二个记录交换–重复上述操作，共进行n-1趟排序后，排序结束ITEducation&TrainingDate:24November2022例初始：[49386597761327]kjjjjjjkki=11349一趟：13[386597764927]i=2k

kjjjjj2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序结束：13273849657697ITEd

ucation&TrainingDate:24November2022–堆排序•堆的定义：n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1例（96，83，27，38，11，9）例（1

3，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值ITEducation&TrainingDate:24November2022•堆排

序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫~•堆排序需解决的两个问题：–如何由一个无序序列建成一个堆

？–如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？•第二个问题解决方法——筛选–方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重

复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”ITEducation&TrainingDate:24November2022例13273849657650979727384965765013输出：1327493

89765765013输出：139749382765765013输出：13273849502765769713输出：13276549502738769713输出：132738ITEducation&TrainingDate:24November2022

4965502738769713输出：1327387665502738499713输出：132738495065762738499713输出：132738499765762738495013输出：13273849506597762738495013输出：13273849509765

762738495013输出：132738495065ITEducation&TrainingDate:24November20227665972738495013输出：1327384950659765762738495013输出：1327384950657697

65762738495013输出：1327384950657697ITEducation&TrainingDate:24November2022第二部分问题与习题ITEducation&TrainingDate:24November2022问题•Q1.为了描述并解决先进先出特征的问题，我们一

般会采用考虑以下哪种数据结构A,队列B,栈C,树D,二叉树•Q2.为了描述并解决先进后出特征的问题，我们一般会采用考虑以下哪种数据结构（）。A,队列B,栈C,树D,二叉树•Q3.对线性表进行二分法查找，其前提条件是A,线性表以顺序方式存储，并且按关键码值排

好序B,线性表以顺序方式存储，并且按关键码值的检索频率排好序C,线性表以链接方式存储，并且按关键码值排好序D,线性表以链接方式存储，并且按关键码值的检索频率排好序