《C语言程序设计与数据结构 教学课件 ppt 作者 周成义 等 第6章》由会员分享，可在线阅读，更多相关《C语言程序设计与数据结构 教学课件 ppt 作者 周成义 等 第6章（31页珍藏版）》请在金锄头文库上搜索。
1、1,第六章 数据的顺序存储结构及应用,6.1 线性表的顺序存储结构和运算 6.2 栈和队列的顺序存储结构和运算 6.3 检索算法 6.4 排序算法,2,6.1 线性表的顺序存储结构和运算,6.1.1 线性表的逻辑结构 6.1.2 线性表的顺序存储结构及基本运算,3,6.1.1 线性表的逻辑结构,线性表（Linear_List）是最常用且最简单的一种数据结构。简单地说，一个线性表是n个数据元素的有限序列。 线性表中元素的个数n（n0），定义为线性表的长度。当n=0时称为空表。在非空的线性表（n0）中，有且仅有一个开始结点a1和一个终端结点an，除a1和an外，表中的每一个结点ai（2in-1）都
2、有一个直接前驱结点ai-1和一个直接后继结点ai+1。表中只有一个结点没有直接前驱，即开始结点a1，同时，也只有一个结点没有直接后继，即终端结点an。,4,6.1.1 线性表的逻辑结构,可以把非空线性表抽象地写成： Linear_List=（D，R） 其中：D=（ai | aiD0，i=1，2，n，n0） R= | ai-1，aiD0，i=1，2，n D0为某个数据对象。,5,6.1.2 线性表的顺序存储结构及基本运算,线性表的顺序存储指的是用一组地址连续的存储单元存储线性表的数据元素。 假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第
3、i+1个数据元素的存储位置LOC（ai+1）和第i个数据元素的存储位置LOC（ai）之间满足下列关系： LOC（ai+1）=LOC（ai）+l 一般来说，线性表的第i个数据元素ai的存储位置为 LOC（ai）=LOC（a1）+（i-1）*l 式中LOC（a1）是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。,6,6.1.2 线性表的顺序存储结构及基本运算,2. 线性表的插入、删除与查找运算 线性表的插入运算是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，就是要使长度为n的线性表 （a1，a2，ai-1，ai，an） 变成长度为n+1的线性表
4、（a1，a2，ai-1，b，ai，an） 可以看出，数据元素ai-1和 ai之间的逻辑关系发生了变化。在插入新的数据元素b时，a1到 ai-1结点位置保持不变，如果插入位置i=n+1，也就是插入到表的末尾，那么只要在表的末尾增加一个结点就可以了；但若1in，则必须将表中ai到 an结点依次向后移动一个位置，共需移动n-i+1个结点。,7,6.1.2 线性表的顺序存储结构及基本运算,线性表的删除运算是使长度为n的线性表 （a1，a2，ai-1，ai，ai+1，an） 变成长度为n-1的线性表 （a1，a2，ai-1，ai+1，an） 数据元素ai-1，ai和ai+1之间的逻辑关系发生变化。当i=
5、n时，即删除表尾结点，只需简单地将表的最后结点删去；但当1in-1时，必须将表中结点ai+1到an依次向前移动一个位置。,8,6.2 栈和队列的顺序存储结构和运算,6.2.1 栈 6.2.2 队列,9,6.2.1 栈,1. 栈的定义 栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（bottom）。不含任何元素的空表称为空栈。,10,6.2.1 栈,2. 栈的顺序存储结构和运算 栈的顺序存储结构是用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶位置。我们约定，top指向栈顶
6、的上一个空位置，即新数据元素将压入的位置，当栈空时，top=0。可用C语言中的一维数组sL_STACK作为栈的顺序存储结构，其中，L_STACK是预先给定的常量，表示栈的最大容量。,11,6.2.2 队列,1队列的定义 和栈相反，队列（Queue）是一种先进先出（First In First Out，缩写为FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾（rear），允许删除的一端则称为队头（front）。假设队列为q=（a1，a2，an）,那么a1就是队头元素，an则是队尾元素。
7、队列中的元素是按照a1，a2，an的顺序进入的，退出队列也只能按照这个次序依次退出，也就是说，只有在a1，a2，an-1都离开队列之后，an才能退出队列。,12,6.2.2 队列,2队列的顺序存储结构和运算 和栈采取顺序存储结构相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，尚需附设两个指针front（f）和rear（r）分别表示队列头元素和队列尾元素的位置。在这里，我们约定，队头指针f指向实际队头的前一个位置；队尾指针r指向实际队尾结点所在的位置。初始时，f=r= -1，入队时，r加1，出队时，f加1。可用C语言中的一维数组qL_QUEUE作为
8、队列的顺序存储结构，其中，L_QUEUE是预先给定的常量，表示队列的最大容量。,13,6.3 检索算法,6.3.1 顺序表查找 6.3.2 哈希查找,14,6.3.1 顺序表查找,1.顺序查找 顺序查找是一种最简单和最基本的查找方法。它的查找过程是：从顺序表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某个元素的关键字等于给定值K，则表明查找成功，返回该元素所在的下标；若直到所有元素都比较完毕，仍找不到关键字为K的元素，则表明查找失败，返回特定的值（常用0表示）。,15,6.3.1 顺序表查找,2.二分查找 二分查找又称折半查找。作为二分查找的表必须是顺序存储的有序表。通常假定有序表
9、是按关键字从小到大有序。二分查找的过程是：首先取整个有序表A（1n）的中点元素Amid（其中mid=（1+n）/2向下取整）的关键字同给定值K比较，若相等，则查找成功，返回该元素的下标mid，否则，若Amid.keyK，则说明要查找元素只可能落在左子集A1mid - 1中，接着只要在左子集中继续进行二分查找即可。若Amid.keyK，则说明要查找元素只可能落在右子集Amid+1n中，接着只要在右子集中进行二分查找即可；这样，经过一次关键字的比较，就缩小一半的查找空间，如此进行下去，直到找到关键字为K的元素，或者当前查找区间为空（即表明查找失败）时为止。,16,6.3.1 顺序表查找,3.分块查
10、找 分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此查找法中，除表本身以外，尚需建立一个“索引表”。 分块查找的平均查找长度为 ASLbsLb+Lw 其中：Lb为查找索引表确定所在块的平均查找长度，Lw为在块中查找元素的平均查找长度。,17,6.3.2 哈希查找,1. 哈希表 在前面介绍的各种查找算法中，在查找记录时需进行一系列和关键字的比较，这类查找方法建立在“比较”的基础上，查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置
11、相对应。因而在查找时，只要根据这个对应关系f找到给定值K的像f（K）。若结构中存在关键字和K相等的记录，则必定在f（K）的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，我们称这个对应关系f为哈希（Hash）函数，按这个思想建立的表为哈希表，由对应关系f所得的存储位置称哈希地址或散列地址。,18,6.3.2 哈希查找,常用的构造哈希函数的方法有： (1)直接地址法 取关键字或关键字的某个线性函数为哈希地址，即H（key）=key或H（key）=a x key+b，其中a和b为常数。 (2)数字分析法 假设关键字是以r为基的数（如：以10为基的十进制数），并且哈希表中可能出现的关键字
12、都是事先知道的，则可取关键字的若干数位组成哈希地址。 (3)平方取中法 取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数的方法。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都有关，由此使随机分布的关键字得到的哈希地址是随机的。取的位数由表长决定。,19,6.3.2 哈希查找,解决冲突的方法基本上有两大类： 一类称为开放地址法。当发生冲突时，用某种方法形成一个探测序列，沿着这个序列一个个单元地查询，直到找到这个关键字或找到一个开放的地址（即没有进行存储的空单元）。如果是插入操作，则遇到空单元就可以进行插入；如果
13、是查找操作，则遇到空单元就是查找失败； 另一类称为链地址法。当发生冲突时，就把发生冲突的结点用单链表链接起来。,20,6.4 排序算法,6.4.1 概述 6.4.2 插入排序 6.4.3 交换排序 6.4.4 选择排序 6.4.5 归并排序,21,6.4.1 概述,排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排序成一个按关键字有序的序列。 假设含n个记录的序列为 R1，R2，Rn 其相应的关键字序列为 K1，K2，Kn 需确定1，2，n的一种排列p1，p2，pn，使其相应的关键字满足如下的非递减（或 非递增）关系 Kp1Kp2Kpn 也就是使序列R1
14、，R2，Rn成为一个按关键字有序的序列 Rp1Rp2Rpn 这样一种操作称为排序。,22,6.4.2 插入排序,1.直接插入排序 直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。例如：数组A（1n）中包含n个待排序的元素，首先把A1看成是一个有序表，其余的n-1个元素A2An构成一个无序表。排序过程中，每次从无序表中取出第一个元素，把它插入到有序表中的适当位置，使之成为新的有序表，这样经过n-1次插入后，无序表就变为空表，有序表中就包含了全部n个元素，排序结束。,23,6.4.2 插入排序,2.二分法插入排序 由于插入
15、排序的基本操作是在一个有序表中进行查找和插入，这个“查找”操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序。其基本思想是：在确定Ri（i=2，3，n）的插入位置时，是将它与前面i-1个记录依次比较，由于前i-1个记录已按关键字有序，可以用二分法较快地找到Ri的插入点。首先取m=1+(i-1)/2，比较Rm与Ri的关键字。若Ri的关键字小于Rm的关键字，则在R1，R2，Rm-1范围内再用二分法，否则在Rm+1，Rn范围内再用二分法。如此反复，直至最后找到Ri的插入位置。令i从2到n，依次插入每个Ri，完成整个排序过程。,24,6.4.2 插入排序,3.希尔排序 希尔排序又称“缩
16、小增量排序”，它也是一种属插入排序类的方法，但在时间效率上较前两种插入排序方法有较大的改进。 在直接插入排序中，只比较相邻的记录，一次比较至多将记录移动一个位置，如果比较相隔较远距离（称为增量）的记录，使得记录移动时能跨过较多的元素，则进行一次比较就可能消除多个反序。D.L.shell于1959年在以他的名字命名的排序算法中实现了这一思想。这个算法先将记录按某个增量d分成若干组，每组中记录的下标相差d。对每组中的记录用某种方法（比如直接插入排序方法）进行排序，然后再用一个较小的增量d对记录进行分组，在每组中再进行排序，当增量减至1时，整个记录被分成一组，排序完成。,25,6.4.3 交换排序,1冒泡排序 冒泡排序的过程很简单。首先将第一个记录A1的关键字和第二个记录A2的关键字进行比较，若为逆序（即A1的关键字大于A2的关键字），则交换两个记录的位置
