数据结构 二维码文件第2章主要算法的C++代码

第2章主要算法的C++代码顺序表类#include"string.h"#include"iostream.h"classSeqList1{public:SeqList1(intsz,intleng);//构造函数intlength(){returnlen;}//表长度voidoutput();//输出线性表中的元素intsearch(intx);//在表中顺序搜索xintget(inti);//在表中取出索引为i的元素intinsert(intx,inti);//在索引i处插入xintadd(intx);//插入表尾intremove(inti);//删除第i个位置处的表项private:int*data;//表的存放数组intmaxSize;//表的最大可容纳项数intlen;//表实际长度};SeqList1::SeqList1(intsz,intleng){//构造函数if(sz>0){maxSize=sz; len=leng;data=newint[maxSize];if(data==NULL){cout<<"存储分配错误！"<<"\n";return;}}}voidSeqList1::output(){//输出线性表中的元素cout<<"线性表元素：{";for(inti=0;i<len;i++){ cout<<data[i]<<"";}cout<<"}"<<endl;}intSeqList1::insert(intx,inti){//在顺序表中索引为i的位置处插入项x//函数返回插入是否成功的信息intj;if(i<0||i>len)return-1;//插入位置不合理，不能插入if(len==maxSize)return-2;//无空闲可用存储单元，不能插入for(j=len;j>i;j--)data[j]=data[j-1];//依次后移data[i]=x;//插入len++;//顺序表长度增1return0;}intSeqList1::add(intx){//在顺序表表尾处插入项x//函数返回插入是否成功的信息if(len==maxSize)return-1;//无空闲可用存储单元，不能插入data[len++]=x;//插入,顺序表长度增1return0;}intSeqList1::remove(inti){//删除第i个位置处的表项intj;if(i<0||i>len)return-1;//删除位置不合理，不能删除for(j=i+1;j<len;j++)data[j-1]=data[j];//依次前移len--;//表长度减1return0;}intSeqList1::search(intx){//搜索函数：在表中顺序搜索与给定值x匹配的表项//找到则函数返回该元素在线性表中的索引//否则函数返回-1，表示搜索失败for(inti=0;i<len;i++)if(data[i]==x)returni;return-1; }intSeqList1::get(inti){//搜索函数：在表中取出索引为i的元素//找到则函数返回该元素//否则函数返回-1，表示搜索失败if(i<0||i>=len) return-1;//索引值不合理，查找失败returndata[i]; }链式表类#include"string.h"#include"iostream.h"#include"stdio.h"structNodeType{ intdata; NodeType*next;};classLinkList{ private: NodeType*Head;//头结点intlen;//长度public:LinkList();//构造~LinkList();//析构intgetLen();voidinput();//输入线性表中的元素，尾插法建表voidoutput();//输出线性表中的元素voidsearch(intx);//在表中顺序搜索xvoidinsert(inti,intx); //在索引i处插入xvoidadd(intx);//插入表尾voidremove();};LinkList::LinkList(){//创建空链表 Head=newNodeType; Head->next=NULL; Head->data=0; len=0;}LinkList::~LinkList(){NodeType*p=Head->next;//使p指向第一个节点 while(p!=NULL){ Head->next=p->next;//使头指针指向p的下一个节点 deletep; p=Head->next; }deleteHead;//最后将头节点也删除cout<<"已经删除链表!"<<endl;}voidLinkList::input(){//尾插法创建链表NodeType*last,*p;intx;last=Head;cout<<"请输入一组数据并且以0结束。"<<endl;cin>>x;//输入数据元素。while(x!=0){ p=newNodeType; p->data=x; last->next=p;//插在表尾last=p;//修改尾指针len++;cin>>x;//读入下一个元素}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; //暂时没找到，则继续向后找}cout<<"记录不存在!"<<endl; //查找不成功}voidLinkList::insert(inti,intx){NodeType*p,*q,*s;//定义结构体类型指针intk=1;p=Head;//让p指向Head节点q=p->next;//让q指向第一个节点while(k<i&&q!=NULL){ p=q; q=q->next; k++; }if(k==i){//实现插入s=newNodeType; s->data=x; p->next=s; s->next=q; len++; cout<<"记录成功插入!"<<endl; }elsecout<<"插入记录失败！";}voidLinkList::remove(){cout<<"输入要删除的元素："<<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();//构造函数boolSTIsEmpty()const;//测试栈是否空boolSTIsFull()const;//测试栈是否满intPushST(DATAx);//进栈intPopST(DATA&x);//出栈intPeekST(DATA&x);//读取栈顶结点voidprint();//打印栈intlen();//获取栈元素个数};/********初始化栈结构*********/Cstack::Cstack(){ top=-1;}/*********判断空栈**********/boolCstack::STIsEmpty()const{ boolt;t=(top==-1);//通过栈顶的值进行判断returnt;}/***********判断满栈********/boolCstack::STIsFull()const{ boolt;t=(top==MAXLEN-1);returnt;}/*********打印栈**********/voidCstack::print(){for(inti=0;i<=top;i++){ cout<<"第"<<i+1<<"个元素:"<<data[i]<<endl; }cout<<endl;}/*********获取栈元素个数**********/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;}链式栈类#include<iostream>#include<string>usingnamespacestd;structDATA{stringname;intage;};structItem{ DATAdata; Item*p_next;};classLstack{public: Lstack(); virtual~Lstack(); voidpush(DATAx);//进栈操作； Item*pop();//出栈操作； boolisEmpty()const;//判断栈空； voidclear();//清空栈，使栈为空； intsize()const;//获得栈的大小； voidprint()const;//打印栈内元素；Item*PeekST();private: Item*p_Top;//栈顶};Lstack::Lstack():p_Top(NULL)//构造函数{}//进栈操作voidLstack::push(DATAx){Item*pushElement=newItem;pushElement->data=x;if(!p_Top){//如果栈为空时p_Top=pushElement; pushElement->p_next=NULL;}else{//若栈不为空时 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;}//打印栈内元素voidLstack::print()const{ intcount=0; Item*temp=p_Top; while(temp&&++count) { cout<<"name:"<<temp-><<"\tage:"<<temp->data.age<<endl; temp=temp->p_next; } }/**********************读取点结构*******************/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<<"输入姓名，年龄进行入栈操作："<<endl;//执行入栈操作while(1) {cin>>>>data.age;if(=="0"){break;//当姓名和年龄都是0的时候退出输入 }else{cst.push(data); }} cout<<"栈内元素个数："<<cst.size()<<endl; cst.print();Item*x= cst.pop(); cout<<"栈顶元素出栈："<<x-><<":"<<x->data.age<<endl; cout<<"栈内元素个数："<<cst.size()<<endl; cst.print(); }循环队类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){//入队if(isFull())returnfalse;element[rear]=x;rear=(rear+1)%maxSize;returntrue;}boolDeQueue(T&x){//出队if(isEmpty())returnfalse;x=element[front];front=(front+1)%maxSize;returntrue;}boolgetFront(T&x){//获取队首元素if(isEmpty())returnfalse;x=element[front];returntrue;}voidmakeEmpty(){//队列置空front=rear=0;}boolisEmpty()const{//判断队列是否为空return(rear==front)?true:false;}boolisFull()const{//队列是否为满return((rear+1)%maxSize==front)?true:false;}intgetSize()const{return(rear-front+maxSize)%maxSize;}};voidmenu(){cout<<"1.入队"<<endl;cout<<"2.获取队首元素"<<endl;cout<<"3.出队"<<endl;cout<<"4.队列置空"<<endl;cout<<"5.获取队中元素数量"<<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;}链式队类#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.入队"<<endl;cout<<"2.获取队首元素"<<endl;cout<<"3.出队"<<endl;cout<<"4.队列置空"<<endl;cout<<"5.获取队中元素数量"<<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;}实验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班级：YYYY"<<endl;cout<<endl;inti=1,op,x,index,res;while(i==1){cout<<"请选择操作代码：";cin>>op;switch(op){ case1:cout<<"请输入要添加的元素："; cin>>x; res=s1.add(x); if(res==0)cout<<"添加成功！"<<endl; elsecout<<"添加失败！"<<endl; break; case2:cout<<"请输入要插入的位置和元素（用空格分隔）："; cin>>index; cin>>x; res=s1.insert(x,index); if(res==0)cout<<"插入成功！"<<endl; elsecout<<"插入失败！"<<endl; break;case3:cout<<"请输入要删除元素的位置："; cin>>index; res=s1.remove(index); if(res==0)cout<<"删除成功！"<<endl; elsecout<<"删除失败！"<<endl; break; case4:cout<<"请输入要查找的元素："; cin>>x; res=s1.search(x); if(res!=-1)cout<<"元素"<<x<<"为线性表中第"<<res+1<<"个元素"<<endl; elsecout<<"查找失败！"<<endl; break;case5:cout<<"请输入要取元素的位置："; cin>>index; res=s1.get(index); if(res!=-1)cout<<"线性表中第"<<index+1<<"个元素为："<<res<<endl; elsecout<<"获取元素失败！"<<endl; break; case6: s1.output(); cout<<"线性表长度："<<s1.length()<<endl; break; default:i=0; }}}实验2：链表的基本操作voidmain(){LinkLists1;s1.input();