区块链技术博客
www.b2bchain.cn

汇总

这篇文章主要介绍了汇总的讲解,通过具体代码实例进行20388 讲解,并且分析了汇总的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=20388

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

 

目录

  1. 1.删顺序表中的最小值(最小值唯一,返回被删元素值,空位由最后一个位置的元素填补)
  2. 2.顺序表元素逆置 要求空间复杂度O1
  3. 3.删除长度为n的顺序表中所有值为x的元素 空间复杂O1,时间复杂O1
  4. 4.在有序顺序表中删除s-t之间(包括s,t)要求s的所有元素,不合理的范围返回错误信息<>
  5. 5.在顺序表中删除值s-t之间(包含s,t)且s的所有元素,不合理的范围返回错误信息<>
  6. 6.在有序表中删除所有重复值的元素(双指针)
  7. 7.将两个有序顺序表合并为一个新的有序顺序表,并由函数返回结果顺序表
  8. 8.已知在一维数组A[m+n]中依次存放两个线性表。试编写函数将两个顺序表位置互换。
  9. 9.线性表(a1..an)中元素递增有序且顺序存储,请查找值为x的元素,找到后与其后继交换位置,若找不到则将其插入表中并使表中元素仍递增有序
  10. 1.递归删除不带头结点的单链表中所有值为x的结点
  11. 2.删除带头结点单链表中所有值为x的节点并释放节点空间,假设x不唯一
  12. 3.把带头结点的单链表从尾到头反向输出(过)方法1.先逆置再输出 方法2.递归(栈的思想)
  13. 4.删除带头结点的单链表中最小值的结点
  14. 5.带头结点单链表就地逆置
  15. 6.对带头结点的单链表排序(递增)
  16. 7.在带头结点的无序单链表中删除所有介于给定值之间的元素
  17. 8.找出两个单链表的公共结点
  18. 9.递增输出一个单链表的所有节点的数据元素并释放节点存储空间
  19. 10.分解带头结点的单链表,A表含有序号为奇数的元素,B表含有序号为偶数的元素
  20. 11.就地拆分(奇偶拆分)一个带头结点单链表,使A为正序,B为逆序
  21. 12.在递增有序的单链表中删除数值相同的节点-过
  22. 13.将两个递增排列的单链表,归并为一个递减排列的单链表(要求利用原来两个单链表的结点存放归并后的单链表)-过
  23. 14.两个带头结点递增有序的单链表,把两个单链表中的公共元素产生新链表,要求不破坏原来的链表
  24. 15.求两个递增排列的单链表的交集
  25. 16.判断两个单链表中的数值,B中元素是否是A中元素的连续子序列
  26. 17.判断带头结点的循环双链表是否对称
  27. 18.两个循环单链表,把后者链接在前者之后,要求链接后的链表仍是循环链表
  28. 19.结点均为正整数的带头结点单链表,反复找出最小节点并输出,然后删除,直到链表为空,在删除表头结点
  29. 20.头指针为L的带表头结点非循环双链表,结点除了前驱pre后继next数据data还包括一个访问频度freq。在链表启用前,全部初始化为0.。每当在链表中进行一次Locate(L,x)运算时,令元素值为x的f、频度域值+1,并使此链表以访问频度排序,且相同频度结点时最近访问的结点排在前面,以便使频繁访问的结点总是靠近表头。请编写符合要求的Locate函数,以指针型返回找到结点的地址
  30. 3.判定栈操作序列是否合法
  31. 4.单链表n个结点,头指针L,存储字符型数据,判断字符是否对称。
  32. 5.两个顺序栈共享0-Maxsize-1的存储区,请设计s1 s2有关出入栈的操作
  33. 天勤9、编写算法将非负十进制N转换为二进
  34. 1.用标志域tag0或1来区分循环队列空满,请编写入队和出队算法
  35. 2.Q是一个队列,S是一个空栈,实现将队列元素逆置
  36. 3.用两个栈模拟队列
  37. 天勤6、假设带头结点的循环链表表示队列,设一个指针指向队尾结点,请写出相应的入队出队算法
  38. 7.如果允许在循环队列的两端都可以插入删除,请写出从队尾删除和从队头插入的算法
  39. 栈和队列的应用p90 1-4
  40. 1.括号配对
  41. 2.车厢调度,两侧单向行驶道,有n节硬座和软座车厢等待调度,对n节车厢做入栈出栈操作,使所有软座排在硬座车厢之前
  42. 3.利用栈实现以下递归函数的非递归计算(可以把结构做数组用,结构定义可以在函数内)
  43. 4.汽车过江渡船问题
  44. 已知一棵二叉树按顺序存储结构进行存储,设计算法求编号i、j的最近公共祖先结点
  45. 二叉树的遍历和线索二叉树 p126 3-18 
  46. 3.编写后序遍历二叉树非递归算法
  47. 4.试给出二叉树自下而上,从右到左的层次遍历算法(层次遍历算法)
  48. 5.假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树的高度(层次遍历算法)非递归 递归
  49. 6.根据前序序列和中序序列构造二叉树,假设结点数据值互不相同。
  50. 7.二叉树按二叉链表形式存储,写一个判别给定二叉树是否是完全二叉树的算法(层次遍历算法)
  51. 8.假设二叉树采用二叉链表存储结构存储,设计一个算法,计算给定二叉树的所有双分支结点个数(中序遍历算法)  递归模型 f(b) 如下:(是双分支结点,则此节点+左右子树中的双分支节点,否则不加)  改造二叉树递归遍历算法
  52. 9.设树B是一棵采用链式结构存储的二叉树,编写一个把树B中所有节点的左右子树交换的函数(后序遍历算法)
  53. 10.假设二叉树采用二叉链表存储结构存储,设计一个算法,求先序遍历序列中第k(1<=k<=二叉树结点个数)个结点的值(前序遍历算法)
  54. 11.已知二叉树以二叉链表存储,编写算法:对于树中每个元素值为x的结点,删去以它为根的子树,释放相应的空间(删除子树:后序遍历算法,找父节点:层次遍历算法)
  55. 12.在二叉树中查找值为x的结点,试编写算法打印值为x的结点的所有祖先,假设值为x的结点不多于一个一般情况下树的题目,用递归比较好
  56. 13.设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根节点的指针,p和q分别为指向该二叉树种任意两个结点的指针,试编写算法ANCESTOR(ROOT,p,q,r),找到p和q的最近公共祖先结点r。(递归)
  57. 14.假设二叉树采用二叉链表存储,设计算法,求非空二叉树的宽度(即具有结点树最多的那一层的结点个数)
  58. 15.设有一棵满二叉树(所有节点值均不同),已知其先序序列为pre,设计一个算法求其后序序列post。
  59. 16.设计一个算法将二叉树的叶节点按从左到右的顺序连成一个单链表,表头指针为head。二叉树按二叉链表的方式存储,链接时用叶节点的右指针域来存放单链表指针
  60. 17.试设计判断两棵二叉树是否相似的算法。所谓二叉树T1T2相似,指的是都空或都只有一个根节点或左子树与左子树相似且右子树与右子树相似 
  61. 天勤(1)设计算法计算给定二叉树的所有节点
  62. (2)计算给定二叉树的所有叶子结点
  63. (5)增加一个指向双亲结点的parent指针,设计算法给这个指针赋值,并输出所有节点到根节点的路径
  64. (6)假设满二叉树b的先序序列存在长度为n的数组中,设计算法将其转换为后序遍历序列
  65. (7)二叉链表存储二叉树,设计算法求二叉树b中值为x的结点的层号
  66. (10)二叉树的双序遍历:对于二叉树的每个节点,先访问这个节点,再按照双序遍历它的左子树,然后再一次访问这个节点,再双序遍历右子树。
  67.  (11)设中序线索二叉树类型为TBTnode *InThTree
  68. (1)设计算法在一棵中序线索二叉树中寻找节点t的子树上中序下的最后一个节点
  69. (2)找t的中序前驱
  70. (3)找t的前序后继
  71. 5.编程求以孩子兄弟表示法存储的森林的叶子节点数
  72. 6.以孩子兄弟链表为存储结构,请设计递归算法求树的深度(层次遍历)
  73. 6.判断给定二叉树是否是二叉排序树
  74. 7.求出指定节点在给定二叉排序树中的层次
  75. 8.利用二叉树遍历的思想编写一个判断二叉树是否是平衡二叉树的算法(后序遍历)
  76. 9.求给定二叉排序树中最大和最小的关键字
  77. 10.设计算法,从大到小输出二叉排序树中所有值不小于k的关键字(中序遍历 )
  78. 6.折半查找的递归算法
  79. 7.将经常被检索的结点尽量置于表的前端
  80. 2.双向冒泡算法,在正反两个方向交替进行扫描,即第一趟把关键字最大的元素放在序列最后,第二趟把关键字最小的元素放在序列最前,如此反复进行。
  81. 3.已知线性表按顺序存储,且每个元素都是不相同的整数型元素,设计把所有的奇数移动到偶数前面的算法。
  82. 5.编写算法,在数组L[1..n]中找出第k小的元素(即从小到大排序后处于第k个位置的元素)
  83. 7.荷兰国旗问题:设有一个仅由红白蓝三种颜色的条块组成的条块序列,编写时间复杂度On的算法,使这些条块按红白蓝顺序排好。
  84. 4.编写算法,在基于单链表表示的待排序关键字序列上进行简单选择排序
  85. 5.设计算法判断数据序列是否构成小根堆
  86. 各种排序算法的比较和应用 p327 2-3 
  87. 2.顺序表A[]中元素存储在下标1~m+n范围内,两部分都递增有序,设计算法使整个顺序表有序
  88. 3.计数排序:对一个待排序的表(数组表示)进行排序,将排序结果放在另一个新表中。表中所有关键码互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键码比该记录的关键码小,假设针对某个记录统计出的计数值为c,则这个记录在新有序表中的合适存放位置为c
  89. (1)、将串str中所有值为ch1的字符转换成ch2的字符,如果str为空串,或者串中不含值为ch1的字符则什么都不做
  90. (2)、实现串str的逆转函数,如果str为空串,则什么都不做
  91. (3)、删除str中值为ch的所有字符,如果str为空,或不含有ch的字符则什么都不做
  92. (4)、从串str中的pos位置起,求出与substr串匹配的子串位置
  93. 2、采用定长顺序存储表示串,编写函数,删除串中下标为i的字符开始,如果第i个字符后没有足够的j个字符,则有几个删除几个
  94. 4、编写一个函数计算子串在主串中的出现次数,不考虑子串重叠。
  95. 5、构造串的链表结点数据结构,编写函数找出串str1中第一个不在str2中出现的字符
  96. 天勤1、将所有的负数放在正值之前,R[0..n-1]
  97. 1、设数组A[0~n-1]的n个元素中有多个0元素,设计算法将所有非零元素移动到数组前端。
  98. 2、关于浮点型数组A[0~n-1]设计递归算法实现:(1)求数组A的最大值(2)求数组n个数之和(3)求数组n个数的平均值
  99. 3、设计算法将数组A的所有奇数移动到偶数之前,不增加存储空间且时间复杂度On
  100. 4、设有一元素为整数的线性表L,存在数组中,设计算法以最后一个元素为准,进行快排一次划分
  101. 2.设计算法,判断一个无向图G是否是一棵树。若是一棵树,则算法返回ture,否则返回false。
  102. 3.写出图的深度优先搜索DFS算法的非递归遍历(图采用邻接表形式)
  103. 4.分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中是否存在Vi到Vj的路径(i不等于j)。注意,算法中涉及的图的基本操作必须在此存储结构上实现。

