1、1,數(shù)據(jù)結(jié)構(gòu) Data Structure,江蘇工業(yè)學(xué)院信息科學(xué)與工程學(xué)院,主講教師：李寧,2,第二講 線性表,線性表的邏輯結(jié)構(gòu) 線性表的順序存儲及實現(xiàn) 線性表的鏈接存儲及實現(xiàn) 順序表和單鏈表的比較 線性表的其他存儲及實現(xiàn),3,學(xué)生成績登記表,2.1 線性表的邏輯結(jié)構(gòu),姓 名,英語,數(shù)據(jù)結(jié)構(gòu),高數(shù),學(xué)號,丁一,96,78,87,0101,李二,87,90,78,0102,張三,67,86,86,0103,孫紅,69,81,96,0104,王冬,87,74,66,0105,4,職工工資登記表,姓 名,崗位津貼,基本工資,獎金,職工號,丁一,600,278,200,0101,李二,300,190,

2、100,0102,張三,300,186,100,0103,孫紅,500,218,200,0104,王冬,300,190,100,0105,數(shù)據(jù)元素之間的關(guān)系是什么？,2.1 線性表的邏輯結(jié)構(gòu),5,線性表：簡稱表，是n（n0）個具有相同類型的數(shù)據(jù)元素的有限序列。 線性表的長度：線性表中數(shù)據(jù)元素的個數(shù)。 空表：長度等于零的線性表，記為：L=( )。 非空表記為：L（a1, a2 , , ai-1, ai , , an),線性表的定義,其中，ai（1in）稱為數(shù)據(jù)元素； 下角標(biāo) i 表示該元素在線性表中的位置或序號 。,2.1 線性表的邏輯結(jié)構(gòu),6,線性表的圖形表示,線性表（a1, a2 , , a

3、i-1, ai , , an)的圖形表示如下：,2.1 線性表的邏輯結(jié)構(gòu),7,1.有限性：線性表中數(shù)據(jù)元素的個數(shù)是有窮的。,2.相同性：線性表中數(shù)據(jù)元素的類型是同一的。,3.順序性：線性表中相鄰的數(shù)據(jù)元素ai-1和ai之間存在序偶關(guān)系(ai-1, ai)，即ai-1是ai的前驅(qū)， ai是ai-1的后繼；a1 無前驅(qū)，an無后繼，其它每個元素有且僅有一個前驅(qū)和一個后繼。,線性表的特性,2.1 線性表的邏輯結(jié)構(gòu),8,線性表的抽象數(shù)據(jù)類型定義,ADT List 數(shù)據(jù)對象：Dai|aiElemset，i1，2，n，n0 數(shù)據(jù)關(guān)系：R1|ai-1，aiD，i1，2，n Operation InitLis

4、t （ typedef struct DataType *Elem; /動態(tài)數(shù)組基址 int length; /線性表當(dāng)前元素個數(shù) int listsize; /順序表當(dāng)前大小 SeqList;,0,順序表的存儲結(jié)構(gòu),2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn),20,Int InitList(SeqList /初始化成功，返回 ,順序表的實現(xiàn)初始化,算法描述：初始化,2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn),21,操作接口： Status ListInsert (SeqList 2. 如果元素的插入位置不合理，則拋出位置異常; 3. 將最后一個元素至第i個元素分別向后移動一個位置； 4. 將元素x填入位置i

5、處； 5. 表長加1；,2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn),順序表的實現(xiàn)插入,算法描述偽代碼,24,void ListInsert (ElemType data ，int i, ElemType x) if (length=MaxSize) printf(“ i 值不符合規(guī)定n ”); if (ilength+1) printf(“表已滿n ”); else for(j=length; j=i; j-) dataj=dataj-1; datai-1=x; length+; ,順序表的實現(xiàn)插入,基本語句？,2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn),25,最好情況（ i=n+1）： 基本語句執(zhí)行0次，時

