考研数据结构算法经典.pdf

《考研数据结构算法经典.pdf》由会员分享，可在线阅读，更多相关《考研数据结构算法经典.pdf（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构算法背诵一、线性表1.逆转顺序表中的所有元素算法思想：第一个元素和最后一个元素对调，第二个元素和倒数第二个元素对调，依此类推。void Reverse(int A,int n)(int i,t;for(i=0;i next;while(p!=NULL)if(p-data=item)q-next=p-next;free(p);p=q-next;else q=p;p=p-next;)if(list-data=item)q=list;list=list-next;free(q);)3.逆转线性链表void Reverse(LinkList&list)(LinkList p,q,r;p=lis

2、t;q=NULL;while(p!=NULL)r=q；q=p；p=p-next;q-next=r;list=q;4.复制线性链表(递归)LinkList Copy(LinkList lista)(LinkList listb;if(lista=NULL)return NULL;else listb=(LinkList)malloc(sizeof(LNode);listb-data=lista-data;listb-next=Copy(lista-next);return listb;)5.将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表LinkList MergeList(Link

3、List lista,LinkList listb)(LinkList listc,p=lista,q=listb,r;/listc指 向 lista和 listb所指结点中较小者if(lista-data data)listc=lista;r=lista;p=lista-next;else listc=listb;r=listb;q=listb-next;while(p!=NULL&q!=NULL)if(p-data data)r-next=p;r=p;p=p-next;else r-next=q;r=q;q=q-next;/将剩余结点(即未参加比较的且已按升序排列的结点)链接到整个链表后面

4、r-next=(p!=NULL)?p:q;return listc;二、树1.二叉树的先序遍历(非递归算法)算法思想：若P所指结点不为空，则访问该结点，然后将该结点的地址入栈，然后再将P指向其左孩子结点；若P所指向的结点为空，则从堆栈中退出栈顶元素(某个结点的地址),将P指向其右孩子结点。重复上述过程，直到p=NULL且堆栈为空，遍历结束。#define MAX_STACK 50void PreOrderTraverse(BTree T)(BTree STACKMAX_STACK,p=T;int top=-1;while(p!=NULLII top!=-l)while(p!=NULL)VISI

5、T(p);STACK+top=p;p=p-lchild;p=STACKtop-;p=p-rchild;)2.二叉树的中序遍历（非递归算法）算法思想：若P所指结点不为空，则将该结点的地址p入栈，然后再将P指向其左孩子结点；若P所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址）送P，并访问该结点，然后再将p指向该结点的右孩子结点。重复上述过程，直到p=NULL且堆栈为空，遍历结束。#define MAX_STACK 50void InOrderTraverse(BTree T)BTree STACKMAX_STACK,p=T;int top=-1;while(p!=NULL II top!

6、=-l);(while(p!=NULL)(STACK+top=p;p=p-lchild;)p=STACKtop-;VISIT(p);p=p-rchild;3.二叉树的后序遍历（非递归算法）算法思想：当P 指向某一结点时，不能马上对它进行访问，而要先访问它的左子树,因而要将此结点的地址入栈；当其左子树访问完毕后，再次搜索到该结点时（该结点地址通过退栈得到），还不能对它进行访问，还需要先访问它的右子树，所以，再一次将该结点的地址入栈。只有当该结点的右子树访问完毕后回到该结点时，才能访问该结点。为了标明某结点是否可以访问，引入一个标志变量fla g,当flag=O时表示该结点暂不访问，flag=1

7、时表示该结点可以访问。flag的值随同该结点的地址一起入栈和出栈。因此，算法中设置了两个堆栈，其中STACK1存放结点的地址，STACK2存放标志变量fla g,两个堆栈使用同一栈顶指针to p,且top的初始值为.lo#define MAX_STACK 50void PostOrderTraverse(BTree T)BTree STACK1MAX_STACKJ,p=T;int STACK2MAX_STACK,flag,top=-1;while(p!=NULL II top!=-l)while(p!=NULL)STACKl+top=p;STACK2top=0;p=p-lchild;p=STA

8、CK 1 top;flag=STACK2top-;if(flag=0)STACKl+top=p;STACK2top=1;p=p-rchild;else VISIT(p);p=NULL;4.二叉树的按层次遍历算法思想：设置一个队列，首先将根结点（的地址）入队列，然后依次从队列中退出一个元素，每退出一个元素，先访问该元素所指的结点，然后依次将该结点的左孩子 结 点（若存在的话）和右孩子 结 点（若存在的话）入队列。如此重复下去，直到队列为空。#define MAX_QUEUE 50void LayeredOrderTraverse（BTree T）（BTree QUEUEMAX_QUEUE,p;i

9、nt front,rear;if(T!=NULL)(QUEUE0=T;front=-1;rear=0;while(front lchild!=NULL)QUEUE+rear=p-lchild;if(p-rchild!=NULL)QUEUE+rearJ=p-rchild;5.建立二叉树(从键盘输入数据，先序遍历递归算法)BTree CreateBT()char ch;BTree T;sacnf(%c,&ch);if(ch=)return NULL;else T=(BTree)malloc(sizeof(BTNode);T-data=ch;T-Ichild=CreateBT();T-rchild=

10、CreateBT();return T;6.建立二叉树(从数组获取数据)BTree CreateBT(int A,int i,int n)BTree p;if(i n)return NULL;else p=(BTree)malloc(sizeof(BTNode);p-data=Ai;p-lchild=CreateBT(A,2*i,n);p-rchild=CreateBT(A,2*i+l,n);return p;)T=CreateBT(A,1,n);BTree CreateBT(int A,int n)int i;BTree*pT;/对应n 个结点申请可容纳n 个指针变量的内存空间pT=(BTr

11、ee*)malloc(sizeof(BTree)*n);/若数组中的某个元素不等于零，则申请相应的结点空间并进行赋值for(i=l;i data=Ai;else pTi=NULL;修改结点的指针域的内容，使父结点指向左、右孩子结点for(i=l;i lchild=pT2*i;pTi-rchild=pT2*i+l;7.求二叉树的深度(递归算法)int Depth(BTree T)(int Idepth,rdepth;if(T=NULL)return 0;else Idepth=Depth(T-lchild);rdepth=Depth(T-rchild);if(Idepth rdepth)retu

12、rn ldepth+1;elsereturn rdepth+1;)8.求二叉树的深度(非递归算法)算法思想：对二叉树进行遍历，遍历过程中依次记录各个结点所处的层次数以及当前已经访问过的结点所处的最大层次数。每当访问到某个叶子结点时，将该叶子结点所处的层次数与最大层次数进行比较，若前者大于后者，则修改最大层次数为该叶子结点的层次数,否则不作修改。遍历结束时，所记录的最大层次数即为该二叉树的深度。本算法使用的是非递归的中序遍历算法（其它遍历顺序也可以）。#define MAX_STACK 50int Depth(BTree T)(BTree STACK 1MAX_STACK,p=T;int STA

13、CK2MAX_STACK;int curdepth,max depth=0,top=-1;if(T!=NULL)(curdepth=1;while(p!=NULL II top!=-)while(p!=NULL)(STACK 1 +top=p;STACK2top=curdepth;p=p-lchild;curdepth+;p=STACK 1 top;curdepth=STACK2top J;if(p-lchild=NULL&p-rchild=NULL)if(curdepth maxdepth)maxdepth=curdepth;p=p-rchild;curdepth+;)return maxd

14、epth;9.求结点所在层次算法思想：采用后序遍历的非递归算法对二叉树进行遍历，遍历过程中对每一个结点判断其是否为满足条件的结点，若是满足条件的结点，则此时堆栈中保存的元素个数再加1 即为该结点所在的层次。#define MAX_STACK 50int LayerNode(BTree T,int item)BTree STACK1 MAX_STACK,p=T;int STACK2MAX_STACK,flag,top=-l;while(p!=NULLII top!=-l)while(p!=NULL)STACKl+top=p;STACK2top=0;p=p-lchild;p=STACK 1 top

15、;flag=STACK2top-;if(flag=0)STACKl+top=p;STACK2top=1;p=p-rchild;else if(p-data=item)return top+2;p=NULL;)10.交换二叉树中所有结点的左右子树的位置算法思想：按层次遍历二叉树，遍历过程中每当访问一个结点时，就将该结点的左右子树的位置对调。#define MAX_QUEUE 50void ExchangeBT(BTree T)BTree QUEUEMAX_QUEUE,temp,p=T;int front,rear;if(T!=NULL)(QUEUE0=T;front=-1;rear=0;whil

16、e(front lchild;p-lchild=p-rchild;p-rchild=temp;if(p-lchild!=NULL)QUEUE+rear=p-lchild;if(p-rchild!=NULL)QUEUE+rear=p-rchild;11.删除二叉树中以某个结点为根结点的子树算法思想：先序遍历找到符合条件的结点(其它遍历方法亦可)，然后删除以该结点为根结点的子树。最后把该结点的父结点的相应的指针域置为NULLo为此，需在算法中设置一个指针变量用以指示当前结点的父结点。#define MAX_STACK 50BTree DeleteSubtree(BTree&T,int item)(

17、BTree STACKMAX_STACK,q,p=T;int top=-1;if(T-data=item)(Destroy BT(T);T=NULL;return NULL;Ielsewhile(p!=NULLII top!=-l)while(p!=NULL)if(p-data=item)(if(q-lchild=p)q-lchild=NULL;elseq-rchild=NULL;DestroyBT(p);return T;STACK+top=p;q=p；p=p-lchild;q=STACKtop-;p=q-rchild;)三、查找1.顺序查找的递归算法int RecurSeqSearch(i

18、nt A,int n,int key,int i)(if(i=n)return-1;if(Ai=key)return i;elsereturn RecurSeqSearch(A,n,key,i+1);)pos=RecurSeqSearch(A,n,key,0);2.折半查找int BinSearch(int A,int n,int key)(int low=0,high=n-1,mid;while(low Amid)low=mid+1;elsehigh=mid-1;return-1;)3.折半查找的递归算法int RecurBinSearch(int A,int low,int high,in

19、t key)(int mid;if(low high)return-1;else mid=(low+high)/2;if(key=Amid)return mid;if(key Amid)return RecurBinSearch(A,mid+1,high,key);elsereturn RecurBinSearch(A,low,mid-1,key);pos=RecurBinSearch(A,0,n-1,key);4.在按值递增排列且长度为n 的线性表中折半查找并插入一元素void Binlnsert(int A,int&n,int key)(int j,low=0,high=n-l,mid;w

20、hile(low Amid)low=mid+1;elsehigh=mid-1;for(j=n;j low;j-)AU=AU-1;Alow=key;n+;)5.在按值递增排列且长度为n的线性表中折半查找值不小于key的最小元素void BinSearch(int A J,int n,int key)int low=0,high=n-l,mid;while(low Amid)low=mid+1;elsehigh=mid-1;if(low=n-1)return low;elsereturn-1;四、排序1.插入排序算法思想：第i趟插入排序为：在含有i.1个元素的有序子序列中插入一个元素，使之成为含有

21、i个元素的有序子序列。在查找插入位置的过程中，可以同时后移元素。整个过程为进行n.1趟插入，即先将整个序列的第1个元素看成是有序的，然后从第2个元素起逐个进行插入，直到整个序列有序为止。void InsertSort(int A,int n)(int i,j,temp;for(i=l;i=n-1;i+)if(Ai=0&temp Aj)(AU+l=Aj；j-s)Aj+1=temp;)2.折半插入排序算法思想：算法同直接插入排序，只不过使用折半查找的方法来寻找插入位置。void BinInsertSort(int A,int n)(int i,j,low,high,mid,temp;for(i=l

22、;i=n-1;i+)temp=Ai;low=0;high=i-1;while(low Amid)low=mid+1;elsehigh=mid-1;)for(j=i;j low;j)AU=AU-1;Alow=temp;)3.冒泡排序算法思想：首先将第1个元素和第2 个元素进行比较，若前者大于后者，则两者交换位置，然后比较第2 个元素和第3 个元素。依此类推，直到第n.1个元素和第n 个元素进行过比较或交换为止。上述过程称为一趟冒泡排序，其结果是使得n 个元素中值最大的那个元素被安排在最后一个元素的位置 o 然后进行第二趟排序，即对前n.l 个元素进行同样的操作，使得前n J 个元素中值最大的那个

23、元素被安排在第n.1个位置上。一般地，第i 趟冒泡排序是从前n.i+1 个元素中的第1个元素开始，两两比较，若前者大于后者，则交换，结果使得前n.i+1 个元素中最大的元素被安排在第i+1 个位置上。显然，判断冒泡排序结束的条件是“在一趟排序中没有进行过交换元素的操作”，为此，设立一个标志变量flag,flag=1表示有过交换元素的操作，flag=0 表示没有过交换元素的操作，在每一趟排序开始前，将flag置为0,在排序过程中，只要有交换元素的操作，就及时将flag置为l o 因为至少要执行一趟排序操作，故第一趟排序时，flag=lovoid BubbleSort(int A,int n)(i

24、nt i,j,temp,flag=1;for(i=n-l;i=1&flag=1;i)(flag=0;for(j=O;j Aj+l)temp=Aj;A =AU+1;Aj+1=temp;flag=1;)4.选择排序算法思想：第i趟排序从序列的后i+1(i=l,2,.,n.l)个元素中选择一个值最小的元素与该个元素的第1个元素交换位置，即与整个序列的第i个元素交换。依此类推，直到i=n.1为止。也就是说，每一趟排序从从未排好序的那些元素中选择一个值最小的元素，然后将其与这些未排好序的元素中的第1个元素交换位置。void SelectSort(int A,int n)int i,j,min,temp;

25、for(i=0;i n;i+)min=1；for(j=i+l;j Aj)min=j;)if(min!=i)temp=Amin;Amin=Ai;Ai=temp;5.快速排序算法思想：在参加排序的序列中任意选择一个元素（通常称为分界元素或基准元素），把小于或等于分界元素的所有元素都移到分界元素的前面，把大于分界元素的所有元素都移到分界元素的后面，这样，当前参加排序的序列就被划分成前后两个子序列，其中前一个子序列中的所有元素都小于后一个子序列的所有元素，并且分界元素正好处于排序的最终位置上。然后分别对这两个子序列递归地进行上述排序过程，直到所有元素都处于排序的最终位置上，排序结束。void Quic

26、kSort(int A,int n)(QSort(A,0,n-1);)void QSort(int A,int low,int high)(int pivotloc;if(low high)(pivot=Partition(A,low,high);QSort(A,low,pivotloc-1);QSort(A,pivotloc+1,high);)int Partition(int A,int low,int high)(int pivot;pivot=A low;/从线性表的两端交替地向中间扫描while(low high)(while(low=pivot)high-;Alow=Ahigh;while(low high&Alow=1;i-)HeapAdjust(A,i,n);for(i=n-1;i=1;i)(temp=Al;Al=Ai+l;Ai+1=temp;/将 A l.i重新调整为大顶堆HeapAdjust(A,1 ,i);)void HeapAdjust(int A,int low,int high)(int i,temp;temp=Alow;for(i=2*low;i=high;i=i*2)/令i为关键字较大的记录的下标if(i high&Ai=Ai)break;else Alow=Ai;low=i;)Alow=temp;/插入