數(shù)據(jù)結(jié)構(gòu)之鏈表課件

SCIE,UniversityofElectronicScienceandTechnologyofChina12.1線性表線性表不同的實(shí)現(xiàn)方式：2.1.1順序表數(shù)組存儲(chǔ)順序表定義順序表基本操作：

遍歷、插入、刪除

順序表算法分析2.1.2單鏈表2.1.3雙向鏈表鏈接存儲(chǔ)2.1.4循環(huán)鏈表SCIE,UniversityofElectronicScienceandTechnologyofChina22.1線性表#include"stdio.h“structlist_seq{intdata[20];intlength;};intmain(){structlist_seqlist;intno,i;

list.length=0;for(i=0;i<10;i++){scanf("%d",&no);if(no==0)break;list.data[i]=no;list.length++;}no=30;insert(list,no,5);delete(list,8)return0;}SCIE,UniversityofElectronicScienceandTechnologyofChina32.1.2單鏈表一、鏈表的引入數(shù)組結(jié)構(gòu)的缺點(diǎn):1、在插入、刪除時(shí)要移動(dòng)大量的節(jié)點(diǎn)2、表的大小固定。 預(yù)先在申明數(shù)組時(shí)指定，無法更改原因：存放的連續(xù)性突破離散存放用指針來表示元素之間的關(guān)系。SCIE,UniversityofElectronicScienceandTechnologyofChina42.1.2單鏈表用鏈表實(shí)現(xiàn)線性表（非連續(xù)存儲(chǔ)）線性表元素：a1、a2、a3、a4....鏈表鏈點(diǎn)線性關(guān)系：a1a2a3a4指針域，指針關(guān)系a1a2a3a4a1a2a3a4順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)SCIE,UniversityofElectronicScienceandTechnologyofChina52.1.2單鏈表二、

鏈表的定義

鏈點(diǎn)datalink元素域鏈接域數(shù)據(jù)域（數(shù)據(jù)元素域）：存放一個(gè)數(shù)據(jù)元素。鏈接域（關(guān)系域）：存放指向下一個(gè)元素的指針

——元素間的關(guān)系。數(shù)據(jù)域+鏈接域=結(jié)點(diǎn)（鏈點(diǎn)）SCIE,UniversityofElectronicScienceandTechnologyofChina62.1.2單鏈表鏈表a1a2an……由鏈點(diǎn)及鏈點(diǎn)相互間的鏈接構(gòu)成head鏈表頭鏈表尾鏈表長度（節(jié)點(diǎn)數(shù)目）taillength^SCIE,UniversityofElectronicScienceandTechnologyofChina72.1.2單鏈表定義structnode_type{ elemtypedata; structnode_type*next;};structlist_type{ node_type*head; node_type*tail; intlength;};鏈點(diǎn)的定義鏈表的定義datanext82.1.2單鏈表SCIE,UniversityofElectronicScienceandTechnologyofChina8帶頭節(jié)點(diǎn)的單鏈表a1an……h(huán)ead^帶頭節(jié)點(diǎn)鏈表的引入是為了使算法對(duì)空表和非空表的處理一致普通單鏈表對(duì)鏈表尾的判斷(假定p是鏈表尾的指針)空表：p==null;非空表：p->next==null;帶頭節(jié)點(diǎn)單鏈表對(duì)鏈表尾的判斷空表：p->next==null;非空表：p->next==null;SCIE,UniversityofElectronicScienceandTechnologyofChina92.1.2單鏈表初始化算法：elemtypeinitlist(node**h){ *h=(node*)malloc(sizeof(node)); (*h)->next=null;}三、鏈表的基本操作訪問插入刪除SCIE,UniversityofElectronicScienceandTechnologyofChina102.1.2單鏈表訪問操作問題描述：訪問鏈表的第i個(gè)節(jié)點(diǎn)問題分析：輸入：鏈表，i輸出：鏈點(diǎn)——指向鏈點(diǎn)的指針?biāo)惴▽?shí)現(xiàn)分析：只能從鏈表頭開始，一個(gè)一個(gè)“數(shù)”下去，直到第i個(gè)。a1an……h(huán)eadtaila2temptemptempSCIE,UniversityofElectronicScienceandTechnologyofChina112.1.2單鏈表從自然語言到算法語言如何描述我們找到第i個(gè)節(jié)點(diǎn)的動(dòng)作。1、先找到鏈表首結(jié)點(diǎn)的地址2、通過“地址”，找到鏈點(diǎn)3、在鏈點(diǎn)中找到后繼元素的“地址”4、記錄這個(gè)地址p=list->head;while(){}p->data……p=p->next;p->next……SCIE,UniversityofElectronicScienceandTechnologyofChina122.1.2單鏈表繼續(xù)完善描述1、先找到鏈表首結(jié)點(diǎn)的地址2、通過“地址”，找到鏈點(diǎn)3、在鏈點(diǎn)中找到后繼元素的“地址”4、記錄這個(gè)地址，回到2p=list->head;while(1){}p->data……p=p->next;p->next……,計(jì)數(shù)，如果計(jì)數(shù)到i，就結(jié)束counter=1;counter++;if(counter==i)break;SCIE,UniversityofElectronicScienceandTechnologyofChina132.1.2單鏈表node_type*get_node(list,i){}while(counter<i&&p!=NULL){ counter=counter+1; p=p->next;}intcounter;node_type*p;returnp;if(p==NULL)returnNULL;p=list->head;counter=1;a1nextaiai+1anpa2逐個(gè)“數(shù)”的動(dòng)作counter：123設(shè)i＝3當(dāng)i>n時(shí)算法結(jié)果怎樣？思考SCIE,UniversityofElectronicScienceandTechnologyofChina142.1.2單鏈表注意1、p=p->next;沿鏈表前進(jìn)2、循環(huán)結(jié)束條件counter==i或node==NULLcounter>list->length思考如果希望獲得值為x的元素，如何實(shí)現(xiàn)？while(p->data==x&&p!=NULL)SCIE,UniversityofElectronicScienceandTechnologyofChina152.1.2單鏈表鏈表插入操作問題描述：在元素ai前插入新的元素new_node;問題分析：輸入：鏈表，location，x輸出：插入新元素后的鏈表。算法實(shí)現(xiàn)分析SCIE,UniversityofElectronicScienceandTechnologyofChina162.1.2單鏈表a1aianheadtailai-1......anewa1aianheadtailai-1......anew兩個(gè)步驟：

