常用算法和数据结构

《常用算法和数据结构》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第1章常用算法和数据结构第1章常用算法和数据结构大纲要求：l排序算法。l查找算法。l数据结构(线性表、栈、队列、数组、树、图)。1.1排序算法1.1.1考点辅导1.1.1.1选择排序若设R[1...n]为待排序的n个记录，R[1...i-1]已按照主关键字由小到大排序，且任意x∈R[1...i-1]，y∈R[i...n]满足x.key≤y.key，则选择排序的主要思路如下。(1)反复从R[i...n]中选出关键字最小的结点R[k]。(2)若i≠k，则将R[i]与R[k]交换，使得R[1...i]有序且

2、保持原来的性质。(3)i增1，直到i为n。为方便描述，被查找的顺序表C类型定义如下：#defineMAXSIZE1000/*顺序表的长度*/typedefintKeyType;/*关键字类型为整数类型*/typedefstruct{KeyTypekey;/*关键字项*/InfoTypeotherinfo;/*其他数据项*/}RecType;/*记录类型*/typedefstruct{RecTyper[MAXSIZE+1];/*r[0]空作为哨兵*/intlength;/*顺序表长度*/}SqList;

3、/*顺序表类型*/顺序存储线性表的选择排序算法如下：voidSqsort(SqList&q){inti,j,k,temp;for(i=0;i

4、为n*(n-1)/2；同时，由于相等的两个元素，位置相对在前的可能被交换到后面，故该选择排序是不稳定的。1.1.1.2直接插入排序若设R[1...n]为待排序的n个记录，R[1...i-1]已按照主关键字由小到大排序，则直接插入排序的主要思路如下。(1)寻找R[i]在R[1…i-1]中的插入位置，确保R[i]插入后保持有序。(2)i增1，若i小于等于n，则转到(1)执行，否则结束。顺序线性存储结构下的直接插入排序算法如下：voidDinsert(SqList&q){inti,j,k;for(i=1;i

5、=0&&t.key

6、线性表采用直接插入排序，最少比较次数为n-1，最多比较次数为n*(n-1)/2。(2)直接插入排序是在有序表的基础上进行的，所以排序效率较高，且比较稳定。1.1.1.3希尔排序希尔排序(ShellSort)的基本思路为：把直接插入方法分成插入步长由大到小不同的若干趟来进行，一开始步长较大，相当于把序列分成几个子表。对每个子表来说，因为其结点少，直接插入排序的效率会很高。以后各趟逐步减小步长，子表的结点也越来越多，但是子表中的结点已经进行过前一趟的大步长的直接插入排序，有相当多的结点已基本有序。这使得后

7、一趟的插入排序能充分利用前一趟的排序结果。当步长降到1时，只要对基本有序的线性表进行一趟直接插入排序即可。101第1章常用算法和数据结构初次取线性表的一半长度为步长，以后每次减半，直到步长为1，希尔排序的算法如下：voidShsort(SqList&q){intj,k,h,y;/*h为步长*/for(h=q.length/2;h>0;h/=2)for(j=h;j=0&&y.key

8、)q.r[k+h]=q.r[k];/*找到插入的位置并移动*/q.[k+h]=y;}}1.1.1.4冒泡排序若设R[1...n]为待排序的n个记录，且假设为从上至下纵向排列，则要求将n个给定记录由小到大排序的冒泡排序(BubbleSort)的基本思路如下。(1)对当前还未排好序的、指定范围内的全部结点，自上而下对相邻的两个结点依次进行比较和调整，让关键字较大的结点往下沉，关键字较小的结点往上冒。即若R[j].key>R[j+1].keg，则将R[j].k