博文
C++常用排序算法(2007-04-02 05:59:00)
摘要：//选择排序法SelectionSort(int arr[],int n)template <typename T>void SelectionSort(T arr[],int n){ int smallIndex; //表中最小元素的下标 int pass,j; //用来扫描子表的下标 T temp; //用来交换表元素的临时变量
//pass的范围是0~n-2 for (pass=0;pass<n-1;pass++) { //从下标pass开始扫描子表 smallIndex=pass; //j遍历整个子表arr[pass+1]到arr[n-1] for(j=pass+1;j<n;j++)
//如果找到更小的元素,则将该位置赋值给smallIndex if(arr[j]<arr[smallIndex]) smallIndex=j;
//如果smallIndex和pass不在相同的位置 //则将子表中的最小项与arr[pass]交换 if(smallIndex!=pass) { temp=arr[pass]; arr[pass]=arr[smallIndex]; arr[smallIndex]=temp; } }}
/************************************************************************双端选择排序算法:是上面选择排序算法的变种,可以定位每......
常用查找算法(2007-04-02 05:58:00)
摘要：//search.h包含了所有的常用查找算法
//使用顺序查找法的查找函数//seqSearch(const int arr[],int first,int last,int target)template <typename T>int seqSearch(const T arr[],int first,int last,const T& target){ int i=first;
//扫描下标范围first<=i<last; 测试是否有匹配 //或下标超出范围 while (!(i==last)&&!(arr[i]==target)) i++;
return i; //i是匹配值的下标,或者,如果没有匹配,则i=last}
//模板函数find_last_of()的实现template <typename T>int find_last_of(const T arr[],int first,int last,const T& target){ int i=last-1;
//描扫下标范围first<=i<last;测试是否有匹配 //或下标超出范围 while(i>=first&&target!=arr[i]) i--; if (i<first) return last; //没找到,则返回last return i;}
//二分查找算法函数binSearch()的实现template <typename T>int binSearch(const T arr[],int first,int last,const T& target){ int mid; //中间点的下标 T midVal......
数据结构学习（C++）续——排序【3】交换排序(2007-04-02 05:57:00)
摘要：交换排序
基本思想是：两两比较待排序记录的关键码，如果发生逆序，则交换之，直到所有对象都排好为止。
起泡排序
起泡排序是比较相邻的两个记录，逆序则交换。这样的做法导致小的关键码一层层的浮上来，因此得名。CSDN的论坛曾经讨论过“冒泡”和“起泡”是不是一个东西，看来这是翻译惹的祸，英文名都是Bubble Sort，具体写的时候可以正着排，也可以倒着排。（严版是从后往前排，殷版是从前往后排，好在两本书都翻译为“起泡排序”，不然就正像某些人得出的结论——一个是从后往前排，一个是从前往后排）
template <class T>
void BubbleSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0; bool exchange = true;
for (int i = 1; i < N && exchange; i++)
for (int j = N - 1; j >= i; j--)
{
exchange = false;
if (++KCN && a[j - 1] > a[j]) { sw......
数据结构学习（C++）续——排序【6】内部排序总结(2007-04-02 05:55:00)
摘要：基数排序本文后面将会提到，我觉得将其和前面的排序算法放在一起比较有些不伦不类。前面介绍了四类排序方法，每种都有基本型和改进型。对于内部排序，我们最关心的当然是速度，这也是为什么快排受欢迎的原因。考虑到快排的缺陷，有时候我们可能会用堆排或者希尔排序、归并排序。
上面可能是选择排序方法最直接的思路了（我们的选择范围也不算广，就那几个翻过来调过去的，好一点的，综合一下搞一个“杂牌”），出于“赌徒”的思维，我们大多数人可能用快排包打天下——出最坏情况？我没那么倒霉吧？大不了再加一个“三者取中”（或者随机选取）。但是，有时候速度并不是一切，我们还要考虑排序的稳定性。
前面没有涉及稳定性，主要是考虑每提到一种算法都要说一些本来并不是十分重要的“是否稳定”实在是干扰读者思路，并且前面的测试也无法反映稳定性。现在我们放在一起来说。排序的稳定性是指，对于相同的关键字，排序完成后他们的次序是否发生了改变，维持原状是稳定，否则就是不稳定的。实际上就是说，对一个多关键字序列，多次排序结果是否能够累积——多次排序能否最终达到预期的有序。打个比方，首先我们按学号对学生排序得到一个序列（在实际的应用中，初始序列总是这样的，我们根本不需要排序），然后按照成绩排序，对于成绩相同的学生，我们希望学号靠前的排在前边（预期的有序），如果排序是不稳定的，就会破坏前面按照学号排好的序列，从而导致得不到最终的预期序列。注意到是“预期有序”，在排成绩的例子中，如果我们不要求相同成绩的学号有序，排序是否稳定就无关紧要了。
什么排序算法是稳定的呢？首先看一下是什么导致了“不稳定”。注意到前边的四类方法都有稳定的算法（这是现有结论，不要问我是怎么来的，反正是就是是了，^_^），排序的思路应该不是不稳定的因素。排序肯定有记录的移动（或者指针的修改），移动方法有平移（直插排序）、交换（起泡排序）、重排（表插、归并）。仔细观察一下，就会发现，不相邻位置记录的交换是导致不稳定的因素。这样一来，凡是有这个隐患的排序算法都是不稳定的，对于原来稳定的算法，如果采用了这样的交换策略，也会导致不稳定，比如直接选择排序对于链表来说是稳定的，但对于数组来说就是不稳定的，然而，如果采用平移来代替原来的交换，那么对于数组也是稳定（估计没人愿意把本来的交换1次改成平移一堆）。
另外对于本来稳定的算法，当更改关键字判断条件后，比如大于变为大......
数据结构学习（C++）续——排序【4】选择排序(2007-04-02 05:55:00)
摘要：【4】选择排序
基本思想是：每次选出第i小的记录，放在第i个位置（i的起点是0，按此说法，第0小的记录实际上就是最小的，有点别扭，不管这么多了）。当i＝N－1时就排完了。
直接选择排序
直选排序简单的再现了选择排序的基本思想，第一次寻找最小元素的代价是O(n)，如果不做某种特殊处理，每次都使用最简单的寻找方法，自然的整个排序的时间复杂度就是O(n2)了。
template <class T>
void SelectSort(T a[], int N, int& KCN, int& RMN)
{
KCN = 0; RMN = 0;
for (int i = 0; i < N; i++)
{
for (int j = i + 1, k = i; j < N; j++) if (++KCN && a[j] < a[k]) k = j;//select min
if (k != i) { swap(a[k], a[i]); RMN += 3; }
}
}
测试结果：
Sort ascending N=10000 TimeSpared: 721ms
KCN=49995000 KCN/N=4999.5 KCN/N^2=0.49995 KCN/NlogN=376.25
RMN=0 &nb......
数据结构学习（C++）续——查找（搜索）【1】(2007-04-02 05:53:00)
摘要：相信每个人都曾感受过找东西的痛苦，大多数人也感受过计算机参与资料管理后所带来的便捷，而学过编程的也曾为了某个问题（比如实现“如果不存在则加入”这样的算法描述——排列组合算法的初级阶段）而实现过查找。在SGI-STL的stl_algo.h里面有这样一段代码：
template <class _InputIter, class _Tp>
inline _InputIter find(_InputIter __first, _InputIter __last,
const _Tp& __val,
input_iterator_tag)
{
while (__first != __last && !(*__first == __val))
++__first;
return __first;
}
这个应该能代表我们曾经写过的所有顺序查找代码，关于为什么写成了这个样子，《C++沉思录》第17章有详细的说明。或许VC6的STL代码更容易理解些：
template<class _II, class _Ty> inline
_II find(_II _F, _II _L, const _Ty& _V)
{for (; _F != _L; ++_F)
......
AVL树的实现（源码）(2007-04-02 05:52:00)
摘要：AVLTree
http://www.staroceans.com/AVLTree.htm
A. First Edition
This is first edition of my AVL Tree and I never expect it takes so long as almost one week to finish! Of course
it is partly because of Christmas when I was continually interrupt by the earthly issues such as visiting a
friend and wasting some meaningful time on meaningless matters.
B.The problem
To write AVL tree on template basis and try to keep as much as possible of original BST frame work
because the code by Mr. Shaffer is very concise and compact! And efficiency is also a very important
issue here. As AVLTree has to store extra information than a BST, it is expected that we need to
reduce as many "balancing operations" as possible.
C.The idea of program
By adding a little piece of code in "insert" method of BST, I actually try to do the keeping-balance
job along the "insert" operation from bottom-up which always keep each node up-to-date balanced. It
is believed by me the best solution to impleme......
迷宫寻路程序2(2007-04-02 05:49:00)
摘要：三，详细设计：
1.主程序文件1.cpp：
#include<stdlib.h>
#include <string.h>
#include <time.h>
#include<iostream.h>
#include"0.h"
#include"mg.h"
void main()
{
cout<<" ****************************************************************"<<endl;
cout<<" 2004数据结构课程设计之迷宫寻路"<<endl;
cout<<" 本程序根据你输入的行，列，复杂水平，生成一个矩阵图形迷宫。"<<endl;
cout<<" 0表示不可行走的障碍，1表示可以行走的路径。"<<endl;
cout<<" 程序自动寻路，用文字显示所有搜索的路径。"<<endl;
cout<<" 再用9标识最后走通的路径。"<<endl;
cout<<" ****************************************************************"<<endl;......
数据结构学习（C++）续——查找（搜索）【2】(2007-04-02 05:45:00)
摘要：树型查找
折半查找所需要的，有序的、可以随机存取的、顺序结构的限制，导致了排序的额外负担（如果是逐个添加，主要的负担是移动数据，此时是折半插入排序）。通过观察折半查找的过程，发现实际上mid是从判定树的根走到了叶子节点，而这棵判定树和有相同节点的完全二叉树的高度是相同的。链式结构的好处就是不用大量移动数据，自然的用链树来做查找结构应该是个好选择。
在前面我们曾经写过一个BSTree类，这个类大致上能满足我们的要求。而为了在不同的输入情况下，使得树的高度尽可能的小，平衡树的概念被提出来了，例如前面的AVLTree类。所谓的平衡，现在更多意义上是指和完全m叉树高度的比值是小于某个常数的树，也就是高度≤klogmn的树，k为一个定常数。注意到AVL树的定义实际上太苛刻，就很容易理解为什么要放宽要求。而实际能应用的平衡树，都是为了满足这个要求而自己定一套规则，比如B－树，这个后面会讲到。
索引
有些字典会提供一个目录，大部分情况是这样的A……xx；B……xx；……。这样就能迅速翻到开头字母对应的页数（实际上也知道了开头字母结束的地方），并且每个页的左右上角的单词也说明了本页的单词范围（可以判断所查单词在不在此页）。这些就是索引。
使用索引能够快速的定位查找范围，从我们查字典的经验看来，这也应该是能提高查找效率的方法。注意到目录的作用，它使得我们所需的字典空间分布，在一页（或者几页）的空间上迅速的被我们得到——类比来看，如果数据太多以至内存装不下，我们也可以弄个“目录”，使得可以将数据分块的读入内存查找。
B－树
当数据膨胀到一个可怕的程度时，连索引都不能被全部装入内存——见过印刷版的EI检索都有这个感觉，光一个检索目录都比我们用的字典厚。我们的办法就是索引再索引，显而易见的，每个索引块都应该尽可能的大，以帮助我们获得尽可能多的信息苊庠俅蔚牟樗饕ù耸币话愣蓟嵘婕巴獯娴拇嫒。?/SPAN>AVL树此时便力不从心了，我们需要一种新的结构。
相信每个学到这里的人都对B－树的定义深恶痛绝，这个的责任应该由写书的人来负，虽然定义、概念是人认知的重要工具和途径，但在这里是适得其反的。原因就是B－树根本不存在概念意义上的“概念”，它只是一个描述型的“概念”，是B－树能够运行从而表现出来的一种现象。不管怎么说，先看一下现有的书上的定义（省略了“或者为空树”这句话......
数据结构学习（C++）续——续篇后记(2007-04-02 05:43:00)
摘要：我觉得续篇的写作我很不负责任，越到后面越是如此，可能是我没有打算写的缘故，或者说是“心浮气躁”——写了几个月有点熬不住了，^_^。但也可能我只能写到这样，毕竟这部分离我们太远，至少和前边的“数据结构”相比是太远。
有人说，查找和排序的算法已经非常成熟了，大师们穷尽脑汁也不可能带来“质的飞跃”了，而像我们这些等着“吸收前人劳动果实”的人，能全盘吸收就甚为不易，更不要说“完成前人所未完成”了。因此，对于教科书上面的讲解，除非作者治学态度有问题（信口开河），否则没有什么好讲的。正像我前面所说的，我只是给大家读书的时候起个向导的作用，并不是想写本书，因此很多的地方都省略了。我所写的，如果使得书上枯燥的数学分析具体化，各种方法的提出不再显得突兀，我就心满意足了。
对于排序，我还显得有点耐性，除了锦标排序和基数排序、外部排序，其他的都给出了例程；对于查找，除了顺序查找和折半、插值查找，二叉搜索树，AVL树，其他的都是说说而已。造成这种结果，固然是我耐性有限，但这也是现状所致——什么东西要是不带个数据库什么的就显得不够专业，有了数据库，B－树什么的还要它作甚？说这话的时候，我常常显得很无奈，但确实是这种现状的受益者。
最后，说说怎样看待数据结构——谈这个话题就是找骂，但到了最后了，我也不怕了。数据结构现在的地位很尴尬，几乎每个有志于写程序的人都把数据结构摆在必须掌握的知识的第一位，但实际上，当必修课学的、计算机专业的学生学完之后，一半茫茫然；而非计算机专业的，甚至没学过数据结构的，程序员也干得好好的。
计算机的应用能到今天的地步，数据结构功不可没，没有串、表、树、图，计算机只能在数值计算里面打转转——现在掉过来了，真正的数值计算反倒没有多少人会写了，^_^。但，这和汇编（更有甚者是01代码，我光知道90是NOP，^_^）的处境一样，汇编也曾在计算机发展上的作用无可估量，而现在会的人真是寥寥无几，就连C的境域也是如此，虽然每所大学不管是不是计算机专业都开设C语言课程。
可以说，我们写的每个还算有点功能的程序，都离不开数据结构。比如我们当初学C的时候，都做过这样的练习：将一组输入的数据逆序输出。我们每个人几乎都能想到先拿数组存起来，然后倒着再输出。我们在这里其实就利用了线性表，只是我们没意识到。再比如我们需要一段排序的程序，而在我们没学过排序方法的时候，大多数人都会写出直接......