博文
快速排序（分治法）(2006-11-22 17:22:00)
摘要：//快速排序法
#include<iostream>#include<cstdlib>using namespace std;
int part(int s[],int p,int r) //把大于s[p]的数放一边,小于它的数放一边{ int x = s[p]; int i = p+1; int j = r; while(true) { while(s[i] < x && i<=r) i++; while(s[j] > x && j>=1) j--; if(i >=j) break; int temp = s[i]; s[i] = s[j]; s[j] = temp; } s[p] = s[j]; s[j] = x; return j;}
void quicksort(int s[],int p,int r) { if(p < r) { int q = part(s,p,r); quicksort(s, p,q-1); quicksort(s,q+1,r); }}
int main(){ int s[] = {1,5,3,8,4,10,5}; int p = 0; int r= sizeof s/sizeof *s -1; cout<<"排序前: "<<endl; for(int i=0;i<=r;i++) cout<<s[i]<<" "; cout<<endl; quicksort(s,p,r); cout<<"排序后: "<<endl; for(i=0;i&l......
合并排序（分治法）(2006-11-22 16:59:00)
摘要：//1.当元素个数为1时，终止排序 //2.否则将待排序元素分成大小规模相同的两个子集合,分别对两个子集合排序(//3.最终将排序好的子集合合并为所要求的排序好的集合
#include<iostream>#include<cstdlib>using namespace std;
void hb(int s[],int tem[],int left,int middle,int right) //合并算法{ int i=left; int j=middle+1;
int k=left-1; //临时数组开头处 while(i<=middle && j<=right) { if(s[i] <= s[j]) tem[++k] = s[i++]; else tem[++k] = s[j++]; }
if(i > middle) { int q; for(q=j;q<=right;q++) tem[++k] = s[q]; } else { int q; for(q=i;q<=middle;q++) tem[++k] = s[q]; } for(int q=left;q<=right;q++) //把排序好的数重新放回S中 s[q] = tem[q]; }
void mergesort(int s[],int left,int right) ......
用分治法求 n个元素的最大元素(2006-11-20 21:51:00)
摘要：//已知S有N个元素，求S的最大元素
#include<iostream>using namespace std;
int max(int a,int b){ return (a>b?a:b);}
int searchmax(int s[],int left,int right) { if(left == right || (left+1) == right) //剩下两个元素或一个元素 { int max1=s[left]; int max2=s[right]; return max(max1,max2); } else { int middle = (left+right)/2; int max1 = searchmax(s,left,middle); int max2 = searchmax(s,middle+1,right); return(max(max1,max2)); }}
int main(){ int a[] = {100,30,7,50,9,90}; int n= sizeof a/sizeof(*a); //元素个数 for(int i = 0;i < n;i++) cout<<a[i]<<" "; cout<<endl;
int max = searchmax(a,0,n-1); &......
图的邻接矩阵创建算法(2006-05-08 23:08:00)
摘要：#include <iostream>#include<stdio.h>using namespace std;
#define FINITY 5000 //此处用5000代表最大#define m 20 //最大顶点树typedef char vertextype; //顶点值类型typedef int edgetype; //权值类型
typedef struct{ vertextype vexs[m]; //顶点值类型 edgetype edges[m][m]; //邻接矩阵 int n,e; //顶点总数 和 边树}mgraph; //邻接矩阵表示的图类型
// 图的邻接矩阵创建算法
void createmgraph1(mgraph *g){ int i,j,k,w; cout<<"\n输入图的顶点数:"; cin>>g->n; cout<<"\n输入图的边数:"; cin>>g->e; getchar(); //取消输入的换行符&......
线程的创建 ？？？(2006-04-20 20:18:00)
摘要：// 我创建了两个线程，本意是 要通过 临界区 实现 线程同步，
在这里 如果去掉 进入（或退出）临界区操作， 可以看到临界区的 作用
但如果都 去掉（即去掉临界区操作那部分） 或 都不 去掉 的话，结果一样，
知道的朋友帮忙改下怎么才能使 两个线程 随机 发生 ？？？？？？？？？？？？
#include<iostream.h>#include<windows.h>
CRITICAL_SECTION hCritical;
void display1(){
EnterCriticalSection(&hCritical); cout<<"Thread1 is runing!"<<endl; LeaveCriticalSection(&hCritical);}
void display2(){
EnterCriticalSection(&hCritical); cout<<"Thread2 is runing!"<<endl; LeaveCriticalSection(&hCritical);}
void main(){ InitializeCriticalSection(&hCritical);
static HANDLE hHandle1=NULL; static HANDLE hHandle2=NULL; DWORD dwThreadID1; while(1) {
hHandle1=CreateThread((LPSECURITY_ATTRIBUTES)NULL, 0,(LPTHREAD_START_ROUTINE)display1, (LPVOID)NULL,0,&dwThreadID1); ......
二叉树其他运算(2006-04-19 17:27:00)
摘要：#include <iostream>using namespace std;
typedef char datatype;typedef struct node{ datatype data; struct node *lchild,*rchild;}bintnode;
typedef bintnode *bintree;bintree root; //指向树根结点指针
// 二叉树的创建（按前序遍历顺序）
void createbintree(bintree *t){ char ch; if((ch=getchar())==' ') *t=NULL; else { *t=(bintnode*)malloc(sizeof(bintnode)); (*t)->data=ch; createbintree(&(*t)->lchild); createbintree(&(*t)->rchild); }}
//二叉树的查找算法
bintree locate(bintree t,datatype x){ bintree p; if(t==NULL) return NULL; else if(t->data==x) return t; else { p=locate(t->lchild,x); if(p) return p; else return locate(t......
二叉树各种非递归遍历(2006-04-13 19:34:00)
摘要：#include <iostream>using namespace std;
//二叉树链式存储的头文件typedef char datatype; //结点属性值类型typedef struct node //二叉树结点的类型{ datatype data; struct node* lchild,*rchild;}bintnode;typedef bintnode *bintree;bintree root; //指向二叉树根结点指针
//下面是些栈的操作 为非递归实现做准备
typedef struct stack //栈结构定义{ bintree data[100]; //data 元素类型为 指针 int tag[100]; //为栈中元素作的标记，用于后序遍历 int top; //栈顶指针}seqstack;
void push(seqstack* s,bintree t) //进栈{ s......
树的层号表示转化为树的孩子表示（数组方式）(2006-04-11 23:43:00)
摘要：#include<iostream>using namespace std;#define m 3 //树的度数#define maxsize 50 //数组元素个数最大值typedef char datatype; typedef struct node //树的扩充孩子表示（数组方式）法中结点类型 多了 双亲{ datatype data; int child[m]; int parent;}treenode;
typedef struct //层号表示法中结点的类型{ int lev; datatype data;}levelnode;
treenode tree[maxsize]; &n......
树的括号表示转化为树的孩子（数组方式）表示方式(2006-04-10 20:28:00)
摘要：//树的括号表示转换成树的孩子（数组方式）表示 算法#include <iostream>#include<stdio.h>using namespace std;#define m 3 //树的度数#define maxsize 20 //数的孩子表示法对应数组大小#define bmaxsize 25 //树的括号表示对应数组大小
typedef char datatype; //树中节点值类型typedef struct node //树的孩子表示法中节点类型{ datatype data; int child[m];}treenode;
treenode tree[maxsize]; //树的孩子表示法存储数组int root; //根结点的下标int length; //树中实际所含结点的个数 char p[bmaxsize]; /......
一般树的 创建以及各种遍历(2006-04-04 23:09:00)
摘要：// 先按前序遍历创建一棵 三度 树,然后按 前序,后序,层次 遍历此树
#include <iostream>using namespace std;#define m 3
typedef char datatype;typedef struct node{ datatype data; struct node* child[m];}node,*tree;tree root;
// 按前序遍历 创建一棵度数为3的树的递归算法
void createtree(tree *p) //*p 可以换成p 吗?{ int i; char ch; if((ch=getchar())==' ') *p=NULL; //建立一棵空树 else { *p=(tree)malloc(sizeof(node)); //用new 怎么建立 (*p)->data=ch; for(i=0;i<m;i++) createtree(&(*p)->child[i]); }}
//树的前序遍历递归算法
void preorder(tree p) //P为指向树根的指针{ int i; if(p!=NULL) //树不为空 { cout<<p->data; //输出根节点的值 for(i=0;i<m;i++) &nb......