數(shù)據(jù)結(jié)構(gòu)課件第2章

1、第二章 線性表 線性表的基本概念線性表：是由一組數(shù)據(jù)元素組成，線性表或者是一個空表，或者 可以寫成a1,a2, ai, , an，其中ai是取自某個集合S 的元素。 當(dāng)1in時，數(shù)據(jù)元素ai-1稱為數(shù)據(jù)元素ai的直 接前趨，而稱ai+1為ai的直接后繼。 若一個數(shù)據(jù)元素由若干個數(shù)據(jù)項組成，則該數(shù)據(jù)元素又稱為記錄，含有大量記錄的線性表又稱為文件。 線性表中元素的個數(shù)稱為該線性表的長度。 線性表的定義第二章 線性表 線性表的基本概念線性表：是由一組數(shù)據(jù)元 線性結(jié)構(gòu)的特點1、數(shù)據(jù)元素的數(shù)據(jù)類型一致。2、數(shù)據(jù)元素之間的相對位置呈線性關(guān)系。3、存在唯一的一個被稱做“第一個”和“最后一個”的數(shù)據(jù)元素。4、

2、除第一個和最后一個外，集合中每個數(shù)據(jù)元素均只有一個前驅(qū)和一個后繼。 線性結(jié)構(gòu)的特點1、數(shù)據(jù)元素的數(shù)據(jù)類型一致。Partition(L, L1, L2)： 將L拆分成L1和L2。Search(L, b): 查找滿足條件b的數(shù)據(jù)元素。Sort(L)： 將L中所有數(shù)據(jù)元素進(jìn)行排序（降序或者升序）。 Prior(L, elm)： 求元素elm的前驅(qū)。Next(L, elm)： 求元素elm的后繼。Empty(L)： 判空表函數(shù)。Clear(L)： 表置空操作。 線性表可以進(jìn)行如下運算： Initiate(L)： 初始化操作，設(shè)定一個線性表。 Length(L)： 長度的函數(shù)，返回元素的個數(shù)。 Acce

3、ss(L, i)： 訪問第i個數(shù)據(jù)元素。 Insert(L, i, b)： 在第i個元素之前，插入元素b。 Delete(L, i)： 刪除第i個元素。 Merge(L1, L2)： 合并L1和L2，合并結(jié)果保存在L1中。Partition(L, L1, L2)： 將L拆分成L1和 線性表的存儲結(jié)構(gòu) 在計算機(jī)中有不同的方法來表示線性表，最普通、最簡單的方法是順序映像或順序分配，即采用一組連續(xù)的存儲單元依次存儲線性表中各數(shù)據(jù)元素。 順序分配的存儲結(jié)構(gòu)采用向量結(jié)構(gòu)：設(shè)線性表的長度為N，建立一向量V，用Vi表示第i個分量，第i個分量是線性表第i個元素ai在計算機(jī)存儲中的映像，即Vi =ai。 順序存

4、儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)的定義 線性表的存儲結(jié)構(gòu) 在計算機(jī)中有不同的方法來表示存儲地址內(nèi)存狀態(tài)元素序號空閑aaaa12in: :bb+Lb+(i-1)Lb+(n-1)Lb+(maxlen-1)L12in線性表的順序存儲結(jié)構(gòu)示意圖 若線性表中的第一個存儲元素的地址為LOCa1，每個元素占用L個存儲單元，則表的第i個元素的存儲地址為： LOCai=LOCa1+(i-1)*L LOCai=LOCai-1+L若每個元素僅占用1個存儲單元，則表的第i個元素的存儲地址為：LOCai=LOCa1+(i-1)存儲密度d：d=數(shù)據(jù)元素的值所需的存儲量/該數(shù)據(jù)元素所需的存儲總量在順序分配的存儲結(jié)構(gòu)中，所有的存儲單元

