《线性群体类.ppt》由会员分享，可在线阅读，更多相关《线性群体类.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性群体类线性群体类 自定义类型的数据是由多个基本类型或自定义类型的元素组成的。我们称之为群体数据。对于群体数据，仅有系统预定义的操作是不够的，在很多情况下，还需要设计与某些具体问题相关的特殊操作，并按照面向对象的方法将数据域操作封装起来，形成群体类。群体类可分为两种：线性群体类和非线性群体类线性群体类和非线性群体类 线性群体类中的元素按位置排列有序，可以区分为第一个元素，第二个元素等等。非线性群体类中的元素不按位置排列顺序来标识元素。线性群体数据的访问：可以直接访问群体中的任意一个元素。（直接访问直接访问）按元素的排列顺序从头开始依次访问各个元素。（顺序访问顺序访问）直接访问群体：数组（直接
2、访问群体：数组（Array）类类 静态数组的大小在编译时已经确定，运行时无法改变大小，且无法有效地避免下标越界。我们可以设计动态的Array类模板。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&operator (int i);int getsize();.;顺序访问群体：链表（顺序访问群体：链表（Linked List）类类
3、在软件设计中，经常会遇到这样的问题：需要处理和表示一个线性群体，但是其中元素的个数无法预先确定，这时就必须应用动态数据结构，在程序运行期间根据问题动态申请内存，并建立这些数据之间的线性关系。链表是一种动态数据结构，可以用来表示顺序访问的线性群体。链表由一系列结点（node）构成，结点可以在运行过程中动态生成。data1data2data3data nNULL头结点（head）尾结点（tail）单链表示意图数据域指针域结点类模板结点类模板 template class Node public:T element;Node*next;Node()next=NULL;Node(T element)t
4、his-element=element;next=NULL;element1nextelement2nextElement nNULL Node*head,*tail;链表为空时：head=tail=NULL;产生链表的第一个结点：head=new Node(“Chicago”);tail=head;产生链表的第二个结点：tail-next=new Node(“Denver”);tail=tail-next;产生链表的第三个结点：tail-next=new Node(“Los angles”);tail=tail-next;element1nextelement2nextElement nNU
5、LLheadtail 遍历（遍历（traverse）所有结点：所有结点：Node*current;for(current=head;current;current=current-next)coutelementendl;element1nextelement2nextElement nNULLheadtail 链表类模板链表类模板按照面向对象的方法，将节点与操作封装起来，便构成链表类按照面向对象的方法，将节点与操作封装起来，便构成链表类 template class LinkedList private:Node*head,*tail;int size;public:LinkedList()
6、;void addFirst(T element);void addLast(T element);void add(int index,T element);T removeFirst();T removeLast();T remove(int index);bool isEmpty();void clear();T getLast(int index);；template LinkedList:LinkedList()head=tail=NULL;size=0;template void LinkedList:addFirst()Node*newNode;newNode=new Node(
7、element);newNode-next=head;head=newNode;size+;if(tail=NULL)tail=head;element1nextelement2nextheadelement1nextnewNode tail tail headelement1nextnewNodeNULL template void LinkedList:addLast()if(tail=NULL)head=tail=new Node(element);else tail-next=new Node(element);tail=tail-next;size+;element1nextelem
8、ent nNULLheadelementNULLnewNode tail tail headelement1nextnewNodeNULL 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=
9、temp;size+;element1nextelement inextelement nNULLelement jnextelementNULLcurrenttempnewnode 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 templa
10、te T LinkedList:removeLast()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
11、nNULLelement knextelement jnextcurrenttemptail 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 curr
12、ent;return element;element1nextelement inextelement nNULLelement knextelement jnextcurrentpevious template T LinkedList:clear()while(head!=NULL)Node temp=head;delete temp;head=head-next;tail=NULL;size=0;element1nextelement inextelement nNULLelement knextelement jnexttemp01nmaxtop栈空pushpopa an n.a a1
13、 1a a0 001nmaxtop一般状态pushpopa amaxmax.a an n.a a1 1a a0 001nmaxtop栈满pushpopLIFO 特殊的线性群体：栈（特殊的线性群体：栈（Stack）类类 栈是一种特殊的线性群体，因此栈可以用数组或链表表示存储.但由于对栈中的元素的访问是受限制的，所以需要设计专门的栈类。要完整地保存栈的信息，栈类的数据成员至少要包括栈元素和栈顶指针。由于栈元素可以用数组或链表来表示，栈的结构也就有了两种：基于数组（静态或动态数组）、基于链表。栈的基本状态有：一般状态、栈空、栈满。栈的基本操作有：初始化、入栈、出栈、栈清空、访问栈顶元素、检测栈状态等
14、。栈类模板（基于链表）栈类模板（基于链表）template class Stack private:LinkedList list;public:Stack();void push(T value);T pop();int getsize();T peek();bool isEmpty();void clear();template Void Stack:push(T value)list.addLast(T value);template T Stack:pop()return list.removeLast();template int Stack:getsize()return list
15、.getsize();template Stack:Stack()template bool Stack:isEmpty()return list.isEmpty();template T Stack:peek()return list.getlast();template void Stack:clear()list.clear();特殊的线性群体：队列（特殊的线性群体：队列（Queue）类类 队列也是一种特殊的线性群体，因此同样可以用数组或链表表示存储，与栈一样队列中的元素的访问是受限制的，只能在一端（队头）删除元素（出队），在另一端（队尾）添加元素（入队）。由于队列操作不同于一般线性群体
16、的操作，所以需要设计专门的队列类。由于队列元素可以用数组或链表来表示，队列的结构也就有了两种：基于数组（静态或动态数组），基于链表。队列的数据成员应包括：队列元素，队头指针，队尾指针 队列的基本状态有：一般状态、队空、队满。队列的基本操作有：初始化、入队、出队、队列清空、访问队首元素、检测队列状态等。队尾队头出队入队队头队尾队头队尾队头队尾FIFO 队列类模板（基于链表）队列类模板（基于链表）template class Queue private:LinkedList list;public:Queue();void enQueue(T elemnet);T deQueue();int ge
17、tsize();T frontQueue();bool isEmpty();void clear();template Queue:Queue()template bool Queue:isEmpty()return list.isEmpty();template T Queue:frontQueue()return list.getfirstt();template void Queue:clear()list.clear();template Void Queue:enQueue(T element)list.addLast(element);template T Queue:deQueue()return list.removeFirst();