C++一些基本算法代码.docx

272010年11月29号开始实习#includeusing namespace std;struct nodeint data;node *next;void main()node *p1,*p2,*p3,*p4,*p5,*p;p1=new node();p2=new node();p3=new node();p4=new node();p5=new node();p1-data=1;p2-data=2;p3-data=3;p4-data=4;p5-data=5;p1-next=p2;p2-next=p3;p3-next=p4;p4-next=p5;p5-next=NULL;coutdata:dataendl;coutdata:dataendl;coutdata:dataendl;coutdata:dataendl;coutdata:dataendl;coutp2=p3endl;p2=p3;coutdata:dataendl;coutnext-data:next-dataendl;coutnext-next-data:next-next-dataendl; /指针与指针之间的指向是按内存地址的指向来寻址的，与指针变量之间没/有太大的联系文档2（平衡二叉树）#include#include#include#include#define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)#define LH+1#define EH0#define RH-1typedef int KeyType;typedef structint key; /关键字域ElemType;typedef struct BSTNode ElemType data; int bf; /结点的平衡因子 struct BSTNode *lchild,*rchild; /左右孩子指针BSTNode,*BSTree;void InitBSTree(BSTree &T)T=NULL;void R_Rotate(BSTree &p) BSTNode *lc; lc=p-lchild; /lc指向的*p的左子树根结点 p-lchild=lc-rchild; /lc的右子树挂接为*p的左子树 lc-rchild=p; p=lc; /p指新的得根结点/R_Rotatevoid L_Rotate(BSTree &p) BSTNode *rc; rc=p-rchild; /lc指向的*p的右子树根结点 p-rchild=rc-lchild; /lc的左子树挂接为*p的右子树 rc-lchild=p; p=rc; /p指新的根结点/L_Rotatevoid LeftBalance(BSTree &T) BSTNode *lc,*rd; lc=T-lchild; switch(lc-bf) case LH: T-bf=lc-bf=EH; R_Rotate(T); break; case RH: rd=lc-rchild; switch(rd-bf) case LH: T-bf=RH; lc-bf=EH; break; case EH: T-bf=lc-bf=EH; break; case RH: T-bf=EH; lc-bf=LH; break; /switch(rd-bf) rd-bf=EH; L_Rotate(T-lchild); R_Rotate(T); /switch(lc-bf)/LeftBalancevoid RightBalance(BSTree &T) BSTNode *lc,*ld; lc=T-rchild; switch(lc-bf) case LH: ld=lc-lchild; switch(ld-bf) case LH: T-bf=EH; lc-bf=RH; break; case EH: T-bf=lc-bf=EH; break; case RH: T-bf=LH; lc-bf=EH; break; /switch(rd-bf) ld-bf=EH; R_Rotate(T-rchild); L_Rotate(T); case RH: T-bf=lc-bf=EH; L_Rotate(T); break; /switch(lc-bf)/RightBalanceint InsertAVL(BSTree &T,ElemType e,bool &taller) if(!T) T=(BSTree)malloc(sizeof(BSTNode); T-data=e; T-lchild=T-rchild=NULL; T-bf=EH; taller=true; else if(EQ(e.key,T-data.key) taller=false; coutThe key e.key is existed.data.key) if(!InsertAVL(T-lchild,e,taller) / cout未插入。bf) case LH: LeftBalance(T); taller=false; break; case EH: T-bf=LH; taller=true; break; case RH: T-bf=EH; taller=false; break; /switch(T-bf) /if else if(!InsertAVL(T-rchild,e,taller) / cout未插入。bf) case LH: T-bf=EH; taller=false; break; case EH: T-bf=RH; taller=true; break; case RH: RightBalance(T); taller=false; break; /switch(T-bf) /else /else return 1;/InsertAVLvoid Print_BSTTree(BSTree T,int i)/i表示结点所在的层次，初始应该为0 if(T) if(T-rchild) Print_BSTTree(T-rchild,i+1); for(int j=1;j=i;j+) cout ; coutdata.keylchild) Print_BSTTree(T-lchild,i+1); int main()BSTree T;ElemType e; InitBSTree(T); bool tall=false; bool choice=true; char y; while(choice) coute.key; InsertAVL(T,e,tall); Print_BSTTree(T,0); couty; if(y=Y|y=y) choice=true; elsechoice=false; return 0; 文档三(引用 的举例)#includeusing namespace std;void swap(int &a,int &b)int temp;temp=a;a=b;b=temp;void swap2(int a,int b)int temp;temp=a;a=b;b=temp;void main()int i=9;int j=12;swap2(i,j);couti=i j=jendl;swap(i,j);couti=i j=jendl;栈试存储#includeusing namespace std;#define maxsize 20class stackpublic :stack()top=-1;int GetTop() return top; void Input(int x) if(top=maxsize-1) throw stack is full ; data+top=x; /input() bool Output() if(top=-1) throw stack is Null; return false; else coutdatatop- ; return true; /output();private:int datamaxsize;int top;/class stackvoid main()stack st;int top;for(int i=0;i10;i+)st.Input(i);top=st.GetTop();if(top=-1)coutstack is emputy ;return ;for(int j=0;j=top;j+)st.Output();栈的链式存储#includeusing namespace std;struct node/用于保存节点的数据信息int data;/数据node *next;/用于保存下一个节点的信息;class LianStack/声明一个类public : LianStack()/构造函数 top=NULL;/初始化节点为空，说明该栈是空栈 void InPutStack(int x)/入栈操作node *s;/生成一个节点，这个节点的下一个指针指向前一个节点。s=new node();s-data=x;s-next=top;top=s; void OutPut()/出栈函数 if(top=NULL)coutstack is emputy !endl;/当栈是空的时候是输出栈为空return;else /栈不为空时出栈 node *p;p=top;coutdatanext;delete p; private:node *top; /定义一个头指针;void main() LianStack lianstack; int a; char select; do/入栈 couta;lianstack.InPutStack(a);coutselect; /出栈 while(select=y); coutendl; char output=y; while(output=y) lianstack.OutPut();coutoutput; coutendl;队列的顺序存储#includeusing namespace std;#define maxsize 10 /队列的长度class Queuepublic :Queue() /构造函数 front=rear=0; /初始时队列是一个空的队列int GetRear()/用于获取指向队尾的变量return rear;/GetRear()int GetFront()/获取队前序号 return front;/int GetFront() void Enqueue(int x)/入队操作 if(rear+1)%maxsize=front)/如果队满时输出队满coutqueue is full endl;return ;else/入队rear=(rear+1)%maxsize;datarear=x; / void Enqueue()void DeleteQueue()/出队操作 if(rear=front)/如果队为空coutthe queue is emputy !endl;return ;elsecoutdata(front+1)%maxsizeendl;/队为非空情况front=(front+1)%maxsize; /DeleteQueue()private:int datamaxsize;int front;int rear;void main()Queue queue;int data;/入队for(int i=0;i10;i+) coutdata;queue.Enqueue(data);/出队for(int j=0;j10;j+)queue.DeleteQueue();队列的链式存储结构#includeusing namespace std;struct node/节点的定义 int data;node *next;class Queuepublic:Queue()/构造函数，用于设置头指针与尾指针为空node * s;s=new node();s-next=NULL;front=rear=s;/Queue() node * GetFront()/用于获取指向头部的指针 return front; void Enqueue(int x)/入队操作函数，x为要入队的数据。node *s; /生成一个节点，将x的值保存到里面，然后使rear指向该节点。s=new node();s-data=x;s-next=NULL;rear-next=s;rear=s;/Enqueue() void DeleQueue()/出队操作，用于将头指针指向的下一个节点出队。 if(rear=front)/队列为空的情况coutthis queue is emputy !next=rear) /队列长度为1的情况。coutdata next;coutdata;coutendl; /Delequeue()private:node *front;node *rear;void main()Queue queue;int data;/入队操作for(int i=0;i10;i+)coutdata;/输入要入队的数据queue.Enqueue(data);/调用入队函数/出队操作for(int j=0;j=10;j+) /队长为十queue.DeleQueue();/调用出队函数操作图的顺序存储#includeusing namespace std;#define maxsize 30int visitedmaxsize;class Graphpublic:Graph()num_sides=0;num_dot=0;for(int i=0;imaxsize;i+)visitedi=0;/构造函数void InitGraphDot()/初始化函数 coutdotnum_dot+;/InitGraph();void InitSides()/初始化边的信息for(int i=0;inum_dot;i+)for(int j=0;jnum_dot;j+)sidesij=0;coutnum_sides;int m,n;for(int a=0;anum_sides;a+)coutm; coutmn;sidesmn=1;sidesnm=1;/InitSides();void PrintGraphdot()/输出接点数据 for(int i=0;inum_dot;i+)couti-doti endl;/InitSides();/PrintGraphdot()void ScanGraph(int x)coutdotx ; visitedx=1;for(int i=0;inum_dot;i+)if(sidesxi=1 & visitedi=0)ScanGraph(i);int GetDotnum()return num_dot;/GetDotnum（）private :int dotmaxsize;int sidesmaxsizemaxsize;int num_sides;int num_dot;void main()Graph gh;int n;/用来设定要输入的顶点的个数coutn;for(int i=0;in;i+)gh.InitGraphDot();coutendl; gh.InitSides();cout输出所有的节点数据：endl;gh.PrintGraphdot();cout深度优先遍历：;gh.ScanGraph(2);链表的基本操作（添加，查找，删除）#includeusing namespace std;struct Node/节点结构体int data;Node *next;class LianBiaopublic:LianBiao()/构造函数root=new Node();root-next=NULL;Node * GetRoot()return root;/GetRoot()void InitLianBiao(int x) /插入节点Node *s;s=new Node();s-data=x; s-next=root-next;root-next=s;voidScanLianBiao(Node *root)/输出所有的节点 Node *p; p=root-next; while(p) coutdatanext; /while()/ScanLianBiao()void FindByseat(int x)/查找第x个节点Node *p;p=root-next;int j=1;while(p & jnext;j+;if(!p)cout查找失败，没有你要查找的位置endl;elsecoutdatanext;int j=1;while(p & p-data !=x)p=p-next;j+;if(!p)cout没有你要查找的数据节点！endl;elsecout你查找的节点是第jdata=x;s-next=root-next;root-next=s;/AddNode()void DeleNodeBySeat(int x)/通过位置删除节点Node *p;p=root-next;Node *q;int j=1;while(p & jnext; j+;/while()if(p-next)q=p-next;p-next=q-next;cout你所要删除第j个节点的值是;coutdataendl; delete q;elsecout查找失败next;q=p-next;if(!p)cout该链表为空data=x)cout删除了节点：data;delete p;return ;elsewhile(q & q-data !=x) p=q;q=q-next;if(q)cout删除了节点：datanext=q-next;delete q;elsecout没有你要删除的节点数据！endl;/DeleNodeByvalue(int x)private: Node *root;void main() int select;LianBiao lb;Node *root;for(int i=0;i10;i+)/向链表中插入十个数据lb.InitLianBiao(i);coutendl;root=lb.GetRoot();/获取根节点的指针。lb.ScanLianBiao(root);/输出所有节点数据lb.FindByseat(2);/查找第2个节点，并输出该节点的值lb.FindByseat(6);/查找第6个节点的值是多少。lb.FindByValue(5);/查找值为12的节点的位置lb.FindByValue(44);lb.DeleNodeBySeat(4);/删除第四个节点lb.ScanLianBiao(root);coutendl;lb.AddPreNode(45);/将45添加到链表中。lb.ScanLianBiao(root);lb.DeleNodeByValue(8);/删除节点为8的节点lb.ScanLianBiao(root);lb.DeleNodeByValue(1);coutendl;图的存储操作（邻接表）#includeusing namespace std;#define maxsize 20int vistedmaxsize;struct SidesNode/定义边表结构体public :int num;SidesNode *next;/SidesNode()struct DotNode/顶点表结构体public :int shuju; SidesNode *first;/DotNode()class Graphpublic :Graph()/构造函数 numofdot=0; numofsides=0; for(int i=0;imaxsize;i+) datai.first=NULL; /for/Graph()void InitGraph()/初始化图的数据信息int m;/节点数据的接收coutnumofdotnumofsides;for(int i=0;inumofdot;i+)coutm;datai.shuju=m;datai.first=NULL;/for()cout节点数据输入完毕！endl;int v1,v2;SidesNode *s;for(int j=0;jnumofsides;j+) /依次输入每一条边的信息，并在相应的位置处插入。coutv1;coutendl;coutv1v2;s=new SidesNode();s-num=v2;s-next=datav1.first;datav1.first=s; /将节点添加到表头的头结点处/for(int j=0;jnumofsides;j+)cout边的输入完毕！endl;/InitGraph()void AddNodeAndSides()/增加节点及边 int v1,v2;/用于接收输入的边的信息SidesNode *s;int node_data,cout_sides;coutnode_data;datanumofdot.shuju=node_data;datanumofdot.first=NULL;numofdot+;coutcout_sides;for(int i=0;icout_sides;i+)coutv1;coutv1v2;s=new SidesNode();s-num=v2;s-next=datav1.first;datav1.first=s;/for()/AddNodeAndSides()void DeleteSides()/删除边函数int i,j;couti;cout终点：j; SidesNode *p,*q;p=datai.first;q=p-next; if(p=NULL)cout你输入的边不存在！num=j)datai.first=p-next;delete p;return ;/if elsewhile(q & q-num != j)p=q;q=q-next;/while() if(q) cout删除边成功！next=q-next; delete q; else cout你输入的边部存在！endl; /else coutdelete successendl;/DeleteSides（）void DeleteNode(int x)/删除节点函数 int i,j;for(i=0;inumofdot;i+) /用于查找用户输入的数据节点值是否存在。if(datai.shuju=x)break;/forif(i=numofdot) /如果没有在图中找到用户输入的数据，则整个函数返回。cout没有你要删除的节点值！endl;return ;/ifcoutiendl;for(j=0;jnext;if(p-num=x)dataj.first=p-next;delete p;continue;/if(p-num=x)elsewhile(q & q-nu