數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)線表講義

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)線表講義 第章第章 緒論緒論一、數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容一、數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的聯(lián)系。數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的聯(lián)系。（1）數(shù)據(jù)的邏輯結(jié)構(gòu)：線性表、樹、圖。）數(shù)據(jù)的邏輯結(jié)構(gòu)：線性表、樹、圖。（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)、鏈?zhǔn)浇Y(jié)構(gòu)。）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)、鏈?zhǔn)浇Y(jié)構(gòu)。（3）運(yùn)算（算法）運(yùn)算（算法） 三、算法分析（設(shè)計(jì)）的要求：三、算法分析（設(shè)計(jì)）的要求： （1）正確性）正確性 （2）可讀性）可讀性 （3）健壯性）健壯性 （4）高效率與低存儲(chǔ)量）高效率與低存儲(chǔ)量 二、算法的概念二、算法的概念 算法是解決給定問題的一種方法（策略）。算法是解決給定問題的一種方

2、法（策略）。四、算法的時(shí)間復(fù)雜性分析四、算法的時(shí)間復(fù)雜性分析 指算法中各語句執(zhí)行時(shí)間的總和指算法中各語句執(zhí)行時(shí)間的總和 用大用大O O表示。表示。 如：如：T(n)=O(nT(n)=O(n2 2) ) 解釋解釋：隨著隨著問題規(guī)模問題規(guī)模 n 的增大，算法的執(zhí)的增大，算法的執(zhí)行時(shí)間行時(shí)間 T(n)與與n2成正比成正比。O(1) O(log2n) O(n)O(nlog2n)O(n2) O(n3) O(2n) 也即隨著也即隨著n的增大的增大, f(n)增長(zhǎng)較慢的算法為增長(zhǎng)較慢的算法為較優(yōu)較優(yōu). 例1-1 分析下列的算法，求T(n). （用大O表示）(1) i=1;j=0; while(i+jj) j

3、+; else i+; T(n)=O(n)(2) x=1; for (i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k1) y= y*x; n=n1; return y;問題：?jiǎn)栴}：(1) 該算法的功能是計(jì)算該算法的功能是計(jì)算 xn 。(2) 該算法的時(shí)間復(fù)雜度是該算法的時(shí)間復(fù)雜度是 0(n) 。(3) 若執(zhí)行一次條件判斷和執(zhí)行一次賦值所需時(shí)間相同，若執(zhí)行一次條件判斷和執(zhí)行一次賦值所需時(shí)間相同，都是一個(gè)單位時(shí)間，則該算法的執(zhí)行時(shí)間等于都是一個(gè)單位時(shí)間，則該算法的執(zhí)行時(shí)間等于 3n1 個(gè)單位時(shí)間。個(gè)單位時(shí)間。（1）順序存儲(chǔ)結(jié)構(gòu)（順序表）順序存儲(chǔ)結(jié)構(gòu)（順序表） hea

4、dk1k2k3 k4a2a3aiana1（2）非順序存儲(chǔ)結(jié)構(gòu)（鏈表）非順序存儲(chǔ)結(jié)構(gòu)（鏈表）0 1 2 i n 第章第章 線性表線性表一、線性表的定義一、線性表的定義 n（n=0）個(gè)元素的有限集，(a1,a2,a3, an)， 每個(gè)元素的位置是線性（一維）的。二、線性表的兩種結(jié)構(gòu)二、線性表的兩種結(jié)構(gòu)三、順序表和鏈表的插入和刪除操作三、順序表和鏈表的插入和刪除操作（1）順序表的插入和刪除順序表的插入和刪除在順序表的第 i 處插入 1 個(gè)結(jié)點(diǎn)，有n-i+1個(gè)結(jié)點(diǎn)后移；刪除第 i 個(gè)結(jié)點(diǎn)有n-i個(gè)結(jié)點(diǎn)前移。 0 1 2 i n（2）鏈表的插入和刪除）鏈表的插入和刪除a2a3aiana1# #defin