6、間復(fù)雜度為O(1)。 最壞情況（ i=1）： 基本語句執(zhí)行n+1次，時間復(fù)雜度為O(n)。 平均情況（1in+1）： 時間復(fù)雜度為O(n)。,時間性能分析,順序表的實現(xiàn)插入,2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn),26,操作接口： ListDelete( ilength; i+) if (datai=x) return i+1; return 0; ,順序表的實現(xiàn)按值查找,算法描述：,時間復(fù)雜度？,O(n),2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn),31,順序表的優(yōu)缺點,順序表的優(yōu)點： 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間； 隨機(jī)存?。嚎梢钥焖俚卮嫒”碇腥我晃恢玫脑?。,順序表的缺點：

7、插入和刪除操作需要移動大量元素； 表的容量難以確定，表的容量難以擴(kuò)充； 造成存儲空間的碎片。,2.2 線性表的順序存儲結(jié)構(gòu)及實現(xiàn),32,單鏈表：線性表的鏈接存儲結(jié)構(gòu)。 存儲思想：用一組任意的存儲單元存放線性表的元素。,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表,33,存儲特點： 邏輯次序和物理次序 不一定相同。 2.元素之間的邏輯關(guān)系 用指針表示。,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),例：(a1, a2 ,a3, a4)的存儲示意圖,單鏈表,a1 0200,a2 0325,a3 0300,a4 ,34,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表,數(shù)據(jù)域,指針域,單鏈表是由若干結(jié)點構(gòu)成的； 單鏈

