概論線性表和數(shù)據(jù)結構

1、數(shù)據(jù)結構第1章 數(shù)據(jù)結構概論 本章主要介紹以下內容 數(shù)據(jù)結構研究的主要內容 數(shù)據(jù)結構中涉及的基本概念 算法的概念、描述方法以及評價標準1.1 數(shù)據(jù)結構研究的主要內容當今計算機應用的特點： l 所處理的數(shù)據(jù)量大且具有一定的關系； 2 對其操作不再是單純的數(shù)值計算，而更多地是需要對其進行組織、管理和檢索。 應用舉例1學籍檔案管理 假設一個學籍檔案管理系統(tǒng)應包含如下表1-1所示的學生信息。表1-1 特點： l 每個學生的信息占據(jù)一行，所有學生的信息按學號順序依次排列構成一張表格； 2 表中每個學生的信息依據(jù)學號的大小存在著一種前后關系，這就是我們所說的線性結構； 3 對它的操作通常是插入某個學生的信

2、息，刪除某個學生的信息，更新某個學生的信息，按條件檢索某個學生的信息等等。 應用舉例2輸出n個對象的全排列 輸出n個對象的全排列可以使用下圖1-1所示的形式描述。圖 1-1 3個對象的全排列過程特點： l在求解過程中，所處理的數(shù)據(jù)之間具有層次關系，這是我們所說的樹形結構； l對它的操作有：建立樹形結構，輸出最低層結點內容等等。應用舉例3制定教學計劃 在制定教學計劃時，需要考慮各門課程的開設順序。有些課程需要先導課程，有些課程則不需要，而有些課程又是其他課程的先導課程。比如，計算機專業(yè)課程的開設情況如下表1-2所示：表1-2課程先后關系的圖形描形式：c1c9c4c2c12c10c11c5c3c6

3、c7c8圖 1-2 計算機專業(yè)必修課程開設先后關系 特點 l課程之間的先后關系用圖結構描述； 2通過實施創(chuàng)建圖結構，按要求將圖結構中的頂點進行線性排序。 結論 計算機的操作對象的關系更加復雜，操作形式不再是單純的數(shù)值計算，而更多地是對這些具有一定關系的數(shù)據(jù)進行組織管理，我們將此稱為非數(shù)值性處理。要使計算機能夠更有效地進行這些非數(shù)值性處理，就必須弄清楚這些操作對象的特點，在計算機中的表示方式以及各個操作的具體實現(xiàn)手段。這些就是數(shù)據(jù)結構這門課程研究的主要內容。1.2 基本概念和術語數(shù)據(jù) 是對客觀事物的符號表示。在計算機科學中其含義是指所有能夠輸入到計算機中并被計算機程序處理的符號集合。數(shù)據(jù)元素 是

4、數(shù)據(jù)集合中的一個實體，是計算機程序中加工處理的基本單位。 數(shù)據(jù)元素按其組成可分為簡單型數(shù)據(jù)元素和復雜型數(shù)據(jù)元素。簡單型數(shù)據(jù)元素由一個數(shù)據(jù)項組成，所謂數(shù)據(jù)項就是數(shù)據(jù)中不可再分割的最小單位；復雜型數(shù)據(jù)元素由多個數(shù)據(jù)項組成，它通常攜帶著一個概念的多方面信息。 數(shù)據(jù)結構 簡單地說，就是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。常見的數(shù)據(jù)結構有：線性結構、樹形結構和圖形結構。 邏輯結構 數(shù)據(jù)結構中所說的“關系”實際上是指數(shù)據(jù)元素之間的邏輯關系，又稱此為邏輯結構。存儲結構（物理結構） 是指數(shù)據(jù)結構在計算機存儲器中的具體實現(xiàn)。與孤立的數(shù)據(jù)元素表示形式不同，數(shù)據(jù)結構中的數(shù)據(jù)元素不但要表示其本身的實際內容

