数据结构源代码(全)107页

1、/*顺序表的操作#include<iostream>#include<stdlib.h>using 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 &am

2、p;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) cout<<"t申请空间失败！&q

3、uot;<<endl; exit(1); l.lenth=0; cout<<"t成功申请空间！该顺序表的长度目前为:"<<l.lenth<<endl; void create(Sq &l) cout<<"t请输入你想输入元素的个数：" int x; cin>>x; if(x<1)&&(x>MAX_SIZE) cout<<"t你说输入的数不在范围里"<<endl; return; int i; for(i=

4、0;i<x;i+) cin>>l.emeli; l.lenth=x;cout<<"t成功赋值！"<<endl; void trval(Sq &l) int i; cout<<"l(" for(i=0;i<l.lenth;i+) cout<<l.emeli<<" " cout<<")"<<" 该顺序表现在的长度为："<<l.lenth<<endl; void

5、find_value(Sq &l) int x,t=0; cout<<"t请输入你要查找的值：" cin>>x; int i; for(i=0;i<l.lenth;i+) if(l.emeli=x) t=1; cout<<"t成功找到该元素，它是顺序表的第"<<i+1<<"个元素！"<<endl; if(t=0) cout<<"t无该元素！"<<endl; void find_position(Sq &am

6、p;l) int x; cout<<"t请输入你要查找的位置：" cin>>x; int i; if(x<1)|(x>l.lenth) cout<<"t输入的值不在范围内！"<<endl; return; for(i=1;i<=l.lenth;i+) if(i=x) cout<<"t成功找到该元素，该值是"<<l.emeli-1<<endl; void insert(Sq &l)int i,x,y;cout<<&q

7、uot;t请输入你要插入的位置"cin>>x;cout<<"t请输入你要插入的值"cin>>y;if(x<1)|(x>l.lenth)cout<<"t输入的值不在范围内！"<<endl;return;if(x=l.lenth)l.emell.lenth=y;l.lenth=l.lenth+1;return;for(i=l.lenth;i>=x;i-)l.emeli=l.emeli-1;l.emelx-1=y;l.lenth=l.lenth+1;void dele(Sq

8、 &l)int i,x;cout<<"t请输入你要删除位置："cin>>x;if(x<1)|(x>l.lenth)cout<<"t输入的值不在范围内！"<<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 成功找到该元素，它是顺序表的

9、第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<stdio.h>#include<stdlib.h>typedef struct Linkint num;struct Link *next;L;L* creat(L* head)head

10、=(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;i<x;i+)q=(L *)malloc(sizeof(L);if(q=NULL)printf("新点申请失败！n");exit(-1

11、);printf("请输入值：");scanf("%d",&q->num);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("成功输入数据！

12、n");print(head);return 0;*/ /* 线性表的操作#include<stdio.h>#include<stdlib.h>typedef 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(&quo

13、t;请输入你想输入数据的个数：");scanf("%d",&x);L *p,*q;p=head;for(i=0;i<x;i+)q=(L *)malloc(sizeof(L);if(q=NULL)printf("新点申请失败！n");exit(-1);printf("请输入值：");scanf("%d",&q->num);q->next=p->next;p->next=q;int print(L* head)L *p;int lenth=0;p=head->

14、;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(in<1 | in>lenth)printf("tt输入值不在范围内！");retur

15、n -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

16、)printf("tt请输入你要删除的元素的位置:");int out;scanf("%d",&out);if(out<1 | out>lenth)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)pr

17、intf("tt请输入你要查找的元素的位置:");int finder;scanf("%d",&finder);if(finder<1 | finder>lenth)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=cre

18、at(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);fin

19、d(head,len);return 0;*/*顺序表的合并#include<iostream>using 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;cout<<"tt请给线性表LA和LB指定长度："cin>>x>>y;la.pa =new in

20、t(sizeof(int)*x);lb.pb =new int(sizeof(int)*y);int i;for(i=0;i<x;i+)cout<<"请输入表LA的值:"cin>>la.pai;cout<<endl;la.lenth=x;for(i=0;i<y;i+)cout<<"请输入表LB的值:"cin>>lb.pbi;lb.lenth=y;cout<<"LA("for(i=0;i<x;i+)cout<<la.pai<<

21、;" "cout<<")"<<endl;cout<<"LB("for(i=0;i<y;i+)cout<<lb.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)*

