博文
二叉树的遍历问题(2006-10-29 22:41:00)
摘要：问题：某二叉树后序遍序是DACBE ，中序遍历序列是DEBAC，它的前序遍历是?
相关概念解析：概念中的前中后序都代表的是根节点在访问中的次序，左先于右的顺序不变。前序概念是:TLR(根左右)先访问根,再访问左"子树",再访问右"子树".访问左 "子树"也是按照这样的原则在左"子树"中前序的访问. 中序概念是:LTR(左根右) 后序概是:LRT(左右根).类似是很好理解的. 求解过程：1)由后序序列,知根在最后,所以,E是根 2)由E为根,中序序列,知道左"子树"是D(在左边),右"子树"是BAC.(在右边) 3)右"子树"BAC中,由后序序列知,B为根,所以AC为根B的右"子树".(在右边) 4)在右"子树"AC中,由后序序列知,C为根,A为其左子树(在左边啊) 树很容易就画出来了(你自己画吧,我怎么画啊呵呵).然后,对它进行前序遍历. 答案：得到的前序序列是:EDBCA ......
冒泡排序学习笔记(2006-10-24 20:58:00)
摘要： 冒泡排序算法： void BubleSort(SqList &L) { bool exchange; for (int i=2; i<=n; i++) { exchange = false; for (int j=1; j<=n-i+1; j++) { if (L.r[j].key>L.r[j+1].key) { exchange = true; L.r[0] = L.r[j+1]; L.r[j+1] = L.r[j]; L.r[j] = L.r[0]; } } if (!exchange) { return; } } }......
快速排序学习笔记(2006-10-24 20:34:00)
摘要：
分解算法：每趟运算确保比枢轴pivot小的值都在其左边，大的都在右边。
int Partition(SqList &L, int low, int high) { L.r[0] = L.r[low];//子表中的第一个记录作为枢轴记录 int pivot = L.r[low].key;//枢轴记录的关键字值 while (low < high) { while (low < high && L.r[high].key>pivot) { high--; } L.r[low].key = L.r[high].key; while (low < high && L.r[low].key<pivot) { low++; } L.r[high].key = L.r[low].key; } L.r[low] = L.r[0]; return low; }
求解过程：递归调用分解函数的过程。
void QSort(SqList &L,int low,int high) { // 对顺序表L中的子序列L.r[low..high]作快速排序。算法10.7 int pivotloc; if(low<high) { // 长度大于1 pivotloc=Partition(L,low,high); // 将L.r[low..high]一分为二 QSort(L,low,pivotloc-1); // 对低子表递归排序，pivotloc是枢轴位置 QSort(L,pivotloc+1......
2_路插入排序学习笔记(2006-10-23 23:06:00)
摘要：
代码：
void P2_InsertSort(SqList &L) { // 2_路插入排序 int i,j,first,final; RedType *d; d=(RedType*)malloc(L.length*sizeof(RedType)); // 生成L.length个记录的临时空间 d[0]=L.r[1]; // 设L的第1个记录为d中排好序的记录(在位置[0]) first=final=0; // first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 for(i=2;i<=L.length;++i) { // 依次将L的第2个～最后1个记录插入d中 if(L.r[i].key<d[first].key) { // 待插记录小于d中最小值，插到d[first]之前(不需移动d数组的元素) first=(first-1+L.length)%L.length; // 设d为循环向量 d[first]=L.r[i]; } else if(L.r[i].key>d[final].key) { // 待插记录大于d中最大值，插到d[final]之后(不需移动d数组的元素) final=final+1; d[final]=L.r[i]; } else { // 待插记......
折半插入排序学习笔记(2006-10-23 22:51:00)
摘要：
程序：
void BInsertSort(SqList &L)
{ // 对顺序表L作折半插入排序。算法10.2
int i,j,m,low,high;
for(i=2;i<=L.length;++i)
{
L.r[0]=L.r[i]; // 将L.r[i]暂存到L.r[0]
low=1;
high=i-1;
while(low<=high)
{ // 在r[low..high]中折半查找有序插入的位置
m=(low+high)/2; // 折半
if LT(L.r[0].key,L.r[m].key)
high=m-1; // 插入点在低半区
else
low=m+1; // 插入点在高半区
}
for(j=i-1;j>=high+1;--j)
L.r[j+1]=L.r[j]; // 记录后移
L.r[high+1]=L.r[0]; // 插入
}
}
总结：此方法和直接插入排序所需的辅助空间相同，从时间上比较，仅减少了关键字比较的次数，记录的移动次数不变。所......
直接插入排序学习笔记(2006-10-23 22:48:00)
摘要：
直接插入排序程序：
void InsertSort(SqList &L)
{ // 对顺序表L作直接插入排序。算法10.1
int i,j;
for(i=2;i<=L.length;++i)//哨兵在0，所以从2开始排序
if (L.r[i].key < L.r[i-1].key) // "<",需将L.r[i]插入有序子表，确保待插入数据小于之前的最后一个，否则就不需要排序，进行下一个
{
L.r[0]=L.r[i]; // 待插入的数据复制为哨兵
for(j=i-1; L.r[0].key < L.r[j].key;--j)// 将每个数据和哨兵从右向左进行比较，直到哨兵大于该比较值
L.r[j+1]=L.r[j]; // 记录后移
L.r[j+1]=L.r[0]; // 插入到正确位置
}
}
总结：时间复杂度O(n2)，空间复杂度O(1)。
思想：L.r[0]用于存储待插入的数据，即哨兵。先将第一个数据看成有序的序列，故从第二个开始开始比较，共需要n-1趟。需将L.r[i]插入有序子表，确保待插入数据小于之前的最后一个，即有序子序列的最后一个。否则就不需要排序，因为改数已经大于最后一个，则为子序列的最大值，应该放于最后。进行此趟排序前，先将i拷入哨兵，之后将每个数据和哨兵从右向左进行比较，若小于该值则将其后移，否则将哨兵拷入该位置即可，本趟排序结束。......