《线性群体类幻灯片.ppt》由会员分享，可在线阅读，更多相关《线性群体类幻灯片.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性群体类线性群体类第1页，共25页，编辑于2022年，星期一直接访问群体：数组（直接访问群体：数组（Array）类）类 静态数组的大小在编译时已经确定，运行时无法改变大小，且无法有效地避免下标越界。我们可以设计动态的Array类模板。第2页，共25页，编辑于2022年，星期一Array类模板类模板 template class Array private:T*alist;int size;public:Array(int sz=50);Array(Array&A);Array();void resize(int sz);Array&operator=(const Array&A);T&ope
2、rator (int i);int getsize();.;第3页，共25页，编辑于2022年，星期一顺序访问群体：链表（顺序访问群体：链表（Linked List）类）类 在软件设计中，经常会遇到这样的问题：需要处理和表示一个线性群体，但是其中元素的个数无法预先确定，这时就必须应用动态数据结构，在程序运行期间根据问题动态申请内存，并建立这些数据之间的线性关系。链表是一种动态数据结构，可以用来表示顺序访问的线性群体。链表由一系列结点（node）构成，结点可以在运行过程中动态生成。data1data2data3data nNULL头结点（head）尾结点（tail）单链表示意图数据域指针域第4页
3、，共25页，编辑于2022年，星期一结点类模板结点类模板 template class Node public:T element;Node*next;Node()next=NULL;Node(T element)this-element=element;next=NULL;element1nextelement2nextElement nNULL第5页，共25页，编辑于2022年，星期一 Node*head,*tail;链表为空时：head=tail=NULL;产生链表的第一个结点：head=new Node(“Chicago”);tail=head;产生链表的第二个结点：tail-next
4、=new Node(“Denver”);tail=tail-next;产生链表的第三个结点：tail-next=new Node(“Los angles”);tail=tail-next;element1nextelement2nextElement nNULLheadtail第6页，共25页，编辑于2022年，星期一 遍历（遍历（traverse）所有结点：）所有结点：Node*current;for(current=head;current;current=current-next)coutelementendl;element1nextelement2nextElement nNULLh
5、eadtail第7页，共25页，编辑于2022年，星期一 链表类模板链表类模板按照面向对象的方法，将节点与操作封装起来，便构成链表类按照面向对象的方法，将节点与操作封装起来，便构成链表类 template class LinkedList private:Node*head,*tail;int size;public:LinkedList();void addFirst(T element);void addLast(T element);void add(int index,T element);T removeFirst();T removeLast();T remove(int inde
6、x);bool isEmpty();void clear();T getLast(int index);；第8页，共25页，编辑于2022年，星期一 template LinkedList:LinkedList()head=tail=NULL;size=0;template void LinkedList:addFirst()Node*newNode;newNode=new Node(element);newNode-next=head;head=newNode;size+;if(tail=NULL)tail=head;element1nextelement2nextheadelement1n
7、extnewNode tail tail headelement1nextnewNodeNULL 第9页，共25页，编辑于2022年，星期一 template void LinkedList:addLast()if(tail=NULL)head=tail=new Node(element);else tail-next=new Node(element);tail=tail-next;size+;element1nextelement nNULLheadelementNULLnewNode tail tail headelement1nextnewNodeNULL 第10页，共25页，编辑于2
8、022年，星期一 template void LinkedList:add(int index,T element)if(index=0)addFirst(element);else if(index=size)addLast(element);else Node *current=head,temp;for(int i=1;inext;temp=current-next;current-next=new Node(element);(current-next)-next=temp;size+;element1nextelement inextelement nNULLelement jnex
9、telementNULLcurrenttempnewnode第11页，共25页，编辑于2022年，星期一 template T LinkedList:removeFirst()if(size 0)Node *temp=head;head=head-next;if(head=NULL)tail=NULL;size-;T element=temp-element;delete temp;return element;element1nextelement inextelement nNULLtemphead第12页，共25页，编辑于2022年，星期一 template T LinkedList:r
10、emoveLast()if(size=1)Node *temp=head;head=tail=NULL;size-;T element=temp-element;delete temp;return element;else Node *current=head;for(int j=0;jnext;Node *temp=tail;tail=current;tail-next=NULL;size-;T element=temp-element;delete temp;return element;element1nextelement inextelement nNULLelement knex
11、telement jnextcurrenttemptail第13页，共25页，编辑于2022年，星期一 template T LinkedList:remove(int index)if(index=0)return removeFirst();else if(index=size-1)return removeLast();else Node *previous=head;for(int j=1;jnext;Node *current=previous-next;previous-next=current-next size-;T element=current-element;delete
12、 current;return element;element1nextelement inextelement nNULLelement knextelement jnextcurrentpevious第14页，共25页，编辑于2022年，星期一 template T LinkedList:clear()while(head!=NULL)Node temp=head;delete temp;head=head-next;tail=NULL;size=0;element1nextelement inextelement nNULLelement knextelement jnexttemp第1
13、5页，共25页，编辑于2022年，星期一01nmaxtop栈空pushpopa an n.a a1 1a a0 001nmaxtop一般状态pushpopa amaxmax.a an n.a a1 1a a0 001nmaxtop栈满pushpopLIFO第16页，共25页，编辑于2022年，星期一 特殊的线性群体：栈（特殊的线性群体：栈（Stack）类）类 栈是一种特殊的线性群体，因此栈可以用数组或链表表示存储.但由于对栈中的元素的访问是受限制的，所以需要设计专门的栈类。要完整地保存栈的信息，栈类的数据成员至少要包括栈元素和栈顶指针。由于栈元素可以用数组或链表来表示，栈的结构也就有了两种：基
14、于数组（静态或动态数组）、基于链表。栈的基本状态有：一般状态、栈空、栈满。栈的基本操作有：初始化、入栈、出栈、栈清空、访问栈顶元素、检测栈状态等。第17页，共25页，编辑于2022年，星期一 栈类模板（基于链表）栈类模板（基于链表）template class Stack private:LinkedList list;public:Stack();void push(T value);T pop();int getsize();T peek();bool isEmpty();void clear();第18页，共25页，编辑于2022年，星期一 template Void Stack:pus
15、h(T value)list.addLast(T value);template T Stack:pop()return list.removeLast();template int Stack:getsize()return list.getsize();第19页，共25页，编辑于2022年，星期一 template Stack:Stack()template bool Stack:isEmpty()return list.isEmpty();template T Stack:peek()return list.getlast();template void Stack:clear()lis
16、t.clear();第20页，共25页，编辑于2022年，星期一 特殊的线性群体：队列（特殊的线性群体：队列（Queue）类）类 队列也是一种特殊的线性群体，因此同样可以用数组或链表表示存储，与栈一样队列中的元素的访问是受限制的，只能在一端（队头）删除元素（出队），在另一端（队尾）添加元素（入队）。由于队列操作不同于一般线性群体的操作，所以需要设计专门的队列类。由于队列元素可以用数组或链表来表示，队列的结构也就有了两种：基于数组（静态或动态数组），基于链表。队列的数据成员应包括：队列元素，队头指针，队尾指针 队列的基本状态有：一般状态、队空、队满。队列的基本操作有：初始化、入队、出队、队列清空
17、、访问队首元素、检测队列状态等。第21页，共25页，编辑于2022年，星期一 队尾队头出队入队队头队尾队头队尾队头队尾FIFO第22页，共25页，编辑于2022年，星期一 队列类模板（基于链表）队列类模板（基于链表）template class Queue private:LinkedList list;public:Queue();void enQueue(T elemnet);T deQueue();int getsize();T frontQueue();bool isEmpty();void clear();第23页，共25页，编辑于2022年，星期一 template Queue:Q
18、ueue()template bool Queue:isEmpty()return list.isEmpty();template T Queue:frontQueue()return list.getfirstt();template void Queue:clear()list.clear();第24页，共25页，编辑于2022年，星期一 template Void Queue:enQueue(T element)list.addLast(element);template T Queue:deQueue()return list.removeFirst();第25页，共25页，编辑于2022年，星期一