ai-1->next=anew;anew->next=ai;SCIE,UniversityofElectronicScienceandTechnologyofChina172.1.2單鏈表voidinsertl（list,new_node,location）｛｝找到ai-1執(zhí)行插入動(dòng)作兩個(gè)步驟：ai-1->next=anew;anew->next=ai;SCIE,UniversityofElectronicScienceandTechnologyofChina182.1.2單鏈表while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}voidinsertl（list,new_node,location）｛｝找到ai-1p->next=new_node;new_node->next=???ai-1->next=anew;anew->next=ai;a1ai-1aianpnewnodea2p＝list->header;counter=1qq=p->next;q;法一SCIE,UniversityofElectronicScienceandTechnologyofChina192.1.2單鏈表while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}voidinsertl（list,new_node,location）｛｝new_node->next=p->next;p->next=new_node;a1ai-1aianpnewnodea2p＝list->header;counter=1法二SCIE,UniversityofElectronicScienceandTechnologyofChina202.1.2單鏈表voidinsertl（list,new_node,location）｛｝while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}new_node->next=p->next;p->next=new_node;counter=1;p=list->head;初始化list->length++;邊界情況：

表首插入 表尾插入SCIE,UniversityofElectronicScienceandTechnologyofChina212.1.2單鏈表a1ai-1aianlist->headnewnodenew_node->next=a1;list->head;list->head=new_node;SCIE,UniversityofElectronicScienceandTechnologyofChina222.1.2單鏈表voidinsertl（list,new_node,location）｛｝while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}new_node->next=p->next;p->next=new_node;counter=1;p=list->head;初始化if(location==1){}else{}new_node=list->head;list->head=new_node;list->length++;邊界情況：

