數據結構第五章多維數組和廣義表

　　第五章多維數組和廣義表

　　多維數組

　　一般用順序存儲的方式表示數組常用方式有)行優先順序將數組元素按行向量排列;)列優先順序將數組元素按列向量排列

　　計算地址的函數LOC(Aij)=LOC(Acc)+((ic)*(dc+)+jc)*d

　　矩陣的壓縮存儲

　　為多個非零元素分配一個存儲空間;對零元素不分配存儲空間

　　 對稱矩陣

　　在一個n階的方陣A中元素滿足Aij=Aji <=ij<=n;稱為對稱矩陣

　　元素的總數為n(n+)/;

　　設I=i或j中大的一個數;J=i或j中小的一個數;

　　則k=I*(I+)/+J;

　　地址計算LOC(Aij)=LOC(sa[k])=LOC(sa[])+k*d= LOC(sa[])+ (I*(I+)/+J )*d

　　 三角矩陣

　　以主對角線劃分三角矩陣有上三角和下三角;上三角的主對角線下元素均為常數c;下三角的主對角線上元素均為常數c

　　元素總數為(n(n+)/)+;

　　以行優先順序存放的Aij與SA[k]的關系

　　上三角陣k=i*(ni+)/+ji;

　　下三角陣k=i*(i+)/+j;

　　對角矩陣

　　所有的非零元素集中在以主對角線為中心的帶狀區域相鄰兩側元素均為零|ij|>(k)/

　　以行優先順序存放的Aij與SA[k]的關系k=i+j;

　　稀疏矩陣

　　當矩陣A中有非零元素S個且S遠小於元素總數時稱為稀疏矩陣對其壓縮的方法有順序存儲和鏈式存儲

　　 三元組表

　　將表示稀疏矩陣的非零元素的三元組(行號列號值)按行或列優先的順序排列得到的一個結點均是三元組的線性表將該表的線性存儲結構稱為三元組表其類型定義

　　#define maxsize

　　typedef int datatype;

　　typedef struct{

　　int ij;

　　datatype v;

　　}trituplenode;

　　typedef struct{

　　trituplenode data[maxsize];

　　int mnt;

　　}tritupletable;

　　帶行表的三元組表

　　在按行優先存儲的三元組表中加入一個行表記錄每行的非零元素在三元組表中的起始位置類型定義

　　#define maxrow

　　typedef struct{

　　tritulpenode data[maxsize];

　　int rowtab[maxrow];

　　int m n t;

　　}rtritulpetable;

　　廣義表的概念

　　廣義表是線性表的推廣廣義表是n個元素的有限序列元素可以是原子或一個廣義表記為LS

　　若元素是廣義表稱它為LS的子表若廣義表非空則第一個元素稱表頭其余元素稱表尾

　　表的深度是指表展開後所含括號的層數

　　把與樹對應的廣義表稱為純表它限制了表中成分的共享和遞歸;

　　允許結點共享的表稱為再入表;

　　允許遞歸的表稱為遞歸表;

　　相互關系線性表∈純表∈再入表∈遞歸表;

　　廣義表的特殊運算)取表頭head(LS);)取表尾tail(LS);

　　附二:

　　第五章多維數組和廣義表

　　**************************************************************************************

　　數組一般用順序存儲的方式表示存儲的方式有 ·行優先順序也就是把數組逐行依次排列PASCALC

　　·列優先順序就是把數組逐列依次排列FORTRAN

　　**************************************************************************************

　　地址的計算方法 ·按行優先順序排列的數組LOCa(ij)=LOCa()+((i)*n+(j))*d

　　·按列優先順序排列的數組LOCa(ij)=LOCa()+((j)*n+(i))*d

　　**************************************************************************************

　　矩陣的壓縮存儲為多個相同的非零元素分配一個存儲空間;對零元素不分配空間

　　特殊矩陣的概念所謂特殊矩陣是指非零元素或零元素分布有一定規律的矩陣

　　稀疏矩陣的概念一個矩陣中若其非零元素的個數遠遠小於零元素的個數則該矩陣稱為稀疏矩陣

　　*************************************************************************************

　　特殊矩陣的類型 ·對稱矩陣滿足a(ij)=a(ji)元素總數n(n+)/I=max(ij)J=min(ij)LOCa(ij)=LOC(sa[])+(I*(I+)/+J)*d

　　·三角矩陣 ·上三角陣k=i*(ni+)/+jiLOCa(ij)=LOC(sa[])+k*d

　　·下三角陣k=i*(i+)/+jLOCa(ij)=LOC(sa[])+k*d

　　·對角矩陣k=i+jLOCa(ij)=LOC(sa[])+k*d

　　*************************************************************************************

　　稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號做為一個結點存放在一起用這些結點組成的一個線性表來表示但這種壓縮存儲方式將失去隨機存儲功能加入行表記錄每行的非零元素在三元組表中的起始位置即帶行表的三元組表

　　************************************************************************

　　廣義表是n(n≥)個元素的有限序列其中的元素是原子或者是一個廣義表

　　廣義表表頭和表尾的概念 ·若廣義表LS非空(n≥)則這個廣義表的第一個元素就是表頭

　　·其余的元素組成的表稱為LS的表尾所以表尾必是一個子表

　　廣義表有兩種表示法一種是括號表示法一種是圖形表示法

　　廣義表與樹(形結構)相對應這個廣義表就是純表

　　如果一個廣義表的結點又可以被其他結點所共享則這個表稱為再入表

　　允許遞歸的表稱為遞歸表

　　線性表∈純表(樹)∈再入表∈遞歸表 可見廣義表是對線性表和樹的推廣

　　廣義表有兩個特殊的基本運算 ·取表頭head(LS)取表中的第一個數據元素不能對空表操作

　　·取表尾tail(LS);取除表頭外其余數據元素構成的子表不能對空表操作

From:http://tw.wingwit.com/Article/program/sjjg/201311/23669.html