數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)筆記

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第一章 概 論1.數(shù)據(jù)：信息的載體,能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。2.數(shù)據(jù)元素：數(shù)據(jù)的基本單位，可由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。3.數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。它包括：1）數(shù)據(jù)的邏輯結(jié)構(gòu)，從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)存儲(chǔ)無(wú)關(guān)，獨(dú)立于計(jì)算機(jī)；2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)，依賴(lài)于計(jì)算機(jī)語(yǔ)言。3）數(shù)據(jù)的運(yùn)算，定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的運(yùn)算：檢索/插入/刪除/更新/排序。4.數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。5.數(shù)據(jù)類(lèi)

2、型：一個(gè)值的集合及在值上定義的一組操作的總稱(chēng)。分為：原子類(lèi)型和結(jié)構(gòu)類(lèi)型。6.抽象數(shù)據(jù)類(lèi)型：抽象數(shù)據(jù)的組織和與之相關(guān)的操作。優(yōu)點(diǎn)：將數(shù)據(jù)和操作封裝在一起實(shí)現(xiàn)了信息隱藏。7. 抽象數(shù)據(jù)類(lèi)型ADT：是在概念層上描述問(wèn)題；類(lèi)：是在實(shí)現(xiàn)層上描述問(wèn)題；在應(yīng)用層上操作對(duì)象（類(lèi)的實(shí)例）解決問(wèn)題。8.數(shù)據(jù)的邏輯結(jié)構(gòu)，簡(jiǎn)稱(chēng)為數(shù)據(jù)結(jié)構(gòu)，有：（1）線(xiàn)性結(jié)構(gòu)，若結(jié)構(gòu)是非空集則僅有一個(gè)開(kāi)始和終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)最多只有一個(gè)直接前趨和后繼。（2）非線(xiàn)性結(jié)構(gòu)，一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和后繼。9.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有：1）順序存儲(chǔ)，把邏輯相鄰的結(jié)點(diǎn)存儲(chǔ)在物理上相鄰的存儲(chǔ)單元內(nèi)。2）鏈接存儲(chǔ)，結(jié)點(diǎn)間的邏輯關(guān)系由附加指針字段表示。

3、3）索引存儲(chǔ)，存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，建立附加索引表，有稠密索引和稀疏索引。4）散列存儲(chǔ)，按結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出存儲(chǔ)地址。 10.評(píng)價(jià)算法的好壞是：算法是正確的；執(zhí)行算法所耗的時(shí)間；執(zhí)行算法的存儲(chǔ)空間（輔助存儲(chǔ)空間）；易于理解、編碼、調(diào)試。 11.算法的時(shí)間復(fù)雜度T(n)：是該算法的時(shí)間耗費(fèi)，是求解問(wèn)題規(guī)模n的函數(shù)。記為O(n)。時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為：常數(shù)階O(1)、對(duì)數(shù)階O(log2n)、線(xiàn)性階O(n)、線(xiàn)性對(duì)數(shù)階O(nlog2n)、平方階O(n2)、立方階O(n3)、k次方階O(nk)、指數(shù)階O(2n)。13.算法的空間復(fù)雜度S(n)：是該算法的空間耗費(fèi)，是求解問(wèn)題規(guī)模n的函數(shù)。

4、12.算法衡量：是用時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)衡量的，它們合稱(chēng)算法的復(fù)雜度。13. 算法中語(yǔ)句的頻度不僅與問(wèn)題規(guī)模有關(guān)，還與輸入實(shí)例中各元素的取值相關(guān)。 第 二 章 線(xiàn) 性 表 1.線(xiàn)性表：是由n(n0)個(gè)數(shù)據(jù)元素組成的有限序列。3.順序表：把線(xiàn)性表的結(jié)點(diǎn)按邏輯次序存放在一組地址連續(xù)的存儲(chǔ)單元里。4.順序表結(jié)點(diǎn)的存儲(chǔ)地址計(jì)算公式：Loc(ai)=Loc(a1)+(i-1)*C；1in 5.順序表上的基本運(yùn)算public interface List /返回線(xiàn)性表的大小，即數(shù)據(jù)元素的個(gè)數(shù)。public int getSize();/如果線(xiàn)性表為空返回 true，否則返回 false。public