8、表的結(jié)點只有一個指針域。,data：存儲數(shù)據(jù)元素 next：存儲指向后繼結(jié)點的地址,35,s=(ListNode*)malloc(sizeof(ListNode) C+: s=new Node ;,Typedef char ElemType; Typedef struct Listnode dataType data; struct Listnode *next; ListNode，*LinkList;,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表,36,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表,如何引用數(shù)據(jù)元素？,data,如何引用指針域？,next,s-next;,s=(ListNode*

9、)malloc(sizeof(ListNode) C+: s=new Node ;,37,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表,重點在數(shù)據(jù)元素之間的邏輯關(guān)系的 表示，所以，將實際存儲地址抽象。,什么是存儲結(jié)構(gòu)？,38,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表,頭指針：指向第一個結(jié)點的地址。 尾標(biāo)志：終端結(jié)點的指針域為空。,39,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表,空表和非空表不統(tǒng)一，缺點？ 如何將空表與非空表統(tǒng)一？,40,頭結(jié)點：在單鏈表的第一個元素結(jié)點之前附設(shè)一個類型相同的結(jié)點，以便空表和非空表處理統(tǒng)一。,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表,非空表,41,單鏈表的實現(xiàn)

10、按位查找,操作接口： T GetElem(int i);,核心操作（關(guān)鍵操作）：工作指針后移。從頭結(jié)點（或開始結(jié)點）出發(fā)，通過工作指針的反復(fù)后移而將整個單鏈表“審視”一遍的方法稱為掃描（或遍歷）。,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),first,a1,a2,an,ai,42,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表的實現(xiàn)按位查找,算法描述偽代碼,43,ListNode * LocateElem(LinkList L,int i) p= L next; j = 1; /初始化 p指向第一個結(jié)點 While( p /返回第i個元素指針 ,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表的實現(xiàn)按位查找,

11、算法描述C描述,44,單鏈表的實現(xiàn)插入,操作接口： void InsertList(int i, T x);,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),如何實現(xiàn)結(jié)點ai-1、x和ai之間邏輯關(guān)系的變化？,s=(LinkList)malloc(sizeof(ListNode); s-data=x; s-next=p-next; p-next=s;,算法描述：,45,注意分析邊界情況表頭、表尾。,單鏈表的實現(xiàn)插入,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),first,a1,an,ai,由于單鏈表帶頭結(jié)點，表頭、表中、表尾三種情況的操作語句一致。,s=(LinkList)malloc(sizeof(ListNo

12、de); s-data=x;s-next=p-next; p-next=s;,算法描述：,46,算法描述偽代碼,1. 工作指針p初始化；累加器j清零； 2. 查找第i-1個結(jié)點并使工作指針p指向該結(jié)點； 3. 若查找不成功，說明插入位置不合理，拋出插入位置異常；否則， 3.1 生成一個元素值為x的新結(jié)點s； 3.2 將新結(jié)點s插入到結(jié)點p之后；,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表的實現(xiàn)插入,47,int InsertList (LinkList ,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),算法描述C描述,單鏈表的實現(xiàn)插入,s data = e ; /賦值 s next = p next; /

13、插入新結(jié)點 p next = s; return 1; ,，,基本語句？時間復(fù)雜度？,O(n),48,單鏈表的實現(xiàn)刪除,操作接口:Status ListDelete_L (LinkList e=q-data; p-next=q-next; free(q);,49,單鏈表的實現(xiàn)刪除,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),注意分析邊界情況表頭、表尾。,表尾的特殊情況： 雖然被刪結(jié)點不存在，但其前驅(qū)結(jié)點卻存在。,p-next=NULL,算法描述：,q=p-next; e=q-data; p-next=q-next; free(q);,50,算法描述偽代碼,1.工作指針p初始化；累加器j清零； 2. 查

14、找第i-1個結(jié)點并使工作指針p指向該結(jié)點； 3. 若p不存在或p不存在后繼結(jié)點，則拋出位置異常； 否則， 3.1 暫存被刪結(jié)點和被刪元素值； 3.2 摘鏈，將結(jié)點p的后繼結(jié)點從鏈表上摘下； 3.3 釋放被刪結(jié)點； 3.4 返回被刪元素值；,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表的實現(xiàn)刪除,51,Status ListDelete_L (LinkList ,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),算法描述C描述,單鏈表的實現(xiàn)刪除,if (!(p-next) | | ji-1) return ERROR; else q=p-next; e=q-data; p-next=q-next; free(q

15、); return OK; ,52,單鏈表的實現(xiàn)初始化函數(shù),操作接口：CreateList_L(LinkList a , int n),頭插法：將待插入結(jié)點插在頭結(jié)點的后面 。,算法描述： first=(LinkList) malloc (siezeof(ListNode); first-next=NULL;,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),53,單鏈表的實現(xiàn)構(gòu)造函數(shù),操作接口：CreateList_L(LinkList a , int n),頭插法：將待插入結(jié)點插在頭結(jié)點的后面 。,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),算法描述： s=(LinkList) malloc (siezeof(

16、ListNode); s-data=a0; s-next=first-next; first-next=s;,插入第一個元素結(jié)點,first,54,單鏈表的實現(xiàn)創(chuàng)建函數(shù),操作接口：CreateList(LinkList a , int n),頭插法：將待插入結(jié)點插在頭結(jié)點的后面 。,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),算法描述： s=(ListNode*) malloc (siezeof(ListNode); s-data=a1; s-next=first-next; first-next=s;,依次插入每一個結(jié)點,55,void CreateList(LinkList a , int n)

17、first=(ListNode*) malloc(siezeof(ListNode); first-next=NULL; for (i=0; idata=ai; s-next=first-next; first-next=s; ,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表的實現(xiàn)創(chuàng)建函數(shù),算法描述：,56,尾插法：將待插入結(jié)點插在終端結(jié)點的后面。,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表的實現(xiàn)創(chuàng)建函數(shù),操作接口：CreateList_L(LinkList a , int n),算法描述： first=(LinkList) malloc (siezeof(LNode); rear=first;,

18、57,尾插法：將待插入結(jié)點插在終端結(jié)點的后面。,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表的實現(xiàn)構(gòu)造函數(shù),操作接口：CreateList_L (LinkList a , int n),算法描述： s=(LinkList) malloc (siezeof(LNode); s-data=a0; first-next=s; rear=first;,插入第一個元素結(jié)點,58,尾插法：將待插入結(jié)點插在終端結(jié)點的后面。,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表的實現(xiàn)構(gòu)造函數(shù),操作接口：CreateList_L (LinkList a , int n),算法描述： s=(LinkList)malloc (siezeof(ListNode); s-data=a1; first-next=s; rear=first;,依次插入每一個結(jié)點,35,59,尾插法：將待插入結(jié)點插在終端結(jié)點的后面。,2.3 線性表的鏈接存儲結(jié)構(gòu)及實現(xiàn),單鏈表的實現(xiàn)構(gòu)造函數(shù),操