線性邏輯結構

1、2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作1第第2章章 線線 性性 表表q2.1 線性表的邏輯結構q2.2 線性表的順序存儲結構q2.3 線性表的鏈式存儲結構q2.4 順序表和鏈表的比較q2.5 習題2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作22.1 線性表的邏輯結構o 1線性表的定義q線性表是n(n0)個結點組成的有限序列。從這個定義中應當理解到以下幾點：q線性表中的元素是有順序的；q線性表中的元素個數(shù)可以為0，即可以是空的線性表；q線性表中的元素可以是多個，但不能是無窮多個；q同一個線性

2、表中元素的類型相同，因此元素長度也相同。2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作3o 2線性表的特點q 任意一個非空的線性表都具有以下特點：q 只有一個排在第一個的元素，稱為線性表的起始元素。q 只有一個排在最后的元素，稱為線性表的終端元素。q 除起始元素外，線性表中的其他元素僅有一個直接前驅元素；除終端元素外，線性表中的其他元素僅有一個直接后繼元素。o 3線性表的邏輯表示形式q 線性表的邏輯表示形式如下:q l1=( )：l1是一個空的線性表；q l2=(a,b,c,d,e)：l2線性表中有5個元素，a是起始元素、e是終端元素，c的直接前

3、驅元素是b，c的直接后繼元素是d。a元素的序號是1，c元素的序號是3。2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作4w 4線性表的基本運算q initlist(l)：初始化運算，其功能是創(chuàng)建了一個空的線性表l。q listlength(l)：求線性表l的長度運算。q getnode(l,i)：讀元素運算，函數(shù)值是線性表l的第i個元素。q locatenode(l,x)：定位運算，是線性表l中x元素的位置。q insertlist(l,x,i)：插入運算，其功能是將x插入線性表l中，作為線性表l的第i個元素。q deletelist(l,i)：刪

4、除運算，將線性表l的第i個元素刪除。q clear(l)：清除表元素運算，其功能是刪除 l表中的元素，使線性表l成為空表。q empty(l)：判斷l(xiāng)表是否是空表，其功能是l表為空時函數(shù)值為1，否則為0。2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作52.2 線性表的順序存儲結構o 2.2.1 線性表順序存儲結構的概念q 順序表:q 將線性表的結點按邏輯次序依次存放在一組地址連續(xù)的存儲單元內，采用這種方法存儲的線性表簡稱為順序表。 順序表的虛擬存儲是采用程序設計語言的一維數(shù)組來存儲線性表。 順序表是存儲在一段連續(xù)的空間內，邏輯上相鄰的元素在存儲位

5、置上也相鄰。 q 提示：用loc(ai)表示線性表元素ai的存儲空間的起始地址，若l表示一個元素的長度，則對于正整數(shù)i有：loc(ai+1)= loc(ai)+ l若線性表的起始地址是b，則：loc(ai)=b+(i-1)*l 或者 loc(ai)= loc(a1)+(i-1)*l2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作62007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作72007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作81順序表的類型定義struct

6、 sqlist datetype elemmaxlen; int length;其中datetype表示線性表元素的抽象數(shù)據(jù)類型，用程序設計語言上機實現(xiàn)算法時，再定義為具體的數(shù)據(jù)類型。maxlen表示線性表最多允許的元素個數(shù)。length表示線性表的當前長度。其值是0至maxlen間的一個整數(shù)。2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作92. 運算的算法插入運算的算法(算法2.1) insert_sqlist(struct qlist l, datetype x, int i) if(il.length+1) error(illegal va

7、lue of i); /*插入位置i不正確*/ else if(l.length = maxlen) error(list overflow) ; /*表滿*/ else /*將線性表的最后一個元素至第i個元素均向后移一個位置*/ for(k=l.length-1; k=i-1; k-) l.elemk+1= l.elemk; l.elemi-1=x ; /*將x插入線性表的第i個位置*/ l.length+ ; /*線性表長度加1*/ 插入算法的時間復雜度為o(n)。 2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作102. 運算的算法刪除運算的