5、boolean isEmpty();/判斷線(xiàn)性表是否包含數(shù)據(jù)元素 e public boolean contains(Object e);/將數(shù)據(jù)元素 e 插入到線(xiàn)性表中 i 號(hào)位置public void insert(int i, Object e) throws OutOfBoundaryException;/刪除線(xiàn)性表中序號(hào)為 i 的元素,并返回之public Object remove(int i) throws OutOfBoundaryException;/刪除線(xiàn)性表中第一個(gè)與 e 相同的元素public boolean remove(Object e);/返回線(xiàn)性表中序號(hào)為 i

6、的數(shù)據(jù)元素public Object get(int i) throws OutOfBoundaryException; 在順序表上插入要移動(dòng)表的n/2結(jié)點(diǎn)，算法的平均時(shí)間復(fù)雜度為O(n)。在順序表上刪除要移動(dòng)表的（n+1）/2結(jié)點(diǎn)，算法的平均時(shí)間復(fù)雜度為O(n)。 public class ListArray implements List private final int LEN = 8; /數(shù)組的默認(rèn)大小private Strategy strategy; /數(shù)據(jù)元素比較策略private int size; /線(xiàn)性表中數(shù)據(jù)元素的個(gè)數(shù)private Object elements; /

7、數(shù)據(jù)元素?cái)?shù)組/構(gòu)造方法public ListArray (Strategy strategy)size = 0;elements = new ObjectLEN;/返回線(xiàn)性表的大小，即數(shù)據(jù)元素的個(gè)數(shù)。public int getSize() return size;/如果線(xiàn)性表為空返回 true，否則返回 false。public boolean isEmpty() return size=0;/判斷線(xiàn)性表是否包含數(shù)據(jù)元素 e public boolean contains(Object e) for (int i=0; i<size; i+)if ( e = = elementsi)

8、return true;return false;/將數(shù)據(jù)元素 e 插入到線(xiàn)性表中 i 號(hào)位置public void insert(int i, Object e) throws OutOfBoundaryException if (i<0|i>size)throw new OutOfBoundaryException("錯(cuò)誤，指定的插入序號(hào)越界。");if (size >= elements.length)expandSpace();for (int j=size; j>i; j-)elementsj = elementsj-1; elements