5、e MAXSIZE 10000define MAXSIZE 10000int aMAXSIZE+1;int aMAXSIZE+1; / /* * 線性表的容量線性表的容量 * */ /int n;int n; / /* * 線性表的表長(zhǎng)線性表的表長(zhǎng) * */ /線性表的容量線性表的容量aMAXSIZE+1;線性表的長(zhǎng)度線性表的長(zhǎng)度int n;四、基于順序表四、基于順序表( (數(shù)組數(shù)組) )的算法設(shè)計(jì)的算法設(shè)計(jì)loc(ai) = loc(a1)+(i-1)*len（）（）插入算法設(shè)計(jì)插入算法設(shè)計(jì) 輸入：長(zhǎng)度為輸入：長(zhǎng)度為n的線性表的線性表a1.an, 插入位置插入位置 i 和插入元素和插入元素

6、x 輸出：在第輸出：在第i處插入新元素處插入新元素x后，得到長(zhǎng)度為后，得到長(zhǎng)度為n+1的線性表的線性表void list_insert( ) void list_insert( ) / /* * 在長(zhǎng)度為在長(zhǎng)度為n n的線性表的線性表a1.na1.n的第的第i i處插入新元素處插入新元素x x * */ / int j; int j; if (n=MAXSIZE) error if (n=MAXSIZE) error( (“表滿表滿”);); else if(in+1)errorelse if(in+1)error( (“ 插入位置錯(cuò)插入位置錯(cuò)”); ); else for (j=n; j=i

7、; j-) else for (j=n; j=i; j-) aj+1= aj; aj+1= aj; / /* * 元素后移元素后移 * */ / ai= x; ai= x; / /* * 在第在第i i處插入處插入x x * */ / n+ n+ ；/ /* * 表長(zhǎng)加表長(zhǎng)加1 1 * */ / 算法list_insert的時(shí)間復(fù)雜性 T(n)=O(n)（）刪除算法設(shè)計(jì)（）刪除算法設(shè)計(jì) 輸入：長(zhǎng)度為輸入：長(zhǎng)度為n的線性表的線性表a1.an, 刪除位置刪除位置 i ; 輸出：刪除第輸出：刪除第i個(gè)元素后，得到長(zhǎng)度為個(gè)元素后，得到長(zhǎng)度為n-1的線性表的線性表 void list_delete( )

8、 void list_delete( ) / /* * 刪除線性表刪除線性表a1.na1.n中的第中的第i i個(gè)元素個(gè)元素 * */ / int j;int j; if (in) errorif (in) error( (“刪除位置錯(cuò)刪除位置錯(cuò)”) ;) ; else if (n=0) errorelse if (n=0) error( (“表空表空”) )； elseelse for (j=i+1; j=n; j+) for (j=i+1; j=n; j+) aj-1=aj; aj-1=aj; / /* * 元素前移元素前移 * */ / n- n- ；/ /* * 表長(zhǎng)減表長(zhǎng)減1 1 *

9、*/ / 算法list_delete的時(shí)間復(fù)雜性 T(n)=O(n)head : 指針變量,存儲(chǔ)第一個(gè)結(jié)點(diǎn)的地址五、基于鏈表的算法設(shè)計(jì)五、基于鏈表的算法設(shè)計(jì)（）查找（定位）算法設(shè)計(jì)（）查找（定位）算法設(shè)計(jì) 1. 1. 功能功能 在鏈表中查找（定位于）第在鏈表中查找（定位于）第i i個(gè)結(jié)點(diǎn)，若存在，個(gè)結(jié)點(diǎn)，若存在，則返回該結(jié)點(diǎn)的地址，否則，返回空（則返回該結(jié)點(diǎn)的地址，否則，返回空（NULLNULL）。）。 2. 2. 算法思想算法思想 從第一個(gè)結(jié)點(diǎn)開始，逐個(gè)查找（后移）并計(jì)數(shù)，從第一個(gè)結(jié)點(diǎn)開始，逐個(gè)查找（后移）并計(jì)數(shù)，直到第直到第i i個(gè)結(jié)點(diǎn)止。個(gè)結(jié)點(diǎn)止。3. 3. 算法設(shè)計(jì)算法設(shè)計(jì)node n

