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ù)的存儲結(jié)構(gòu)：順序存儲、鏈?zhǔn)浇Y(jié)構(gòu)。）數(shù)據(jù)的存儲結(jié)構(gòu)：順序存儲、鏈?zhǔn)浇Y(jié)構(gòu)。（3）運算（算法）運算（算法） 三、算法分析（設(shè)計）的要求：三、算法分析（設(shè)計）的要求： （1）正確性）正確性 （2）可讀性）可讀性 （3）健壯性）健壯性 （4）高效率與低存儲量）高效率與低存儲量 二、算法的概念二、算法的概念 算法是解決給定問題的一種方法（策略）。算法是解決給定問題的一種方

2、法（策略）。四、算法的時間復(fù)雜性分析四、算法的時間復(fù)雜性分析 指算法中各語句執(zhí)行時間的總和指算法中各語句執(zhí)行時間的總和 用大用大O O表示。表示。 如：如：T(n)=O(nT(n)=O(n2 2) ) 解釋解釋：隨著隨著問題規(guī)模問題規(guī)模 n 的增大，算法的執(zhí)的增大，算法的執(zhí)行時間行時間 T(n)與與n2成正比成正比。O(1) O(log2n) O(n)O(nlog2n)O(n2) O(n3) O(2n) 也即隨著也即隨著n的增大的增大, f(n)增長較慢的算法為增長較慢的算法為較優(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;問題：問題：(1) 該算法的功能是計算該算法的功能是計算 xn 。(2) 該算法的時間復(fù)雜度是該算法的時間復(fù)雜度是 0(n) 。(3) 若執(zhí)行一次條件判斷和執(zhí)行一次賦值所需時間相同，若執(zhí)行一次條件判斷和執(zhí)行一次賦值所需時間相同，都是一個單位時間，則該算法的執(zhí)行時間等于都是一個單位時間，則該算法的執(zhí)行時間等于 3n1 個單位時間。個單位時間。（1）順序存儲結(jié)構(gòu)（順序表）順序存儲結(jié)構(gòu)（順序表） hea

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

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

6、x 輸出：在第輸出：在第i處插入新元素處插入新元素x后，得到長度為后，得到長度為n+1的線性表的線性表void list_insert( ) void list_insert( ) / /* * 在長度為在長度為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( (“ 插入位置錯插入位置錯”); ); 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+ ；/ /* * 表長加表長加1 1 * */ / 算法list_insert的時間復(fù)雜性 T(n)=O(n)（）刪除算法設(shè)計（）刪除算法設(shè)計 輸入：長度為輸入：長度為n的線性表的線性表a1.an, 刪除位置刪除位置 i ; 輸出：刪除第輸出：刪除第i個元素后，得到長度為個元素后，得到長度為n-1的線性表的線性表 void list_delete( )

8、 void list_delete( ) / /* * 刪除線性表刪除線性表a1.na1.n中的第中的第i i個元素個元素 * */ / int j;int j; if (in) errorif (in) error( (“刪除位置錯刪除位置錯”) ;) ; 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- ；/ /* * 表長減表長減1 1 *

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

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

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

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

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

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

15、0; int j=0; / /* * j j為計數(shù)器為計數(shù)器 * */ / while (p-next!=NULL & jnext!=NULL & jnext; j+; p=p-next; j+; / /* *尋找第尋找第i-1i-1個結(jié)點個結(jié)點(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的下一個結(jié)點的下一個結(jié)點( (即第即第i i個結(jié)點）個結(jié)點）* */ / p-next=q-next; p-next=q-next; / /*

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

17、 n個分量中個分量中 且遞增有序且遞增有序, , 將將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個元素，將個元素，將k k個元素一次刪除個元素一次刪除 * */ / n - = k; n - = k; / /* * 表長表長k k *

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

19、 找到第找到第1個值為個值為0的結(jié)點的結(jié)點 */ 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é)點的結(jié)點(p-next=x)(p-next=x)* */ / if ( p-next!=NULL) if ( p-next!=NULL) q=p-next; q=p-next; / /* *q q指向指向p p的下一個結(jié)點的下一個結(jié)點( (即值為即值為x x的結(jié)點）的結(jié)點）* */ / p-next=q-next; p-next=q-next; / /* *刪除值為刪除值為x x的結(jié)點的結(jié)點* */ /free(q) ;