表首插入 表尾插入SCIE,UniversityofElectronicScienceandTechnologyofChina232.1.2單鏈表a1ai-1aianlist->head注意當(dāng)循環(huán)執(zhí)行到表尾時(shí)p的值為NULL（空）p->next是懸空的值while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}new_node->next=p->next;p->next=new_node;p->next!=NULL){NULLp因此循環(huán)結(jié)束應(yīng)以p->next==NULL為條件當(dāng)i>鏈表長度時(shí)會(huì)造成系統(tǒng)崩潰表尾插入SCIE,UniversityofElectronicScienceandTechnologyofChina242.1.2單鏈表voidinsertl（list,new_node,location）｛｝while(counter<i-1&&p->next!=NULL){ counter=counter+1; p=p->next;}new_node->next=p->next;p->next=new_node;counter=1;p=list->head;if(location=

=1){}else{}new_node->next=list->head;list->head=new_node;list->length++;SCIE,UniversityofElectronicScienceandTechnologyofChina252.1.2單鏈表從插入算法中對(duì)鏈表操作的體會(huì)1、鏈表操作往往從表頭開始，逐個(gè)找到需要的鏈點(diǎn)2、鏈表操作的有向性不能回退；3、鏈表指針小心使用，謹(jǐn)防丟失。4、不能訪問空指針的成員5、插入過程沒有進(jìn)行鏈點(diǎn)內(nèi)容進(jìn)行搬移。SCIE,UniversityofElectronicScienceandTechnologyofChina262.1.2單鏈表鏈表的創(chuàng)建參見教材P15問題描述：根據(jù)輸入的元素，生成一個(gè)鏈點(diǎn)，把它插入到鏈表頭；逐個(gè)插入鏈點(diǎn)，形成鏈表鏈表的刪除操作問題描述：刪除元素ai;問題分析：輸入：鏈表，location輸出：刪除元素后的鏈表。算法實(shí)現(xiàn)分析SCIE,UniversityofElectronicScienceandTechnologyofChina272.1.2單鏈表a1ai+1anheadtailai-1......aiai-1->next

=ai->next;即ai-1->next=

ai-1->next->next;SCIE,UniversityofElectronicScienceandTechnologyofChina282.1.2單鏈表｝找到ai-1執(zhí)行刪除動(dòng)作ai-1->next=

ai-1->next->nextvoiddeletel（list,location）｛注意，從鏈表上取下的鏈點(diǎn)ai-1需要掛在一個(gè)指針上，否則可能丟失a1ai+1anheadtailai-1......aitempSCIE,UniversityofElectronicScienceandTechnologyofChina292.1.2單鏈表voiddeletel（list,location）｛｝while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}p->next=p->next->next;counter=1;p=list->head;初始化if(location==1){}else{}list->head=list->head->next;temp=p->next;free(temp);temp=list->head;free(temp);list->length--;從鏈表刪除的鏈點(diǎn)，一般應(yīng)該釋放其空間SCIE,UniversityofElectronicScienceandTechnologyofChina302.1.2單鏈表注意:對(duì)被刪除刪除鏈點(diǎn)的處理往往需要要free（）SCIE,UniversityofElectronicScienceandTechnologyofChina312.1.2單鏈表四、鏈表的特點(diǎn)１、操作的順序性有平均Ｎ／２次查找過程。２、離散存放不受鏈表大小限制不進(jìn)行鏈點(diǎn)內(nèi)容的搬移查找操作：數(shù)組效率優(yōu)于鏈表插入、刪除操作：鏈表效率優(yōu)于數(shù)組

SCIE,UniversityofElectronicScienceandTechnologyofChina322.1.2單鏈表作業(yè)教材74頁第9題（用鏈表實(shí)現(xiàn)）、第10題SCIE,UniversityofElectronicScienceandTechnologyofChina332.1.3雙向鏈表特點(diǎn)：每一個(gè)鏈點(diǎn)包含兩個(gè)指針，前趨指針后繼指針a1……h(huán)eadtailNa2NPanPa1NPP：priorN：nextSCIE,UniversityofElectronicScienceandTechnologyofChina342.1.3雙向鏈表一、雙向鏈表的定義structdouble_link_node_type{ structdouble_link_node_type*prior; structdouble_link_node_type*next; elemtypedata;};structdouble_link_list_type{ dl_node_type*head; dl_node_type*tail; intlength;};鏈點(diǎn)的定義鏈表的定義SCIE,UniversityofElectronicScienceandTechnologyofChina352.1.3雙向鏈表二、雙向鏈表的插入操作ai-1ai問題描述：在第i個(gè)元素前插入新元素anewp2、anew->next=p;1、p->prior->next=anew;3、anew->prior=p->prior;4、p->prior=anew;