數(shù)據(jù)結構復習筆記(共41頁)

1、第一章 概 論1.數(shù)據(jù)：信息的載體,能被計算機識別、存儲和加工處理。2.數(shù)據(jù)元素：數(shù)據(jù)的基本單位，可由若干個數(shù)據(jù)項組成，數(shù)據(jù)項是具有獨立含義的最小標識單位。3.數(shù)據(jù)結構：數(shù)據(jù)之間的相互關系，即數(shù)據(jù)的組織形式。它包括：1）數(shù)據(jù)的邏輯結構，從邏輯關系上描述數(shù)據(jù)，與數(shù)據(jù)存儲無關，獨立于計算機；2）數(shù)據(jù)的存儲結構，是邏輯結構用計算機語言的實現(xiàn)，依賴于計算機語言。3）數(shù)據(jù)的運算，定義在邏輯結構上，每種邏輯結構都有一個運算集合。常用的運算：檢索/插入/刪除/更新/排序。4.數(shù)據(jù)的邏輯結構可以看作是從具體問題抽象出來的數(shù)學模型。數(shù)據(jù)的存儲結構是邏輯結構用計算機語言的實現(xiàn)。5.數(shù)據(jù)類型：一個值的集合及在值上定

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

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

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

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

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

7、blic ListArray (Strategy strategy)size = 0;elements = new ObjectLEN;/返回線性表的大小，即數(shù)據(jù)元素的個數(shù)。public int getSize() return size;/如果線性表為空返回 true，否則返回 false。public boolean isEmpty() return size=0;/判斷線性表是否包含數(shù)據(jù)元素 e public boolean contains(Object e) for (int i=0; i<size; i+)if ( e = = elementsi) return true;r

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

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

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

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

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

13、ment = 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; /單鏈表首結點引用private int size; /線性表中數(shù)據(jù)元素的個數(shù)pu

14、blic ListSLinked () head = new SLNode(); size = 0;/輔助方法：獲取數(shù)據(jù)元素 e 所在結點的前驅結點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;/輔助方法：獲取序號為 0<=i<size 的元素所在結點的前驅結點private SLNode getPreNode(int i) SLN

15、ode p = head; for (; i>0; i-) p = p.getNext(); return p;/獲取序號為 0<=i<size 的元素所在結點private SLNode getNode(int i) SLNode p = head.getNext(); for (; i>0; i-) p = p.getNext(); return p;/返回線性表的大小，即數(shù)據(jù)元素的個數(shù)。public int getSize() return size;/如果線性表為空返回 true，否則返回 false。public boolean isEmpty() retur

