3-1引言v第三章棧和隊列括號匹配問題在實際問題的處理過程中，有些數(shù)據(jù)具有后到先處理的特點【問題】判斷給定表達(dá)式中所含括號是否正確配對?！鞠敕ā颗鋵υ瓌t：右括號與其前面最近的尚未配對的左括號相配對。順序掃描表達(dá)式，將右括號與已經(jīng)掃描過的最后一個尚未配對的左括號進(jìn)行配對。如何保存已經(jīng)掃描過的尚未配對的左括號，并對其實施配對操作？5+((3+2)×8–7)÷35+((3+2)×8–7))÷3用棧保存，掃描到左括號進(jìn)棧，掃描到右括號出棧進(jìn)制轉(zhuǎn)換問題【問題】將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)。【想法】轉(zhuǎn)換規(guī)則：除基取余，逆序排列。如何保存得到的余數(shù)，使之能夠逆序輸出？232111215222120101(23)10=用棧保存，從最后進(jìn)棧的元素開始輸出在實際問題的處理過程中，有些數(shù)據(jù)具有后到先處理的特點(10111)2

函數(shù)嵌套調(diào)用【問題】嵌套調(diào)用：在函數(shù)的執(zhí)行過程中調(diào)用其他函數(shù)，返回到哪里？【想法】為保證函數(shù)嵌套調(diào)用的正確執(zhí)行，返回到調(diào)用位置。如何保存調(diào)用位置？用棧保存，返回最后進(jìn)棧的位置主函數(shù)mainABCED在實際問題的處理過程中，有些數(shù)據(jù)具有后到先處理的特點Office的撤銷機制人生無法后悔，所以且行且珍惜！計算機后悔很容易，所以大膽往前走！隨處可見的棧結(jié)構(gòu)關(guān)于棧結(jié)構(gòu)什么是棧？在邏輯上有什么特點？在操作上有什么特性？如何存儲棧結(jié)構(gòu)？在不同的存儲結(jié)構(gòu)上，如何實現(xiàn)插入、刪除、查找等基本操作？在不同的存儲結(jié)構(gòu)上，基本操作的時空性能如何？銀行排隊問題在實際問題的處理過程中，有些數(shù)據(jù)具有先到先處理的特點【問題】銀行個人儲戶的儲蓄業(yè)務(wù)。【想法】先來先服務(wù)原則，模擬排隊，儲戶叫號后排在隊尾，窗口順次叫號。如何保存正在等待的儲戶順序？用隊列保存等待隊列打印緩沖區(qū)【問題】多個用戶共享打印機，保證打印功能。【想法】先來先服務(wù)原則，設(shè)置打印緩沖區(qū)，先送到緩沖區(qū)的先打印。如何保存等待打印的文件？用隊列保存即將打印的文檔在實際問題的處理過程中，有些數(shù)據(jù)具有先到先處理的特點隨處可見的隊列隨處可見的隊列關(guān)于隊列什么是隊列？在邏輯上有什么特點？在操作上有什么特性？如何存儲隊列？在不同的存儲結(jié)構(gòu)上，如何實現(xiàn)插入、刪除、查找等基本操作？在不同的存儲結(jié)構(gòu)上，基本操作的時空性能如何？八皇后問題很多問題的表現(xiàn)形式是矩陣，很多科學(xué)問題的數(shù)據(jù)模型是矩陣【問題】八皇后問題是數(shù)學(xué)家高斯于1850年提出的。問題是：在8×8的棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。?！鞠敕ā獢?shù)據(jù)表示】如何表示棋盤？如何獲得每個皇后的位置信息進(jìn)而判斷是否互相攻擊？用二維數(shù)組保存QQQQQQQQ解不唯一，N皇后可能無解！騎士巡游問題【騎士巡游問題】在n×n