P18顺序表


1.删顺序表中的最小值(最小值唯一,返回被删元素值,空位由最后一个位置的元素填补)

  • 搜索整个顺序表,查找最小元素并记住其位置,搜索结束后用最后一个元素补空出的原最小值元素的位置
/*从顺序表中删除最小值(假设唯一),并返回被删元素值,空出的位置由最后一个元素填补*/ int minValue(sqlist &l,int &x){     if(l.length==0) return false;  	int pos=0; 	int min=L.data[0]; 	 	for(int i=0;i<L.length;i++) {   		  		 if(L.data[i]<min) { 		 	min=L.data[i]; 		 	pos=i; 		 } 	} 	data[pos]=data[l.length-1]; 	L.length--; 	return min; } 

2.顺序表元素逆置 要求空间复杂度O1

  • 扫描顺序表的前半部 分,对于l.data[i] (0<=i<=length/2),将其与后半部分的对应元素交换,l.data[l.length-i-1]
void reverse(sqlist &l){     int i,temp;     for(i=0;i<l.length/2;i++){      	temp=l.data[i]; 		l.data[i]=l.data[l.length-i-1]; 		l.data[l.length-i-1]=temp;	 	}   } 

3.删除长度为n的顺序表中所有值为x的元素 空间复杂O1,时间复杂O1

  • 用size记录顺序表中不等于x的元素个数(即需要保存的元素个数),边扫描L边统计size
  • 并将不等于x的元素向前移动size个位置,最后修改l的长度
void dele_x(sqlist &l,int x){ 	int size=0; 	for(int i=0;i<l.length;i++){ 		if(l.data[i]!=x) l.data[size++]=l.data[i];  	} 	l.length=size; }

4.在有序顺序表中删除s-t之间(包括s,t)要求s<t的所有元素,不合理的范围返回错误信息

  • 寻找值大于等于s的第一个元素(第一个删除的元素)
  • 然后寻找值大于t的第一个元素(最后一个删除的元素的下一个元素)
  • 要将这段元素删除,只需将后面的元素前移。
