軟件技術基礎

軟件技術基礎線性結構——鏈表制作主講xxx鏈接存儲的線性表1.2、鏈接存儲的線性表（鏈表）的定義1.2.1、鏈表的引入數(shù)組結構的缺點:1、在插入、刪除時要移動大量的節(jié)點2、表的大小固定。 預先在申明數(shù)組時指定，無法更改原因：都可歸因到：存放的連續(xù)性突破離散存放用指針來表示元素之間的關系。鏈接存儲的線性表用鏈表實現(xiàn)線性表（非連續(xù)存儲）線性表元素：a1、a2、a3、a4....鏈表鏈點線性關系：a1a2a3a4指針域，指針關系鏈表的定義1.2.2鏈表的定義鏈點datalink元素域鏈接域元素域（數(shù)據(jù)元素域）：存放一個數(shù)據(jù)元素。鏈接域（關系域）：存放指向下一個元素的指針

——表示/記錄元素間的關系。元素域+鏈接域=結點（鏈點）鏈表的要素鏈表a1a2an……由鏈點及鏈點相互間的鏈接構成head鏈表頭——head鏈表尾——tail鏈表長度（結點數(shù)目）——lengthtaillength算法動手做請準備6張小紙片在紙片的中間畫兩個格子。在最左邊格子外面按序寫上不同的號碼，代表每個鏈點的地址。寫完地址后，像洗撲克牌那樣將小紙片交換位置。在紙片中間一格填寫“ax”表示元素值（目的是使x的大小關系盡量不要和地址大小關系一致）做好卡片后，同組的同學交換卡片，完成后面的內容最右邊一格代表每個鏈點的指針變量，在里面填寫后繼元素的“地址”。請將其中的5張卡片按照地址大小排成一列，然后再按元素線性關系填寫“地址欄”形成一個鏈表。做好后，從鏈表首開始逐個尋找鏈點，體會鏈表的結構50a270a1鏈表的定義定義typedefstructnode_type{ elemtypedata; structnode_type*next;}node_type;typedefstructlist_type{ node_type*head; node_type*tail;//很少用 intlength;}list_type;鏈點的定義鏈表的定義datanext元素值的類型，如：int整型char字符型long長整型struct復合型……鏈表的定義鏈表組織：list_type*list;list->head=&a1;a1->next=&a2;a2->next=&a3;……an->next=NULL；list->tail=&an;list->length=n;a1a2an……h(huán)eadtailNULL，表示指針的值為“空”，即指針指向空處鏈表的基本操作1.2.3鏈表的基本操作訪問插入刪除鏈表的基本操作訪問操作問題描述：訪問鏈表的第i個節(jié)點問題分析：輸入：鏈表，i輸出：鏈點——指向鏈點的指針算法實現(xiàn)分析：a1a2an……h(huán)eadtail只能從鏈表頭開始，一個一個“數(shù)”下去，直到第i個。temptemptemp算法動手做回到小紙片中，如何描述我們找到第i個節(jié)點的動作。1、先得到鏈表首結點（的地址）2、通過“地址”，找到鏈點3、在鏈點中找到后繼元素的“地址”4、記錄這個地址，回到2505561667061667050NULLhead=55;a1a2從自然語言到算法語言如何描述我們在鏈表上“逐個去找”的動作？1、先找到鏈表首結點的地址2、通過“地址”，找到鏈點3、在鏈點中找到后繼元素的“地址”4、記錄這個地址，回到2p=list->head;while(){}p->data……p=p->next;p->next……繼續(xù)完善描述我們需要的是找到第i個節(jié)點1、先找到鏈表首結點的地址2、通過“地址”，找到鏈點3、在鏈點中找到后繼元素的“地址”4、記錄這個地址，回到2p=list->head;while(){}p->data……p=p->next;p->next……counter=1;counter++;if(counter==i)break;p=list->head;while(){}p=p->next;counter=1;counter++;if(counter==i)break;計數(shù)，如果計數(shù)到i，就結束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逐個“數(shù)”的動作counter：123設i＝3當i>n時算法結果怎樣？思考訪問操作注意1、p=p->next;沿鏈表前進2、循環(huán)結束條件counter==i或node==NULLcounter>list->length思考如果希望獲得值為x的元素，如何實現(xiàn)？while(p->data==x&&p!=NULL)插入操作鏈表插入操作問題描述：在元素ai前插入新的元素new_node;問題分析：輸入：鏈表，location，x輸出：插入新元素后的鏈表。算法實現(xiàn)分析算法動手做又回到小紙片，如果要向第4個節(jié)點前放入一個新的鏈點。如何描述這個過程。50leng55duan61yang66mao70liu61667050NULL44anewNULLhead=55p

=插入操作a1aianheadtailai-1......anewa1aianheadtailai-1......anew兩個步驟：

ai-1->next=anew;anew->next=ai;插入操作voidinsertl（list,new_node,location）｛｝找到ai-1執(zhí)行插入動作兩個步驟：ai-1->next=anew;anew->next=ai;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;法一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法二插入操作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++;邊界情況： 表首插入 表尾插入插入操作a1ai-1aianlist->headnewnodenew_node->next=list->head;list->head=new_node;a1;插入操作表首插入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->next=list->head;list->head=new_node;list->length++;邊界情況：

表首插入 表尾插入思考，教材算法中輸入參數(shù)的**，與本算法的異同，相應的原因插入操作表尾插入a1ai-1aianlist->head注意當循環(huán)執(zhí)行到表尾時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)結束應以p->next==NULL為條件當i>鏈表長度時會造成系統(tǒng)崩潰插入操作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++;從插入算法中對鏈表操作的體會1、鏈表操作往往從表頭開始，逐個找到需要的鏈點2、鏈表操作的有向性不能回退；3、鏈表指針小心使用，謹防丟失。4、不能訪問空指針的成員5、插入過程沒有對鏈點內容進行搬移。鏈表的創(chuàng)建從鏈點的生成過程中體會動態(tài)內存申請的動作create_list(list,x){while(){

new_node->data=x; new_node->next=NULL; new_node->next=list_head; list->head=new_node;}}問題描述：根據(jù)輸入的元素，生成一個鏈點，把它插入到鏈表頭；逐個插入鏈點，形成鏈表new_node=malloc(sizeof(node_type));scanf(“%d”,&x);為什么要為鏈點申請動態(tài)內存？不能是局部變量不能是全局變量不能是靜態(tài)變量刪除操作鏈表的刪除操作問題描述：刪除元素ai;問題分析：輸入：鏈表，location輸出：刪除元素后的鏈表。算法實現(xiàn)分析a1ai+1anheadtailai-1......aiai-1->next

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

