软件技术基础-数据结构.ppt

* 简单排序算法 简单选择排序 selectsort(elemtype x[],int n) { int i,j,small; elemtype swap; for(i=0;in-1;i++) /* n-1次循环 */ { small=i; /* 无序部分第1个元素的位置 */ for(j=i+1;jn;j++) /* 寻找最小值循环 */ { if(x[j].keyx[small].key) small=j; /* 记录最小值的位置 */ } if （small!=i) { swap=x[i]; /* 交换最小值与无序部分第1个元素位置 */ x[i]=x[small]; x[small]=swap; } } } 排序 －数 据 结 构 软件技术基础 * 简单排序算法 冒泡排序 排序过程 将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].keyr[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置 重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止 排序 －数 据 结 构 软件技术基础 * 简单排序算法 冒泡排序 排序 －数 据 结 构 软件技术基础 例 49 38 65 97 76 13 27 30 初始关键字 38 49 65 76 13 27 30 97 第一趟 38 49 65 13 27 30 76 第二趟 38 49 13 27 30 65 第三趟 38 13 27 30 49 第四趟 13 27 30 38 第五趟 13 27 30 第六趟 38 49 76 97 13 97 27 97 30 97 13 76 76 76 27 30 13 65 27 65 30 65 13 13 49 49 30 49 27 38 27 38 30 38 * 哈希查找 哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象 哈希函数可写成：addr(ai)=H(ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字 查找 －数 据 结 构 软件技术基础 * 哈希查找 哈希函数常用的构造方法 数字分析法 平方取中法 折叠法 除留余数法（求模取余法） 直接定址法 查找 －数 据 结 构 软件技术基础 * 哈希查找 数字分析法 当关键字的位数比存储区地址码位数多时，可合理选择关键字的某几位组成的哈希地址。 选取的原则： 尽量避免计算出的地址有冲突。 举例： 学校的电话号码是8位十进制数，学校的程控交换机是3000门。但经分析不难得出： 0XXX 8320 8XXX 9XXX 前4位是相同的，第5位分别为“0、8、9”，这样一来，正好可以表示3000个不同的电话号码。 H（KEY）= Right（telenum，4） 查找 －数 据 结 构 软件技术基础 * 哈希查找 平方取中法 取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数的方法。通常在选定哈希函数时不知道关键字的全部情况，取其中的哪几位也不一定合适，在这种情况下，取一个数平方后的中间几位数作哈希地址。取的位数由表长决定。 例如，3288，平方后是，取后4位为哈希地址，即“0944”。 查找 －数 据 结 构 软件技术基础 * 哈希查找 折叠法 将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。 关键字位数很多，且每一位上数字分布大致均匀时，可采用折叠法。 举例：某资料室藏书近万册。采用国际标准图书编号（ISBN），每个编号10位十进制数字。可用折叠法构造一个4位数的哈希函数。 例如： 书号为： 0 - 4 4 2 - 2 0 5 8 6 - 4 5 8 6 4 4 2 2 0