數(shù)據(jù)結(jié)構(gòu) 二維碼文件第2章主要算法的C++代碼

第2章主要算法的C++代碼順序表類#include"string.h"#include"iostream.h"classSeqList1{public:SeqList1(intsz,intleng);//構(gòu)造函數(shù)intlength(){returnlen;}//表長(zhǎng)度voidoutput();//輸出線性表中的元素intsearch(intx);//在表中順序搜索xintget(inti);//在表中取出索引為i的元素intinsert(intx,inti);//在索引i處插入xintadd(intx);//插入表尾intremove(inti);//刪除第i個(gè)位置處的表項(xiàng)private:int*data;//表的存放數(shù)組intmaxSize;//表的最大可容納項(xiàng)數(shù)intlen;//表實(shí)際長(zhǎng)度};SeqList1::SeqList1(intsz,intleng){//構(gòu)造函數(shù)if(sz>0){maxSize=sz; len=leng;data=newint[maxSize];if(data==NULL){cout<<"存儲(chǔ)分配錯(cuò)誤！"<<"\n";return;}}}voidSeqList1::output(){//輸出線性表中的元素cout<<"線性表元素：{";for(inti=0;i<len;i++){ cout<<data[i]<<"";}cout<<"}"<<endl;}intSeqList1::insert(intx,inti){//在順序表中索引為i的位置處插入項(xiàng)x//函數(shù)返回插入是否成功的信息intj;if(i<0||i>len)return-1;//插入位置不合理，不能插入if(len==maxSize)return-2;//無空閑可用存儲(chǔ)單元，不能插入for(j=len;j>i;j--)data[j]=data[j-1];//依次后移data[i]=x;//插入len++;//順序表長(zhǎng)度增1return0;}intSeqList1::add(intx){//在順序表表尾處插入項(xiàng)x//函數(shù)返回插入是否成功的信息if(len==maxSize)return-1;//無空閑可用存儲(chǔ)單元，不能插入data[len++]=x;//插入,順序表長(zhǎng)度增1return0;}intSeqList1::remove(inti){//刪除第i個(gè)位置處的表項(xiàng)intj;if(i<0||i>len)return-1;//刪除位置不合理，不能刪除for(j=i+1;j<len;j++)data[j-1]=data[j];//依次前移len--;//表長(zhǎng)度減1return0;}intSeqList1::search(intx){//搜索函數(shù)：在表中順序搜索與給定值x匹配的表項(xiàng)//找到則函數(shù)返回該元素在線性表中的索引//否則函數(shù)返回-1，表示搜索失敗for(inti=0;i<len;i++)if(data[i]==x)returni;return-1; }intSeqList1::get(inti){//搜索函數(shù)：在表中取出索引為i的元素//找到則函數(shù)返回該元素//否則函數(shù)返回-1，表示搜索失敗if(i<0||i>=len) return-1;//索引值不合理，查找失敗returndata[i]; }鏈?zhǔn)奖眍?include"string.h"#include"iostream.h"#include"stdio.h"structNodeType{ intdata; NodeType*next;};classLinkList{ private: NodeType*Head;//頭結(jié)點(diǎn)intlen;//長(zhǎng)度public:LinkList();//構(gòu)造~LinkList();//析構(gòu)intgetLen();voidinput();//輸入線性表中的元素，尾插法建表voidoutput();//輸出線性表中的元素voidsearch(intx);//在表中順序搜索xvoidinsert(inti,intx); //在索引i處插入xvoidadd(intx);//插入表尾voidremove();};LinkList::LinkList(){//創(chuàng)建空鏈表 Head=newNodeType; Head->next=NULL; Head->data=0; len=0;}LinkList::~LinkList(){NodeType*p=Head->next;//使p指向第一個(gè)節(jié)點(diǎn) while(p!=NULL){ Head->next=p->next;//使頭指針指向p的下一個(gè)節(jié)點(diǎn) deletep; p=Head->next; }deleteHead;//最后將頭節(jié)點(diǎn)也刪除cout<<"已經(jīng)刪除鏈表!"<<endl;}voidLinkList::input(){//尾插法創(chuàng)建鏈表NodeType*last,*p;intx;last=Head;cout<<"請(qǐng)輸入一組數(shù)據(jù)并且以0結(jié)束。"<<endl;cin>>x;//輸入數(shù)據(jù)元素。while(x!=0){ p=newNodeType; p->data=x; last->next=p;//插在表尾last=p;//修改尾指針len++;cin>>x;//讀入下一個(gè)元素}last->next=NULL;cout<<"鏈表建成!"<<endl;}voidLinkList::output(){ NodeType*p; p=Head->next; cout<<"鏈表的值為："<<endl; while(p!=NULL){ printf("%5d",p->data); p=p->next; } cout<<endl;}voidLinkList::search(intx){ NodeType*p=Head;while(p!=NULL){ if(p->data==x){ cout<<"記錄查找成功!"<<endl;//找到x return; }p=p->next; //暫時(shí)沒找到，則繼續(xù)向后找}cout<<"記錄不存在!"<<endl; //查找不成功}voidLinkList::insert(inti,intx){NodeType*p,*q,*s;//定義結(jié)構(gòu)體類型指針intk=1;p=Head;//讓p指向Head節(jié)點(diǎn)q=p->next;//讓q指向第一個(gè)節(jié)點(diǎn)while(k<i&&q!=NULL){ p=q; q=q->next; k++; }if(k==i){//實(shí)現(xiàn)插入s=newNodeType; s->data=x; p->next=s; s->next=q; len++; cout<<"記錄成功插入!"<<endl; }elsecout<<"插入記錄失?。?;}voidLinkList::remove(){cout<<"輸入要?jiǎng)h除的元素："<<endl; intx; cin>>x;NodeType*p,*q;intk=1;p=Head;q=p->next;while(q!=NULL&&q->data!=x){ p=q; q=q->next;}if(q!=NULL&&q->data==x){ p->next=q->next; deleteq; len--; cout<<x<<"記錄成功刪除!"<<endl;}else{ cout<<"x不存在"<<endl; }}voidLinkList::add(intx){//插入表尾NodeType*p,*q; q=Head; while(q->next)q=q->next; p=newNodeType; p->data=x; p->next=NULL; q->next=p;//插在表尾len++;cout<<"記錄添加成功!"<<endl;}intLinkList::getLen(){ returnlen;}順序棧類#include<iostream>usingnamespacestd;typedefintDATA;#defineMAXLEN50classCstack{private:inttop;DATAdata[MAXLEN];public:Cstack();//構(gòu)造函數(shù)boolSTIsEmpty()const;//測(cè)試棧是否空boolSTIsFull()const;//測(cè)試棧是否滿intPushST(DATAx);//進(jìn)棧intPopST(DATA&x);//出棧intPeekST(DATA&x);//讀取棧頂結(jié)點(diǎn)voidprint();//打印棧intlen();//獲取棧元素個(gè)數(shù)};/********初始化棧結(jié)構(gòu)*********/Cstack::Cstack(){ top=-1;}/*********判斷空棧**********/boolCstack::STIsEmpty()const{ boolt;t=(top==-1);//通過棧頂?shù)闹颠M(jìn)行判斷returnt;}/***********判斷滿棧********/boolCstack::STIsFull()const{ boolt;t=(top==MAXLEN-1);returnt;}/*********打印棧**********/voidCstack::print(){for(inti=0;i<=top;i++){ cout<<"第"<<i+1<<"個(gè)元素:"<<data[i]<<endl; }cout<<endl;}/*********獲取棧元素個(gè)數(shù)**********/intCstack::len(){ returntop+1;}intCstack::PushST(DATAx){ if(STIsFull()){cout<<"棧溢出"<<endl;return0;}data[++top]=x;//將元素壓入棧return1;}intCstack::PopST(DATA&x){ if(STIsEmpty()){cout<<"棧為空！"<<endl;return0;}x=data[top--];return1;}鏈?zhǔn)綏ｎ?include<iostream>#include<string>usingnamespacestd;structDATA{stringname;intage;};structItem{ DATAdata; Item*p_next;};classLstack{public: Lstack(); virtual~Lstack(); voidpush(DATAx);//進(jìn)棧操作； Item*pop();//出棧操作； boolisEmpty()const;//判斷棧空； voidclear();//清空棧，使棧為空； intsize()const;//獲得棧的大小； voidprint()const;//打印棧內(nèi)元素；Item*PeekST();private: Item*p_Top;//棧頂};Lstack::Lstack():p_Top(NULL)//構(gòu)造函數(shù){}//進(jìn)棧操作voidLstack::push(DATAx){Item*pushElement=newItem;pushElement->data=x;if(!p_Top){//如果棧為空時(shí)p_Top=pushElement; pushElement->p_next=NULL;}else{//若棧不為空時(shí) pushElement->p_next=p_Top; p_Top=pushElement;}}//出棧操作Item*Lstack::pop(){if(!p_Top){ return0;}Item*x=p_Top;p_Top=p_Top->p_next;returnx;}//判斷棧是否為空boolLstack::isEmpty()const{ returnp_Top==NULL;}//清空棧，使棧置為空棧voidLstack::clear(){Item*deleteElement;while(p_Top){ deleteElement=p_Top; p_Top=p_Top->p_next; deletedeleteElement;}}//獲得棧的大小intLstack::size()const{ intlength=0; Item*temp=p_Top; while(temp&&++length) { temp=temp->p_next; } returnlength;}//打印棧內(nèi)元素voidLstack::print()const{ intcount=0; Item*temp=p_Top; while(temp&&++count) { cout<<"name:"<<temp-><<"\tage:"<<temp->data.age<<endl; temp=temp->p_next; } }/**********************讀取點(diǎn)結(jié)構(gòu)*******************/Item*Lstack::PeekST(){if(p_Top){cout<<"棧已空"<<endl;exit(0);}returnp_Top;}Lstack::~Lstack(){Item*deleteElement; while(p_Top) { deleteElement=p_Top; p_Top=p_Top->p_next; deletedeleteElement; }}voidmain(){ Lstackcst; DATAdata,*p_data; cout<<"===============入棧操作：============="<<endl;cout<<"輸入姓名，年齡進(jìn)行入棧操作："<<endl;//執(zhí)行入棧操作while(1) {cin>>>>data.age;if(=="0"){break;//當(dāng)姓名和年齡都是0的時(shí)候退出輸入 }else{cst.push(data); }} cout<<"棧內(nèi)元素個(gè)數(shù)："<<cst.size()<<endl; cst.print();Item*x= cst.pop(); cout<<"棧頂元素出棧："<<x-><<":"<<x->data.age<<endl; cout<<"棧內(nèi)元素個(gè)數(shù)："<<cst.size()<<endl; cst.print(); }循環(huán)隊(duì)類template<classT>classSeqQueue{protected:T*element;intfront,rear;intmaxSize;public:SeqQueue(intsz=10){front=rear=0;maxSize=sz;element=newT[maxSize];}~SeqQueue(){delete[]element;}boolEnQueue(constT&x){//入隊(duì)if(isFull())returnfalse;element[rear]=x;rear=(rear+1)%maxSize;returntrue;}boolDeQueue(T&x){//出隊(duì)if(isEmpty())returnfalse;x=element[front];front=(front+1)%maxSize;returntrue;}boolgetFront(T&x){//獲取隊(duì)首元素if(isEmpty())returnfalse;x=element[front];returntrue;}voidmakeEmpty(){//隊(duì)列置空front=rear=0;}boolisEmpty()const{//判斷隊(duì)列是否為空return(rear==front)?true:false;}boolisFull()const{//隊(duì)列是否為滿return((rear+1)%maxSize==front)?true:false;}intgetSize()const{return(rear-front+maxSize)%maxSize;}};voidmenu(){cout<<"1.入隊(duì)"<<endl;cout<<"2.獲取隊(duì)首元素"<<endl;cout<<"3.出隊(duì)"<<endl;cout<<"4.隊(duì)列置空"<<endl;cout<<"5.獲取隊(duì)中元素?cái)?shù)量"<<endl;cout<<"6.退出"<<endl;}voidfunction(intnum,SeqQueue<int>*sq){switch(num){intx;case1:cin>>x;sq->EnQueue(x);break;case2:sq->getFront(x);cout<<x<<endl;break;case3:sq->DeQueue(x);break;case4:sq->makeEmpty();break;case5:x=sq->getSize();cout<<x<<endl;break;default:exit(1);}}intmain(intargc,char**argv){SeqQueue<int>*sq=newSeqQueue<int>;intnum;while(true){menu();cin>>num;function(num,sq);}deletesq;return0;}鏈?zhǔn)疥?duì)類#include<iostream>usingnamespacestd;template<classT>structLinkNode{Tdata;LinkNode<T>*link;LinkNode(T&x,LinkNode<T>*l=NULL){data=x;link=l;}};template<classT>classLinkedQueue{protected:LinkNode<T>*front,*rear;public:LinkedQueue(){front=rear=NULL;}~LinkedQueue(){makeEmpty();}boolenQueue(T&x){if(front==NULL)front=rear=newLinkNode<T>(x);else{rear=rear->link=newLinkNode<T>(x);}returntrue;}booldeQueue(T&x){if(isEmpty())returnfalse;LinkNode<T>*p=front;x=front->data;front=front->link;deletep;returntrue;}boolgetFront(T&x)const{if(isEmpty())returnfalse;x=front->data;returntrue;}voidmakeEmpty(){LinkNode<T>*p;while(front!=NULL){p=front;front=front->link;deletep;}}boolisEmpty()const{return(front==NULL)?true:false;}intgetSize()const{LinkNode<T>*p;intcount=0;p=front;while(p!=NULL){count++;p=p->link;}returncount;}};voidmenu(){cout<<"1.入隊(duì)"<<endl;cout<<"2.獲取隊(duì)首元素"<<endl;cout<<"3.出隊(duì)"<<endl;cout<<"4.隊(duì)列置空"<<endl;cout<<"5.獲取隊(duì)中元素?cái)?shù)量"<<endl;cout<<"6.退出"<<endl;}voidfunction(intnum,LinkedQueue<int>*lq){switch(num){intx;case1:cin>>x;lq->enQueue(x);break;case2:lq->getFront(x);cout<<x<<endl;break;case3:lq->deQueue(x);break;case4:lq->makeEmpty();break;case5:x=lq->getSize();cout<<x<<endl;break;default:exit(1);}}intmain(intargc,char**argv){LinkedQueue<int>*lq=newLinkedQueue<int>;intnum;while(true){menu();cin>>num;function(num,lq);}deletelq;return0;}實(shí)驗(yàn)1：順序表的基本操作voidmain(){SeqList1s1(100,5);s1.input();cout<<"線性表初始化完成！"<<endl;;//顯示菜單cout<<"======================"<<endl;cout<<"1:添加元素"<<endl;cout<<"2:插入元素"<<endl;cout<<"3:刪除元素"<<endl;cout<<"4:查找元素"<<endl;cout<<"5:取表元素"<<endl;cout<<"6:顯示線性表"<<endl;cout<<"其他:退出"<<endl;cout<<"======================"<<endl;cout<<"作者：XXXX班級(jí)：YYYY"<<endl;cout<<endl;inti=1,op,x,index,res;while(i==1){cout<<"請(qǐng)選擇操作代碼：";cin>>op;switch(op){ case1:cout<<"請(qǐng)輸入要添加的元素："; cin>>x; res=s1.add(x); if(res==0)cout<<"添加成功！"<<endl; elsecout<<"添加失??！"<<endl; break; case2:cout<<"請(qǐng)輸入要插入的位置和元素（用空格分隔）："; cin>>index; cin>>x; res=s1.insert(x,index); if(res==0)cout<<"插入成功！"<<endl; elsecout<<"插入失??！"<<endl; break;case3:cout<<"請(qǐng)輸入要?jiǎng)h除元素的位置："; cin>>index; res=s1.remove(index); if(res==0)cout<<"刪除成功！"<<endl; elsecout<<"刪除失??！"<<endl; break; case4:cout<<"請(qǐng)輸入要查找的元素："; cin>>x; res=s1.search(x); if(res!=-1)cout<<"元素"<<x<<"為線性表中第"<<res+1<<"個(gè)元素"<<endl; elsecout<<"查找失敗！"<<endl; break;case5:cout<<"請(qǐng)輸入要取元素的位置："; cin>>index; res=s1.get(index); if(res!=-1)cout<<"線性表中第"<<index+1<<"個(gè)元素為："<<res<<endl; elsecout<<"獲取元素失敗！"<<endl; break; case6: s1.output(); cout<<"線性表長(zhǎng)度："<<s1.length()<<endl; break; default:i=0; }}}實(shí)驗(yàn)2：鏈表的基本操作voidmain(){LinkLists1;s1.input();