版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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 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;/* 求整數(shù)集合求整數(shù)集合a = (a-b)(b-a) (求集合(求集合a、 b的對(duì)稱差存入集合的對(duì)稱差存入集合a)。)。算法思路:算法思路: 分別用帶頭結(jié)點(diǎn)的單鏈表分別用帶頭結(jié)點(diǎn)的單鏈表la lb表示集合表示集合a和和b, 用用for循環(huán)逐個(gè)從循環(huán)逐個(gè)從lb表中取元素存入表中取元素存入x中,中, 在在la表中查找表中查找x,若找到,則,若找到,則xab
17、,將,將x從從 la表刪除;否則表刪除;否則xba,將,將x插入插入la表,表, for循環(huán)結(jié)束算法完成;此時(shí)循環(huán)結(jié)束算法完成;此時(shí)la表代表所求的表代表所求的 (a-b)(b-a)集合,集合,lb保持不變。保持不變。 #include #include #include llist.hvoid symm_diff(llist&, llist&); / 求以單鏈表存儲(chǔ)的兩個(gè)集合求以單鏈表存儲(chǔ)的兩個(gè)集合“對(duì)稱差對(duì)稱差”之原型之原型(prototype)聲聲明明void crtlinklist(llist&,int); /為集合產(chǎn)生若干互不相等的整數(shù)插入鏈表的原型聲明為集合
18、產(chǎn)生若干互不相等的整數(shù)插入鏈表的原型聲明void setunion(llist&,llist&);/ 求以單鏈表存儲(chǔ)的兩個(gè)集合求以單鏈表存儲(chǔ)的兩個(gè)集合“并并”之原型聲明之原型聲明void main() llist la, lb, lc; int s1, s2; / s1, s2是存放是存放la,lb大小的變量大小的變量 time_t t; srand(unsigned)time(&t); /初始化隨時(shí)間變化的隨機(jī)數(shù)種子初始化隨時(shí)間變化的隨機(jī)數(shù)種子 couts1s2; / 輸入集合輸入集合a,b元素?cái)?shù)元素?cái)?shù) coutnset a = | ; / 輸出集合輸出集合a的名稱的
19、名稱 crtlinklist(la,s1); / 創(chuàng)建集合創(chuàng)建集合a,輸出集合元素輸出集合元素 coutn length=s1nnset b = | ; / 輸出集合輸出集合b的名稱的名稱 / continue crtlinklist(lb,s2); / 創(chuàng)建集合創(chuàng)建集合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產(chǎn)生產(chǎn)生n個(gè)互不相等的整數(shù)插入表個(gè)互不相等的整數(shù)插入表尾尾 int x,i,j ; for(i=0; in; i+) / 用隨機(jī)數(shù)發(fā)生器產(chǎn)生用隨機(jī)數(shù)發(fā)生器產(chǎn)生n個(gè)集合元素個(gè)集合元素,不得重復(fù)不得重復(fù) do x=rand() % 37; / 產(chǎn)生產(chǎn)生0-36間的隨機(jī)整數(shù)間的隨機(jī)整數(shù) while(j=l.fin
21、d(x)!=-1); / 在集合中找在集合中找x, 找不到則脫離循環(huán)找不到則脫離循環(huán) l.append(x); / 插入表尾插入表尾 coutx ; / 輸出輸出x ( 集合元素邊產(chǎn)生邊輸出集合元素邊產(chǎn)生邊輸出) 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表中逐次刪除素尾元素,這樣不必移動(dòng)元素表中逐次刪除素尾元素,這樣不必移動(dòng)元素 lb.remove(b); / 調(diào)用刪除算法,被刪元素存入調(diào)用刪
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 《證據(jù)習(xí)題刑訴法》課件
- 江蘇省鎮(zhèn)江一中等2025屆高考考前模擬英語試題含解析
- 14.1《故都的秋》課件 2024-2025學(xué)年統(tǒng)編版高中語文必修上冊
- 2025屆山東省威海市乳山一中高考沖刺押題(最后一卷)數(shù)學(xué)試卷含解析
- 2025屆山東省微山二中高考數(shù)學(xué)三模試卷含解析
- 2025屆上海市虹口區(qū)復(fù)興高中高考考前模擬數(shù)學(xué)試題含解析
- 10.1《勸學(xué)》課件 2024-2025學(xué)年統(tǒng)編版高中語文必修上冊-3
- 湖南省邵陽市邵東縣創(chuàng)新實(shí)驗(yàn)學(xué)校2025屆高三第三次模擬考試英語試卷含解析
- 河南省駐馬店市2025屆高考考前模擬數(shù)學(xué)試題含解析
- 全國普通高等學(xué)校招生統(tǒng)一考試2025屆高考語文五模試卷含解析
- MOOC 英文技術(shù)寫作-東南大學(xué) 中國大學(xué)慕課答案
- JGJ_T231-2021建筑施工承插型盤扣式鋼管腳手架安全技術(shù)標(biāo)準(zhǔn)(高清-最新版)
- 畢業(yè)論文(設(shè)計(jì))除雪車工作裝置設(shè)計(jì)
- 交通工程精細(xì)化施工質(zhì)量控制及驗(yàn)收標(biāo)準(zhǔn)
- 鏡片加工知識(shí)之四研磨
- 核電站1E級(jí)電氣設(shè)備鑒定標(biāo)準(zhǔn)技術(shù)經(jīng)驗(yàn)
- 乒乓球中的力學(xué)原理PPT課件
- 激光原理與激光技術(shù)習(xí)題全解(北工大)
- 中央空調(diào)設(shè)備運(yùn)行管理方案課案
- 預(yù)算單位財(cái)務(wù)服務(wù)平臺(tái)-出納管理操作手冊
- 在全市裝備制造業(yè)現(xiàn)場推進(jìn)會(huì)上的講話
評(píng)論
0/150
提交評(píng)論