第3講數(shù)據(jù)結(jié)構(gòu)

1、優(yōu)點(diǎn)：優(yōu)點(diǎn)： （1）無須為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間。 （2）可以方便地隨機(jī)存儲(chǔ)表中的任一結(jié)點(diǎn)。缺點(diǎn)：缺點(diǎn)： （1）插入和刪除平均須移動(dòng)一半結(jié)點(diǎn)。 （2）存儲(chǔ)分配只能預(yù)先進(jìn)行（靜態(tài)） 過大 浪費(fèi) 過小 溢出 -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序表的優(yōu)、缺點(diǎn)順序表的優(yōu)、缺點(diǎn)： -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：（鏈表linked list）&鏈表：鏈表：用一組任意的存儲(chǔ)單元（可以是無序的）存放線性表的數(shù)據(jù)元素。 *無序-可零散地分布在內(nèi)存中的任何位置上。&鏈表的特點(diǎn)：鏈表的特點(diǎn)： 鏈表中結(jié)點(diǎn)的邏輯次序和物

2、理次序不一定相同。即：邏輯上相鄰未必在物理上相鄰。 結(jié)點(diǎn)之間的相對位置由鏈表中的指針域指示，結(jié)點(diǎn)之間的相對位置由鏈表中的指針域指示，而結(jié)點(diǎn)在存儲(chǔ)器中的存儲(chǔ)位置是隨意的。 -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：（鏈表linked list）&結(jié)點(diǎn)的組成：結(jié)點(diǎn)的組成： 數(shù)據(jù)域 指針域 數(shù)據(jù)域數(shù)據(jù)域-表示數(shù)據(jù)元素自身值。 指針域（鏈域）指針域（鏈域）-表示與其它結(jié)點(diǎn)關(guān)系。 通過鏈域，可將n個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起（不論其物理次序如何）。 -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：（鏈表linked

3、 list）&單鏈表：單鏈表：-每個(gè)結(jié)點(diǎn)只有一個(gè)鏈域。開始結(jié)點(diǎn)開始結(jié)點(diǎn)-（無前趨）用頭指針指向之。最后一個(gè)結(jié)點(diǎn)最后一個(gè)結(jié)點(diǎn)(尾結(jié)點(diǎn)尾結(jié)點(diǎn))-指針為空（無后繼），用或null表示。表中其它結(jié)點(diǎn)表中其它結(jié)點(diǎn)-由其前趨的指針域指向之。a1 a2 an Head -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 單鏈表：單鏈表：&空表空表-頭指針為空。頭結(jié)點(diǎn)頭結(jié)點(diǎn)-其指針域 指向表中第一個(gè)結(jié)點(diǎn)的指針。單鏈表的描述單鏈表的描述 單鏈表由頭指針唯一確定單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。 例如：若頭指針為head,則可把鏈表稱為“表head”。a1 a2 an Head

4、Typedef int datatype; typedef structure node /*結(jié)點(diǎn)類型定義*/ datatype data; /*數(shù)據(jù)域*/ struct node *next; JD; /*next為指針域， 指向該結(jié)點(diǎn)的后繼*/ JD *head,*p; /*指針類型說明*/指針p與指向的結(jié)點(diǎn)關(guān)系示意圖Data nextp 結(jié)點(diǎn) (*p) 單鏈表的描述：單鏈表的描述： 指針p與指向的結(jié)點(diǎn)關(guān)系示意圖： p 結(jié)點(diǎn) (*p) 說明：說明： p-指向鏈表中某一結(jié)點(diǎn)的指針。 *p-表示 由指針p所指向的結(jié)點(diǎn)。 (*p).data或或p-data-表示由p所指向結(jié)點(diǎn)的數(shù)據(jù)域。 (*p)