方格的國際象棋棋盤上，馬（也稱為騎士）從任意指定的方格出發(fā)，以跳馬規(guī)則（橫一步豎兩步或橫兩步豎一步）周游棋盤的每一個格子，要求每個格子只能跳一次?！鞠敕ā獢?shù)據(jù)表示】如何表示棋盤？如何表示走位信息（位移量）？科學(xué)計算中的矩陣計算機中的矩陣關(guān)于數(shù)組多維數(shù)組：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及尋址矩陣的壓縮存儲：特殊矩陣、稀疏矩陣3-2棧v第三章棧和隊列棧的邏輯結(jié)構(gòu)棧的順序存儲結(jié)構(gòu)及實現(xiàn)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)學(xué)什么？順序棧和鏈棧的比較3-2-1棧的邏輯結(jié)構(gòu)v第三章棧和隊列棧的定義棧：限定僅在一端進(jìn)行插入和刪除操作的線性表（a1,…,an-1,an）棧頂（top）：允許插入和刪除的一端稱為棧頂棧底（bottom）：另一端稱為棧底插入位置：1~n+1刪除位置：1~n線性表插入位置：n+1刪除位置：n棧棧底棧頂棧的操作特性插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧a插入刪除bc此時執(zhí)行出棧操作，哪個元素可以出棧呢？棧的操作特性：后進(jìn)先出（LastInFirstOut，LIFO）空棧：不含任何數(shù)據(jù)元素的棧

條件判斷

abc棧只是對插入和刪除操作的位置進(jìn)行了限制并沒有限定插入和刪除操作進(jìn)行的時間例1有三個元素按a、b、c的次序依次進(jìn)棧，且每個元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？情況一出棧：cbaabc情況二出棧：bca棧的操作特性abc能否得到如下出棧序列？出棧：cab例1有三個元素按a、b、c的次序依次進(jìn)棧，且每個元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧的操作特性棧的抽象數(shù)據(jù)類型定義ADTStackDataModelOperationendADT棧中元素具有相同類型及后進(jìn)先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系InitStack：棧的初始化DestroyStack：棧的銷毀Push：入棧Pop：出棧GetTop：取棧頂元素Empty：判空相對于其他數(shù)據(jù)結(jié)構(gòu)，棧的基本操作是確定的InitStack輸入：無功能：棧的初始化，初始化一個空棧輸出：無

DestroyStack輸入：無功能：銷毀棧，釋放棧所占用的存儲空間輸出：無Push

輸入：元素值x

功能：在棧頂插入一個元素x

輸出：如果插入成功，棧頂增加了一個元素，否則返回失敗信息入棧出棧Push操作需要指明插入位置嗎？棧的抽象數(shù)據(jù)類型定義

Pop輸入：無功能：刪除棧頂元素輸出：如果刪除成功，返回被刪元素值；否則返回失敗信息GetTop輸入：無功能：讀取當(dāng)前的棧頂元素輸出：若棧不空，返回當(dāng)前的棧頂元素值；否則返回失敗信息Empty輸入：無功能：判斷棧是否為空輸出：如果棧為空，返回1；否則，返回0入棧出棧棧的抽象數(shù)據(jù)類型定義3-2-2棧的順序存儲結(jié)構(gòu)及實現(xiàn)v第三章棧和隊列順序棧的存儲結(jié)構(gòu)定義順序棧：棧的順序存儲結(jié)構(gòu)

012345678如何表示棧頂：設(shè)變量top存儲棧頂元素所在的下標(biāo)如何表示棧底：用數(shù)組的一端作為棧底如何改造數(shù)組實現(xiàn)棧的順序存儲呢？topabc什么是順序存儲？constintStackSize=10;template<typenameDataType>classSeqStack{public:SeqStack();~SeqStack();voidPush(DataTypex);DataTypePop();DataTypeGetTop();intEmpty();private:DataTypedata[StackSize];inttop;};

順序棧的類定義InitStack：棧的初始化DestroyStack：棧的銷毀Push：入棧Pop：出棧GetTop：取棧頂元素Empty：判空棧的抽象數(shù)據(jù)類型定義？棧滿：top=StackSize-1template<typenameDataType>voidSeqStack<DataType>::Push(DataTypex){

if(top==StackSize-1)throw"上溢";

data[++top]=x;}時間復(fù)雜度？什么情況下無法入棧？順序棧的實現(xiàn)——入棧

012…

StackSize-1topabcx棧空：top=-1template<typenameDataType>DataTypeSeqStack<DataType>::Pop(){

DataTypex;

if(top==-1)throw"下溢";

x=data[top--];

returnx;}如何取棧頂元素？什么情況下無法出棧？

012…

StackSize-1abctop順序棧的實現(xiàn)——出棧判空的函數(shù)原型是什么？Empty

輸入：無功能：判斷棧是否為空輸出：如果棧為空，返回1；否則，返回0

012…