5、，還要表示清楚數(shù)據(jù)元素之間的邏輯結構。常見的存儲結構 順序存儲結構：特點是借助于數(shù)據(jù)元素的相對存儲位置來表示數(shù)據(jù)元素之間的邏輯結構； 鏈式存儲結構：特點是借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元素之間的邏輯結構。1.3 算法 1.3.1 算法的概念 算法是解決某個特定問題的一種方法或一個過程。 計算機對數(shù)據(jù)的操作可以分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進行的是算術運算；而在非數(shù)值性操作中主要進行的是檢索、排序、插入、刪除等等。設計算法的基本過程 l通過對問題進行詳細地分析，抽象出相應的數(shù)學模型； 2確定使用的數(shù)據(jù)結構，并在此基礎上設計對此數(shù)據(jù)結構實施各種操作的算法； 3選用某種語言將

6、算法轉換成程序； 4調試并運行這些程序。算法應該具有下列五個特性（1）有窮性：一個算法必須在執(zhí)行有窮步之后結束。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時不會產生二義性。（3）可行性：算法中描述的每一步操作都可以通過已有的基本操作執(zhí)行有限次實現(xiàn)。（4）輸入：一個算法應該有零個或多個輸入。（5）輸出：一個算法應該有一個或多個輸出。這里所說的輸出是指與輸入有某種特定關系的量。舉例問題：按從小到大的順序重新排列x，y，z三個數(shù)值的內容。算法： （1）輸入x，y，z三個數(shù)值； （2）從三個數(shù)值中挑選出最小者并換到x中； （3）從y，z中挑選出較小者并換到y(tǒng)中； （4）輸出排序后的結果

7、。 1.3.2 算法的描述 選擇算法描述語言的準則（1）該語言應該具有描述數(shù)據(jù)結構和算法的基本功能；（2）該語言應該盡可能地簡捷，以便于掌握、理解；（3）使用該語言描述的算法應該能夠比較容易地轉換成任何一種程序設計語言。 “類C”描述語言是通過對C語言進行精心篩選保留的一個核心子集，并為了便于描述，又做了若干擴展修改，從而，增強了語言的描述功能。 1. 預定義常量及類型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 數(shù)據(jù)元素被約定為dateType 類型，用戶需要根據(jù)具體情況，自行

8、定義該數(shù)據(jù)類型。2. 算法描述為以下的函數(shù)形式： 函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） 語句序列； 為了簡化函數(shù)的書寫，提高算法描述的清晰度，我們規(guī)定除函數(shù)參數(shù)表中的參數(shù)需要說明數(shù)據(jù)類型外，函數(shù)中使用的局部變量可以不做變量說明，必要時給出相應的注釋即可。另外，在書寫算法時，應該養(yǎng)成對重點語句段落添加注解的良好習慣。3. 在算法描述中可以使用的賦值語句形式有： 簡單賦值 變量名 = 表達式； 串聯(lián)賦值 變量名1 = 變量名2 = . = 變量名n = 表達式； 成組賦值 （變量名1，.，變量名n）=（表達式1，.，表達式n）； 結構賦值 結構名1 = 結構名2； 結構名 =（值1，值2，.，值n）；

9、條件賦值 變量名 = 條件表達式 ? 表達式1：表達式2； 交換賦值 變量名1 變量名2；4. 在算法描述中可以使用的選擇結構語句形式有：條件語句1 if （表達式） 語句；條件語句2 if （表達式） 語句； else 語句；開關語句1 switch （表達式） case 值1：語句序列1；break； case 值2：語句序列2；break； . case 值n：語句序列n；break； default：語句序列n+1； 開關語句2 switch case 條件1：語句序列1；break； case 條件2：語句序列2；break； . case 條件n：語句序列n；break； defa

10、ult：語句序列n+1； 5. 在算法描述中可以使用的循環(huán)結構語句形式有： for循環(huán)語句 for （表達式1；循環(huán)條件表達式； 表達式2） 語句； while循環(huán)語句 while （循環(huán)條件表達式） 語句； do-while循環(huán)語句 do 語句序列； while （循環(huán)條件表達式）；6. 在描述算法中可以使用的結束語句形式有： 函數(shù)結束語句 return 表達式； return; case或循環(huán)結束語句 break; 異常結束語句 exit（異常代碼）； 7. 在算法描述中可以使用的輸入輸出語句形式有： 輸入語句 scanf( 格式串，變量名1，.，變量名n)； 輸出語句 printf( 格

11、式串，表達式1，.，表達式n); /方括號（ ）中的內容是可以省略的部分。8. 在算法描述中使用的注釋格式為： 單行注釋 /文字序列9. 在算法描述中可以使用的擴展函數(shù)有： 求最大值 max（表達式1，.，表達式n）；這個函數(shù)返回參數(shù)表中n個表達式計算結果中的最大值。 求最小值 min（表達式1，.，表達式n）；這個函數(shù)返回參數(shù)表中n個表達式計算結果中的最小值。【算法1-1】用類C描述將三個數(shù)值排序的算法。 viod Three_Sort( int *x,int *y,int *z)/將x,y,z三個指針所指示的內容按從小到大的順序重新排列 /挑選出最小的數(shù)值并換到 x指針所指的存儲單元中 i