16、n size=0;/判斷線性表是否包含數(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 插入到線性表中 i 號位置public void insert(int i, Object e) throws OutOfBoundaryException if (i<0|i>size) throw new OutOfBound

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

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

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

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

21、表查找開始結點和尾結點的時間都是O(1)。10.在結點中增加一個指針域，prior|data|next。形成的鏈表中有兩條不同方向的鏈稱為雙鏈表。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 getNext()retur

22、n 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 size; /規(guī)模 privat

23、e DLNode head;/頭結點,啞元結點 private DLNode tail;/尾結點,啞元結點 public LinkedListDLNode() size = 0; head = new DLNode();/構建只有頭尾結點的鏈表 tail = new DLNode(); head.setNext(tail); tail.setPre(head);/輔助方法，判斷結點 p 是否合法，如合法轉換為 DLNodeprotected DLNode checkPosition(Node p) throws InvalidNodeException if (p=null) throw ne

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

25、pty() return size=0;/返回第一個結點public Node first() throws OutOfBoundaryException if (isEmpty() throw new OutOfBoundaryException("錯誤：鏈接表為空。"); return head.getNext();/返回最后一結點public Node last() throws OutOfBoundaryException if (isEmpty() throw new OutOfBoundaryException("錯誤：鏈接表為空。"); r

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

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

28、re(node); head.setNext(node); size+; return node;/將 e 作為最后一個元素插入列表,并返回 e 所在結點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 InvalidNodeException DL

29、Node 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() throws OutOf

30、BoundaryException 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） 基于空間的考慮：順序表的存儲空間是靜態(tài)分配的，鏈表的存儲空間是動態(tài)分配的。順序表的存儲密度比鏈表大。

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

32、表（LIFO表）。插入、刪除端稱為棧頂，另一端稱棧底。表中無元素稱空棧。2.棧的基本運算有：1） initstack(s),構造一個空棧；2） stackempty(s),判?？?；3） stackfull(s),判棧滿；4） push(s,x),進棧；5） pop (s),退棧；6） stacktop(s)，取棧頂元素。3.順序棧：棧的順序存儲結構稱順序棧。4.當棧滿時，做進棧運算必定產(chǎn)生空間溢出，稱“上溢”。 當?？諘r，做退棧運算必定產(chǎn)生空間溢出，稱“下溢”。上溢是一種錯誤應設法避免，下溢常用作程序控制轉移的條件

33、。5.在順序棧上的基本運算：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 private final

34、int LEN = 8;/數(shù)組的默認大小 private Object elements;/數(shù)據(jù)元素數(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.length) expandSp

35、ace();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("錯誤，堆棧為空。"); Object obj = elemen

36、tstop; elementstop- = null; return obj;/取棧頂元素public Object peek() throws StackEmptyException if (getSize()<1)throw new StackEmptyException("錯誤，堆棧為空。");return elementstop;6.鏈棧：棧的鏈式存儲結構稱鏈棧。棧頂指針是鏈表的頭指針。7.鏈棧上的基本運算：public class StackSLinked implements Stack private SLNode top;/鏈表首結點引用 privat

37、e 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 (size<1)thro

38、w new StackEmptyException("錯誤，堆棧為空。"); Object obj = top.getData();top = top.getNext();size-;return obj;/取棧頂元素public Object peek() throws StackEmptyException if (size<1)throw new StackEmptyException("錯誤，堆棧為空。");return top.getData(); 8.隊列是一種運算受限的線性表，允許刪除的一端稱隊首，允許插入的一端稱隊尾。隊列

39、又稱為先進先出線性表，F(xiàn)IFO表。9.隊列的基本運算：1） initqueue(q),置空隊；2） queueempty(q),判隊空；3） queuefull(q),判隊滿；4） enqueue(q,x),入隊；5） dequeue(q),出隊；6） queuefront(q),返回隊頭元素。10.順序隊列：隊列的順序存儲結構稱順序隊列。設置front和rear指針表示隊頭和隊尾元素在向量空間的位置。11.順序隊列中存在“假上溢”現(xiàn)象，由于入隊和出隊操作使頭尾指針只增不減導致被刪元素的空間無法利用，隊尾指針超過向量空間的上界而不能入

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

41、pty();/數(shù)據(jù)元素 e 入隊public void enqueue(Object e);/隊首元素出隊public Object dequeue() throws QueueEmptyException;/取隊首元素public Object peek() throws QueueEmptyException;public class QueueArray implements Queue private static final int CAP = 7;/隊列默認大小private Object elements;/數(shù)據(jù)元素數(shù)組private int capacity;/數(shù)組的大小 el

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

43、return front=rear;/數(shù)據(jù)元素 e 入隊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 開始到 rear 前一個存儲單元的元素復制到新數(shù)組aj+ = elementsi;i = (

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

45、素public Object peek() throws QueueEmptyException if (isEmpty()throw new QueueEmptyException("錯誤：隊列為空");return elementsfront;15.鏈隊列：隊列的鏈式存儲結構稱鏈隊列，鏈隊列由一個頭指針和一個尾指針唯一確定。16.鏈隊列的基本運算：public class QueueSLinked implements Queue private SLNode front;private SLNode rear; private int size;public Queu

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

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

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

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

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

51、; Int length;seqstring;以上方式的缺點是：串值空間大小是靜態(tài)的，難以適應插入、鏈接等操作。2） 動態(tài)存儲分配的順序串：簡單定義：typedef char * string;復雜定義：typedef struct   char *ch;   int length;  hstring;（2）串的鏈式存儲：串的鏈式存儲結構稱鏈串。鏈串由頭指針唯一確定。類型定義：typedef struct 

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

53、trnode;6.串運算的實現(xiàn)（1）順序串上的子串定位運算。1）子串定位運算又稱串的模式匹配或串匹配。主串稱目標串；子串稱模式串。2）樸素的串匹配算法。時間復雜度為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;  while

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

55、#160;*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(

56、p=NULL)  return shift; else  return NULL; 第 五 章    多 維 數(shù) 組 和 廣 義 表1.多維數(shù)組：一般用順序存儲的方式表示數(shù)組。2.常用方式有：1）行優(yōu)先順序，將數(shù)組元素按行向量排列；2）列優(yōu)先順序，將數(shù)組元素按列向量排列。3.計算地址的函數(shù)：LOC(Aij)=LOC(Ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d4.矩陣的壓縮存