精品数据结构Lists

1、listsa list is a finite, ordered sequence of data items.important concept: list elements have a position.notation: what operations should we implement?list implementation conceptsour list implementation will support the concept of a current position.we will do this by defining the list in terms of l

2、eft and right partitions. either or both partitions may be empty.partitions are separated by the fence.list adt page 90 template class list public: virtual void clear() = 0; virtual bool insert(const elem&) = 0; virtual bool append(const elem&) = 0; virtual bool remove(elem&) = 0; virtua

3、l void setstart() = 0; virtual void setend() = 0; virtual void prev() = 0; virtual void next() = 0; virtual int leftlength() const = 0; virtual int rightlength() const = 0; virtual bool setpos(int pos) = 0; virtual bool getvalue(elem&) const =0; virtual void print() const = 0; ;list adt (continu

4、e)array-based list insertarray-based list class page 93 template class alist : public list private: int maxsize; int listsize; int fence; elem* listarray; public: alist(int size=defaultlistsize) maxsize = size; listsize = fence = 0; listarray = new elemmaxsize; array-based listmaximum size of listac

5、tual elem countposition of fencearray holding listalist() delete listarray; void clear() delete listarray; listsize = fence = 0; listarray = new elemmaxsize;void setstart() fence = 0; void setend() fence = listsize; void prev() if (fence != 0) fence-; void next() if (fence = 0) & (pos = 0) &

6、 (pos = listsize);bool getvalue(elem& it) const if (rightlength() = 0) return false; else it = listarrayfence; return true; inserttemplate bool alist:insert(const elem& item) if (listsize = maxsize) return false; for(int i=listsize; ifence; i-) listarrayi = listarrayi-1; listarrayfence = ite

7、m; listsize+; return true;insert at front of right partition shift elems up to make room increment list sizeappendtemplate bool alist:append(const elem& item) if (listsize = maxsize) return false; listarraylistsize+ = item; return true;append elem to end of the listremovetemplate bool alist:remo

8、ve(elem& it) if (rightlength() = 0) return false; it = listarrayfence; for(int i=fence; ilistsize-1; i+) listarrayi = listarrayi+1; listsize-; return true;remove and return first elem in rightpartition copy elem shift them down decrement sizemain#include #include alist.h“void main() / declare so

9、me sample lists alist l1; alist l2(26); int i, j; coutlist l1 is: ; for(i=0; i5; i+) j=i*2+1; l1.insert(j); for(i=1; i6; i+) j=i*2; l1.append(j); l1.print(); coutnlist l1 move next 2 pos: ; l1.setstart(); l1.next(); l1.next(); l1.print(); coutnlist l1 remove: ; l1.remove(j); l1.print(); coutremove e

10、lem is j endl; coutnlist l1 insert 39: ; j=39; l1.insert(j); l1.print(); char c; coutnlist l2 is: ; for(i=0; i26; i+) c=i+65; l2.append(c); for(i=0; i13; i+)l2.next(); l2.print();resultlist l1 is: list l1 move next 2 pos: list l1 remove: remove elem is 5list l1 insert 39: list l2 is: link classdynam

11、ic allocation of new list elements.template class link public: elem element; link *next; link(const elem& elemval, link* nextval =null) element = elemval; next = nextval; link(link* nextval =null) next = nextval; ;singly-linked list nodevalue for this nodepointer to next nodetemplate class llist

12、 : public list private: link* head; link* tail; link* fence; int leftcnt; int rightcnt; void init() fence = tail = head = new link; leftcnt = rightcnt = 0; point to list headerpointer to last elemlast element on left size of leftsize of rightvoid removeall() while(head != null) fence = head; head =

13、head-next; delete fence; public: llist(int size=defaultlistsize) init(); llist() removeall(); void clear() removeall(); init(); page 97return link nodes to free storedestructorlinked list class (add) template int llist:find(const elem&x)/* search elem x,return -1 if not find, otherwise return po

14、sition of x */ link *q = head-next; int i=0; while(q& q-element!=x) q=q-next, i+; if(q) return i; else return -1; templatellist: llist(const llist&copy) / copy constructor init(); link *s = head, *q = head-next, *p=copy.head-next ; while(p) q = new link(p-element); s-next = q; s = q; p = p-n

