常用算法模板库(C++)


1 常用算法模板库(C++) 目录 目录 ................................................................................................................................................... 1 1 排序算法 ........................................................................................................................................ 3 1.1 冒泡排序 ................................................................................................................................. 3 1.2 选择排序 ................................................................................................................................. 4 1.3 插入排序 ................................................................................................................................. 5 1.4 快速排序 ................................................................................................................................. 6 1.5 哈希排序 ................................................................................................................................. 8 2 数学问题 ........................................................................................................................................ 8 2.1 求最大公约数最小公倍数 ....................................................................................................... 8 2.2 求素数 ..................................................................................................................................... 9 2.2.1 穷举法 .............................................................................................................................. 9 2.2.2 筛法 ................................................................................................................................ 10 2.3 排列组合 ............................................................................................................................... 10 2.3.1 排列数 ............................................................................................................................ 10 2.3.2 组合数 ............................................................................................................................ 11 2.3.3 全排列算法 .................................................................................................................... 12 2.3.4 从n个数中选 m个的组合 ................................................................................................ 13 2.4 进制转换 ............................................................................................................................... 14 2.4.1 十进制转N进制 .............................................................................................................. 14 2.4.2 N进制转十进制 ............................................................................................................... 14 3 查找 ............................................................................................................................................. 15 3.1 二分查找 ............................................................................................................................... 15 4 栈 ................................................................................................................................................. 16 4.1 栈的定义 ............................................................................................................................... 16 4.2 表达式求值 ........................................................................................................................... 19 5 队列 ............................................................................................................................................. 21 5.1 队列的定义 ........................................................................................................................... 21 6 串 ................................................................................................................................................. 24 6.1 基本操作 ............................................................................................................................... 24 6.1.1 赋值 ................................................................................................................................ 24 6.1.2 比较大小(字典顺序) ................................................................................................. 24 6.2 模式匹配 ............................................................................................................................... 25 2 6.2.1 一般匹配算法 ................................................................................................................ 25 6.2.2 KMP算法 ........................................................................................................................ 26 7 树 ................................................................................................................................................. 27 7.1 二叉树的定义 ........................................................................................................................ 27 7.2 根据先序序列和中序序列建立二叉树 .................................................................................. 31 7.3 二叉排序树 ........................................................................................................................... 32 7.4 建立哈夫曼树 ........................................................................................................................ 32 7.5 树的定义 ............................................................................................................................... 34 8 图 ................................................................................................................................................. 38 8.1 图的定义 ............................................................................................................................... 38 8.2 图的最短路径 ........................................................................................................................ 43 8.2.1 Dijkstra算法 .................................................................................................................... 43 8.2.2 Floyd算法 ........................................................................................................................ 44 8.3 最小生成树 ........................................................................................................................... 44 8.3.1 prim算法 ......................................................................................................................... 44 8.3.2 Kruskal算法 .................................................................................................................... 45 8.4 拓扑排序 ............................................................................................................................... 46 8.5 关键路径 ............................................................................................................................... 47 9 高精度计算 .................................................................................................................................. 48 9.1 加法 ....................................................................................................................................... 48 9.2 减法 ....................................................................................................................................... 49 9.3 乘法 ....................................................................................................................................... 50 3 1 排序算法 1.1 冒泡排序 /* 函数功能:对数组中的某一部分进行冒泡排序。 函数原形:void BubSort(DataType a[], int l, int r, bool Up=true); 参数: DataType a[]:欲排序的数组; int l:有序序列在数组中的起始位置; int r:有序序列在数组中的结束位置; bool Up:true 按升序排列,false 按降序排列。 返回值:无。 备注:无。 */ template void BubSort(DataType a[], int l, int r, bool Up=true) { int i,j; DataType k; if (Up) { for (i=l;i<=r-1;i++) for (j=r;j>=i+1;j--) if (a[j-1]>a[j]) { k=a[j-1]; a[j-1]=a[j]; a[j]=k; } } else for (i=l;i<=r-1;i++) for (j=r;j>=i+1;j--) if (a[j-1] void SelectSort(DataType a[], int l, int r, bool Up=true) { int i,j; DataType k; if (Up) { for (i=l;i<=r-1;i++) for (j=i+1;j<=r;j++) if (a[i]>a[j]) { k=a[i]; a[i]=a[j]; a[j]=k; } } else for (i=l;i<=r-1;i++) for (j=i+1;j<=r;j++) if (a[i] void SelectSort(DataType a[], int l, int r, bool Up=true) { int i,j,k; DataType x; if (Up) { for (i=l;i<=r-1;i++) { k=i; for (j=i+1;j<=r;j++) if (a[j]a[k]) k=j; x=a[i]; a[i]=a[k]; a[k]=x; } } 1.3 插入排序 /* 函数功能:向有序数组中插如元素,并使插入新元素后仍然有序。 函数原形:void InsertSort(DataType s[], int &Count, DataType x, bool Up=true); 参数: DataType s[]:欲插入元素的有序序列; int &Count:有序序列中现有元素个数; DataType x:欲插入的元素; bool Up:true 按升序排列,false 按降序排列。 返回值:无。 备注:无。 */ 6 template void InsertSort(DataType s[], int &Count, DataType x, bool Up=true) { int i,k=-1; if (Up) { for (i=0;i<=Count-1;i++) if (xs[i]) { k=i; break; } if (k==-1) s[++Count-1]=x; else { for (i=Count-1;i>=k;i--) s[i+1]=s[i]; s[k]=x; Count++; } } 1.4 快速排序 /* 函数功能:对数组中的某一部分进行快速排序。 函数原形:void QuickSort(DataType a[], int l, int r, bool Up=true); 参数: DataType a[]:欲排序的数组; int l:有序序列在数组中的起始位置; int r:有序序列在数组中的结束位置; bool Up:true 按升序排列,false 按降序排列。 返回值:无。 备注:无。 */ template 7 void QuickSort(DataType a[], int l, int r, bool Up=true) { int i,j; DataType Mid,k; i=l; j=r; Mid=a[(l+r)/2]; if (Up) { do { while (a[i]Mid) ++i; while (Mid>a[j]) --j; if (i<=j) { k=a[i]; a[i]=a[j]; a[j]=k; ++i; --j; } } while (i<=j); if (ir) break; } } else for (i=32767-1;i>=0;i--) { for (j=1;j<=Hash[i];j++) a[k++]=i; if (k>r) break; } } 2 数学问题 2.1 求最大公约数最小公倍数 /* 函数功能:求两数的最大公约数。 9 函数原形:int GCD(int m, int n); 参数: int m, int n:求这两个数的最大公约数。 返回值:int 型,m、n 的最大公约数。 备注:最小公倍数=m*n/GCD(m,n)。 */ int GCD(int m, int n) { int Temp,x,y; x=m; y=n; Temp=x%y; while (Temp!=0) { x=y; y=Temp; Temp=x%y; } return y; } 2.2 求素数 2.2.1 穷举法 /* 函数功能:判断一个数是否是素数。 函数原形:bool Prime(int x); 参数: int x:欲判断的数。 返回值:bool 型,返回 true 表示 x 是素数,返回 false 表示 x 不是素数。 备注:需包含头文件。 */ bool Prime(int x) { int i; x=abs(x); if (x<=1) return false; for (i=2;i<=int(sqrt(float(x)));i++) if (x%i==0) return false; return true; 10 } 2.2.2 筛法 /* 函数功能:判断小于等于 n 的数是否是素数。 函数原形:void Prime(bool Hash[], int n); 参数: bool Hash[]:最终结果,Hash[i]=true 表示 i 是素数,否则表示 i 不是素数; int n:判断范围。 返回值:无。 备注:无。 */ void Prime(bool Hash[], int n) { int i,k; Hash[0]=false; Hash[1]=false; for (i=2;i<=n;i++) Hash[i]=true; i=2; while (i<=n/2) { k=i; while (k+i<=n) { k=k+i; Hash[k]=false; } i++; while (Hash[i]==false && iNum[i-1]) x=i; 13 for (i=x;i<=n;i++) if (Num[i]>Num[x-1]) y=i; if (x>1) { Swap(Num[x-1],Num[y]); //交换 Num[x-1]和 Num[y] Inverse(Num,x,n); //对 num[x]~num[n]作逆序处理 for (i=1;i<=n;i++) cout<0) j--; a[j]++; for (i=j+1;i<=n;i++) a[i]=a[i-1]+1; } delete[] a; } 14 2.4 进制转换 2.4.1 十进制转 N 进制 /* 函数功能:将一个十进制数转换成一个 N 进制数。 函数原形:string DecToN(DataType x, int n); 参数: DataType x:欲转换的数; int n:返回结果的进制。 返回值:string 类对象,转换结果。 备注:需包含。 */ template string DecToN(DataType x, int n) { string Ans; int Count,i,j=0,a[64]; Count=0; if (x==0) { Ans[0]='0'; Ans[1]='\0'; } else { while (x>0) { a[Count++]=x%n; x=x/n; } for (i=Count-1;i>=0;i--) if (a[i]<10) Ans.append(1,a[i]+'0'); else Ans.append(1,a[i]+'A'-10); } return Ans; } 2.4.2 N 进制转十进制 /* 15 函数功能:将一个 N 进制数转换成一个十进制数。 函数原形:long NToDec(string x, int n); 参数: string x:欲转换的数; int n:被转换数的进制。 返回值:long 型,转换结果。 备注:需包含。 */ long NToDec(string x, int n) { int a[32],y,Count,i,j; long Ans; Ans=0; for (i=0;i<=(int)x.length()-1;i++) if ('0'<=x[i] && x[i]<='9') a[i]=x[i]-'0'; else a[i]=toupper(x[i])-'A'+10; Count=0; for (i=(int)x.length()-1;i>=0;i--) { y=1; for (j=1;j<=Count;j++) y=y*n; Count++; Ans=Ans+y*a[i]; } return Ans; } 3 查找 3.1 二分查找 /* 函数功能:查找指定元素在数组中的位置。 函数原形:int BinarySearch(DataType a[], DataType x, int l, int r); 参数: DataType a[]:目标数组; DataType x:待查找的元素; int l:数组下标上限; int r:数组下标下限。 返回值:int 型,元素 x 在数组 a 中的下标。 备注:无。 16 */ template int BinarySearch(DataType a[], DataType x, int l, int r) { int Mid; while (l<=r) { Mid=(l+r)/2; if (x==a[Mid]) return Mid; else { if (xa[Mid]) l=Mid+1; } } return -1; } 4 栈 4.1 栈的定义 template class StackClass { private: struct BodyNodeStruct { DataType Data; BodyNodeStruct *Pre,*Next; } Bottom,*Top; public: StackClass(); //构造函数,创建一个空栈 bool Empty(); //判断栈是否为空,若为空则返回 true,否则返回 false int Push(DataType Data); //将 Data 压栈,如果压栈成功则返回 0,否则返回 1 int Pop(DataType &Data); // 弹出栈顶元素,保存在 Data 中,若栈不为空则返回 0, 否则返回 1 int GetTop(DataType &Data); // 读取栈顶元素,保存在 Data 中,若栈不为空则返回 0,否则返回 1 int Size(); //返回栈中元素个数 17 void Clear(); //清空栈 ~StackClass(); //析构函数 } ; template StackClass::StackClass() { Top=&Bottom; Top->Pre=NULL; Top->Next=NULL; } template bool StackClass::Empty() { if (Top==&Bottom) return true; else return false; } template int StackClass::Push(DataType Data) { BodyNodeStruct *Temp=new BodyNodeStruct; if (Temp!=NULL) { Temp->Pre=Top; Temp->Next=NULL; Top->Next=Temp; Top->Data=Data; Top=Temp; return 0; } else return 1; } template int StackClass::Pop(DataType &Data) { if (!Empty()) { Top=Top->Pre; Data=Top->Data; delete Top->Next; 18 Top->Next=NULL; return 0; } else return 1; } template int StackClass::GetTop(DataType &Data) { if (!Empty()) { Data=Top->Pre->Data; return 0; } else return 1; } template int StackClass::Size() { BodyNodeStruct *Temp=&Bottom; int Count=0; while (Temp!=Top) { Count++; Temp=Temp->Next; } return Count; } template void StackClass::Clear() { DataType Temp; while (!Empty()) Pop(Temp); } template StackClass::~StackClass() { Clear(); } 19 4.2 表达式求值 /* 函数功能:计算四则运算表达式的值。 函数原形:long Evaluate(string Exp); 参数: string Exp:欲求值的四则运算表达式。 返回值:long 型,表达式的值。 备注:需包含。 */ long Evaluate(string Exp) { StackClass Optr; StackClass Opnd; long a,b,Ans; int TempOptr,x,i,Length,Operator[7][7]={{2,2,0,0,0,2,2},{2,2,0,0,0,2,2},{2,2,2,2,0, 2,2},{2,2,2,2,0,2,2},{0,0,0,0,0,1,-1},{2,2,2,2,-1,2,2},{0,0,0,0,0,-1,1}}; char TempOpnd[6]; Optr.Push(6); Opnd.Push(0); Length=0; i=0; Optr.GetTop(x); while (Exp[i]!='=' || x!=6) { if (48<=Exp[i] && Exp[i]<=57) { TempOpnd[Length++]=Exp[i]; i++; } else if (Exp[i]=='+' || Exp[i]=='-' || Exp[i]=='*' || Exp[i]=='/' || Exp[i]=='(' || Exp[i]==')' || Exp[i]=='=') { if (Length>0) { TempOpnd[Length]='\0'; Length=0; Opnd.Push(atoi(TempOpnd)); } switch (Exp[i]) 20 { case '+': TempOptr=0; break; case '-': TempOptr=1; break; case '*': TempOptr=2; break; case '/': TempOptr=3; break; case '(': TempOptr=4; break; case ')': TempOptr=5; break; case '=': TempOptr=6; break; } Optr.GetTop(x); switch (Operator[x][TempOptr]) { case 0: Optr.Push(TempOptr); i++; break; case 1: Optr.Pop(x); i++; break; case 2: Optr.Pop(TempOptr); Opnd.Pop(b); Opnd.Pop(a); switch (TempOptr) { case 0: Opnd.Push(a+b); break; case 1: 21 Opnd.Push(a-b); break; case 2: Opnd.Push(a*b); break; case 3: Opnd.Push(a/b); break; } break; } } Optr.GetTop(x); } Opnd.Pop(Ans); return Ans; } 5 队列 5.1 队列的定义 template class QueueClass { private: struct BodyNodeStruct { DataType Data; BodyNodeStruct *Pre,*Next; } *Front,*Rear; public: QueueClass(); //构造函数,构造一个空队列 bool Empty(); //判断队列是否为空,若为空则返回 true,否则返回 false int Push(DataType Data); //将 Data 压入队尾,如果压入成功则返回 0,否则返回 1 int Pop(DataType &Data); //弹出队头元素,保存在 Data 中,若队列不为空则返回 0,否则返回 1 int GetFront(DataType &Data); / /读取队头元素,保存在 Data 中,若队列不为空则 返回 0,否则返回 1 int Size(); //返回队列中元素个数 void Clear(); //清空队列 22 ~QueueClass(); //析构函数 } ; template QueueClass::QueueClass() { Front=new BodyNodeStruct; Front->Pre=NULL; Front->Next=NULL; Rear=Front; } template bool QueueClass::Empty() { if (Front==Rear) return true; else return false; } template int QueueClass::Push(DataType Data) { BodyNodeStruct *Temp=new BodyNodeStruct; if (Temp!=NULL) { Temp->Pre=Rear; Temp->Next=NULL; Rear->Next=Temp; Rear->Data=Data; Rear=Temp; return 0; } else return 1; } template int QueueClass::Pop(DataType &Data) { if (!Empty()) { Data=Front->Data; Front=Front->Next; delete Front->Pre; 23 Front->Pre=NULL; return 0; } else return 1; } template int QueueClass::GetFront(DataType &Data) { if (!Empty()) { Data=Front->Data; return 0; } else return 1; } template int QueueClass::Size() { BodyNodeStruct *Temp=Front; int Count=0; while (Temp!=Rear) { Count++; Temp=Temp->Next; } return Count; } template void QueueClass::Clear() { DataType Temp; while (!Empty()) Pop(Temp); } template QueueClass::~QueueClass() { Clear(); delete Front; 24 } 6 串 6.1 基本操作 6.1.1 赋值 /* 函数功能:复制一个串到另一个串中。 函数原形:void Copy(char Str[], char Source[]); 参数: char Str[]:目标串; char Source[]:源串。 返回值:无。 备注:需包含。 */ void Copy(char Str[], char Source[]) { unsigned i; for (i=0;i<=strlen(Source);i++) Str[i]=Source[i]; } 6.1.2 比较大小(字典顺序) /* 函数功能:比较两个串的大小(按字典顺序)。 函数原形:int Compare(char Str1[], char Str2[]); 参数: char Str1[],Str2[]:欲比较的两个串。 返回值:int 型,如果 Str1>Str2 返回 1,如果 Str1=Str2 返回 0,如果 Str1。 */ int Compare(char Str1[], char Str2[]) { unsigned Len,Len1,Len2,i=0; Len1=(unsigned)strlen(Str1); Len2=(unsigned)strlen(Str2); 25 if (Len1toupper(Str2[i])) return 1; else return -1; } else if (Len1==Len2) return 0; else if (Len1>Len2) return 1; else return -1; } 6.2 模式匹配 6.2.1 一般匹配算法 /* 函数功能:返回模式串在目标串中的位置。 函数原形:int Index(char s[], char t[], int Pos); 参数: char s[]:目标串; char t[]:模式串; int Pos:起始检测位置。 返回值:int 型,如果模式串能够匹配,则返回其在目标串中的位置,否则返回-1。 备注:需包含头文件。 */ int Index(char s[], char t[], int Pos) { int i,j; i=Pos; j=0; while (i<=(int)strlen(s)-1 && j<=(int)strlen(t)-1) if (s[i]==t[j]) { i++; j++; } else { 26 i=i-j+1; j=0; } if (j>(int)strlen(t)-1) return i-strlen(t); else return -1; } 6.2.2 KMP 算法 /* 函数功能:返回模式串在目标串中的位置。 函数原形:int IndexKMP(char s[], char t[], int Pos); 参数: char s[]:目标串; char t[]:模式串; int Pos:起始检测位置。 返回值:int 型,如果模式串能够匹配,则返回其在目标串中的位置,否则返回-1。 备注:需包含头文件。 */ void GetNext(char t[], int Next[]) { int i,j; i=0; Next[0]=-1; j=-1; while (i<(int)strlen(t)-1) if (j==-1 || t[i]==t[j]) { i++; j++; if (t[i]!=t[j]) Next[i]=j; else Next[i]=Next[j]; } else j=Next[j]; } int IndexKMP(char s[], char t[], int Pos) { int i,j,*Next=new int[strlen(t)]; GetNext(t,Next); i=Pos; j=0; 27 while (i<=(int)strlen(s)-1 && j<=(int)strlen(t)-1) if (j==-1 || s[i]==t[j]) { i++; j++; } else j=Next[j]; delete[] Next; if (j>(int)strlen(t)-1) return i-strlen(t); else return -1; } 7 树 7.1 二叉树的定义 template class BinaryTreeClass { private: DataType Data; BinaryTreeClass *Prt,*Lch,*Rch; public: BinaryTreeClass(); //构造函数,创建一个二叉树根结点 BinaryTreeClass(DataType x); //构造函数,创建一个值为 x 的二叉树根结点 BinaryTreeClass(BinaryTreeClass *Parent); //构造函数,创建一个父 亲结点为 Parent 的二叉树叶子结点 BinaryTreeClass(DataType x, BinaryTreeClass *Parent); //构造函数, 创建一个父亲为 Parent 值为 x 的二叉树叶子结点 void Assign(DataType x); //将结点赋值为 x DataType Value(); //返回结点的值 BinaryTreeClass *Root(); //返回本结点所在二叉树的根结点 BinaryTreeClass *Parent(); //返回本结点的父亲结点 BinaryTreeClass *LeftChild(); //返回本结点的左儿子结点 BinaryTreeClass *RightChild(); //返回本结点的右儿子结点 void PreOrder(int (*Visit)(BinaryTreeClass *)); //对以本结点为根 的二叉树,函数 int Visit(BinaryTreeClass *)为访问方式进行先序遍历 void InOrder(int (*Visit)(BinaryTreeClass *)); //对以本结点为根的 二叉树,函数 int Visit(BinaryTreeClass *)为访问方式进行中序遍历 void PostOrder(int (*Visit)(BinaryTreeClass *)); // 对以本结点为根 的二叉树,函数 int Visit(BinaryTreeClass *)为访问方式进行后序遍历 28 int InsertChild(int Child, BinaryTreeClass *SubTree); //将二叉树 SubTree 作为本结点的某一子树插入本结点所在二叉树 int DeleteChild(int Child); //删除本结点的某一子树 ~BinaryTreeClass(); //析构函数 } ; template BinaryTreeClass::BinaryTreeClass():Prt(NULL),Lch(NULL),Rch(NULL){} template BinaryTreeClass::BinaryTreeClass(DataType x):Data(x),Prt(NULL),Lch(NULL),Rch(NULL){} template BinaryTreeClass::BinaryTreeClass(BinaryTreeClass *Parent):Prt(Parent),Lch(NULL),Rch(NULL){} template BinaryTreeClass::BinaryTreeClass(DataType x, BinaryTreeClass *Parent):Data(x),Prt(Parent),Lch(NULL),Rch(NULL){} template void BinaryTreeClass::Assign(DataType x) { Data=x; } template DataType BinaryTreeClass::Value() { return Data; } template BinaryTreeClass *BinaryTreeClass::Root() { BinaryTreeClass *Temp=this; while (Temp->Prt!=NULL) Temp=Temp->Prt; return Temp; } template BinaryTreeClass *BinaryTreeClass::Parent() 29 { return Prt; } template BinaryTreeClass *BinaryTreeClass::LeftChild() { return Lch; } template BinaryTreeClass *BinaryTreeClass::RightChild() { return Rch; } template void BinaryTreeClass::PreOrder(int (*Visit)(BinaryTreeClass *)) { Visit(this); if (Lch!=NULL) Lch->PreOrder(Visit); if (Rch!=NULL) Rch->PreOrder(Visit); } template void BinaryTreeClass::InOrder(int (*Visit)(BinaryTreeClass *)) { if (Lch!=NULL) Lch->InOrder(Visit); Visit(this); if (Rch!=NULL) Rch->InOrder(Visit); } template void BinaryTreeClass::PostOrder(int (*Visit)(BinaryTreeClass *)) { if (Lch!=NULL) Lch->PostOrder(Visit); if (Rch!=NULL) Rch->PostOrder(Visit); Visit(this); } template 30 int BinaryTreeClass::InsertChild(int Child, BinaryTreeClass *SubTree) { if (SubTree==NULL) return 1; else if (Child==0) { if (Lch==NULL) { Lch=SubTree; SubTree->Prt=this; return 0; } else return 2; } else if (Rch==NULL) { Rch=SubTree; SubTree->Prt=this; return 0; } else return 2; } template int BinaryTreeClass::DeleteChild(int Child) { if (Child==0) { if (Lch!=NULL) { delete Lch; Lch=NULL; return 0; } else return 1; } else if (Rch!=NULL) { delete Rch; Rch=NULL; return 0; 31 } else return 1; } template BinaryTreeClass::~BinaryTreeClass() { DeleteChild(0); DeleteChild(1); } 7.2 根据先序序列和中序序列建立二叉树 /* 函数功能:根据先序序列和中序序列建立二叉树。 函数原形:BinaryTreeClass *Create(string PreOrder, string InOrder); 参数: string PreOrder:先序序列; string InOrder:中序序列。 返回值:BinaryTreeClass *型,二叉树根结点地址。 备注:需包含头文件。 */ BinaryTreeClass *Create(string PreOrder, string InOrder) { BinaryTreeClass *Root=new BinaryTreeClass(PreOrder[0]); string LTI,RTI,LTP,RTP; int x; if (Root!=NULL) { x=(int)InOrder.find(Root->Value()); LTI.assign(InOrder,0,x); RTI.assign(InOrder,x+1,InOrder.length()-x-1); LTP.assign(PreOrder,1,x); RTP.assign(PreOrder,x+1,RTI.length()); if (LTI.length()>0) Root->InsertChild(0,Create(LTP,LTI)); if (RTI.length()>0) Root->InsertChild(1,Create(RTP,RTI)); } return Root; } 32 7.3 二叉排序树 /* 函数功能:向二叉排序树中插入元素。 函数原形:BinaryTreeClass *Insert(BinaryTreeClass *Root, DataType x); 参数: BinaryTreeClass *Root:目标二叉排序树; DataType x:欲插入二叉排序树*Root 的元素。 返回值:BinaryTreeClass *型,插入新元素后的二叉排序树根结点地址。 备注:无。 */ template BinaryTreeClass *Insert(BinaryTreeClass *Root, DataType x) { BinaryTreeClass *Point=Root,*Pre=NULL; while (Point!=NULL) { Pre=Point; if (x<=Point->Value()) Point=Point->LeftChild(); else Point=Point->RightChild(); } Point=new BinaryTreeClass(x,Pre); if (Point->Parent()!=NULL) if (x<=Point->Parent()->Value()) Point->Parent()->InsertChild(0,Point); else Point->Parent()->InsertChild(1,Point); return Point->Root(); } 7.4 建立哈夫曼树 /* 函数功能:根据指定权值建立一棵哈夫曼树。 函数原形:BinaryTreeClass *Huffman(DataType Weight[], int n); 参数: DataType Weight[]:权值; int n:权值个数。 返回值:BinaryTreeClass *型,生成的哈夫曼树根结点地址。 备注:无。 */ template void SortData(BinaryTreeClass *a[], int l, int r) 33 { int i,j; DataType Mid; BinaryTreeClass *k; i=l; j=r; Mid=a[(l+r)/2]->Value(); do { while (a[i]->Value()Value()) --j; if (i<=j) { k=a[i]; a[i]=a[j]; a[j]=k; ++i; --j; } } while (i<=j); if (i BinaryTreeClass *Huffman(DataType Weight[], int n) { BinaryTreeClass **Tree=new BinaryTreeClass *[n],*Root; int i; for (i=0;i<=n-1;i++) Tree[i]=new BinaryTreeClass(Weight[i]); while (n>1) { SortData(Tree,0,n-1); //按 Data 域升序排序 Root=new BinaryTreeClass(Tree[0]->Value()+Tree[1]->Value()); Root->InsertChild(0,Tree[0]); Root->InsertChild(1,Tree[1]); Tree[0]=Root; Tree[1]=Tree[n-1]; n--; } return Root; } 34 7.5 树的定义 /*注:在调用成员函数 void BFS(int (*Visit)(TreeClass *))前需要定义 QueueClass类*/ template class TreeClass { private: DataType Data; int Dgr; TreeClass *Prt,**Chd; public: TreeClass(int Degree); //构造函数,创建树的一个度为 Degree 的根结点 TreeClass(int Degree, DataType x); //构造函数,创建树的一个度为 Degree 值为 x 的根结点 TreeClass(int Degree, TreeClass *Parent); //构造函数,创建一个度 为 Degree 父亲结点为 Parent 的叶子结点 TreeClass(int Degree, DataType x, TreeClass *Parent); // 构造函数, 创建一个度为 Degree 值为 x 父亲为 Parent 值为 x 的叶子结点 void Assign(DataType x); //将结点赋值为 x DataType Value(); //返回结点的值 int Degree(); //返回结点的度 int ChildAmount(); //返回结点的孩子个数 TreeClass *Root(); //返回本结点所在树的根结点 TreeClass *Parent(); //返回本结点的父亲结点 TreeClass *Child(int Child); //返回本结点的某个儿子结点 void DFS(int (*Visit)(TreeClass *)); //对以本结点为根的树,函数 int Visit(BinaryTreeClass *)为访问方式进行深度优先遍历 void BFS(int (*Visit)(TreeClass *)); //对以本结点为根的树,函数 int Visit(BinaryTreeClass *)为访问方式进行宽度优先遍历 int InsertChild(TreeClass *SubTree); // 将树 SubTree 作为本结点的某 一子树插入本结点所在树 int DeleteChild(int Child); //删除本结点的某一子树 ~TreeClass(); //析构函数 } ; template TreeClass::TreeClass(int Degree) { int i; Dgr=Degree; 35 Prt=NULL; Chd=new TreeClass *[Dgr]; for (i=0;i<=Dgr-1;i++) Chd[i]=NULL; } template TreeClass::TreeClass(int Degree, DataType x) { int i; Dgr=Degree; Data=x; Prt=NULL; Chd=new TreeClass *[Dgr]; for (i=0;i<=Dgr-1;i++) Chd[i]=NULL; } template TreeClass::TreeClass(int Degree, TreeClass *Parent) { int i; Dgr=Degree; Prt=Parent; Chd=new TreeClass *[Dgr]; for (i=0;i<=Dgr-1;i++) Chd[i]=NULL; } template TreeClass::TreeClass(int Degree, DataType x, TreeClass *Parent) { int i; Dgr=Degree; Data=x; Prt=Parent; Chd=new TreeClass *[Dgr]; for (i=0;i<=Dgr-1;i++) Chd[i]=NULL; } template void TreeClass::Assign(DataType x) { 36 Data=x; } template DataType TreeClass::Value() { return Data; } template int TreeClass::Degree() { return Dgr; } template int TreeClass::ChildAmount() { int i=0; for (i=0;i<=Dgr-1;i++) if (Chd[i]==NULL) return i; return i; } template TreeClass *TreeClass::Root() { TreeClass *Temp=this; while (Temp->Prt!=NULL) Temp=Temp->Prt; return Temp; } template TreeClass *TreeClass::Parent() { return Prt; } template TreeClass *TreeClass::Child(int Child) { if (Child>=Dgr) return NULL; 37 else return Chd[Child]; } template void TreeClass::DFS(int (*Visit)(TreeClass *)) { int i; Visit(this); for (i=0;i<=Dgr-1;i++) if (Chd[i]!=NULL) Chd[i]->DFS(Visit); else break; } template void TreeClass::BFS(int (*Visit)(TreeClass *)) { TreeClass *Temp=this; QueueClass *> Queue; int i; Queue.Push(Temp); while (!Queue.Empty()) { Queue.Pop(Temp); Visit(Temp); for (i=0;i<=Dgr-1;i++) if (Temp->Chd[i]!=NULL) Queue.Push(Temp->Chd[i]); else break; } } template int TreeClass::InsertChild(TreeClass *SubTree) { int i; if (SubTree!=NULL) { for (i=0;i<=Dgr-1;i++) if (Chd[i]==NULL) { Chd[i]=SubTree; SubTree->Prt=this; 38 return 0; } return 2; } else return 1; } template int TreeClass::DeleteChild(int Child) { if (Chd[Child]!=NULL) { delete Chd[Child]; Chd[Child]=NULL; return 0; } else return 1; } template TreeClass::~TreeClass() { int i; for (i=0;i<=Dgr-1;i++) if (Chd[i]!=NULL) DeleteChild(i); else break; } 8 图 8.1 图的定义 /*注:在调用成员函数 int BFS(int (*Visit)(GraphClass &,int), int Start)前需要定义 QueueClass类*/ template class GraphClass { private: int Size; VexType *Vex; ArcType **Arc; 39 void DfsTravel(int (*Visit)(GraphClass &,int), int Now, bool Visited[]); public: void Init(); //初始化图顶点和边 GraphClass(int x); //构造函数,创建一个定点数为 x 的图 int UpdateVex(int Num, VexType Data); //更改顶点 Num 的数据为 Data int UpdateArc(int x, int y, ArcType Data, bool Untl=false); //更改边 的数据为 Data,Untl=true 时表示这条边是单向边 int GetSize(); //返回图的顶点数 VexType GetVex(int Num); //获取顶点 Num 的数据 ArcType GetArc(int x, int y); //获取边的数据 int InDegree(int Num); //求顶点 Num 的入度 int OutDegree(int Num); //求顶点 Num 的出度 int DFS(int (*Visit)(GraphClass &,int), int Start); //以 Start 为起点,Visit 为访问方式,深度优先遍历图 int BFS(int (*Visit)(GraphClass &,int), int Start); //以 Start 为起点,Visit 为访问方式,宽度优先遍历图 ~GraphClass(); //析构函数 } ; template void GraphClass::Init() { int i,j; for (i=0;i<=Size-1;i++) Vex[i]=0; for (i=0;i<=Size-1;i++) for (j=0;j<=Size-1;j++) Arc[i][j]=0; } template GraphClass::GraphClass(int x) { int i; Size=x; Vex=new VexType[Size]; Arc=new ArcType *[Size]; for (i=0;i<=Size-1;i++) Arc[i]=new ArcType[Size]; Init(); } 40 template int GraphClass::UpdateVex(int Num, VexType Data) { if (Num int GraphClass::UpdateArc(int x, int y, ArcType Data, bool Untl=false) { if (x int GraphClass::GetSize() { return Size; } template VexType GraphClass::GetVex(int Num) { if (Num ArcType GraphClass::GetArc(int x, int y) { if (x int GraphClass::InDegree(int Num) { int Ans=0,i; for (i=0;i<=Size-1;i++) if (Arc[i][Num]>0) Ans++; return Ans; } template int GraphClass::OutDegree(int Num) { int Ans=0,i; for (i=0;i<=Size-1;i++) if (Arc[Num][i]>0) Ans++; return Ans; } template void GraphClass::DfsTravel(int (*Visit)(GraphClass &,int), int Now, bool Visited[]) { int i; Visit(*this,Now); Visited[Now]=true; for (i=0;i<=Size-1;i++) if (Arc[Now][i]>0 && !Visited[i]) DfsTravel(Visit,i,Visited); } template int GraphClass::DFS(int (*Visit)(GraphClass &,int), int Start) { int i; bool *Visited=new bool[Size]; if (Start int GraphClass::BFS(int (*Visit)(GraphClass &,int), int Start) { QueueClass Queue; int i,Temp; bool *Visited=new bool[Size]; if (Start0 && !Visited[i]) { Queue.Push(i); Visited[i]=true; } } return 0; } else return 1; } template GraphClass::~GraphClass() { int i; delete[] Vex; for (i=0;i<=Size-1;i++) delete[] Arc[i]; delete[] Arc; } 43 8.2 图的最短路径 8.2.1 Dijkstra 算法 /* 函数功能:计算图的单源最短路径。 函数原形:void Dijkstra(GraphClass &Graph, int Start); 参数: GraphClass &Graph:目标图; int Start:起点下标。 返回值:ArcType *型,结果数组首地址。 备注:无。 */ template ArcType *Dijkstra(GraphClass &Graph, int Start) { ArcType *Distance=new ArcType[Graph.GetSize()],Min,Infinite=ArcType(unsigned(~0)/2); int i,j,m; bool *Used=new bool[Graph.GetSize()]; for (i=0;i<=Graph.GetSize()-1;i++) { Used[i]=false; if (Graph.GetArc(Start,i)>0) Distance[i]=Graph.GetArc(Start,i); else Distance[i]=Infinite; } Distance[Start]=0; Used[Start]=1; for (i=1;i<=Graph.GetSize()-1;i++) { Min=Infinite; m=Start; for (j=0;j<=Graph.GetSize()-1;j++) if (!Used[j] && Distance[j]0 && !Used[j] && Min+Graph.GetArc(m,j) &Graph); 参数: GraphClass &Graph:目标图。 返回值:ArcType **型,结果数组首地址。 备注:无。 */ template ArcType **Floyd(GraphClass &Graph) { ArcType **Distance,Infinite=ArcType(unsigned(~0)/2); int i,j,k; Distance=new ArcType *[Graph.GetSize()]; for (i=0;i<=Graph.GetSize()-1;i++) Distance[i]=new ArcType[Graph.GetSize()]; for (i=0;i<=Graph.GetSize()-1;i++) for (j=0;j<=Graph.GetSize()-1;j++) if (Graph.GetArc(i,j)>0) Distance[i][j]=Graph.GetArc(i,j); else Distance[i][j]=Infinite; for (k=0;k<=Graph.GetSize()-1;k++) for (i=0;i<=Graph.GetSize()-1;i++) for (j=0;j<=Graph.GetSize()-1;j++) if (i!=j && i!=k && k!=j) if (Distance[i][k]+Distance[k][j] *Prim(GraphClass &Graph); 45 参数: GraphClass &Graph:目标图。 返回值:GraphClass *型,最小生成树地址。 备注:无。 */ template GraphClass *Prim(GraphClass &Graph) { ArcType Min,Infinite=ArcType(unsigned(~0)/2); GraphClass *Mcst=new GraphClass(Graph.GetSize()); int i,j,k,x,y; bool *Vertex=new bool[Graph.GetSize()]; for (i=0;i<=Graph.GetSize()-1;i++) { Vertex[i]=false; Mcst->UpdateVex(i,Graph.GetVex(i)); } Vertex[0]=true; for (k=1;k<=Graph.GetSize()-1;k++) { Min=Infinite; for (i=0;i<=Graph.GetSize()-1;i++) for (j=0;j<=Graph.GetSize()-1;j++) if (Graph.GetArc(i,j)>0 && Vertex[i] && !Vertex[j] && Graph.GetArc(i,j)UpdateArc(x,y,Graph.GetArc(x,y)); } return Mcst; } 8.3.2 Kruskal 算法 /* 函数功能:求图的最小生成树。 函数原形:GraphClass *Kruskal(GraphClass &Graph); 46 参数: GraphClass &Graph:目标图。 返回值:GraphClass *型,最小生成树地址。 备注:无。 */ template GraphClass *Kruskal(GraphClass &Graph) { ArcType Min,Infinite=ArcType(unsigned(~0)/2); GraphClass *Mcst=new GraphClass(Graph.GetSize()); int i,j,k,x,y,a,b,*VexSet=new int[Graph.GetSize()]; for (i=0;i<=Graph.GetSize()-1;i++) { VexSet[i]=i; Mcst->UpdateVex(i,Graph.GetVex(i)); } for (k=1;k<=Graph.GetSize()-1;k++) { Min=Infinite; for (i=0;i<=Graph.GetSize()-1;i++) for (j=0;j<=Graph.GetSize()-1;j++) if (Graph.GetArc(i,j)>0 && VexSet[i]!=VexSet[j] && Mcst->GetArc(i,j)==0 && Graph.GetArc(i,j)UpdateArc(x,y,Graph.GetArc(x,y)); } return Mcst; } 8.4 拓扑排序 /* 函数功能:求有向图的拓扑序列。 函数原形:int TopSort(GraphClass &Graph, int Sequence[]); 47 参数: GraphClass &Graph:目标图; int Sequence[]:拓扑序列。 返回值:int 型,返回 1 表示有向图中有环路。 备注:需定义 StackClass 类。 */ template int TopSort(GraphClass &Graph, int Sequence[]) { StackClass Stack; int i,x,Count,*InDegree=new int[Graph.GetSize()]; for (i=0;i<=Graph.GetSize()-1;i++) InDegree[i]=Graph.InDegree(i); for (i=0;i<=Graph.GetSize()-1;i++) if (InDegree[i]==0) Stack.Push(i); Count=0; while (!Stack.Empty()) { Stack.Pop(x); Sequence[Count++]=x; for (i=0;i<=Graph.GetSize()-1;i++) if (Graph.GetArc(x,i)>0) if (--InDegree[i]==0) Stack.Push(i); } if (Count==Graph.GetSize()) return 0; else return 1; } 8.5 关键路径 /* 函数功能:求有向图的关键路径。 函数原形:GraphClass *CriticalPath(GraphClass &Graph); 参数: GraphClass &Graph:目标图。 返回值:GraphClass *型,关键路径地址,如果图中有环路,返回 NULL。 备注:需定义 TopSort,和 StackClass 类。 */ template GraphClass *CriticalPath(GraphClass &Graph) { ArcType Min,Max,*VexEarlest=new ArcType[Graph.GetSize()],*VexLatest=new ArcType[Graph.GetSize()],Infinite=ArcType(unsigned(~0)/2); 48 GraphClass *Path=new GraphClass(Graph.GetSize()); int i,j,*Sequence=new int[Graph.GetSize()]; if (TopSort(Graph,Sequence)==0) { for (i=0;i<=Graph.GetSize()-1;i++) Path->UpdateVex(i,Graph.GetVex(i)); VexEarlest[0]=0; for (i=1;i<=Graph.GetSize()-1;i++) { Max=0; for (j=0;j<=Graph.GetSize()-1;j++) if (Graph.GetArc(j,Sequence[i])>0 && VexEarlest[j]+Graph.GetArc(j,Sequence[i])>Max) Max=VexEarlest[j]+Graph.GetArc(j,Sequence[i]); VexEarlest[Sequence[i]]=Max; } VexLatest[Graph.GetSize()-1]=VexEarlest[Graph.GetSize()-1]; for (i=Graph.GetSize()-2;i>=0;i--) { Min=Infinite; for (j=0;j<=Graph.GetSize()-1;j++) if (Graph.GetArc(Sequence[i],j)>0 && VexLatest[j]-Graph.GetArc(Sequence[i],j)0 && VexEarlest[i]==VexLatest[i] && VexEarlest[j]==VexLatest[j]) Path->UpdateArc(i,j,Graph.GetArc(i,j),1); return Path; } else return NULL; } 9 高精度计算 9.1 加法 /* 函数功能:高精度加法。 49 函数原形:string Add(string Num1, string Num2); 参数: string Num1, string Num2:被加数与加数。 返回值:string 型,两数之和。 备注:需包含。 */ string Add(string Num1, string Num2) { string Ans; int *a,*b,i,Max,Len,Len1,Len2,k; Len1=(int)Num1.length(); Len2=(int)Num2.length(); if (Len1>Len2) Len=Len1; else Len=Len2; Max=Len; a=new int[Len+1]; for (i=0;i<=Len;i++) a[i]=0; b=new int[Len]; for (i=0;i<=Len-1;i++) b[i]=0; k=0; for (i=Len1-1;i>=0;i--) a[k++]=Num1[i]-'0'; k=0; for (i=Len2-1;i>=0;i--) b[k++]=Num2[i]-'0'; for (i=0;i<=Len-1;i++) { a[i]=a[i]+b[i]; if (a[i]>=10) { a[i]=a[i]-10; a[i+1]++; } } while (Len+1>Max || a[Len+1]==0) Len--; for (i=Len+1;i>=0;i--) Ans.append(1,a[i]+'0'); return Ans; } 9.2 减法 /* 函数功能:高精度减法。 函数原形:string Sub(string Num1, string Num2); 参数: 50 string Num1, string Num2:被减数与减数。 返回值:string 型,两数之差。 备注:需包含。 */ string Sub(string Num1, string Num2) { string Ans; int *a,*b,i,Max,Len,Len1,Len2,k; Len1=(int)Num1.length(); Len2=(int)Num2.length(); Len=Len1; Max=Len; a=new int[Len]; b=new int[Len]; for (i=0;i<=Len-1;i++) { a[i]=0; b[i]=0; } k=0; for (i=Len1-1;i>=0;i--) a[k++]=Num1[i]-'0'; k=0; for (i=Len2-1;i>=0;i--) b[k++]=Num2[i]-'0'; for (i=0;i<=Len-1;i++) if (a[i]0 || Len>=Max) Len--; for (i=Len;i>=0;i--) Ans.append(1,a[i]+'0'); return Ans; } 9.3 乘法 /* 函数功能:高精度乘法。 函数原形:string Sub(string Num1, string Num2); 参数: string Num1, string Num2:被乘数与乘数。 51 返回值:string 型,两数之积。 备注:需包含。 */ string Mul(string Num1, string Num2) { string Ans; int *a,*b,*c,Max,Len1,Len2,Len,k,x,y,z,i,j,w; Len1=(int)Num1.length(); Len2=(int)Num2.length(); Len=Len1+Len2; Max=Len; a=new int[Len1]; for (i=0;i<=Len1-1;i++) a[i]=0; b=new int[Len2]; for (i=0;i<=Len2-1;i++) b[i]=0; c=new int[Len]; for (i=0;i<=Len-1;i++) c[i]=0; k=0; for (i=Len1-1;i>=0;i--) a[k++]=Num1[i]-'0'; k=0; for (i=Len2-1;i>=0;i--) b[k++]=Num2[i]-'0'; for (i=0;i<=Len1-1;i++) for (j=0;j<=Len2-1;j++) { x=a[i]*b[j]; y=x/10; z=x%10; w=i+j; c[w]=c[w]+z; c[w+1]=c[w+1]+c[w]/10+y; c[w]=c[w]%10; } while (c[Len]==0 && Len>0 || Len>=Max) Len--; for (i=Len;i>=0;i--) Ans.append(1,c[i]+'0'); return Ans; }
还剩50页未读

继续阅读

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

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

需要 20 金币 [ 分享pdf获得金币 ] 4 人已下载

下载pdf

pdf贡献者

opencw

贡献于2011-09-23

下载需要 20 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf