数据结构真题及实验报告.pdf

《数据结构真题及实验报告.pdf》由会员分享，可在线阅读，更多相关《数据结构真题及实验报告.pdf（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、#include#include#include#include#includeusing namespace std;typedef struct city(string name;double locatex;double locatey;city*next;city,*citynode;void InitCity(citynode Link)(Link-next=NULL;)void insert(citynode L,double lx,double ly,string cname)(citynode temp=new city;temp-name=cname;temp-locatex

2、=lx;temp-locatey=ly;temp-next=L-next;L-next=temp;)void create(citynode L)(string cname;double lx,ly,i=l;docoutvvn请输入城市名称：”；cincname;coutn请输入经度：cinlx;coutvvn请输入纬度：”；cinly;insert(L,lx,ly,cname);system(uclsH);coulnext!=NULL)(x 1 i=L-next-locatex;y 1 i=L-next-locatey;namel i=L-next-name;count+;i+；if(L-n

3、ext-name=coname)(coutvv”它的经度：,L-next-locatextt 纬度：nL-next-locateyendl;swi=l;x=L-next-locatex;y=L-next-locatey;)L-next=L-next-next;)if(swi=l)coutvv”请输入距离：u;cind2;coutvv它到距离小于”vd2”的城市有：endl;for(i=0;i=count;i+)(if(coname!=namel i)(d=(x-x 1 i)*(x-x 1 ij)+(y-y li)*(y-y lij);d=sqrt(d);if(dd2)coutnamel ien

4、dl;if(swi=0)coutMDo not exit this city!Mendl;coutW Wuendl;system(upause);1-2#include#include#include#include#includeusing namespace std;typedef struct Joseph(int code;Joseph*next;int number;Joseph*rear;Joseph,*Josephnode;void insert(Josephnode head,int i)(Josephnode temp=new Joseph;if(temp=NULL)cout

5、vv”链表申请不到空间!”code;temp-number=i;head-rear-next=temp;head-rear=temp;)int create(Josephnode head)(int n,i;coutvv”请输入人数 n:endl;cinn;for(i=l;irear-next=head-next;)return n;)void sequenceout(Josephnode head,int n)(int N=l+rand()%20;coutHM 为随机数vvNvvendl;coutvv”输出的顺序是：endl;Josephnode pre=headxurrent=head-n

6、ext,r;while(n!=l)int j=l;while(jnext;j+4-;)coutvvcurrent-numbervvtt”;N=current-code;n-；pre-next=current-next;r=current;current=current-next;free(r);coutcurrent-number;void main()(Josephnode head=new Joseph;head-next=NULL;head-rear=head;int n;n=create(head);sequenceout(head,n);coutn 谢谢!Mendl;system(p

7、ause);)2-1#include#include#include#include#includeusing namespace std;typedef struct stack(char elem50J;int top;stack;void initstack(stack*s)(s-top=-l;)void push(stack*s,char e)if(s-toptop+;s-elems-top=e;elsecouttop=-1)coutvv”此栈 J 经空 了;else c=s-elems-top;s-top;return c;)int stackempty(stack*s)(if(s-

8、top=-1)return 1;else return 0;)int main()(stack*s=new stack;char c,e;initstack(s);cout”请输入字符串，然后请输入回车，再输入&停止”endl;while(e=getchar()!=,&,)coutvv”现在 e 是 veendl;push(s,e);coutvv”请输入回文串(注意回车也会被读出来，所以请保持上下格式一样！最后请将字母以及同时输入，才可以正常结束！因为由于回车读入，栈空时读入的可能是回车字符！):uendl;while(e=getchar()!=,)(coulvv”现在 e 是“vvevven

9、dl;if(stackempty(s)coutv不匹配！谢谢使用 1 ,;system(,pauseM);retum 0;c=pop(s);coutvv现在 c 是vvcvvendl;if(e!=c)coutvv不匹配!谢谢使用！”;system(pause);reium 0;)if(!stackempty(s)coutvv不 匹 配!谢谢使用！K;system(pauseu);return 0;coutvv”匹配成 功!谢谢使用！endl;system(pause);return 1;system(pause);)2-2#include#include#include#include#inc

10、lude#includeusing namespace std;class park(public:park():state(O),car(000000)(；void enter(string camum)state=l;t_start=time(NULL);cai*=carnum;park getlink()return*link;void carexit(double p)(price=0;state=O;coutvv车牌号为vvcarvvendl;t_end=time(NULL);sum=(int)difftime(t_end,t_start);coutvv”停留时间为：Hsum end

11、l;dosum=sum/60;price+;while(sum60);coutvv”价格为：H(price*p)endl;carstate();)string getcamum()return car;void carstate()(if(state=l)cout 当前汽车状态为：在停车场内，已驶入。elsecoutvv”当前汽车状态为：离开 vvendl;)private:int state;/1 A,0 出string car;double price;int sum;t_start,t_end;park*link;)；struct queue(string car;queue*next;

12、);int main()(cout.setf(ios:showpoinl);设置为始终输出小数点后的数字，就 是 说 a=3,它也 输 出 3.00这样cout.precision(2);cout.setf(ios:fixed);double p;string car;system(pause);park.*pc=new park 20;int choice;int top=0;system(pause);coutv请输入每分钟价格：uendl;cinp;LOOP:coutvv请输入您要使用的功能1.进入停车场t2.离开停车场t0.退出”vendl;cinchoice;switch(choic

13、e)(case l:cout 请 输 入 此 车 的 车 牌 号：uendl;cincar;pctop.enter(car);if(top=19)c o u t 车 满 了 uendl;else top+;gotoLOOP;case 2:if(top=0)coutvv”停车场空了!Hendl;else top-;pctop.carexit(p);goto LOOP;case 3:case 0:coutvv”欢迎下次使用”；)system(npause);return 0;)2-3#include#include#include#include#includeHstdlib.h#include#