22、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+;cout<<"LC("int i=0;for(i=0;i&l

23、t;lc.lenth;i+)cout<<lc.pci<<" "cout<<")"<<endl;*/栈/*#include<iostream>using namespace std;#include<stdlib.h>#define MAXSIZE 100typedef structint *base;int *top;int stacksize;Sqstack;int Initstack(Sqstack &s);void Push(Sqstack &s,int e);

24、void StackTraverse(Sqstack &s);void Gettop(Sqstack &s);void Pop(Sqstack &s);int main()Sqstack s;Initstack(s);cout<<"tt初始化栈成功！"<<endl;Push(s,2);cout<<"tt2入栈成功！"<<endl;Push(s,4);cout<<"tt4入栈成功！"<<endl;Push(s,6);cout<<&

25、quot;tt6入栈成功！"<<endl;Push(s,8);cout<<"tt8入栈成功！"<<endl;cout<<"n由栈底至栈顶的元素为："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

26、 &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(p<s.top)i+;cout<<*p+<<" "cout<<"tt栈的长度是"<<i<<endl;void Gettop(Sqstack &s)if(s.base=s.top)exit(1);cout<<"栈顶元素是：&quo

27、t;<<*(s.top-1)<<endl;void Pop(Sqstack &s)if(s.top=s.base)exit(1);cout<<"出栈的第一个元素是:"cout<<*-s.top<<" "<<endl;*/队列例题：/*#include<iostream>#include<stdlib.h>using namespace std;#define MAXQSIZE 100typedef structint *base;int front;i

28、nt 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

29、(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;cout<<x<<endl;*

30、/*#include<iostream>#include<stdlib.h>using 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

31、);void DeQueue(LinkQueue &Q);int main() LinkQueue Q; InitQueue(Q); EnQueue(Q,1); cout<<"t元素1入队成功！"<<endl; EnQueue(Q,3); cout<<"t元素3入队成功！"<<endl; EnQueue(Q,5); cout<<"t元素5入队成功！"<<endl; EnQueue(Q,7); cout<<"t元素7入队成功！"

32、;<<endl; cout<<"t队列的元素分别是："<<endl; TrvalQueue(Q); cout<<"t第一个出队的元素是："<<endl; DeQueue(Q); cout<<"nt第一个元素出队完成之后队列中从队头至队尾的元素为：" TrvalQueue(Q); return 0;int InitQueue(LinkQueue &Q) Q.rear=new Qnode; Q.front=Q.rear; if(Q.front=NULL) ex

33、it(0); Q.front->next=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 <<p->date<<&q

34、uot; " Q.front=p; p=p->next; cout<<endl;void DeQueue(LinkQueue &Q) if(Q.front=Q.rear) return; Qnode *p=Q.front->next; cout<<"t"<<p->date<<endl; Q.front->next=p->next; if(Q.rear=p) Q.rear=Q.front; delete p; */*/表达式求值#include<iostream>#in

35、clude<stdlib.h>#include<stdio.h>using 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 &

36、amp;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,'#'

37、); char ch; char p; cin>>ch; while(ch!='#' | Gettop(op_t)!='#') if(!In(ch) Pushstack(op_n,ch); cin>>ch; else switch( Precede(Gettop(op_t),ch) ) case '<': Pushstack(op_t,ch); cin>>ch; break; case '>': char x,y,z; x=Popstack(op_t,x); y=Popstack(o

38、p_n,y); z=Popstack(op_n,z); Pushstack(op_n,operate(z,x,y); break; case '=': p=Popstack(op_t,p); cin>>ch; break; cout<<"t表达式结果是："<<Gettop(op_n)<<endl; return 0;int Initstack(OPND &op_n,OPTR &op_t) op_n.base=new charMAXSIZE; op_t.base=new charMAXSIZE;

39、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;cout<<ch<<" 入数字栈"<<endl;void Pushstack(OPTR &

40、op_t,char ch) if(op_t.top-op_t.base=op_t.c) return; *op_t.top+=ch;cout<<ch<<" 入操作符"<<endl;char Popstack(OPND &op_n,char ch) if(op_n.top=op_n.base) exit(1); ch=*-op_n.top;cout<<ch<<" 出数字栈"<<endl; return ch;char Popstack(OPTR &op_t,char c

41、h) if(op_t.top=op_t.base) exit(1); ch=*-op_t.top;cout<<ch<<" 出字符栈"<<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<<"得到操作符栈顶"<<x<<endl; return x;char Gettop(OPND op_n) char x; if(op_n.top=op_

42、n.base) exit(1); x=*(op_n.top-1);cout<<"得到操作数栈顶"<<x<<endl; return x;int In(char ch) if(ch='+'|ch='-'|ch='*'|ch='/'|ch='('|ch=')'|ch='#') return 1; else return 0; char Precede(char x,char y) if(x='+' | x='

43、-') if(y='+' | y='-' | y=')' | y='#') return '>' else return '<' if(x='*'|x='/') if(y='(') return '<' else return '>' if(x='(') if(y=')') return '=' else if(y='+'|y

44、='-'|y='*'|y='/'|y='(') return '<' if(x=')') if(y!='(') return '>' if(x='#') if(y='#') return '=' else if(y!=')') return '<' char operate(char z,char x,char y) if(x='+') return (z

45、-'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; */*#include<iostream>using namespace std;int main()char a10;char *b10;c

46、har *c10;return 0;*/*#include<iostream>using 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); cout<<p<<endl; return 0;*/数列出队/*#include<iostream>#include<stdlib.h>using namespace st

47、d;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; cout<<&quo

48、t;请输入总人数:" cin>>x; for(i=1;i<=x;i+) EnQueue(Q,i); cout<<"请输入第几个数淘汰:" cin>>y; while(1) for(i=0;i<y;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<<"最后剩下的是："<<e<<endl; retu

49、rn 0;int InitQueue(LinkQueue &Q) Q.front=new Qnode; Q.rear=Q.front; if(Q.front=NULL) exit(1); Q.front->next=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(

50、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<iostream>#include<stdlib.h>using namespace std;typedef struct BiTNode char date; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void Creat

51、eBiTree(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&l