5、空間全部被數(shù)據(jù)元素有效占用，因此，順序分配結(jié)構(gòu)的存儲密度d=1。存儲地址內(nèi)存狀態(tài)元素序號空閑aaaa12in: :二、順序存儲結(jié)構(gòu)的插入和刪除運算 1 刪除運算例：設(shè)有長為n的線性表a1,a2, , an, 刪除ai，并把它送入某單元Y。 Yaia1a2a3ai-1aian:123i-1in-1i+1n:a1a2a3ai-1an:123i-1in-1i+1n:ai+1順序存儲結(jié)構(gòu)的刪除操作二、順序存儲結(jié)構(gòu)的插入和刪除運算例：設(shè)有長為n的線性表a1,順序存儲結(jié)構(gòu)的刪除操作算法： 1、如果1=i=n，則將第i個元素送給y。反之，則退出。 2、從第i個存儲單元開始，依次將第i+1個元素送給第i個存儲

6、單元，將第i+2個元素送到第i+1個存儲單元，直到將第n個元素送給第n-1個存儲單元。 3、線性表長度減1。 4、返回。刪除操作算法的時間復(fù)雜性： 1、假設(shè)刪除每個數(shù)據(jù)元素的概率相等，即概率為1/n。 2、基本操作為移動數(shù)據(jù)元素。 3、平均移動次數(shù)為 4、所以，刪除操作算法的時間復(fù)雜性為O(n)。順序存儲結(jié)構(gòu)的刪除操作算法：刪除操作算法的時間復(fù)雜性：# define m 1000typedef struct L_stru int n; /*表長度為n*/ int am; /*數(shù)據(jù)元素向量為整型*/；void delete(L, i, y) /*刪除數(shù)據(jù)元素函數(shù)*/ struct L_stru

7、L； /*定義參數(shù)類型*/int i, *y; int j; if(iL.n) /*判斷刪除數(shù)據(jù)元素的位置*/ printf(“The delete position is not correct ! n”); else *y=L.ai-1; /*a的下標(biāo)從0開始，不是從1開始*/ for(j=i; j=L.n-1; j+) /*j=L.n-1即j=n-1*/ L.aj-1=L.aj; L.n=L.n-1; 刪除操作算法的程序段：# define m 1000刪除操作算法 2 插入運算例：設(shè)有長為n的線性表a1,a2, , an, 在第i位置插入新數(shù)據(jù)元素x。 順序存儲結(jié)構(gòu)的插入操作xa1a2

8、a3ai-1aian:123i-1ini+1:a1a2a3ai-1an-1:123i-1ini+1n+1:aixan 2 插入運算例：設(shè)有長為n的線性表a1,a2, , 順序存儲結(jié)構(gòu)的插入操作算法： 1、如果1=i=n+1，則插入數(shù)據(jù)元素x。反之，則退出。 2、從第n到第i個存儲單元的數(shù)據(jù)元素，依次后移，騰出空位i：第n個元素送給第n+1個存儲單元，將第n-1個元素送到第n個存儲單元，直到將第i個元素送給第i+1個存儲單元。 3、在空位i處插入元素x，線性表長度加1。 4、返回。插入操作算法的時間復(fù)雜性1: 1、假設(shè)在每個位置插入數(shù)據(jù)元素的概率相等，即概率為1/n。 2、基本操作為移動數(shù)據(jù)元素

9、。 3、平均移動次數(shù)為 4、所以，插入操作算法的時間復(fù)雜性為O(n)。順序存儲結(jié)構(gòu)的插入操作算法：插入操作算法的時間復(fù)雜性1:順序存儲結(jié)構(gòu)的插入操作算法： 1、如果1=i=n+1，則插入數(shù)據(jù)元素x。反之，則退出。 2、從第n到第i個存儲單元的數(shù)據(jù)元素，依次后移，騰出空位i：第n個元素送給第n+1個存儲單元，將第n-1個元素送到第n個存儲單元，直到將第i個元素送給第i+1個存儲單元。 3、在空位i處插入元素x，線性表長度加1。 4、返回。插入操作算法的時間復(fù)雜性2： 1、假設(shè)在每個位置插入數(shù)據(jù)元素的概率相等，即概率為1/(n+1)。 2、基本操作為移動數(shù)據(jù)元素。 3、平均移動次數(shù)為 4、所以，插

