常用算法和数据结构

moreregard 贡献于2013-05-26

作者 Administrator  创建于2006-10-11 06:30:00   修改者fanglp  修改于2010-04-12 04:03:00字数81051

文档摘要:常用算法和数据结构
关键词:

第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]有序且保持原来的性质。 (3) i增1,直到i为n。 为方便描述,被查找的顺序表C类型定义如下: #define MAXSIZE 1000 /*顺序表的长度*/ typedef int KeyType; /*关键字类型为整数类型*/ typedef struct{ KeyType key; /*关键字项*/ InfoType otherinfo; /*其他数据项*/ }RecType; /*记录类型*/ typedef struct { RecType r[MAXSIZE+1]; /*r[0]空作为哨兵*/ int length; /*顺序表长度*/ }SqList; /*顺序表类型*/ 顺序存储线性表的选择排序算法如下: void Sqsort(SqList &q) { int i, j, k, temp; for(i=0;i=0 && t.key0;h/=2) for(j=h;j=0&&y.keyR[j+1].keg,则将R[j].key与R[j+1].key交换。 (2) 初始化时,排序范围是R[1...n],以后的排序范围由前一遍的扫描结果确定:当自上而下将当前排序范围内的结点执行一遍比较之后,若最后往下沉的结点是R[j],R[j]下沉到R[j+1]的位置,R[j+1]以下的结点比较后会发现它们都不再需要交换。因此,下一趟的排列范围可以缩减为从R[1]到R[j]。 (3) 整个排列过程最多执行n-1趟。若某一趟的比较没有结点交换,所有相邻结点的排列顺序都与排序要求一致,则线性表为有序的。 顺序线性存储结构下的冒泡排序算法如下: void bubblesort(SqList &q) { int j,p=q.length-1,h,t; /*p用来记录一趟排序最后下沉的结点位置*/ for(h=1;h<=p;) for(j=0;jq.r[j+1].key){ temp=q.r[j]; q.r[j]=q.r[j+1];q.r[j+1]=temp; p=j; } } 可见,对n个结点的线性表采用冒泡排序,外循环最多执行n-1趟,每一趟最多执行n-1次比较;第2趟最多执行n-2次比较;依次类推,第n-1趟最多执行1次比较。因此,整个排序过程最多执行n*(n-1)/2次比较。由于关键字相等的结点不交换,故冒泡排序算法是稳定的。 第1章 常用算法和数据结构 1.1.1.5 快速排序 快速排序(Quick Sort)的主要思路为:通过对线性表序列的一趟扫描使某个结点移到中间的某个位置,且使其左边序列的各结点的关键字都比该结点的关键字小,而其右边序列的各结点的关键字都不比该结点的关键字小,常称这样的一次扫描为“划分”。然后,对左、右序列进行同样的处理,直到所有序列均只包含一个结点为止,这样便可将原线性表排好序。 快速排序可以看做是冒泡排序的改进,冒泡排序可以看做是快速排序的退化,即每趟划分总是在同一端进行。 若设待排序的记录序列{ R1,R2,…,Rn }为R[1...n],则对其按关键值的非递减序列进行快速排序的算法如下: void QuickSort1(SqList &R, int s, int t) { /*对n个元素的数组R进行由小到大排序*/ int low, high; low=s; high=t; privotkey=R.r[s].key; R.r[0]=R.r[s]; while(lowlow && R.r[high].key>privotkey) high--; if (lownext , *mid, *midpre, *pre, *r; int temp; midpre=head; mid=p; if(!p)return 1; pre=p; p=p->next; while(p!=tail) { r=p->next; if(p->data<=head->next->data) { pre->next=r; /*断开与p结点的链接*/ midpre->next=p; /*将p结点插入到mid之前*/ p->next=mid; midpre=p; p=r ; } else { /*结点的位置保持不变*/ pre=p; p=r; } } QuickSort2(head, midpre); /*对前一部分链表进行快速排序*/ QuickSort2(mid->next,tail); /*对后一部分链表进行快速排序*/ } /*QuickSort2*/ 可见,只要充分领会顺序存储结构下的算法思想,熟悉链表存储结构就可以通过掌握顺序存储结构下的算法得到链表存储结构下的相应算法。 1.1.1.7 堆排序 首先,要认真掌握堆的定义,然后才能进一步理解建堆的算法。堆的定义为:n个关键字序列k1,k2,k3,…,kn称为堆,当且仅当该序列满足如下性质(也称堆性质):①ki≤k2i 且 k 第1章 常用算法和数据结构 i≤k2i+1 或 ②ki≥k2i 且 ki≥k2i+1(1≤i≤n/2)。满足第①种情况的堆称为小根堆,满足第②种情况的堆称为大根堆。这里仅讨论第①种情况。 本质上,堆排序在排序过程中,是将顺序表中存储的数据看成一棵完全二叉树,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最小记录。堆排序分建堆和堆调整两个过程。 建堆的过程为:堆排序的过程是一个不断从堆顶到叶子的调整过程(又称“筛选”)。从一个无序序列建堆的过程就是一个反复筛选的过程。若将此序列看成是一个完全二叉树,则最后一个非终端结点是第n/2个元素,因此筛选只需从第n/2个元素开始。 堆调整过程为:将该完全二叉树中最后一个元素替代已输出的结点。若新的完全二叉树的根结点小于左右子树的根结点,则直接输出。反之,则比较左右子树根结点的大小。若左子树的根结点小于右子树的根结点(或右子树的根结点小于左子树的根结点),则将左子树(或右子树)的根结点与该完全二叉树的根结点进行交换。重复上述过程,调整左子树(或右子树),直至叶子结点,则新的二叉树满足堆的条件。 堆排序的算法描述如下: void HeapSort(Sqlist &R) /*R.r[1...R.length]看成是完全二叉树的*/ /*顺序存储结构*/ { /*建立小根堆*/ for(i=R.length/2; i>0; i--) /*从最后一个内部结点开始调整*/ HeapAdjust(R, i, R.length); } void HeapAdjust(Sqlist & R, int i, int m) { /*i为堆调整的位置,m为堆的大小,该函数建立小根堆*/ R.r[0]=R.r[i]; for(j=2*i; j<=m; j*=2) { if(jR.r[j+1].key)++j; /*找孩子结点中关键字最小的*/ if(R.r[0].key<=R.r[j].key) /*调整结束*/ break; R.r[i]=R.r[j]; /*使得根结点的关键字小于等于左右孩子的关键字*/ i=j; } R.r[s]=R.r[0]; } 堆排序算法的时间复杂度为O(nlog2n),这是一个不稳定的排序方法。 1.1.1.8 合并排序 合并排序(Merging Sort)的基本思想是:将两个或者两个以上的有序子表合并成一个新的有序表。对于两个有序子表合并成一个有序表的2-路合并排序来说,初始时,把含有n个结点的待排序序列看做由n个长度都为1的有序子表所组成,将它们依次两两合并得到长度为2的若干有序子表,再对它们做两两合并,直到得到长度为n的有序表,排序即告 完成。 第1章 常用算法和数据结构 2-路合并排序算法如下: void mergesort(SqList &q) { SqList r; r.length=q.length; int len=1,f=0; while(len=q.length) { end=q.length-1; /*最后一个段可能不足len个结点*/ mergestep(&q,&r,start, start+len-1, end); /*相邻有序段合并*/ start=end+1; } } if(start=1;i--) { t[(1)]=a[i]; count[(a[i]/ divisor)%Radix]:=(2); } for(i=1;i<=n;i++) (3); divisor=(4); } } 基数排序的两种主要方法是:最高位优先MSD(Most Significant Digit first)和最低位优先LSD(Least Significant Digit first)。这里的程序采用最低位优先LSD方法对输入的n个整数进行排序,采用的主要思想是把各整数看成由4个16位数组成;若从低到高分别称为L1、L2、L3、L4,则执行下面步骤。 第1章 常用算法和数据结构 (1) 初始化计数器count[0...15],使各个count[i]=0(0≤i≤15)。 (2) 统计L1为0、1、 …、15的各个整数个数分别到count[0...15]。 (3) 将count[0]、count[1]、…、count[15]合并起来得到L1为j(0≤j≤15)的整数在一趟排序后的起始位置;如a[j]在count[(a[j]> divisor%) Radix]到count[(a[j]/divisor)%Radix+1]-1之间;同时L1相同的整数的前后位置没有明显的界限,只需根据读入的次序来定。 (4) 按照得到的各个整数a[i]的位置count[j]将该元素登记在相应的位置上,同时count[j]增加1,以便存放下一个和整数a[i]的L1相同的元素。 (5) 对L2、L3、L4重复上述过程。 通过仔细分析,不难得到如下答案。 (1) count[(a[i] / divisor)% Radix] (2) count[(a[i] / divisor)% Radix]+1 (3) a[i]=t[i] (4) divisor*16 进一步推广,若把整数看成八进制或其他进制,同样也能得到问题的答案。 1.1.1.10 败者树 采用败者树的目的是为了在进行最小键值的查找时减少比较次数。 败者树是一棵完全二叉树,其中每个结点的键值都取其两个子结点的键值中的较小者,因此,根结点的键值是这棵树中所有结点的键值中最小的。这就像k个参加淘汰赛的球队,胜者(值较小者)进入下一轮的比赛,根结点为冠军(值最小者)。 败者树的构造过程是:对具有k个记录的序列,首先用这k个记录作为叶结点,然后把相邻的两个结点进行比较,把键值小的记录(优胜者)作为这两个结点的父结点,按此方法自下而上一层一层地产生败者树的结点。为了节约内存空间,非叶子结点可不包含整个记录,只要存放记录的键值及指向该记录的指针即可。 败者树的根结点的值是构成败者树的元素中最小的,在后面的应用中,往往把根结点的值输出并用一个新的元素替换,要求构成新的败者树,这时只要在原来的败者树的基础上进行调整即可。调整仅在从根到新加入的叶子结点的树枝上的结点及其兄弟结点之间进行,自下而上进行比较并调整其父结点。 1.1.1.11 k路归并法 有了m个初始归并段(都是有序段),便可进行k路归并了,即将k个初始归并段采用某种方法进行归并产生一个段,这样m个初始归并段便产生多个更大的段,然后对这些段再进行归并,如此下去,直到只生成一个段为止,这个段就是最后生成的归并段。 在内存里进行k路归并的方法很多。当归并路数k较大时,为了减少合并时的比较次数,常采用败者树进行合并的方法,其合并过程如下。 (1) 用参加合并的k个有序段的第一个记录构造一棵初始败者树,该树中的根结点就是这k个记录中具有最小键值的记录。 第1章 常用算法和数据结构 (2) 把败者树根结点所代表的记录送到输出缓冲区。 (3) 输出记录所在的有序段的下一个记录代替输出记录的位置,调整败者树。 (4) 重复步骤(2)和(3),直到k个有序段的所有记录都输出为止。 对于总共有n个记录的k个有序段的合并过程,如果采用败者树进行合并,那么要选取键值最小的记录,在建立败者树时需要进行k-1次比较,此后每次调整败者树只要进行log2k次比较即可(因为树中保留了以前的比较结果)。所需总的比较次数为k+nlog2k,当n>>k时,总的比较次数约为nlog2k。 1.1.2 典型例题分析 例1 阅读以下说明和C语言函数,将应填入 (n) 处的字句写在答题纸的对应栏内。(2007年上半年试题四) 【说明】 函数sort(NODE *head)的功能是:用冒泡排序法对单链表中的元素进行非递减排序。对于两个相邻结点中的元素,若较小的元素在后面,则交换这两个结点中的元素值。其中,head 指向链表的头结点。排序时,为了避免每趟都扫描到链表的尾结点,设置一个指针 endptr,使其指向下趟扫描需要到达的最后一个结点。例如,对于图1-1(a)所示的链表进行一趟冒泡排序后,得到图1-1(b)所示的链表。 图1-1 排序 链表的结点类型定义如下: typedef struct Node {   int data;   struct Node *next; }NODE; 【C语言函数】 void sort(NODE *head) { NODE *ptr,*preptr,*endptr; int tempdata; ptr = head -> next; while (1) /*查找表尾结点*/ ptr = ptr -> next; 第1章 常用算法和数据结构 endptr = ptr; /*令 endptr 指向表尾结点*/ ptr =(2) ; while(ptr != endptr) { while((3) ) { if (ptr->data > ptr->next->data) { tempdata = ptr->data; /*交换相邻结点的数据*/ ptr->data = ptr->next->data; ptr->next->data = tempdata; } preptr =(4) ;ptr = ptr -> next; } endptr =(5) ;ptr = head->next; } } 分析:从(1)处代码中可知ptr最后应该指向表尾结点。所以(1)处应为ptr -> next。进行冒泡排序时,不断调整元素的位置,最终使最大元素放到表的最后,所以(2)处应为head->next。(3)处的循环条件应该是扫描的结点,不是最后一个结点,所以(3)处应为ptr!=endptr。ptr每向后修改一次,preptr就要修改一次,所以(4)处应为ptr,(5)处应为preptr。 答案: (1) ptr -> next (2) head->next (3) ptr!=endptr,或其他等价形式 (4) ptr (5) preptr 1.1.3 同步练习 1. 下面是一个链接存储线性表的直接插入排序函数。把未排序序列中的第一个结点插入到已排序序列中。排序完毕,链表中的结点按结点值从小到大链接,请在空缺处填上适当内容,每个空缺只填一个语句。 typedef struct node{ char data; struct node *link; }NODE; NODE *insertsort (NODE *h) { NODE *t, *s, *u, *v; s=h->link; h->link=NULL; while(s!=NULL) { 第1章 常用算法和数据结构 for(t=s, v=h; v!=NULL && v->datadata; (1), (2)); s=s->link; if(v==h) (3); else (4) ; (5) ; } return h; } 2. 请仔细阅读下面的堆排序算法。待排序记录存储在一维数组中,说明如下: typedef struct node{ int key; datatype info; }Node; typedef Node[n+1] heaptype; 函数heapsort的功能是将数组heap中的前n个记录按关键码值递减的次序排序。heapsort调用sift函数,sift函数的参数heap、h和r具有如下的含义:调用sift函数时,以heap[h+1], heap[h+2], …, heap[r/2]为根的子树已经成为堆;sift函数执行后,以heap[h], heap[h+1], heap[h+2], …, heap[r/2]为根的子树都成为堆。 sift(heaptype &heap, int h, int r) { int i, j, finish; Node x; i=h; x=heap[i]; j=2*i; finish=0; while( (1) ) { if(jheap[j+1].key) j++; if(x.key>heap[j].key) { (2); } else finish=1; } (3); } heapsort(heaptype &heap, int n) { int h, r, i, j; Node x; for(h=n/2; h>=1; h--) (4); for(r=n; r>=2; r--) 第1章 常用算法和数据结构 { x=heap[1]; heap[1]=heap[r]; heap[r]=x; (5); } } (1) 请在sift函数和heapsort函数的空缺处填入适当内容,使它们能正确执行。 (2) 如果调用heapsort函数的参数值n=10,那么在heapsort的执行过程中sift函数被调用了多少次? 3. 下面是一改进了的快速排序算法,试补充其中的空白语句,并分析该算法所需的最大递归空间是多少。 qsort(Sqlist &R, int m, int n) /*R.r[m].key=k)j--; if(iR.r[j]; } R.r[m]<-->R.r[i]; if(n-j>=j-m) { qsort(R, (1) , (2) ); (3) ; } else{ qsort(R, (4) , (5) ); (6) ; } } } 4. 下面的排序算法的思想是:第一趟比较将最小的元素放在r[1]中,最大的元素放在r[n]中;第二趟比较将次小的放在r[2]中,将次大的放在r[n-1]中;依次类推,直到待排序列递增有序(注:<-->代表两个变量的数据交换)。 void sort(sqlist &r, int n) { i=1; 第1章 常用算法和数据结构 While( (1) ) { min=max=i; for(j=i+1; (2) ; ++j) { if( (3) )min=j; else if(r[j].key>r[max].key)max=j; } if( (4) )r[min]<-->r[i]; if(max!=n-i+1) { if( (5) )r[min]<-->r[n-i+1]; else (6) ; } i++; } }//sort 5. 选择排序,试补充其中的空白语句。 void selectionsort( datatype A[], int N) { for(int last= (1) ; last>=1; last--) int L=indexoflargest(A, last+1); datatype temp; temp= (2) ; A[L]=A[last]; A[last]= (3) ; } int indexoflargest(datatype A[], int size) { int indexsofar= (4) ; for(int currentindex=1; currentindexA[indexsofar]) (5) ; } return (6) ; } 1.1.4 同步练习答案 1. 分析:本题的主要思路是:将当前结点插入到该结点前的有序单链表中,直到当前结点为空。在将当前结点插入到该结点前的有序单链表的过程类似顺序表的策略,从单链表的表头开始查找,直到找到该结点应插入的位置,然后完成插入任务。 答案: (1) u=v 第1章 常用算法和数据结构 (2) v=v->link (3) h=t (4) u->link=t (5) t->link=v 2. 分析:本题的堆排序的功能是将数组heap中的前n个记录按关键码值递减的次序排序,因此要构造一个“小根堆”,需先选择一个关键字作为最小的记录,并与序列中最后一个记录交接,然后对序列中前n-1个记录进行筛选,重新将其调整为一个“小根堆”,如此反复直至排序的结束。 答案:依据上述的分析,本题的答案如下。 (1) j≤r && !finish (2) h[i]=h[j];h[j]=x; i=j (3) j=2*j (4) sift(h,k,n) (5) sift(h,1,r-1) 若n=10,那么sift共被调用了5+9=14次。 3. 分析:本题修改的快速排序算法相对1.1.1.5中的快速排序算法而言,多了对划分后所得两个子序列的长度进行判断的if复合语句,进而先对长度较短的子序列进行快速排序,此目的是为了将快速排序的运行栈空间降为O()。 答案:依据上述分析,本题的答案如下。 (1) m (2) j-1 (3) m=j+1 (4) j+1 (5) n (6) n=j-1 4. 分析:仔细分析,可以看出本题采用的算法是选择排序算法的变种,传统的选择排序算法是每次从未排序序列中找一个最小关键字值的记录;这里的算法是每次找到一个最小关键值的记录,同时找到一个最大关键字值的记录,使两端有序。 答案:依据上述分析,可得问题的如下答案。 (1) I<=n/2 (2) j<=n-i+1 (3) r[j].keyr[n-i+1] 5. 分析:本题采用的算法是选择排序算法的变形,第一次从所有的元素中找一个最大的元素与A[N-1]交换;第二次从剩下的元素中找一个最大的元素与A[N-2]交换;依次类推,直到所有的元素都递增有序。 答案:依据上述分析,本题的答案如下。 (1) N-1 (2) A[L] (3) temp (4) 0 (5) indexsofar=currentindex (6) indexsofar 1.2 查 找 算 法 1.2.1 考点辅导 1.2.1.1 查找的基本概念 所谓“查找”(检索)就是在一个含有众多数据元素(记录)的查找表中找出某个“特定的”数据元素。查找表是一种非常重要的数据结构,是由同一类型的数据元素(记录)构成的集合。在查找表中,通常通过查找其关键字是否等于给定值来确定查找是否成功。若查到其关键字等于给定值的记录,则称“查找成功”,否则,称“查找失败”。 对查找表而言,除了按关键字查找外,查找表的插入和删除是对查找表进行的另两个基本操作。 关键字是数据元素(记录)中某个数据项的值,可以标识一个记录,若能惟一标识,则称为主关键字,否则,称为次关键字。 考生特别要注意的是:在查找中是和关键字进行比较,而不是和数据元素进行比较,因而在算法描述中要体现关键字比较的特征。同时,考生要特别注意查找在顺序存储结构和链式存储结构上的区别。 查找的效率通过平均检索长度(ASL)和所需的辅助空间来确定。在查找其关键字等于给定值的过程中,需要与给定值进行比较的关键字个数的期望值称为检索成功时的平均检索长度。 1.2.1.2 静态查找 静态查找的算法有顺序查找、折半查找、分块查找和静态树查找等,其中顺序表上的顺序查找、折半查找是静态查找的重点。被查找的顺序表C类型定义如下。 第1章 常用算法和数据结构 #define MAXSIZE 1000 /*顺序表的长度*/ typedef int KeyType; /*关键字类型为整数类型*/ typedef struct{ KeyType key; /*关键字项*/ InfoType otherinfo; /*其他数据项*/       }RecType; /*记录类型*/ typedef struct { RecType r[MAXSIZE+1]; /*r[0]空作为哨兵*/ int length; /*顺序表长度*/ }SqList; /*顺序表类型*/ 1.顺序查找 顺序查找的基本思想是:从表中第n个(第1个)记录开始,逐个进行记录的关键字与给定值的比较,若某个记录的关键字和给定值比较相等,则查找成功,找到所查记录;反之,若直到第1个(第n个)记录,其关键字和给定值比较都不等,则表明该表中没有所查的记录,查找不成功。 顺序查找的算法描述如下: int SeqSearch(SqList R, KeyType k) /*在R.r[1..R.length]中查找关键字*/ /*为k的记录*/ { /*从后往前查找*/ int i; R.r[0].key=k; /*查找一定结束*/ for(i=R.length; i>=0&&R.r[i].key!=k; i--); if(i<=0) return -1; /*查找不成功*/ else return i; } 可见,在查找中与关键字的比较次数ci取决于所查记录在表中的位置,如查找表中第n个记录,仅需比较一次;而查找表中第1个记录时,需比较n次,即ci=n-i+1。因此,在等概率的情况下,成功查找时的顺序查找的平均查找长度为: 即查找成功时的平均比较次数约为表长的一半。若k值不在表中,则须进行n+1次比较才能确定查找失败。 2.折半查找 若顺序表中元素已按关键字有序排列,检索时不必顺序检索,而是用待查关键字与中间位置的元素的关键字进行比较,若相等,则检索成功;若待查关键字较小,则在由中间位置分开的左子表中查找,否则,在右子表中进行查找。如此下去,直至检索成功或检索失败。 折半查找的算法描述如下: int BinSearch(SqList R, KeyType k) /*在有序表R.r[1...R.length]中检索关键字为k的记录*/ 第1章 常用算法和数据结构 /*若检索成功,返回该记录的位置;否则返回-1*/ { int l=1; h=R.length; while (l<=h) { i=(l+h)/2; /*取中间位置*/ if (R.r[i].key==k) return(i); /*算法结束*/ else if (R.r[i].key>k) h=i-1; /*在左子表查找*/ else l=i+1; /*在右子表查找*/ } return(-1); } 折半查找的过程可用二叉树来描述,中间结点是二叉树的根,左子表相当于左子树,右子表相当于右子树,由此得到的二叉树便为描述折半查找的判定树。折半查找的过程是走了一条从根结点到叶子结点的过程,不论检索成功与失败,查找长度均不超过树的高度,其平均性能为h= [log2(n+1)]。 折半查找速度快,但表必须有序,且频繁插入和删除不方便。它适合表中元素很少变化而检索频繁的情况;顺序表检索适于检索少而表中元素频繁变化的情况。 3.分块查找 分块查找综合了顺序查找和折半查找的优点,既有动态结构,又适于快速查找。分块查找的基本思想是:将待查找文件等长地分为若干个子文件(最后一个子文件长度可能会小)。子文件内的元素无序,但子文件之间有序,即第一个子文件的最高关键字小于第二个子文件的所有记录的关键字,第二个子文件的最高关键字小于第三个子文件的所有记录的关键字,依次类推。再建立一个索引表(文件),文件中的每个元素含有各个子文件的最高关键字和各个子文件中第一个元素的地址(下标),索引文件按关键字有序。 分块查找过程分两步:第一步是在索引表中确定待查记录所在的块,可以顺序查找或折半查找;第二步是在块内顺序查找。 设待检索文件有n个记录,平均分成b块,每块有s个记录。若只考虑检索成功的概率,且在块内和索引表中均用顺序检索,则平均查找长度为: ASLbs=Lb+Lw==(s2+2s+n)/(2s) 其中,Lb为确定块的平均查找长度;Lw为块内查找次数。 若s=,则平均查找长度取最小值:+1。 若对索引表采用二分法检索,则平均查找长度为: E(n)=Eb+Ew=élog2(b+1)ù+ 1.2.1.3 动态查找 动态查找也称树表查找,可执行动态查找的数据结构有二叉排序树、B-树和B+树等。 第1章 常用算法和数据结构 动态查找表的特点是:表结构本身是在查找过程中动态生成的,即对于给定值key,若表中存在其关键字等于key的记录,则在查找成功后返回,否则插入关键字等于key的记录。考生重点掌握二叉排序树,因此这里主要介绍二叉排序树。 二叉排序树(简称BST)或者是一棵空树,或者是具有下列性质的二叉树。 l 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值。 l 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。 l 它的左、右子树也分别为二叉排序树。 从BST的性质可推出二叉排序树的另一个重要性质:按中序遍历该树所得到的中序序列是一个递增有序序列。 二叉排序树的查找方法:类似于折半查找,当二叉排序树不空时,首先将给定值k与根结点的关键字进行比较,若相等则查找成功;否则依k的大小在左子树或右子树上查找。可见,二叉排序树的查找是一个递归过程。 二叉排序树的构造:二叉排序树由依次输入的数据元素的序列构造而成。每读入一个元素,建立一个新的结点,并按下列原则插入结点。 l 若二叉排序树为空树,则新结点为二叉排序树的根结点。 l 若二叉排序树非空,则新结点的值与根结点比较,若小于根结点,则插入到左子树;否则插入到右子树。 二叉排序树的结点删除主要有以下三种情况: l 若删除的结点为*p,其双亲为*f,如果*p没有左右孩子,则可直接删除*p,修改*f的指针即可。 l 若*p结点只有左子树或只有右子树,此时只要令其左子树或右子树直接成为其双亲结点*p的左子树即可。  l 若*p结点的左子树和右子树均不空,如果希望中序遍历该二叉树得到的序列的相对位置在删除结点前后不变,则可采用如下方法:其一,令*p的左子树为*f的左子树,而*p的右子树为*s的右子树。其中*s为*p左子树中最右边的一个结点。其二,令*p的直接前驱(或直接后继)替代*p,然后再从二叉排序树中删除它的直接前驱(或直接后继)。这两种删除方法都能使原二叉排序树的中序遍历结果中结点的先后次序保持不变。 就平均时间性能而言,二叉排序树上的查找和折半查找相似。但就维护表的有序性而言,前者更有效,因为无需移动记录,只需修改指针即可完成对二叉排序树的插入和删除操作,且其平均的执行时间均为O(log2n)。 有关平衡二叉树、B-树和B+树的知识,考生可参考相关参考文献。 1.2.1.4 散列查找(或哈希查找) 在记录的存储位置与它的关键字之间建立一个确定的对应关系f,通过这个对应关系f找给定值k的像f(k),进行查找的方法为散列方法。称这个关系f为哈希函数,按此建立的表为哈希表。 设哈希表是一个地址为0~(n-1)的向量,冲突是指由关键字得到的哈希地址为j∈[0, n-1]的位置上已存有记录,而冲突处理就是为该关键字的记录找到另一个空的哈希地址。 第1章 常用算法和数据结构 1. 哈希函数的构造方法 哈希函数的构造方法有如下几种。 l 直接定址法:取关键字或关键字的某个线性函数值为哈希地址,即:H(key)=key 或 H(key)=a*key+b;其中a和b为常数。 l 数字分析法:假设关键字是以r 为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。 l 平方取中法:取关键字平方后的中间几位为哈希地址。 l 折叠法:将关键字分割成位数相同的几部分,然后取这几部分的叠加和。 l 除余数法:取关键字被某个不大于哈希表表长m 的数p 除后所得余数为哈希地址,即:H(key)=key mod p,p≤m(注:p的选择很重要)。 l 随机数法:选择一个随机函数,取关键字的随机函数值为它的哈希地址。即:H(key)=random(key)。 2.处理冲突的方法 处理冲突的方法有如下几种。 l 开放地址法:Hi=(H(key)+di) mod m,i=1, 2, 3, …, n,其中,H(key)为哈希函数,m为哈希表表长,di为增量序列。若di=1, 2, …, n,则称线性探测再散列;di=12, -12, 22, -22, …, n2, -n2,则称二次探测再散列;di=伪随机数序列,则称伪随机探测再散列。 l 再哈希法:Hi=RHi(key), i=1, 2, …, n,其中,RHi均是不同的哈希函数,即在同义词产生地址冲突时计算另一个哈希函数地址,直到冲突不再发生。这种方法不易产生聚集,但增加了计算的时间。 l 链地址法:将所有关键字为同义词的记录存储在同一线性链表中。 l 建立一个公共溢出区:关键字和基本表中关键字为同义词的记录,一旦发生冲突,就将其填入溢出表。 3. 哈希表查找的性能分析 给定k值,根据造表时设定的哈希函数求得哈希地址,若表中此位置没有记录,则查找不成功;否则比较关键字,若和给定值相等,则查找成功;若不等,则根据造表时设定的处理冲突的方法查找下一个地址,直至某个位置上表为空或关键字比较相等为止。可见,比较关键字的个数取决于三个因素:哈希函数、处理冲突的方法和哈希表的装填因子。 哈希表的平均查找长度不是对象个数n的函数,而是装填因子(=n/m)的函数。线性探测法成功查找的平均查找长度为(1+1/(1-))/2,而不成功查找的平均查找长度为(1+1/(1-)2)/2;二次探测再散列法的成功查找的平均查找长度为,而不成功查找的平均查找长度为1/(1-);链地址法的成功查找的平均查找长度为1+/2,而不成功查找的平均查找长度为。 第1章 常用算法和数据结构 1.2.2 典型例题分析 例1 阅读以下说明和 C 函数,将应填入 (n) 处的字句写在答题纸的对应栏内。(2009年下半年试题二) 【说明1】 函数 Counter ( int n , int w[ ])的功能是计算整数n的二进制表示形式中1的个数,同时用数组w记录该二进制数中1所在位置的权。 例如,十进制数22的二进制表示为10110。对于该二进制数,1的个数为3,在w[0]中存入2 (即21),w[1]中存入4 (即 22),w[2]中存入16 (即 24)。 【C函数1】 int Counter ( int n , int w[ ] ) { int i = 0 , k = l ; while ( (1) ) { if ( n % 2 ) w [ i + + ] = k ; n = n / 2 ; (2) ; } return i; } 【说明2】 函数 Smove (int A[] , int n )的功能是将数组中所有的奇数都放到所有偶数之前。其过程为:设置数组元素下标索引i(初值为0)和j(初值为n-1),从数组的两端开始检查元素的奇偶性。若A[i]、A[j]都是奇数,则从前往后找出一个偶数,再与A[j]进行交换;若A[i]、A[j]都是偶数,则从后往前找出一个奇数,再与A[i]进行交换;若A[i]是偶数而A[j]是奇数,则交换两者,直到将所有的奇数都排在所有偶数之前为止。 【C函数2】 void Smove (int A[] , int n) { int temp , i= 0 , j = n-l ; if ( n < 2 ) return; while ( i< j ) { if ( A [i]%2 == l & & A[j] % 2 ==l ) { (3) ; } else if ( A[i] % 2 == 0 & & A[j]% 2==0 ) { 第1章 常用算法和数据结构 (4) ; } else { if ( (5) ) { temp = A[i] ; A[i] = A[j] ; A[j]= temp ; } i++,j++ ; } } } 分析:由说明1中可知函数 Counter ( int n , int w[ ])的功能是计算整数 n 的二进制表示形式中1的个数,同时用数组 w 记录该二进制数中 1 所在位置的权。所以(1)处循环判断条件应为n!=0,即当n不为0时进行操作,每执行一次k的值就增加一倍,所以(2)处应为k=k*2 或 k*=2 。由函数Smove ( int A[] , int n )的功能可知,若 A [i]、A[j]都是奇数(A [i]%2 == l & & A[j] % 2 ==l),则从前往后找出一个偶数,再与 A[j]进行交换,所以此时应将A [i]继续向后查找(即i++),而 A[j]保持不变,留待A [i]为偶数时与之交互,同理,若 A [i]、 A[j]都是偶数,则A[j]向前查找(j--),A[i]保持不变,留待A[j]为奇数时与之交互,若 A [i]是偶数而A[j]是奇数,则交换两者,所以(3)处应为i++,(4)处应为j--,(5)处应为a[i]%2==0&& a[j]% 2==1。 答案: (1) n或n!=0 (2) k=k*2、k*=2 或其他等价表达式 (3) i++或其他等价表达式 (4) j--或其他等价表达式 (5) a[i]%2==0&&a[j]%2==1或其他等价表达式 例2 阅读以下说明和 C 函数,将解答填入答题纸的对应栏内。(2009年下半年试 题四) 【说明】 函数del_substr ( S , T )的功能是从头至尾扫描字符串S,删除其中与字符串T相同的所有子串,其处理过程为:首先从串S的第一个字符开始查找子串T,若找到,则将后面的字符向前移动将子串T覆盖掉,然后继续查找子串T,否则从串S的第二个字符开始查找,依此类推,重复该过程,直到串s的结尾为止。该函数中字符串的存储类型SString定义 如下: typedef struct { char * ch ; /*串空间的首地址*/ int length ; /*串长*/ } SString ; 【C函数】 void del _ substr ( SString * S , SString T ) 第1章 常用算法和数据结构 { inti , j ; if ( S->length < l || T . length < l || S->length < T . length ) return; i=0 ; /*i为串S中字符的下标*/ for ( ; ; ) { j = 0 ; /*j 为串 T 中字符的下标*/ While ( i < S->length & & j < T . length ) { /*在串 S 中查找与 T 相同的子串*/ if ( S->ch[i]== T . ch[j] ) { i++; j++; }else { i= (1) ; j = 0 ; /*i值回退,为继续查找T做准备*/ } } If( (2) ) { /*在S中找到与T相同的子串*/ i= (3) ; /*计算S中子串T的起始下标*/ for ( k = i + T. length ; k < s->length ; k + + ) /*通过覆盖子串 T 进行删除*/ S-> ch[ (4) ] =S-> ch[k] ; S->length = ( 5 ) ; /*更新S的长度*/ } else break ; /*串S中不存在子串T*/ } } 分析:进行查找时,如果T中前j个字符和S中从下标i开始的j个字符相同,则i都会增加到i+j,如果T中第j+1个和S中下一个字符不同,则查找结束,此时需将i的值(此时已是i+j)回退到此遍历进行前的值(即i)的下一个字符位置即i-j+1,并开始新一轮的遍历查找,所以空(1)处应为i-j+1。一轮查找结束后,如果j的值等于T的长度,表明S中存在子字符串和T相同,因为只要其中有一个字母不同,j就会清零一次,最后的值就一定会小于T的长度,所以空(2)处应为j==T.length。找到时,同时i的值也已经增加了T的长度,所以要计算 S 中子串 T 的起始下标只需i减去T的长度即可,所以空(3)处应为i-T.length 或者i-j。通过覆盖子串 T 进行删除时,从i + T. length到s->length,只需将每个字符替换到其前j处,即空(4)处应为k-j。替换后,将S的长度减去T的长度即可更新S的长度。所以空(5)处应为s->length-T.length。 答案: (1) i-j+1 (2) j==T.length (3) i-T.length或i-j (4) k-j (5) s->length-T.length 第1章 常用算法和数据结构 例3 阅读以下说明、C函数和问题,将解答填入答题纸的对应栏内。(2009年上半年试题三) 【说明】 二叉查找树又称为二叉排序树,它或者是一棵空树,或者是具有如下性质的二叉树: l 若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值; l 若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值; l 左、右子树本身就是二叉查找树。 设二叉查找树采用二叉链表存储结构,链表结点类型定义如下: typedef struct BiTnode { int key_value ; /*结点的键值,为非负整数*/ struct BiTnode * left , * right ; /*结点的左、右子树指针*/ } * BSTree ; 函数find_key ( root , key )的功能是用递归方式在给定的二叉查找树(root指向根结点)中查找键值为key的结点并返回结点的指针;若找不到,则返回空指针。 【C函数】 BSTree find _ key ( BSTree root , int key) { If( (l) ) return NULL ; else if(key==root->key_value) return (2) ; else if(keykey_value) return (3) ; else return (4) ; } 【问题1】请将函数find_key中应填入(1)到(4)处的字句写在答题纸的对应栏内。 【问题2】若某二叉查找树中有n个结点,则查找一个给定关键字时,需要比较的结点个数取决于 (5) 。 分析:依题意,当遍历到叶子节点的左右子树时递归结束,返回NULL,所以空(1)处应为root==NULL。在进行查找的过程中,如果key等于root的键值,则root就是所要查找的结点,所以空(2)处应为root。依题意若它的左子树非空,则其左子树上所有结点的键值均小于根结点的键值;若它的右子树非空,则其右子树上所有结点的键值均大于根结点的键值,所以如果key小于root的键值,应查询其左子树,大于root则查询其右子树,所以空(3)和空(4)处分别为find_key(root->left, key)和find_key(root->right, key)。若某二叉查找树总有n个结点,则查找一个的给定关键字时,需要比较的结点个数取决于关键字所在结点的层数和二叉树的高度。因为若结点存在,层次越高,查找次数就越多,若结点不存在,则就要遍历整个树。 答案: (1) root==NULL 第1章 常用算法和数据结构 (2) root (3) find_key(root->left, key) (4) find_key(root->right, key) (5) 关键字所在结点的层数和二叉树的高度 1.2.3 同步练习 1. 在下列算法中画横线的位置上填空,使之成为完整、正确的算法。 算法说明:已知r[1...n]是n个记录的递增有序表,用折半查找法查找关键字(key)为k的记录。若查找失败,则输出“failure”,函数返回值为0;否则输出“success”,函数返回值为该记录的序号值。 int binary search(struct recordtype r[], int n, keytype k) /*r[1...n]为n个记录的递增有序表,k为关键字*/ { int mid, low=1, hig=n; while(low<=hig) { mid= (1) ; if(kdata) { if(d < ptr->data) (1) ; else (2) ; } return (3) ; } 3. 阅读下列函数说明和C代码,请填入 (n) 处的字句。(2002年下午试题五)设二叉树的结点数据类型为: typedef struct node{ char data; struct node *left; struct node *right: }BTREE; 【说明】 函数void SortTreeInsert(BTREE **tree,BTREE*s)采用递归方法,将结点s插入以*tree为根结点指针的二叉排序树(二叉查找树)中。 【函数】 void SortTreeInsert(BTREE **tree,BTREE *S) { if(*tree == NULL) *tree=S; else if(S->data<(*tree)->data) SortTreelnsert( (1) , S); else if(S->data>(*tree)->data) SortTreelnsert( (2) , S); } 4. 阅读以下说明和 C 语言函数,将应填入 (n) 处的字句写在答题纸的对应栏内。(2005年上半年下午试题四) 【说明】 假设一个剧场有N*N个座位,顾客买票时可以提出任意有效的座号请求。下面用二维数组a[N][N]模拟剧场中的座位,a[i][j]等于0表示第i排第j列(0≤i , j≤N-1)的票尚未售出。 函数int Find ( int a[][N] , int R , int *row , int *col )的功能是:在部分票已售出的情况下,找出剧场中的R*R个空座位,要求这些座位的排列形成一个正方形。若找到满足要求的一个座位排列,则函数返回1,并算出该正方形左上角的行、列号;若未找到,返回0。 例如,一个7×7个座位的剧场如图1-2(a)所示,已售出部分座位的剧场如图(b)所示,图中阴影部分表示已售出的座位,从图1-2(b)中找出3×3正方形空座位,如图1-2(c)中斜线区所示。 【函数】 第1章 常用算法和数据结构 int Find ( int a[][N] , int R , int *row , int *col ) { int i,j,k,c,t; int FOUND = 0; for ( i=0 ; !FOUND && i=R ) /*查找第i排连续的R个空座位*/ { for ( c=0 ; c < R ; c++ ) /*查找其余的R*(R-1)个座位*/ { for ( t = 1 ; t < R ; t++ ) if (a[ (3) ] [j+c] !=0 ) break; if ( t typedef struct{ 第1章 常用算法和数据结构 int Temp; /*环境温度*/ double Ratio; /*传感器的输出值*/ }CURVE; #define ITEMS 7 double GetK(int,CURVE *,int); void main() { int Degree; double k; CURVE Curve[ITEMS]={-40,0.2},{-20,0.60},{-10,0.8},{0,1.0}, {10,1.17},{30,1.50},{50,1.8}};  printf("环境温度校正系数\n"); for(Degree = -40; Degree <= 50; Degree++) { k = GetK(Degree,Curve,ITEMS); printf("%3d %4.2f\n",Degree,k); } } double GetK(int Temp,CURVE *p,int n) { /*用二分法在n个元素的有序表p中查找与Temp对应的传感器输出值*/ int low,high,m; double Step; low = 0; high = n-1; if ((Temp < p->Temp)||(Temp > (p+high)->Temp)) return 0.0; /*超出温度范围时返回0.0*/ while (low <= high) { m= (1) ; if (Temp == (p+m)->Temp) return (2) ; if (Temp < (p+m)->Temp) high = m-1; else low = (3) ; } p += high; Step = ( (4) ) / ((p+1)->Temp - p->Temp); return 1.0 / (p->Ratio + Step * ( (5) )); } 1.2.4 同步练习答案 1. 分析:依据折半查找算法的思路,不难得到本题的答案。 答案: (1) (low+hig)/2 (2) hig=mid-1 第1章 常用算法和数据结构 (3) printf("success\n") (4) return mid (5) low=mid+1 (6) printf("failure\n") (7) return 0 2. 分析:依据二叉排序树的定义,其左子树中的所有结点的关键字值都小于根结点的关键字值,而其右子树中所有结点的关键字值都大于根结点的关键字值。因此当关键字值比当前结点的关键字值小时,转向左子树查找,否则转向右子树查找。于是,空(1)填“ptr=ptr->left”;空(2)填“ptr=ptr->right”;空(3)填“ptr”。 答案: (1) ptr = ptr->left (2) ptr = ptr->right (3) ptr 3. 分析:二叉排序树的结点插入是在其叶子结点上进行的,当要插入的结点的关键字小于当前结点的关键字时,则结点插入到其左子树中,否则插入到结点的右子树中。因此 空(1)填“&((*tree) ->left)”,空(2)填“&((*tree) ->right)”。这里要注意的是实参和形参的类型要一致。 答案: (1) &((*tree)->left) (2) c&((*tree)->right) 4. 分析:根据题目中的说明可知,函数Find ( )的功能是:在部分票已售出的情况下,找出剧场中的R*R个空座位,要求这些座位的排列形成一个正方形。计算过程是:在有标记的方阵中找出一个R*R的尚未标记的子方阵。根据第4行的代码及注释“for ( i=0 ; !FOUND && i high ),则可确定查找失败。 空(1)处应填:“(low+high)/2”。 空(2)处:按题中要求,若找到了相应的温度值,则按相应的Ratio的值求倒数得到K值,故空(2)处应填:1.0/(p+m)->Ratio。 空(3)处应填:m+1。 空(4)处:根据题中描述的线性插值再求倒数的计算方法和p+=high,可得到Step的表达式:Step=((p+1)->Ratio - p->Ratio)/(Tp1-Tp2),故空(4)处应填:(p+1) ->Ratio - p->Ratio 空(5)处:根据题中描述的线性插值再求倒数的计算方法和p+=high,可得到K的表达式:K=1.0/(p+m) ->Ratio+Step*(Temp-p->Temp)),故空(5)处应填:Temp-p->Temp 答案: (1) (low+high)/2 (2) 1.0/(p+m) ->Ratio (3) m+1 (4) (p+1) ->Ratio - p->Ratio (5) Temp - p->Temp 1.3 数 据 结 构 1.3.1 考点辅导 1.3.1.1 线性表 1.线性表的顺序存储结构 1) 顺序表 线性表的顺序存储结构采用一组连续的存储单元依次存储线性表中的各数据元素。建立一个数组V,线性表的长度为N,V[i]表示第i个分量,第i个分量是线性表中第i个元素ai在计算机存储器中的映像,即V[i]= ai。若线性表的第一个元素的存储地址是LOC(a1),每个元素用L个存储单元,则表的第i个元素的存储地址为:LOC(ai)=LOC(a1)+(i-1)*L。 假设线性表的数据元素的类型为ElemType(在实际应用中,此类型应根据实际问题中出现的数据元素的特性具体定义,如为int、float类型等),则线性表的顺序表的C语言 第1章 常用算法和数据结构 描述如下: #define MAXSIZE /*顺序表的长度为对MAXSIZE定义的值*/ typedef struct { ElemType data[MAXSIZE]; int len; /*线性表数据元素的个数*/ }Sqlist; 从中可以看出,顺序表是由数组data和len两部分组成的。为了反映data和len之间的关系,上述类型定义中将它们说明为结构体类型Sqlist的两个域。这样,Sqlist类型就完全描述了顺序表的组织。 2) 基本运算在顺序表上的实现 由于C语言中数组的下标是从0开始的,所以,在逻辑上所指的“第k个位置”实际上对应的是顺序表的“第k-1个位置”。这里仅给出在顺序表上线性表的插入和删除函数。 (1) 插入函数。 insert(v, n, i, x) /*该算法在长度为n的线性表L的第i个位置插入元素x*/ int n, i; float x, v[]; { if ((i<0)||(i>n+1)) /*插入位置非法*/ printf("error"); else for(j=n;j>=i;j--) v[j+1]=v[j]; v[i]=x; n++; } (2) 删除函数。 delete (L,n,i) /*该算法删除长度为n的线性表L的第i个位置的元素x*/ int n, i; float L[]; { if ((i>=n)||(i<0)) printf("error"); else { for (j=i;jnext=NULL; } 2) 插入函数insert(Slink *head, int i , ElemType x) 插入函数的设计思想是:创建一个data域值为x的新结点*p,然后插入到head所指向的单链表的第i个结点之前。为保证插入正确有效,必须查找到指向第i个结点的前一个结点的指针,主要的时间耗费在查找上,因而在长度为n的线性单链表中进行插入操作的时间复杂度为O(n)。插入函数的语句如下: 第1章 常用算法和数据结构 insert(Slink *head, int i, ElemType x) { Slink *p, *pre, *q; int j=0; p=( Slink *) malloc(sizeof(Slink )); p->data=x; /*生成p结点,x是元素的值*/ pre=head; /*pre指向待插入结点的前驱结点*/ q=head->next; /*q指向当前比较结点*/ while (q&&jnext; j++; } if(j!=i-1||i<1)return 0; /*插入不成功*/ else{ p->next=q; /*将p结点插入链表*/ pre->next=p; } return 1; /*插入成功*/ } 3) 删除函数delete(Slink *head, int i , ElemType * x) 删除函数的设计思想是:线性链表中元素的删除要修改被删元素前驱的指针,回收被删元素所占的空间。主要的时间耗费在查找上,因而在长度为n的线性单链表进行删除操作的时间复杂度为O(n)。删除函数的语句如下: delete(Slink *head,int i,ElemType x) /*删除第i个结点,并通过x返回值*/ { Slink *p, *q; int j=0; p=head; while(p->next && jnext; j++; } if(!(p->next)|| j>i-1) return 0; /*删除位置不合适*/ q=p->next; /*删除并释放结点*/ p->next=q->next; x=q->data; free(q); return 1; } 4) 查找函数get(Slink *head, int i) 查找函数的设计思想是:在线性链表中查找元素要找元素前驱的指针。在长度为n的线性单链表进行查找操作的时间复杂度为O(n)。查找函数的语句如下: 第1章 常用算法和数据结构 Slink * get(Slink *head, int i) /*查找第i个结点*/ { Slink *p; int j=0; p=head; while(p->next&&jnext; j++; } if(!(p->next)|| j>i-1) return NULL; /*查找位置不合适*/ return p->next; } 5) 求单链表表长函数Length(Slink *head) 求单链表长函数的设计思想是:通过遍历的方法,从头数到尾,即可得到单链表的表长。求单链表表长函数的语句如下: int Length (Slink *head ) { int len=0 ; Slink *p; p=head; /*设该表有头结点*/ while(p->next) { p=p->next; len++; } return len; } 3.带头结点的单链表和不带头结点的单链表的区别 带头结点的单链表和不带头结点的单链表的区别主要体现在其结构和算法操作上。 在结构上,带头结点的单链表不管链表是否为空,均含有一个头结点;而不带头结点的单链表不含头结点。 在操作上,带头结点的单链表的初始化为申请一个头结点,且在任何结点位置进行的操作算法一致;而不带头结点的单链表让头指针为空,同时其他操作要特别注意空表和第一个结点的处理。下面列举带头结点的单链表插入操作和不带头结点的插入操作的区别。 定义单链表的结点类型如下: typedef struct node { ElemType data; /*结点的数据域*/ struct node *next; /*结点的指针域或链域*/ } Slink; 1) 带头结点的单链表插入函数insert(Slink *head, int i , ElemType x) 带头结点的单链表插入函数的设计思想是:创建一个data域值为x的新结点*p,然后插入到head所指向的单链表的第i个结点之前。为保证插入正确有效,必须查找到指向第i个结点的前一个结点的指针,主要的时间耗费在查找上,因而在长度为n的线性单链表中进行插入操作的时间复杂度为O(n) 第1章 常用算法和数据结构 。 2) 不带头结点的单链表插入函数insert(int i , ElemType x) 不带头结点的单链表插入函数的设计思想是:创建一个data域值为x的新结点*p,然后插入到单链表的第i个结点之前。由于链表不带头结点,所以当i=1时的插入操作的算法实现与i>1时是有差别的,必须单独处理。为保证插入正确有效,必须查找到指向第i个结点的前一个结点的指针,主要的时间耗费在查找上,因而在长度为n的线性单链表中进行插入操作的时间复杂度为O(n)。 可见,带头结点的单链表插入操作和不带头结点的插入操作在算法实现上有很大的区别,主要体现在初始化、能否插入成功的判别及插入时的操作上,在带头结点的单链表上插入在任何位置上都是相同的,而在不带头结点单链表的第一个结点和其他结点前插入操作是不同的。 对于带头结点的单链表和不带头结点的单链表在其他操作上的区别可类似得到。 4.链表的指针修改次序对结果的影响 链表的指针修改必须保持其逻辑结构的次序,否则将违背线性表的特征,尤其是进行插入和删除操作。下面通过双向链表的插入操作来说明,若在图1-3所示的P所指向的结点之前插入一个S所指向的结点,则需进行指针的修改,修改指针的策略有两种,如图1-4和图1-5所示,指针的修改次序为1,2,3,4。根据线性表的性质可知,图1-4可保证指针修改成功;而图1-5中指针修改不成功,主要原因是其首先将P的前驱指向S,这样P结点的原前驱结点就不能找到了,因而指针修改步骤3和4不成立。 图1-3 双向链表的结点插入前 图1-4 指针的修改策略1 图1-5 指针的修改策略2 第1章 常用算法和数据结构 可见,指针的修改次序是链表插入成功与否的关键因素之一;同理,在进行结点的删除时也同样需要主要指针的次序。 5.顺序存储结构上的算法如何移植到链式存储结构上 很多优秀的算法都是建立在顺序存储结构上的,如何在链式存储结构上实现这些优秀算法是考生应注意的问题。近年来,在不少程序员水平考试试题中都出现了这样的题目。这里,我们通过在顺序存储结构和链式存储结构两种存储结构上实现选择排序来进行说明。依据顺序存储结构下的算法sort1可以拓展到链式存储结构下的算法sort2。 sort1(int R[], int n) /*对n个元素的数组R进行由小到大排序*/ { int i, j, k, temp; for(i=0; inext , *q, *r; int temp; while(p) { q=p; r=p->next; while(r) { if(r->datadata)q=r; /*在以p为首结点的单链表中找最小的元素*/ r=r->next; } if(q!=p) { temp=p->data; 第1章 常用算法和数据结构 p->data=q->data; q->data=temp; } /*找到的结点和p结点进行数据交换*/ p=p->next; } } /*sort2*/ 可见,只要充分领会顺序存储结构下的算法思想,熟悉链表存储结构就可通过掌握顺序存储结构下的算法得到链表存储结构下的相应算法。 1.3.1.2 栈 1.栈的顺序存储结构 栈的顺序存储用向量作为栈的存储结构,向量S表示栈,m表示栈的大小,用一栈指针top指向栈顶位置,S[top]表示栈顶元素,当在栈中进行插入、删除操作时,都要移动栈指针;而当top=m-1时,则栈满,当top=-1时,则栈空。同时为了避免浪费空间可以采用双栈机制,即向量的两端为栈底。 栈的顺序存储结构的C语言描述如下: #define StackSize 100 /*栈的容量*/ typedef struct { ElemType data[StackSize]; int top; } SqStack; SqStack sq; 栈的说明如下。 l 由于C语言的数组下标的范围是从0至StackSize -1,初始化设置为sq.top= -1。 l 栈空条件为sq.top== -1,栈满条件为sq.top== StackSize -1。 l 栈顶元素为sq.data[sq.top]。 l 元素压栈的规则为:在栈不满时,先改变栈顶指针(top=top+1),再压栈。出栈时,在栈非空时,先取栈顶元素的值,再修改栈顶指针(top=top -1)。 l 栈中元素的个数为当前栈顶指针加1。 在顺序栈上实现基本操作的有关函数如下。 1) 初始化InitStack(SqStack *S) void InitStack(SqStack *S) { S->top=-1; } 2) 判空StackEmpty(SqStack S) int StackEmpty(SqStack S) { if(S.top==-1) return 1; else return 0; } 第1章 常用算法和数据结构 3) 压栈Push(SqStack *S, ElemType e) int Push(SqStack *S, ElemType e) { if(S->top< StackSize-1) { S->top=S->top+1; S->data[S->top]=e; return 1; } else {printf("栈满!\n"); return 0; } } 4) 出栈Pop(SqStack *S, ElemType *e) int Pop(SqStack*S, ElemType*e) { if(sq->top==-1) return 0; else { *e=sq->data[sq->top]; sq->top--; return 1; } } 5) 取栈顶GetTop(SqStack *S, ElemType *e) int GetTop(SqStack*S, ElemType*e) { if(sq->top==-1) return 0; else { *e=sq->data[sq->top]; return 1; } } 6) 清栈ClearStack(SqStack *S) int ClearStack(SqStack *S) { S->top=-1; } 2.栈的链式存储结构 栈的链式存储也叫链栈,我们把插入和删除均在链表表头进行的链表称为链栈。链栈也分带头结点和不带头结点两种。带头结点的链栈操作比较方便。 第1章 常用算法和数据结构 链栈的结点类型定义如下: typedef struct stnode{ ElemType data; struct stnode *next; }LStack; LStack *S; 链栈的约定与说明如下。 l 栈以链表的形式出现,链表(不带头结点)首指针为S,即栈顶为S,链表尾结点为栈底。 l 初始化时,S=NULL(不带头结点);S=(LStack *),malloc(sizeof(LStack)),S-> next=NULL(带头结点)。 l 栈顶指针的引用为S(不带头结点)或S->next(带头结点),栈顶元素的引用为S-> data(不带头结点)或S->next->data(带头结点)。 l 栈空条件为S==NULL(不带头结点)或S->next==NULL(带头结点)。 l 进栈操作和出栈操作与单链表在开始结点的插入和删除操作一致。 对不带头结点的链栈,其基本操作函数如下。 1) 初始化initstack(LStack *S) void initstack(LStack *S) { S=NULL; } 2) 压栈(入栈)push(LStack *S, ElemType x) int push(LStack *S, ElemType x) /*将元素x压到链栈S中*/ { p=(LStack *) malloc(sizeof(LStack )); p->data=x; p->next=NULL; if(S==NULL)S=p; else { p->next=S; S->next=p; } return 1; } 3) 退栈(出栈) pop(LStack *S, ElemType *x) int pop(LStack *S, ElemType *x) { if(S==null) /*链栈为空*/ { printf("\n underflow"); 第1章 常用算法和数据结构 return 0; } else { p=S; S=S->next; x=p->data; free(p); return 1; } } 4) 读栈顶元素 gettop(LStack *S, ElemType *x) int gettop(LStack *S, ElemType *x) { if (S==null) /*链栈为空*/ { printf("\n underflow"); return 0; } else { x=S->data; return 1; } } 5) 判栈空isempty(LStack *S) int isempty(LStack *S) { if (S==null) return 0; else return 1; } 3.栈的应用 栈具有广泛的应用,如:求表达式的值及递归到非递归等。 1) 表达式求值 在源程序编译中,若要把一个含有表达式的赋值语句翻译成正确求值的机器语言,首先应正确地解释表达式。例如,对赋值语句X=4+8×2-3;,其正确的计算结果应该是17,但若在编译程序中简单地按自左向右扫描的原则进行计算,则为:X=12×2-3=24-3=21。这个结果显然是错误的。因此,为了使编译程序能够正确地求值,必须事先规定求值的顺序和规则。通常采用运算符优先法。 2) 递归到非递归 将一个递归算法转换为功能等价的非递归算法有很多方法,可以使用栈保存中间结果。其一般形式如下: 第1章 常用算法和数据结构 将初始状态s0进栈; while(栈不为空){ 退栈,将栈顶元素赋给s; if(s是要找的结果)返回; else{ 寻找到s的相关状态s1; 将s1入栈; } } 例如,求n!的递归函数如下: int funrec(int n) { if(n==0||n==1) return 1; else return n*funrec(n-1); } 使用转换成等价的非递归算法如下,其中st[top][0]用于存放n值,st[top][1]用于存放n!值,在初始时,设置st[top][1]为0,表示n!尚未求出。 #define Max 100 int funnonrec(int n) { int st[Max][2], top=-1; /*栈定义及初始化*/ top++; st[top][0]=n; st[top][1]=0; do{ /*循环求解*/ if(st[top][0]==1) /*满足递归出口,给出st[top][0]值*/ st[top][1]=1; if(st[top][0]>1 && st[top][1]==0) { /*递推入栈*/ top++; st[top][0]=st[top-1][0]-1; st[top][1]=0; } if(st[top][1]!=0) { /*求值出栈*/ st[top-1]=st[top][1]*st[top-1][0]; top--; } }while(top>0); return st[0][1]; /*返回栈底值*/ } 第1章 常用算法和数据结构 1.3.1.3 队列 1.队列的顺序存储结构 顺序存储结构采用一维数组(向量)实现,设队列头指针front和队列尾指针rear,并且假设front指向队头元素的前一位置,rear指向队尾元素。若不考虑队满,则入队操作语句为 Q[rear++]=x;若不考虑队空,则出队操作语句为 x=Q[++front]。当然,出队时,并不一定需要队头元素(与退栈类似)。 按上述的做法,有可能出现假溢出,即队尾已到达一维数组的高端,不能再入队,但因为连续出队,队列中元素个数并未达到最大值。解决这种问题,可用循环队列。在循环队列中,需要区分队空和队满:仍用front==rear表示队列空,在牺牲一个单元的前提下,用front==(rear+1)%MAX表示队列满。在这种约定下,入队操作的语句为:rear=(rear+1) % MAX,Q[rear]=x;出队操作语句为:front=(front+1) % MAX。 顺序队列的类型定义如下: #define QueueSize 20 /*队列的容量*/ typedef struct Squeue{ ElemType data[QueueSize]; int front, rear; }SQueue; SQueue SQ; 顺序队列定义为一个结构类型,该类型变量有3个数据域:data、front、rear。其中data为存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量,取值范围是0~QueueSize-1。约定队尾指针指示队尾元素在一维数组中的当前位置,队头指针指示队头元素在一维数组中的当前位置的前一个位置,这种顺序队列说明如下。 l 初始化时,设置SQ.front=SQ.rear=0。 l 队头指针的引用为SQ.front,队尾指针的引用为SQ.rear。 l 队空的条件为SQ.front==SQ.rear;队满的条件为SQ.front==(SQ.rear+1)% QueueSize。 l 入队操作:在队列未满时,队尾指针先加1(要取模),再送值到队尾指针指向的空闲元素。出队操作:在队列非空时,队头指针先加1(要取模),再从队头指针指向的队头元素处取值。 l 队列长度为(SQ.rear+ QueueSize-SQ.front)% QueueSize。 特别应注意的是:在循环队列的操作中队头指针、队尾指针加1时都要取模,以保持其值不出界。 在循环队列上实现队列的基本操作的函数如下。 1) 初始化initqueue(SQueue *SQ) void initqueue(SQueue *SQ) { SQ->front=SQ->rear=0; } 2) 判空QueueEmpty(SQueue SQ) int QueueEmpty(SQueue SQ) /*队列SQ为空,返回1;队列SQ为非空,返回0*/ 第1章 常用算法和数据结构 { if(SQ.front==SQ.rear) return 1; else return 0; } 3) 入队EQueue(SQueue *SQ, ElemType e) int EQueue(SQueue *SQ, ElemType e) /*若队不满,则进队*/ { if((SQ->rear+1)% QueueSize ==SQ.front) { printf("queue is overflow.\n"); return 0; } else { SQ->rear=(SQ->reare+1)%QueueSize; SQ->data[SQ->rear]=e; return 1; } } 4) 出队OQueue(SQueue *SQ, ElemType *e) int OQueue(SQueue *SQ, ElemType *e) /*若队不空,则队首元素出队*/ { if(SQ.front==SQ.rear) { printf("Queue is empty.\n"); return 0; } else{ SQ->front=(SQ->front+1) % QueueSize; *e=SQ->data[SQ->front]; return 1; } } 5) 取队首元素GetQhead(SQueue *SQ, ElemType *e) int GetQhead(SQueue *SQ, ElemType *e) /*若队不空,则得到队首元素*/ { if(SQ.front==SQ.rear) { printf("Queue is empty.\n"); return 0; } else{ 第1章 常用算法和数据结构 *e=SQ->data[(SQ->front+1) % QueueSize]; return 1; } } 6) 清队列ClearQueue(SQueue *SQ) void ClearQueue(SQueue *SQ) { SQ->front=SQ->rear=0; } 2.队列的链式存储结构 队列的链接实现称为链队,链队实际上是一个同时带有头指针和尾指针的单链表。头指针指向队头结点,尾指针指向队尾结点即单链表的最后一个结点。为了简便,链队设计成一个带头结点的单链表。 链队的类型定义如下: typedef struct QNode{ /*链队结点的类型*/ QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct{ QueuePtr front; QueuePtr rear; }LQueue; LQueue *LQ; 链队列的说明如下。 l 队列以链表形式出现,链首结点为队头,链尾结点为队尾。 l 队头指针为LQ->front,队尾指针为LQ->rear,队头元素的引用为Q->front->data,队尾元素的引用为LQ->rear->data。 l 初始化时,设置LQ->front=LQ->rear=NULL。 l 进队操作,与链表中链尾插入操作一样;出队操作,与链表中链首删除操作一样。 l 队空的条件为LQ->front==NULL。理论上,只要系统内存足够大,链队是不会满的。 下面给出在链队上实现队列基本操作的函数: 1) 队列初始化InitQueue(LQueue *LQ) void InitQueue(LQueue *LQ) /*构造一个空队列LQ*/ { LQ->rear=LQ->front=NULL; } 2) 入队EQueue(LQueue *LQ, ElemType e) void EQueue(LQueue *LQ, ElemType e) /*插入元素e为LQ的新队尾元素*/ { QueuePtr s; 第1章 常用算法和数据结构 s=(QueuePtr)malloc(sizeof(QNode)); /*创建新结点,插入到队尾*/ s->data=e; s->next=NULL; if(LQ->front==NULL && LQ->rear==NULL) /*队空*/ LQ->rear=LQ->front=s; else{ LQ->rear->next=s; LQ->rear=s; } } 3) 出队OQueue(LQueue *LQ, ElemType *e) void OQueue(LQueue *LQ, ElemType *e) /*若队列不空,删除队首元素,用e返回,并返回1;否则返回0*/ { QueuePtr s; if(LQ->front==NULL && LQ->rear==NULL) /*队空*/ { printf("Queue is empty.\n"); return 0; } s=LQ->front; *e=s->data; if(LQ->rear==LQ->front) /*原队列中仅有一个结点,删除后队列变空*/ LQ->rear=LQ->front=NULL; else LQ->front=LQ->front->next; free(s); return 1; } 4) 判空QueueEmpty(LQueue *LQ) int QueueEmpty(LQueue *LQ) /*若队列Q为空队列,返回1;否则返回0*/ { if(LQ->front==NULL && LQ->rear==NULL) return 1; else return 0; } 5) 取队首元素GetQhead(LQueue *LQ, ElemType *e) int GetQhead(LQueue *LQ, ElemType *e) /*若队列不空,用e返回LQ的队首元素,并返回1;否则返回0*/ { if(LQ->front==NULL && LQ->rear==NULL) return 0; else{ *e=LQ->front->data; return 1; } 第1章 常用算法和数据结构 } 6) 清队列ClearQueue(LQueue *LQ) void ClearQueue(LQueue *LQ) /*将LQ清为空队列*/ { QueuePtr s, t; s=LQ->front; while (s) { t=s; free(t); /*释放队列中的所有结点*/ s=s->next; } LQ->rear=LQ->front=NULL; } 3.循环队列中的边界条件判别准则 判别循环队列的“空”或“满”不能以头尾指针是否相等来确定,一般是通过以下几种方法:一是另设一个布尔变量来区别队列的空和满;二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合,如果会重合就认为队列已满;三是设置一个计数器记录队列中的元素总数,不仅可判别空或满,还可以得到队列中元素的个数。 4.双端队列的作用 双端队列是限定插入和删除操作在线性表的两端进行,可将其看成是栈底连在一起的两个栈,但其与两个栈共享存储空间是不同的。共享存储空间中的两个栈的栈顶指针是向两端扩展的,因而每个栈只需一个指针;而双端队列允许两端进行插入和删除元素,因而每个端点必须设立两个指针,如图1-6所示。 图1-6 双端队列的示意图 在实际应用中,可对双端队列的输出进行限制(即一个端点允许插入和删除,另一个端点只允许插入),也可对双端队列的输入进行限制(即一个端点允许插入和删除,另一个端点只允许删除)。可见,采用双端队列可增加应用中的灵活性。 1.3.1.4 数组和矩阵 1.数组的特征 数组是一组具有相同类型的变量,其中各个元素共用一个数组名,但是用不同的下标来访问(引用)。如int a[6];说明了一个一维整型数组a,其中各个整型元素组成了一个向量:a[0],a[1],a[2],a[3],a[4],a[5]。 数组还可以是多维数组,但二维以上的多维数组不是线性结构。 第1章 常用算法和数据结构 n维数组是一维数组(向量)的推广。二维数组(也叫矩阵)可看做是其元素是一维数组的一维数组(线性表、向量),n维数组可看做是其元素是n-1维数组的一维数组(线性表、向量)。n维数组的每个元素处于n个向量中,有n个前驱,也有n个后继。 对二维数组来说,给定维数和下标,如何得到数组元素的存储位置?设每个数组占用l个内存单元,则二维数组Amn按行优先顺序(下标从1开始)计算,aij的地址为: LOC(aij)=LOC(a11)+((i-l)*n+(j-1))*l 二维数组Amn按列优先顺序(下标从1开始)计算,aij的地址为: LOC(aij)=LOC(a11)+((j-l)*m+(i-1))*l 在C语言中,二维数组是按行优先存储的,数组float a[4][5];的存储顺序为a[0][0], a[0][1],…,a[0][4],…,a[3][0],…,a[3][4],a[2][3]的地址为S+(2*5+3)*4=42,其中S为起始地址。 2.求解特殊矩阵的压缩存储地址 特殊矩阵是值相同或零元素在矩阵中的分布有一定的规律的矩阵,为了节约空间,常对下列特殊矩阵进行压缩存储。 对n阶对称矩阵或下三角矩阵A而言,如图1-7所示。如按行将a11, a21, a22, a31, a32, …, an1, an2, …, ann存放在某一维数组B[1...(n+1)n/2]中,则某个aij(i≥j)在B中的存储位置可通过数列求和得到。由于第i行前共有i-1行,且元素个数分别为1, 2, …, i-1,则前i-1行的元素个数为: 1+2+3+…+(i-1)=i(i-1)/2 因而,矩阵元素aij在B中的存储位置为k=i(i-1)/2+j (i≥j)。 图1-7 n阶对称矩阵或下三角矩阵A 对三对角矩阵,其某个矩阵元素在一维数组中的存储位置可类似确定。 3.由压缩存储地址还原矩阵元素的行和列 若已知某个特殊矩阵的非零元素在一维数组中的存储位置,如何得到该矩阵元素的行和列坐标呢?下面就以下三角矩阵在一维数组中的存储位置求相应矩阵元素的行和列来加以说明。 对本小节2.求解特殊矩阵的压缩存储地址中的A和B,若k为某个下三角矩阵元素aij在B中的存储位置,则: i(i-1)/2+j=k 第1章 常用算法和数据结构 初始化i=1,若i(i-1)/2<=k,则i++,直到i(i-1)/2>k,因而可得到行为i-1,列为k-i(i-1)/2。由k求i和j的算法如下: void getaddr(int k, int *i, int *j) { for(*i=1; *i*(*i-1)<=k; *i++); *i--; *j=k-*i*(*i-1); } 4.稀疏矩阵的三元组存储结构 稀疏矩阵是指矩阵中非零元素很少,且分布没有规律。设二维数组Am×n有N个非零元素,N<0) { for(col=1;col<=a.nu;col++)num[col]=0; /*初始化*/ for (t=1;t<=a.tu;t++)num[a.data[t].j]++;/*求M中每一列的非零元个数*/ cpot[1]=1; /*求第col列中第一个非零元在b.data中的序号*/ for(col=2;col<=a.nu;col++) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p<=a.tu;p++) { col=a.data[p].j; q=cpot[col]; b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; ++cpot[col]; } } } 5.稀疏矩阵的十字链表 链式存储可方便插入与删除。十字链表为每行和每列的非零元链成循环链表,每个非零元用一个结点来表示,其形式如下: 其中,i、j分别表示该数组某非零元素的行、列值,e表示该非零元素的值。down指向该行的下一行具有相同列的非零元素, 第1章 常用算法和数据结构 right指向该列的下一列具有相同行的非零元素。此外用两个数组分别存储指向某行和某列第一个元素的指针。 十字链表结点结构和带头结点的数据结构可定义如下: #define M 3 /*矩阵行*/ #define N 4 /*矩阵列*/ #define Max((M)>(n)?(M):(n)) /*矩阵行列较大者*/ typedef struct mtxn{ int row; int col; struct mtxn *right, *down; union { int value; struct mtxn *link; }tag; }matnode; 1.3.1.5 串 串的运算是串的重点和难点,特别是顺序串上子串定位的运算。 子串定位运算又称串的“模式匹配”或“串匹配”,即在主串中查找出子串出现的位置,实际应用中非常广泛,如文本编辑中的“查找和替换”用到的就是子串定位运算的 算法。 在串匹配中,将主串称为目标(串),子串称为模式(串),子串如同一个模板(样本),用其在目标上从头往后比较查找,若找到和子串一样的一个连续子序列,则称匹配成功,并返回其相应的起始位置。 经典的模式匹配算法——Brute-Force的思想是:从目标串s=“s0s1...sn-1”的第一个字符开始和模式串t=“t0t1...tm-1”中的第一个字符比较,若相等,则继续逐个比较后继字符;否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较,依次类推。若存在模式串的每个字符依次和目标串中的一个连续字符序列相等,则匹配成功,函数返回模式串t中第一个字符在主串s中的位置;否则匹配失败,函数返回-1。 Brute-Force算法在进行模式匹配过程中,指向主串的指针经常回溯,因而在某些情况下时间复杂度较高,为此,提出了KMP算法。 KMP算法是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,所以称为Knuth-Morris-Pratt算法,简称KMP算法。该算法比Brute-Force算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有一定程度的提高。 设s=“s0s1...sn-1”,t=“t0t1...tm-1”,当si≠tj(0≤i≤n-m, 0≤j<m)时,存在: “t0t1...tj-1”=“si-jsi-j+1...si-1” (3-1) 若模式串中存在可互相重叠的真子串满足: “t0t1...tk-1”=“sj-ksj-k+1...sj-1” (0<k<j) (3-2) 则由式(3-1)说明模式串中的子串“t0t1...tk-1”已和主串“si-ksi-k+1...si-1”匹配,下一次可直接比较si和tk,若不存在式(3-2),则结合式(3-1)说明在“t0t1...tj-1”中不存在任何以t0为首字符的子串与 第1章 常用算法和数据结构 “si-jsi-j+1...si-1”中以si-1为末字符的匹配子串,下一次可直接比较si和t0。 定义next[j]函数为: max{k|0<k<j,且“t0t1...tk-1”=“sj-ksj-k+1...sj-1” 当此集合非空时 next[j]= 0 其他情况 -1 当j=0时 若模式串t中存在真子串“t0t1...tk-1”=“sj-ksj-k+1...sj-1”,且满足0<k<j,则next[j]表示当模式串t中第j个字符与主串中相应字符(即si)不相等时,模式串中需要重新和主串中该字符si进行比较的字符位置为k,即下一次开始比较si和tk;若不存在这样的真子串,next[j]=0,则下一次开始比较si和t0;当j=0时,令next[j]= -1,此处-1为一个标记,表示下一次开始比较si+1和t0,称每次进行了模式串的右滑。模式串右滑后若仍有si≠tk,则这个模式串的右滑过程可一直进行,直到next[j]=-1时,模式串不再右滑,下一次开始比较si+1和t0。简言之,KMP算法对Brute-Force算法的改进就是利用已经得到的部分匹配结果将模式串右滑一段距离后再继续比较,而无需回溯主串指针。 KMP算法的思想是:设s为目标串,t为模式串,并设i指针和j指针分别指示目标串和模式串中正待比较的字符,令i和j的初值均为0。若有si和tj相等,则i和j分别增1;否则,i不变,j退回到j=next[j]的位置(即模式串右滑),比较si和tj,若相等则i和j指针分别增1,否则j再退回到下一个j=next[j]的位置(即模式串继续右滑),再比较si和tj。依次类推,直到下列两种情况之一:一种是j退回到某个j=next[j]时有si=tj,则指针各增1后继续匹配;另一种是j退回到j= -1时,令指针各增1,即下一次比较si+1和t0。 但前面介绍的next函数在某些情况下尚有缺陷,这就是说,若按上述定义得到next[j]=k,而模式中tj=tk,则当主串中字符si和tj比较不等时,不需要再和tk进行比较,而直接和tnext[k]进行比较,换句话说,此时的next[j]应和next[k]相同。因而可得nextval[j]的值。 1.3.1.6 树 1.树的存储结构及遍历操作 树是非线性的结构,存储树时,须把树中结点之间存在的关系反映在树的存储结构中。树有很多存储结构,这里仅介绍最常用的两种。 1) 树的标准存储结构 树的标准存储结构由结点的数据和指向子结点的指针数组组成;对于度为M的树,其指针数组中的元素个数为M。 2) 树的带逆存储结构 由于树的带逆存储结构需要一个从子结点指向父结点的指针,因而该结构在标准存储结构的基础上,需要在树的结点中增加一个指向其双亲结点位置的指针。 树的遍历是树的基本操作之一,也是最重要的操作之一。树的遍历含义是指:按照某种要求依次访问树中的每个结点,每个结点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。 (1) 树的前序遍历。首先访问根结点,然后从左到右前序遍历根结点的各棵子树。树的前序遍历递归算法如下: #define M 10 第1章 常用算法和数据结构 typedef struct node{ eletype data; struct node *child[M]; }TNode; void tpreorder(TNode *t, int m) { int i; if(t){ print(t->data); /*访问树结点*/ for(i=0;ichild[i],m); /*前序遍历各子树*/ } } 若利用栈来记录当前未访问完的子树的根结点指针,则前序遍历的非递归算法如下: void NTPreorder(TNode *t, int m) { TNode *s[Maxlen]; /*Maxlen为最大的栈空间*/ int top=0; /*top为栈顶指针*/ int i; if (!t) return; s[top++]=t; /*树根指针进栈*/ while(top>0) { t=s[--top]; print(t->data); /*访问树结点*/ for(i=0;ichild[i])s[top++]=t->child[i]; /*各子树根指针进栈*/ } } (2) 树的后序遍历。树的后序遍历的基本思想是:先依次遍历每棵子树,然后访问根结点,与后序遍历二叉树相同。树的后序遍历递归算法如下: #define M 10 typedef struct node{ eletype data; struct node *child[M]; }TNode; void postorder(TNode *t, int m) { int i; if(t){ for(i=0;ichild[i],m); /*后序遍历各子树*/ print(t->data); /*访问树结点*/ } } 第1章 常用算法和数据结构 (3) 树的中序遍历。树的中序遍历的基本思想是:先左子树,遍历根结点,然后依次遍历其他各棵子树,类似二叉树的中序遍历。树的中序遍历递归算法如下: #define M 10 typedef struct node{ eletype data; struct node *child[M]; }TNode; void inorder(TNode *t, int m) { int i; if(t){ inorder (t->child[0],m); /*中序遍历各左子树*/ print(t->data); /*访问树结点*/ for(i=1;ichild[i],m); /*中序遍历各子树*/ } } 2.二叉树的递归定义 二叉树是结点的集合,这个集合或者为空,或者是由一个根和两棵互不相交的被称为左子树和右子树的二叉树组成。二叉树中的每个结点至多有两棵子树,且有左右之分,次序不能颠倒。 二叉树是一种重要的树型结构,但不是树的特例,其有5种形态,分别为:空(二叉树);只有根结点;根结点和左子树;根结点和右子树;根结点和左右子树。 二叉树与树的区别:二叉树可以为空,每个结点子树不超过两个,而树至少有一个结点且结点子树无限制。 3.二叉树的性质及其推广 二叉树的性质如下。 性质1:在二叉树的第i层上至多有2i-1个结点(i≥1)。 性质2:深度为k的二叉树至多有2k-1个结点(k≥1)。 性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0= n2+1。 性质4:具有n个结点的完全二叉树的深度为+1。 性质5:如果有n个结点的完全二叉树,对任一结点i(1n,则无左孩子,否则左孩子为2i。 l 如果2i+1>n,则无右孩子,否则右孩子为2i+1。 二叉树的有关性质可推广到k叉树,如:一棵含有n个结点的二叉树共含有n+1个空指针;而一棵含有n个结点的三叉树共含有2n+1个空指针。推而广之,一棵含有n个结点的k叉树共含有(k-1)n+1个空指针。 不难看出,在k叉树的第i层上至多有ki-1个结点(i≥1);深度为H的k叉树至多有(k 第1章 常用算法和数据结构 H-1)/(k-1)个结点(H≥1)。 同理,可得含N个结点和N个叶子结点的完全三叉树的高度分别为: 及 其推导过程如下: (1) 设含N个结点的完全三叉树的高度为H,则1+3+…+3H-2+1≤N≤1+3+…+3H-1,3H-1≤2N-1≤3H-2,即。 (2) 设含N个叶子结点的完全三叉树的高度为H,则3H-2≤N≤3H-1,即 可进一步推广,含N个结点的完全k叉树的高度为。 4.二叉树遍历的非递归 二叉树的遍历是其操作的重点,通常采用的递归算法不难实现和理解。但要实现二叉树遍历的非递归则有一定的难度,因而是理解二叉树遍历的难点。 由于很多程序员考题中都隐含地利用二叉树遍历的非递归算法,如:求二叉树中某个结点的祖先等,因而必须牢固地掌握二叉树的三种遍历的非递归算法。本质上,程序员考题中不是要考生遍历二叉树中的所有结点,而是遍历满足某种条件的结点并输出,在成功找到答案之前需要保留访问过的部分结点信息,因而须借助栈和队列等重要的数据结构。 二叉树的前序、中序和后序遍历的非递归算法分别如下所述。 二叉链表的C语言描述如下: typedef struct BitNode{ TelemType data; /*结点的数据域*/ struct BiTNode *lchild, *rchild; /*左右子树指针*/ }BiTNode, *BiTree; 1) 前序遍历的非递归算法 int PreorderTraverse(BiTree T, int (*Print)(TElemType e)) { /*采用二叉链表存储结构,Print是对数据元素操作的应用函数*/ /*前序遍历的非递归算法,对每个元素调用函数Print*/ InitStack(S); BiTree p=T; while(!StackEmpty(S)||p){ if(p){ if(!Print (p->data)) return 0; /*访问根结点*/ Push(S,p); /*当前结点指针入栈*/ p=p->Lchild; /*当前指针指向左子树*/ } else { /*若栈顶指针不为0*/ Pop(S,p); /*栈顶元素退栈*/ p=p->rchild; /*当前指针指向右子树*/ 第1章 常用算法和数据结构 } /*else*/ } /*while*/ return 1; } /*PreOrderTraverse*/ 2) 中序遍历的非递归调用算法 int InOrderTraverse(Bitree T, int (*Print)(TElemType e)) { /*采用二叉链表存储结构,Print是对数据元素操作的应用函数*/ /*中序遍历的非递归算法,对每个元素调用函数Print*/ InitStack(S); Push(S,T); /*根指针进栈*/ while(!StackEmpty(S)) { while(GetTop(S,p)&&p) push(S,p->lchild); /*向左走到尽头*/ Pop(S,p); /*空指针退栈*/ if(!StackEmpty(S)){ /*访问结点,向右一步*/ Pop(S,p); if(!Print(p->data)) return 0; Push(S,p->rchild); } /*if*/ } /*while*/ return 1; } /*InOrderTraverse*/ 3) 后序遍历的非递归调用算法 int PostOrderTraverse(Bitree T, int (*Print)(TElemType e)){ /*采用二叉链表存储结构,Print是对数据元素操作的应用函数*/ /*后序遍历的非递归算法,对每个元素调用函数Print*/ int tag[MaxSize], top=-1; InitStack(S); p=T; do{ while(p){ /*扫描左子树,入栈*/ Push(S, p); tag[++top]=0; /*右子树还未访问过的标志*/ p=p->lchild; } if(top>-1) if(tag[top]==1) /*左右子树已被访问过*/ {Print(gettop(S)->data); Pop(S); top--; } else{ p=gettop(S); if(top>-1){ 第1章 常用算法和数据结构 p=p->rchild; /*扫描右子树*/ tag[top]=1; /*置当前结点的右子树已访问过的标志*/ } } }while((p!=NULL)||(top!=-1)); } 下面通过例子来说明二叉树遍历的非递归应用。 例如,在以二叉链表为存储结构的二叉树中,打印数据域值为x的结点(假定结点值不相同),并打印x的所有祖先的数据域值。 解决此问题的算法思想是:若在查找某结点的过程中,记下其祖先结点,则可实现本问题要求。能实现这种要求的数据结构是栈,故设置一个栈用于装入x结点的所有祖先。而这种查找只有用非递归的后序遍历。 栈的元素结构说明如下: typedef struct { bitreptr p; int tag; /*tag=0表示已访问了左子树,tag=1表示已访问了右子树*/ }snode,s[]; int search(bitreptr T,datatype x) { top=0; /*栈s初置为0*/ while ((T!=null)&&(T->data!=x)||(top!=0)) { while ((T!=null)&&(T->data!=x)) { top ++; s[top].p=T; s[top].tag=0; /*结点入栈,置标志0*/ T=T->lchild; /*找左子树*/ } if ((T!=null)&&(T->data==x)) /*找到*/ { for (i=1;i<=top;i++) printf("%d\n",s[i].p->data); /*输出*/ return(1); } else while((top>0)&&(s[top].tag==1)) top--; /*退出右子树已访问过的结点*/ if (top>0) { s[top].tag=1; /*置访问标志为1,访问右子树*/ T=s[top]; T=T->rchild; } } return(0); } 第1章 常用算法和数据结构 5.用线索二叉树实现二叉树的非递归 以二叉链表作为存储结构时,只能找到左、右子树信息,不能直接得到结点在任一序列中的前驱和后继信息,最简单的方法是每个结点上增加两个指针域,但有点浪费。其实,n个结点的二叉链表中必定存在n+1个空链域,因此可用这些链域来存放结点的前驱和后继信息。改进后的结点结构如下: lchild ltag data rtag rchild 其中,ltag = 0:表示lchild域指示结点的左子树。 ltag = 1:表示lchild域指示结点的前驱。 rtag = 0:表示rchild域指示结点的左子树。 rtag =1:表示rchild域指示结点的前驱。 其C语言描述如下: /*Link==0:指针;Thread==1:线索*/ typedef enum{ Link, Thread} PointerTag; typedef struct BiThrNode{ TelemType data; struct BiThrNode *lchild, *rchild; /*左右孩子指针*/ PointerTag ltag, rtag; /*左右标志*/ }BiThrNode, *BiThrTree; 以这种结构构成的二叉链表叫线索链表,其中指向结点前驱和后继的指针叫线索。加 上线索的二叉树叫线索二叉树。对二叉树以某种次序遍历使其成为线索二叉树的过程叫线索化。 对给定的线索二叉树中的某个结点p,查找结点p的后继(中序),其特点为所有叶子结点的右链直接指示了后继,所有非终端结点的后继应是其右子树中第一个中序遍历的结点。 对给定的线索二叉树中的某个结点p,查找结点p的前驱(中序),其特点为若其左标志为“1”,则左链为线索,指示其前驱,否则其前驱为左子树上最后遍历的一个结点。 可见,对线索二叉树进行遍历可通过线索找到相应的前驱和后继,而无须进行递归。 例如,对给定的中序线索化二叉树,查找结点*p的中序后继。在中序线索二叉树中,查找p指针的结点,其后继分为两种情况:若p->rtag=1,则p->rchild,即指向其后继结点;若p->rtag=0,则*p结点的中序后继必为其右子树中第一个中序遍历到的结点,即从*p的右子树开始,沿着左指针链向下找,直到找到一个没有左子树的结点,该结点就是*p的右子树中“最左下”的结点。其算法如下: BiThrNode *succ(BiThrNode *p) { BiThrNode *q; if(p->rtag==1) return p->rchild; else{ q=p->rchild; while(q->ltag==0) q=q->lchild; 第1章 常用算法和数据结构 return q; } } 6.二叉树与树或森林转换的目的 由于树或森林可借用孩子兄弟表示法实现与二叉树的转换,因而我们只要研究二叉树的特性就行了,而无须对树或森林单独进行深入的讨论。 这里仅给出森林和二叉树的转换算法,树和二叉树的转换算法类似。 1) 森林的二叉树表示 森林转换成二叉树的步骤如下。 设F={T1, T2,…, Tn}是森林,对应的二叉树B={root, LB, RB},则: (1) 若F为空,即n=0,则B为空。 (2) 若F非空,即n>0,则二叉树的根为T1的根,其左子树是从T1中根结点的子树森林F={T11, T12,…, T1n}转换而成的二叉树;其右子树是从森林F={T2, T3, …, Tn}转换而成的二叉树。 2) 二叉树转化为森林 若B是一棵二叉树,根为T,L为左子树的根,R为右子树的根,则其相应的森林F{B}由下列步骤形成。 (1) 若B为空,则F为空。 (2) 若B非空,则B的根结点T为{T1, T2,…, Tn}的根结点,B[L]构成了T1的不相交的子树集合{T11, T12,…, T1n};B[R]构成了森林中其他的树T2, …, Tn。 7.建立二叉树的若干方法 建立二叉树的方法有很多,如:按完全二叉树的形式输入字符序列,其中空格表示相应的子树为空。 近年来,在程序员考试中经常出现的二叉树建立为:已知二叉树的后序序列和中序序列或已知二叉树的前序序列和中序序列,要求考生确定一棵二叉树。 例如,一棵二叉树的中序序列和后序序列分别是DCBAEFG和DCBGFEA,请给出该二叉树的前序序列。该题可通过后序遍历确定二叉树的根结点,然后找到该数据值在前序序列中的位置,并用该位置的左部序列和后序序列中的相应序列构造左子树,该位置的右部序列和后序序列中的相应序列构造右子树,如此不断地递归构造即可得到二叉树。建立的二叉树如图1-9所示。 图1-9 二叉树 第1章 常用算法和数据结构 而且,该题还可引申到要考生证明已知二叉树的前序序列和中序序列,可唯一确定一棵二叉树;或要求考生针对已知二叉树的前序序列和中序序列,写出建立一棵二叉树的算法等。同时,要求考生证明已知二叉树的前序序列和后序序列,不能唯一确定一棵二叉树。 当然还可通过给定的广义表建立二叉树等。可见,建立二叉树的方法很多,只要考生掌握了二叉树的递归定义的本质和输入形式就可以方便地建立二叉树。 8.哈夫曼树的建立和哈夫曼编码的构造 1) 哈夫曼树的基本概念 l 路径:由从树中一个结点到另一个结点之间的分支构成两结点之间的路径。 l 路径长度:路径上的分支数目。 l 树的路径长度:从树根到每一个结点的路径长度之和。 l 结点的带权路径长度:从结点到根之间的路径长度与结点上权的乘积WkLk。 l 树的带权路径长度:树中所有带权叶子结点的路径长度之和。 l 哈夫曼树:假设有n个数值{W1, W2, …, Wn},试构造一棵有n个叶子结点的二叉树,结点带权为Wl,带权路径长度WPL最小的二叉树称哈夫曼树。 对图1-10给定的两棵二叉树,它们的带权路径长度分别如下。 (1) WPL=7*2+5*2+2*2+4*2=36。 (2) WPL=7*1+5*2+2*3+4*3=35。 图1-10 二叉树 2) 哈夫曼树的构造 哈夫曼树的构造算法如下。 (1) 根据给定的n个数值{W1, W2,…, Wn}构成n棵二叉树的集合F = { T1, T2,…, Tn},其中每棵二叉树Ti中只有一个带权为 Wi的根结点,左右子树均空。 (2) 在F中选取两棵根结点的数值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的数值为其左右子树上根结点的数值之和。 (3) 在F中删除这两棵树,同时将新得到的二叉树加入F中。 (4) 重复步骤(2)、(3),直到F只含一棵树为止。 3) 哈夫曼编码 哈夫曼编码的设计思想是:若要设计长短不等的编码,则必须是任一个字符的编码都不是另一个字符的编码的前缀,这种编码称做前缀编码。利用二叉树来设计二进制的前缀编码,设计长度最短的二进制前缀编码,以n种字符出现的频率作为权,由此得到的二进制前缀编码为哈夫曼编码。 第1章 常用算法和数据结构 9.如何利用树型结构求解集合的幂 求集合{1, 2, …, n}的幂集问题是一个经典的问题。解决这个问题的最典型做法就是递归调用,传统的做法这里不再讨论。 如何利用树型结构这个参照系来设计求集合{1, 2, …, n}的幂集算法是我们讨论的重点。对于给定的集合{1, 2, 3, 4},按幂集集合中的元素个数和字典次序建立的树如图1-11所示。 图1-11 集合{1, 2, 3, 4}的幂集树型示意图 为保持集合中元素的字典次序,可采用两种方法来求集合{1, 2, 3, 4}的幂集集合,其一是采用前序遍历树;其二是按层次遍历树。特别要注意的是在设计求集合的幂集时并不建立真正的树,而是在考生的心里建立这样一个虚拟的树,并以这棵树为参照系。下面给出这两种方法的算法。 方法1:前序遍历虚拟树。 power(int a[], int n, int i) /*用数组记录集合{1,2,…,n}的一个幂集,a[0]记录当前幂集的元素个数*/ /*i+1表示将要加入到a中的元素*/ { int j,k; if(a[0]==0)printf("{}"); else { printf("{"); for(j=1;jlchild==Null&&T->rchild==Null) /*只有根结点*/ printf("%c",T->dala); else /*(T->lchild!=NuI1||T->rchild!=Null)*/ printf("("); printf("%c",T->data); if(T->lchild->lchild==Null&&T->lchild->rchild==Null); printf("("); print(T->lchild); if(T->rchild!=Null) printf(","); print(T->rchild); if(T->lchild->lchild==Null&&T->lchild->rchild==Null); printf(")"); printf(")"); } (2) 建立哈夫曼树和哈夫曼编码。 typedef struct { unsigned int w; unsigned int parent,lchild,rchild; } HTNode,*HTree; typedef struct { unsigned int bits[n]; unsigned int start; } HTCode; #define MAX最大数 /*准备在选取最小权结点时做比较用*/ void CreatHuffman(ht,weight,hcd) HTree ht[]; unsigned int weight[]; HTCode hcd[]; { int i,j,x,y,m,n; for(i=1;i<=2*n-1;i++) /*初始化数组,n为权叶结点的个数*/ { ht[i].parent=ht[i].lchild=ht[i].rchild=0; if(i<=n) ht[i].w=weight[i]; /*数组中前n个结点的权即为叶结点的权*/ else ht[i].w=0; } /*选取两个权最小的结点,分别用x,y表示其下标,用m,n表示最小权及次最小的权*/ for(i=1;i<=n;i++) { x=y=0; m=n=MAX; for(j=1;jlchild; /*沿着左子树前进*/ } pop(&p,&top); if(!pre){ h=p; /*p指向最左结点,为中序遍历首结点*/ p->ltag=0; /*继续保持空指针*/ } else{ if(p->lchild==NULL){ p->lchild=pr; /*让p的左指针为前驱线索*/ 第1章 常用算法和数据结构 p->ltag=1; /*让标志为1*/ } else p->ltag=0; if(pre->rchild==NULL) { pre->rchild=p; pre->rtag=1; /*让pre的左指针为后继线索且右标志为1*/ } else pre->rtag=0; pre=p; p=p->rchild; /*进入右子树*/ }while(p||top); pre->rtag=0; /*最右结点继续保持空指针*/ return h; } } 1.3.1.7 图 1.图的遍历 图遍历主要有广度优先遍历和深度优先遍历两种,若深刻理解这两种算法的含义,则有利于进一步理解二叉树及树的前序遍历和层次遍历,尤其是理解这两种遍历的非递归算法。 图的广度优先遍历的非递归算法如下。下面来讨论图的深度优先遍历的非递归算法。这里,我们采用邻接表存储结构,首先讨论图的深度优先遍历的递归算法,然后再讨论图的深度优先遍历的非递归算法。 邻接表的C类型描述如下: #define MAX n /*定义最大顶点个数n为某一正整数*/ typedef struct EdgeNode { int adjnum; /*邻接点域,存储位置序号,为int型*/ DataType info; struct EdgeNode *nextarc; /*链域,指向下一条边(弧)的指针*/ } EdgeNode; typedef struct VNode { /*表头结点的类型 VNode*/ DataType vexdata; /*表头结点的数据域*/ struct EdgeNode *firstarc; /*表头结点的指针域*/ } VNode; typedef VNode AdGraph [MAX+l]; /*定义图的类型AdGraph,为一个一维数组*/ typedef struct{ AdGraph adgraph; /*邻接表*/ int e, n; /*边和顶点的数目*/ }Adlist; (1) 图的深度优先遍历的递归遍历算法如下: int visited[MAX+1]; /*结点是否访问过标记*/ void DFSTraverse(Adlist G) { for(v=0; v0){ v=stack1[top1--]; if(!visited[v])print(v);/*打印顶点的信息*/ for(w=First Adjv(G, v); w ; w=Next Adjv(G, v, w)) if(!visited[w])stack2[++top2]=w; /*对v的未访问的邻接顶点w*/ while(top2>0) stack1[++top1]=stack2[top2--]; } /*while*/ } /*if*/ /*NonRecDFSTraverse*/ } 2.图的最小生成树 一棵生成树的代价即树上各边的代价之和,如果该生成树的代价最小,则称该树为最小生成树(也称最小代价生成树)。 求图的最小生成树有着广泛的应用价值,例如,如何在n个城市之间建立通信联络网,并且连通n个城市只需要n-1条线路,而且通信代价最少。 构造最小生成树的算法主要有Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法两种。 1) Prim算法 Prim算法用于求无向图的最小生成树。N=(V, E)是连通网,V={V1, V2, …, Vn}是网的顶点集合,E是N上最小生成树中边的集合。引入顶点集合U和边的集合TE,U的初始状态为{V1},它存放的是当前所得到的(还未完成的)最小代价生成树上的所有顶点,TE的初始状态为。在Prim算法的每一步,都从所有的边{(u, v)| v∈V-U, u ∈U }中找出所有代价最小的边(u, v),同时将v并入U,(u, v)并入集合TE,直到U=V为止。此时TE中必有n-1条边,则T=(V, TE)为N的最小生成树。 第1章 常用算法和数据结构 Prim算法的时间复杂度为O(n2)。它适合稠密图。 2) Kruskal算法 Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。若G=(V, E)是一个连通的无向图,其中V={1, 2, …, n},引入辅助集合T,来存放当前所形成的最小生成树的所有边,其初始状态为空,则Kruskal算法是逐步给T添加不与T中的边构成回路的当前最小代价边。具体步骤如下。 (1) 初始化T=。 (2) 当T的边小于n-1时,做如下工作。 (3) 从E中选取代价最小的边(v, u)并删除。 (4) 若(v, u)不和T中的边一起构成回路,则将边(v, u)并入T中。 (5) 循环执行步骤(2)~(4),直到T中的所有顶点都在同一个连通图上且包含n-1条边为止。 若带权连通无向图G有e条边,则用Kruskal算法构造最小生成树的时间复杂度为O(elog2e)。它适用于稀疏图。 3.拓扑排序 顶点活动的网(也称AOV-网)是用顶点表示活动、用弧表示活动优先关系的有向图。在网中,如果从顶点i到顶点j有一条有向路径,则称i是j的前驱,j是i的后继。若是网中的一条弧,则i是j的直接前驱,j是i的直接后继。 在AOV-网中,不应存在环,因某项活动不应以它自己为先决条件,故对给定的AOV-网,可采用对有向图构造其顶点的拓扑有序序列来监测其是否存在环。拓扑有序序列是AOV-网中的顶点所构成的有序序列T= ( 1, …, I, …, n),且满足以下条件: l AOV-网的优先关系与序列所反映的先后关系一致; l 在AOV-网中无优先关系的顶点也被赋予了一定的先后关系。 则称序列T为AOV-网的一个拓扑有序序列,对AOV-网构造它的拓扑有序序列的过程叫做拓扑排序。 若网中的所有顶点都在它的拓扑有序序列中,则该AOV-网中必定不存在环。 拓扑有序序列的构造方法如下。 (1) 在有向图中选择一个没有前驱(即入度为0)的顶点并输出。 (2) 从图中删除该顶点和所有以它为尾弧的顶点。 (3) 重复执行上述步骤(1)和(2),直到全部顶点都已输出或图中已没有无前驱的顶点。 拓扑排序方法是关键路径求解问题等的基础,同时可应用于课程计划的制订等。从拓扑排序构造的方法可见拓扑排序本质上就是图的遍历过程。 4.经典的最短路径算法 Dijkstra(迪杰斯拉特)算法和Floyd(弗洛伊德)算法为求给定带权有向图G的最短路径的两种方法,其中Dijkstra算法用于求图中某一顶点到其余顶点的最短路径,Floyd算法用于求图中每一对顶点之间的最短路径。 Dijkstra算法提出了一个按路径递增的顺序产生最短路径的算法。首先引入一个辅助向量D,它的分量D(i)表示当前所有找到的从始点V到每个终点Vi的最短路径的长度。其初 第1章 常用算法和数据结构 态为:若从V到Vi有弧,则D(i)为弧上权,否则为无穷大;显然,长度为D(j)=Min{D(i)| Vi∈V}的路径是从V出发的一条最短路径,此路径为(V, Vj)。下一条次短的路径可通过下面的算法求得:设次短路径的终点是Vk,则这条路径或者是(V, Vk),或者是(V, Vj, Vk)。其长度或者是从V到Vk的弧上的权值,或者是D(j)和从Vj到Vk的弧上的权值之和。 Dijkstra算法的时间复杂度为O(n2)。但对于n个顶点的图,求每一对顶点间的最短路径,若按Dijkstra算法,求每一个顶点到其他各顶点间的最短路径,即在上面的基础上,再加一层循环,时间复杂度是O(n3)。而Floyd算法,虽然时间复杂度也是O(n3),但形式上 简单。 Floyd算法的思想是:设求顶点Vi到Vj间的最短路径,若Vi到Vj有弧,则弧上的权值是一条路径,但未必是最短路径,要经过n-1次测试。首先将顶点V1加入,即看(Vi, V1),(V1, Vj)是否有路径,且比(Vi, Vj)低,如果是,则用后两段路径代替,并称这是Vi到Vj中间顶点序号不大于1的最短路径。再将顶点V2加入,得到Vi到Vj中间顶点序号不大于2的最短路径。如此下去,直到Vn加入,得到Vi到Vj中间顶点序号不大于n的最短路径,算法结束。 5.关键路径 在有向图中,顶点表示事件,有向边表示活动,边上的权表示活动的持续时间,此有向图G称为边表示活动的网络,简称为AOE网(Activity On Edge)。其中,每个事件表示在它之前的活动已经完成,在它之后的事件可以开始。整个工程的开始点(入度为0)称为源点,一个完成点(出度为0)称为汇点。 关键路径是从源点到汇点之间路径长度最长的路径,它是完成工程的最短时间。路径长度是指路径上各活动的持续时间之和。 最早发生时间表示从源点V1到Vi的最长路径长度。最迟开始时间是指在不推迟整个工程完成的前提下,活动ai必须最迟开始进行的时间l(i),活动ai必须最早开始进行的时间为e(i)。l(i)-e(i)为完成活动ai的时间余量,将l(i)=e(i)的活动叫关键活动。 寻找e(i)=l(i)的活动,分以下两步进行。 (1) 从Ve(j)=0开始向前递推:Ve(j)=Max{Ve(i)+dut()},∈T,j=1, 2, …, n,T是以j为头的弧的集合。 (2) 从Vl(n)=Ve(n)起向后递推:Vl(i)=Min{Vl(j) -dut()},∈S,i= n-1, …, 1,S是以i为尾的弧的集合。 求关键路径的步骤如下。 (1) 输入e条弧,并建立AOE网的十字链表存储结构。 (2) 从源点出发,令Ve[0]=0,按拓扑排序求每个顶点的最早发生时间Ve(i)(1≤i≤n)。若拓扑排序的循环次数小于n,则说明网中存在回路,不能求关键路径。 (3) 从汇点Vn出发,令Vl[n-1]=Ve[n-1],按逆拓扑排序求每个顶点的最迟发生时间 Vl(i)(2≤i≤n-2)。 (4) 根据各顶点的Ve和Vl值,校正每条弧S的最大开始时间e(s)和最迟开始时间l(s);若e(s)=l(s),则该弧为关键活动,输出。 第1章 常用算法和数据结构 1.3.2 典型例题分析 例1 阅读以下说明和C程序,将应填入 (n) 处的字句写在答题纸的对应栏内。(2008年上半年试题三) 【说明】 下面的程序用Dole Rob算法生成N阶(N为奇数)魔方阵(各行、列、对角线数字之和相等)。该算法的过程为:从1开始,按如下方法依次插入各自然数,直到N2为止。 ① 在第一行的正中插入1。 ② 新位置应当处于最近插入位置的右上方,若该位置已超出方阵的上边界,则新位置取应选列的最下一个位置;若超出右边界,则新位置取应选行的最左一个位置。 ③ 若最近插入的元素是N的整数倍,则选同列的下一行位置为新位置。 例如,3阶魔方阵如下所示: 8 1 6 3 5 7 4 9 2 【C程序】 #include #include #define SIZE 50 main( ) { int row, col, n, value; int a[SIZE+1][SIZE+1]; /*不使用下标为0的元素*/ printf("请输入要输出魔方阵的阶数n(奇数, <%d):n=", SIZE); scanf("%d",&n); if (!(n % 2)||n < 1 || (1) ) { printf("输入数据有误!\n"); exit(0); } row = 1; col = (n+1)/2; value = 1; while(value <= (2) ) { a[row][col] = value; /*计算下一位置*/ if(value%n != 0){ row--; (3) ; if(row < 1) row = n; if(col > n) (4) ; } else row++; value = (5) ; } printf("\n%d 阶魔方阵如下所示:\n\n",n); for(row = 1; row <= n; row++){ for(col = 1; col <= n; col++) 第1章 常用算法和数据结构 printf("%5d",a[row][col]); printf("\n"); } } 分析:程序中空(1)处判断n的合法性,n需为奇数,矩阵规模应不超过SIZE2。所以(1)处应为n > SIZE,或其等价表示。将数值填入方阵的语句为“a[row][col] = value;”,该语句在循环中,循环条件为“value <=n*n”,所以(2)处应填入“n*n”。对于3阶魔方阵,1填入第1行第2列,2填入第3行第3列,3填入第2行第1列,其余位置按照算法步骤类推。所以(3)处填入“col++”或其等价形式,(4)处填入“col = 1”或“col -= n”。程序中,本次填入的数值为value的值,下一次要填入的数值为value加1,因此,空(5)处应填入“value+1”。 答案: (1) n > SIZE,或其等价表示          (2) n*n               (3) col++,或++col,或col=col+1,或其等价表示     (4) col -= n,或col = 1,或其等价表示       (5) value+1,或其等价表示 例2 阅读以下说明和C函数,将应填入 (n) 处的字句写在答题纸的对应栏内。(2008年上半年试题四) 【说明】 计算机在处理算术表达式时,首先将其转换为后缀表达式。例如,表达式“46+5*(120-37)”的后缀表达式形式为“46 5 120 37 - * +”。 计算后缀表达式时,从左至右扫描后缀表达式:若遇到运算对象,则压入栈中;遇到运算符,则从栈中弹出相关运算对象进行计算,并将运算结果压入栈中。重复以上过程,直到后缀表达式扫描结束。例如,后缀表达式“46 5 120 37 - * +”的计算过程如下。 ① 依次将46、5、120、37压入栈中。 ② 遇到“-”,取出37、120,计算120-37=83,将其压入栈中。 ③ 遇到“*”,取出83、5,计算5×83=415,将其压入栈中。 ④ 遇到“+”,取出415、46,计算46+415=461,将其压入栈中。 ⑤ 表达式结束,则计算过程完成。 函数computing(char expr[],int *result)的功能是基于栈计算后缀形式的表达式(以串形式存入字符数组expr)的值,并通过参数result返回该值。函数的返回值为-1/0,分别表示表达式有/无错误。假设表达式中仅包含数字、空格和算术运算符号,其中所有项均以空格分隔,且运算符仅包含加(“+”)、减(“-”)、乘(“*”)、除(“\”)。 函数computing中所用栈的基本操作的函数原型说明如下。 l void InitStack(STACK *s):初始化栈。 l void Push(STACK *s, int e):将一个整数压栈,栈中元素数目增1。 l void Pop(STACK *s):栈顶元素出栈,栈中元素数目减1。 l int Top(STACK s):返回非空栈的栈顶元素值,栈中元素数目不变。 l int IsEmpty(STACK s):若s是空栈,则返回1;否则返回0。 第1章 常用算法和数据结构 【C函数】 int computing(char expr[], int *result) { STACK s; int tnum, a,b; char *ptr; InitStack(&s); ptr = expr; pstr /*字符指针指向后缀表达式串的第一个字符*/ while (*ptr!='\0') { if (*ptr==' ') { /*当前字符是空格*/ (1) ; /*字符指针指向下一字符*/ continue; } else if (isdigit(*ptr)) { /*当前字符是数字,则将该数字开始的数字串转换为数值*/ tnum = (2) ; while (*ptr>='0' && *ptr <='9') { tnum = tnum * 10 + (3) ; ptr++; } Push( (4) ); } else /*当前字符是运算符或其他符号*/ if (*ptr=='+'||*ptr=='-'||*ptr =='*'||*ptr =='/'){ if (!IsEmpty(s)) { a = Top(s); Pop(&s); /*取运算符的第二个运算数*/ if (!IsEmpty(s)) { b = Top(s); Pop(&s); /*取运算符的第一个运算数*/ } else return -1; } else return -1; switch (*ptr) { case '+': Push(&s,b+a); break; case '-': Push(&s,b-a); break; case '*': Push(&s,b*a); break; case '/': Push(&s,b/a); break; } } else return -1; ptr++; /*字符指针指向下一字符*/ } /*while*/ if (IsEmpty(s)) return -1; else { (5) = Top(s); Pop(&s); /*取运算结果*/ if (!IsEmpty(s)) return -1; return 0; } 第1章 常用算法和数据结构 } 分析:由于后缀表达式以字符串方式存储且以空格分隔符号(数值、运算符),因此遇到空格字符时,指向表达式中字符的指针ptr应增加1指向后续字符,所以(1)处应填入“ptr++”或其等价形式。tnum的初始值应为0,因此,空(2)处应填入“0”,空(3)所在表达式将数字字符转换为数值,即空(3)处填入“*ptr-48”。空(4)处用于将转换所得的数值tnum压入栈顶,根据题目中Push的原型“void Push(STACK *s, int e)”,调用时第一个实际参数是STACK类型变量的地址,第二个实际参数是一个整数,因此,空(4)处填入“&s,tnum”。由于函数computing(char expr[],int *result)通过参数result返回该表达式的值,因此需要将存在栈顶的运算结果赋值给result指向的整型变量,即空(5)处填入“*result”。 答案: (1) ptr++,或++ptr,或ptr=ptr+1,或其等价表示 (2) 0,或tnum = 0 (3) *ptr-48,或*ptr -'0',或其等价表示 (4) &s,tnum (5) *result 例3 阅读以下说明和C函数,将应填入 (n) 处的字句写在答题纸的对应栏内。(2008年下半年试题三) 【说明】 已知某二叉树的非叶子结点都有两个孩子结点,现将该二叉树存储在结构数组 Ht中。结点结构及数组Ht的定义如下: #define MAXLEAFNUM 30 struct node{ char ch; char *pstr; int parent; int lchild,rchild;   }; struct node Ht[2 * MAXLEAFNUM]; 该二叉树的n个叶子结点存储在下标为1~n的Ht数组元素中。例如,某二叉树如 图1-12所示,其存储结构如图1-13所示,其中,与叶子结点a对应的数组元素下标为1,a的父结点存储在Ht[5],表示为Ht[1].parent=5。Ht[7].parent=0表示7号结点是树根,Ht[7].lchild=3、Ht[7].rchild=6分别表示7号结点的左孩子是3号结点、右孩子是6号结点。 第1章 常用算法和数据结构 图1-12 二叉树 图1-13 二叉树存储结构 如果用“0”或“1”分别标识二叉树的左分支和右分支(如图1-12所示),从根结点开始到叶子结点为止,按所经过分支的次序将相应标识依次排列,可得到一个0、1序列,称之为对应叶子结点的编码。例如,图1-12中a、b、c、d的编码分别是100、101、0、11。 函数LeafCode(Ht[], n)的功能是:求解存储在Ht中的二叉树中所有叶子结点(n个)的编码,叶子结点存储在Ht[1]~Ht[n]中,求出的编码存储区由对应的数组元素pstr域指示。 函数LeafCode从叶子到根逆向求叶子结点的编码。例如,对图1-12中叶子结点a求编码的过程如图1-14所示。 图1-14 从叶子到根求结点编码示意图 【函数】 typedef enum Status {ERROR, OK} Status; Status LeafCode(struct node Ht[], int n) { int pc, pf; int i,start; char tstr[31] = {'\0'}; for(i=1; (1) ; i++) { start = 29; pc = i; pf = Ht[i].parent; while (pf != (2) ) { if ( (3) .lchild == pc ) tstr[--start] = '0'; else tstr[--start] = '1';   pc = (4) ; pf = Ht[pf].parent; 第1章 常用算法和数据结构 } Ht[i].pstr = (char *) malloc(31-start); if (!Ht[i].pstr) return ERROR; strcpy(Ht[i].pstr, (5) ); } return OK; } 分析:题中已指出该二叉树的n个叶子节点存储在下标为1到n的Ht数组元素中,同时举例说明父节点编号为0的节点是树根节点。所以,(1)处应为“i<=n”。而到达根即父节点为0时,所以(2)处为“0”。pc用于指出树中的节点,pf则用于指出pc所对应节点的父节点,所以(3)处应为“Ht[pf]”,(4)处应为“pf”。根据tstr的作用,strcpy函数的实参应该是“tstr+start”或“&tstr[start]”,所以(5)处应该为“tstr+start”或“&tstr[start]”。 答案: (1)i<=n,或其等价形式 (2)0 (3)Ht[pf],或(*(Ht+pf)) (4)pf (5)tstr+start或&tstr[start] 例4 阅读以下说明和C语言函数,将应填入 (n) 处的字句写在答题纸的对应栏内。(2007年下半年试题四) 【说明】 已知包含头结点(不存储元素)的单链表的元素已经按照非递减方式排序,函数compress(NODE *head)的功能是去掉其中重复的元素,使得链表中的元素互不相同。 处理过程中,当元素重复出现时,保留元素第一次出现所在的结点。 图1-15(a)、(b)是经函数compress()处理前后的链表结构示例图。 图1-15 链表结构 链表的结点类型定义如下: typedef struct Node { int data; struct Node *next; }NODE; 【C语言函数】 void compress(NODE *head) { NODE *ptr,*q; ptr = (1) ; /*取得第一个元素结点的指针*/ while ( (2) && ptr -> next) { 第1章 常用算法和数据结构 q = ptr -> next; while(q && (3) ) { /*处理重复元素*/ (4) = q -> next; free(q); q = ptr -> next; } (5) = ptr -> next; } /*end of while*/ } /*end of compress*/ 分析:本题考查的是对链表的查找、插入和删除等运算。要找到重复的元素并删除使各元素互不相同。我们可以顺序遍历链表,比较逻辑上相邻的两个元素是否相同,如果相同则删除后一个元素,依次类推。代码如下: void compress(NODE *head) { NODE *ptr,*q; ptr =head -> next; /*取得第一个元素结点的指针*/ while (ptr && ptr -> next) { q = ptr -> next; while(q && ptr -> data== q-> data) { /*处理重复元素*/ ptr -> next = q -> next; free(q); q = ptr -> next; } ptr= ptr -> next; } /*end of while*/ } /*end of compress*/ 答案: (1) head -> next (2) ptr (3) ptr -> data== q-> data 或其等价形式 (4) ptr -> next (5) ptr 例5 阅读以下说明和C语言函数,将应填入 (n) 处的字句写在答题纸的对应栏内。(2006年上半年试题三) 【说明】 函数bool Del_elem(STACK *S,char para_ch)的功能是:删除栈*s中与para_ch值相等且最接近栈顶的元素(字符),若栈中不存在该元素,则函数返回FALSE,否则返回TRUE。其中,STACK是栈的类型名。 函数Del_elem实现上述功能的方法是利用栈的基本操作,先将栈*s中所有比para_ch之值更接近栈顶的元素暂时存放在临时工作栈s_bak中,使得与para_ch值相等的元素成为栈顶元素,此时执行出栈操作,即从栈中删除与para_ch值相等的元素,最后再将s_bak中的元素依次存回栈*s。 第1章 常用算法和数据结构 在函数Del_elem中必须使用栈的基本操作进行栈上的运算,实现栈的基本操作的函数原型说明如下: l void InitStack(STACK*S):初始化栈。 l void Push(STACK*S, char e):将一个字符压栈,栈中元素数目增1。 l void Pop(STACK*S):栈顶元素出栈,栈中元素数目减1。 l char Top(STACK S):返回非空栈的栈顶元素值,栈中元素数目不变。 l bool IsEmpty(STACK S):若S是空栈,则返回TRUE;否则返回FALSE。 bool类型定义如下: typedef enum{ FALSE=0,TRUE=1 } bool; 【C语言函数】 bool Del_elem(STACK *S,char para_ch) { STACK s_bak; /*定义临时工作栈s_bak*/ char Ch; bool tag=FALSE; (1) ; /*初始化临时工作栈s_bak*/ /*将栈*s中所有比para_ch更接近栈顶的元素暂时存放在临时工作栈s_bak中*/ while(!IsEmpty(*s)){ ch= (2) ; /*取栈顶元素*/ Pop(S); if(Ch=para_ch){ tag=TRUE; break; } (3) ; } /*将暂存于临时工作栈s_bak中的元素存回栈*s*/ while ( (4) ){ Ch=Top(s_bak); (5) ; Push(s,ch); } return tag; } 分析:InitStack函数的实参应该是对STACK类型变量取地址,所以(1)处应为InitStack(&s_bak)。(2)处应该是调用Top函数获取栈顶元素的值,所以(2)处应为Top(*s)。临时工作栈需要保存从栈*s弹出的元素,所以(3)处应为Push(&s_bak,ch)。从栈中取元素要先判断是否为空,所以(4)处应为!IsEmpty(s_bak)。最后,(5)处应为Pop(&s_bak)。 答案: (1) InitStack(&s_bak) (2) Top(*s) 第1章 常用算法和数据结构 (3) Push(&s_bak,ch) (4) !IsEmpty(s_bak) (5) Pop(&s_bak) 1.3.3 同步练习 1. 阅读下列C语言程序,将程序的运行结果依次输出。 #include #define LEN 8 main() { int j,c; static char num[2][LEN+1]={ "17208980","28219198"}; c=0; for ( j=LEN-1;j>=0;j-- ) { c+=num[0][j]+num[1][j]-2*'0'; printf( "%d\n",c ); num[0][j]=c%10+'0'; c=c/10; } printf( "%s\n",&num[0][0] ); } 2. 阅读以下程序说明和 C 程序,将应填入 (n) 处的字句写在对应栏内。 程序说明:函数maxword()从给定的两个由英文单词组成的字符串 s 和 t 中,找出其中都包含的最长的相同单词(将同一字母的大小写视做不同字符)。约定单词全由英文字母组成,单词之间用空格表示。 【程序】 #include #include maxword( char *S,char *t ) { char *res,xtemp,chs,cht; int i,j,found,maxlen=0 ; while (*s!='\0' ) { while (*s==' ') s++; for ( i=0; (1) ; i++) if ( i>maxlen ) { chs=s[i]; (2) ; temp=t; found=0; while ( *temp !='\0' && !found ) { while ( *temp==' ') temp++; 第1章 常用算法和数据结构 for ( j=0; (3) ; j++ ) if ( j==i ) { cht=temp[j]; (4) ; if ( strcmp(s,temp)==0) { (5) =i; res=S;found=1; } temp[j]=cht; } temp=&temp[j]; } s[i]=chs; } s=&s[i]; } if ( maxlen==0 ) printf( "There is no same word.\n" ); else { chs=res[maxlen]; res[maxlen]='\0'; printf( "%s\n",res );res[maxlen]=chs; } } char s[]="This is C programming test",t[]="This is a test for C programming"; main() { maxword(s,t);} 3. 阅读以下程序说明和 C 程序,将应填入程序中 (n) 处的字句写在对应栏内。 程序说明:本程序所列函数 replace ( char *s1, char *s2, char *str1, char *str2 ) 实现若已知字符串 s1中有与字符串 str1 相同的字符列时,就把该字符复制到字符数组 s2的功能;当从某字符开始能构成一个与字符串 str1 相同的字符列时,就将字符串 str2 的各字符复制到字符数组s2,并继续访问字符串 s1 中那个字符列之后的字符,直至字符串 s1 被访问完,字符复制即告结束。 如程序中所列数据,程序运行输出为: ABCXYZdefg abABCXYZd abab 【程序】 replace(char *s1, char *s2, char *str1, char *str2) { char *t0, *t1, *t2; while ( (1) ) { for(t0=s1, t1=str1;*t1!='\0'&& (2) ; t0++, t1++); if (*t1 != '\0') *s2++ = (3) ; else { for(t1=str2;*t1 != '\0';) *S2++ = (4) ; 第1章 常用算法和数据结构 (5) ; } } *S2 = '\0'; } main( ) { char s1[ ] = "abcdefg ababcd abab ."; char s2[80]; replace(s1, s2, "abc","ABCXYZ"); printf("%s\n", s2); } 4. 试利用下列栈和串的基本操作完成下述填空题。 基本操作如下: initstack(s):置s为空栈。 push(s, x):元素x入栈。 pop(s):出栈操作。 gettop(s):返回栈顶元素。 sempty(s):判栈空函数。 setnull(st):置st为空串。 length(st):返回串st的长度。 equal(s1, s2):判串s1和s2是否相等的函数。 concat(s1, s2):返回连接s1和s2之后的串。 sub(s, i, 1):返回s中第i个字符。 empty(st):判串空函数。 op(ch):判断ch是否运算符。 【程序】 int invert( string pre, string *exp) /*若给定的表达式的前缀式pre正确,则本过程求得和它相应的表达式exp并返回1, 否则exp为空串,并返回0。已知原表达式中不包含括号*/ { Stack s; char ch; int i, n, succ; i=0; n=length(pre); succ=1; (1) ; (2) ; while(i,使得对所有的j=0,1,…,k-1,有xij=yj。例如,X=“FEGDAADWS”,Y=“FEAD”是X的一个子序列。 给定两个序列A和B,称序列Z是A和B的公共子序列,是指Z同是A和B的子序列。问题是要求出已知两序列A和B的最长公共子序列。 【程序】 #include #include #define N 100 char a[N],b[N],str[N]; int lcs len(char *a,char *b,int c[][N]) { int m=strlen(a),n=strlen(b),i,j; for(i=0;i<=m;i++)c[i][0]=0; for(j=0;j<=n;j++) (1) ; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(a[i-1]==b[j-1])c[i][j]=c[i-1][j-1]+1; else if(c[i-1][j]>=c[i][j-1]) c[i][j]= (2) ; else c[i][j]=c[i][j-1]; return (3) ; } char *buildlcs(char s[],char *a,char *b) { int k,i=strlen(a),j=strlen(b),c[N][N]; k=lcslen(a,b, (4) ); s[k]='\0'; while(k>0) if(c[i][j]==c[i-1][j])i--; else if(c[i][j]==c[i][j-1]) (5) ; else { s[--k]=a[i-1]; i--;j--; } return s; } void main() { 第1章 常用算法和数据结构 printf("Enter two string(<%d)!\n",N); scanf("%s%s",a,b); printf("Lcs=%s\n",buildlcs(str,a,b)); } 7. 函数char *strrchr(char*s,char ch)的功能是:在字符串s中寻找字符ch,若ch出现在字符串s中,则返回最后一次出现时的位置,否则返回NULL。 【函数】 char *strrchr(char *s, char ch) { char *p; p = (1) ; /*p指向字符串s的结束标志*/ while( --p >= s) if( (2) ) return p; return NULL; } 8. 下面的函数对用邻接表表示的有向图的顶点进行拓扑排序。 请在空缺处填上适当内容,每个空缺只填一个语句。并指出:语句(1)、(2)的功能是什么?语句(3)、(4)的功能是什么?语句(5)、(6)的功能是什么? 【程序】 #define maxn 50 #define maxm 100 typedef struct { int t ver; int h ver; }E NODE; typedef struct vl node{ int ver; struct vl node *link; }VL NODE; typedef struct { int count; VL NODE *head; }CH NODE; E NODE e[maxm]; CH NODE ch[maxn]; int tpv[maxn]; int n, m, i, count; int topol order (ch, n, tpv) CH NODE ch[ ]; int n, tpv[ ]; { int i, j, k; int top=0; VL NODE *t; for (i=1; i<=n; i++) 第1章 常用算法和数据结构 if( ch[i].count==0) { (1) ; (2) ; } i=0; while (top!=0){ (3) ; (4) ; tpv[++i]=j; t=ch[j].head; while (t!=NULL){ k=t->ver; if(--(ch[k].count)==0){ (5) ; (6) ; } t=t->link; } } return(i); } 9. 应用Prim算法求解连通网络的最小生成树问题。 (1) 针对图1-16所示的连通网络,试按如下格式给出在构造最小生成树过程中顺序选出的各条边。 (始顶点号,终顶点号,权值) (始顶点号,终顶点号,权值) (始顶点号,终顶点号,权值) (始顶点号,终顶点号,权值) (始顶点号,终顶点号,权值) (始顶点号,终顶点号,权值) 图1-16 带权无向图 (2) 下面是Prim算法的实现,中间有5处空缺,请阅读程序后将它们补上。 const int Maxint=INT MAX; //INT MAX的值在中 const int n=6; //图的顶点数,应由用户定义 typedef int Adjmatrix[n][n]; //用二维数组作为邻接矩阵表示 第1章 常用算法和数据结构 typedef struct{ //生成树的边结点 int fromvex, tovex; //边的起点与终点 int weight; //边上的权值 }Treeedgenode; typedef Treeedgenode MST[n-1]; //最小生成树定义 void PrimMST(Adjmatrix G, int rt) { //从顶点rt出发构造G的最小生成树T,rt称为树的根结点 Treeedgenode e; int i ,k=0, min, minpos, v; For (i=0; i上的权,若不存在弧,则为0(ai, j规定为0),在上述条件下,除了将数组ve作为topsort的参数,即topsort(array, indegree, ve, n)外: ① crein是否需修改,如何修改(写出修改部分的语句)。 ② topsort如何修改,写出修改部分的语句。 注意:若要删除某语句注明语句号;插入语句注明在哪一行后插入;若修改某行,注明行号替换为……。 11. 阅读下列程序说明和C代码,将应填入 (n) 处的字句写在对应栏内。 设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序是输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,求得从站0出发乘公交车至站n-1的最少换车次数。 第1章 常用算法和数据结构 程序利用输入信息构建一张有向图G(用邻接矩阵g表示),有向图的顶点是车站,若有某条公交线路经i站能到达j站,就在顶点i到顶点j之间设置一条权为1的有向边。如果这样,那么从站点x至站点y的最少上车次数便对应图G中从点x至点y的最短路径长度。而程序要求的换车次数就是上车次数减1。 #include #define M 20 #define N 50 int a[N+1]; /*用于存放一条线路上的各站编号*/ int g[N][N]; /*存储对应的邻接矩阵*/ int dist[N]; /*存储站0到各站的最短路径*/ int m,n; void buildG() { int i,j,k,sc,dd; printf("输入公交线路数,公交站数\n"); for(i=0;i=0&&dd=0;k++) /*处理第i+1条公交线路*/ for(j=0;j0&&(k==-1||dist[j]0,且a[i-1]==b[j-1]。 (3) c[i][j]=max(c[i][j-1],c[i-1][j]),如果i、j>0,且a[i-1]!=b[j-1]。 按此算式可写出计算两个序列最长公共子序列长度的函数lcs len。 由c[i][j]的产生仅依赖于c[i-1][j-1],c[i-1][j]和c[i][j-1]可知,利用函数lcslen所产生的数组c[][],可以从c[m][n]开始,跟踪c[i][j]的产生过程,由函数buildlcs逆向构造出最长公共子序列。 答案: (1) c[0][j]=0 (2) c[i-1][j] (3) c[m][n] (4) c (5) j-- 7. 分析:可以看出,题目要求若ch出现在字符串s中,则返回最后一次出现时的位置,否则返回NULL。因此,本题采用自后向前搜索的方法进行,首先将p定位到'\0'的位置,然后向前搜索,直到找到或到达s 第1章 常用算法和数据结构 -1的位置为止,一旦找到立即停止。因此,空(1)应填“strlen(s) + s”;空(2)应填“*p == ch”。 答案: (1) strlen(s) + s (2) *p == ch 8. 分析:本题主要要求考生熟悉拓扑排序的主要思想和主要步骤,并熟悉邻接表的存储结构特点及栈的基本操作。本题反映了拓扑排序的过程,首先判断顶点的入度为0;栈不空,则出栈,并记录出栈的顶点,同时将以该顶点为尾弧的所有顶点的入度减1,若使得某顶点的入度变为0,则该顶点进栈。循环结束时,一个拓扑排序序列被求出,同时通过返回遍历的顶点数判断图中是否有回路。 答案:依据上述分析,可得到如下答案。 (1) top++ (2) e[top].t ver=i (3) j=e[top].t ver (4) top-- (5) top++ (6) e[top].t ver=k 其中,语句(1)、(2)的功能是入度为0的顶点进栈;语句(3)、(4)的功能是出栈;语句(5)、(6)的功能是入度变为0的顶点入栈。 9. 分析:本题要求考生熟悉Prim算法的主要思想和主要步骤,尤其是求两个顶点集合之间距离最短的两个顶点,该题的思路就是Prim算法的具体实现。 答案: 1) ( 始顶点号 ,终顶点号,权值 ) ( 0 , 3 , 1 ) ( 3 , 5 , 4 ) ( 5 , 2 , 2 ) ( 3 , 1 , 5 ) ( 1 , 4 , 3 ) 2) 应填入的语句 (1) T[k].tovex=i (2) min=Maxint (3) minpos=i 第1章 常用算法和数据结构 (4) exit(0) (5) T[i].fromvex=v 10. 分析:本题主要考核有关拓扑排序和关键路径方面的知识点,这里要求熟悉邻接矩阵存储结构、有关拓扑排序和关键路径的算法思想和主要步骤。本题主要思路是利用邻接矩阵来进行拓扑排序,首先计算各顶点的入度,入度为0的顶点入栈;栈不空,出栈且修改相应的顶点的入度,并将入度为0的顶点入栈,如此反复直到循环结束。 答案: (1) ① 0 ② j ③ i ④ 0 ⑤ indegree[i] ⑥ [vex][i] ⑦ k!=0 ⑧ indegree[i]=0 (2) 由于邻接矩阵中的元素值已改为权值,因而在求顶点入度时要做相应的改变;语句7改为 if ( array[j][i]!=0 ) indegree[i]++。 为求各顶点的最早发生时间(记在ve[k]中,0≤k≤n-1),除了将topsort(array, indegree, n)改为topsort(array, indegree, ve, n)外;在语句3的后面插入初始化语句: for(i=0; ive[i])ve[i]= ve[vex]+array[vex][i]; 11. 分析:本题的主要思路源于最短路径求解。由于数组a是用于存放一条线路上的各站编号,而函数buildG的功能是根据输入的线路对邻接矩阵赋值,且每次输入一条线路,因此空(1)填“a[sc++]=dd”。对空(2),不访设a[0]=1,a[1]=3,a[2]=4,a[3]=6,则g[1][3]=1,g[1][4]=1,g[3][4]=1,g[3][6]=1,g[4][6]=1,g[1][6]=1,因此空(2)填“[a[j]][a[k]]”。 对建好的邻接矩阵,由于站是顺序编号的,故函数minLen中的dist[j]表示从站0到 站j的最短路径长度。每次确定下一个最少上车次数的站k,再判断k到j与dist[j]的大小,即可得空(3)和空(4)分别为“(dist[j]>=0)&&(g[k][j]==1)”和“-dist[k]+1”。若找到的最少上车次数的站k<0,则返回为-1,否则返回为j-1,这里j-1表示转车的次数。 答案: (1) a[sc++]=dd (2) [a[j]][a[k]] 第1章 常用算法和数据结构 (3) (dist[j]>=0)&&(g[k][j]==1) (4) -dist[k]+1 (5) k<0 ? -1 : j-1 1.4 本 章 小 结 数据结构在计算机科学中占有重要的核心地位,不仅是计算机专业本科教育的核心课程之一,也是非计算机专业从事计算机学习的重要课程之一。数据结构可为从事程序设计的人员提供方法论的理论指导,是程序设计的灵魂。 本章知识点在2009年的新大纲中变化较小,只是一些表述方式的调整。 在程序员考试下午试卷中(2004年下半年以后),每年重点考察数据结构的题量一般为1题(一般是第2题或第3题),且在必答题中出现,分值为15分。数据结构的题型一般与C语言结合考察,重在考察基本概念和性质,难度不会太大。 1.5 达标训练题及参考答案 1.5.1 达标训练题 1. 阅读下列程序说明和C代码,将应填入 (n) 处的字句写在对应栏内。 设M叉树采用列表法表示,即每棵子树对应一个列表,列表的结构为:子树根结点的值部分(设为一个字符)和用“()”括起来的各子树的列表(如有子树的话),各子列表间用“,”分隔。例如下面的三叉树(如图1-17所示),可用列表 a( b(c,d),e,f(g,h,i))来表示。 本程序输入列表,生成一棵M叉树,并由M叉树输出列表。假定输入无错误。 #include〈stdio.h〉 #include〈stdlib.h〉 #define M 3 typedef struct node{ char val;       struct node *subTree[M]; } NODE; char buf[255] ,*str = buf; 第1章 常用算法和数据结构 图1-17 三叉树 NODE *d = NULL; NODE *makeTree( ) /*由列表生成M叉树*/ { int k; NODE *s ; s = (1) ; s -> val = *str++ ; for ( k = 0 ; k < M ; k++ ) s-> subTree[k] = NULL ; if(*str='( '){      k = 0;      do { str++;          s -> subTree[k] = (2) ;          if ( *str == ')' ) { str++; break ; }          k = k+l ;      } while ( (3) ); } return s ; } void walkTree( NODE *t ) /*由 M 叉树输出列表*/ { int i ; if( t != NULL ) {      (4) ;      if ( t -> subTree[0] == NULL ) return ;      putchar ( '( ' ) ;      for (i=0 ; isubTree[i]!= NULL )              putchar ( ', ' ) ;      }      putchar (') ') ; } }   void main( ) { printf( "Enter exp:" ) ; scanf( "%S" , str ) ; d = makeTree() ; walkTree( d ) ; 第1章 常用算法和数据结构 putchar( '\n') ; } 2. 阅读下列程序说明和C代码,将应填入 (n) 处的字句写在对应栏内。 设已知一棵二叉树用二叉链表存储,t指向根结点,p指向树中任一结点。下列算法为输出从t到p之间路径上的结点。 #define MaxSize 1000 typedef struct node{ TelemType data; struct node *lchild, *rchild; }BiNode, *BiTree; void Path(BiTree t, BiNode * p) { BiTree *stack[MaxSize], *stack1[maxSize], *q; int tag[MaxSize], top=0, top1; q=t; /*通过前序遍历发现p*/ do{ while(q!=NULL &&q!=p ) /*扫描左孩子,且相应的结点不为p*/ { (1) ; stack[top]=q; tag[top]=0; (2) ; } if(top>0) { if(stack[top]==p)break; /*找到p, 栈底到栈顶为t到p*/ if(tag[top]==1)top--; else { q=stack[top]; q=q->rchild; tag[top]=1; } } } (3) ; top--; top1=0; while(top>0) {q=stack[top]; /*反向打印准备*/ top1++; (4) ; top--; } while( (5) ){ /*打印栈的内容*/ q=stack1[top1]; printf(q->data); top1--; } } 第1章 常用算法和数据结构 3. 请在下列算法的 (n) 处添入适当的语句。 inlusion(Slink *ha, Slink *hb) /*以ha和hb为头指针的单链表分别表示有序表A和B,本算法判别表A是否包含在*/ /*表B内,若是,则返回1,否则返回0*/ { Slink *pa=ha->next, *pb=hb->next; (1) ; while( (2) ) if(pa->data==pb->data) (3) ; else (4) ; (5) ; } 4. 由二叉树的前序遍历和中序遍历序列能确定惟一的一棵二叉树。下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列,生成一棵用二叉链表表示的二叉树并打印出后序遍历序列。请写出程序中所缺的语句。 #define MaxSize 100 char pred[MaxSize], inod[MaxSize]; void main(int argc, char *argv[]) { BiTree root; if(argc<3) eixt(0); strcpy(pred, argv[1]); strcpy(inod, argv[2]); root=restore(pred, inod, strlen(pred)); postorder(root); } BiTree restore(char *ppos, char *ipos, int n) { BiTree ptr; char *rpos; int k; if(n<=0) return NULL; ptr=(BiTree)malloc(sizeof(BiNode)); ptr->data= (1) ; ptr->lchild=ptr->rchild=NULL; for( (2) ; rposlchild=restore(ppos+1, (4) , k); ptr->rchild=restore( (5) , rpos+1, n-k-1); return ptr; } postorder(BiTree ptr) 第1章 常用算法和数据结构 { if(ptr!=NULL) postorder(ptr->lchild); postorder(ptr->rchild); printf("%c", ptr->data); } 5. 下面的程序对给定的链表p进行快速排序,与对顺序存储的线性表进行快速排序类似,采用分治法进行处理,以链表的第一个结点值作为基准,把其他结点按小于基准结点值分为两组,再递归地对这两组结点分别进行快速排序,最后链接所有的链表。程序中last为全程指针变量,指向已排序链表的最后一个结点。 typedef struct node{ int data; struct node *next; }Node; Node *last; Node *quick_sort(p) Node *p; { Node *low_head, *low_tail, *mid_head, *mid_tail, *high_head,*high_tail; if(!p){ last=NULL; return(p); } low_head=low_tail=NULL; mid_head=mid_tail=NULL; high_head=high_tail=NULL; if(mid_head==NULL) mid_head=NULL; else mid_tail->next=p; mid_tail=p; p=p->next; while( (1) ){ if(p->datadata) { if(low_head==NULL) low_head=p; else low_tail->next=p; low_tail=p; } else if(p->data==mid_head->data) { if(mid_head==NULL) high_head=p; else (2) ; (3) ; } 第1章 常用算法和数据结构 else{ if(high_head==NULL) high_head=p; else high_tail->next=p; high_tail=p; } (4) ; } if(low_head!=NULL){ low_tail->next=NULL; (5) =quick_sort(low_head); last->next=mid_head; } else p=mid_head; if(high->head!=NULL) high_tail->next=NULL; (6) =quick_sort(high_head); if(last==NULL) last=mid_tail; (7) ; } 6. 在下列程序中,函数difference(A,B)用于求两个集合之差C=A-B,即当且仅当e是A中的一个元素,但不是B中的元素时,e是C中的一个元素。集合用有序链表实现,用一个空链表表示一个空集合,表示非空集合的链表根据元素之间按递增排列。执行C=A-B之后,表示集合A和B的链表不变,若结果集合C非空,则表示其链表根据元素之值按递增排列。函数append()用于在链表中添加结点。 #include typedef struct node{ int element; struct node *link; }Node; Node *A, *B, *C; Node *append(last, e) Node *last; int e; { last->link=(Node *)malloc(sizeof(Node)); last->link->element=e; return(last->link); } Node *difference(A, B) Node *A, *B; { Node *C, *last; C=last=(Node *)malloc(sizeof(Node)); while( (1) ) if(A->elementelement) { last=append(last, A->element); 第1章 常用算法和数据结构 A=A->link; } else if( (2) ) { A=A->link; B=B->link; } else (3) ; while( (4) ) { last=append(last, A->element); A=A->link; } (5) ; last=C; C=C->link free(last); return(C); } 1.5.2 参考答案 1. 分析:本题在本质上是以广义表形式表示一棵树,将广义表表示的字符串转化为一棵树仍然按照建树的步骤进行。在建树的过程中,首先是建立一个个结点,并进行赋值,然后插入到树中。从函数makeTree的算法思路可见,其采用的是递归算法,类似图的深度优先遍历。因此,空(1)应填结点空间申请函数,即“(NODE*) malloc (sizeof (NODE))”。函数makeTree中的do…while循环是生成S的各棵子树,而以逗号间隔的字符均为S的子树,故空(3)填“*str==','”;而空(2)应该填子树的生成函数makeTree (),这是因为每次makeTree返回一个指向当前结点的指针。 在函数walkTree()中,首先输出当前根结点对应的数据,若其子树不空,则输出“(”,递归输出各子树,输出“)”。因此,空(4)应填“putchar (t->val)”;空(5)应填“walkTree (t->subTree[i])”。 答案: (1) (NODE*) malloc (sizeof (NODE)) (2) makeTree ( ) (3) *str == ',' (4) putchar (t->val) (5) walkTree (t->subTree[i]) 2. 分析:本题本质上是对二叉树的前序遍历进行考核,但不是简单地进行前序遍历,而是仅遍历从根结点到给定的结点p为止。本题采用非递归算法来实现,其主要思想如下。 第1章 常用算法和数据结构 (1) 初始化栈。 (2) 根结点进栈,栈不空则循环执行以下步骤直到发现结点p。 (3) 当前结点不为空且不为p,则进栈。 (4) 栈顶为p,则结束;否则转(3)。 (5) 若右子树访问过,则栈顶的右孩子为当前结点,转(3)。 答案: (1) top++ (2) q=q->lchild (3) while(top>0) (4) stack1[top1]=q (5) top1>0 3. 分析:本题本质上是一个递归实现算法。空(1)表示比较到了ha的尾结点;空(2)表示结点pa之前和pb之前具备包含关系。 答案: (1) if(pa==NULL) return 1 (2) pb && pa->data==pb->data (3) return(inclusion(pa, pb)) (4) pb=pb->next (5) return 0 4. 分析:本题程序中的算法是根据前序遍历序列和中序序列递归求解对应的二叉树,因此其算法的空缺答案不难得到。 答案: (1) *ppos (2) rpos=ipos (3) rpos-ipos (4) ipos (5) ppos+k+1 5. 分析:本题程序中的算法经过一趟快速排序,将待排序序列分为三个部分:以low_head为头指针,low_tail为尾指针前面部分;以mid_head为头指针,mid_tail为尾指针的中间部分;以high_head为头指针,high_tail为尾指针的右边部分;且中间部分各结点关键字值相等。算法在递归调用前面部分和后面部分,并将排好序的序列链接起来。 第1章 常用算法和数据结构 答案: (1) p (2) mid_tail->next=p (3) mid_tail=p (4) p=p->next (5) last (6) last (7) return(last) 6. 分析:本题用链表表示集合,通过比较链表的元素值判断集合中元素之间的关系。 答案: (1) b->link (2) a->element==b->element (3) b=b->link (4) a->link!=NULL (5) last->link=NULL

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档