10、ode * *loc(node loc(node * *head, int i) head, int i) / /* *head:head:帶頭結(jié)點(diǎn)的單鏈表的頭指針，該算法定位于表中的第帶頭結(jié)點(diǎn)的單鏈表的頭指針，該算法定位于表中的第i i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)* */ / node node * *p=head;p=head; / /* *指針初始化指針初始化, p, p指向頭結(jié)點(diǎn)指向頭結(jié)點(diǎn)* */ / int j=0; int j=0; / /* * j j為計(jì)數(shù)器，初值為為計(jì)數(shù)器，初值為0 0* */ / while (p!=NULL)&(ji) while (p!=NULL)&(jnext; j+

11、; p=p-next; j+; / /* * p p后移，后移，j j計(jì)數(shù)計(jì)數(shù),p ,p移至第移至第i i個(gè)結(jié)點(diǎn)止個(gè)結(jié)點(diǎn)止 * */ / return (p); return (p); / /* * p p指向第指向第i i個(gè)結(jié)點(diǎn)（返回第個(gè)結(jié)點(diǎn)（返回第i i個(gè)結(jié)點(diǎn)的地址）個(gè)結(jié)點(diǎn)的地址）* */ / 算法Loc的時(shí)間復(fù)雜性 T(n)=O(n)(2)(2)插入算法設(shè)計(jì)插入算法設(shè)計(jì)1. .功能：在線性表第功能：在線性表第i i處插入其數(shù)值為處插入其數(shù)值為x x新結(jié)點(diǎn)。新結(jié)點(diǎn)。 2. 2.算法思想：算法思想： 首先，找到第首先，找到第i-1i-1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（p p指向第指向第i-1i-1個(gè)結(jié)點(diǎn)）；

12、個(gè)結(jié)點(diǎn)）；然后，在然后，在p p結(jié)點(diǎn)之后插入值為結(jié)點(diǎn)之后插入值為x x新結(jié)點(diǎn)新結(jié)點(diǎn)q q。在結(jié)點(diǎn)在結(jié)點(diǎn)p p之后插入新結(jié)點(diǎn)之后插入新結(jié)點(diǎn)q: q: 頭結(jié)點(diǎn)頭結(jié)點(diǎn)的作用的作用q-next=p-next;P-next=q;3. 3.算法設(shè)計(jì)算法設(shè)計(jì)void ins(node void ins(node * *head, int i, elemtype x,node head, int i, elemtype x,node * *q q) ) / /* * head: head:帶頭結(jié)點(diǎn)的單鏈表的頭指針，該算法在第帶頭結(jié)點(diǎn)的單鏈表的頭指針，該算法在第i i個(gè)結(jié)個(gè)結(jié) 點(diǎn)后面插入其數(shù)值為點(diǎn)后面插入其數(shù)值

13、為x x新結(jié)點(diǎn)新結(jié)點(diǎn)q q* */ / node node * *p; p; p=loc(head,i-1); p=loc(head,i-1); / /* * 令令 p p 指向第指向第i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) if (p!=NULL)if (p!=NULL) q-next=p-next; p-next=qq-next=p-next; p-next=q; ; / /* *在在p p結(jié)點(diǎn)之后插入值為結(jié)點(diǎn)之后插入值為x x新結(jié)點(diǎn)新結(jié)點(diǎn)q q * */ / 算法ins的時(shí)間復(fù)雜性 T(n)=O(n)(3)(3)刪除算法設(shè)計(jì)刪除算法設(shè)計(jì) 1. .功能：刪除第功能：刪除第i i個(gè)結(jié)點(diǎn)。個(gè)結(jié)點(diǎn)。 2. 2

14、.算法思想：算法思想：首先，找到第首先，找到第i-1i-1個(gè)結(jié)點(diǎn)（個(gè)結(jié)點(diǎn)（p p指向第指向第i-1i-1個(gè)結(jié)點(diǎn)）；個(gè)結(jié)點(diǎn)）；然后，刪除然后，刪除p p的下一個(gè)結(jié)點(diǎn)。的下一個(gè)結(jié)點(diǎn)。3.3.算法設(shè)計(jì)算法設(shè)計(jì)void del (node* head, int i, elemtype *e) / /* * head: head:帶頭結(jié)點(diǎn)的單鏈表的頭指針，刪除表中的帶頭結(jié)點(diǎn)的單鏈表的頭指針，刪除表中的i i個(gè)結(jié)點(diǎn)，并將結(jié)點(diǎn)個(gè)結(jié)點(diǎn)，并將結(jié)點(diǎn)的值回帶（的值回帶（* *e e）* */ / node node * *p=head; p=head; / /* * 指針初始化指針初始化 * */ / int j=

15、0; int j=0; / /* * j j為計(jì)數(shù)器為計(jì)數(shù)器 * */ / while (p-next!=NULL & jnext!=NULL & jnext; j+; p=p-next; j+; / /* *尋找第尋找第i-1i-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(p)(p)* */ / if ( p-next!=NULL & j=i-1 ) if ( p-next!=NULL & j=i-1 ) q=p-next; q=p-next; / /* *q q指向指向p p的下一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)( (即第即第i i個(gè)結(jié)點(diǎn)）個(gè)結(jié)點(diǎn)）* */ / p-next=q-next; p-next=q-next; / /*

16、*刪除第刪除第i i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)* */ / * *e=q-data ; e=q-data ; / /* *保留第保留第i i個(gè)結(jié)點(diǎn)的值個(gè)結(jié)點(diǎn)的值 * */ / free(q) ; free(q) ; 例2-1 線性表有8000個(gè)數(shù)據(jù)元素，若采用順序存儲(chǔ)(一維數(shù)組），第一個(gè)結(jié)點(diǎn)的地址為1000，每個(gè)結(jié)點(diǎn)的值需占用8個(gè)存儲(chǔ)單元。問 （1） 該線性表需要多大的存儲(chǔ)空間？ （2）第113個(gè)結(jié)點(diǎn)的起始地址是多少？ （3）在線性表的第 34 處插入一個(gè)新元素，有多少個(gè)元素向后移動(dòng)?六、示例六、示例例例2.12.1設(shè)線性表存于整型數(shù)組設(shè)線性表存于整型數(shù)組 a1.MAXSIZEa1.MAXSIZE的前的前n

17、 n個(gè)分量中個(gè)分量中 且遞增有序且遞增有序, , 將將x x插入到線性表的適當(dāng)位置。插入到線性表的適當(dāng)位置。 void ins( ) void ins( ) int i; int i; if if （nMAXSIZEn=1 & x=1 & x0 & 1=i & i+k-10 & 1=i & i+k-1=n ) for (j=i+k; j=n; +j) for (j=i+k; j=n; +j) aj-k=aj; aj-k=aj; / /* * 前移前移k k個(gè)元素，將個(gè)元素，將k k個(gè)元素一次刪除個(gè)元素一次刪除 * */ / n - = k; n - = k; / /* * 表長(zhǎng)表長(zhǎng)k k *

18、*/ / 思考：算法的選擇及效率思考：算法的選擇及效率（1）每次刪除）每次刪除1個(gè)元素，做個(gè)元素，做k次次（2）一次將）一次將k個(gè)元素全部刪除個(gè)元素全部刪除例例2.3 2.3 已知線性表存于已知線性表存于a1.MAXSIZEa1.MAXSIZE中的前中的前n n個(gè)分量個(gè)分量 中，寫一算法刪除表中所有值為中，寫一算法刪除表中所有值為0 0的元素（將非的元素（將非 0 0元素移到前面來），各元素間的相對(duì)位置不變。元素移到前面來），各元素間的相對(duì)位置不變。void del_0( ) /* 刪除所有值為刪除所有值為0的元素的元素 */ i=1; while(i=n)&(ai!=0) i=i+1; /*

19、 找到第找到第1個(gè)值為個(gè)值為0的結(jié)點(diǎn)的結(jié)點(diǎn) */ for(j=i+1;jnext!=NULL & p-next-data!=x)while (p-next!=NULL & p-next-data!=x) p=p-next; p=p-next; / /* *尋找表中值為尋找表中值為x x的結(jié)點(diǎn)的結(jié)點(diǎn)(p-next=x)(p-next=x)* */ / if ( p-next!=NULL) if ( p-next!=NULL) q=p-next; q=p-next; / /* *q q指向指向p p的下一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)( (即值為即值為x x的結(jié)點(diǎn)）的結(jié)點(diǎn)）* */ / p-next=q-next; p-next=q-next; / /* *刪除值為刪除值為x x的結(jié)點(diǎn)的結(jié)點(diǎn)* */ /free(q) ;