10、入操作算法的時間復(fù)雜性為O(n)。順序存儲結(jié)構(gòu)的插入操作算法：插入操作算法的時間復(fù)雜性2：順序存儲結(jié)構(gòu)的插入操作算法： 1、如果1=im) printf(“The list is overflow ! n”); /*溢出*/ else if (iL.n+1) /*判斷插入數(shù)據(jù)元素的位置*/ printf(“The insertion position is not correct ! n”); else if ( i !=L.n+1 ) /*在線性表最末插入不必移動*/ for (j=L.n-1;j=i-1;j-) /*依次移動元素*/ L.aj+1=L.aj; L.n=L.n+1; /*線性

11、表長度加1*/ L.ai-1=x; /*在空位i處插入x*/ 插入操作算法的程序段：# define m 1000插入操作算法的程序段：一、單鏈表線形鏈表：在線形表中每一個元素的值和該表中下一個元素的地址放在一起，這兩個部分的信息組成一個結(jié)點，若干個這樣的結(jié)點構(gòu)成了一個線形鏈表。 鏈?zhǔn)酱鎯Y(jié)構(gòu)在線性鏈表的存儲結(jié)構(gòu)中，若數(shù)據(jù)域與指針域所需的存儲單元空間相等，則線性鏈表的存儲密度d=0.5。ai+1結(jié)點的地址ai（指針域）（數(shù)據(jù)域）邏輯結(jié)構(gòu)中的數(shù)據(jù)元素ai 對應(yīng)存儲結(jié)構(gòu)中的結(jié)點為：一、單鏈表線形鏈表：在線形表中每一個元素的值和該表中下一個元例：用圖形表示線性表BAT,CAT,HAT,KAT,VAT

12、,WAT的存儲結(jié)構(gòu)。地址數(shù)據(jù)順序分配 BAT CAT HAT KAT VAT WAT NULLL0+IL0L0+2IL0+3IL0+4IL0+5IL0+6I地址數(shù)據(jù)指針鏈接分配初ABCDEF KATF WATNULL CATD HATA BATC VATBE指針表示頭指針head BATHATCATKATVATWAT順序表的特點：可以隨機(jī)存取表中的任一元素；在作插入和刪除操作時,需移動大量的元素。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)：用任意的存儲單元存儲線性表的數(shù)據(jù)元素。用鏈指針體現(xiàn)線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。例：用圖形表示線性表BAT,CAT,HAT,KAT,VAT單鏈表的插入操作：例：如圖所示鏈表，表