12、f (*y*x&*y*z) *x*y; else if (*z*x&*z*y) *x*z; /在y和z所指示的存儲單元中挑選出較小者換到y(tǒng)中 if(*zlength=-1； /將當前線性表長度置0 return L； 2. 銷毀線性表Lvoid Destroy_List(SQ_LIST *L) if (L) free(L); /釋放線性表占據(jù)的所有存儲空間3. 清空線性表Lvoid Clear_List(SQ_LIST *L) L-length=-1; /將線性表的長度置為04. 求線性表L的長度int Length_List(SQ_LIST L) return (L.length+1); 5

13、. 判斷線性表L是否為空int IsEmpty(SQ_LIST L) if (L.length= =-1) return TRUE; else return FALSE;6. 獲取線性表L中的某個數(shù)據(jù)元素的內容int Get _List(SQ_LIST L,int i,dataType *e) if (iL .length+1) return ERROR; /判斷i值是否合理，若不合理，返回ERROR *e=L .datai-1; /數(shù)組中第i-1的單元存儲著線性表中第i個數(shù)據(jù)元素的內容 return OK;7. 在線性表L中檢索值為e的數(shù)據(jù)元素int Locate _List(SQ_LIST

14、 *L,dataType e) for (i=0;ilength;i+) if (L-datai= =e) return i+1; return 0;8. 在線性表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e int Insert_List (SQ_LIST *L,int i, dataType e) if (L-length=LIST_MAX_LENGTH-1) return ERROR; /檢查是否有剩余空間 if (iL-length+2) return ERROR; /檢查i值是否合理 for (j=L-length;j=i-1; j- -) /將線性表第i個元素之后的所有元素向后移動 L-d

15、ataj+1=L-dataj; L-datai-1=e; /將新元素的內容放入線性表的第i個位置 L-length+; return OK;9. 將線性表L中第i個數(shù)據(jù)元素刪除int Delete_List (SQ_LIST *L,int i,dataType *e) if (IsEmpty(*L) return ERROR; /檢測線性表是否為空 if (iL-length+1) return ERROR; /檢查i值是否合理 *e=L-datai-1; /將欲刪除的數(shù)據(jù)元素內容保留在e所指示的存儲單元中 for (j=i;jlength;j+) /將線性表第i+1個元素之后的所有元素向前移

16、動 L-dataj-1=L-dataj; L-length- -; return OK; 插入算法的分析 假設線性表中含有n個數(shù)據(jù)元素，在進行插入操作時，若假定在n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為： 刪除算法的分析 在進行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為： 分析結論 順序存儲結構表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當線性表的數(shù)據(jù)元素量較大，并且經常要對其做插入或刪除操作時，這一點需要值得考慮。2.3 線性表的鏈式存儲結構 線性表順序存儲結構的特點： 它是一種簡單、方便的存儲方式。它要求線性表的數(shù)據(jù)元素依次

17、存放在連續(xù)的存儲單元中，從而利用數(shù)據(jù)元素的存儲順序表示相應的邏輯順序，這種存儲方式屬于靜態(tài)存儲形式。 暴露的問題： l 在做插入或刪除元素的操作時，會產生大量的數(shù)據(jù)元素移動； 2 對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用； 3 線性表的容量難以擴充。線性表的鏈式存儲結構 線性表的鏈式存儲結構是指用一組任意的存儲單元（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關系，對于每個數(shù)據(jù)元素不僅要表示它的具體內容，還要附加一個表示它的直接后繼元素存儲位置的信息。假設有一個線性表（a,b,c,d），可用下圖2-2所示的形式存儲：

18、圖2-2 線性表鏈式存儲結構示意圖 術語： 表示每個數(shù)據(jù)元素的兩部分信息組合在一起被稱為結點；其中表示數(shù)據(jù)元素內容的部分被稱為數(shù)據(jù)域（data）； 表示直接后繼元素存儲地址的部分被稱為指針或指針域（next）。 單鏈表簡化的圖2-3描述形式headd cba圖 2-3 單鏈表結構示意圖 其中，head是頭指針，它指向單鏈表中的第一個結點，這是單鏈表操作的入口點。由于最后一個結點沒有直接后繼結點，所以，它的指針域放入一個特殊的值NULL。NULL值在圖示中常用（ ）符號表示。 帶頭結點的單鏈表： 為了簡化對鏈表的操作，人們經常在鏈表的第一個結點之前附加一個結點，并稱為頭結點。這樣可以免去對鏈表第

19、一個結點的特殊處理。如下圖2-4所示：d headcba圖 2-4 帶頭結點的單鏈表結構示意圖鏈式存儲結構的特點（1）線性表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致；（2）在對線性表操作時，只能通過頭指針進入鏈表，并通過每個結點的指針域向后掃描其余結點，這樣就會造成尋找第一個結點和尋找最后一個結點所花費的時間不等。在C語言中，實現(xiàn)線性表的鏈式存儲結構的類型定義 typedef struct node /結點類型及表頭類型 datatype data; struct node *next; LNODE,* LINK_LIST;2.3.2 典型操作的算法實現(xiàn)1初始化鏈表L(在單鏈表的

20、頭部插入結點)LINK_LIST Init_List1() LINK_LIST L=NULL； LNODE *s; int x; scanf(“%d”,&x); while(x!=-1) s=malloc(sizeof(LNODE); s-data=x; s-next=L; L=s; scanf(“%d”,&x); return L ; 2 初始化鏈表L(在單鏈表的尾部插入結點)LINK_LIST Init_List2() LINK_LIST L=NULL； LNODE *s，*R=NULL; int x; scanf(“%d”,&x); while(x!=-1) s=malloc(sizeo

21、f(LNODE)； s-data=x； if (L= =NULL) L=s； else R-next=s； R=s； scanf(“%d”,&x)； if (R!=NULL) R-next=NULL； return L ; 2. 清空鏈表L void Destory_List(LINK_LIST L) LNODE *p; while (L-next) /依次刪除鏈表中的所有結點 p=L-next; L-next=p-next; free(p); 3. 求鏈表L的長度int Length_List (LINK_LIST L) LNODE *p； int len； for(p=L, len=0；p

22、-next!=NULL；len+,p=p-next); return(len)；4. 判鏈表L空否 int IsEmpty(LINK_LIST L) if (L-next=NULL) return TRUE; else return FALSE; 5. 在鏈表L中查找到第i個元素，并把元素內容放到元素e中LNODE *Get_List(LINK_LIST L,int i, dataType *e) LNODE *p=L; int j; /檢測i值的合理性 if (iLength_List(L) return NULL; for (j=0;jnext,j+); *e=p-data; /將第i個結

23、點的內容賦給e return p; /返回指針p6. 在鏈表L中檢索值為e的數(shù)據(jù)元素LNODE *LocateELem(LINK_LIST L,dataType e) LNODE *p; for (p=L-next;p!=NULL&p-data!=e;p=p-next); /尋找滿足條件的結點 return(p);7. 返回鏈表L中結點e的直接前驅結點LNODE *PriorElem(LINK_LIST L,LNODE* e) LNODE *p; if (L-next-data=e) return NULL; /檢測第一個結點 for (p=L-next;p-next!=NULL & p-ne

24、xt-data!=e;p=p-next); if (p-next-data=e) return p; else return NULL; 8. 返回鏈表L中結點e的直接后繼結點LNODE *NextElem(LINK_LIST L,LNODE *e) LNODE *p; for(p=L-next;p&p!=e;p=p-next); if (p) p=p-next; return p;9. 在鏈表L中第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e int Insert_List (LINK_LIST L,int i,dataType e) LNODE *p,*s; p=Get_List(L,i-1); if(

25、p= =NULL) printf(“參數(shù)錯誤！”);return 0; else s=malloc(sizeof(LNODE); if (s=NULL) return ERROR; s-data=e; s-next=p-next; p-next=s; return OK;10. 將鏈表L中第i個數(shù)據(jù)元素刪除，并將其內容保存在e中int Delete_List (LINK_LIST L,int i,dataType *e) LNODE *p，*s; p=Get_List(L,i-1); if(p= =NULL) printf(“第i-1個結點不存在！”);return -1; else if(p

26、-next= =NULL) printf(“第i個結點不存在！”);return 0; else s=p-next; /用s指向將要刪除的結點 *e=s-data; p-next=s-next; /刪除s指針所指向的結點 free(s); return OK; 2.3.3 循環(huán)鏈表 若將鏈表中最后一個結點的next域指向頭結點 實現(xiàn)循環(huán)鏈表的類型定義與單鏈表完全相同，它的所有操作也都與單鏈表類似。只是判斷鏈表結束的條件有所不同。下面我們就列舉兩個循環(huán)鏈表操作的算法示例。head 圖2-7 帶頭結點的循環(huán)鏈表示意圖1. 初始化鏈表CLLINK_LIST InitList() LINK_LIST

27、CL; LNODE *s，*R=NULL; CL=(LNODE *)malloc(sizeof(LNODE)； CL-next=CL； int x; scanf(“%d”,&x); while(x!=-1) s=(LNODE *)malloc(sizeof(LNODE)； s-data=x； if (CL-next= =CL) s-next=CL;CL-next=s； else s-next=CL;R-next=s； R=s； scanf(“%d”,&x)； return CL ; 2. 在循環(huán)鏈表CL中檢索值為e的數(shù)據(jù)元素LNODE *Locatedata(LINK_LIST CL,data

28、Type e) LNODE *p; for (p=CL-next;(p!=CL)&(p-data!=e);p=p-next); if (p!=CL) return p; else return NULL ; 2.3.4 雙向循環(huán)鏈表 在循環(huán)鏈表中，訪問結點的特點：訪問后繼結點，只需要向后走一步，而訪問前驅結點，就需要轉一圈。 結論：循環(huán)鏈表并不適用于經常訪問前驅結點的情況。 解決方法：在需要頻繁地同時訪問前驅和后繼結點的時候，使用雙向鏈表。所謂雙向鏈表。 雙向鏈表就是每個結點有兩個指針域。一個指向后繼結點，另一個指向前驅結點。圖 2-8headprioritemnext(a)(b)用C語言實現(xiàn)

29、雙向循環(huán)鏈表的類型定義typedef strcut du_node /雙向鏈表的結點類型 dataType item; struct du_node *prior,*next;LNODE,* LINK_LIST;（1）初始化雙向循環(huán)鏈表DLLINK_LIST InitDuList() LINK_LIST DL; LNODE *s，*R=NULL; DL=(LNODE *)malloc(sizeof(LNODE)； DL-next=CL；DL-prior=DL; int x; scanf(“%d”,&x); while(x!=-1) s=(LNODE *)malloc(sizeof(LNODE)

30、； s-data=x； if (DL-next= =DL) s-next=DL;DL-next=s； s-prior=DL;DL-prior=s； else s-next=DL;R-next=s； s-prior=R;DL-prior=s； R=s； scanf(“%d”,&x)； return DL ; （2）在雙向循環(huán)鏈表DL中，第i個數(shù)據(jù)元素之前插入數(shù)據(jù)元素e 在一個結點之前插入一個新結點的過程。 在雙向循環(huán)鏈表中的p結點之前插入s結點應使用下列語句序列： s-next=p; s-prior=p-prior; p-prior-next=s; p-prior=s;圖 2-9ps2.4 線性表的應用舉例 約瑟夫（Joseph）問題：編號為1，2，n的n個人按順時針方向圍坐在一張圓桌旁，每個人手中持有一個密碼（正整數(shù)）。首先輸入一個正整數(shù)作為報數(shù)上限值m，然后，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m的人離開桌旁，并將他手中的密碼作為新的m值，從順時針方向的下一個就坐在桌旁的人人開始重新從1報數(shù)，如此下去，直至所有人全部離開桌旁為止。 假設有7個人，編號從1到7，他們手中的密碼分別是3，1，7，2，4，8，4，最初的m=2，通過報數(shù)，這7個人離開桌旁的順序應該是：2，3，5，4，7，6，1。 數(shù)據(jù)結構的分析 這個問題的主角是n個人，每