8、算法(算法2.2)elemtype delete_sqlist(struct sqlist l, int i) if(il.length) error(illegal value of i); /*刪除元素的序號i不 正確*/ else if(l.length = 0) error(list empty); /*表空*/ else x=l.elemi-1; /*將線性表的第i+1個元素至最后一個元素均向前移一個位置*/ for(k=i;knext=null; /* l指向的結點作為鏈表的表頭結點，空鏈表表頭結點的指針域為空 */2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，

9、歡迎收藏電子信息系黃力明制作14q 求表長運算的算法(算法2.4)int listlength(list l) p=l ; /* p是指針類型變量，開始時p指向表頭結點*/ j=0; /* j是整型變量，用它記錄著結點的個數(shù)*/ while(p-next!=null) p=p-next ; /* 讓指針變量p指向鏈表的下一個結點*/ j+; /* j記錄的個數(shù)加1*/ return(j); /* j的最后的值是鏈表的長度*/2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作15q 讀元素運算的算法(算法2.5)pointer getnode(list

10、 l, int i) p=l;j=0;while(p-next!=null)&(jnext; j+;if(i=j) return(p); /* 找到了第i個結點，返回p指針*/else return(null); /* 返回空指針*/2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作16q 插入運算的算法(算法2.6)void insertlist(list l, datatype x, int i) p=l;j=0;while(p!=null)&(jnext;j+; /* 使指針p指向第i-1個結點*/if(p=null) prin

11、tf(第i-1個結點不存在); /* i值不正確*/else s=(struct node *)malloc(sizeof(struct node);/* 申請一個結點s */ s-data=x; /* 將x送入新結點 */ s-next=p-next; /* 使新結點指向鏈表的原第i個結點 */ p-next=s; /* 使鏈表的原第i-1個結點指向新結點 */2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作17q 刪除運算的算法(算法2.7)datatype deletelist(list l, int i)p=l;j=0;while(p!=n

12、ull)&(jnext;j+; /* 使指針p指向第i-1個結點*/if(!p & p-next!=null) printf(第i-1個結點不存在); /* i值不正確*/else q=p-next; /*使指針q指向第i個結點 */ p-next=q-next; /*使鏈表的原第i-1個結點指向第i+1個結點*/ x=q-next; /*使刪除結點的值賦給x */ free(q); /*釋放被刪除結點的空間 */ return(x); /*返回被刪除結點的值 */2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作18q2.3.2 循

13、環(huán)鏈表q提示：單鏈表的尾結點的指針域(next)是空指針，如果將該指針域改為指向表頭結點的指針，則該鏈表就是循環(huán)鏈表。q提示：循環(huán)鏈表的算法與單鏈表的算法基本相同，只是單鏈表l是空鏈表的條件是:ql-next=null，而循環(huán)鏈表l是空鏈表的條件是l-next=l。圖2.4 循環(huán)鏈表2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作19w 2.3.3 雙向鏈表o 提示：如果將循環(huán)鏈表的每個結點都設置指向前驅和指向后繼的指針，則該鏈表就是雙向循環(huán)鏈表。o 1雙向鏈表結點的數(shù)據(jù)結構o typedef struct dulnode *pointer;o t

14、ypedef struct dulnodeo o datatype data;o pointer prior,next;o dulnode;2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作20圖2.5 雙向鏈表2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作212雙向鏈表運算的算法雙向鏈表刪除的算法(算法2.8)datatype deletelist_dul(dulnode *l,dulnode *p)/*刪除雙向鏈表l中p指針所指的元素，并將被刪除的結點的值作為函數(shù)值返回*/ x=p-data; /*

15、 使刪除結點的值賦給x */ p-prior-next=p-next; /* 使p結點的前驅結點的后繼指針指向p結點的后繼結點*/ p-next-prior=p-prior; /* 使p結點的后繼結點的向前指針指向p結點的前驅結點*/ free(p); /* 釋放p所指被刪除的結點 */ return (x); /* 返回被刪除結點的值 */2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作22在雙向鏈表l中插入元素的算法(算法2.9)inserterlist_dul(dulnode *l,dulnode *p, datatype e) /*將e元素

16、插入到雙向鏈表l中p指針所指的元素的前邊*/s=(struct dulnode *)malloc(sizeof(struct dulnode); /* 申請一個結點，讓指針s指向它*/s-data=x; /* 將x送入新結點*/ s-next=p; /* 使新結點的后繼指針指向p結點*/s-prior=p-prior; /* 使新結點的前驅指針指向p結點的前驅結點*/p-prior-next=s; /* 使p結點的前驅結點的后繼指針指向新結點*/p-prior=s; /* 使p結點的前驅指針指向新結點*/ 2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力

17、明制作232.5 習 題一、填空題(1) 鏈表中邏輯上相鄰的元素的物理位置_相連。(2) 在單鏈表中除首結點外，任意結點的存儲位置都由_結點中的指針指示。(3) 在單鏈表中，設置頭結點的作用是在插入或刪除首結點時不必對_進行處理。(4) 已帶表頭結點的單鏈表l，指針p指向l鏈表中的一個結點，指針q是指向l鏈表外的一個結點，則： 在指針p所指結點后插入q所指結點的語句序列是_； 在指針p所指結點前插入q所指結點的語句序列是_； 將q所指結點插入在鏈表首結點的語句序列是_； 將q所指結點插入在鏈表尾結點的語句序列是_。2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信

18、息系黃力明制作24(5) 已知帶表頭結點的單鏈表l，指針p指向l鏈表中的一個結點(非首結點非尾結點)，則： 刪除指針p所指結點的直接后繼結點的語句是_； 刪除指針p所指結點的直接前驅結點的語句序列是_； 刪除指針p所指結點的語句序列是_； 刪除首結點的語句序列是_； 刪除尾結點的語句序列是_。(6) 已知指針p指向雙向鏈表中的一個結點(非首結點，非尾結點)，則： 將結點s插入在指針p所指結點的直接后繼位置的語句是_； 將結點s插入在指針p所指結點的直接前驅位置的語句是_； 刪除指針p所指結點的直接后繼結點的語句序列是_； 刪除指針p所指結點的直接前驅結點的語句序列是_； 刪除指針p所指結點的語

19、句序列是_。2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作25(7) 線性表的存儲結構有順序存儲和_存儲兩種。(8) 線性表的元素長度為4，在順序存儲結構下loc(ai)=2000，則loc(ai+1)= _。(9) 線性表a的元素長度為l，在順序存儲結構下loc(ai)=loc(a1)+_。(10) 在線性表的鏈式存儲結構中，某結點的指針字段指向該結點的_兩種存儲。(11) 線性表的元素長度為4，loc(a1)=1000，則loc(a3)= _。(12) 在下圖所示的鏈表中，若在指針p所指的結點之后插入數(shù)據(jù)字段相繼為a和b的兩個結點，則可用下列

20、兩個語句實現(xiàn)該操作，它們依次是_和_。2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作262007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作27二、選擇題2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作282007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作292007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作302007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分

21、享，歡迎收藏電子信息系黃力明制作312007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作322007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作33三、簡答題（1）在什么情況下使用順序表比鏈表好？（2）已知帶表頭的單鏈表l，簡述下列對l鏈表操作算法的功能。 status a(l)if(l-next & l-next-next) q=l-next;l=q-next;p=q; while(p-next) p=p-next;p-next=q; q-next=null;return ok;2007年8月12日星期日行業(yè)報告 多媒體課件 豆丁網(wǎng)友友情分享，歡迎收藏電子信息系黃力明制作34(3) 已知帶表頭的循環(huán)鏈表l，簡述下列對l鏈表操作算法的功能。void