9、i = e; size+;return;private void expandSpace()Object a = new Objectelements.length*2;for (int i=0; i<elements.length; i+)ai = elementsi;elements = a;/刪除線(xiàn)性表中序號(hào)為 i 的元素,并返回之public Object remove(int i) throws OutOfBoundaryException if (i<0|i>=size)throw new OutOfBoundaryException("錯(cuò)誤，指定的刪除

10、序號(hào)越界。");Object obj = elementsi;for (int j=i; j<size-1; j+)elementsj = elementsj+1;elements-size = null;return obj;/替換線(xiàn)性表中序號(hào)為 i 的數(shù)據(jù)元素為 e，返回原數(shù)據(jù)元素public Object replace(int i, Object e) throws OutOfBoundaryException if (i<0|i>=size)throw new OutOfBoundaryException("錯(cuò)誤，指定的序號(hào)越界。");

11、 Object obj = elementsi;elementsi = e;return obj;/返回線(xiàn)性表中序號(hào)為 i 的數(shù)據(jù)元素public Object get(int i) throws OutOfBoundaryException if (i<0|i>=size)throw new OutOfBoundaryException("錯(cuò)誤，指定的序號(hào)越界。");return elementsi;/刪除線(xiàn)性表中第一個(gè)與 e 相同的元素public boolean remove(Object e) int i = indexOf(e);if (i<0)

12、 return false;remove(i);return true;6.單鏈表：只有一個(gè)鏈域的鏈表稱(chēng)單鏈表。在結(jié)點(diǎn)中存儲(chǔ)結(jié)點(diǎn)值和結(jié)點(diǎn)的后繼結(jié)點(diǎn)的地址，data next data是數(shù)據(jù)域，next是指針域。 （1）建立單鏈表。時(shí)間復(fù)雜度為O(n)。加頭結(jié)點(diǎn)的優(yōu)點(diǎn)：1）鏈表第一個(gè)位置的操作無(wú)需特殊處理；2）將空表和非空表的處理統(tǒng)一。（2）查找運(yùn)算。時(shí)間復(fù)雜度為O(n)。 public class SLNode implements Node private Object element;private SLNode next;public SLNode(Object ele, SLNode

13、next)this.element = ele;this.next = next;public SLNode getNext()return next;public void setNext(SLNode next)this.next = next;public Object getData() return element;public void setData(Object obj) element = obj;public class ListSLinked implements List private SLNode head; /單鏈表首結(jié)點(diǎn)引用private int size; /

14、線(xiàn)性表中數(shù)據(jù)元素的個(gè)數(shù)public ListSLinked () head = new SLNode(); size = 0;/輔助方法：獲取數(shù)據(jù)元素 e 所在結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)private SLNode getPreNode(Object e) SLNode p = head;while (p.getNext()!=null) if (p.getNext().getData()=e) return p; else p = p.getNext();return null;/輔助方法：獲取序號(hào)為 0<=i<size 的元素所在結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)private SLNode getPreNo

15、de(int i) SLNode p = head; for (; i>0; i-) p = p.getNext(); return p;/獲取序號(hào)為 0<=i<size 的元素所在結(jié)點(diǎn)private SLNode getNode(int i) SLNode p = head.getNext(); for (; i>0; i-) p = p.getNext(); return p;/返回線(xiàn)性表的大小，即數(shù)據(jù)元素的個(gè)數(shù)。public int getSize() return size;/如果線(xiàn)性表為空返回 true，否則返回 false。public boolean is

16、Empty() return size=0;/判斷線(xiàn)性表是否包含數(shù)據(jù)元素 e public boolean contains(Object e) SLNode p = head.getNext(); while (p!=null) if (p.getData()=e) return true; else p = p.getNext(); return false;/將數(shù)據(jù)元素 e 插入到線(xiàn)性表中 i 號(hào)位置public void insert(int i, Object e) throws OutOfBoundaryException if (i<0|i>size) throw n

