数据结构个人笔记总结

∩_∩-[数据结构个人笔记总结][王小龙]GoodluckBelieveyourselfJustgo数据结构部分一、数据结构的基本概念1.逻辑结构1)集合结构(集)：结构中的元素除了同属一个集之外，没有任何联系。2)线性结构(表)：结构中的元素具有一对一的前后关系。3)树型结构(树)：结构中的元素具有一对多的父子关系。4)网状结构(图)：结构中的元素具有多对多的交叉映射关系。2.物理结构1)顺序结构(数组)：结构中的元素存放在一段连续的地址空间中。随机访问方便，空间利用率低，插入删除不便。2)链式结构(链式)：结构中的元素存放在彼此独立的地址空间中，每个独立的地址空间被称为节点，节点除了保存数据以外，还保存另外一个或几个相关节点的地址。空间利用率高，插入删除方便，随机访问不便。3.逻辑结构和物理结构的关系表树图顺序数组顺序树复链式链表链式树合二、数据结构的基本运算1.创建与销毁2.插入与删除3.获取与修改4.排序与查找三、堆栈1.基本特征：后进先出2.基本操作：压入(push)，弹出(pop)3.实现要点：初始化空间，栈顶指针，判空判满。12341*9^3+2*9^2+3*9^1+4*9^0-4123-312-21-1例子1：基于顺序表的堆栈#includeiostreamusingnamespacestd;//基于顺序表的堆栈classStack{public://构造过程中分配内存Stack(size_tsize=10):m_array(newint[size]),m_size(size),m_top(0){}//析构过程中释放内存~Stack(void){if(m_array){delete[]m_array;m_array=0;}}//压入要判断是否满了voidpush(intdata){if(full())//如果返回为真，则满了throwOverFlow();//抛出异常m_array[m_top++]=data;//压入元素，用后++，因为先在栈顶的位置压入元素，在将栈顶上移，等待新的元素压入}//弹出要判断是否为空intpop(void){//if(empty())//如果返回为真，则为空throwUnderFlow();//抛出异常returnm_array[--m_top];//用前--，因为要先将栈顶下降一，在弹出}//判满boolfull(void)const{returnm_top=m_size;//如果满了，返回真}//判空boolempty(void)const{return!m_top;//如果位空，返回为真}private://上溢异常classOverFlow:publicexception{//内部类，继承标准异常constchar*what(void)constthrow(){//给what提供一个覆盖return堆栈上溢！;}};//下溢异常classUnderFlow:publicexception{//内部类，继承标准异常constchar*what(void)constthrow(){return堆栈下溢！;}};int*m_array;//数组size_tm_size;//容量size_tm_top;//栈顶};voidprintb(unsignedintnumb,intbase){//堆栈的产生与使用的顺序是相反的。Stackstack(256);do{stack.push(numb%base);//进行求余得到没以为的数字，不过顺序相反}while(numb/=base);//while(!stack.empty()){//将栈中的内容拿出。因为堆栈是后进先出，所以顺序再次颠倒，刚好恢复顺序intdigit=stack.pop();if(digit10)coutdigit;elsecoutchar(digit-10+'A');//强制转换成char型，小于十的直接用上一行的代码打印，大于十的转换位a，b，c，d，e，f打印}coutendl;}intmain(void){try{Stackstack;for(inti=0;!stack.full();++i)//压入元素，直到栈满stack.push(i);//stack.push(0);//这时栈满，抛出OverFlowwhile(!stack.empty())//判断是否为空，不空则打印出coutstack.pop()endl;//stack.pop();//这时栈空，抛出UnderFlow}catch(exception&ex){coutex.what()endl;//调用的是相对应exception类的子类中的what的覆盖版本return-1;}cout输入一个整数：flush;intnumb;cinnumb;cout您想看几进制：flush;intbase;cinbase;cout结果：;printb(numb,base);return0;}----------------------------------------------------------------------------------------------------------------------例子2：基于链式表的堆栈#includeiostreamusingnamespacestd;//基于链式表的堆栈classStack{public://构造过程中初始化为空堆栈Stack(void):m_top(NULL){}//析构过程中销毁剩余的节点~Stack(void){for(Node*next;m_top;m_top=next){next=m_top-m_next;deletem_top;}}//压入voidpush(intdata){/*Node*node=newNode;node-m_data=data;node-m_next=m_top;m_top=node;*/m_top=newNode(data,m_top);//和上面的四行实现的是一样的}//弹出intpop(void){if(empty())//如果为空，则抛出异常throwUnderFlow();intdata=m_top-m_data;//保存弹出的节点的值Node*next=m_top-m_next;//保存弹出的节点后指针指向的地址（也就是保存弹出节点的后一个节点的地址）deletem_top;m_top=next;//将栈顶指针移动到弹出节点的后指针指向的那个节点（也就是将栈顶指针指向弹出节点的后一个节点的地址）returndata;//返回弹出的元素值}//判空boolempty(void)const{return!m_top;}private://下溢异常//链表实现的堆栈不会存在满的情况。classUnderFlow:publicexception{//继承标准异常constchar*what(void)constthrow(){return堆栈下溢！;}};//节点classNode{public:Node(intdata=0,Node*next=NULL):m_data(data),m_next(next){}intm_data;//数据Node*m_next;//后指针};Node*m_top;//栈顶};intmain(void){try{Stackstack;for(inti=0;i10;++i)stack.push(i);while(!stack.empty())coutstack.pop()endl;//stack.pop();}catch(exception&ex){coutex.what()endl;return-1;}return0;}----------------------------------------------------------------------------------------------------------------------四、队列1.基本特征：先进先出，FIFO2.基本操作：压入(push)、弹出(pop)3.实现要点：初始化空间，从前端(front)弹出，从后端(rear)压入，循环使用，判空判满思考：用堆栈实现队列。例子1：基于顺序表的队列#includeiostreamusingnamespacestd;//基于顺序表的队列classQueue{public://构造过程中分配内存Queue(size_tsize=5):m_array(newint[size]),m_size(size),m_rear(0),m_front(0),m_count(0){}//析构过程中释放内存~Queue(void){if(m_array){delete[]m_array;m_array=NULL;}}//压入voidpush(intdata){if(full())//判断是否，满了throwOverFlow();if(m_rear=m_size)m_rear=0;//如果后端指针指向的位置超过数组的大小，则循环利用，从最初的数组起始位置开始压入，不用担心0处是否会有元素，因为前面已经判断是否为满，既然能执行到这，没有抛出异常，就说明没有满，可以在0处压入++m_count;//压入一个元素，计数则加一m_array[m_rear++]=data;//用后++，向数组中后端指针指向的位置压入元素，在将后端指针移动到下一个位置}//弹出intpop(void){if(empty())//判断是否为空throwUnderFlow();if(m_front=m_size)//如果前段指针指向的位置超过数组大小，则循环利用，从数组的起始位置0处开始弹出m_front=0;//不用担心0处是否有元素可弹出，因为前面已经判断过是否为空，既然执行到这，说明不为空，没有抛出异常，则0出异一定有元素可弹出--m_count;//弹出一个元素，技术则减一returnm_array[m_front++];//用后++，返回弹出的元素，在将前段指针移动到下一个要弹出的位置}//判空boolempty(void)const{return!m_count;//如果计数为0则为空，返回真说明空了}//判满boolfull(void)const{returnm_count==m_size;//如果计数与数组大小相等，则说明满了}private://上溢异常classOverFlow:publicexception{constchar*what(void)constthrow(){return队列上溢！;}};//下溢异常classUnderFlow:publicexception{constchar*what(void)constthrow(){return队列下溢！;}};int*m_array;//数组size_tm_size;//容量size_tm_rear;//后端size_tm_front;//前端size_tm_count;//计数};intmain(void){try{Queuequeue;queue.push(10);queue.push(20);queue.push(30);queue.push(40);queue.push(50);//queue.push(60);//会显示队列上溢coutqueue.pop()endl;//10弹出0处先进先出queue.push(60);//循环利用，前面已经将0处的10弹出，则会将60压入到0这里coutqueue.pop()endl;//20弹出1处queue.push(70);//选还利用，前面将1处的20弹出，则会将70压入到1这里//queue.push(80);//会显示队列上溢coutqueue.pop()