ai-1->next->next;刪除操作｝找到ai-1執(zhí)行刪除動作ai-1->next=

ai-1->next->nextvoiddeletel（list,location）｛注意，從鏈表上取下的鏈點ai-1需要用一個臨時指針記錄下來，否則可能丟失a1ai+1anheadtailai-1......aitemp刪除操作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--;從鏈表刪除的鏈點，一般應該釋放其空間刪除操作注意:對被刪除刪除鏈點的處理往往需要釋放其動態(tài)申請的空間free（）思考如果希望刪除值為x的元素，如何實現(xiàn)？while(p->data==x&&p!=NULL)可以嗎？while(p->next->data==x&&p->next!=NULL)可以嗎？1.2.4鏈表的特點１、操作的順序性有平均Ｎ／２次查找過程。２、離散存放不受鏈表大小限制不進行鏈點內容的搬移查找操作：數(shù)組效率優(yōu)于鏈表插入、刪除操作：鏈表效率優(yōu)于數(shù)組鏈表的特點

上機練習題例１、讀入一組數(shù)建立鏈表，以負數(shù)作為輸入結束算法實現(xiàn)分析輸入：空鏈表元素值從鍵盤輸入。（從文件讀入？）輸出：創(chuàng)建好的鏈表例１、讀入一組數(shù)建立鏈表，以負數(shù)作為輸入結束算法實現(xiàn)分析：（１）如何讀入一組數(shù)并以負數(shù)為結束

建立框架：上機練習指導main(){ x＝0;初始化

while(x>=0){ read(&x)； 插入鏈表； }}read(int*x){ scanf(“data%d:“，x);}上機練習題（２）如何建立鏈表——新的元素以怎樣的方式插入鏈表？每次插在表頭或者每次插在表尾？決定每次插在表尾！new_node->next=list.tail->next;list.tail->next=new_node;（3）邊界問題：第一個節(jié)點插入時list.header=new_node;list.tail=new_node;上機練習指導list_type*create_list(){}初始化；while(x>=0){}read(&x);生成新元素插入新元素returnlist;上機練習指導list_type*create_list(){list_type*list;list->length=0;list->header=NULL;list->tail=NULL;node_type*new_node;intx;list=malloc(sizeof(list_type));while(x>=0){new_node=(node_type*)malloc(size_of(structnode_type));new_node->data=x;假設elemtype就是整數(shù)類型new_node->next=NULL;生成新鏈點if(list.length<=0){ list.header=new_node; list.tail=new_node;}else{ new_node->next=list.tail->next; list.tail->next=new_node; list.tail=new_node;}list.legth++;read(x);}returnlist;}read(x);上機練習題例2、檢查一個（單向）鏈表，刪除其中數(shù)據(jù)大于100的元素算法實現(xiàn)分析（1）逐個檢查鏈表的算法框架while(current!=NULL){ ...... current=current->next;}ai+1ai-1......aicurrent上機練習題(2)刪除大于100的鏈點if(current->data>100){

刪除該鏈點}必須找到current的前趨鏈點才能刪除ai+1ai-1......aicurrentlastlast->next=current->next;free(current);current=last->next;刪除不刪除last=current;current=current->next;上機練習題(3)邊界：第一個元素需要刪除時if(last=

=NULL){ list->header=current->next; free(current); current=list->header;}ai+1a1...aicurrentlast上機練習題del_over100(list_type*list){}初始化while(current!=NULL){ if(current->data>100){

刪除current; } else{

走向下一個鏈點；

}}voiddel_over100(list_type*list){last=NULL;current=list->header;if(last==NULL){ list->header=current->next; free(current); current=list->header;}else{ last->next=current->next; free(current); current=last->next;}else{ last=current; current=current->next;}while(current!=NULL){

if(current->data>100){}}//while