17、ew OutOfBoundaryException("錯(cuò)誤，指定的插入序號(hào)越界。"); SLNode p = getPreNode(i); SLNode q = new SLNode(e,p.getNext(); p.setNext(q); size+; return; /刪除線(xiàn)性表中序號(hào)為 i 的元素,并返回之public Object remove(int i) throws OutOfBoundaryException if (i<0|i>=size) throw new OutOfBoundaryException("錯(cuò)誤，指定的刪除序號(hào)越界。

18、"); SLNode p = getPreNode(i); Object obj = p.getNext().getData(); p.setNext(p.getNext().getNext(); size-; return obj;/刪除線(xiàn)性表中第一個(gè)與 e 相同的元素public boolean remove(Object e) SLNode p = getPreNode(e); if (p!=null) p.setNext(p.getNext().getNext(); size-; return true; return false;/替換線(xiàn)性表中序號(hào)為 i 的數(shù)據(jù)元素為 e，

19、返回原數(shù)據(jù)元素public Object replace(int i, Object e) throws OutOfBoundaryException if (i<0|i>=size) throw new OutOfBoundaryException("錯(cuò)誤，指定的序號(hào)越界。"); SLNode p = getNode(i); Object obj = p.getData(); p.setData(e); return obj;/返回線(xiàn)性表中序號(hào)為 i 的數(shù)據(jù)元素public Object get(int i) throws OutOfBoundaryExcep

20、tion if (i<0|i>=size) throw new OutOfBoundaryException("錯(cuò)誤，指定的序號(hào)越界。"); SLNode p = getNode(i); return p.getData();7.循環(huán)鏈表：是一種首尾相連的鏈表。特點(diǎn)是無(wú)需增加存儲(chǔ)量，僅對(duì)表的鏈接方式修改使表的處理靈活方便。8.空循環(huán)鏈表僅由一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。9.很多時(shí)候表的操作是在表的首尾位置上進(jìn)行，此時(shí)頭指針表示的單循環(huán)鏈表就顯的不夠方便，改用尾指針rear來(lái)表示單循環(huán)鏈表。用頭指針表示的單循環(huán)鏈表查找開(kāi)始結(jié)點(diǎn)的時(shí)間是O(1),查找尾結(jié)點(diǎn)的時(shí)間是O(n

21、)；用尾指針表示的單循環(huán)鏈表查找開(kāi)始結(jié)點(diǎn)和尾結(jié)點(diǎn)的時(shí)間都是O(1)。10.在結(jié)點(diǎn)中增加一個(gè)指針域，prior|data|next。形成的鏈表中有兩條不同方向的鏈稱(chēng)為雙鏈表。public class DLNode implements Node private Object element;private DLNode pre;private DLNode next;public DLNode(Object ele, DLNode pre, DLNode next)this.element = ele;this.pre = pre;this.next = next;public DLNode g

22、etNext()return next;public void setNext(DLNode next)this.next = next;public DLNode getPre() return pre;public void setPre(DLNode pre)this.pre = pre;public Object getData() return element;public void setData(Object obj) element = obj;public class LinkedListDLNode implements LinkedList private int siz

23、e; /規(guī)模 private DLNode head;/頭結(jié)點(diǎn),啞元結(jié)點(diǎn) private DLNode tail;/尾結(jié)點(diǎn),啞元結(jié)點(diǎn) public LinkedListDLNode() size = 0; head = new DLNode();/構(gòu)建只有頭尾結(jié)點(diǎn)的鏈表 tail = new DLNode(); head.setNext(tail); tail.setPre(head);/輔助方法，判斷結(jié)點(diǎn) p 是否合法，如合法轉(zhuǎn)換為 DLNodeprotected DLNode checkPosition(Node p) throws InvalidNodeException if (p=n

24、ull) throw new InvalidNodeException("錯(cuò)誤：p 為空。"); if (p=head) throw new InvalidNodeException("錯(cuò)誤：p 指向頭節(jié)點(diǎn)，非法。"); if (p=tail) throw new InvalidNodeException("錯(cuò)誤：p 指向尾結(jié)點(diǎn)，非法。"); DLNode node = (DLNode)p; return node;/查詢(xún)鏈接表當(dāng)前的規(guī)模public int getSize() return size;/判斷鏈接表是否為空public

25、 boolean isEmpty() return size=0;/返回第一個(gè)結(jié)點(diǎn)public Node first() throws OutOfBoundaryException if (isEmpty() throw new OutOfBoundaryException("錯(cuò)誤：鏈接表為空。"); return head.getNext();/返回最后一結(jié)點(diǎn)public Node last() throws OutOfBoundaryException if (isEmpty() throw new OutOfBoundaryException("錯(cuò)誤：鏈接表

26、為空。"); return tail.getPre();/返回 p 之后的結(jié)點(diǎn)public Node getNext(Node p)throws InvalidNodeException,OutOfBoundaryException DLNode node = checkPosition(p); node = node.getNext(); if (node=tail) throw new OutOfBoundaryException("錯(cuò)誤：已經(jīng)是鏈接表尾端。"); return node;/返回 p 之前的結(jié)點(diǎn)public Node getPre(Node p

27、) throws InvalidNodeException, OutOfBoundaryException DLNode node = checkPosition(p); node = node.getPre(); if (node=head) throw new OutOfBoundaryException("錯(cuò)誤：已經(jīng)是鏈接表前端。"); return node;/將 e 作為第一個(gè)元素插入鏈接表public Node insertFirst(Object e) DLNode node = new DLNode(e,head,head.getNext(); head.g

28、etNext().setPre(node); head.setNext(node); size+; return node;/將 e 作為最后一個(gè)元素插入列表,并返回 e 所在結(jié)點(diǎn)public Node insertLast(Object e) DLNode node = new DLNode(e,tail.getPre(),tail); tail.getPre().setNext(node); tail.setPre(node); size+; return node;/刪除給定位置處的元素，并返回之public Object remove(Node p) throws InvalidNod

29、eException DLNode node = checkPosition(p); Object obj = node.getData(); node.getPre().setNext(node.getNext(); node.getNext().setPre(node.getPre(); size-; return obj;/刪除首元素，并返回之public Object removeFirst() throws OutOfBoundaryException return remove(head.getNext();/刪除末元素，并返回之public Object removeLast()

30、 throws OutOfBoundaryException return remove(tail.getPre();/將處于給定位置的元素替換為新元素，并返回被替換的元素public Object replace(Node p, Object e) throws InvalidNodeException DLNode node = checkPosition(p); Object obj = node.getData(); node.setData(e); return obj;11.順序表和鏈表的比較1） 基于空間的考慮：順序表的存儲(chǔ)空間是靜態(tài)分配的，鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的。

31、順序表的存儲(chǔ)密度比鏈表大。因此，在線(xiàn)性表長(zhǎng)度變化不大，易于事先確定時(shí)，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)。2） 基于時(shí)間的考慮：順序表是隨機(jī)存取結(jié)構(gòu)，若線(xiàn)性表的操作主要是查找，很少有插入、刪除操作時(shí)，宜用順序表結(jié)構(gòu)。對(duì)頻繁進(jìn)行插入、刪除操作的線(xiàn)性表宜采用鏈表。若操作主要發(fā)生在表的首尾時(shí)采用尾指針表示的單循環(huán)鏈表。12.存儲(chǔ)密度=（結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量）/（整個(gè)結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量）存儲(chǔ)密度：順序表=1，鏈表<1。第 三 章   棧 和 隊(duì) 列  1.棧是限制僅在表的一端進(jìn)行插入和刪除

32、運(yùn)算的線(xiàn)性表又稱(chēng)為后進(jìn)先出表（LIFO表）。插入、刪除端稱(chēng)為棧頂，另一端稱(chēng)棧底。表中無(wú)元素稱(chēng)空棧。2.棧的基本運(yùn)算有：1） initstack(s),構(gòu)造一個(gè)空棧；2） stackempty(s),判棧空；3） stackfull(s),判棧滿(mǎn)；4） push(s,x),進(jìn)棧；5） pop (s),退棧；6） stacktop(s)，取棧頂元素。3.順序棧：棧的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)順序棧。4.當(dāng)棧滿(mǎn)時(shí)，做進(jìn)棧運(yùn)算必定產(chǎn)生空間溢出，稱(chēng)“上溢”。 當(dāng)?？諘r(shí)，做退棧運(yùn)算必定產(chǎn)生空間溢出，稱(chēng)“下溢”。上溢是一種錯(cuò)誤應(yīng)設(shè)法避免，下

33、溢常用作程序控制轉(zhuǎn)移的條件。5.在順序棧上的基本運(yùn)算：public interface Stack /返回堆棧的大小public int getSize();/判斷堆棧是否為空public boolean isEmpty();/數(shù)據(jù)元素 e 入棧public void push(Object e);/棧頂元素出棧public Object pop() throws StackEmptyException;/取棧頂元素public Object peek() throws StackEmptyException;public class StackArray implements Stack p

34、rivate final int LEN = 8;/數(shù)組的默認(rèn)大小 private Object elements;/數(shù)據(jù)元素?cái)?shù)組 private int top;/棧頂指針public StackArray() top = -1;elements = new ObjectLEN;/返回堆棧的大小public int getSize() return top+1;/判斷堆棧是否為空public boolean isEmpty() return top<0;/數(shù)據(jù)元素 e 入棧public void push(Object e) if (getSize()>=elements.len

35、gth) expandSpace();elements+top = e;private void expandSpace()Object a = new Objectelements.length*2;for (int i=0; i<elements.length; i+)ai = elementsi;elements = a;/棧頂元素出棧public Object pop() throws StackEmptyException if (getSize()<1)throw new StackEmptyException("錯(cuò)誤，堆棧為空。"); Object

36、 obj = elementstop; elementstop- = null; return obj;/取棧頂元素public Object peek() throws StackEmptyException if (getSize()<1)throw new StackEmptyException("錯(cuò)誤，堆棧為空。");return elementstop;6.鏈棧：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)鏈棧。棧頂指針是鏈表的頭指針。7.鏈棧上的基本運(yùn)算：public class StackSLinked implements Stack private SLNode top;/鏈

37、表首結(jié)點(diǎn)引用 private int size;/棧的大小public StackSLinked() top = null;size = 0; /返回堆棧的大小public int getSize() return size;/判斷堆棧是否為空public boolean isEmpty() return size=0;/數(shù)據(jù)元素 e 入棧public void push(Object e) SLNode q = new SLNode(e,top);top = q;size+;/棧頂元素出棧public Object pop() throws StackEmptyException if (s

38、ize<1)throw new StackEmptyException("錯(cuò)誤，堆棧為空。"); Object obj = top.getData();top = top.getNext();size-;return obj;/取棧頂元素public Object peek() throws StackEmptyException if (size<1)throw new StackEmptyException("錯(cuò)誤，堆棧為空。");return top.getData(); 8.隊(duì)列是一種運(yùn)算受限的線(xiàn)性表，允許刪除的一端稱(chēng)隊(duì)首，

39、允許插入的一端稱(chēng)隊(duì)尾。隊(duì)列又稱(chēng)為先進(jìn)先出線(xiàn)性表，F(xiàn)IFO表。9.隊(duì)列的基本運(yùn)算：1） initqueue(q),置空隊(duì)；2） queueempty(q),判隊(duì)空；3） queuefull(q),判隊(duì)滿(mǎn)；4） enqueue(q,x),入隊(duì)；5） dequeue(q),出隊(duì)；6） queuefront(q),返回隊(duì)頭元素。10.順序隊(duì)列：隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)順序隊(duì)列。設(shè)置front和rear指針表示隊(duì)頭和隊(duì)尾元素在向量空間的位置。11.順序隊(duì)列中存在“假上溢”現(xiàn)象，由于入隊(duì)和出隊(duì)操作使頭尾指針只增不減導(dǎo)致被刪元素的空間無(wú)法利用，隊(duì)尾指針

40、超過(guò)向量空間的上界而不能入隊(duì)。12.為克服“假上溢”現(xiàn)象，將向量空間想象為首尾相連的循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱(chēng)循環(huán)隊(duì)列。i=(i+1)%queuesize13.循環(huán)隊(duì)列的邊界條件處理：由于無(wú)法用front=rear來(lái)判斷隊(duì)列的“空”和“滿(mǎn)”。解決的方法有：1） 另設(shè)一個(gè)布爾變量以區(qū)別隊(duì)列的空和滿(mǎn)；2） 少用一個(gè)元素，在入隊(duì)前測(cè)試rear在循環(huán)意義下加1是否等于front；3） 使用一個(gè)記數(shù)器記錄元素總數(shù)。14.循環(huán)隊(duì)列的基本運(yùn)算：public interface Queue /返回隊(duì)列的大小public int getSize();/判斷隊(duì)列是否為空public

41、 boolean isEmpty();/數(shù)據(jù)元素 e 入隊(duì)public void enqueue(Object e);/隊(duì)首元素出隊(duì)public Object dequeue() throws QueueEmptyException;/取隊(duì)首元素public Object peek() throws QueueEmptyException;public class QueueArray implements Queue private static final int CAP = 7;/隊(duì)列默認(rèn)大小private Object elements;/數(shù)據(jù)元素?cái)?shù)組private int capac

42、ity;/數(shù)組的大小 elements.length private int front;/隊(duì)首指針,指向隊(duì)首private int rear;/隊(duì)尾指針,指向隊(duì)尾后一個(gè)位置public QueueArray() this(CAP);public QueueArray(int cap)capacity = cap + 1;elements = new Objectcapacity;front = rear = 0;/返回隊(duì)列的大小 public int getSize() return (rear -front+ capacity)%capacity;/判斷隊(duì)列是否為空public boole

43、an isEmpty() return front=rear;/數(shù)據(jù)元素 e 入隊(duì)public void enqueue(Object e) if (getSize()=capacity-1) expandSpace();elementsrear = e;rear = (rear+1)%capacity;private void expandSpace()Object a = new Objectelements.length*2;int i = front;int j = 0;while (i!=rear)/將從 front 開(kāi)始到 rear 前一個(gè)存儲(chǔ)單元的元素復(fù)制到新數(shù)組aj+ = el

44、ementsi;i = (i+1)%capacity;elements = a;capacity = elements.length;front = 0;rear = j; /設(shè)置新的隊(duì)首、隊(duì)尾指針/隊(duì)首元素出隊(duì)public Object dequeue() throws QueueEmptyException if (isEmpty()throw new QueueEmptyException("錯(cuò)誤：隊(duì)列為空"); Object obj = elementsfront;elementsfront = null;front = (front+1)%capacity;ret

45、urn obj;/取隊(duì)首元素public Object peek() throws QueueEmptyException if (isEmpty()throw new QueueEmptyException("錯(cuò)誤：隊(duì)列為空");return elementsfront;15.鏈隊(duì)列：隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)鏈隊(duì)列，鏈隊(duì)列由一個(gè)頭指針和一個(gè)尾指針唯一確定。16.鏈隊(duì)列的基本運(yùn)算：public class QueueSLinked implements Queue private SLNode front;private SLNode rear; private int siz

46、e;public QueueSLinked() front = new SLNode(); rear = front;size = 0;/返回隊(duì)列的大小public int getSize() return size;/判斷隊(duì)列是否為空 public boolean isEmpty() return size=0;/數(shù)據(jù)元素 e 入隊(duì)public void enqueue(Object e) SLNode p = new SLNode(e,null); rear.setNext(p);rear = p;size+;/隊(duì)首元素出隊(duì)public Object dequeue() throws Qu

47、eueEmptyException if (size<1)throw new QueueEmptyException("錯(cuò)誤：隊(duì)列為空");SLNode p = front.getNext();front.setNext(p.getNext();size-;if (size<1) rear = front; /如果隊(duì)列為空,rear 指向頭結(jié)點(diǎn)return p.getData();/取隊(duì)首元素public Object peek() throws QueueEmptyException if (size<1)throw new QueueEmptyExce

48、ption("錯(cuò)誤：隊(duì)列為空");return front.getNext().getData(); 第 四 章   串 1.串：是由零個(gè)或多個(gè)字符組成的有限序列；包含字符的個(gè)數(shù)稱(chēng)串的長(zhǎng)度；2.空串：長(zhǎng)度為零的串稱(chēng)空串；     空白串：由一個(gè)或多個(gè)空格組成的串稱(chēng)空白串；子串：串中任意個(gè)連續(xù)字符組成的子序列稱(chēng)該串的子串；    主串：包含子串的串稱(chēng)主串；子串的首字符在主串中首次出現(xiàn)的位置定義為子串在主串中的位置；3.

49、空串是任意串的子串；  任意串是自身的子串；串常量在程序中只能引用但不能改變其值； 串變量取值可以改變；4.串的基本運(yùn)算1） int strlen(char *s);求串長(zhǎng)。2） char *strcpy(char * to,char * from);串復(fù)制。3） char *strcat(char * to,char * from);串聯(lián)接。4） int strcmp(char *s1

50、,char *s2);串比較。5） char *strchr(char *s,char c);字符定位。5.串的存儲(chǔ)結(jié)構(gòu)：（1）串的順序存儲(chǔ)：串的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)順序串。按存儲(chǔ)分配不同分為：1） 靜態(tài)存儲(chǔ)分配的順序串：直接用定長(zhǎng)的字符數(shù)組定義，以“0”表示串值終結(jié)。#define maxstrsize 256typedef char seqstringmaxstrsize;seqstring s;不設(shè)終結(jié)符，用串長(zhǎng)表示。Typedef struct Char 

51、;chmaxstrsize; Int length;seqstring;以上方式的缺點(diǎn)是：串值空間大小是靜態(tài)的，難以適應(yīng)插入、鏈接等操作。2） 動(dòng)態(tài)存儲(chǔ)分配的順序串：簡(jiǎn)單定義：typedef char * string;復(fù)雜定義：typedef struct   char *ch;   int length;  hstring;（2）串的鏈?zhǔn)酱鎯?chǔ)：串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)鏈串。鏈串由頭指針唯一確定。類(lèi)型定義：typedef 