15、ext; setpos(copy.leftcnt); template llist& llist: operator=(llist& copy) / overloaded assignment = if (copy.size() = 0) clear(); else link *s = head, *q = head-next, *p = copy.head-next ; while ( p & q ) q-element=p-element; s=q, q=q-next; p=p-next; / continue if(q) do p=q-next; delete q

16、; q=p; while(q); else while(p) q = new link(p-element); s-next = q; s = q; p = p-next; setpos(copy.leftcnt); return *this;/* 求整数集合求整数集合a = (a-b)(b-a) （求集合（求集合a、 b的对称差存入集合的对称差存入集合a）。）。算法思路：算法思路： 分别用带头结点的单链表分别用带头结点的单链表la lb表示集合表示集合a和和b， 用用for循环逐个从循环逐个从lb表中取元素存入表中取元素存入x中，中， 在在la表中查找表中查找x，若找到，则，若找到，则xab

17、，将，将x从从 la表删除；否则表删除；否则xba，将，将x插入插入la表，表， for循环结束算法完成；此时循环结束算法完成；此时la表代表所求的表代表所求的 (a-b)(b-a)集合，集合，lb保持不变。保持不变。 #include #include #include llist.hvoid symm_diff(llist&, llist&); / 求以单链表存储的两个集合求以单链表存储的两个集合“对称差对称差”之原型之原型(prototype)声声明明void crtlinklist(llist&,int); /为集合产生若干互不相等的整数插入链表的原型声明为集合

18、产生若干互不相等的整数插入链表的原型声明void setunion(llist&,llist&);/ 求以单链表存储的两个集合求以单链表存储的两个集合“并并”之原型声明之原型声明void main() llist la, lb, lc; int s1, s2; / s1, s2是存放是存放la,lb大小的变量大小的变量 time_t t; srand(unsigned)time(&t); /初始化随时间变化的随机数种子初始化随时间变化的随机数种子 couts1s2; / 输入集合输入集合a,b元素数元素数 coutnset a = | ; / 输出集合输出集合a的名称的

19、名称 crtlinklist(la,s1); / 创建集合创建集合a,输出集合元素输出集合元素 coutn length=s1nnset b = | ; / 输出集合输出集合b的名称的名称 / continue crtlinklist(lb,s2); / 创建集合创建集合b,输出集合元素输出集合元素 coutn length=s2nnc=a is ; lc=la; lc.print(); cout n length=s1nn(a-b)(b-a) = ; symm_diff(la,lb); / la = (a-b)(b-a) la.print(); coutlist la now length

20、= la.size()endl; cout nn cb=; setunion(lc,lb); lc.print(); llist ld(la); cout nn ld=; ld.print(); void crtlinklist(llist& l , int n) / 为链表为链表l产生产生n个互不相等的整数插入表个互不相等的整数插入表尾尾 int x,i,j ; for(i=0; in; i+) / 用随机数发生器产生用随机数发生器产生n个集合元素个集合元素,不得重复不得重复 do x=rand() % 37; / 产生产生0-36间的随机整数间的随机整数 while(j=l.fin

21、d(x)!=-1); / 在集合中找在集合中找x, 找不到则脱离循环找不到则脱离循环 l.append(x); / 插入表尾插入表尾 coutx ; / 输出输出x ( 集合元素边产生边输出集合元素边产生边输出) void symm_diff(llist& la, llist& lb) int x,i; lb.setstart(); for(int j=0; jlb.size(); j+) lb.getvalue(x); / 取集合取集合b的元素的元素 lb.next(); if (i=la.find(x) = -1) / 集合集合b的元素不在的元素不在a中中 la.inser

22、t(x); / 插入插入a集合集合 else / 集合集合b的元素在的元素在a中中,删除之删除之 la.setpos(i); la.remove(x); void setunion(llist&la,llist&lb)/ 将将la表和表和lb表所表示的集合做表所表示的集合做并并，存入，存入la表，表，lb表被清空。表被清空。int i,k,b; lb.setstart(); for (i=lb.size(); i0; i-) / 从从lb表中逐次删除素尾元素，这样不必移动元素表中逐次删除素尾元素，这样不必移动元素 lb.remove(b); / 调用删除算法，被删元素存入调用删

23、除算法，被删元素存入b k=la.find(b); / 在在la表中查找表中查找b if(k=-1) / la表中找不到元素表中找不到元素b la.insert(b); / 插入至插入至la表尾表尾 / end_forcomparison of implementationsarray-based lists: insertion and deletion are (n). prev and direct access are (1). array must be allocated in advance. no overhead if all array positions are full

24、.linked lists: insertion and deletion are (1). prev and direct access are (n). space grows with number of elements. every element requires overhead.space comparison“break-even” point:de = n(p + e);n = de p + ee: space for data value.p: space for pointer.d: number of elements in array.freelistssystem

25、 new and delete are slow./ singly-linked list node with freelisttemplate class link private: static link* freelist; / headpublic: elem element; / value for this node link* next; / point to next node link(const elem& elemval, link* nextval =null) element = elemval; next = nextval; link(link* next

26、val =null) next=nextval; void* operator new(size_t); / overload void operator delete(void*); / overload;freelists (2)template link* link:freelist = null;template / overload for newvoid* link:operator new(size_t) if (freelist = null) return :new link; link* temp = freelist; / reuse freelist = freelis

27、t-next; return temp; / return the linktemplate / overload deletevoid link:operator delete(void* ptr) (link*)ptr)-next = freelist; freelist = (link*)ptr;doubly linked listssimplify insertion and deletion: add a prev pointer./ doubly-linked list link nodetemplate class link public: elem element; / val

28、ue for this node link *next; / pointer to next node link *prev; / pointer to previous node link(const elem& e, link* prevp =null, link* nextp =null) element=e; prev=prevp; next=nextp; link(link* prevp =null, link* nextp =null) prev = prevp; next = nextp; ;doubly linked listsdoubly linked insertd

29、oubly linked insert/ insert at front of right partitiontemplate bool llist:insert(const elem& item) fence-next = new link(item, fence, fence-next); if (fence-next-next != null) fence-next-next-prev = fence-next; if (tail = fence) / appending new elem tail = fence-next; / so set tail rightcnt+; /

30、 added to right return true;doubly linked removedoubly linked remove/ remove, return first elem in right parttemplate bool llist:remove(elem& it) if (fence-next = null) return false; it = fence-next-element; link* ltemp = fence-next; if (ltemp-next != null) ltemp-next-prev = fence; else tail = f

31、ence; / reset tail fence-next = ltemp-next; / remove delete ltemp; / reclaim space rightcnt-; / removed from right return true;dictionaryoften want to insert records, delete records, search for records.required concepts: search key: describe what we are looking for key comparison equality: sequentia

32、l search relative order: sorting record comparisoncomparator classhow do we generalize comparison? use =, =: disastrous overload =, =: disastrous define a function with a standard name implied obligation breaks down with multiple key fields/indices for same object pass in a function explicit obligat

33、ion function parameter template parametercomparator exampleclass intintcompare public: static bool lt(int x, int y) return x y; ;comparator example (2)class payroll public: int id; char* name;class idcompare public: static bool lt(payroll& x, payroll& y) return x.id y.id; ;class namecompare

34、public: static bool lt(payroll& x, payroll& y) return strcmp(, ) 0; ;dictionary adt/ the dictionary abstract class.template class dictionary public: virtual void clear() = 0; virtual bool insert(const elem&) = 0; virtual bool remove(const key&, elem&) = 0; virtual boo

35、l removeany(elem&) = 0; virtual bool find(const key&, elem&) const = 0; virtual int size() = 0;unsorted list dictionarytemplate class ualdict : public dictionary private: alist* list;public:bool remove(const key& k, elem& e) for(list-setstart(); list-getvalue(e); list-next() if (kecomp:eq(k, e) list-remove(e); return true; return false; ;stackslifo: last in, first out.restricted form of list: insert and remove only at front of list.notation: insert: push remove: pop th