StackSize-1abctop?？眨簍op=-1template<typenameDataType>intSeqStack<DataType>::Empty(){if(top==-1)return1elsereturn0;}順序棧的實現(xiàn)——判空3-2-3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)v第三章棧和隊列存儲結(jié)構(gòu)定義鏈棧：棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)單鏈表是如何存儲線性表的？firsta1a2an∧ai棧頂topanan-1a1∧firsta1a2an∧aiP：用鏈表的哪一端作為棧頂？A：為方便操作，用鏈頭作為棧頂P：鏈棧需要加頭結(jié)點嗎？P：單鏈表為什么加頭結(jié)點？A：鏈棧無須加頭結(jié)點，也可以為了一致加上頭結(jié)點鏈棧的類定義template<typenameDataType>classLinkedStack{public:LinkedStack();~LinkedStack();voidPush(DataTypex);DataTypePop();DataTypeGetTop();intEmpty();private:

Node<DataType>*top;};InitStack：棧的初始化DestroyStack：棧的銷毀Push：入棧Pop：出棧GetTop：取棧頂元素Empty：判空棧的抽象數(shù)據(jù)類型定義？鏈棧的實現(xiàn)——入棧topanan-1a1∧xstoptemplate<typenameDataType>voidLinkedStack<DataType>::Push(DataTypex){Node<DataType>*s=nullptr;s=newNode<DataType>;s->data=x;//申請結(jié)點s數(shù)據(jù)域為x

s->next=top;top=s;//將結(jié)點s插在棧頂}鏈棧的入棧操作為什么不用判斷是否棧滿？template<typenameDataType>DataTypeLinkedStack<DataType>::Pop(){Node<DataType>*p=nullptr;DataTypex;if(top==nullptr)throw"下溢";x=top->data;p=top;//暫存棧頂元素

top=top->next;//將棧頂結(jié)點摘鏈deletep;returnx;}topanan-1a1∧topp

什么情況下無法刪除？top=nullptr空棧如何取棧頂元素？鏈棧的實現(xiàn)——出棧順序棧和鏈棧的比較作為一般規(guī)律，當(dāng)棧的使用過程中元素個數(shù)變化較大時，應(yīng)該采用鏈棧，反之，應(yīng)該采用順序棧?；静僮鞯臅r間復(fù)雜度均為O(1)。比較空間性能：順序棧：初始時必須確定一個固定的長度，有存儲元素個數(shù)的限制和浪費空間的問題。鏈棧：沒有棧滿的問題，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。3-3隊列v第三章棧和隊列隊列的邏輯結(jié)構(gòu)隊列的順序存儲結(jié)構(gòu)及實現(xiàn)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)學(xué)什么？循環(huán)隊列和鏈隊列的比較3-3-1隊列的邏輯結(jié)構(gòu)v第三章棧和隊列隊列的定義隊列：只允許在表的一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作（a1,a2,…,an-1,an）隊尾：允許插入的一端，相應(yīng)地，位于隊尾的元素稱為隊尾元素a1

a2

…

an棧a1

a2

…

an隊列隊頭隊尾隊頭：允許刪除的一端，相應(yīng)地，位于隊頭的元素稱為隊頭元素隊列的操作特性插入：入隊、進(jìn)隊任何時候執(zhí)行出隊操作，一定是哪個元素呢？隊列的操作特性：先進(jìn)先出（FirstInFirstOut，F(xiàn)IFO）a入隊出隊bc例：有三個元素按a、b、c的次序依次入隊，且每個元素只允許進(jìn)一次隊，則出隊序列是什么？答：出隊序列只有一種情況：abc刪除：出隊空隊列：不含任何數(shù)據(jù)元素的隊列

隊列的抽象數(shù)據(jù)類型定義ADTStackDataModelOperationendADT隊列中元素具有相同類型及先進(jìn)先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系InitQueue：隊列的初始化DestroyQueue：隊列的銷毀EnQueue：入隊DeQueue：出隊GetQueue：取隊頭元素Empty：判空與棧類似，隊列的基本操作是確定的InitQueue

輸入：無功能：初始化隊列，創(chuàng)建一個空隊列輸出：無DestroyQueue

輸入：無功能：銷毀隊列，釋放隊列所占用的存儲空間輸出：無EnQueue

輸入：元素值x

功能：在隊尾插入一個元素輸出：如果插入成功，隊尾增加了一個元素；否則返回失敗信息a1

a2

…an入隊出隊Enqueue操作需要指明插入位置嗎？隊列的抽象數(shù)據(jù)類型定義DeQueue