52、;struct node char data; struct node *next;linkstrnode;typedef linkstrnode *linkstring;linkstring s;將結(jié)點(diǎn)數(shù)據(jù)域存放的字符個(gè)數(shù)定義為結(jié)點(diǎn)的大小。結(jié)點(diǎn)大小不為1的鏈串類(lèi)型定義：#define nodesize 80typedef struct node char datanodesize; struct node *

53、60;next;linkstrnode;6.串運(yùn)算的實(shí)現(xiàn)（1）順序串上的子串定位運(yùn)算。1）子串定位運(yùn)算又稱(chēng)串的模式匹配或串匹配。主串稱(chēng)目標(biāo)串；子串稱(chēng)模式串。2）樸素的串匹配算法。時(shí)間復(fù)雜度為O(n2)。比較的字符總次數(shù)為（n-m+1）m。Int naivestrmatch(seqstring t,seqstring p) int i,j,k; int m=p.length; int n=t.length; for(i=0;i<=n-m;i+)  j=0;k=i;

54、0; while(j<m&&t.chk=p.chj)   j+;k+;    if (j=m) return i;  return 1;（2）鏈串上的子串定位運(yùn)算。時(shí)間復(fù)雜度為O(n2)。比較的字符總次數(shù)為（n-m+1）m。Linkstrnode * lilnkstrmatch(linkstring T, linkstring P) linkstrnode *shi

55、ft, *t, *p; shift=T; t=shift;p=P; while(t&&p)  if(t->data=p->data)t=t->next;   p=p->next;     else   shift=shift->next;   t=shift;   p=P;     if(p=NULL)  return shift; else  return NULL; 第 五 章    多 維 數(shù) 組 和 廣 義 表1.多維數(shù)組：一般用順序存儲(chǔ)的方式表示數(shù)組。2.常用方式有：1）行優(yōu)先順序，將數(shù)組元素按行向量排列；2）列優(yōu)先順序，將數(shù)組元素按列向量排列。3.計(jì)算地址的函數(shù)：LOC(Aij)=LOC(Ac1c2)+(i-c1)*(d2-c2+1