bool Delete(sqlist &l,int s,int t){ 	if(l.length==0||s>=t) return false; 	 	int i,j; 	for(i=0;i<l.length&&l.data[i]<s;i++); 	if(i>=l.length) return flase;                //>=,i找到表外面去了表长只有length-1 	for(j=i;j<l.length&&l.data[j]<=t;j++); 	 	for(;j<l.length;j++,i++){                    //i++ 		l.data[i]=l.data[j]; 	} 	l.length=i+1;                               //i+1 	return true; }

5.在顺序表中删除值s-t之间(包含s,t)且s<t的所有元素,不合理的范围返回错误信息

  • 从前向后扫描顺序表L
  • 用k记录下元素值在s-t之间元素的个数(初始k=0)
  • 对于当前扫描的元素,若其值不再s-t之间,则前移k个位置,否则k++
bool dele_st(sqlist &l,int s,int t){ 	if(s>=t||l.length==0) return false; 	 	int k=0; 	for(int i=0;i<l.length;i++){ 		if(l.data[i]>=s||l.data[i]<=t) k++; 		else l.data[i-k]=l.data[i];          //i-k,只有不再范围内的值才做赋值,不存在i<k的情况 	} 	l.length-=k; 	return ture; }

6.在有序表中删除所有重复值的元素(双指针)

  • 有序顺序表值相同的元素一定在连续的位置上,用类似于直接插入排序的思想
  • 初始时将第一个元素视为非重复的有序表,之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同
  • 若相同则继续向后判断,若不同则插入到前面的非重复有序表的最后,直至判断到表尾为止
void dele_copy(sqlist &l){ 	int i=0,j; 	for(j=i+1;j<l.length;j++){ 		if(l.data[j]!=l.data[i])               l.data[++i]=l.data[j];    //++i,用例子分析可以知道 	} 	l.length=i+1;                            //i+1,i是数组下标 }

7.将两个有序顺序表合并为一个新的有序顺序表,并由函数返回结果顺序表

  • 首先,按顺序表不断取下两个顺序表表头较小的节点存入新的顺序表中。
  • 然后,看哪个表还有剩余,将剩下的部分加到新表后面。
bool Merge(sqlist &l1,sqlist &l2,sqlist &l){     //用新表的引用就省去了定义新表的过程,也不用判断两个表的情况(一空一满)  	if(l1.length+l2.length>l.length) return false; //如果新表不够装,要返回错误   	int i=0,j=0,k=0;								//K 必须有新变量来标记新表中的位置,i和j都在变化的不能用  	while(i<l1.length&&j<l2.length){ 				//用while ,变量变化都在表达式里  		if(l1.data[i]<=l2.data[j])                      //<=,在两数相等时,也加入新表因为是不断比较的  			l.data[k++]=l1.data[i++]; 		else l.data[k++]=l1.data[j++];                   //前面已经<=了,else就是>了,不用特殊说明  	} 	while(i<l1.length) l.data[k++]=l1.data[i++];     //如果有剩余的就直接放进新表  	while(j<l2.length) l.data[k++]=l2.data[j++]; 	c.length=k+1; 	return true;	 }

8.已知在一维数组A[m+n]中依次存放两个线性表。试编写函数将两个顺序表位置互换。

  • 首先将数组的全部元素原地逆置,再对前n个元素和后m个元素分别使用逆置算法,从而实现顺序表位置互换。
  • 整体求逆:(AB)逆=B逆A逆   各部分分别求逆:(B逆)逆(A逆)逆=BA
typedef int datatype;   //下标都是int,只有数组中的内容可能是数字也可能是字符所以另写类型为了更好修改  void reverse(datatype A[],int left,int right,int arraysize){    	if(left>=right||right>=arraysize)  		return;//return;表示什么都不返回,只结束此函数 	//如果要逆转的数组元素超出总数组元素个数,则数组参数有误,什么都不返回  	int mid=(left+right)/2  	for(int i=0;i<mid-left;i++){   //注意第二段遍历范围  		datatype temp=A[left+i]; 		A[left+i]=A[right-i]; 		A[right-i]=temp; 	} }   void exchange(datatype A[],int m,int n,int arraysize){//要给数据表长度,用来判断逆转的范围是否正确  	 	reverse(A,0,m+n-1,arraysize);  //分清什么时候用结构类型,什么时候不用 	reverse(A,0,m-1,arraysize);  //先总体求逆,再分别求逆  	reverse(A,n,m+n-1,arraysize); }

9.线性表(a1..an)中元素递增有序且顺序存储,请查找值为x的元素,找到后与其后继交换位置,若找不到则将其插入表中并使表中元素仍递增有序

折半查找最快

void SearchExchangeInsert(ElemType a[],int n,ElemType x){ 	int low=0,high=n-1,mid; 	 	while(low<=high){ 		mid=(low+high)/2; 		if(a[mid]==x) break; 		else if(a[mid]<x) low=mid+1; 		else high=mid-1; 	} 	 	if(mid!=n-1&&a[mid]==x){     //查找成功,则与后继交换  		int temp=a[mid+1]; 		a[mid+1]=a[mid]; 		a[mid]=temp; 	} 	 	if(low>high){      //查找,则插入元素  		for(int i=n-1;i>high;i--) a[i+1]=a[i]; 		a[i+1]=x; 	} }

P38链表


1.递归删除不带头结点的单链表中所有值为x的结点

  1. 终止条件:若表空,不做任何事
  2. 递归主体:值相等,删除结点,继续处理后续结点。值不等,递归处理子序列 
  3. 引用型,是直接对原链表操作,所以不会造成断链
void Delete_x(Linklist &l,int x){ 	if(l==NULL) return;   //空表情况   	if(l->data!=x){                 //不等的情况  		Dlete_x(l->next,x); 		return; 	}                                             	LNode *p;                    //与x相等的情况  	p=l; 	l=l->next; 	free(p); 	Delete_x(l,x); } 

2.删除带头结点单链表中所有值为x的节点并释放节点空间,假设x不唯一

p做判断指针,指向待判断结点的前驱,若p的后继的值=x就删除,若不等于就判断下一个 

void Delete_x(Linklist &l,int x){    if(l->next==NULL) return;    //表空情况     Lnode *p=l;        while(p->next){                  //遍历链表  	  if(p->next->data!=x)  p=p->next;          //值不等情况直接下一个  	  else {                             //值相等情况做链表结点删除操作  	  	Lnode *temp=p->next; 	  	p->next=p->next->next; 	  	free(temp); 	  }    } } 

3.把带头结点的单链表从尾到头反向输出(过)

方法1.先逆置再输出

void reverse(Linklist &l){ 	if(l||l->next) return; 	 	Linklist *p=l->next,*temp; 	l->next=NULL; 	while(p->next){ 		*temp=p->next; 		p->next=l->next; 		l->next=p; 		 		p=temp;		 	} 	while(l->next){ 		printf("%d",l->next->data); 		l=l->next; 	}printf("%d",l->data); } 

方法2.递归(栈的思想)

每当访问一个节点时,先递归输出该节点自身,这样链表就反向输出了。

void R_print(Linklist l){ 	if(l->next) R_printf(l->next); 	printf("%d",l->data);  }

4.删除带头结点的单链表中最小值的结点

用p扫描单链表,pre指向p所指结点的前驱,用minp保存值最小的结点指针(初值为p),minpre指向minp所指结点的前驱(初值为pre)。一边扫描一边比较,若p->data小于minp->data,则将p、pre分别赋给minp、minpre。当p扫描完毕,minp指向最小值结点,minpre指向最小值结点的前驱节点,再将minp所指结点删除即可。

void delete_min(Linklist &l){ 	Lnode *pre=l,*p=pre->next; 	Lnode *minpre=pre,*minp=p; 	while(p!=NULL){ 		if(p->data<min->data){ 			minp=p; 			minpre=pre; 		} 		pre=p; 		p=p->next;  	} 	minpre->next=minp->next; 	free(minp);	  }

5.带头结点单链表就地逆置

6.对带头结点的单链表排序(递增)

类似插入排序算法的思想,先构成只含有一个数据节点的有序单链表,然后依次扫描单链表中剩下的结点*p(直至p==NULL),在有序表中通过比较查找插入*p的前驱节点:*pre,然后将*p插入*pre之后

void sort_list(Linklist &l){ 	Lnode *pre,*p=l->next; 	Lnode *r=p->next;  //存上位置否则就丢了  	p->next=NULL;//此时l表中只有原链表中的第一个结点 	p=r;  	 	while(p!=NULL){ 		r=p->next;//存位置 		pre=l; 		while(pre->next!=NULL&&pre->next->data<p->data) 			pre=pre->next; 		p->next=pre->next; 		pre->next=p; 		p=r;		  	}	  }

7.在带头结点的无序单链表中删除所有介于给定值之间的元素

逐个节点检查,执行删除

void rangeDelete(Linklist &l,int min,int max){ 	Lnode *pre=l,*p=l->next; 	while(p!=NULL){ 		if(p->data>min&&p->data<max){ 			pre->next=p->next; 			free(p); 			p=pre->next; 		} 		pre=p; 		p=p->next; 	}	  }

8.找出两个单链表的公共结点

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {     struct ListNode *pa=headA,*pb=headB;     while(pa!=pb){         pa=pa==NULL?headB:pa->next;         pb=pb==NULL?headA:pb->next;     }     return pa; }

9.递增输出一个单链表的所有节点的数据元素并释放节点存储空间

对链表进行遍历,在每次遍历中找出整个链表的最小值元素,输出并释放结点所占空间:再查找次小值元素,输出并释放空间。如此直至链表空,最后释放头结点。

void Min_delete(Linklist &l){ 	Linklist *minpre,*p,*temp; 	while(l->next!=NULL){ 		minpre=l; 		p=l->next; 		while(p->next!=NULL){  //找到最小值的前驱  			if(p->next->data<minpre->next->data) 				minpre=p; 			p=p->next;	 		} 		printf("%d",minpre->next->data);  //打印最小值  		temp=minpre->next;       //删除最小值  		minpre->next=minpre->next->next; 		free(temp);              //释放结点空间  	} 	free(l);        //释放头结点  }

10.分解带头结点的单链表,A表含有序号为奇数的元素,B表含有序号为偶数的元素

设置一个访问序号变量初值为0,每访问一个节点就序号+1,然后根据序号的奇偶性将节点插入到AB表中,重复操作直到表尾。

Linklist disCreat(Linklist &A){ 	int i=0; 	Linklist B=(Linklist)malloc(sizeof(LNode)); 	B->next=NULL; 	Lnode *ra=A,*rb=B; 	Lnode *p=A->next; 	A->next=NULL; 	 	while(p!=NULL){ 		i++; 		if(i%2==0){ 			rb->next=p;   //尾插  			rb=p; 		}	 		else{ 			ra->next=p; 			ra=p; 		} 		p=p->next; 	} 	ra->next=NULL; 	rb->next=NULL; 	return B; } 

11.就地拆分(奇偶拆分)一个带头结点单链表,使A为正序,B为逆序

采用上题的思路,但不设序号变量。二者的差别仅在于对B表的建立不采用尾插法而是头插法。

Linklist discreat_2(Linklist &A){ 	Linklist B=(Linklist)malloc(sizeof(Lnode)); 	B->next=NULL; 	Lnode *p=A->next,*temp; 	Lnode *ra=A; 	 	while(p!=NULL) { 		ra->next=p;  		ra=p; 		p->next=p; 		temp=p->next;    		p->next=B->next; 		B->next=p; 		p=temp;     	}     ra->next=NULL;     return B; }

12.在递增有序的单链表中删除数值相同的节点-过

由于是有序表,所有相同值域的节点都是相邻的。用p扫描递增链表l,若*p节点的值域等于其后继节点的值域,则删除后者,否则p移向下一个节点

void Delete(Linklist &l){    	 	if(l==NULL) return; 	Linknode *p=l; //无头结点  	 	while(p!=NULL){ 		if(p->data==p->next->data) p->next=p->next->next; 		else p=p->next; 	} } 

13.将两个递增排列的单链表,归并为一个递减排列的单链表(要求利用原来两个单链表的结点存放归并后的单链表)-过

两个链表已经递增次序排列,合并时,均从第一个节点进行比较,较小的头插法链入表中,同时后移工作指针。若有剩余则依次头插法链入新链表中

void merge(Linklist &A,Linklist &B){  	Lnode *pa=A->next,*pb=B->next,*temp; 	A->next=NULL; 	B->next=NULL; 	 	while(pa!=NULL&&pb!=NULL){ 		if(pa->data<=pb->data) { 			temp=pa->next; 			pa->next=A->next; 			A->next=pa; 			pa=temp;		 		} else{ 			temp=pb->next; 			pb->next=B->next; 			B->next=pb; 			pb=temp; 		} 	} 	if(pa!=NULL){ 		temp=pa->next; 		pa->next=A->next; 		A->next=pa; 		pa=temp; 	} else if(pb!=NULL){ 		temp=pb->next; 		pb->next=B->next; 		B->next=pb; 		pb=temp; 	} 	free(B)  ; } 

14.两个带头结点递增有序的单链表,把两个单链表中的公共元素产生新链表,要求不破坏原来的链表

表A、B都有序,可从第一个元素起依次比较A、B两表的元素,若元素值不等,则值小的指针往后移,若元素值相等,则创建一个值等于两节点的元素值的新节点,使用尾插法插入到新链表中,并将两个原表指针后移一位,直到其中一个链表遍历到表尾

void Get_common(Linklist A,Linklist B){  	 Lnode *p=A->next,*q=B->next,*r,*s; 	 Linklist C=(Linklist)malloc(sizeof(Lnode)); 	 r=C; 	  	 while(p!=NULL&&q!=NULL){ 	 	if(p->data<q->data) p=p->next; 	 	else if(p->data>q->data) q=q->next; 	 	else{ 	 		s=(Lnode*)malloc(sizeof(Lnode)); 	 		s->data=p->data;        //尾插  	 		r->next=s; 	 		r=s; 	 		p=p->next; 	 		q=q->next; 		 } 	 } 	 r->next=NULL; } 

15.求两个递增排列的单链表的交集

采用归并的思想,设置两个工作指针pa pb对两个链表进行归并扫描,只有同时出现在两集合中的元素才链接到结果表中且仅保留一个,其他节点全部释放。当一个链表遍历完毕后,释放另一个表中的剩下所有节点

Linklist Union(Linklist &A,Linklist &B){  	Lnode *pa=A->next,*pb=B->next,*temp; 	pc=A; 	 	while(pa!=NULL&&pb!=NULL){ 		 if(pa->data<pb->data){ 		 	temp=pa; 		 	pa=pa->next; 		 	free(temp); 		 } 		 else if(pa->data>pb->data){ 		 	temp=pb; 		 	pb=pb->next; 		 	free(temp); 		 } 		 else{ 		 	pc->next=pa; 		 	pc=pa; 		 	pa=pa->next; 		 	temp=pb; 		 	pb=pb->next; 		 	free(temp); 		 } 	} 	pc->next=NULL; 	free(B); 	return A; } 

16.判断两个单链表中的数值,B中元素是否是A中元素的连续子序列

因为两个整数序列已经存入两个链表中,操作从两个链表的第一个结点开始,若对应数据相等,则后移指针;若数据不等,则A链表从上次开始比较结点的后继开始,B链表仍从第一个结点开始比较,直到B链表到尾表示匹配成功。A链表到尾而B链表未到尾表示失败。操作中应记住A链表每次的开始结点,以便下次匹配时好从其后继开始

int Pattern(Linklist A,Linklist B){  	Lnode *pa=A,*pb=B,*pre=A; 	while(pa!=NULL&&pb!=NULL){ 		if(pa->data==pb->data){   //结点值相同,继续检查  			pa=pa->next; 			pb=pb->next; 		} 		else{     //结点值不同,让pa回到pre->next,让pb回到头上重新比较  			pre=pre->next; 			pa=pre; 			pb=B; 		} 	if(pb==NULL) return 1; 	else return 0; 	} } 

17.判断带头结点的循环双链表是否对称

让p从左向右扫描,q从右向左扫描,直到它们指向同一节点或者结点相邻为止,若它们所指结点值相同,则继续比较,否则返回0,若全部相等,返回1.

int Symmetry(DLinklist L){ 	Dndoe *p=L->next,*q=L->prior; 	while(p!=q&&p->next!=q) 		if(p->data==q->data){ 			p=p->next; 			q=q->prior; 		} 		else return 0; 	return 1; } 

18.两个循环单链表,把后者链接在前者之后,要求链接后的链表仍是循环链表

找到两个链表的尾指针,将第一个链表的尾指针与第二个链表的头结点链接起来,再使之成为循环的

Linklist Link(Linklist &h1,Linklist &h2){ 	Lnode *p=h1,*q=h2; 	while(p->next!=NULL)	p=p->next; 	while(q->next!=NULL)	q=q->next; 	p->next=h2; 	q->next=h1; 	return h1; }

19.结点均为正整数的带头结点单链表,反复找出最小节点并输出,然后删除,直到链表为空,在删除表头结点

表不空时用一个循环遍历单链表,每循环一次查找一个最小值结点(minp保存最小值结点,minpre指向最小值节点前一个节点),输出最小值节点,然后删除,最后释放头结点。

void Delete_min(Linklist &L){ 	Lnode *minp,*minpre,*p,*pre; 	while(L->next!=L){ 		p=L->next; 		pre=L; 		minp=p; 		minpre=pre; 		while(p!=L){ 			if(p->data<minp->data){ 				minp=p; 				minpre=pre; 			} 			pre=p; 			p=p->next; 		} 		printf("%d",minp->data); 		minpre->next=minpre->next->next; 		free(minp); 	} 	free(L); }

20.头指针为L的带表头结点非循环双链表,结点除了前驱pre后继next数据data还包括一个访问频度freq。在链表启用前,全部初始化为0.。每当在链表中进行一次Locate(L,x)运算时,令元素值为x的f、频度域值+1,并使此链表以访问频度排序,且相同频度结点时最近访问的结点排在前面,以便使频繁访问的结点总是靠近表头。请编写符合要求的Locate函数,以指针型返回找到结点的地址

主要考察双链表的查找、删除和插入。

首先在双向链表中查找数据值为x的结点,查到后,将节点从链表上摘下,然后在顺在结点的前驱查找该节点的插入位置(频度递减,且排在同频度第一个,即向前找到第一个比它的频度大的结点,插入位置为该节点之后)并插入到该位置

DLinklist Locate(DLinklist &L,int x){ 	Dnode *p=L->next,*pre; 	while(p&&p->data!=x) p=p->next; 	if(!p){ 		printf("不存在值为x的结点n"); 		exit(0); 	} 	else{ 		p->freq++; 		pre=p->pred; 		p->next->pred=p->pred; 		p->pred->next=p->next; 		while(pre!=L&&pre->freq<=p->freq) pre=pre->pred; 		p->next=pre->next; 		pre->next->pred=p; 		p->pred=pre; 		pre->next=p; 	} 	return p; }

栈p66 3-5


3.判定栈操作序列是否合法

依次逐一扫描入栈出栈序列,每扫描至任一位置均需检查出栈次数是否小于入栈次数,若大于则为非法序列。扫描结束后,再判断入栈和出栈次序是否相等,若不相等则不合题意。

bool Judge(char A[]){ 	int i=0;   //用来遍历  	int j=k=0; 	while(A[i]!=''){ 		switch(A[i]){ 			case 'I':  j++; break; 			case 'O':  k++; 			if(k>j) { 				printf("序列非法n"); 				exit(0); 			}          		} 		i++; 	} 	if(j!=k){ 		printf("序列非法n"); 		return false;	 	} 	else{ 		printf("序列合法n"); 		return true; 	} }

4.单链表n个结点,头指针L,存储字符型数据,判断字符是否对称。

使用栈来判断链表中的数据是否中心对称。让链表的前一半元素依次进栈。在处理链表的后一半元素时,当访问到链表的一个元素后,就从栈中弹出一个元素,两个元素比较,若相等,则将链表中的下一个元素与栈中再弹出的元素比较,直至链表到尾。这时若栈时空栈,则得出链表中心对称的结论;否则,当链表中的一个元素与栈中弹出元素不等时,结论文链表非中心对称,结束算法的执行。

bool dc(Linklist L,int n){ 	int i; 	char s[n/2]; 	Lnode *p=L->next; 	 	for(i=0;i<n/2;i++){ 		s[i]=p->data; 		p=p->next; 	} 	i--; 	if(n%2==1) p=p->next; 	while(p!=NULL&&s[i]==p->data){ 		i--; 		p=p->next; 	} 	if(p==NULL) return true; 	else return false;	 }

5.两个顺序栈共享0-Maxsize-1的存储区,请设计s1 s2有关出入栈的操作

两个栈共享向量空间,将两个栈的栈底设在向量两端,初始时,s1栈顶指针为-1,s2栈顶指针为Maxsize,两个栈顶指针相邻时为栈满。两个栈顶相向,迎面增长,栈顶指针指向栈顶元素。

#define Maxsize 100 #define elementype int typedef struct { 	elementype stack[Maxsize]; 	int top[2]; }stk; stk s;  int push(int i,elementype x){    //i时栈号 //入栈成功返回1,否则返回0     if(i<0||i>1){    		printf("输入栈号不对"); 		exit(0);    }    if(s.top[1]-s.top[0]==1){    		printf("栈满");    		return 0;    }    switch(i){    		case 0: s.stack[++s.top[0]]=x; 		   		return 1;break; 		case 1: s.stack[--s.top[1]]=x; 				return 1;    } } int pop(int i){ 	//出栈成功返回栈顶元素,否则返回-1     if(i<0||i>1){    		printf("输入栈号不对"); 		exit(0);    }    switch(i){    		case 0:     			if(s.top[0]==-1){    				printf("栈空");    				return -1; 			} 			else return  s.stack[s.top[0]--]; 		case 1: 			if(s.top[1]==Maxsize) { 				printf("栈空");    				return -1;  			} 			else return s.stack[s.top[1]++];    } }

天勤9、编写算法将非负十进制N转换为二进制

void transform(int N){ 	int i,result=0; 	int stack[maxSize],top=-1; 	while(N!=0){ 		i=N%2; 		N=N/2; 		stack[++top]=i; 	} 	while(top!=-1){ 		i=stack[top]; 		--top; 		result=result*10+i; 	} 	return result; }

 


队列p81 1-3


1.用标志域tag0或1来区分循环队列空满,请编写入队和出队算法

初始状态:tag=0   front=rear=0

#define Maxsize 100 typedef struct{ 	int front,rear,tag; 	int data[Maxsize]; }Q; int enque(sqQue &Q,elementype x){ 	if(Q.front==Q.rear&&Q.tag==1) return 0; 	Q.data[Q.rear]=x;   //rear指向空位置  	Q.rear=(Q.rear+1)%Maxsize; 	Q.tag=1;   //可能队满  	return 1; }  int deque(sqQue &Q,elementype x){ 	if(Q.rear==Q.front&&Q.tag==0) return 0; 	x=Q.data[Q.front];   //front指向队头元素  	Q.front=(Q.front+1)%Maxsize; 	Q.tag=0;        //可能队空  	return 1; }

2.Q是一个队列,S是一个空栈,实现将队列元素逆置

全部出队入栈,全部出栈入队

void reverse(stack S,queue Q){ 	while(!QueueEmpty(Q)){    		x=Dequeue(Q); 		push(S,x);          //出队入栈  	} 	while(!StackEmpty(S)){    //出栈入队  		pop(S,x); 		Enqueue(Q,x); 	} }

3.用两个栈模拟队列

当需要入队,用s1来存放已输入的元素,即s1执行入栈操作

当需要出队时,则对s2执行出栈操作

由于从栈中取出元素的顺序是原顺序的逆序,所以必须先将s1中的所有元素全部出栈并入栈s2,再从s2中执行出栈,即出队,而在执行此操作前必须判断s2是否空,否则导致顺序混乱,当两个栈都为空时队列为空。

总结:s2为空时,先将s1中所有元素入栈s2。只有s1满s2空时,才能将s1中的全部元素插入s2。

push(S,x)        	 pop(S,x)             stackempty(S) 空返回1,不空返回0        stackoverflow(S)  满返回1,不满返回0  enqueue dequeue queueempty  bool enqueue(stack &s1,stack &s2,elemtype x){ 	 if(!stackoverflow(s1)){    //S1不满  	 	push(s1,x);    //入队  	 	return true; 	 } 	 if(stackoverflow(s1)&&!stackempty(s2)){  //s1满且s2非空  	 	printf("队列满");    		return false; //不允许1到2去//这种情况时不能入队  	 } 	 if(stackoverflow(s1)&&stackempty(s2)){ 	 	while(!stackempty(s1)){ 	 		pop(s1,x); 	 		push(s2,x); 		 }               //s1全部进入s2,s1空  	 }  	push(s1,x);    //s1空,可以直接入队(进栈s1)  	return true;   } bool dequeue(stack &s1,stack &s2,elemtype x){ 	if(!stackempty(s2)){ 		pop(s2,x); 		return true; 	} 	else if(stackempty(s1)){ 		printf("队空") ; 	} 	else{ 		while(!stackempty(s1)){ 			pop(s1,x); 			push(s2,x); 		} 		pop(s2,x); 	} }

天勤6、假设带头结点的循环链表表示队列,设一个指针指向队尾结点,请写出相应的入队出队算法

int Dequeue(Linklist &rear,int &x){ 	if(rear->next= rear) return 0; 	else{ 		Lnode *p=rear,*temp; 		p=rear->next->next; 		rear->next->next=p->next; 		x=p->data; 		if(p==rear) rear=rear->next; 		free(p); 		return 1;		 	}	 } 

7.如果允许在循环队列的两端都可以插入删除,请写出从队尾删除和从队头插入的算法

typedef struct{ 	int front; 	int rear; 	int data[Maxsize]; }SqQueue; int Dequeue(SqQueue &l,int &x){ 	 if(l.front==l.rear) return 0; 	 else{ 	 	x=l.data[l.rear]; 	 	l.rear=(l.rear+1)%Maxsize; 	 	return 1; 	 } }  int Enqueue(SqQueue &l,int &x){ 	if((l.rear+1)%Maxsize==front)  		return 0; 	else{ 		l.data[l.front]=x; 		l.front=(l.front+1)%MaxSize; 		return 1;		 	} }

栈和队列的应用p90 1-4


1.括号配对

扫描每个字符,遇到左括号进栈,遇到右括号时检查栈顶是否为相应左括号,若是:退栈,否则匹配错误,最后若栈不空也为匹配错误。

bool BracketCheck(char str*){ 	Initstack(s); 	int i=0; 	 	while(str[i]!=''){		 		switch(str[i]){ 		case '(': push(s,'(');break; 		case '{': push(s,'{');break; 		case '[': push(s,'[');break; 		case ')': pop(s,x);if(x!='(') return false;break; 		case '}': pop(s,x);if(x!='{') return false;break; 		case ']': pop(s,x);if(x!='[') return false;break; 		default: break; 		} 		i++; 	} 	if(!isEmpty(s)){ 		 printf("括号不匹配"); 		 return false; 	} 	else{ 		printf("括号匹配"); 		return true;	 	} 	 }

2.车厢调度,两侧单向行驶道,有n节硬座和软座车厢等待调度,对n节车厢做入栈出栈操作,使所有软座排在硬座车厢之前

所有车厢依次前进逐一检查,硬座车厢入栈,等待调度,检查完之后对硬座车厢出栈。

void Train_arrange(char *train){ 	char *p=train,*q=train,c; 	stack s; 	Initstack(s); 	 	while(p!=NULL){ 		if(*p=='H') push(s,'H'); 		else *(q++)=*p; 		p++;		 	} 	while(!stackEmpty){ 		pop(s,c); 		*(q++)=c; 	} }

3.利用栈实现以下递归函数的非递归计算(可以把结构做数组用,结构定义可以在函数内)

设置一个栈用于保存n和对应的Pn(x)值,栈中相邻元素的Pn(x)有题中关系。然后边出栈边计算Pn(x),栈空时得到答案。

汇总汇总

(借图https://blog.csdn.net/qq_33514421)

double p(int n,double x){ 	struct stack{ 		int no; 		double val; 	}st[MaxSize]; //  顺序栈  	 	int top=-1,i; 	double fv1=1,fv2=2*x; //通过初始值计算其余值 	  	for(i=n;i>=2;i--){   //存入n的值  		top++; 		st[top].no=i; 	} 	 	while(top>=0){        //每次循环通过两个值计算出新值存到val中  		st[top].val=2*x*fv2-2*(st[top].no-1)*fv1; 		fv1=fv2; 		fv2=st[top].val; 		top--;    //循环结束时fv2中保存着最后结果  	} 	if(n==0) return fv1;     //条件 1   	return fv2; }

4.汽车过江渡船问题

汽车轮渡口,每次可10辆过江。同类车先到先上船。客车先于货车上传,每上四辆客车,可以上一辆货车。客车不足四辆则货车代替。若无货车等待,允许所有客车上船。

设数组q最大下标为10。假设客车队列为q1,货车队列为q2。若q1充足,则每取四个q1后取一个q2,直到q长度为10.若q1不足,则直接用q2补齐。

汇总

Queue q,q1,q2;  //q1客车队列 q2货车队列  void manager(){ 	int i=0,j=0;         //i计数4辆,j计数车总数  	 	while(j<10){ 		if(!QueueEmpty(q1)&&i<4){  //上四辆客车  			Dequeue(q1,x); 			Enqueue(q,x); 			i++; 			j++; 		} 		else if(i==4&&!QueueEmpty(q2)){ //四辆客车后上一辆货车  			Dequeue(q2,x); 			Enqueue(q,x); 			i=0;    //每上一辆货车i重新计数  			j++; 		} 		else{       //客车队列空货车货车队列空  			while(j<10&&i<4&&!QueueEmpty(q2)){ 				Dequeue(q2,x); 				Enqueue(q,x); 				i++; 				j++; 			} 		i=0; 		} 		if(QueueEmpty(q1)&&QueueEmpty(q2)) j=11; //都不足你也得走  	} }

二叉树的概念 p113 5


已知一棵二叉树按顺序存储结构进行存储,设计算法求编号i、j的最近公共祖先结点

二叉树中任意两个结点必然存在最近的公共祖先结点,最差的情况是根节点,而且从最近的公共祖先结点到根节点全部祖先节点都是公共的。由二叉树顺序存储的性质可知,任意节点i的双亲结点编号为i/2。

求解i、j的最近公共祖先结点的算法步骤如下(设数组下标从1开始存储):

1、若i>j,则结点i的所在层次大于等于结点j的所在层次,结点i的双亲结点为结点i/2,若i/2=j,则找到最近公共祖先结点j,若不等,则令i=i/2,即以该节点i的双亲结点为起点,采用递归的方法继续查找。

2、同理i<=j

重复过程,直到找到他们最近的公共祖先结点为止

ElemType Comm_Ancester(Sqtree T,int i,int j){ 	if(T[i]!='#'&&T[j]!='#'){ 		while(i!=j){ 			if(i>j) i=i/2; 			else j=j/2; 		} 		return T[i]; 	} }

二叉树的遍历和线索二叉树 p126 3-18 


3.编写后序遍历二叉树非递归算法

后序非递归遍历二叉树的顺序是先访问左子树,再访问右子树,最后访问根节点,当用堆栈来存储节点时必须分清返回根节点时是从左子树返回的还是从右子树返回的。所以使用辅助指针r,其指向最近访问过的结点。

汇总

void PostOrder(BiTree T){ 	InitStack(S); 	p=T;     r=NULL; 	while(p||!IsEmpty(S)){ 		if(p){ 			push(S,p); 			p=p->lchild;//向左走到底,全部入栈 		} 		else{ 			GetTop(S,p); 			if(p->rchild&&p->rchild!=r){    //如果有右子树并且没访问过 				p=p->rchild;    //对右子树全部做同样操作 				push(S,p); 				p=p->lchild; 			} 			else{    //没有右子树或右子树访问过了,此时可以输出栈中节点值,这是个根节点(没有左子树也没有右子树或根据后序遍历右子树已经访问过了,此时可以输出根节点了) 				pop(S,p); 				printf("%d",p->data); 				r=p;      //记录最近访问的结点  				p=NULL;    //结点访问完后,重置p指针  			} 		} 	} }

4.试给出二叉树自下而上,从右到左的层次遍历算法(层次遍历算法)

一般层次遍历时自上而下从左到右,这里遍历顺序恰好相反

利用原有的层次遍历算法,出队的同时将各节点指针入栈,在所有节点入栈后再从栈顶开始依次访问。

具体实现如下:1、根节点入队。2、一个元素出队,遍历这个元素。3、依次把这个元素的右孩子左孩子入队。4、队列不空则跳到2,否则结束。

void InvertLevel(BinTree bt){ 	Stack S; 	Queue Q; 	BiTree p; 	 	InitStack(S);    //初始化栈,栈中存放二叉树结点的指针 	InitQueue(Q);      //初始化队列,队列中存放二叉树结点的指针 	EnQueue(Q,bt); 	while(!IsEmpty(Q)){	     		DeQueue(Q,p);    //出队入栈  		Push(S,p);      //入栈  		if(p->lchild) 			EnQueue(Q,p->lchild); //入队左右孩子  		if(p->rchild) 			EnQueue(Q,p->rchild); 	} //队空时,全部进栈了  	while(!IsEmpty(S)){ 		Pop(S,p);              //出栈可得反向序列  		printf("%d",p->data); 	}                        }  基于层次遍历 void LevelOrder(BiTree T){     Queue  Q; 	InitQueue(Q); 	BiTree p; 	EnQueue(Q,T); 	 	while(!IsEmpty(Q)){ 		DeQueue(Q,p); 		visit(p); 		if(p->lchild!=NULL)  EnQueue(Q,p->lchild); 		if(p->rchild!=NULL)  EnQueue(Q,p->rchild);		 	}  } 

5.假设二叉树采用二叉链表存储结构,设计一个非递归算法求二叉树的高度(层次遍历算法)

采用层次遍历的算法,设置变量level记录当前节点所在层数,设置变量last指向当前层最右节点,每次层次遍历出队时与last指针比较,若两者相等,则层数加一,并让last指向下一层的最右节点,直到遍历完成。level的值即为树的高度。

非递归

int Btdepth1(BinTree T){ 	if(T==NULL)  return 0; 	int front=-1,rear=-1; 	int last=0,level=0; 	BinTree Q[MaxSize]; 	Q[++rear]=T;     //入队  	BinTree p; 	while(front<rear){ 		p=Q[++front];   //出队  		if(p->lchild) Q[++rear]=p->lchild;   //入队左右孩子  		if(p->rchild) Q[++rear]=p->rchild; 		if(front=last){ 			level++;         //妙,rear每次指向层中最后一个节点  			last=rear; 		}  	} 	return level; }

递归

int Btdepth2(BinTree T){ 	if(T==NULL) return 0; //递归出口  	int ldep=Btdepth(T->lchild); 	int rdep=Btdepth(T->rchild); 	if(ldep>rdep) return ldep+1;  //树的高度=子树最大高度+1  	else return rdep+1; }  

6.根据前序序列和中序序列构造二叉树,假设结点数据值互不相同。

确定根节点在中序中的位置,将中序序列分为两个子序列,递归处理直到所处理的子序列只剩下一个元素

汇总

BTnode *CreateBt(char pre[],char in[],int l1,int r1,int l2,int r2){ 	BTnode *s=(BTnode *)malloc(sizeof(BTnode)); 	int i; 	if(l1>r1) return NULL;	 	s->lchild=s->rchild=NULL; 	for(i=l2;i<=r2;i++) 		if(in[i]==pre[l1]) break; 	s->data=in[i];   //确定根节点位置  	s->lchild=CreateBt(pre,in,l1+1,l1+i-l2,l2,i-1); 	s->rchild=CreateBt(pre,in,l1+i-l2+1,r1,i+1,r2); 	return s;  }   

7.二叉树按二叉链表形式存储,写一个判别给定二叉树是否是完全二叉树的算法(层次遍历算法)

根据完全二叉树的定义,具有n个结点的完全二叉树和满二叉树中编号从1-n的结点一一对应。

采用层次遍历算法,将所有结点加入队列(包括空节点)。遇到空节点时,看其后是否右非空节点。若有,则不是完全二叉树。

bool IsComplete(BiTree T){ 	InitQueue(Q); 	if(T==NULL)   		return 1;//空树为满二叉树 	EnQueue(Q,T); 	while(!IsEmpty(Q)){ 		DeQueue(Q,p); 		if(p!=NULL){ 			EnQueue(Q,p->rchild); 			EnQueue(Q,p->lchild); 		} 		else 			while(!IsEmpty(Q)){ 	 //遍历的时候空节点也入队了,此时表示出现结点为空结点而队列非空 	 //若空节点之后又出现非空节点,那么一定不是完全二叉树  				DeQueue(Q,p); 				if(p) return 0; 			} 	}  	return 1; }

8.假设二叉树采用二叉链表存储结构存储,设计一个算法,计算给定二叉树的所有双分支结点个数(中序遍历算法)

递归模型 f(b) 如下:(是双分支结点,则此节点+左右子树中的双分支节点,否则不加)

汇总

int DsonNode(BiTree b){ 	if(b==NULL)  		return 0; 	else if(b->rchild!=NULL&&b->lchild!=NULL) 		return DsonNode(b->rchild)+DsonNode(b->lchild)+1; //是双分支就+1  	else  		return DsonNode(b->rchild)+DsonNode(b->lchild); //不是就+0  }

 改造二叉树递归遍历算法

(二叉树的前中后序遍历算法中的visit根节点,可以根据题目的需要做改变)设计一个全局变量cnt用于计数双分支结点个数

int cnt=0; void InOrder(BiTree T){ 	if(T!=NULL){ 		InOrder(T->lchild); 		if(T->lchild!=NULL&&T->rchild!=NULL) 			cnt++; 		InOrder(T->rchild); 	} }

9.设树B是一棵采用链式结构存储的二叉树,编写一个把树B中所有节点的左右子树交换的函数(后序遍历算法)

采用递归算实现交换二叉树的左右子树,首先交换b节点的左孩子的左右子树,然后交换b右孩子的左右子树,最后交换b节点的左右孩子,当结点为空时递归结束(后序遍历的思想)(前中后序都可以,就是对遍历到的每个结点的孩子进行交换,与遍历顺序其实是无关的,前序就是:先交换b的左右孩子然后再对b的左右子树交换,中序就是:先交换b的左孩子的左右子树,然后交换b的左右孩子,最后交换b的右孩子的左右子树)

void swap(BiTree b){ 	if(b){ 		swap(b->lchild); 		swap(b->rchild); 		temp=b->lchild; 		b->lchild=b->rchild; 		b->rchild=temp; 	} }

10.假设二叉树采用二叉链表存储结构存储,设计一个算法,求先序遍历序列中第k(1<=k<=二叉树结点个数)个结点的值(前序遍历算法)

设置一个全局变量 i 记录已访问过的结点的序号,其初值是根节点在先序序列中的序号,即1.当二叉树b为空时返回特殊字符“#”,当i==k时表示找到了满足条件的结点,返回b->data;当i!=k时,递归的在左子树中查找,若找到则返回该值,否则继续递归的在右子树中查找,并返回其结果。 (二叉树的遍历算法可以引申出大量的算法题,必须熟练掌握(本题基于前序遍历算法:访问根节点,递归访问左右子树(添加改动:对根节点进行递归出口判断第k个值是否存在))

int i=1;         //记录已经访问过的序号 ElemType PreNode(BiTree b,int k){  //前序遍历根据需要改造  	if(b==NULL)  return '#'; 	if(i==k)     return b->data; 	i++;      	char ch; 	ch=PreNode(b->lchild,k);    	if(ch!='#')    return ch; 	else{         		ch=PreNode(b->rchild,k);  		return ch;    //因为题目限定了一定能找到,所以不在左子树必定在右子树,无需进行找不到的判断 	} }

11.已知二叉树以二叉链表存储,编写算法:对于树中每个元素值为x的结点,删去以它为根的子树,释放相应的空间(删除子树:后序遍历算法,找父节点:层次遍历算法)

删除以元素值x为根的子树,只要能删除其左右子树,就可以释放值为x的根节点,因此宜采用后序遍历

删除值为x的结点,意味着应将其父节点的左右孩子指针置空,用层次遍历易于找到某结点的父节点。本题要求删除树种每个元素值为x的结点的子树,因此要遍历完整二叉树。

void DeleteXTree(BiTree bt){  //后序遍历:删除树,先删左右子树,再删根节点  	if(bt){ 		DeleteXTree(bt->lchild); 		DeleteXTree(bt->rchild); 		free(bt); 	}	 }  void Search(BiTree bt,Elemtype x){ 	Queue Q; 	InitQueue(Q); 	EnQueue(Q,bt); 	 	if(bt==NULL) return;	 	if(bt->data==x){ 		DeleteXTree(bt); 		return ; 	} 	  	while(!IsEmpty(Q)){ 		DeQueue(Q,p); 		if(p->lchild){ 			if(p->lchild->data==x){ 				DeleteXTree(p->lchild); 				p->lchild=NULL; 			} 			else	EnQueue(Q,p->lchild); 		}		 		if(p->rchild){ 			if(p->rchild->data==x){ 				DeleteXTree(p->rchild); 				p->rchild=NULL; 			} 			else 	EnQueue(Q,p->rchild);    				 		} 	}	  }

12.在二叉树中查找值为x的结点,试编写算法打印值为x的结点的所有祖先,假设值为x的结点不多于一个

一般情况下树的题目,用递归比较好

判断左右子树里有没有x,从下向上输出所有祖先结点

bool Ancestors(Node *root,int x){ 	if(root==NULL) return false; 	if(root->data==x) return true;  //这两个出口为下一个递归判断条件服务  	if(Ancestors(root->lchild,x)||Ancestors(root->rchild,x)){ 		printf("%d",root->data);   //任一孩子有x就输出这个根  		return true; 	} 	return false; } 

13.设一棵二叉树的结点结构为(LLINK,INFO,RLINK),ROOT为指向该二叉树根节点的指针,p和q分别为指向该二叉树种任意两个结点的指针,试编写算法ANCESTOR(ROOT,p,q,r),找到p和q的最近公共祖先结点r。(递归)

递归:递归遍历左右子树,找pq,递归结束后可以知道pq在左子树还是右子树,

  1. 若pq都不在左子树,那么他们都在右子树,右子树先遍历到的结点就是公共祖先
  2. 若left不空,说明左子树中有节点,那么看看右子树,若right时空的,说明全在左子树,那么左子树中先遍历到的就是公共祖先
  3. 否则,left和right都不空,说明pq在root异侧,则root就是公共祖先
  4. 注意:结点本身也可以是自己的祖先
 struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q){ // 如果 p和q中有等于 root的,那么它们的最近公共祖先即为root(一个节点也可以是它自己的祖先) 	if(root==NULL||root==q||root==p) 		return root;  // 递归遍历左右子树,只要在左子树中找到了p或q,则先找到谁就返回谁 	struct TreeNode *left = lowestCommonAncestor(root->left, p, q); 	struct TreeNode *right = lowestCommonAncestor(root->right, p, q);  // 如果在左子树中 p和 q都找不到,则 p和 q一定都在右子树中, //右子树中先遍历到的那个就是最近公共祖先(一个节点也可以是它自己的祖先) 	if(left==NULL)  		return right;  // 否则,如果 left不为空,在左子树中有找到节点(p或q), //这时候要再判断一下右子树中的情况,如果在右子树中,p和q都找不到, //则 p和q一定都在左子树中,左子树中先遍历到的那个就是最近公共祖先(一个节点也可以是它自己的祖先) 	if(right==NULL)  		return left;  //否则,当 left和 right均不为空时,说明 p、q节点分别在 root异侧, 最近公共祖先即为 root   	return root;  }

14.假设二叉树采用二叉链表存储,设计算法,求非空二叉树的宽度(即具有结点树最多的那一层的结点个数)

采用层次遍历的方法求出所有节点的层次,并将所有结点和对应层次放在一个队列中,然后通过扫描队列求出各层的结点总数,最大的层结点总数即为二叉树的宽度。 

15.设有一棵满二叉树(所有节点值均不同),已知其先序序列为pre,设计一个算法求其后序序列post。

对于一般二叉树仅根据先序序列或后序序列不能确定另一个遍历序列,但是满二叉树任意一个节点的左右子树含有相等的节点数,同时,先序序列的第一个节点作为后序序列的最后一个节点。

void PreToPost(ElemType pre[],int l1,int h1,ElemType post[],int l2,int h2){ 	int half; 	if(h1>=l1){ 		post[h2]=pre[l1]; 		half=(h1-l1)/2; 		PreToPost(pre,l1+1,l1+half,post,l2,l2+half-1);  //转换左子树  		PreToPost(pre,l1+half+1,h1,post,l2+half,h2-1);   //转换右子树  	} }

16.设计一个算法将二叉树的叶节点按从左到右的顺序连成一个单链表,表头指针为head。二叉树按二叉链表的方式存储,链接时用叶节点的右指针域来存放单链表指针

通常使用的树的遍历对叶节点的访问都是从左到右,所以都可以,这里采用中序递归遍历。设置前驱指针为pre,初始为空。第一个叶节点由指针head指向,遍历到叶节点时,就将它前驱的rchild指针指向它,最后一个叶节点的rchild为空。 

Link head,pre=NULL; LinkList InOrder(BiTree bt){ 	 if(bt){         InOrder(bt->lchild);         if(bt->lchild==NULL&&bt->rchild==NULL){             if(pre==NULL){                 head=bt;                 pre=bt;             }             else{                 pre->rchild=bt;                 pre=bt;             }             InOrder(bt->rchild);             pre->rchild=NULL;         } 	 } 	 return head; }

17.试设计判断两棵二叉树是否相似的算法。所谓二叉树T1T2相似,指的是都空或都只有一个根节点或左子树与左子树相似且右子树与右子树相似 

本题采用递归思想,若都空,则相似;若一个空一个不空,则必然不相似;否则递归的比较他们的左右子树是否相似

两空,一空,都不空的三种情况

int Similar(BiTree T1,BiTree T2){ 	int leftS,rightS; 	if(T1==NULL&&T2==NULL) return 1; 	esle if(T1==NULL||T2==NULL)   return 0; 	else{ 		leftS=similar(T1->lchild,T2->lchild); 		rightS=similar(T1->rchild,T2->rchild); 		return leftS&&rightS;  //仅当都为1的时候返回1  	} } 

天勤(1)设计算法计算给定二叉树的所有节点

实质遍历二叉树

int n=0;    //先序遍历 void count(BTnode *p){ 	if(p){ 		++n; 		count(p->lchild); 		count(p->rchild); 	} }  //后序遍历 int count(BTnode *p){ 	int n1,n2; 	if(p==NULL){ 		return 0; 	} 	else { 		n1=count(p->lchild); 		n2=count(p->rchild); 		return 1+n1+n2; 	} }

(2)计算给定二叉树的所有叶子结点

int n=0;     //采用前序遍历  void count(BTnode *p){ 	if(p){ 		if(p->lchild==NULL&&p->rchild==NULL) ++n; 		count(p->lchild); 		count(p->rchild); 	} }   //对应后序遍历  int count(BTnode *p){ 	int n1,n2; 	if(p==NULL){ 		return 0; 	}else if(p->lchild==NULL&&p->rchild==NULL)   return 1; 	else { 		n1=count(p->lchild); 		n2=count(p->rchild); 		return n1+n2; 	} }  

(5)增加一个指向双亲结点的parent指针,设计算法给这个指针赋值,并输出所有节点到根节点的路径

修改二叉链表结点数据结构,将所有结点的parent指针指向双亲结点,打印所有节点到根节点的路径。

typedef struct BTnode{ 	char data; 	struct BTnode *rchild; 	struct BTnode *lchild; 	struct BTnode *parent; }BTnode; //给parent指针赋值  void triBTree(BTnode *p,BTnode *q){//q始终指向当前访问结点p的双亲结点  	if(p){ 		p->parent=q; 		q=p; 		triBTree(p->lchild,q); 		triBTree(p->rchild,q); 	}	 } //任给一个节点求其到根节点的路径  void printPath(BTnode *p){ 	while(p){ 		printf("%d",p->data); 		p=p->parent; 	} }

(6)假设满二叉树b的先序序列存在长度为n的数组中,设计算法将其转换为后序遍历序列

只需将根节点移动到整个序列的末尾,然后继续递归处理序列的前一半和后一半

void change(char pre[],int l1,int r1,char post[],int l2,int r2){ 	if(l1<=r1){         int half=(l1-r1)/2; 		post[r2]=pre[l1]; 		change(pre,l1+1,half+l1,post,l2,half+l2-1); 		change(pre,half+l1+1,r1,post,half+l2,r2-1); 	} }

(7)二叉链表存储二叉树,设计算法求二叉树b中值为x的结点的层号

int L=1; void high_x(BTnode *b,int x){ 	if(b){ 		if(p->data==x) printf("%d",L); 		++L; 		high_x(p->lchild,x); 		high_x(p->rchild,x); 		--L;	 	} }

(10)二叉树的双序遍历:对于二叉树的每个节点,先访问这个节点,再按照双序遍历它的左子树,然后再一次访问这个节点,再双序遍历右子树。

void Double_order(BTnode *t){ 	if(t){ 		Visit(t); //已经定义的访问t的函数  		Double_order(t->lchild); 		Visit(t) ; 		Double_order(t->rchild); 	} }

 (11)设中序线索二叉树类型为TBTnode *InThTree

(1)设计算法在一棵中序线索二叉树中寻找节点t的子树上中序下的最后一个节点

沿着t的右子树链一直走下去,直到遇到其右指针为右线索的节点为止

TBTnode *inLast(TBTnode *t){ 	TBTnode *p=t; 	while(p&&!p->rtag)	p=p->rchild; 	return p; }

(2)找t的中序前驱

若t有左线索,则其左线索所指结点即为中序前驱;若无左线索,则其左子树中中序最后一个节点为它的中序前驱

TBTnode *inPrior(TBTnode *t){ 	TBTnode *p=t->lchild; 	if(p&&!t->ltag) p=inLast(p); 	return p; }

(3)找t的前序后继

分三种情况:1、节点有左孩子 2、节点只有右孩子  3、节点没有孩子,此时其前序后继是此节点的右线索走到无右线索节点这个节点就是前序后继

TBTnode *preNext(TBTnode *t){ 	TBTnode *p; 	if(!t->ltag) p=t->lchild; 	else if(!t->rtag) p=t->rchild; 	else{ 		p=t; 		while(p&&p->rtag) p=p->rchild; 		if(p) p=p->rchild; 	} 	return p; }

 


树、森林 p152 5-7


5.编程求以孩子兄弟表示法存储的森林的叶子节点数

森林以孩子兄弟表示法存储(只要结点没有左孩子,则必定是叶子)时,若结点没有孩子,则必定是叶子,总的叶子结点个数是孩子子树上的叶子树和兄弟子树上的叶节点个数之和。

  • 没有左孩子,叶子数=1+兄弟子树叶子数
  • 有左孩子,叶子数=孩子子树叶子数+兄弟子树叶子数
typedef struct node{ 	ElemType data; 	struct node *fch,*nsib; }*Tree;  int Leaves(Tree t){ 	if(t==NULL) return 0; 	if(t->fch==NULL) return 1+Leaves(t->nsib); 	else return Leaves(t->fch)+Leaves(t->nsib); }

6.以孩子兄弟链表为存储结构,请设计递归算法求树的深度(层次遍历)

由孩子兄弟链表表示的树,求高度的算法思想如下:采用递归算法,若树为空,高度为0;否则高度为第一子女树高+1和兄弟子树高度的大者。左孩子右兄弟,只有孩子节点增加高度(只有第一子女+1是树的高度,其余的子女全是作为兄弟,所以不增加1)

int Height(CSTree bt){ 	int hc,hs; 	if(bt==NULL) return 0; 	else{       //否则高度取子女高度+1和兄弟子树高度的大者  		hc=height(bt->firstchild);   //第一子女树高  		hs=height(bt->nextsibling);  //兄弟树高  		if(hc+1>hs) return hc+1; 		else return hs; 	} } 

 


树和二叉树的应用 p168 6-10


6.判断给定二叉树是否是二叉排序树

对于二叉排序树来说,其中序遍历序列为一个递增有序序列。因此,对给定的二叉树进行中序遍历,若始终能保持递增,则为二叉排序树。

KeyType predt=-32767;   //保存当前节点中序前驱的值,初值为负无穷   int JudgeBST(BiTree bt){ 	int b1,b2;     //用来确认是否是二叉排序树  	if(bt==NULL) return 1;    //空树  	else{ 		b1=JudgeBST(bt->lchild);   //判断左子树  		if(b1==0||predt>=bt->data) return 0;      //若返回值为0或前驱大于当前节点,则不是二叉排序树  		predt=bt->data;     //保存当前节点值  		b2=JudgeBST(bt->child);      //判断右子树  		return b2;                   //返回右子树判断结果   	} }

7.求出指定节点在给定二叉排序树中的层次

实际上就是二分查找,每次比较一次就层数加一。设二叉树采用二叉链表存储结构。在二叉排序树中,查找一次就下降一层。因此,查找该节点所用的次数就是该节点在二叉排序树中的层次。采用二叉排序树非递归查找算法,用n保存查找层次,每查找一次,n就加1,直到找到相应的结点

int level(BiTree bt,BSTNode *p){ 	int n=0;    //统计查找次数  	BiTree t=bt; 	if(bt!=NULL){ 		n++;   //树非空则n最低为1  		while(t->data!=p->data){ 			if(t->data<p->data) t=t->rchild; 			else t=t->lchild; 			n++;//比较一次层数+1  		} 	} 	return n; } 

8.利用二叉树遍历的思想编写一个判断二叉树是否是平衡二叉树的算法(后序遍历)

递归判断根节点和左右子树是否平衡。(高度用来判断根,平衡标记用来判断子树)设置二叉树的平衡标记balance,标记返回二叉树bt是否为平衡二叉树,若为平衡二叉树,则返回1,否则返回0,h为二叉树bt的高度。采用后序递归遍历的思想:

void Judge_AVL(BiTree bt,int &balance,int &h){  //为了返回多个值,h在递归里要用,不可省略  	int bl=0,br=0,hl=0,hr=0;    //左右子树平衡标记和高度  	if(bt==NULL){ 		h=0; 		balance=1; 	} 	else if(bt->lchild==NULL||bt->rchild==NULL){ 		h=1; 		balance=1; 	} 	else{ 		Judge_AVL(bt->lchild,bl,hl); 		Judge_AVL(bt->rchild,br,hr); 		h=(hl>hr?hl:hr)+1; 		if(abs(hl-hr)<2) balance=bl&&br; 		else balance=0;  	} }

9.求给定二叉排序树中最大和最小的关键字

最小节点是左子树最左,最大节点是右子树最右

KeyType MinKey(BSTNode *bt){ 	while(bt->lchild!=NULL) 		bt=bt->lchild; 	return bt->data;	 } KeyType MaxKey(BSTNode *bt){ 	while(bt->rchild!=NULL) 		bt=bt->rchild; 	return bt->data; }

10.设计算法,从大到小输出二叉排序树中所有值不小于k的关键字(中序遍历 )

对二叉排序树来说中序遍历得到递增序列,题要求递减序列,所以采用右根左的中序递归遍历,一边遍历一边输出结点值,直到找到k(先遍历右子树,再访问根节点,后遍历左子树)

void OutPut(BSRNode *bt,KeyType k){ 	if(bt==NULL) return; 	if(bt->rchild!=NULL) OutPut(bt->rchild,k); 	if(bt->data>=k) printf("%d",bt->data); 	if(bt->lchild!=NULL) OutPut(bt->lchild,k); }

 


顺序查找和折半查找 p247 6-7


6.折半查找的递归算法

ElemType array[]; int BinSearchRec(ElemType key,int low,int high){ 	if(low>high) return -1; 	int mid=(low+high)/2; 	if(key>array[mid]) 		Search(key,mid+1,high); 	else if(key<array[mid]) 		Search(key,low,mid-1); 	else return mid; } 

7.将经常被检索的结点尽量置于表的前端

若找到指定节点,将该节点与其前驱节点(若存在)交换。设计顺序结构和链式结构的线性表上实现上述策略的顺序检索算法。

int SeqSearch(dataType R[],Elemtype k){ 	int i=0; 	while((R[i].key!=k)&&(i<n)) i++; 	if(i<n&&i>0){ 		temp=R[i];R[i]=R[i-1];R[i-1]=temp;   //找到就交换  		return --i; //返回交换后的位置  	} 	return -1;    //交换失败  }

交换排序 p303 2-7 


2.双向冒泡算法,在正反两个方向交替进行扫描,即第一趟把关键字最大的元素放在序列最后,第二趟把关键字最小的元素放在序列最前,如此反复进行。

  • 奇数趟时,从前向后比较相邻元素的关键字,遇到逆序即交换,直到把序列中关键字最大的元素移动到序列尾部。

偶数趟时,从后往前比较相邻元素的关键字,遇到逆序即交换,直到把序列中关键字最小的元素移动到序列前端。

void bubblesort(ElemType A[],int n){ 	int low=0,high=n-1; 	bool flag=true;     //标记是否交换  	while(low<high&&flag){ 		flag=false; 		for(i=low;i<high;i++){ 			if(a[i]>a[i+1]){ 				swap(a[i],a[i+1]); 				flag=true; 			} 			high--;          //更新上界  		} 		 		for(i=high;i>low;i--){ 			if(a[i]<a[i-1]){ 				swap(a[i],a[i-1]); 				flag=true; 			} 			low--;       //每次冒泡确定一个元素位置  		}	 	} }

3.已知线性表按顺序存储,且每个元素都是不相同的整数型元素,设计把所有的奇数移动到偶数前面的算法。

  • 可采用基于快速排序的划分思想来设计算法,只需要遍历一次即可,时间On空间O1
  • 假设表为L[1..n]
  • 从前向后找到一个偶数元素L(i)
  • 从后向前找到一个奇数元素L(j)

将二者交换,重复过程指导i>j

void move(ElemType A[],int len){ 	int i=0,j=len-1; 	while(i<j){ 		while(i<j&&A[i]%2!=0) i++; 		while(i<j&&A[j]%2!=1) j--; 		if(i<j){ 			swap(A[i],A[j]); 			i++;j--; 		} 	} } 

5.编写算法,在数组L[1..n]中找出第k小的元素(即从小到大排序后处于第k个位置的元素)

  • 基于快排的划分操作
  • 从数组中选择枢轴pivot,进行快排的划分操作,表被划分为L[1..m-1]L[m+1..n],其中L(m)=pivot
  • 落在哪个区间上就对这个区间递归查找这个元素
  • 时间复杂On,空间复杂取决于划分方法
int searchkth(int A[],int low,int high,int k){ 	int pivot=A[low]; 	int low_temp=low; 	int high_temp=high; 	while(low<high){ 		while(low<high&&A[high]>=pivot)	--high;  		A[low]=A[high];	 		while(low<high&&A[low]<=pivot)	++low; 		A[high]=A[low];	 	} 	a[low]=pivot; 	if(low==k) return low; 	else if(low>k)	return  searchkth(a,low_temp,low-1,k); 	else    return  searchkth(a,low+1,high_temp,k-low); }

7.荷兰国旗问题:设有一个仅由红白蓝三种颜色的条块组成的条块序列,编写时间复杂度On的算法,使这些条块按红白蓝顺序排好。

  • 顺序扫描线性表,将红色交换到最前面,蓝色交换到最后
  • 设立三个指针,j为工作指针表示当前扫描的元素,i以前全部为红色,k以后全部为蓝色。根据j所指示元素的颜色,决定将其交换到序列的前部或尾部
typedef enum{ 	RED;WHITE;BLUE;  }color;  void Flag(color a[],int n){ 	int i=0,j=0,k=n-1; 	while(j<=k){ 		switch(a[j]){ 			case RED:swap(a[i],a[j]);i++;j++;break; 			case WHITE:j++;break; 			case BLUE:swap(a[j],a[k]);k--; 		} 	} } 

选择排序 p314 4-5 


4.编写算法,在基于单链表表示的待排序关键字序列上进行简单选择排序

  • 每趟在原始链表中摘下关键字最大的结点,插入到结果链表的最前端
void selectSort(Linklist &l){ 	 Linknode *h=l,*p,*pre,*max,*maxpre; 	 l=NULL; 	 while(h!=NULL){ 	 	p=max=h;pre=maxpre=NULL; 	 	while(p!=NULL){  //找最大结点  	 		if(p->data>max->data){ 	 			max=p; 	 			maxpre=pre; 			} 			pre=p; 			p=p->next;  		 } 		 if(max==h) h=h->next;   //找了一圈发现最大的就在头上,那么继续对剩下的元素进行选择排序  		 else maxpre->next=max->next;     //否则摘下结点  		 max->next=l;     //链接到已经有序的链表中  		 l=s; 	 } }

5.设计算法判断数据序列是否构成小根堆

  • 将顺序表L[1..n]视为完全二叉树,扫描所有分支节点,遇到孩子节点的关键字小于根节点的关键字时返回false,扫描完成后返回true
bool IsMinHeap(ElemType A[],int len){ 	if(len%2==0){      //说明有一个单分支结点  		if(A[len/2]>A[len])  return false;  //判断单分支结点  		for(i=len/2-1;i>=1;i--){                 //判断所有双分支  			if(A[i]>A[2*i]||A[i]>A[2*i+1]) return false; 		} 	} 	else{ 		for(i=len/2;i>=1;i--){ 			if(A[i]>A[2*i]||A[i]>A[2*i+1]) return false; 		} 	} 	return true; }

各种排序算法的比较和应用 p327 2-3 


2.顺序表A[]中元素存储在下标1~m+n范围内,两部分都递增有序,设计算法使整个顺序表有序

  • 从m+1开始,将后n个元素依次插入前面的有序表中(插入排序)
void Insert_sort(int A[],int m,int n){ 	int i,j; 	for(i=m+1;i<=m+n;i++){ 		A[0]=A[i]; 		for(j=i-1;A[j]>A[0];j--) A[j+1]=A[j]; 		A[j+1]=A[0]; 	} }

3.计数排序:对一个待排序的表(数组表示)进行排序,将排序结果放在另一个新表中。表中所有关键码互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统计表中有多少个记录的关键码比该记录的关键码小,假设针对某个记录统计出的计数值为c,则这个记录在新有序表中的合适存放位置为c

  • 统计关键字比它小的元素个数,然后放到另一个数组的对应位置上
void CountSort(int A[],int B[],int n){ 	int cnt; 	for(i=0;i<n;i++){            //对每个元素 		for(j=0,cnt=0;j<n;j++){    //统计比它小的元素个数 			if(A[j].key<A[i].key) cnt++; 		} 		B[cnt]=A[i];//放在对应位置 	} }

串 p103 


(1)、将串str中所有值为ch1的字符转换成ch2的字符,如果str为空串,或者串中不含值为ch1的字符则什么都不做

(2)、实现串str的逆转函数,如果str为空串,则什么都不做

(3)、删除str中值为ch的所有字符,如果str为空,或不含有ch的字符则什么都不做

typedef struct{ 	char ch[maxSize]; 	int length; }Str;   void delete_ch(Str &str,char ch){   	while(str.length!=0){  		for(int i=0;i<str.length;){ 			if(str.ch[i]==ch){ 				for(int j=i;j<str.length-1;j++)  					str.ch[j]=str.ch[j+1]; 				str.length--; 		}else i++; 		str.ch[str.length]='';	 		}	 	} }

(4)、从串str中的pos位置起,求出与substr串匹配的子串位置

void get_next(Str substr,int next[]){ 	int i=1,j=0; //j是当前子串最长相等前后缀长度 	next[1]=0; 	while(i<substr.length){ 		if(j==0||substr.ch[i]==substr.ch[j]){ 			++i;++j;next[i]=j;    //01是确定的 		} 		else j=next[j]; 	} }  int Kmp(Str str,Str substr,int next[],int pos){ 	int i=pos,j=1; 	while(i<=str.length&&j<=substr.length){ 		if(j==0||str.ch[i]==substr.ch[j]){ 			++i;++j; 		} 		else j=next[j]; 	} 	if(j>substr.length) return i-substr.length;//得到与模式串匹配的子串的首字符位置 	else return 0; }

2、采用定长顺序存储表示串,编写函数,删除串中下标为i的字符开始,如果第i个字符后没有足够的j个字符,则有几个删除几个

typedef struct{ 	char ch[maxSize]; 	int length; }Str;   int Delete_i(Str &str,int i,int j){ 	if(i<str.length&&i>=0&&j>=0){ 		for(int k=i+j;k<str.length;k++){ 			str.ch[k-j]=str.ch[k]; 		} 		str.length-=(str.length-i<j?str.length-i:j); 	} 	str.ch[str.length]=''; }

4、编写一个函数计算子串在主串中的出现次数,不考虑子串重叠。

5、构造串的链表结点数据结构,编写函数找出串str1中第一个不在str2中出现的字符

typedef struct SNode{ 	char data; 	struct Str *next; }SNode;  char findfirst(SNode &str1,SNode &str2){ 	SNode *p=str1,*q=str2; 	while(p){ 		bool flag=true; 		while(q){ 			if(p->data==q->data){ 				flag=true; 				break;	 			} 			q=q->next; 			if(flag==false) return p->data;  		} 		p=p->next;			 	} }

数组、矩阵、广义表 p122 


天勤1、将所有的负数放在正值之前,R[0..n-1]

void Resort(int R[],int n){ 	int i=0,j=n-1; 	int temp; 	while(i<j){ 		while(i<j&&R[i]<0) ++i; 		temp=R[i]; 		while(i<j&&R[j]>0) --j; 		R[i++]=R[j]; 		R[j--]=temp; 	} }

 

1、设数组A[0~n-1]的n个元素中有多个0元素,设计算法将所有非零元素移动到数组前端。

void Move(int A[],int n){ 	int i=-1,j,temp; 	for(int j=0;j<n;j++){ 		if(A[j]!=0){ 			++i; 			if(i!=j){ 				temp=A[i]; 				A[i]=A[j]; 				A[j]=temp; 			} 		}  	} }

2、关于浮点型数组A[0~n-1]设计递归算法实现:(1)求数组A的最大值(2)求数组n个数之和(3)求数组n个数的平均值

find_max(A,0,n-1); float Find_max(float A[],int i,int j){ //	int max=A[0]; //	int pos; //	for(int i=0;i<n;i++){ //		if(A[i]>max){ //			max=A[i]; //			pos=i; //		} //	} //	return pos; 	float max; 	if(i==j) return A[i]; 	else{ 		max=find_max(A,i+1,j); 		if(A[i]>max) return A[i]; 		else return max; 	}  	 } Sum(A,0,n-1); float Sum(float A[],int i,int j){ //	float sum=0; //	for(int i=0;i<n;i++){ //		sum+=A[i]; //	} //	return sum; 	if(i==j) return A[i]; 	else return A[i]+Sum(A,i+1,j); } Average(A,0,n-1); float Average(float A[],int i,int j){ //	float sum=Sum(A,n); //	float average=sum/n; 	if(i==j) return A[i]; 	else return (A[i]+(j-i)*Average(A,i+1,j))/(j-i+1); } 

3、设计算法将数组A的所有奇数移动到偶数之前,不增加存储空间且时间复杂度On

void Move(int A[],int n){ 	int i=0,j=-1,temp; 	while(i<j){ 		while(A[i]%2==1&&i<j)	++i; 		while(A[j]%2==0&&i<j)	--j; 		if(i<j){ 			temp=A[i]; 			A[i]=A[j]; 			A[j]=temp; 			++i; 			--j; 		} 	} }

4、设有一元素为整数的线性表L,存在数组中,设计算法以最后一个元素为准,进行快排一次划分

 

 

 

图的遍历 p206 2-5


2.设计算法,判断一个无向图G是否是一棵树。若是一棵树,则算法返回ture,否则返回false。

  • 一个无向图G是一棵树的条件是,G必须是无回路的连通图或有n-1条边的连通图。
  • 这里采用后者作为判断条件。对连通的判定,可用能否遍历全部顶点来实现。
  • 可以采用深度优先搜索算法在遍历图的过程中统计可能访问到的顶点个数和边的条数,若一次遍历就能访问到n个顶点和n-1条边,则可以断定此图是一棵树。
bool isTree(Graph &G){  //判断树  	for(i=1;i<G.vexnum,i++) 		visited[i]=FALSE;          //初始化所有节点未访问  	int Vnum=0,Enum=0;           //记录顶点数和边数  	DFS(G,1,Vnum,Enum,visited); 	if(Vnum==G,vexnum&&Enum==2(G.vexnum-1)) return  true;          //符合树的条件  	else return false; } void DFS(Graph &G,int v,int &Vnum,int &Enum,int visited[]){   //深度遍历  	visited[v]=TRUE;Vnum++;     //访问标记,访问结点个数+1  	int w=FirstNeighbor(G,v);         //取第一个邻接顶点  	while(w!=-1){          //当邻接结点存在  		Enum++;           //有边存在,边+1       		//函数结束之后,enum是实际边数的两倍 ,注意一下,对应到树的判断  		if(!visited[w])        //没访问过的结点  			DFS(G,w,Ynum,Enum,visited); 		w=NextNeighbor(G,v,w);	  //下一个邻接顶点  	} }

3.写出图的深度优先搜索DFS算法的非递归遍历(图采用邻接表形式)

在深度优先搜索非递归算法中使用了一个栈S来记忆下一步可能访问的顶点,同时使用了一个访问标记数组visited[i]来记忆第i个顶点是否在栈内或曾经在栈内,若是则它以后不能再进栈。

void DFS_Non_R(AGraph& G,int v){ 	int w;//顶点序号 	InitStack(S); 	for(i=0;i<G.vnum;i++) 		visited[i]=FALSE;     //初始都是未访问  	Push(S,v);visited[v]=TRUE;    //入栈并更改状态  	while(!IsEmpty(S)){ 		k=Pop(S);         //退栈  		visit(k);          //访问此节点,这里的访问满足深度搜索的  		for(w=FirstNeighbor(G,k);w>=0;w=NextNeighor(G,k,w)){ //遍历所有k的邻接点  			if(!visited[w]){      //若其邻接点未被访问过则进栈  				Push(S,w); 				visited[w]=true;  //做好标记避免再次入栈  			} //if  		} //for 	}  //while  }

4.分别采用基于深度优先遍历和广度优先遍历算法判别以邻接表方式存储的有向图中是否存在Vi到Vj的路径(i不等于j)。注意,算法中涉及的图的基本操作必须在此存储结构上实现。

两个不同的遍历算法都采用顶点Vi出发,依次遍历图中每个顶点,直到搜索到顶点Vj,若能够搜索到Vj,则说明路径存在。

//深度 int visited[MAXSIZE]={0}; int Exist_Path_DFS(ALGraph G,int i,int j){ 	int p;              //顶点序号  	if(i==j) return 1; 	else{ 		visited[i]=1; 		for(p=FirstNeighbor(G,i);p>=0;p=NextNeighbor(G,i,p)){  //对邻接点遍历  			if(!visited[p]&&Exist_Path_DFS(G,p,j)) 				return 1; 		} 	} 	return 0; }  //广度 (层次遍历) int visited[MAXSIZE]={0}; int Exist_Path_BFS(ALGraph G,int i,int j){ 	InitQueue(Q);EnQueue(Q,i); 	while(!isEmpty(Q)){ 		DeQueue(Q,u); 		visited[u]=1; 		for(p=FirstNeighbor(G,i);p>=0;p=NextNeighbor(G,i,p)){ 			//k=p.adjvex; 			//if(k==j) return 1; 			//else if(!visited[k]) EnQueue(Q,k);              if(p==j) return 1;             else if(!visited[p]) EnQueue(Q,p); 		} 	} 	return 0;  } 

 

本文转自互联网,侵权联系删除汇总

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 汇总
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们