数据结构源代码(全)

/*顺序表的操作#include#includeusing namespace std;Release 13.12 rev 9501 (2013/12/25 19:25:45) gcc 4.7.1 Windows/unicode - 32 bit#define MAX_SIZE 100typedef structint *emel;int lenth;Sq;void init(Sq &l);void create(Sq &l);void trval(Sq &l);void find_value(Sq &l);void find_position(Sq &l);void insert(Sq &l);void dele(Sq &l);int main() Sq l; init(l); create(l); trval(l); find_value(l); find_position(l); insert(l); trval(l); dele(l); trval(l); return 0; void init(Sq &l) l.emel =new intMAX_SIZE; if(l.emel =NULL) coutt申请空间失败！endl; exit(1); l.lenth=0; coutt成功申请空间！该顺序表的长度目前为:l.lenthendl; void create(Sq &l) coutx; if(xMAX_SIZE) coutt你说输入的数不在范围里endl; return; int i; for(i=0;il.emeli; l.lenth=x;coutt成功赋值！endl; void trval(Sq &l) int i; coutl(; for(i=0;il.lenth;i+) coutl.emeli ; cout) 该顺序表现在的长度为：l.lenthendl; void find_value(Sq &l) int x,t=0; coutx; int i; for(i=0;il.lenth;i+) if(l.emeli=x) t=1; coutt成功找到该元素，它是顺序表的第i+1个元素！endl; if(t=0) coutt无该元素！endl; void find_position(Sq &l) int x; coutx; int i; if(xl.lenth) coutt输入的值不在范围内！endl; return; for(i=1;i=l.lenth;i+) if(i=x) coutt成功找到该元素，该值是l.emeli-1endl; void insert(Sq &l)int i,x,y;coutx;couty;if(xl.lenth)coutt输入的值不在范围内！=x;i-)l.emeli=l.emeli-1;l.emelx-1=y;l.lenth=l.lenth+1;void dele(Sq &l)int i,x;coutx;if(xl.lenth)coutt输入的值不在范围内！endl;return;for(i=x-1;i=l.lenth;i+)l.emeli=l.emeli+1;l.lenth=l.lenth-1; 成功申请空间！该顺序表的长度目前为:0 请输入你想输入元素的个数：3852 成功赋值！l(8 5 2 ) 该顺序表现在的长度为：3 请输入你要查找的值：5 成功找到该元素，它是顺序表的第2个元素！ 请输入你要查找的位置：3 成功找到该元素，该值是2 请输入你要插入的位置3 请输入你要插入的值10l(8 5 2 10 ) 该顺序表现在的长度为：4 请输入你要删除位置：3l(8 5 10 ) 该顺序表现在的长度为：3-Process exited with return value 0Press any key to continue . . .*/*#include#includetypedef struct Linkint num;struct Link *next;L;L* creat(L* head)head=(L *)malloc(sizeof(L);if(head=NULL)printf(头节点申请失败！n);exit(-1);head-next=NULL;return head;void insert(L* head)int x,i;printf(请输入你想输入数据的个数：);scanf(%d,&x);L *p,*q;p=head;for(i=0;inum);q-next=NULL;p-next=q;p=q;void print(L* head)L *p;p=head-next;while(p!=NULL)printf(值为：%dn,p-num);p=p-next;int main()L *head;head=creat(head);printf(成功创建头节点！n);insert(head);printf(成功输入数据！n);print(head);return 0;*/ /* 线性表的操作#include#includetypedef struct Linkint num;struct Link *next;L;L* creat(L* head)head=(L *)malloc(sizeof(L);if(head=NULL)printf(头节点申请失败！n);exit(-1);head-next=NULL;return head;void init(L* head)int x,i;printf(请输入你想输入数据的个数：);scanf(%d,&x);L *p,*q;p=head;for(i=0;inum);q-next=p-next;p-next=q;int print(L* head)L *p;int lenth=0;p=head-next;printf(ttL();while(p!=NULL)lenth+;printf(%d ,p-num);p=p-next;printf()n);return lenth;int insert(L *head,int lenth)printf(tt请输入你要插入的元素的位置:);int in;scanf(%d,&in);if(inlenth)printf(tt输入值不在范围内！);return -1;L *p,*q;p=head-next;q=(L *)malloc(sizeof(L);if(q=NULL)printf(新点申请失败！n);return -1;printf(tt请为新节点输入值：);scanf(%d,&q-num);int i=0;while(p!=NULL)i+;if(i=in-1)q-next=p-next;p-next=q;p=p-next;lenth+;return lenth;int dele(L *head,int lenth)printf(tt请输入你要删除的元素的位置:);int out;scanf(%d,&out);if(outlenth)printf(tt输入值不在范围内！);return -1;L *p,*q;p=head-next;q=head;int i=0;while(p!=NULL)i+;if(i=out)q-next=p-next;q=p;p=p-next;lenth-;return lenth;void find(L *head,int lenth)printf(tt请输入你要查找的元素的位置:);int finder;scanf(%d,&finder);if(finderlenth)printf(tt输入值不在范围内！);return ;L *p;p=head-next;int i=0;while(p!=NULL)i+;if(i=finder)printf(tt你要找的该位置所对应的值为：%dn,p-num);p=p-next;int main()L *head;head=creat(head);printf(成功创建头节点！n);init(head);printf(成功输入数据！n);int len;len=print(head);printf(tt该线性表的长度为:%dn,len);len=insert(head,len);len=print(head);printf(tt插入后线性表的长度为:%dn,len);len=dele(head,len);len=print(head);printf(tt删除后该线性表的长度为:%dn,len);find(head,len);return 0;*/*顺序表的合并#includeusing namespace std;struct LAint *pa;int lenth;struct LBint *pb;int lenth;struct LCint *pc;int lenth;void mergelist(LA la,LB lb,LC &lc);int main()int x,y;LA la;LB lb;coutxy;la.pa =new int(sizeof(int)*x);lb.pb =new int(sizeof(int)*y);int i;for(i=0;ix;i+)coutla.pai;coutendl;la.lenth=x;for(i=0;iy;i+)coutlb.pbi;lb.lenth=y;coutLA(;for(i=0;ix;i+)coutla.pai ;cout)endl;coutLB(;for(i=0;iy;i+)coutlb.pbi ;cout)endl;LC lc;mergelist(la,lb,lc);return 0;void mergelist(LA la,LB lb,LC &lc)lc.lenth=la.lenth+lb.lenth;lc.pc=new int(sizeof(int)*lc.lenth);int *pa=la.pa,*pb=lb.pb,*pc=lc.pc;int *pa_last=la.pa+la.lenth-1;int *pb_last=lb.pb+lb.lenth-1;while(pa=pa_last & pb=pb_last)if(*pa = *pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pb=pb_last)*pc+=*pb+;coutLC(;int i=0;for(i=0;ilc.lenth;i+)coutlc.pci ;cout)endl;*/栈/*#includeusing namespace std;#include#define MAXSIZE 100typedef structint *base;int *top;int stacksize;Sqstack;int Initstack(Sqstack &s);void Push(Sqstack &s,int e);void StackTraverse(Sqstack &s);void Gettop(Sqstack &s);void Pop(Sqstack &s);int main()Sqstack s;Initstack(s);couttt初始化栈成功！endl;Push(s,2);couttt2入栈成功！endl;Push(s,4);couttt4入栈成功！endl;Push(s,6);couttt6入栈成功！endl;Push(s,8);couttt8入栈成功！endl;coutn由栈底至栈顶的元素为：;StackTraverse(s);Gettop(s);Pop(s);Gettop(s);return 0;int Initstack(Sqstack &s)s.base=new intMAXSIZE;if(s.base=NULL)exit(1);s.top=s.base;s.stacksize=MAXSIZE;void Push(Sqstack &s,int e)if(s.top-s.base=s.stacksize)exit(1);*s.top+=e;void StackTraverse(Sqstack &s)int *p=s.base,i=0;while(ps.top)i+;cout*p+ ;couttt栈的长度是iendl;void Gettop(Sqstack &s)if(s.base=s.top)exit(1);cout栈顶元素是：*(s.top-1)endl;void Pop(Sqstack &s)if(s.top=s.base)exit(1);cout出栈的第一个元素是:;cout*-s.top endl;*/队列例题：/*#include#includeusing namespace std;#define MAXQSIZE 100typedef structint *base;int front;int rear;SqQueue;int InitQueue(SqQueue &q);int EnQueue(SqQueue &q,int x);int DeQueue(SqQueue &q);int main()SqQueue q;InitQueue(q);EnQueue(q,1);EnQueue(q,3);EnQueue(q,5);EnQueue(q,7);DeQueue(q);DeQueue(q);DeQueue(q);DeQueue(q);return 0;int InitQueue(SqQueue &q)q.base=new intMAXQSIZE;if(q.base=NULL)exit(1);q.front=0;q.rear=0;return 0;int EnQueue(SqQueue &q,int x)if(q.rear+1)%MAXQSIZE=q.front)exit(0);q.baseq.rear=x;q.rear=(q.rear+1)%MAXQSIZE;return 0;int DeQueue(SqQueue &q)if(q.front=q.rear)exit(0);int x=q.baseq.front;q.front=(q.front+1)%MAXQSIZE;coutxendl;*/*#include#includeusing namespace std;typedef struct Qnode int date; struct Qnode *next;Qnode,*Queueptr; typedef struct Queueptr front; /队头指针 Queueptr rear; /队尾指针LinkQueue;int InitQueue(LinkQueue &Q);void EnQueue(LinkQueue &Q,int e);void TrvalQueue(LinkQueue Q);void DeQueue(LinkQueue &Q);int main() LinkQueue Q; InitQueue(Q); EnQueue(Q,1); coutt元素1入队成功！endl; EnQueue(Q,3); coutt元素3入队成功！endl; EnQueue(Q,5); coutt元素5入队成功！endl; EnQueue(Q,7); coutt元素7入队成功！endl; coutt队列的元素分别是：endl; TrvalQueue(Q); coutt第一个出队的元素是：endl; DeQueue(Q); coutnext=NULL; return 0;void EnQueue(LinkQueue &Q,int e) Qnode *p=new Qnode; if(!p) exit(1); p-date=e; p-next=NULL; Q.rear-next=p; /连接 Q.rear=p; /修改队尾指针void TrvalQueue(LinkQueue Q) Qnode *p=Q.front-next;/队头元素 while(Q.front!=Q.rear) cout datenext; coutnext; couttdatenext=p-next; if(Q.rear=p) Q.rear=Q.front; delete p; */*/表达式求值#include#include#includeusing namespace std;#define MAXSIZE 100typedef struct char *base; char *top; char num;OPND; /数据栈typedef struct char *base; char *top; char c;OPTR; /符号栈int Initstack(OPND &op_n,OPTR &op_t);void Pushstack(OPND &op_n,char ch);void Pushstack(OPTR &op_t,char ch);char Popstack(OPND &op_n,char ch);char Popstack(OPTR &op_t,char ch);char Gettop(OPTR op_t);char Gettop(OPND op_n);int In(char ch);char Precede(char x,char y);char operate(char z,char x,char y);int main() OPND op_n; OPTR op_t; Initstack(op_n,op_t); Pushstack(op_t,#); char ch; char p; cinch; while(ch!=# | Gettop(op_t)!=#) if(!In(ch) Pushstack(op_n,ch); cinch; else switch( Precede(Gettop(op_t),ch) ) case ch; break; case : char x,y,z; x=Popstack(op_t,x); y=Popstack(op_n,y); z=Popstack(op_n,z); Pushstack(op_n,operate(z,x,y); break; case =: p=Popstack(op_t,p); cinch; break; coutt表达式结果是：Gettop(op_n)endl; return 0;int Initstack(OPND &op_n,OPTR &op_t) op_n.base=new charMAXSIZE; op_t.base=new charMAXSIZE; if(op_n.base=NULL) | (op_t.base=NULL) exit(1); op_n.top=op_n.base; op_t.top=op_t.base; op_n.num=MAXSIZE; op_t.c=MAXSIZE; return 0;void Pushstack(OPND &op_n,char ch) if(op_n.top-op_n.base=op_n.num) return; *op_n.top+=ch;coutch 入数字栈endl;void Pushstack(OPTR &op_t,char ch) if(op_t.top-op_t.base=op_t.c) return; *op_t.top+=ch;coutch 入操作符endl;char Popstack(OPND &op_n,char ch) if(op_n.top=op_n.base) exit(1); ch=*-op_n.top;coutch 出数字栈endl; return ch;char Popstack(OPTR &op_t,char ch) if(op_t.top=op_t.base) exit(1); ch=*-op_t.top;coutch 出字符栈endl; return ch;char Gettop(OPTR op_t) char x; if(op_t.top=op_t.base) exit(1); x=*(op_t.top-1);cout得到操作符栈顶xendl; return x;char Gettop(OPND op_n) char x; if(op_n.top=op_n.base) exit(1); x=*(op_n.top-1);cout得到操作数栈顶x; else return ; if(x=*|x=/) if(y=() return ; if(x=() if(y=) return =; else if(y=+|y=-|y=*|y=/|y=() return ; if(x=#) if(y=#) return =; else if(y!=) return ; char operate(char z,char x,char y) if(x=+) return (z-0) + (y-0)+48; if(x=-) return (z-0) - (y-0)+48; if(x=*) return (z-0)* (y-0)+48; if(x=/) return (z-0)/ (y-0)+48; */*#includeusing namespace std;int main()char a10;char *b10;char *c10;return 0;*/*#includeusing namespace std;char f(char x,char y) return (x-0) * (y-0)+48;int main() char a=3,b=5; char p=f(a,b); coutpendl; return 0;*/数列出队/*#include#includeusing namespace std;typedef struct Qnode int num; struct Qnode *next;Qnode,*Queueptr;typedef struct Queueptr front; Queueptr rear;LinkQueue;int InitQueue(LinkQueue &Q);void EnQueue(LinkQueue &Q,int x);int DeQueue(LinkQueue &Q,int p);int main() LinkQueue Q; InitQueue(Q); int x,i,y,num=0,e; coutx; for(i=1;i=x;i+) EnQueue(Q,i); couty; while(1) for(i=0;iy;i+) if(i!=y-1) e=DeQueue(Q,e); EnQueue(Q,e); else DeQueue(Q,e); num+; if(num=x-1) break; e=DeQueue(Q,e); cout最后剩下的是：enext=NULL;void EnQueue(LinkQueue &Q,int x) Qnode *p=new Qnode; if(!p) exit(1); p-num=x; p-next=NULL; Q.rear-next=p; Q.rear=p;int DeQueue(LinkQueue &Q,int e) Qnode *p; if(Q.rear=Q.front) exit(0); p=Q.front-next; e=p-num; Q.front-next=p-next; if(Q.rear=p) Q.front=Q.rear; delete p; return e;*/*二叉树#include#includeusing namespace std;typedef struct BiTNode char date; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void CreateBiTree(BiTree &T);int Depth(BiTree T);int NodeCount(BiTree T);int LeavesNodeCount(BiTree T);int PreOrderTraverse(BiTree T);int InOrderTraverse(BiTree T);int PostOrderTraverse(BiTree T);int main() BiTree T; CreateBiTree(T); cout二叉树的深度为：Depth(T)endl; cout二叉树中结点个数为：NodeCount(T)endl; cout二叉树中叶子结点个数为：LeavesNodeCount(T)endl; cout先序遍历：;PreOrderTraverse(T);coutn中序遍历：;InOrderTraverse(T);coutn后序遍历：;PostOrderTraverse(T);coutendl; return 0;void CreateBiTree(BiTree &T) coutch; if(ch=#) T=NULL; else T =new BiTNode;