5、.next或或p-next-表示由p所指向結(jié)點(diǎn)的指針域。Data next 單鏈表的描述：單鏈表的描述：P=(JD*)malloc(sizeof(JD)-對指針p賦值使其指向某一結(jié)點(diǎn)（按需生成一個(gè)JD結(jié)點(diǎn)類型的新結(jié)點(diǎn)）。其中： (JD*)-進(jìn)行類型轉(zhuǎn)換。Sizeof(JD)-求結(jié)點(diǎn)需用占用的字節(jié)數(shù)。Malloc(size)-在內(nèi)存中分配size個(gè)連續(xù)可用字節(jié)的空間。Free(p)-系統(tǒng)回收p結(jié)點(diǎn)。（動(dòng)態(tài)） 單鏈表的描述：單鏈表的描述： -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算 （1）建立單鏈表之）建立單鏈表之 -頭插法建表： 思想：思想：從一個(gè)空表開始，重復(fù)

6、讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放在新結(jié)點(diǎn)的數(shù)據(jù)域 中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。 B A C D HeadHead -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) S注：頭插法生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。10JD *CREATELISTF()Char ch; /*逐個(gè)插入字符，以“$“為結(jié)束符，返回單鏈表頭指針*/ JD *head,*s; head=NULL; /*鏈表開始為空*/ ch=getchar(); /*讀入第一個(gè)結(jié)點(diǎn)的值*/ while(ch!=$) s=（JD *）malloc(sizeof(JD); /生成新結(jié)點(diǎn)*/ s-data=

7、ch; s-next=head; head=s; ch=getchar(); return head; /*CREATLISTF*/ 頭插法建表頭插法建表: 算法思想：算法思想：將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，可增加一個(gè)尾指針r，使其始終指向鏈表的尾結(jié)點(diǎn)。 pA D C B -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算 （1）建立單鏈表之）建立單鏈表之 -尾插建表法：head r S 尾插建表可使生成的結(jié)點(diǎn)次序和輸入的順序相同12JD *CREATLISTR()Char ch; /*逐個(gè)插入字符，以“$“為結(jié)束符，返回單鏈表頭指針*/ JD *head,*s,*

8、r; head=NULL; /*鏈表開始為空*/ r=NULL; /*尾指針初值為空*/ ch=getchar(); /*讀入第一個(gè)結(jié)點(diǎn)的值*/ while(ch!=$) /*“$“為輸入結(jié)束符*/ s=（JD *）malloc(sizeof(JD); /生成新結(jié)點(diǎn)*/s-data=ch;if(head=NULL)head=s;else r-next=s;r=sch=getchar();If(r!=NULL) r-next=NULL; return head; /*CREATLISTR*/ 尾插法建表尾插法建表:頭、尾插法建表分析：頭、尾插法建表分析： 上述頭、尾插法建表由于沒有生成（附上述頭

9、、尾插法建表由于沒有生成（附 加）頭結(jié)點(diǎn)，因此開始結(jié)點(diǎn)和其它結(jié)點(diǎn) 的插入處理并不一樣，原因是開始結(jié)點(diǎn) 的位置存放在頭指針中，而其余結(jié)點(diǎn)的 位置是在其前趨結(jié)點(diǎn)的指針域 。 尾插法建表的改進(jìn)算法尾插法建表的改進(jìn)算法 思想：思想： 設(shè)頭結(jié)點(diǎn)，設(shè)頭結(jié)點(diǎn)，使第一個(gè)結(jié)點(diǎn)和其余結(jié)點(diǎn)的插入操作一致。 單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算 -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（表）頭結(jié)點(diǎn)（表）頭結(jié)點(diǎn)（在第一個(gè)結(jié)點(diǎn)之前附設(shè)）-其指針域 存貯指向第一個(gè)結(jié)點(diǎn)的指針（即第一個(gè)結(jié)點(diǎn)的存貯位置）。 頭結(jié)點(diǎn)的數(shù)據(jù)域：頭結(jié)點(diǎn)的數(shù)據(jù)域：可有可無 頭結(jié)點(diǎn)的指針域：頭結(jié)點(diǎn)的指針域：指向第一個(gè)結(jié)點(diǎn)的指針。 -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性

10、表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表的基本運(yùn)算之單鏈表的基本運(yùn)算之-改進(jìn)的尾插法建表算法改進(jìn)的尾插法建表算法 -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)帶頭結(jié)點(diǎn)的單鏈表帶頭結(jié)點(diǎn)的單鏈表 空表空表heada1 an 頭結(jié)點(diǎn)開始結(jié)點(diǎn) 非空表非空表無論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)的非空指針，所以表的第一個(gè)結(jié)點(diǎn)和其它結(jié)點(diǎn)的操作一致。16JD *CREATLISTR1()/*帶頭結(jié)點(diǎn)的尾插法建立單鏈表，返回表頭指針*/Char ch; JD *head,*s,*r; head=malloc(sizeof(JD); /*生成頭結(jié)點(diǎn)*/ r=head; /*尾指針初值指向頭結(jié)點(diǎn)*/ ch=getchar(); wh

11、ile(ch!=$) /*“$“為輸入結(jié)束符*/ s=（JD *）malloc(sizeof(JD); /生成新結(jié)點(diǎn)*/s-data=ch;r-next=s;/*新結(jié)點(diǎn)插入表尾*/r-next=s;r=s;/*尾指針r指向新的表尾*/ch=getchar();/*讀下一結(jié)點(diǎn)*/r-next=NULL; return head; /*CREATLISTR1*/改進(jìn)的改進(jìn)的 尾插建表算法尾插建表算法:按序號(hào)查找按序號(hào)查找 設(shè)單鏈表的長度為n，要查找表中第I個(gè)結(jié)點(diǎn)，算法思想如下：算法思想如下： 從頭結(jié)點(diǎn)開始順鏈掃描，用指針p指向當(dāng)前掃描到的結(jié)點(diǎn)，用j作統(tǒng)計(jì)已掃描結(jié)點(diǎn)數(shù)的計(jì)數(shù)器，當(dāng)p掃描下一個(gè)結(jié)點(diǎn)時(shí)，

12、j自動(dòng)加1。 P的初值指向頭結(jié)點(diǎn)，j的初值為0。 當(dāng)j=I時(shí)，指針p所指的結(jié)點(diǎn)就是第I個(gè)結(jié)點(diǎn)。 算法描述（略）算法描述（略） 單鏈表的基本運(yùn)算之單鏈表的基本運(yùn)算之 （2）查找運(yùn)算）查找運(yùn)算 -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)按按值查找：按按值查找： 在鏈表中，查找是否有結(jié)點(diǎn)等于給定值key的結(jié)點(diǎn)，若有的話，則返回首次找到的值勤為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回null. 算法思想：算法思想： 從開始結(jié)點(diǎn)出發(fā)，順鏈逐個(gè)結(jié)點(diǎn)的值和給予定值key作比較。 算法描述（略）算法描述（略） 單鏈表的基本運(yùn)算之單鏈表的基本運(yùn)算之（2）查找運(yùn)算）查找運(yùn)算 -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 設(shè)

13、指針p指向單鏈表的某一結(jié)點(diǎn)，指針s指向等到插入的、其值為x的新結(jié)點(diǎn)。實(shí)現(xiàn)方法（兩種）：實(shí)現(xiàn)方法（兩種）： 后插后插-將新結(jié)點(diǎn)*s插入結(jié)點(diǎn)*p之后。 前插前插-將新結(jié)點(diǎn)*s插入結(jié)點(diǎn)*p之前。 單鏈表的基本運(yùn)算之單鏈表的基本運(yùn)算之（3）插入運(yùn)算）插入運(yùn)算 -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 算法思想：算法思想：取一新結(jié)點(diǎn)，將其數(shù)據(jù)域置為新結(jié)點(diǎn)，再修改有關(guān)結(jié)點(diǎn)的鏈域： 把原p結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)作為s結(jié)點(diǎn)的直接后繼，s結(jié)點(diǎn)作為p結(jié)點(diǎn)的直接后繼。 X -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算（3）插入運(yùn)算之）插入運(yùn)算之 后插操作后插操作 S P21INSERT