13、頭指針為head，欲在值為y的數(shù)據(jù)元素處插入新數(shù)據(jù)元素x。rxheada1ai-1yanqprxheada1ai-1yanqp單鏈表的插入操作：例：如圖所示鏈表，表頭指針為head，欲在單鏈表的插入位置可能有4種情況：1）原來鏈表為空表，則插入結(jié)點作為表頭結(jié)點；2）在鏈表第1個結(jié)點位置插入，則插入結(jié)點為新表頭結(jié)點，原來的表頭結(jié)點成為第2個結(jié)點；3）在鏈表中間位置插入，則注意修改插入位置前后指針域；4）如果根本不存在所指定結(jié)點，則在鏈表尾部插入結(jié)點?？紤]所有可能情況的程序如下頁：單鏈表的插入位置可能有4種情況：1）原來鏈表為空表，則插入結(jié)typedef struct node /*定義結(jié)點的結(jié)構(gòu)

14、*/ /*程序如下*/ int data; struct node *next;；void insert_link (head, x, y) /*在元素y處插入元素x*/struct node *head; /*定義參數(shù)*/int x, y; struct node *q, *p, *r; r=(struct node *) (malloc (sizeof (struct node); /*分配存儲空間給r*/ rdata=x; /*元素x保存在r的數(shù)據(jù)域*/ if (head= =NULL) /*空表，r為唯一結(jié)點*/ head=r; rnext=NULL; else if (headdat

15、a= =y) /*第1個結(jié)點為y*/ rnext=head; head=r; typedef struct node else q=head; p=headnext; while (p !=NULL) /*循環(huán)查找*/ if (pdata !=y) q=p; p=pnext; else break; if (p !=NULL) /*在p指針指向結(jié)點處插入新結(jié)點r*/ qnext=r; rnext=p; else /*沒有值為y的結(jié)點，在表尾插入新結(jié)點r*/ qnext=r; rnext=NULL; else單鏈表的刪除操作：例：如圖所示鏈表，表頭指針為head，欲刪除數(shù)據(jù)域為x的結(jié)點。head

16、a1ai-1xan釋放該結(jié)點空間ai+1rqpnextheada1ai-1xanqpai+1pnext單鏈表的刪除操作：例：如圖所示鏈表，表頭指針為head，欲刪單鏈表的刪除操作可能有4種情況：1）鏈表為空表，則沒有數(shù)據(jù)元素可以刪除。2）被刪除結(jié)點為鏈表的第1個結(jié)點，存在兩種情況：僅有頭結(jié)點情況，刪后為空表；鏈表有多個結(jié)點情況，頭指針需要改變。3）在鏈表中間位置刪除，則注意修改刪除位置前后指針域；4）否則查找到鏈表末，根本不存在所指定結(jié)點?？紤]所有可能情況的程序如下頁：單鏈表的刪除操作可能有4種情況：1）鏈表為空表，則沒有數(shù)據(jù)元typedef struct node /*定義結(jié)點的結(jié)構(gòu)*/ /

17、*程序如下*/ int data; struct node *next;；void delete_link (head, x) /*刪除元素x的函數(shù)*/struct node *head; /*定義參數(shù)*/int x; struct node *q, *p, *r; if (head= =NULL) /*空表*/ printf (“The link list is empty ! n”); else if (headdata = =x) /*第1個結(jié)點為x*/ p=head; if (headnext= =NULL) /*僅有頭結(jié)點情況，刪后為空表*/ head=NULL; else head

18、=headnext; /*鏈表有多個結(jié)點情況，頭指針需要改變*/ free (p); typedef struct node else p=head; q=p; while (p != NULL) /*循環(huán)查找*/ if (pdata !=x) q=p; p=pnext; else break; if (p !=NULL) /*刪除p指針指向的結(jié)點x*/ r=p; qnext =pnext; free (r); else /*查找完整個鏈表，沒有結(jié)點x*/ printf (“x element is not in the link list ! n”); else 二、循環(huán)鏈表 將單鏈表的最后

19、一個結(jié)點的指針域next指向它的頭結(jié)點所得的鏈表。如下圖所示，訪問結(jié)點更加方便。H單循環(huán)鏈表空單循環(huán)鏈表HH帶表頭結(jié)點的單循環(huán)鏈表 為了可以統(tǒng)一地表示和處理空表和非空表的情況，在循環(huán)鏈表的第一個結(jié)點前增加一個特殊的表頭結(jié)點。如下圖所示。二、循環(huán)鏈表 將單鏈表的最后一個結(jié)點的指針域n三、雙向鏈表 若只有一個指針域，指向該結(jié)點的后繼，如果要找到它的前趨結(jié)點，則需要從表頭指針出發(fā)。為此要作以下擴(kuò)充： 每個結(jié)點包括三個域：一個數(shù)據(jù)域，兩個指針域：一個指向前趨，稱為左鏈域 llink，一個指向后繼，稱為右鏈域 rlink。由此形成雙向鏈表。 其每個結(jié)點的物理結(jié)構(gòu)、雙向鏈表、循環(huán)雙向鏈表如下所示：結(jié)點的物

20、理形式 llinkdatarlinkHBCDA雙向鏈表HBCD循環(huán)雙向鏈表A空循環(huán)雙向鏈表P三、雙向鏈表 若只有一個指針域，指向該結(jié)點的后循環(huán)雙向鏈表中插入操作 在結(jié)點值域為x的結(jié)點右邊插入一個值為y的新結(jié)點，過程為：1）設(shè)立一個搜索指針p，循環(huán)地在鏈表中進(jìn)行查找。2）若查找到指定的結(jié)點，則在其后插入新結(jié)點，并修改相關(guān)結(jié)點的指針域值。3）如果查找不到值為x的結(jié)點，則在鏈表尾插入新結(jié)點y。 雙向鏈表結(jié)點的指針域存在如下關(guān)系： p =prlinkllink =pllinkrlink 插入前指針狀態(tài)Hxpr插入后指針狀態(tài)Hxpyqr循環(huán)雙向鏈表中插入操作 雙向鏈表結(jié)點的指針域存在如下關(guān)系：用C語言描

21、述插入操作如下：typedef struct node struct node *llink; /*定義指向直接前驅(qū)的指針*/ int data; /*定義數(shù)據(jù)類型*/ struct node *rlink; /*定義指向直接后繼的指針*/; void insert_bilink (head, x, y)struct node *head;int x, y; struct node *p, *q, *r; q= (struct node *) (malloc (sizeof (struct node); /*建立新結(jié)點q*/ qdata=y; /*對建立的新結(jié)點q進(jìn)行賦值為y*/ 用C語言描述

22、插入操作如下： if (head = = NULL) /*空表，插入結(jié)點y為循環(huán)雙向鏈表的唯一結(jié)點*/ head=q; qllink=head; qrlink=head; else if (headdata = = x) /*非空表，第1個結(jié)點為x，在其右插入y*/ qrlink=headrlink; headrlinkllink=q; headrlink=q; qllink=head; if (head = = NULL) /*空表 else r=head; /*r指針指向當(dāng)前結(jié)點p的前驅(qū)結(jié)點*/ p=headrlink; while (p !=head) /*指針r一直查找到表尾，指針p一

23、直查找到表頭*/ if (pdata !=x) /*當(dāng)沒有找到x時，指針r和p同時前移一個結(jié)點*/ r=p; p=prlink; else /*當(dāng)找到x或指針r指向最后一個結(jié)點，退出*/ break; else if (p !=head) /*當(dāng)在鏈表中間某個位置找到x時，在指針p右邊插入*/ qrlink=prlink; /*將q的后繼指向p的后繼*/ qrlinkllink=q; /*將q的后繼的前驅(qū)指向q*/ prlink=q; /*p的后繼指向q*/ qllink=p; /*q的前驅(qū)指向p*/ else /*當(dāng)沒有找到x時，在指向鏈表最后1個結(jié)點的指針r右邊插入*/ qrlink=he

24、ad; qllink=r; rrlink=q; headllink=q; if (p !=head) /*當(dāng)在循環(huán)雙向鏈表中刪除操作 在循環(huán)雙向鏈表中，刪除值域為x的結(jié)點，過程為：1）設(shè)立一個搜索指針p，循環(huán)地在鏈表中進(jìn)行查找。2）若查找到值域為x的指定結(jié)點，則進(jìn)行刪除，并修改相關(guān)結(jié)點的指針域值。3）如果查找不到值為x的結(jié)點，則輸出提示信息。 刪除前指針狀態(tài)Hxp刪除后指針狀態(tài)Hxp釋放該結(jié)點空間循環(huán)雙向鏈表中刪除操作刪除前指針狀態(tài)Hxp刪除后指針狀態(tài)Hx用C語言描述刪除操作如下：typedef struct node struct node *llink; /*定義指向直接前驅(qū)的指針*/ i

25、nt data; /*定義數(shù)據(jù)類型*/ struct node *rlink; /*定義指向直接后繼的指針*/; void delete_bilink (head, x)struct node *head;int x; struct node *p, *q, *r; 用C語言描述刪除操作如下： if (head = = NULL) /*空表，無結(jié)點可刪*/ printf (“The bidirectional loop link-list is empty ! n”); else if (headdata = = x) /*非空表，第1個結(jié)點為x，刪除第1個結(jié)點*/ p=head; if (h

26、eadrlink = = head) /*鏈表僅有唯一一個結(jié)點，且為結(jié)點x*/ head=NULL; else /*鏈表中有多個結(jié)點，第1個為結(jié)點x*/ headrlinkllink= headllink; headllinkrlink= headrlink; head=headrlink; free (p); if (head = = NULL) else /*非空表，且值為x的結(jié)點不在第1個位置*/ p=headrlink; /*p指針前移，指向第2個結(jié)點*/ while (p !=head) /*指針p一直查找，循環(huán)到表頭*/ if (pdata !=x) /*當(dāng)沒有找到x時，指針p前移

27、一個結(jié)點*/ p=prlink; else /*當(dāng)找到結(jié)點x，退出*/ break; if (p !=head) /*當(dāng)在鏈表中某個位置找到x時，刪除指針p指向的結(jié)點*/ pllinkrlink=prlink; /*p的前驅(qū)的后繼指向p的后繼*/ prlinkllink=pllink; /*p的后繼的前驅(qū)指向p的前驅(qū)*/ free (p); /*釋放該結(jié)點所占用的存儲空間*/ else /*當(dāng)沒有找到x時，提示信息*/ printf (“No x element in the bidirectional link-list ! n”); else 多項式概述 多項式的算術(shù)運算，已經(jīng)成為線性表處

28、理的一個經(jīng)典問題，可用兩種鏈表(線性鏈表或循環(huán)線性鏈表)來表示多項式，研究兩個多項式相加運算。 一般多項式的形式為： Pn (x) = p1 xe1 + p2 xe2 + pn xen 其中：pi為多項式的系數(shù)，ei為多項式的指數(shù)，且滿足： 0 e1 e2 en 設(shè)一個多項式有n個非零項，n個（帶表頭結(jié)點時為n+1個）結(jié)點的線性鏈表就能唯一的確定這個多項式。設(shè)該線性鏈表有三個域：系數(shù)域coef ，指數(shù)域exp，指針域next。如下圖所示。 expcoefexpcoefcoefexp.p 多項式概述 多項式的算術(shù)運算，已經(jīng)成為線性 多項式相加運算規(guī)則：若兩指數(shù)相等，則系數(shù)相加；若兩指數(shù)不相等，則

29、按指數(shù)大小次序分別復(fù)制相應(yīng)的兩項。解：用線性鏈表的形式表示上面的兩個多項式，如下圖所示。pa13506302104310 PAH1050-630-55PBHpb例：計算下面兩個多項式的相加結(jié)果,并在PCH中存放結(jié)果。 PAH=13X50+6X30+2X10+4X3+1 PBH=10X50-6X30-5X5+3X2 上面兩個多項式相加，相加2次，比較6次，主要操作共8次；而PAH有5項，PBH有4項，共9項；相加或比較次數(shù)跟多項式的長度正相關(guān)。 結(jié)論：設(shè)多項式PAH有m項，PBH有n項，則相加的時間復(fù)雜性為O(m+n)。32pc2350210-554332 PCH10 多項式相加運算規(guī)則：若兩指

30、數(shù)相等，則系數(shù)相加；若兩指數(shù)不算法描述如下： 1、若paexp = pbexp，則倆coef域相加。若相加結(jié)果不等于0 ，則寫入pc鏈表中；若相加結(jié)果為0，則不寫入該結(jié)點。指針pa和pb后移。 2、paexp pbexp，則把pa所指結(jié)點寫入pc鏈表中。指針pa后移。 3、paexp pbexp) /*pa指數(shù)大于pb指數(shù)時*/ pc=create_item (pc, pacoef , paexp); pa=panext; /* 則pa后移*/ else /*pb指數(shù)大于pa指數(shù)時*/ pc=create_item (pc, pbcoef , pbexp); pb=pbnext; /* 則pb

31、后移*/ while (pa != NULL) /* 復(fù)制pah鏈表剩余結(jié)點*/ pc=create_item (pc, pacoef , paexp); pa=panext; /* 則pa后移*/ while (pb != NULL) /* 復(fù)制pbh鏈表剩余結(jié)點*/ pc=create_item (pc, pbcoef , pbexp); pb=pbnext; /* 則pb后移*/ else if (paexp pcnext =NULL; /*尾結(jié)點指針賦空*/ pc=pch; /*指針pc指向頭結(jié)點*/ pch=pchnext; /*指針pch指向第1個結(jié)點*/ free(pc); /*

32、刪除臨時頭結(jié)點*/ pcnext =NULL; 數(shù)組的定義及其運算數(shù) 組 數(shù)組是線性表的推廣，它是由下標(biāo)和值組成的偶對（下標(biāo)，值）的一個集合。即在數(shù)組中，對于每一組有定義的下標(biāo)i1，i2，in總是有一個固定的數(shù)值（數(shù)據(jù)元素）與之對應(yīng)，這樣的數(shù)組稱為n維數(shù)組。例2：二維數(shù)組Am*n可定義為：例1：一維數(shù)組An可定義為：下標(biāo)i對應(yīng)ai下標(biāo)i, j對應(yīng)aij 數(shù)組的定義及其運算數(shù) 組 數(shù)組是線性表的推廣 也可把數(shù)組看成這樣一個線性表：它的每個數(shù)據(jù)元素仍是一個線性表。 如上例2中：A=a1，a2，an，其中每個aj是一個列向量的線性表（即列線性表），aj= a1j，a2j ， ，amj，1j n ；同

33、理也可用行向量表示（即行線性表）。行（列）線性表說明了矩陣的線性二維性。 數(shù)組通常只有兩種運算：1、Value (array, index)：給定數(shù)組array的下標(biāo)index，存取相應(yīng)的數(shù)據(jù)元素2、Assign (array, index, value)：給定數(shù)組array的下標(biāo)index，賦予或修改相應(yīng)數(shù)據(jù)元素的值為value。 也可把數(shù)組看成這樣一個線性表：它的每個數(shù)據(jù)元 數(shù)組的順序存儲結(jié)構(gòu) 由于存儲單元是一維結(jié)構(gòu)，而數(shù)組是多維結(jié)構(gòu)，則用一組連續(xù)的存儲單元存放數(shù)組的數(shù)據(jù)元素就有個次序約定，主要有兩種方式：1、以行序為主: 有C/C+，BASIC，COBAL，PASCAL；2、以列序為主:

34、 有FORTRAN，MATLAB。 數(shù)組的順序存儲結(jié)構(gòu) 由于存儲單元是一維結(jié)構(gòu)， 對數(shù)組而言，一旦規(guī)定了數(shù)組的維數(shù)和各維的上下界限，便可為它分配存儲空間；反之，只要給出一組下標(biāo)便可求得相應(yīng)數(shù)組元素的存儲位置。a11:a1na21:a2n:amna1a11:am1a12:am2:amna1以行為主以列為主 對數(shù)組而言，一旦規(guī)定了數(shù)組的維數(shù)和各維的上下界限 數(shù)組的存儲地址計算公式 1. 一維數(shù)組 長度為n的一維數(shù)組 An A0, A1, A2, , An-1 ，數(shù)組首地址為LOC(A0)，則數(shù)組中任一元素Aj （第j1個元素）的地址LOC(Aj)的計算公式為： LOC(Aj) LOC(A0)j；（

35、數(shù)組下標(biāo)從0開始，每個元素存儲空間為1） LOC(Aj) LOC(A0)j*L；（數(shù)組下標(biāo)從0開始，每個元素存儲空間為L） 以行序為主 數(shù)組的存儲地址計算公式 1. 一維數(shù)組 2. 二維數(shù)組 長度為m*n的二維數(shù)組 Am*n，數(shù)組首地址為LOC(A0, 0)，則數(shù)組中任一元素Ai, j （第i1行、第j1列元素）的地址LOC(Ai, j)的計算公式為：LOC(Ai, j)= LOC(A0, 0)+(i*n+j); （每個元素存儲空間為1）LOC(Ai, j)= LOC(A0, 0)+(i*n+j) *L; （每個元素存儲空間為L） 2. 二維數(shù)組 3. 三維數(shù)組 長度為d1*d2*d3的三維數(shù)

36、組 Ad1*d2*d3，數(shù)組首地址為LOC(A0, 0, 0)，則數(shù)組中任一元素Ai1, i2, i3 的地址LOC(Ai1, i2, i3)的計算公式為：LOC(Ai1, i2, i3 )= LOC(A0, 0, 0)+(i1*d2*d3+i2*d3+i3); LOC(Ai1, i2, i3 )= LOC(A0, 0, 0)+(i1*d2*d3+i2*d3+i3)*L; 3. 三維數(shù)組 4. n維數(shù)組 各維長度為d1, d2, d3, dn 的n維數(shù)組A，數(shù)組首地址為LOC(A0,0)，則數(shù)組中任一元素Ai1,in 的地址LOC(Ai1,in)的計算公式為：LOC(Ai1,in )= LOC

37、(A0,0)+(i1*d2*d3*dn+i2*d3*d4*dn+in-1*dn+in)*L; 4. n維數(shù)組 n維數(shù)組 各維長度為d1, d2, d3, dn 的n維數(shù)組A，數(shù)組首地址為LOC(A0,0)，則數(shù)組中任一元素Ai1,in 的地址LOC(Ai1,in)的計算公式為：LOC(Ai1,in )= LOC(A0,0)+(in*d1*d2*dn-1+in-1*d1*d2*dn-2+i2*d1+i1)*L; 以列序為主 n維數(shù)組 以列序為主例：有如下數(shù)組定義 float a1054;1、若數(shù)組a的首地址為1200，求數(shù)組元素a345在按行存儲方式下的地址？2、其按列存儲方式下的地址？ 注：s

38、izeof(float)=4解：d1=10, d2=5, d3=4; i1=3, i2=4, i3=5;1、LOC(a345)=1200+(i1*d2*d3+i2*d3+i3)*L =1200+(3*5*4+4*4+5)*4=1524;2、LOC(a345)=1200+(i3*d1*d2+i2*d1+i1)*L =1200+(5*10*5+4*10+3)*4=2372;例：有如下數(shù)組定義解：d1=10, d2=5, d3=4; 矩陣的壓縮存儲 特殊矩陣 特殊矩陣：值相同，或非零元素在矩陣中的分布有一定的規(guī)律，或矩陣元素本身的數(shù)值分布具有一定規(guī)律。 對稱矩陣 如：n階對稱矩陣：一個n階對稱矩陣A中的元素有下述性質(zhì)： aij=aji， 1=i， j = n。 n階對稱矩陣中有一半元素是相同的。還有的矩陣中只有上三角或下三角中的元素不為0，為節(jié)省空間，采用壓縮存儲，只存儲下三角或上三角的元素。 矩陣的壓縮存儲 特殊矩陣 特殊矩陣：值相同，或非 例：如果一個4階對稱矩陣A如下所示，只存儲下三角元素，則可用如下的一數(shù)組元素表示：01234567894352651079 僅需要存儲的下三角元素個數(shù)123410 個數(shù)組下標(biāo) 例：如果一個4階對稱矩陣A如下所示，只存儲下三 例：如果一個n階對稱矩陣A只存在下三