《线性表、栈和队列》由会员分享，可在线阅读，更多相关《线性表、栈和队列（60页珍藏版）》请在金锄头文库上搜索。
1、1线性表、栈和队列线性表、栈和队列2数据逻辑关系 数据元素可存在于非空有限集合中数据元素可存在于非空有限集合中 26个英文字母表26个英文字母表（A，B，C，（A，B，C，Z）某校从1978年到1983年各种型号计算机拥有量的 变化情况，Z）某校从1978年到1983年各种型号计算机拥有量的 变化情况（6，17，28，50，92，188）一个学校的学生健康情况登记表（6，17，28，50，92，188）一个学校的学生健康情况登记表一般计9319男050102李四 健康健康状况健康状况计93班级班级18年龄年龄男性别性别050101学号学号张三姓名姓名3线性结构的线性结构的基本特征基本特征为:为
2、:线性结构 是线性结构 是 一个数据元素的一个数据元素的有序（次序）集有序（次序）集1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ；3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。最简单的线性结构线性结构称为称为线性表线性表4Lists线性表是由数据项组成的一种有限且有序的序列线性表是由数据项组成的一种有限且有序的序列.重要的概念重要的概念: 线性表中的每一个元素都有自己的位置线性表中的每一个元素都有自己的位置. 每一个
3、元素都有一种数据类型每一个元素都有一种数据类型 线性表中不包含任何元素时，称为空表线性表中不包含任何元素时，称为空表。 当前存储的元素数目称为线性表的长度当前存储的元素数目称为线性表的长度。 线性表的开始结点称为表头线性表的开始结点称为表头（head） 线性表的结尾结点称为表尾线性表的结尾结点称为表尾（tail） 有序线性表有序线性表的元素按照值的递增顺序排列，而无序线的元素按照值的递增顺序排列，而无序线 性表性表在元素的值与位置之间就没有特殊的联系。在元素的值与位置之间就没有特殊的联系。表示法表示法: 我们将实现什么操作呢我们将实现什么操作呢?5线性表 ADT template class
4、List public: virtual void clear() = 0; virtual bool insert(const Elem virtual bool append(const Elem virtual bool remove(Elem virtual void setStart() = 0; virtual void setEnd() = 0; virtual void prev() = 0; virtual void next() = 0; virtual int leftLength() const = 0; virtual int rightLength() const
5、= 0; virtual bool setPos(int pos) = 0; virtual bool getValue(Elem virtual void print() const = 0; ;6线性表实现中的一些概念我们在线性表中将实现对当前位置我们在线性表中将实现对当前位置的支持的支持.为了定义当前位置的概念，假设线性表由左、 右两个分离部分组成为了定义当前位置的概念，假设线性表由左、 右两个分离部分组成. 其中任一部分或两者可以为空其中任一部分或两者可以为空.这两个部分被一个栅栏这两个部分被一个栅栏（fence）分开）分开.7List ADT ExamplesList: MyList
6、.insert(99);Result: Iterate through the whole list:for (MyList.setStart(); MyList.getValue(it); MyList.next() DoSomething(it);8List Find Function/ Return true iff K is in list bool find(List for (L.setStart(); L.getValue(it); L.next() if (K = it) return true; / Found it return false; / Not found 9线性
7、表的实现 线性表的实现有两种标准方法线性表的实现有两种标准方法 顺序表（顺序表（array-based list） 链表（链表（linked list） 顺序表的实现方法顺序表的实现方法 链表的实现方法链表的实现方法 比较两种方式的时间、空间效率比较两种方式的时间、空间效率10Array-Based List Insert11Array-Based List Class (1)template / Array-based list class AList : public List private: int maxSize; / Maximum size of list int listSiz
8、e; / Actual elem count int fence; / Position of fence Elem* listArray; / Array holding list public: AList(int size=DefaultListSize) maxSize = size; listSize = fence = 0; listArray = new ElemmaxSize; 12Array-Based List Class (2)AList() delete listArray; void clear() delete listArray; listSize = fence
9、 = 0; listArray = new ElemmaxSize; void setStart() fence = 0; void setEnd() fence = listSize; void prev() if (fence != 0) fence-; void next() if (fence = 0) listArraylistSize+ = item; return true; 15Insert/ Insert at front of right partition template bool AList:insert(const Elem for(int i=listSize;
10、ifence; i-) / Shift Elems up to make room listArrayi = listArrayi-1; listArrayfence = item; listSize+; / Increment list size return true; 16Remove/ Remove and return first Elem in right / partition template bool AList:remove(Elem it = listArrayfence; / Copy Elem for(int i=fence; i class Link public:
11、 Elem element; / Value for this node Link *next; / Pointer to next node Link(const Elem next = nextval; Link(Link* nextval =NULL) next = nextval; ;19Linked List Position (1)20Linked List Position (2)21Linked List Class (1)/ Linked list implementation template class LList: public List private: Link*
12、head; / Point to list header Link* tail; / Pointer to last ElemLink* fence;/ Last element on left int leftcnt; / Size of left int rightcnt; / Size of right22Linked List Class (2)void init() / Intialization routine fence = tail = head = new Link; leftcnt = rightcnt = 0; void removeall() / Return link
13、 nodes to free store while(head != NULL) fence = head; head = head-next; delete fence; public: LList(int size=DefaultListSize) init(); LList() removeall(); / Destructor void clear() removeall(); init(); 23Linked List Class (3)void setStart() fence = head; rightcnt += leftcnt;leftcnt = 0; void setEnd
14、() fence = tail; leftcnt += rightcnt;rightcnt = 0; void next() / Dont move fence if right emptyif (fence != tail) fence = fence-next; rightcnt-; leftcnt+; int leftLength() const return leftcnt; int rightLength() const return rightcnt; bool getValue(Elemit = fence-next-element;return true; 24Insertio
15、n25Insert/Append/ Insert at front of right partition template bool LList:insert(const Elem if (tail = fence) tail = fence-next; rightcnt+; return true;/ Append Elem to end of the list template bool LList:append(const Elem rightcnt+; return true;26Removal27Remove/ Remove and return first Elem in right / partition template bool LList:remove(Elem it = fence-next-element; / Remember val / Remember link node Link* ltemp = fence-next; fence-next = ltemp-next; / Remove if (tail = ltemp) / Reset tail tail = fence; delete l