14、AFTER（P，X）/*將值為X的新結(jié)點(diǎn)插入*P之后*/JD *p;datatype x; s=（JD *）malloc(sizeof(JD); /生成新結(jié)點(diǎn)*/s-data=x;s-next=p-next;p-next=s;/*將*s插入*p之后*/ /*INSERTAFTER */ -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算（3）插入運(yùn)算之）插入運(yùn)算之 后插算法：后插算法：后插算法的時(shí)間復(fù)雜度：O（1） 先找到p結(jié)點(diǎn)的前趨結(jié)點(diǎn)（單鏈表無前趨指針），然后修改其鏈域，使其指向待插入的s結(jié)點(diǎn)，而將s結(jié)點(diǎn)指向p結(jié)點(diǎn)。 X -線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 單鏈表的基本運(yùn)算單鏈表的基本運(yùn)算 （3）插入運(yùn)算之）插入運(yùn)算之前插操作：前插操作： S q p 23INSERTBEFORE（head,p,x）/*在帶頭結(jié)點(diǎn)的單鏈表head中,將值為X的新結(jié)點(diǎn)插入*P之前*/JD *head,*p;datatype x;JD *q;s=（JD *）malloc(sizeof(JD); /生成新結(jié)點(diǎn)*/s-data=x;q=head; /*從頭指針開始*/While(q-next!=p) q=q-next; /坦*p的前趨結(jié)點(diǎn)*/s-next=p；q-next=s; /*將*s插入*p之 前*/ /*INSERTBEFORE */ -線性表的鏈?zhǔn)酱?/p>