- 论坛徽章:
- 0
|
1，特别推荐MSDN Library Visual Studio 6.0 简体中文版\n http://ftp.sdshiyan.cn/soft/program/DN60ACHS1.rar\n http://ftp.sdshiyan.cn/soft/program/DN60ACHS2.rar\n2， C/C++ 函数设计\n\n \n 函数设计\n函数是C++/C程序的基本功能单元，其重要性不言而喻。函数设计的细微缺点很容易导致该函数被错用，所以光使函数的功能正确是不够的。本章重点论述函数的接口设计和内部实现的一些规则。\n\n函数接口的两个要素是参数和返回值。C语言中，函数的参数和返回值的传递方式有两种：值传递（pass by value）和指针传递（pass by pointer）。C++ 语言中多了引用传递（pass by reference）。由于引用传递的性质象指针传递，而使用方式却象值传递，初学者常常迷惑不解，容易引起混乱，请先阅读6.6节“引用与指针的比较”。\n\n6.1 参数的规则\nl 【规则6-1-1】参数的书写要完整，不要贪图省事只写参数的类型而省略参数名字。如果函数没有参数，则用void填充。\n\n例如：\n\nvoid SetValue(int width, int height); // 良好的风格\n\nvoid SetValue(int, int); // 不良的风格\n\nfloat GetValue(void); // 良好的风格\n\nfloat GetValue(); // 不良的风格\n\n\n\nl 【规则6-1-2】参数命名要恰当，顺序要合理。\n\n例如编写字符串拷贝函数StringCopy，它有两个参数。如果把参数名字起为str1和str2，例如\n\nvoid StringCopy(char *str1, char *str2);\n\n那么我们很难搞清楚究竟是把str1拷贝到str2中，还是刚好倒过来。\n\n可以把参数名字起得更有意义，如叫strSource和strDestination。这样从名字上就可以看出应该把strSource拷贝到strDestination。\n\n还有一个问题，这两个参数那一个该在前那一个该在后？参数的顺序要遵循程序员的习惯。一般地，应将目的参数放在前面，源参数放在后面。\n\n如果将函数声明为：\n\nvoid StringCopy(char *strSource, char *strDestination);\n\n别人在使用时可能会不假思索地写成如下形式：\n\nchar str[20];\n\nStringCopy(str, “Hello World”); // 参数顺序颠倒\n\n\n\nl 【规则6-1-3】如果参数是指针，且仅作输入用，则应在类型前加const，以防止该指针在函数体内被意外修改。\n\n例如：\n\nvoid StringCopy(char *strDestination，const char *strSource);\n\n\n\nl 【规则6-1-4】如果输入参数以值传递的方式传递对象，则宜改用“const &”方式来传递，这样可以省去临时对象的构造和析构过程，从而提高效率。\n\n\n\n² 【建议6-1-1】避免函数有太多的参数，参数个数尽量控制在5个以内。如果参数太多，在使用时容易将参数类型或顺序搞错。\n\n\n\n² 【建议6-1-2】尽量不要使用类型和数目不确定的参数。\n\nC标准库函数printf是采用不确定参数的典型代表，其原型为：\n\nint printf(const chat *format[, argument]…);\n\n这种风格的函数在编译时丧失了严格的类型安全检查。\n\n6.2 返回值的规则\nl 【规则6-2-1】不要省略返回值的类型。\n\nC语言中，凡不加类型说明的函数，一律自动按整型处理。这样做不会有什么好处，却容易被误解为void类型。\n\nC++语言有很严格的类型安全检查，不允许上述情况发生。由于C++程序可以调用C函数，为了避免混乱，规定任何C++/ C函数都必须有类型。如果函数没有返回值，那么应声明为void类型。\n\n\n\nl 【规则6-2-2】函数名字与返回值类型在语义上不可冲突。\n\n违反这条规则的典型代表是C标准库函数getchar。\n\n例如：\n\nchar c;\n\nc = getchar();\n\nif (c == EOF)\n\n…\n\n按照getchar名字的意思，将变量c声明为char类型是很自然的事情。但不幸的是getchar的确不是char类型，而是int类型，其原型如下：\n\nint getchar(void);\n\n由于c是char类型，取值范围是[-128，127]，如果宏EOF的值在char的取值范围之外，那么if语句将总是失败，这种“危险”人们一般哪里料得到！导致本例错误的责任并不在用户，是函数getchar误导了使用者。\n\n\n\nl 【规则6-2-3】不要将正常值和错误标志混在一起返回。正常值用输出参数获得，而错误标志用return语句返回。\n\n回顾上例，C标准库函数的设计者为什么要将getchar声明为令人迷糊的int类型呢？他会那么傻吗？\n\n在正常情况下，getchar的确返回单个字符。但如果getchar碰到文件结束标志或发生读错误，它必须返回一个标志EOF。为了区别于正常的字符，只好将EOF定义为负数（通常为负1）。因此函数getchar就成了int类型。\n\n我们在实际工作中，经常会碰到上述令人为难的问题。为了避免出现误解，我们应该将正常值和错误标志分开。即：正常值用输出参数获得，而错误标志用return语句返回。\n\n函数getchar可以改写成 BOOL GetChar(char *c);\n\n虽然gechar比GetChar灵活，例如 putchar(getchar()); 但是如果getchar用错了，它的灵活性又有什么用呢？\n\n\n\n² 【建议6-2-1】有时候函数原本不需要返回值，但为了增加灵活性如支持链式表达，可以附加返回值。\n\n例如字符串拷贝函数strcpy的原型：\n\nchar *strcpy(char *strDest，const char *strSrc);\n\nstrcpy函数将strSrc拷贝至输出参数strDest中，同时函数的返回值又是strDest。这样做并非多此一举，可以获得如下灵活性：\n\nchar str[20];\n\nint length = strlen( strcpy(str, “Hello World”) ); \n\n\n\n² 【建议6-2-2】如果函数的返回值是一个对象，有些场合用“引用传递”替换“值传递”可以提高效率。而有些场合只能用“值传递”而不能用“引用传递”，否则会出错。\n\n例如：\n\nclass String\n\n{…\n\n// 赋值函数\n\nString & operate=(const String &other); \n\n// 相加函数，如果没有friend修饰则只许有一个右侧参数\n\nfriend String operate+( const String &s1, const String &s2); \n\nprivate:\n\nchar *m_data; \n\n}\n\n\n\nString的赋值函数operate = 的实现如下：\n\nString & String: perate=(const String &other)\n\n{\n\nif (this == &other)\n\nreturn *this;\n\ndelete m_data;\n\nm_data = new char[strlen(other.data)+1];\n\nstrcpy(m_data, other.data);\n\nreturn *this; // 返回的是 *this的引用，无需拷贝过程\n\n}\n\n\n\n对于赋值函数，应当用“引用传递”的方式返回String对象。如果用“值传递”的方式，虽然功能仍然正确，但由于return语句要把 *this拷贝到保存返回值的外部存储单元之中，增加了不必要的开销，降低了赋值函数的效率。例如：\n\nString a,b,c;\n\n…\n\na = b; // 如果用“值传递”，将产生一次 *this 拷贝\n\na = b = c; // 如果用“值传递”，将产生两次 *this 拷贝\n\n\n\nString的相加函数operate + 的实现如下：\n\nString operate+(const String &s1, const String &s2) \n\n{\n\nString temp;\n\ndelete temp.data; // temp.data是仅含‘\0’的字符串\n\ntemp.data = new char[strlen(s1.data) + strlen(s2.data) +1];\n\nstrcpy(temp.data, s1.data);\n\nstrcat(temp.data, s2.data);\n\nreturn temp;\n\n}\n\n\n\n对于相加函数，应当用“值传递”的方式返回String对象。如果改用“引用传递”，那么函数返回值是一个指向局部对象temp的“引用”。由于temp在函数结束时被自动销毁，将导致返回的“引用”无效。例如：\n\nc = a + b; \n\n此时 a + b 并不返回期望值，c什么也得不到，流下了隐患。\n\n6.3 函数内部实现的规则\n不同功能的函数其内部实现各不相同，看起来似乎无法就“内部实现”达成一致的观点。但根据经验，我们可以在函数体的“入口处”和“出口处”从严把关，从而提高函数的质量。\n\n\n\nl 【规则6-3-1】在函数体的“入口处”，对参数的有效性进行检查。\n\n很多程序错误是由非法参数引起的，我们应该充分理解并正确使用“断言”（assert）来防止此类错误。详见6.5节“使用断言”。\n\n\n\nl 【规则6-3-2】在函数体的“出口处”，对return语句的正确性和效率进行检查。\n\n如果函数有返回值，那么函数的“出口处”是return语句。我们不要轻视return语句。如果return语句写得不好，函数要么出错，要么效率低下。\n\n注意事项如下：\n\n（1）return语句不可返回指向“栈内存”的“指针”或者“引用”，因为该内存在函数体结束时被自动销毁。例如\n\nchar * Func(void)\n\n{\n\nchar str[] = “hello world”; // str的内存位于栈上\n\n…\n\nreturn str; // 将导致错误\n\n}\n\n（2）要搞清楚返回的究竟是“值”、“指针”还是“引用”。\n\n（3）如果函数返回值是一个对象，要考虑return语句的效率。例如 \n\nreturn String(s1 + s2);\n\n这是临时对象的语法，表示“创建一个临时对象并返回它”。不要以为它与“先创建一个局部对象temp并返回它的结果”是等价的，如\n\nString temp(s1 + s2);\n\nreturn temp;\n\n实质不然，上述代码将发生三件事。首先，temp对象被创建，同时完成初始化；然后拷贝构造函数把temp拷贝到保存返回值的外部存储单元中；最后，temp在函数结束时被销毁（调用析构函数）。然而“创建一个临时对象并返回它”的过程是不同的，编译器直接把临时对象创建并初始化在外部存储单元中，省去了拷贝和析构的化费，提高了效率。\n\n类似地，我们不要将 \n\nreturn int(x + y); // 创建一个临时变量并返回它\n\n写成\n\nint temp = x + y;\n\nreturn temp;\n\n由于内部数据类型如int,float,double的变量不存在构造函数与析构函数，虽然该“临时变量的语法”不会提高多少效率，但是程序更加简洁易读。\n\n6.4 其它建议\n² 【建议6-4-1】函数的功能要单一，不要设计多用途的函数。\n\n² 【建议6-4-2】函数体的规模要小，尽量控制在50行代码之内。\n\n² 【建议6-4-3】尽量避免函数带有“记忆”功能。相同的输入应当产生相同的输出。\n\n带有“记忆”功能的函数，其行为可能是不可预测的，因为它的行为可能取决于某种“记忆状态”。这样的函数既不易理解又不利于测试和维护。在C/C++语言中，函数的static局部变量是函数的“记忆”存储器。建议尽量少用static局部变量，除非必需。\n\n² 【建议6-4-4】不仅要检查输入参数的有效性，还要检查通过其它途径进入函数体内的变量的有效性，例如全局变量、文件句柄等。\n\n² 【建议6-4-5】用于出错处理的返回值一定要清楚，让使用者不容易忽视或误解错误情况。\n\n6.5 使用断言\n程序一般分为Debug版本和Release版本，Debug版本用于内部调试，Release版本发行给用户使用。\n\n断言assert是仅在Debug版本起作用的宏，它用于检查“不应该”发生的情况。示例6-5是一个内存复制函数。在运行过程中，如果assert的参数为假，那么程序就会中止（一般地还会出现提示对话，说明在什么地方引发了assert）。\n\n\n\nvoid *memcpy(void *pvTo, const void *pvFrom, size_t size)\n\n{\n\nassert((pvTo != NULL) && (pvFrom != NULL)); // 使用断言\n\nbyte *pbTo = (byte *) pvTo; // 防止改变pvTo的地址\n\nbyte *pbFrom = (byte *) pvFrom; // 防止改变pvFrom的地址\n\nwhile(size -- > 0 )\n\n*pbTo ++ = *pbFrom ++ ;\n\nreturn pvTo;\n\n}\n\n3，信息来源：风云剑侠Swords\n转帖来源：中国 邪恶八进制（www.EvilOctal.com）\n\n\n这是我学数据结构编写的算法，我把他整理出来，都是基本算法，供大家学习。我使用c++面向对象形式编写，各种算法都封装在各自的类里，如果想增加功能，在相应的类里增加函数即可。我对树和图的构造也做了一些人性化设计，输入更加形象化，你可能看不懂，没关系漫漫来。各种类都使用模版设计，可以对各种数据类型操作（整形，字符，浮点） \n\n/////////////////////////// \n// // \n// 堆栈数据结构 stack.h // \n// // \n////////////////////////// \n\n\n#include<iostream.h> \n\ntemplate<class Type>class Stack; \n\ntemplate<class Type> \nclass StackNode \n{ \nfriend class Stack<Type>; \nprivate: \nType data; \nStackNode<Type> *link; \n StackNode(Type D=0,StackNode<Type> *L=NULL):link(L),data(D){} \n}; \n\ntemplate<class Type> \nclass Stack \n{ \npublic: \nStack():top(NULL),NumItem(0){} \nvoid Push(Type item); \nType Pop(); \nType GetTop(); \nvoid MakeEmpty(); \nbool ISEmpty(); \nint GetNum(); \nprivate: \nint NumItem; \nStackNode<Type> *top; \n}; \n\ntemplate<class Type> \nvoid Stack<Type>: ush(Type item) \n{ \n top=new StackNode<Type>(item,top); \nNumItem++; \n} \n\ntemplate<class Type> \nType Stack<Type>:op() \n{ \nStackNode<Type> *p; \nType temp; \ntemp=top->data; \np=top; \ntop=top->link; \ndelete p; \nNumItem--; \nreturn temp; \n\n} \n\ntemplate<class Type> \nType Stack<Type>::GetTop() \n{ \nreturn top->data; \n} \n\ntemplate<class Type> \nbool Stack<Type>::ISEmpty() \n{ \nreturn top==NULL; \n} \n\ntemplate<class Type> \nvoid Stack<Type>::MakeEmpty() \n{ \ndelete top; \n} \n\ntemplate<class Type> \nint Stack<Type>::GetNum() \n{ \nreturn NumItem; \n}\n\n-------------------------------------------------------------------------------------------------------------\n/////////////////////////// \n// // \n// 队列数据结构 Queue.h // \n// // \n////////////////////////// \n#include<iostream.h> \n\ntemplate<class Type> class Queue; \n\ntemplate<class Type> class QueueNode \n{ \nfriend class Queue<Type>; \nprivate: \nType data; \nQueueNode<Type> *link; \nQueueNode(Type d=0,QueueNode *l=NULL):data(d),link(l){} \n}; \n\ntemplate <class Type> class Queue \n{ \npublic: \nQueue():rear(NULL),front(NULL){} \n~Queue(); \nvoid EnQueue(Type item); \nType DelQueue(); \nType GetFront(); \nvoid MakeEmpty(); \nbool ISEmpty() { return front==NULL; } \nprivate: \nQueueNode<Type> *front,*rear; \n}; \n\n\ntemplate<class Type> \nQueue<Type>::~Queue() \n{ \nQueueNode<Type> *p; \nwhile(front!=NULL) \n{ \np=front; \nfront=front->link; \ndelete p; \n} \n} \n\ntemplate<class Type> \nvoid Queue<Type>::EnQueue(Type item) \n{ \nif(front==NULL) \nfront=rear=new QueueNode<Type> (item,NULL); \nelse \nrear=rear->link=new QueueNode<Type> (item,NULL); \n} \n\n\ntemplate<class Type> \nType Queue<Type>: elQueue() \n{ \nQueueNode<Type> *p=front; \nType temp=p->data;; \nfront=front->link; \ndelete p; \nreturn temp; \n} \n\n\ntemplate<class Type> \nType Queue<Type>::GetFront() \n{ \nreturn front->data; \n} \n\n\ntemplate<class Type> \nvoid Queue<Type>::MakeEmpty() \n{ \nQueueNode<Type> *p; \nwhile(front!=NULL) \n{ \np=front; \nfront=front->link; \ndelete p; \n} \n}\n-------------------------------------------------------------------------------------------------\n/////////////////////////// \n// // \n// 链表数据结构 list.h // \n// // \n////////////////////////// \n\n\n#include<iostream.h> \n\ntemplate<class type> \nclass list; \n\ntemplate<class type> \nclass listnode \n{ \npublic: \nfriend class list<type>; \nprivate: \ntype data; \nlistnode<type> * next; \n}; \n\n\ntemplate<class type> \nclass list \n{ \npublic: \nlist(); \n~list(); \nvoid insertend(type); //向链表尾部插入元素 \nbool insert(type,int); //向链表任意位置插入元素 \nvoid delnode(int i); //删除元素 \nint find(type T); //查找元素 \nvoid makeempty(); //销毁链表 \nbool print(); //打印链表 \nint getlen(); //得到链表长度 \n private: \nlistnode<type> *first,*last; \nint length; \n}; \n\ntemplate<class type> \nvoid initlist(type &tmp); \n\ntemplate<class type> \nvoid list_exit(list<type> &L,type tmp); \n\nvoid initation(); \n\ntemplate<class type> \nvoid list_insertend(list<type> &L,type tmp); \n\n\ntemplate<class type> int list<type>::getlen() \n{ \nreturn length; \n} \n\ntemplate<class type> void list<type>::makeempty() \n{ \nlistnode<type> *p1,*p2; \n\np1=first->next; \nfirst->next=NULL; \nwhile(p1!=NULL) \n { \np2=p1; \np1=p1->next; \ndelete p2; \n} \nlength=0; \n} \n\ntemplate<class type> void list<type>::insertend(type t) \n{ \n\nlistnode<type> *p; \np=new listnode<type>; \np->data=t; \np->next=NULL; \nlast->next=p; \nlast=p; \n\nlength++; \n} \n\ntemplate<class type> bool list<type>::insert(type t,int i) \n{ \nlistnode<type> *p; \np=first; \n\nint k=1; \nwhile(p!=NULL&&k<i) \n{ \np=p->next; \nk++; \n} \nif(p==NULL&&k!=i) \nreturn false; \nelse \n{ \n listnode<type> *tp; \n tp=new listnode<type>; \n tp->data=t; \n tp->next=p->next; \n p->next=tp; \n length++; \n \n return true; \n} \n} \n\ntemplate<class type> void list<type>::delnode(int i) \n{ \nint k=1; \nlistnode<type> *p,*t; \np=first; \n\nwhile(p->next!=NULL&&k!=i) \n{ \np=p->next; \n k++; \n} \n t=p->next; \ncout<<\"你已经将数据项 \"<<t->data<<\"删除\"<<endl; \n\np->next=p->next->next; \nlength--; \ndelete t; \n} \n\ntemplate<class type> bool list<type>::print() \n{ \nlistnode<type> *p=first->next; \nif(length==0) \nreturn false; \nelse \n{ \ncout<<\"链表中有\"<<length<<\"项数据: \"<<endl; \nwhile(p) \n{ \n cout<<p->data<<\" \"; \n p=p->next; \n} \n} \ncout<<endl; \n\n\nreturn true; \n} \n\ntemplate<class type> int list<type>::find(type T) \n{ \nlistnode<type> *p=first->next; \nint i=1; \nwhile(p&&p->data!=T) \n{ \np=p->next; \ni++; \n} \nif(p) \nreturn i; \nelse \n return 0; \n} \n\n\ntemplate<class type> list<type>::~list() \n{ \ndelete first; \ncout<<\"欢迎再次使用 (!^!) \"<<endl; \n} \n\ntemplate<class type> list<type>::list() \n{ \n listnode<type> *node=new listnode<type>; \n node->next=NULL; \n first=last=node; \n length=0; \n}\n--------------------------------------------------------------------------------------------------------------\n/////////////////////////// \n// // \n// 图数据结构 graph.h // \n// // \n////////////////////////// \n\n\n#include<iostream.h> \n#include\"Queue.h\" \n\ntemplate<class NameType,class DisType>class Graph; \n\ntemplate<class NameType,class DisType> struct Node \n{ \nfriend class Graph<NameType,DisType>; \nint num; \nDisType val; \nNode<NameType,DisType> *next; \n}; \n\ntemplate<class NameType,class DisType> struct GpNode \n{ \nfriend class Graph<NameType,DisType>; \nNameType data; \n Node<NameType,DisType> *link; \n}; \n\ntemplate<class NameType,class DisType> \nclass Graph \n{ \npublic: \nvoid Creat(); //创建图 \nvoid PrintNode(); //打印图中的各个数据项 \nvoid DFS(); //图的深度优先搜索,主过程 \nvoid DFS(int v,int visited[]); // 子过程 \nvoid BFS(); //图的广度优先搜索，主过程 \nvoid BFS(int v,int visited[]); //子过程 \nvoid ShortPath(); //求最短路径 \nprivate: \nGpNode<NameType,DisType> *table; \nNode<NameType,DisType> *p; \nint NumNode; //节点个数 \n}; \n\n\ntemplate<class NameType,class DisType> \nvoid Graph<NameType,DisType>::Creat() \n{ \ndo \n{ \ncout<<\"请输入节点个数: \"; \ncin >> NumNode; \n}while(NumNode<=0); \n\ntable=new GpNode<NameType,DisType>[NumNode]; \ncout<<\"请输入各节点数据项\"<<endl; \nfor(int i=0;i<NumNode;i++) \n{ \ncin>>table.data; \ntable.link=NULL; \n} \n\ncout<<\"请输入各边的关系 (如: A B)\"<<endl; \ni=1; \nNameType nodeA,nodeB; \nbool findA,findB; \nchar ISExit; \nint m,n; \ndo \n{ \nfindA=findB=false; \ncout<<\"请输入第\"<<i<<\"对边的关系\"<<endl; \ncin>>nodeA>>nodeB; \nfor(m=0,n=0;m<NumNode&&n<NumNode&&!(findA & findB) //查找边的节点 \n{ \n if(nodeA!=table[m].data) \n m++; \n else \n findA=true; \n if(nodeB!=table[n].data) \n n++; \n else \n findB=true; \n\n} \nif(!(findA & findB)) \n cout<<\"输入的节点数据项有错误\"<<endl; \nelse \n{ \n p=new Node<NameType,DisType>; \n p->next=table[m].link; \n p->num=n; \n table[m].link=p; \n cout<<\"请输入该对边的权值: \"; \n cin>>p->val; \n i++; \n} \ncout<<\"是否继续输入: y)继续,X)任意键退出 \"; \ncin>>ISExit; \nif(ISExit!=/y/&&ISExit!=/Y/) \n break; \n\n}while(true); \n \n} \n\ntemplate<class NameType,class DisType> \nvoid Graph<NameType,DisType>:rintNode() \n{ \ncout<<\"图中各节点数据项 : \"; \nfor(int i=0;i<NumNode;i++) \n cout<<table.data<<\" \"; \ncout<<endl; \n} \n\n\ntemplate<class NameType,class DisType> \nvoid Graph<NameType,DisType>:FS() \n{ \nint *visited=new int[NumNode]; \ncout<<\"图的深度优先搜索 : \"; \nfor(int i=0;i<NumNode;i++) \nvisited=0; \nfor(i=1;i<NumNode;i++) //遍厉孤立节点 \nDFS(i,visited); \ndelete []visited; \ncout<<endl; \n} \n\ntemplate<class NameType,class DisType> \nvoid Graph<NameType,DisType>:FS(int v,int visited[]) \n{ \nNode<NameType,DisType> *t; \nif(visited[v]==0) \n cout<<table[v].data<<\" \"; \nvisited[v]=1; \nt=table[v].link; \nwhile(t!=NULL) \n{ \nif(visited[t->num]==0) \n DFS(t->num,visited); \nt=t->next; \n} \n} \n\n\ntemplate<class NameType,class DisType> \nvoid Graph<NameType,DisType>::BFS() \n{ \nint *visited=new int[NumNode]; \ncout<<\"图的广度优先搜索 : \"; \nfor(int i=0;i<NumNode;i++) \nvisited=0; \nfor( i=0;i<NumNode;i++) \n BFS(i,visited); \n} \n\n\ntemplate<class NameType,class DisType> \nvoid Graph<NameType,DisType>::BFS(int v,int visited[]) \n{ \nQueue<int> q; \nint n; \nif(visited[v]==0) \n{ \nvisited[v]=1; \ncout<<table[v].data<<\" \"; \nq.EnQueue(v); \nwhile(!q.ISEmpty()) \n{ \n n=q.DelQueue(); \n p=table[n].link; \n while(p!=NULL) \n { \n n=p->num; \n if(visited[n]==0) \n { \n cout<<table[n].data<<\" \"; \n visited[n]=1; \n\n } \n p=p->next; \n } \n\n} \n} \n\n}\n-----------------------------------------------------------------------------------------------------------\n/////////////////////////// \n// // \n// 排序算法数据结构 Compositor.h // \n// // \n////////////////////////// \n\n\n#include<iostream.h> \n\n\ntemplate<class Type> \nclass Compositor \n{ \npublic: \nCompositor():sort(NULL){} \nvoid Creat(); //创建排序数组 \nvoid Bubble(); //冒泡排序 \nvoid Insert(); //插入排序 \n//快速排序 \nvoid Quick(); \nvoid QSort(int,int); \nint Partition(int low,int high); \n//归并排序 \nvoid Merge(Type SR[],Type TR[],int i,int m,int n); \nvoid Msort(Type SR[],Type TR1[],int s,int t); \n void MergeSort(); \n//选择排序 \nvoid Select(); \nvoid Print(); //打印排序后的结果 \nprotected: \nType *sort; \nint leng; \n}; \n\ntemplate<class Type> \nvoid Compositor<Type>::Creat() \n{ \ncout<<\"输入你需要排序的数据个数: \"; \ncin>>leng; \nwhile(leng<=0) \n{ \ncout<<\"输入数据有误\"; \ncin>>leng; \n} \nsort=new Type[leng]; \ncout<<\"请输入各数据项：\"; \nfor(int i=0;i<leng;i++) \ncin>>sort; \n} \n\n\ntemplate<class Type> \nvoid Compositor<Type>::Insert() \n{ \nCreat(); \nType temp; \n for(int i=1;i<leng;i++) \n{ \n if(sort<sort[i-1]) \n { \n temp=sort; \n for(int j=i-1;temp<sort[j]&&j>=0;j--) \n { \n sort[j+1]=sort[j]; \n } \n sort[j+1]=temp; \n } \n} \nPrint(); \n\n} \n\ntemplate<class Type> \nvoid Compositor<Type>::Bubble() \n{ \n Creat(); \nType temp; \nfor(int i=leng-1;i>=0;i--) \n{ \nfor(int j=0;j<leng-1;j++) \n{ \n if(sort[j]>sort[j+1]) \n { \n temp=sort[j]; \n sort[j]=sort[j+1]; \n sort[j+1]=temp; \n } \n} \n} \nPrint(); \n} \n\ntemplate<class Type> \nvoid Compositor<Type>: uick() \n{ \nCreat(); \n QSort(0,leng-1); \nPrint(); \n} \n\ntemplate<class Type> \nvoid Compositor<Type>:Sort(int s,int t) \n{ \nif(s<t-1) \n{ \nint pivotloc=Partition(s,t); \nQSort(s,pivotloc-1); \nQSort(pivotloc+1,t); \n} \n} \n\ntemplate<class Type> \nint Compositor<Type>:artition(int low,int high) \n{ \n Type pivotkey=sort[low]; \nwhile(low < high) \n{ \n while(low<high&&sort[high]>=pivotkey) \n --high; \n sort[low++]=sort[high]; \n while(low<high&&sort[low]<=pivotkey) \n ++low; \n sort[high--]=sort[low]; \n} \nsort[low]=pivotkey; \nreturn low; \n} \n\ntemplate<class Type> \nvoid Compositor<Type>::MergeSort() \n{ \nCreat(); \n Msort(sort,sort,0,leng-1); \nPrint(); \n} \n\n\ntemplate<class Type> \nvoid Compositor<Type>::Msort(Type SR[],Type TR1[],int s,int t) \n{ \nint m; \nType *TR2=new Type[t-s]; \nif(s==t) TR1=SR; \nelse \n{ \nm=(t+s)/2; \nMsort(SR,TR2,s,m); \nMsort(SR,TR2,m+1,t); \nMerge(TR2,TR1,s,m,t); \n} \n} \n\ntemplate<class Type> \nvoid Compositor<Type>::Merge(Type SR[],Type TR[],int i,int m,int n) \n{ \nfor(int j=m+1,k=i;i<=m&&j<=n;k++) \n{ \nif(SR<=SR[j]) \n TR[k]=SR[i++]; \nelse \n TR[k]=SR[j++]; \n} \nwhile(i<=m) \nTR[k++]=SR[i++]; \nwhile(j<=n) \nTR[k++]=SR[j++]; \n} \n\n\ntemplate<class Type> \nvoid Compositor<Type>::Select() \n{ \nCreat(); \n Type temp; \nint t; \nfor(int i=0;i<leng;i++) \n{ \nt=i; \nfor(int j=i+1;j<leng;j++) \n{ \n if(sort[t]>sort[j]) \n t=j; \n} \nif(t!=i) \n{ \n temp=sort[t]; \n sort[t]=sort; \n sort=temp; \n} \n} \nPrint(); \n} \n\ntemplate<class Type> \nvoid Compositor<Type>:rint() \n{ \ncout<<\"排序结果为: \"; \nfor(int i=0;i<leng;i++) \ncout<<sort<<\" \"; \ncout<<endl; \n}\n------------------------------------------------------------------------------------------------------------\n/////////////////////////// \n// // \n// 二叉树数据结构 BinTree.h // \n// // \n////////////////////////// \n\n\n#include<iostream.h> \n\ntemplate<class Type>class BinTree; \n\ntemplate<class Type> \nclass TreeNode \n{ \n protected: \n friend class BinTree<Type>; \nTreeNode():lchild(NULL),rchild(NULL){} \n Type data; \n TreeNode *lchild; //左，右子树 \n TreeNode *rchild; \n}; \n\ntemplate<class Type> \nclass BinTree \n{ \nfriend void BinTree_PRE(BinTree<Type>& BinTreeOPP); //友元函数 \nfriend void BinTree_INO(BinTree<Type>& BinTreeOPP); \nfriend void BinTree_POS(BinTree<Type>& BinTreeOPP); \nfriend void BinTree_Destroy(BinTree<Type>& BinTreeOPP); \npublic: \nBinTree():root(NULL){} \nvoid CreatTree(); //创建二叉树,主过程 \nvoid CreatTree(TreeNode<Type>* child,int k); //子过程 \nvoid PreTree(TreeNode<Type> *point); //先序遍历二叉树 \nvoid InoTree(TreeNode<Type> *point); //中序遍历二叉树 \nvoid PosTree(TreeNode<Type> *point); //后序遍历二叉树 \nvoid Destroy(TreeNode<Type> *point); //销毁二叉树 \nbool ISEmpty(); \nprotected: \nTreeNode<Type>* root; \n}; \n\n\ntemplate<class Type> \nvoid BinTree<Type>::CreatTree() \n{ \nCreatTree(root,1); \n} \n\ntemplate<class Type> \nvoid BinTree<Type>::CreatTree(TreeNode<Type>* child,int k) \n{ \n TreeNode<Type>* point; \npoint=new TreeNode<Type>; \ncout<<\"输入节点数据项 :\"; \n cin>>point->data; \n switch(k) \n{ \ncase 1: root=point; break; \ncase 2: child->lchild=point;break; \ncase 3: child->rchild=point;break; \n} \n\nchar temp; \n cout<<\"该\"<<point->data<<\"节点是否有左子树 Y / 任意键 :\"; \ncin>>temp; \nif(temp==/y/||temp==/Y/) \n{ \n CreatTree(point,2); \n} \n\n cout<<\"该\"<<point->data<<\"节点是否有右子树 Y / 任意键 :\"; \n cin>>temp; \n if(temp==/y/||temp==/Y/) \n{ \n CreatTree(point,3); \n} \n} \n\ntemplate<class Type> \nvoid BinTree<Type>:reTree(TreeNode<Type> *point) \n{ \nif(point!=NULL) \n{ \ncout<<\" \"<<point->data; \nPreTree(point->lchild); \nPreTree(point->rchild); \n} \n} \n\n\ntemplate<class Type> \nvoid BinTree<Type>::InoTree(TreeNode<Type> *point) \n{ \nif(point!=NULL) \n{ \n \n InoTree(point->lchild); \ncout<<\" \"<<point->data; \nInoTree(point->rchild); \n} \n} \n\ntemplate<class Type> \nvoid BinTree<Type>:osTree(TreeNode<Type> *point) \n{ \nif(point!=NULL) \n{ \n \nPosTree(point->lchild); \nPosTree(point->rchild); \ncout<<\" \"<<point->data; \n} \n} \n\n\ntemplate<class Type> \nbool BinTree<Type>::ISEmpty() \n{ \nreturn root==NULL; \n} \n\ntemplate<class Type> \nvoid BinTree<Type>:estroy(TreeNode<Type> *point) \n{ \nif(point!=NULL) \n{ \nDestroy(point->lchild); \nDestroy(point->rchild); \ndelete point; \n} \n}\n------------------------------------------------------------------------------------------------------------------\n/////////////////////////// \n// // \n// 基本功能函数 BaseFun.h // \n// // \n////////////////////////// \n\nvoid GRAPH(); \nvoid LIST(); \nvoid STACK(); \nvoid QUEUE(); \nvoid COMPOSITOR(); \nvoid BINTREE(); \n\n/////////////////////////// \n// // \n// 堆栈功能函数 Stack.cpp/ / \n// // \n////////////////////////// \n\n\n\n#include\"Stack.h\" \n#include\"iostream.h\" \n\n\nconst int INT =13; \nconst double FLOAT= 13.33; \nconst char CHAR =/a/; \n\n\n\n\ntemplate<class Type> \nvoid Stack_Push(Stack<Type> &StackOPP) \n{ \ncout<<\"请输入要插入的数据项: \"; \nType item; \ncin>>item; \n StackOPP.Push(item); \n} \n\ntemplate<class Type> \nvoid Stack_Pop(Stack<Type> &StackOPP) \n{ \nif(!StackOPP.ISEmpty()) \n{ \n cout<<\"出栈数据项: \"; \n cout<<StackOPP.Pop()<<endl; \n} \nelse \n{ \ncout<<\"堆栈已经为空!\"<<endl; \n} \n} \n\ntemplate<class Type> \nvoid Stack_ISEmpty(Stack<Type> &StackOPP) \n{ \nif(!StackOPP.ISEmpty()) \n cout<<\"堆栈不空,还有\"<<StackOPP.GetNum()<<\"数据项!\"<<endl; \nelse \ncout<<\"堆栈为空!\"<<endl; \n \n} \n\ntemplate<class Type> \nvoid Stack_GetTop(Stack<Type> &StackOPP) \n{ \nif(!StackOPP.ISEmpty()) \n cout<<\"栈顶元素为：\"<<StackOPP.GetTop()<<endl; \nelse \n cout<<\"堆栈为空!\"<<endl; \n} \n\ntemplate<class Type> \nvoid Stack_MakeEmpty(Stack<Type> &StackOPP) \n{ \nif(!StackOPP.ISEmpty()) \n{ \nStackOPP.MakeEmpty(); \ncout<<\"堆栈已经销毁!\"<<endl; \n} \nelse \n{ \ncout<<\"销毁失败!\"<<endl; \n} \n} \n\n\ntemplate<class Type> \nvoid StackINI(Type temp) \n{ \nStack<Type> StackOPP; \n\ndo \n{ \ncout<<\"堆栈的操作: \"<<endl \n<<\" 1) 插入堆栈\"<<endl \n<<\" 2) 出栈\"<<endl \n<<\" 3) 堆栈是否为空\"<<endl \n<<\" 4) 得栈顶数据项\"<<endl \n<<\" 5) 销毁堆栈\"<<endl \n<<\" X) 退出堆栈操作\"<<endl; \nint item; \ncin>>item; \nswitch(item) \n{ \ncase 1: Stack_Push(StackOPP); break; \ncase 2: Stack_Pop(StackOPP); break; \ncase 3: Stack_ISEmpty(StackOPP); break; \ncase 4: Stack_GetTop(StackOPP); break; \ncase 5: Stack_MakeEmpty(StackOPP); break; \n\ndefault: return ; \n} \n\n}while(true); \n\n\n} \n\n\nvoid STACK() \n{ \nint item; \ncout<<\"清选择数据类型: 1) 整型 2) 浮点型 3) 字符型 X) 退出: \"; \n\ncin>>item; \nswitch(item) \n{ \ncase 1: StackINI(INT); break; //根据不同的用户需要选择数据类型 \ncase 2: StackINI(FLOAT); break; \ncase 3: StackINI(CHAR); break; \n default: return ; break; \n} \n} \n\n\n\n/////////////////////////// \n// // \n// 队列功能函数 Queue.h // \n// // \n////////////////////////// \n\n\n\n#include\"Queue.h\" \n\nconst int INT =13; \nconst double FLOAT= 13.33; \nconst char CHAR =/a/; \n\n\n\ntemplate<class Type> \nvoid Queue_Enter(Queue<Type> &QueueOPP) \n{ \ncout<<\"请输入要插入队列的数据: \"; \nType item; \ncin>>item; \nQueueOPP.EnQueue(item); \n} \n\ntemplate<class Type> \nvoid Queue_Del(Queue<Type> &QueueOPP) \n{ \n if(!QueueOPP.ISEmpty()) \n { \n cout<<\"出队数据:\"<<QueueOPP.DelQueue()<<endl; \n } \n else \n { \n cout<<\"队列已为空!\"<<endl; \n } \n} \n\ntemplate<class Type> \nvoid Queue_ISEmpty(Queue<Type> &QueueOPP) \n{ \nif(QueueOPP.ISEmpty()) \n{ \ncout<<\"队列已空!\"<<endl; \n} \nelse \n{ \ncout<<\"队列不空!\"<<endl; \n} \n} \n\n\ntemplate<class Type> \nvoid Queue_GetFront(Queue<Type> &QueueOPP) \n{ \nif(!QueueOPP.ISEmpty()) \n{ \ncout<<\"队头元素为: \"<<QueueOPP.GetFront()<<endl; \n} \nelse \n{ \ncout<<\"队列已空!\"<<endl; \n} \n} \n\ntemplate<class Type> \nvoid Queue_MakeEmpty(Queue<Type> &QueueOPP) \n{ \nQueueOPP.MakeEmpty(); \ncout<<\"队列清空!\"<<endl; \n} \n\ntemplate<class Type> \nvoid QueueINI(Type temp) \n{ \nQueue<Type> QueueOPP; \n\ndo \n{ \ncout<<\"队列的操作: \"<<endl \n<<\" 1) 插入队列\"<<endl \n<<\" 2) 出队\"<<endl \n<<\" 3) 队列是否为空\"<<endl \n<<\" 4) 得队头数据项\"<<endl \n<<\" 5) 销毁队列\"<<endl \n<<\" X) 退出队列操作\"<<endl; \nint item; \ncin>>item; \nswitch(item) \n{ \ncase 1: Queue_Enter(QueueOPP); break; \ncase 2: Queue_Del(QueueOPP); break; \ncase 3: Queue_ISEmpty(QueueOPP); break; \ncase 4: Queue_GetFront(QueueOPP); break; \ncase 5: Queue_MakeEmpty(QueueOPP); break; \n\ndefault: return ; \n} \n\n}while(true); \n\n\n} \n\n\nvoid QUEUE() //根据不同的用户需要选择数据类型 \n{ \nint item; \ncout<<\"清选择数据类型: 1) 整型 2) 浮点型 3) 字符型 X) 退出: \"; \n\n\ncin>>item; \nswitch(item) \n{ \ncase 1: QueueINI(INT); break; \ncase 2: QueueINI(FLOAT); break; \ncase 3: QueueINI(CHAR); break; \n default: return ; break; \n} \n} \n \n-----------------------------------------------------------------------------------------------------------------\n/////////////////////////// \n// // \n// 链表 List.h // \n// // \n////////////////////////// \n\n\n#include\"list.h\" \n#include<iostream.h> \n#include<stdlib.h> \n\n\ntemplate<class type> \nvoid initlist(type &tmp) \n{ \n list<type> List; \n int n; \n\n while(true) \n { \n\n cout<<\"请选择你要对链表进行的操作 \"<<endl \n <<\"1) 在末尾插入数据\"<<endl \n <<\"2) 在任意处插入数据\"<<endl \n <<\"3) 删除数据项\"<<endl \n <<\"4) 删除整个链表\"<<endl \n <<\"5) 打印链表\"<<endl \n <<\"6) 查找数据项\"<<endl \n <<\"7) 退出\"<<endl; \n\n cout<<\"> \"; \n cin>>n; \n\n while(n<1||n>7) \n { \ncout<<\"输入有误，请从新输入!\"<<endl; \n cout<<\"> \"; \n cin>>n; \n} \n\nswitch(n) \n{ \ncase 1: list_insertend(List);break; \ncase 2: list_insert(List);break; \ncase 3: list_delnode(List);break; \ncase 4: list_makeempty(List);break; \ncase 5: list_print(List);break; \ncase 6: list_find(List);break; \ncase 7: return ;break; \n} \n\n } \n\n} \n\nvoid LIST() \n{ \nint n; \n cout<<\"请选择你要构造的链表的数据类型 1)整型，2)字符型,3)浮点型\"<<endl; \ncout<<\"> \"; \ncin>>n; \n\n while(n<1||n>3) \n { \ncout<<\"输入有误，请从新输入!\"<<endl; \n cout<<\"> \"; \n cin>>n; \n} \n\nchar t_c=/c/; \nint t_i=12; \ndouble t_f=23.3; \n\nswitch(n) \n{ \ncase 1:initlist(t_i);break; \ncase 2:initlist(t_c);break; \ncase 3:initlist(t_f);break; \n} \n} \n\ntemplate<class type> \nvoid list_insertend(list<type> &L) \n{ \ntype t; \ncout<<\"请输入插入数据: >\"; \ncin>>t; \nL.insertend(t); \n} \n\ntemplate<class type> \nvoid list_find(list<type> &L) \n{ \ntype T; \ncout<<\"请输入你要查找的数据项：> \"; \ncin>>T; \n\nint i; \nif(!(i=L.find(T))) \ncout<<\"你要查找的数据项不存在!\"<<endl; \nelse \ncout<<\"你要查找的数据项在第\"<<i<<\"个位置\"<<endl; \n} \n\ntemplate<class type> \nvoid list_insert(list<type> &L) \n{ \n\ntype t; \ncout<<\"请输入插入数据: >\"; \ncin>>t; \n\nint n; \ncout<<\"请输入插入位置: >\"; \ncin>>n; \nif(L.insert(t,n)) \ncout<<\"插入成功! 在\"<<n<<\"位置 插入\"<<t<<endl; \nelse \ncout<<\"插入失败! 插入位置不正确!\"<<endl; \n\n} \n\ntemplate<class type> \nvoid list_delnode(list<type>& L) \n{ \nint i; \n cout<<\"请输入要删除数据项的位置: >\"; \ncin>>i; \n\n\nwhile(i<1||i>L.getlen()) \n{ \n cout<<\"输入有误，可能大与链表长度,请从新输入!\"<<endl; \n cout<<\"> \"; \n cin>>i; \n} \n\nL.delnode(i); \n} \ntemplate<class type> \nvoid list_makeempty(list<type> &L) \n{ \nL.makeempty(); \n} \n\ntemplate<class type> \nvoid list_print(list<type> &L) \n{ \nif(!L.print()) \ncout<<\"链表为空!\"<<endl; \n}\n------------------------------------------------------------------------------------------------------------------------\n/////////////////////////// \n// // \n// 图功能函数 Graph.h // \n// // \n////////////////////////// \n\n\n#include\"Graph.h\" \n\ntemplate<class NameType,class DisType> \nvoid Graph_Creat(Graph<NameType,DisType> &GraphOPP) \n{ \nGraphOPP.Creat(); \n} \n\ntemplate<class NameType,class DisType> \nvoid Graph_DFS(Graph<NameType,DisType> &GraphOPP) \n{ \nGraphOPP.DFS(); \n} \n\ntemplate<class NameType,class DisType> \nvoid Graph_BFS(Graph<NameType,DisType> &GraphOPP) \n{ \nGraphOPP.BFS(); \n} \n\ntemplate<class NameType,class DisType> \nvoid Graph_PRINT(Graph<NameType,DisType> &GraphOPP) \n{ \nGraphOPP.PrintNode(); \n} \n\n\nvoid GRAPH() \n{ \nGraph<char,int> GraphOPP; \ndo \n{ \ncout<<\"图的操作: \"<<endl \n<<\" 1) 建立图\"<<endl \n<<\" 2) 图的深度优先搜索\"<<endl \n<<\" 3) 图的广度优先搜索\"<<endl \n<<\" 4) 打印图中各结点\"<<endl \n<<\" X) 退出排序操作\"<<endl; \nint item; \ncin>>item; \nswitch(item) \n{ \ncase 1: Graph_Creat(GraphOPP); break; \ncase 2: Graph_DFS(GraphOPP); break; \ncase 3: Graph_BFS(GraphOPP); break; \ncase 4: Graph_PRINT(GraphOPP); break; \ndefault: return ; \n} \n\n}while(true); \n\n\n}\n-------------------------------------------------------------------------------------------------------------------------------\nID=51210-442-8255366-13565\n\n[ 本帖最后由 freeadmin 于 2005-11-30 12:54 PM 编辑 ] |
|
免费注册
发表于 2005-10-20 23:27
