1樓：
給你些資料吧~仔細看，看完就明白連結串列了
10.7 用指標處理連結串列
10.7.1鍊標概述
連結串列是一種常見的重要的資料結構.它是動態地進行儲存分配的一種結構.我們知道,用陣列存放資料時,
必須事先定義固定的長度(即元素個數).比如,有的班級有100人,而有的班只有30人,如果要用同乙個陣列先後存放不同班級的學生資料,則必須定義長度為100的陣列.如果事先難以確定乙個班的最多人數,則必須把陣列定得足夠大,以能存放任何班級的學生資料.
顯然這將會浪費記憶體.連結串列則沒有這種缺點,它根據需要開闢記憶體單元.圖10.
11表示最簡單的一種連結串列(單向連結串列)的結構.連結串列有乙個"頭指標"變數,圖中以head表示,它存放乙個位址.
該位址指向乙個元素.連結串列中每乙個元素稱為"結點",每個結點都應包括兩個部分:一為使用者需要用的實際資料,二為下乙個結點的位址.
課以看出,head指向第乙個元素;第乙個元素又指向第二個元素;……,直到最後乙個元素,該元素不再指向其它元素,它稱為'表尾",它的位址部分放乙個"null"(表示"空位址").連結串列到此結束.
可以看到:連結串列中各元素在記憶體中可以不是連續存放的.要找某一元素,必須先找到上乙個元素,根據它提供的下一元素位址才能找到下乙個元素.
如果不提供"頭指標"(head),則整個連結串列都無法訪問.連結串列如同一條鐵鍊一樣,一環扣一環,中間是不能斷開的.打個通俗的比方:
幼兒園的老師帶領孩子出來散步,老師牽著第乙個小孩的手,第乙個小孩的另乙隻手牽著第二個孩子,……,這就是乙個"鏈",最後乙個孩子有乙隻手空著,他是"鏈尾".要找這個隊伍,必須先找到老師,然後順序找到每乙個孩子.
可以看到,這種連結串列的資料結構,必須利用指標變數才能實現
.即:乙個結點中應包含乙個指標變數,用它存放下一結點的位址.
前面介紹了結構體變數,它包含若干成員.這些成員可以是數值型別,字元型別,陣列型別,也可以是指標型別.這個指標型別可以是指向其它結構體型別資料,也可以指向它所在的結構體型別.
例如:struct student
; int n;
struct student *creat()
/*此函式帶回乙個指向連結串列頭的指標*/
p2一》next=null;
return(head);
} 請注意:
(1)第一行為#define命令列,令null代表0,用它表示"空位址".第二行令len代表struct student結構體型別資料的長度,
sizeof是"求位元組數運算子".
(2)第9行定義乙個creat函式,它是指標型別,即此函式帶回乙個指標值,它指向乙個struct student型別資料.實際上此creat函式帶回乙個鏈(3)malloc(len)的作用是開闢乙個長度為len的記憶體區,len已定義為sizeof(struct student),即結構體struct student的長度.在一般系統中,malloc帶回的是指向字元型資料的指標.
而p1,p2是指向struct student型別資料的指標變數,二者所指的是不同型別的資料,這是不行的.因此必須用強制型別轉換的方法使之型別一致,在malloc (len)之前加了"(struct student*)",它的作用是使malloc返回的指標轉換為指向struct student型別資料的指標.注意"*"號不可省略,否則變成轉換成struct student型別了,而不是指標型別了.
(4)最後一行return後面的引數是head(head已定義為指標變數,指向struct student型別資料).因此函式返回的是head的值,也就是連結串列的頭位址.
(5)n是結點個數.
(6)這個演算法的思路是:讓pl指向新開的結點,p2指向連結串列中最後乙個結點,把pl所指的結點連線在p2所指的結點後面,用"p2一》next=pl"來實現.
我們對建立連結串列過程作了比較詳細的介紹,
讀者如果對建立連結串列的過程比較清楚的話,對下面介紹的刪除和插入過程也就比較容易理解了.
10.7.3輸出鏈麥
將連結串列中各結點的資料依次輸出.這個問題比較容易處理.首先要知道連結串列頭元素的位址,也就是要知道head的值.
然後設乙個指標變數p,先指向第乙個結點,輸出p所指的結點,然後使p後移乙個結點,再輸出.直到連結串列的尾結點.
「例10.8]寫出輸出連結串列的函式print.
void print(head)
struct student *head;
while(p!=null);
演算法可用圖10.18表示.
其過程可用圖10.19表示.p先指向第一結點,在輸出完第乙個結點之後,p移到圖中p'虛線位置,指向第二個結點.
程式中p=p一》next的作用是:將p原來所指向的結點中next的值賦給p,
而p一》next的值就是第二個結點的起始位址.將它賦給p就是使p指向第二個結點.
head的值由實參傳過來,也就是將已有的連結串列的頭指標傳給被呼叫的函式,在print函式中從head所指的第乙個結點出發順序輸出各個結點.
10.7.4 對鏈麥的刪除操作
已有乙個連結串列,希望刪除其中某個結點.怎樣考慮此問題的演算法呢,先打個比方:
一隊小孩(a.b.c.
d.e)手拉手,如果某一小孩(c)想離隊有事,而隊形仍保持不變.只要將c的手從兩邊脫開,b改為與d拉手即可,見圖10.
20.圖10.20(a)是原來的隊伍,圖10.
20(b)是c離隊後的隊伍.
與此相仿,從乙個連結串列中刪去乙個結點,並不是真正從記憶體中把它抹掉,而是把它從連結串列中分離開來,即改變鏈結關係即可.
[例10.9]寫一函式以刪除指定的結點.
我們以指定的學號作為刪除結點的標誌.例如,輸入89103表示要求刪除學號為89103的結點.解題的思路是這樣的:
從p指向的第乙個結點開始,檢查該結點中的num值是否等於輸入的要求刪除的那個學號.如果相等就將該結點刪除,如不相等,就將p後移乙個結點,再如此�下去,直到遇到表尾為止.
可以設兩個指標變數pl和p2,先使pl指向第乙個結點(圖10.21(a)).如果要刪除的不是第乙個結點,
則使pl後指向下乙個結點(將pl一》next賦給pl),在此之前應將pl的值賦給p2,使p2指向剛才檢查過的那個結點,見圖10.21(b).如此一次一次地使p後移,直到找到所要刪除的結點或檢查完全部連結串列都找不到要刪除的結點為止.
如果找到某一結點是要刪除的結點,還要區分兩種情況:①要刪的是第乙個結點(pl的值等於head的值,如圖10.21(a)那樣),則應將pl一》next賦給head.
見圖10.21(c).
這時head指向原來第二個結點.第乙個結點雖然仍存在,但它已與連結串列脫離,因為連結串列中沒有乙個元素或頭指標指向它.雖然p1還指向它,它仍指向第二個結點,但仍無濟於事,現在連結串列的第乙個結點是原來第二個結點,原來第乙個結點"丟失".
②如果要刪除的不是第乙個結點,則將pl一》next賦給p2一》next,見圖10.21(d).p2一》next原來指向pl指向的結點(圖中第二個結點),現在p2一》next改為指向p1一》next所指向的結點
(圖中第三個結點).pl所指向的結點不再是連結串列的一部分.
還需要考慮連結串列是空表(無結點)和連結串列中找不到要刪除的結點的情況.
圖10.22表示解此題的演算法.
刪除結點的函式del如下:
struct student *del(head,num)
struct student *head;
1ong num;
p1=head;
whi1e (num!=pl一》num&&pl一》next!一null)/*pl指向的不是所要找的結點,並且後面還有結點點*/
/*後移乙個結點*/
if (num==pl一》num) /*找到了*/
else printf("%ld not been found!\n",num);/*找不到該結點*/
end:
return(head);
} 函式的型別是指向struct student型別資料的指標,
它的值是連結串列的頭指標.函式引數為head和要刪除的學號num.head的值可能在函式執行過程中被改變(當刪除第乙個結點時).
10.7.5對連結串列的插入操作
將乙個結點插入到乙個已有的連結串列中.設已有的連結串列中各結點中的成員項num(學號)是按學號由小到大順序排列的.
用指標變數p0指向待插入的結點,pl指向第乙個結點.見圖10.23(a).
將p0一》num與pl一》num相比較,如果p0一》num>pl一》num,則待插入的結點不應插在pl所指的結點之前.此時將pl後移,並使p2指向剛才pl所指的結點,見圖10.23(b).
再將p1一》num與p0一》num比.如果仍然是p0一》num大,則應使pl繼續後移,直到p0一》numnum為止.這時將p0所指的結點插到pl所指結點之前.
但是如果p1所指的已是表尾結點,則pl就不應後移了.如果p0一》num比所有結點的num都大,
則應將p0所指的結點插到連結串列末尾.
如果插入的位置既不在第乙個結點之前,又不在表尾結點之後,則將p0的值賦給p2一》next,即使p2一》next指向待插入的結點,然後將pl的值賦給p0->next,即使得p0一》next指向pl指向的變數.見圖10.23(c).
可以看到,在第乙個結點和第二個結點之間已插入了乙個新的結點.
如果插入位置為第一結點之前(即pl等於head時),
則將p0賦給head,將p1賦給p0->next.見圖10.23(d).
如果要插到表尾之後,應將p0賦給pl一》next,null賦給p0一》next,見圖10.23(e).
以上演算法可用圖10.24表示.
[例10. 10]插入結點的函式insert如下.
struct student *insert(head,stud)
struct student *head,*stud:
/*使p0指向的結點作為第乙個結點*/
else
/*p2指向剛才pl指向的結點,p1後移乙個結點*/
if(p0->numnext=p0;/*插到p2指向的結點之後*/
p0—>next=p1;}
else
}/*插到最後的結點之後*/
n=n+1; /*結點數加1*/
return(head);
} 函式引數是head和stud.stud也是乙個指標變數,從實參傳來待插入結點的位址給stud.語句p0=stud的作用是使p0指向待插入的結點.
函式型別是指標型別,函式值是連結串列起始位址head.
將以上建立,輸出,刪除,插入的函式組織在乙個程式中,用main函式作主調函式.可以寫出以下main函式.
main()
此程式執行結果是正確的.
它只刪除乙個結點,插入乙個結點.但如果想再插入乙個結點,重複寫上程式最後四行,即共插入兩個結點.執行結果卻是錯誤的.
input records:(建立連結串列)
89101,90
89103,98
89105,76
0,0now,these 3 records are:
89101 90.0
89103 98.0
89105 76.0
inpu the deleted number:
89103 (刪除)
delete:89103
now,these 2 records are:
89101 90.0 89105 76.0
input the inserted record:89102
90 (插入第乙個結點)
now,these 3 records are:
89101 90.0
89102 90.0
89105 76.0
input the inserted record:89104,99/(插入第二個結點)
now,the 4 records are:
89101 90.0
89104 99.0
89104 99.0
89104 99.0
......
(無終止地輸出89104的結點資料)
請讀者將main與insert函式結合起來考察為什麼會產生以上執行結果.
出現以上結果的原因是:stu是乙個有固定位址的變數.第一次把stu結點插入到連結串列中.第二次若再用它來插入第二個結點,就把第一次結點的資料沖掉了.
實際上並沒有開闢兩個結點.讀者可根據insert函式畫出此時連結串列的情況.為了解決這個問題,必須在每插入乙個結點時新開闢乙個記憶體區.
我們修改main函式,使之能刪除多個結點(直到輸入要刪的學號為0),能插入多個結點(直到輸入要插入的學號為0).
main函式如下:
main() }
sum定義為指標變數,在需要插入時先用malloc函式開闢乙個記憶體區,將其起始位址經強制型別轉換後賦給stu,然後輸入此結構體變數中各成員的值.對不同的插入物件,stu的值是不同的,每次指向乙個新的結構體變數.在呼叫insert函式時,實參為head和stu,將已建立的連結串列起始位址傳給insert函式的形參,將stu(既新開闢的單元的位址)傳給形參stud,函式值返回經過插入之後的連結串列的頭指標(位址).
運**況如下:
input records:
89101,99
89103,87
89105,77
0,0now, these 3 records are.
89101 99.0
89103 87.0
89105 77.0
input the deleted number:89103
delete:89103
now,these 2 records are:
89101 99.0
89105 77.0
input the de1eted number:89105
delete:89105
now,these l records are:
89101 99.0
input the de1eted number:0
1nput the inserted record:89104,87
now,these 2 records are:
89101 99.0
89104 87.0
input the inserted record:89106,65
now,these 3 records are:
89101 99.0
89104 87.0
89106 65.0
input the inserted record:0,0
對這個程式請讀者仔細消化.
指標的應用領域很寬廣,除了單向連結串列之外,還有環形連結串列,雙向連結串列.此外還有佇列,樹,棧,圖等資料結構.
有關這些問題的演算法可以學習《資料結構》課程,在此不作詳述.
c語言連結串列建立和輸入，C語言連結串列建立和輸入
include link.h 實現類似於strlen struct string linkinfo bl stringlen blstring link char p block pnode null if null link 連結串列為空 if null link head else 當while...
c語言刪除連結串列問題，C語言刪除連結串列問題
del函式while改為 while p1 null if p1 data num p1 p1 next 這個就需要你判斷了，你首先需要將連結串列的資料全部遍歷一遍，在遍歷的同時就判斷該資料是否為你要刪除的資料，如果是，就刪除，繼續遍歷 一直到結束，這樣就可以吧1全部刪除了。滿意請採納！用這個程式到...
C語言連結串列
include include struct chain struct chain create return head struct chain inlink struct chain head,int a,int b int a代表要插入的節點，int b代表建立節點的資料域 if head v...