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

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

2、除第一個(gè)和最后一個(gè)外，集合中每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)和一個(gè)后繼。 線性結(jié)構(gòu)的特點(diǎn)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)行如下運(yùn)算： Initiate(L)： 初始化操作，設(shè)定一個(gè)線性表。 Length(L)： 長度的函數(shù)，返回元素的個(gè)數(shù)。 Acce

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

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

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

6、單元，將第i+2個(gè)元素送到第i+1個(gè)存儲(chǔ)單元，直到將第n個(gè)元素送給第n-1個(gè)存儲(chǔ)單元。 3、線性表長度減1。 4、返回。刪除操作算法的時(shí)間復(fù)雜性： 1、假設(shè)刪除每個(gè)數(shù)據(jù)元素的概率相等，即概率為1/n。 2、基本操作為移動(dòng)數(shù)據(jù)元素。 3、平均移動(dòng)次數(shù)為 4、所以，刪除操作算法的時(shí)間復(fù)雜性為O(n)。順序存儲(chǔ)結(jié)構(gòu)的刪除操作算法：刪除操作算法的時(shí)間復(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 插入運(yùn)算例：設(shè)有長為n的線性表a1,a2, , an, 在第i位置插入新數(shù)據(jù)元素x。 順序存儲(chǔ)結(jié)構(gòu)的插入操作xa1a2

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

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

10、入操作算法的時(shí)間復(fù)雜性為O(n)。順序存儲(chǔ)結(jié)構(gòu)的插入操作算法：插入操作算法的時(shí)間復(fù)雜性2：順序存儲(chǔ)結(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 ) /*在線性表最末插入不必移動(dòng)*/ for (j=L.n-1;j=i-1;j-) /*依次移動(dòng)元素*/ L.aj+1=L.aj; L.n=L.n+1; /*線性

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

12、,WAT的存儲(chǔ)結(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順序表的特點(diǎn)：可以隨機(jī)存取表中的任一元素；在作插入和刪除操作時(shí),需移動(dòng)大量的元素。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：用任意的存儲(chǔ)單元存儲(chǔ)線性表的數(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é)點(diǎn)作為表頭結(jié)點(diǎn)；2）在鏈表第1個(gè)結(jié)點(diǎn)位置插入，則插入結(jié)點(diǎn)為新表頭結(jié)點(diǎn)，原來的表頭結(jié)點(diǎn)成為第2個(gè)結(jié)點(diǎn)；3）在鏈表中間位置插入，則注意修改插入位置前后指針域；4）如果根本不存在所指定結(jié)點(diǎn)，則在鏈表尾部插入結(jié)點(diǎn)?？紤]所有可能情況的程序如下頁：?jiǎn)捂湵淼牟迦胛恢每赡苡?種情況：1）原來鏈表為空表，則插入結(jié)typedef struct node /*定義結(jié)點(diǎn)的結(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); /*分配存儲(chǔ)空間給r*/ rdata=x; /*元素x保存在r的數(shù)據(jù)域*/ if (head= =NULL) /*空表，r為唯一結(jié)點(diǎn)*/ head=r; rnext=NULL; else if (headdat

15、a= =y) /*第1個(gè)結(jié)點(diǎn)為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é)點(diǎn)處插入新結(jié)點(diǎn)r*/ qnext=r; rnext=p; else /*沒有值為y的結(jié)點(diǎn)，在表尾插入新結(jié)點(diǎn)r*/ qnext=r; rnext=NULL; else單鏈表的刪除操作：例：如圖所示鏈表，表頭指針為head，欲刪除數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)。head

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

18、=headnext; /*鏈表有多個(gè)結(jié)點(diǎn)情況，頭指針需要改變*/ 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é)點(diǎn)x*/ r=p; qnext =pnext; free (r); else /*查找完整個(gè)鏈表，沒有結(jié)點(diǎn)x*/ printf (“x element is not in the link list ! n”); else 二、循環(huán)鏈表 將單鏈表的最后

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

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

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

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