輸入：無功能：刪除隊頭元素輸出：如果刪除成功，返回被刪元素值；否則給出失敗信息GetQueue

輸入：無功能：讀取隊頭元素輸出：若隊列不空，返回隊頭元素；否則給出失敗信息Empty

輸入：無功能：判斷隊列是否為空輸出：如果隊列為空，返回1，否則，返回0a1

a2

…an入隊出隊隊列的抽象數(shù)據(jù)類型定義3-3-2隊列的順序存儲結(jié)構(gòu)及實現(xiàn)v第三章棧和隊列順序隊列順序隊列：隊列的順序存儲結(jié)構(gòu)如何表示隊尾：設(shè)變量rear存儲隊尾元素所在的下標(biāo)如何表示隊頭：用數(shù)組的一端作為隊頭，從下標(biāo)0處開始存放如何改造數(shù)組實現(xiàn)隊列的順序存儲？01234a1a2a3a4rear例：a1a2a3a4依次入隊入隊操作的時間性能？01234a1a2a3a4rear例：a1a2依次出隊順序隊列順序隊列：隊列的順序存儲結(jié)構(gòu)出隊操作的時間性能？如何表示隊尾：設(shè)變量rear存儲隊尾元素所在的下標(biāo)如何表示隊頭：用數(shù)組的一端作為隊頭，從下標(biāo)0處開始存放如何改造數(shù)組實現(xiàn)隊列的順序存儲？如何改進(jìn)出隊操作的時間性能？01234a2a3a4rear設(shè)置隊頭、隊尾兩個位置指針約定：隊頭front指向隊頭元素的前一個位置，隊尾rear指向隊尾元素fronta1例：a1a2依次出隊入隊、出隊時間性能均是O(1)順序隊列隊列的移動有什么特點？01234a2a3a4front例：a1a2依次出隊整個隊列向數(shù)組下標(biāo)較大方向移動單向移動性隊列的單向移動性會產(chǎn)生什么問題？a5假溢出：數(shù)組空間發(fā)生上溢，但數(shù)組的低端還有空閑空間rear順序隊列如何解決假溢出呢？01234a3a4rearfront如何使數(shù)組下標(biāo)循環(huán)呢？a5a6if(rear+1>4)rear=0;elserear++;循環(huán)隊列：隊列采用順序存儲，并且數(shù)組是頭尾相接的循環(huán)結(jié)構(gòu)程序技巧：求模（正余數(shù)）使得數(shù)組下標(biāo)循環(huán)rear=(rear+1)%5循環(huán)隊列循環(huán)隊列的類定義InitQueue：隊列的初始化DestroyQueue：隊列的銷毀EnQueue：入隊DeQueue：出隊GetQueue：取隊頭元素Empty：判空隊列的抽象數(shù)據(jù)類型定義？constintQueueSize=100;template<typenameDataType>classCirQueue{public:CirQueue();~CirQueue();voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();intEmpty();private:

DataTypedata[QueueSize];intfront,rear;};CirQueue<DataType>::CirQueue(){front=rear=QueueSize-1;}循環(huán)隊列的實現(xiàn)——初始化01234rearfrontCirQueue<DataType>::CirQueue(){front=rear=-1;}rearfront循環(huán)隊列：隊列采用順序存儲，并且數(shù)組是頭尾相接的循環(huán)結(jié)構(gòu)設(shè)置隊頭、隊尾兩個位置指針會出現(xiàn)Bug？01234a3rearfront如何判斷循環(huán)隊列的隊空？隊空的判定條件：front=rearintCirQueue<DataType>::Empty(){if(rear==front)return1;elsereturn0;}循環(huán)隊列的實現(xiàn)——判空a6a2a4a5rearfront如何判斷循環(huán)隊列隊滿？隊空的判定條件：front=rear隊滿的判定條件：front=rearx隊空和隊滿0123401234a6a2a4a5rearfront如何確定不同的隊空、隊滿的判定條件？隊空的判定條件：front=rear隊滿的判定條件：front=rear數(shù)組中有一個空閑單元01234a1a2a4a5rearfront(rear+1)%QueueSize=front隊空和隊滿template<typenameDataType>voidCirQueue<DataType>::EnQueue(DataTypex){

if((rear+1)%QueueSize==front)throw"上溢";

rear=(rear+1)%QueueSize;//隊尾指針在循環(huán)意義下加1data[rear]=x;//在隊尾處插入元素}

01234a3a4rearfront時間復(fù)雜度是多少？循環(huán)隊列的實現(xiàn)——入隊xPage07template<typenameDataType>DataTypeCirQueue<DataType>::DeQueue(){if(rear==front)throw"下溢";

front=(front+1)%QueueSize;//隊頭指針在循環(huán)意義下加1returndata[front];//讀取并返回出隊前的隊頭元素}取隊頭元素的實現(xiàn)？01234a2a3a4rearfront循環(huán)隊列的實現(xiàn)——出隊3-3-3隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)及實現(xiàn)v第三章棧和隊列鏈隊列的存儲結(jié)構(gòu)定義鏈隊列：隊列的鏈接存儲結(jié)構(gòu)firsta1a2an∧aiP：用鏈表的哪一端作為隊頭？哪一端作為隊尾？A：鏈頭作為隊頭，出隊時間為O(1)

鏈尾作為隊尾，入隊時間為O(n)P：鏈隊列需要加頭結(jié)點嗎？rearfront設(shè)置隊尾指針rear鏈隊列的類定義InitQueue：隊列的初始化DestroyQueue：隊列的銷毀EnQueue：入隊DeQueue：出隊GetQueue：取隊頭元素Empty：判空隊列的抽象數(shù)據(jù)類型定義？template<typenameDataType>classLinkedQueue{public:

LinkedQueue();~LinkedQueue();voidEnQueue(DataTypex);DataTypeDeQueue();DataTypeGetQueue();intEmpty();private:

Node<DataType>*front,*rear;};xs∧front∧rear沒有頭結(jié)點會怎樣？xs∧rearfrontrear=s;front=s;鏈隊列的實現(xiàn)——入隊voidLinkedQueue<DataType>::EnQueue(DataTypex){

Node<DataType>*s=nullptr;

s=newNode<DataType>;//申請結(jié)點s

s->data=x;s->next=nullptr;

rear->next=s;rear=s;}時間復(fù)雜度是多少？a1a2an∧airearfrontxs∧考慮邊界情況？p∧考慮邊界情況？如何判斷邊界情況？a1a2an∧airearfrontprear∧a1frontp->next=nullptr鏈隊列的實現(xiàn)——出隊DataTypeLinkedQueue<DataType>::DeQueue(){DataTypex;Node<DataType>*p=nullptr;

if(rear==front)throw"下溢";p=front->next;x=p->data;

front->next=p->next;if(p->next==nullptr)rear=front;deletep;returnx;}如何取隊頭元素？循環(huán)隊列與鏈隊列的比較作為一般規(guī)律，當(dāng)隊列中元素個數(shù)變化較大時，應(yīng)該采用鏈隊列，反之，應(yīng)該采用循環(huán)隊列，如果確定不會發(fā)生假溢出，也可以采用順序隊列?；静僮鞯臅r間復(fù)雜度均為O(1)。比較空間性能：循環(huán)隊列：初始時必須確定一個固定的長度，所以有存儲元素個數(shù)的限制和浪費空間的問題。鏈隊列：沒有溢出的問題，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。3-4多維數(shù)組v第三章棧、隊列和數(shù)組數(shù)組的邏輯結(jié)構(gòu)數(shù)組的存儲結(jié)構(gòu)及尋址學(xué)什么？3-4-1數(shù)組的邏輯結(jié)構(gòu)v第三章棧、隊列和數(shù)組數(shù)組的定義（多維）數(shù)組：由一組類型相同的數(shù)據(jù)元素構(gòu)成的有序集合，每個數(shù)據(jù)元素稱為一個數(shù)組元素（簡稱為元素），每個元素受n(n≥1)個線性關(guān)系的約束，每個元素在n個線性關(guān)系中的序號i1、i2、…、in稱為該元素的下標(biāo)，并稱該數(shù)組為

n維數(shù)組。

a11…a1n

…………

am1…amnA=a21

a22…a2na12am2數(shù)組有什么特點呢？（1）元素本身可以具有某種結(jié)構(gòu)，屬于同一數(shù)據(jù)類型；

A=(A1，A2，…，An)其中：Aj=(a1j，a2i，…，amj)(1≤j≤n)

A=(A1，A2，…，Am)其中：Ai=(ai1，ai2，…，ain)(1≤i≤m)（2）數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)集合。x數(shù)組的抽象數(shù)據(jù)類型定義數(shù)組有什么基本操作呢？（1）存?。航o定一組下標(biāo)，讀出對應(yīng)的數(shù)組元素（2）修改：給定一組下標(biāo)，存儲或修改與其相對應(yīng)的數(shù)組元素尋址ADTMDArrayDataModel

相同類型的數(shù)據(jù)元素的有序集合，每個元素受n（n≥1）個線性關(guān)系的約束Operation

InitArray：數(shù)組的初始化

DestroyArray：數(shù)組的銷毀Get：讀操作，讀取這組下標(biāo)對應(yīng)的數(shù)組元素Set：寫操作，存儲或修改這組下標(biāo)對應(yīng)的數(shù)組元素endADT3-4-2數(shù)組的存儲結(jié)構(gòu)及尋址v第三章棧、隊列和數(shù)組數(shù)組的存儲結(jié)構(gòu)如何存儲（多維）數(shù)組呢？數(shù)組沒有插入和刪除操作，所以，不用預(yù)留空間，適合采用順序存儲二維數(shù)組內(nèi)存二維結(jié)構(gòu)一維結(jié)構(gòu)按行優(yōu)先：先存儲行號較小的元素，行號相同者先存儲列號較小的元素按列優(yōu)先：先存儲列號較小的元素，列號相同者先存儲行號較小的元素按行優(yōu)先：先存儲行號較小的元素，行號相同者先存儲列號較小的元素l2h2

l1h1aij第l1行第l1+1行如何得到元素aij的存儲地址？數(shù)組的存儲結(jié)構(gòu)l2h2

l1h1aijaij前面的元素個數(shù)=整行數(shù)×每行元素個數(shù)+本行中aij前面的元素個數(shù)=(i

-l1)×(h2

-l2＋1)＋(j

-l2)Loc(aij)Loc(al1l2)(i

-l1)×(h2

-l2+1)＋(j

-l2)個元素Loc(aij)＝Loc(al1l2)＋((i－l1)×(h2－l2＋1)＋(j－l2))×c按列優(yōu)先與此類似，請自行給出數(shù)組元素的尋址3-5矩陣的壓縮存儲v第三章棧、隊列和數(shù)組對稱矩陣的壓縮存儲三角矩陣的壓縮存儲對角矩陣的壓縮存儲學(xué)什么？稀疏矩陣的壓縮存儲特殊矩陣的壓縮存儲3-5-1特殊矩陣的壓縮存儲v第三章棧、隊列和數(shù)組特殊矩陣什么是特殊矩陣？

特殊矩陣：矩陣中很多值相同的元素并且它們的分布有一定的規(guī)律特殊矩陣如何壓縮存儲？為值相同的元素分配一個存儲空間特殊矩陣壓縮存儲后有什么要求嗎？保證隨機存取，即在O(1)時間內(nèi)尋址3647862842481697460582957A＝對稱矩陣特點：aij=aji如何壓縮存儲對稱矩陣呢？只存儲下三角部分的元素對稱矩陣aij在一維數(shù)組中的序號=

i×(i-1)/2+j∵一維數(shù)組下標(biāo)從0開始∴aij在一維數(shù)組中的下標(biāo)k=i×(i-1)/2+j-1

1…

i

n1…j…n

aij第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2-1對稱矩陣下三角中的元素aij（i≥j）：k＝i×(i-1)/2＋j-1壓縮存儲后的尋址方法上三角中的元素aij（i＜j），k＝j(luò)×(j-1)/2＋i

-1如何壓縮存儲三角矩陣呢？3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩陣相同的常數(shù)只存儲一個下（上）三角部分的元素三角矩陣下三角矩陣的壓縮存儲第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2c下三角中的元素aij（i≥j）：k＝i×(i

-1)/2+j-1上三角中的元素aij（i＜j）：k＝n×(n+1)/2下三角矩陣壓縮存儲后的尋址方法上三角矩陣的壓縮存儲請仿此給出三角矩陣對角矩陣對角矩陣：所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，所有其他元素都為零。

a11a120

00a21a22

a23000a32

a33a34000

a43

a44

a45000a54

a55A=如何壓縮存儲對角矩陣呢？只存儲非零元素

元素aij在一維數(shù)組中的序號=2+3(i-2)+(j-i+2)=2i+j-2∵一維數(shù)組下標(biāo)從0開始∴元素aij在一維數(shù)組中的下標(biāo)=

2i+j-3a11a12000a21a22

a23000a32a33

a34000

a43a44

a45

000a54a55A=

a11a12a21a22a23a32a33a34a43a44a45a54a55012345678