14、include time.h#include stdio.h,include stdlib.hn#include LinkedList.h#include#include using namespace std;class stackpublic:int num;int data;string name;)；const int INCREMENT=20;栈模板/templateclass SeqStack(public:SeqStack(int size=50);-SeqStack();void Push(T x);bool Pop(T&e);bool IsEmptyO;bool IsFull

15、();int Length();bool getTop(T&x);void MakeEmptyO;void Output();private:T*elements;int top;int maxSize;void overflowProcess();)；templateSeqStack:SeqStack(int sz)top=-1;maxSize=sz;elements=new TmaxSize;assert(elements!=NULL);)templateSeqStack:-SeqStack()(deleteelements;)templatevoid SeqStack:Push(T x)

16、(if(IsFull()(overflowProcess();)elements+topl=x;)templatebool SeqStack:Pop(T&e)(if(IsEmpty()(return false;else(e=elementstop-;return true;)templatebool SeqStack:IsEmpty()if(top=-1)return true;return false;templatebool SeqStack:IsFull()(if(top=maxSize-1)(return true;)return false;)templatebool SeqSta

17、ck:getTop(T&x)(if(IsEmpty()(return false;)x=elementstop;)templateint SeqStack:Length()(return(top+l);)templatevoid SeqStack:MakeEmpty()(top=-1;)templatevoid SeqStack:overflowProcess()(T*newElems=new TfmaxSize+INCREMENT;if(newElems=NULL)(cerrMemory allocate error!uendl;exit(l);)for(int i=0;i=top;i+)n

18、ewElemsi=elementsi;)maxSize=maxSize+INCREMENT;deleteelements;elements=newElems;)templatevoid SeqStack:Output()(int i=0;if(!IsEmpty()(coutn-top-endl;for(i=top;i=0;i)(coutelementsiendl;(cout-base-endl;)队列模板！/templateclass Queueprivate:int rear,front;队尾，队头指针T*elements;队列元素数组int maxSize;/最大元素个数public:Qu

19、eue(int sz=10);-Queue()delete Jelements;void EnQueue(const T&item);进队bool DeQueue();退队T GetFront();取队头元素void MakeEmpty()front=rear=0;int IsEmpty()constreturn front=rear;int IsFull()constreturn(rear+1 )%maxSize=front;int Length()constretum(rear-front+maxSize)%maxSize;);templateQueue:Queue(int sz):fro

20、nt(0),rear(0),maxSize(sz)elements=new TmaxSize;assert(elements!=NULL);templatevoid Queue:EnQueue(const T&item)assert(!IsFull();rear=(rear+l)%maxSize;elements rear=item;templatebool Queue:DeQueue()if(IsEmpty()return false;front=(front4-1 )%maxSize;return true;templateT Queue:GetFront()assert(!IsEmpty

21、();return elements(front+1 )%maxSize;队列模板/链表模板templateLinkedList:LinkedList()(start=current=NULL;)templateLinkedList:LinkedList(const LinkedList&aplist)deepCopy(aplist);templateLinkedList:LinkedList()(makeEmptyO;)templateLinkedList&LinkedList:operator=(const LinkedList&rlist)(if(this=&rlist)return t

22、his;makeEmptyO;deepCopy(rlist);return this;)在链表的表头插入DT&element,插入后没有当前位置templatevoid LinkedList:insert(const DT&element)(current=NULL;Node*NNode=new Node;NNode-info=element;NNode-next=start;start=NNode;)在链表的尾部插入templatevoid LinkedList:insert_end(const DT&element)(current=NULL;Node*NNode=new Node;NNo

23、de-info=element;NNode-next=NULL;Node*temp;DT item;if(start=NULL)(start=NNode;temp=start;return;temp=start;while(temp-next!=NULL)temp=temp-next;temp-next=NNode;)把链表中的第一个元素存放在listEl中，并且把第一个元素的位置置为currenttemplatebool LinkedList:first(DT&listEl)(if(start=NULL)return false;current=start;listEl=start-info

24、;return true;)把链表中current的下个元素放在listEl中,current指向下一个元素templatebool LinkedList:getNext(DT&listEl)(if(current=NULL)return false;if(current-next=NULL)(current=NULL;return false;)listEl=current-next-i nfb;current=current-next;return true;)如果找到elm ent,返回true,current在 getNext。中设置templatebool LinkedList:fi

25、nd(const DT&element)(DT item;if(!first(item)return false;检查是否为空doif(item=element)return true;while(getNext(item);return false;)templatebool LinkedList:retrieve(DT&element)if(!find(element)return false;element=current-info;return true;)检索templatebool LinkedList:replace(const DT&newElement)(if(cuiTent

26、=NULL)return false;current-info=newElemenl;return true;templatebool LinkedList:remove(DT&element)(current=NULL;if(start=NULL)return false;Node*ptr=start;if(start-info=element)(element=start-info;start=ptr-next;delete ptr;return true;)while(ptr-next!=NULL)if(ptr-next-info=element)(Node*tempptr=ptr-ne

27、xt;element=tempptr-info;ptr-next=tempptr-next;delete tempptr;return true;)ptr=ptr-next;)return false;templatebool LinkedList:isEmpty()constreturn start=NULL;)templatevoid LinkedList:makeEmpty()(while(start!=NULL)(current=start;start=start-next;delete current;)current=NULL;)templatevoid LinkedList:de

28、epCopy(const LinkedList&original)(start=current=NULL;if(original.start=NULL)return;Node*copyptr=start=new Node;Node*originalptr=original.start;copyptr-info=originalptr-info;if(originalptr=original.current)current=copyptr;while(originalptr-next!=NULL)(copyptr-next=new Node;这一句有难度啊！originalptr=origina

29、lptr-next;copyptr=copyptr-next;copyptr-info=originalptr-info;if(originalptr=original.current)current=copyptr;)copyptr-next=NULL;/#endifvoid bubble(stack*a,int i)(int work;stack datatemp;for(int pass=O;passi;pass+)work二 1;for(int j=O;ji-pass;j+)if(a|j.datatm_hour);输出 tm 结构体的时间成员printf(HUTC hour is:%d

30、n,local-tm_hour);/local=gmtime(&t);gmtime()函数是将日历时间转化为世界标准时间(即格林尼治时间)，并返回一个tm 结构体来保存这个时间ptr=gmtime(&t);将日历时间转化为世界标准时间printf(The UTC time is%sn”,asctime(ptr);格式化输出世界标准时间printf(The local time is%sn,ctime(&t);输出本地时间/*asctime()函数(参数为tm 结构指针)和ctime()函数(参数为time_t结构)将时间以固定的格式显示出来，两者的返回值都是char*型的字符串。返回的时间格式

31、为：星期儿月份日期时:分:秒年n0*/int choice=l,i=0;stack tempi 100,SeqStack good(100),trains(100);Queue contained 100);string st I=12:13”；string st2=n 14:14*1;coutvv”请向货物栈中装入货物(输入0 停止)：”；while(choice!=0)(cout”请输入商品名称：endl;cintempli.name;cout”请输入商品数量 vvendl;cintempi.num;coutv”请输入上货I I期”vendl;cintempi.data;coutvc”是否

32、继续？输入 0 退出！uendl;cinchoice;if(choice!=0)i+;)bubble(temp,i);for(int j=O;j=i;j+)good.Push(tempj);loop:coutvc”请输入您要进行的操作：-nl.添加新的货物。n2.输出全部货物。n3.退出。”；cinchoice;switch(choice)(case l:cout”请输入您要插入的数据：endl;coutv“依次输入名称日期(月份和日之间不需要空格)数量:n”；cinttemp.name;fflush(stdin);cinttemp.data;fflush(stdin);cinttemp.nu

33、m;fflush(stdin);coutvv”输入完毕”;good.Pop(ttt);while(ttt.datattemp.dala)(container.EnQueue(ttt);if(good.IsEmpty()break;good.Pop(ttt);)coutvv”到达！container.EnQueue(ttemp);do(if(container.IsEmpty()break;ttt=container.GetFront();coutttt.name;trains.Push(ttt);while(container.DeQueue();coutvv”到达！while(!trains

34、.IsEmptyO)(trains.Pop(ttt);good.Push(ttt);)coutvv”到达！coutv=0;o-)good.Pop(ttemp);coutn 商 品 信 息 为-n 1.名称：vvttemp.namevv”n2.上架 日 期：uttemp.datan3.数量：ttemp.numendl;Jbreak;default:couterrorendl;goto loop;case 3:break;)coutvv”谢谢使用,作者制作！120400231M;system(upausen);头文件，加进去才能用#ifndef LINKEDLIST_H#define LINKED

35、LIST_Htemplatestruct Node(DT info;Node*next;);templateclass LinkedList(public:LinkedList();LinkedList(const LinkedList&aplist);LinkedList。；LinkedList&operator=(const LinkedList&rlist);void insert(const DT&element);在链表的头部之前插入void insert_end(const DT&element);在链表的尾部插入bool first(DT&listEl);得到对头的数据inlin

36、e bool getNext(DT&listEl);得到当前指针所指的下一个数据bool find(const DT&element);查找一个数据bool retrieve(DT&element);检索一 数 据bool replace(const DT&newElement);更改一个数据bool remove(DT&element);bool isEmptyO const;void makeEmptyO;private:Node*start;指向头结点Node current;指向当前的结点inline void deepCopy(const LinkedList&original);“

37、深复制”）；#endif2-4头文件与2-3相同#include#include#include#include#includestdlib.h#include#include time.h#include stdio.h”#include ustdlib.husing namespace std;#include LinkedList.huclass data;struct link;templateLinkedList:LinkedList()(start=current=NULL;)templateLinkedList:LinkedList(const LinkedList&aplist

38、)(deepCopy(aplist);)templateLinkedList:LinkedList()(makeEmpty();)templateLinkedList&LinkedList:operator=(const LinkedList&rlist)(if(this=&rlist)return this;makeEmptyO;deepCopy(rlist);return this;在链表的表头插入data&element,插入后没有当前位置templatevoid LinkedList:insert(const int&element)current=NULL;Node*NNode=ne

39、w Node;NNode-info=element;NNode-next=start;start=NNode;)/在链表的尾部插入templatevoid LinkedList:insert_end(int&listEl)(current=NULL;Node*NNode=new Node;NNode-info=element;NNode-next=NULL;Node*temp;data item;if(start=NULL)(start=NNode;temp=start;return;)temp=start;while(temp-next!=NULL)(temp=temp-next;)temp

40、-next=NNode;把链表中的第一个元素存放在listEl中，并且把第一个元素的位置置为currenttemplatebool LinkedList:first(int&listEl)(if(start=NULL)return false;current=start;listEl=start-info;return true;)把链表中current的下个元素放在listEl中，current指向下一个元素templatebool LinkedList:getNext(int&listEl)if(current=NULL)return false;if(current-next=NULL)

41、(current=NULL;return false;)listEl=current-next-info;current=current-next;return true;)如果找到elm ent,返回true,current在 getNext。中设置templatebool LinkedList:find(const data&element)(data item;if(!first(item)return false;检查是否为空do=element)return true;while(getNext(item);return false;)templatebool LinkedLi st

42、:retrieve(data&element)(if(!find(element)return false;element=current-info;return true;)检索templatebool LinkedList:replace(const data&newElement)(if(current=NULL)return false;current-info=newElement;return true;)templatebool LinkedList:remove(data&element)cunent=NULL;if(start=NULL)return false;Node*p

43、tr=start;if(start-info=element)(element=start-info;start=ptr-next;delete ptr;return true;)while(ptr-next!=NULL)if(ptr-next-info=element)(Node*tempptr=ptr-next;element=tempptr-info;ptr-next=tempptr-next;delete tempptr;return true;)ptr=ptr-next;)return false;)templatebool LinkedList:isEmpty()const(ret

44、urn start=NULL;)templatevoid LinkedList:makeEmpty()(while(start!=NULL)(current=start;start=start-next;delete cuiTent;)current=NULL;)templatevoid LinkedList:deepCopy(const LinkedList&original)(start=current=NULL;if(original.start=NULL)return;Node*copyptr=start=new Node;Node*originalptr=original.start

45、;copyptr-info=originalptr-info;if(originalptr=original.current)current=copyptr;while(originalptr-next!=NULL)(copyptr-next=new Node;这一句有难度啊！originalptr=originalptr-next;copyptr=copyptr-next;copyptr-info=originalptr-info;if(originalptr=original.current)current=copyptr;)copyptr-next=NULL;)/#endifvoid m

46、ain()struct tm*local,*ptr;定义tm 结构指针存储时间信息time_t t,t_end;时间结构或者对象t=time(NULL);获取当前系统的日历时间local=localtime(&t);ptr=gmtime(&t);coutn欢迎使用，制 作 者 作 者 endl,世 界 标 准 时 间是:nuasctim e(ptr)endl本土也时间是:nctime(&t)endl;int N,X,d;int temp;LinkedList S;char NumJ=H0 123456789ABCDEF;/Node D;loop:coutvv”请输入原十进制数”；cinN;co

47、utn转换后它是多少进制的：”;cind;if(N0)N=-N;coutu-M;while(N!=0)X=N%d;N=Wd;S.insert(X);coul插入“vvXvv”t”;system(”pause)；S.first(temp);couttemp;while(S.getNext(temp)couttemp;coutendl;t_end=time(NULL);coutvv”是否继续使用?输入 1 继续“vvendl;cintemp;if(temp=l)goto loop;coutv“谢 谢 使 用!现 在 本 地 时 间 是:nendlctim e(&t_end)M 已经使用时间是:vv

48、difftime(t_end,t)vv秒vvendl;system(pausen);6-1#include#include#include#include#includestdlib.h#include#include utime.h#include stdio.h#include ustdlib.h#include nLinkedList.hu#include#include using namespace std;class tree(public:tree()signal=1 ;lchild=NULL;rchild=NULL;char data;tree*lchild;tree*rchi

49、ld;int signal;);void build(tree*&t)先序建树(char c;cinc;if(c=!)(t=NULL;elset=new tree;t-data=c;build(t-lchild);build(t-rchild);)void preorder(tree*root)这是递归实现(if(root!=NULL)(coutroot-data;preorder(root-lchild);preorder(root-rchild);)Ivoid inorder(tree*&root)(if(root!=NULL)(inorder(root-lchild);coutroot-

50、data;inorder(root-rchild);)void pastorder(tree*&root)(if(root!=NULL)(pastorder(root-lchild);pastorder(root-rchild);coutroot-data;)class stack(public:tree*top,*base;)；void init(stack*s)初始化栈s-base=new treellOO;s-top=s-base;void push(stack*s,tree*t)入栈(*(s-top+)=*t;)void pop(stack*s,tree&t)取栈顶元素(t=*(sto