24、ad; qllink=r; rrlink=q; headllink=q; if (p !=head) /*當(dāng)在循環(huán)雙向鏈表中刪除操作 在循環(huán)雙向鏈表中，刪除值域?yàn)閤的結(jié)點(diǎn)，過程為：1）設(shè)立一個(gè)搜索指針p，循環(huán)地在鏈表中進(jìn)行查找。2）若查找到值域?yàn)閤的指定結(jié)點(diǎn)，則進(jìn)行刪除，并修改相關(guān)結(jié)點(diǎn)的指針域值。3）如果查找不到值為x的結(jié)點(diǎn)，則輸出提示信息。 刪除前指針狀態(tài)Hxp刪除后指針狀態(tài)Hxp釋放該結(jié)點(diǎn)空間循環(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é)點(diǎn)可刪*/ printf (“The bidirectional loop link-list is empty ! n”); else if (headdata = = x) /*非空表，第1個(gè)結(jié)點(diǎn)為x，刪除第1個(gè)結(jié)點(diǎn)*/ p=head; if (h

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

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

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

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

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

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

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

33、理也可用行向量表示（即行線性表）。行（列）線性表說明了矩陣的線性二維性。 數(shù)組通常只有兩種運(yùn)算：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ù)組看成這樣一個(gè)線性表：它的每個(gè)數(shù)據(jù)元 數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 由于存儲(chǔ)單元是一維結(jié)構(gòu)，而數(shù)組是多維結(jié)構(gòu)，則用一組連續(xù)的存儲(chǔ)單元存放數(shù)組的數(shù)據(jù)元素就有個(gè)次序約定，主要有兩種方式：1、以行序?yàn)橹? 有C/C+，BASIC，COBAL，PASCAL；2、以列序?yàn)橹?

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

35、數(shù)組下標(biāo)從0開始，每個(gè)元素存儲(chǔ)空間為1） LOC(Aj) LOC(A0)j*L；（數(shù)組下標(biāo)從0開始，每個(gè)元素存儲(chǔ)空間為L） 以行序?yàn)橹?數(shù)組的存儲(chǔ)地址計(jì)算公式 1. 一維數(shù)組 2. 二維數(shù)組 長度為m*n的二維數(shù)組 Am*n，數(shù)組首地址為LOC(A0, 0)，則數(shù)組中任一元素Ai, j （第i1行、第j1列元素）的地址LOC(Ai, j)的計(jì)算公式為：LOC(Ai, j)= LOC(A0, 0)+(i*n+j); （每個(gè)元素存儲(chǔ)空間為1）LOC(Ai, j)= LOC(A0, 0)+(i*n+j) *L; （每個(gè)元素存儲(chǔ)空間為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)的計(jì)算公式為：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)的計(jì)算公式為：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)的計(jì)算公式為：LOC(Ai1,in )= LOC(A0,0)+(in*d1*d2*dn-1+in-1*d1*d2*dn-2+i2*d1+i1)*L; 以列序?yàn)橹?n維數(shù)組 以列序?yàn)橹骼河腥缦聰?shù)組定義 float a1054;1、若數(shù)組a的首地址為1200，求數(shù)組元素a345在按行存儲(chǔ)方式下的地址？2、其按列存儲(chǔ)方式下的地址？ 注：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; 矩陣的壓縮存儲(chǔ) 特殊矩陣 特殊矩陣：值相同，或非零元素在矩陣中的分布有一定的規(guī)律，或矩陣元素本身的數(shù)值分布具有一定規(guī)律。 對(duì)稱矩陣 如：n階對(duì)稱矩陣：一個(gè)n階對(duì)稱矩陣A中的元素有下述性質(zhì)： aij=aji， 1=i， j = n。 n階對(duì)稱矩陣中有一半元素是相同的。還有的矩陣中只有上三角或下三角中的元素不為0，為節(jié)省空間，采用壓縮存儲(chǔ)，只存儲(chǔ)下三角或上三角的元素。 矩陣的壓縮存儲(chǔ) 特殊矩陣 特殊矩陣：值相同，或非 例：如果一個(gè)4階對(duì)稱矩陣A如下所示，只存儲(chǔ)下三角元素，則可用如下的一數(shù)組元素表示：01234567894352651079 僅需要存儲(chǔ)的下三角元素個(gè)數(shù)123410 個(gè)數(shù)組下標(biāo) 例：如果一個(gè)4階對(duì)稱矩陣A如下所示，只存儲(chǔ)下三 例：如果一個(gè)n階對(duì)稱矩陣A只存在下三