不過看樓主的問題，好像並未理解鏈表，這個不涉及面向對象。
給妳點資料，摘自譚浩強《C程序設計》
可以到/c?m=9d78d513d9d437a84f9ae4690c66c0161e43f1652bd6a00209d5843b97732d405017e2ac26520775d0d20b1616d9484b9ef02173471450c48cbef95ddccb85585b9f5042676c8d5665d20eafba5155c037e42cfede1af0cb802592dec5a3d84320cd44740e97848b4d0164dd1ef30341e5b1e94b022866adec4072895d605ae83431c0508ee0256e769686ad4b3cc83da66006e1ad22b14e05c563b36f1e3332a25bc07f462740f73e24e8343b13e2e84a905c6e4052a139c3aeb2c6fc39f8cb9e318ffbbbb85e967796c3fd8972550724ed24cebcbdc52a653515a9ccc967b425cd8cfbcd4cfe15a7072cca4a06247cb86a83f48d40f3124d84e37f882836616854d0e932b937676e42b52318b215d775c689614babee8a88e81546ac849d312eafb0ee5fd02f507ebf71364d92a0176a159b0e7e98d6ad6dd67d05a7ce0bc6101aeb285058&p=85769a44ce9711a05f9f8c2354&user=baidu
來看，這樣代碼會自然壹些
10.7 用指針處理鏈表
10.7.1鏈標概述
鏈表是壹種常見的重要的數據結構.它是動態地進行存儲分配的壹種結構.我們知道,用數組存放數據時,
必須事先定義固定的長度(即元素個數).比如,有的班級有100人,而有的班只有30人,如果要用同壹個數組先後存放不同班級的學生數據,則必須定義長度為100的數組.如果事先難以確定壹個班的最多人數,則必須把數組定得足夠大,以能存放任何班級的學生數據.顯然這將會浪費內存.鏈表則沒有這種缺點,它根據需要開辟內存單元.圖10.11表示最簡單的壹種鏈表(單向鏈表)的結構.鏈表有壹個"頭指針"變量,圖中以head表示,它存放壹個地址.
該地址指向壹個元素.鏈表中每壹個元素稱為"結點",每個結點都應包括兩個部分:壹為用戶需要用的實際數據,二為下壹個結點的地址.課以看出,head指向第壹個元素;第壹個元素又指向第二個元素;……,直到最後壹個元素,該元素不再指向其它元素,它稱為'表尾",它的地址部分放壹個"NULL"(表示"空地址").鏈表到此結束.
可以看到:鏈表中各元素在內存中可以不是連續存放的.要找某壹元素,必須先找到上壹個元素,根據它提供的下壹元素地址才能找到下壹個元素.
如果不提供"頭指針"(head),則整個鏈表都無法訪問.鏈表如同壹條鐵鏈壹樣,壹環扣壹環,中間是不能斷開的.打個通俗的比方:幼兒園的老師帶領孩子出來散步,老師牽著第壹個小孩的手,第壹個小孩的另壹只手牽著第二個孩子,……,這就是壹個"鏈",最後壹個孩子有壹只手空著,他是"鏈尾".要找這個隊伍,必須先找到老師,然後順序找到每壹個孩子.
可以看到,這種鏈表的數據結構,必須利用指針變量才能實現
.即:壹個結點中應包含壹個指針變量,用它存放下壹結點的地址.
前面介紹了結構體變量,它包含若幹成員.這些成員可以是數值類型,字符類型,數組類型,也可以是指針類型.這個指針類型可以是指向其它結構體類型數據,也可以指向它所在的結構體類型.例如:
struct student
{int num;
float score;
struct student *next;
next是成員名,它是指針類型的,它指向struct student類型數據(這就是next所在的結構體類型).用這種方法可以建立鏈表.見圖10.12.
其中每壹個結點都屬於struct student類型,它的成員next存放下壹結點的地址,程序設計人員可以不必具體知道地址值,
只要保證將下壹個結點的地址放到前壹結點的成員next中即可.
請註意:上面只是定義了壹個struct student類型,並未實際分配存儲空間.前面講過,鏈表結構是動態地分配存儲的,即在需要時才開辟壹個結點的存儲單元.怎樣動態地開辟和釋放存儲單元呢 C語言編譯系統的庫函數提供了以下有關函數.
1.malloc(size) 在內存的動態存儲區中分配壹個長度為size的連續空間.
此函數的值(即"返回值")是壹個指針,它的值是該分配域的起始地址.如果此函數未能成功地執行,則返回值為0.
2.calloc(n,size) 在內存的動態區存儲中分配n個長度為size的連續空間.函數返回分配域的起始地址;如果分配不成功,返回0.
3.free(ptr) 釋放由ptr指向的內存區.ptr是最近壹次調用ca11或ma11oc函數時返回的值.
上面三個函數中,參數n和size為整型,ptr為字符型指針.
請註意:許多C版本提供的malloc和call0c函數得到的是指向字符型數據的指針.新標準C提供的ma110c和ca11oc函數規定為void*類型.
有了本節所介紹的初步知識,下面就可以對鏈表進行操作了(包括建立鏈表,插入或刪除鏈表中壹個結點等).有些概念需要在後面的應用中逐步建立和掌握.
10.7.2建立鏈表
所謂建立鏈表是指從無到有地建立起壹個鏈表,即壹個壹個地輸入各結點數據,並建立起前後相鏈的關系.下面通過壹個例子來說明如何建立壹個鏈表.
[例10.7]寫壹函數建立壹個有5名學生數據的單向鏈表.
先考慮實現此要求的算法(見圖10. 13).
設三個指針變量:head,p1,p2,它們都指向結構體類型數據.先用mal1oc函數開辟壹個結點,並使p1,p2指向它.
然後從鍵盤讀人壹個學生的數據給pl所指的結點.我們約定學號不會為零,如果輸入的學號為0,則表示建立鏈表的過程完成,該結點不應連接到鏈表中.先使head的值為NULL(即等於0),這是鏈表為"空"時的情況(即head不指向任何結點,鏈表中無結點),以後增加壹個結點就使head指向該結點.
如果輸入的pl壹>num不等於0,而且輸入的是第壹個結點數據(n=1)時,則令head=p1,
即把p1的值賦給head,也就是使head也指向新開辟的結點(圖10.14).P1所指向的新開辟的結點就成為鏈表中第壹個結點.然後再開辟另壹個結點並使p1指向它,接著讀入該結點的數據(見圖10.15(a)).如果輸入的p1->num!=0,則應鏈入第2個結點(n=2),由於n!=1,則將p1的值賦給p2-->next,也就是使第壹個結點的next成員指向第二個結點(見圖10.15(b)).接著使p2=p1,
也就是使p2指向剛才建立的結點,見圖10.15(c).再開辟壹個結點並使pl指向它,並讀入該結點的數據(見圖10.16(a)),在第三次循環中,由於n=3(n!=1),又將pl的值賦給p2壹>next,也就是將第3個結點連接到第2個結點之後,並使p2=p1,使p2指向最後壹個結點(見圖10.16(b).
再開辟壹個新結點,並使pl指向它,
輸入該結點的數據(見圖10.17(a)).由於pl壹>num的值為0,不再執行循環,此新結點不應被連接到鏈表中.此時將NULL賦給p2壹>next,見圖10.17(b).建立鏈表過程至此結束,pl最後所指的結點未鏈入鏈表中,第3個結點的next成員的值為NULL,它不指向任何結點.雖然pl指向新開辟的結點,但從鏈表中無法找到該結點.
建立鏈表的函數可以如下:
#define NULL 0
#define LEN sizeof(struct student)
struct student
{1ong num;
float score;
struct student *next;
};
int n;
struct student *creat()
/*此函數帶回壹個指向鏈表頭的指針*/
{struct student *head;
struct student *p1, *p2;
n=0;
p1=p2=(struct student*)mal1oc(LEN);/*開辟壹個新單元*/
scanf("%ld,%f",&pl壹>num,&pl壹>score);
head=NULL:
while (pl壹>num!=0)
{n=n十1;
if(n==1) head=pl;
else p2壹>next=p1;
p2=pl;
pl=(struct student*)malloc(LEN);
scanf("%1d,%f",&p1-->num,&pl壹>score);
}
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;
{struct student *p;
printf("\nNow,These%drecords are:\n",n);
p=head;
if(head!=NULL)
do
{printf("%ld%5.1f\",p壹>num,p—>score);
p=p壹>next;
}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;
{struct student *p1,*p2;
if(head==NULL) {printf("\nlist null!\n");goto end;}
p1=head;
whi1e (num!=pl壹>num&&pl壹>next!壹NULL)/*pl指向的不是所要找的結點,並且後面還有結點點*/
{p2=p1;pl=pl壹>next;}/*後移壹個結點*/
if (num==pl壹>num) /*找到了*/
{if (n1==head) head=pl壹>next;/*若pl指向的是頭結點,把第二個結點地址賦予head*/
e1se p2壹>next=pl壹>next;/*否則將下壹結點地址賦給前壹結點地址*\
printf("delete:%ld\n",num);
n=n-1;
}
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:
{struct student *p0,*p1,*p2;
pl=head;/*使pl指向第壹個結點*/
p0=stud;/*p0指向要插入的結點*/
if (head==NULL)/*原來是空表*/
{head=p0;p0壹>next=NULL;}/*使p0指向的結點作為第壹個結點*/
else
{while ((p0壹>num>pl壹>num)&&(pl壹>next!=NULL))
{p2=p1;p1=pl壹>next;}/*p2指向剛才pl指向的結點,p1後移壹個結點*/
if(p0->numnext=p0;/*插到p2指向的結點之後*/
p0—>next=p1;}
else
{pl壹>next=p0;p0壹>next=NULL;}}/*插到最後的結點之後*/
n=n+1; /*結點數加1*/
return(head);
}
函數參數是head和stud.stud也是壹個指針變量,從實參傳來待插入結點的地址給stud.語句p0=stud的作用是使p0指向待插入的結點.
函數類型是指針類型,函數值是鏈表起始地址head.
將以上建立,輸出,刪除,插入的函數組織在壹個程序中,用main函數作主調函數.可以寫出以下main函數.
main()
{struct student *head,stu;
1ong de1_num;
printf("input records:\n");
head=creat(); /*返回頭指針*/
print(head); /*輸出全部結點*/
printf("\ninput the deleted 0number:");
scanf("%ld",&de1_mum);/*輸入要刪除的學號*/
head=del(head,de1_num);/*刪除後的頭地址*/
print(head); /*輸出全部結點*/
prinif("/ninput the inserted record:")/*輸入要插入的記錄*/
scanf("%ld,%f",&stu.num,&stu.score);
head=insert(head,&stu);/*返回地址*/
print(head);
}
此程序運行結果是正確的.
它只刪除壹個結點,插入壹個結點.但如果想再插入壹個結點,重復寫上程序最後四行,即***插入兩個結點.運行結果卻是錯誤的.
input records:(建立鏈表)
89101,90
89103,98
89105,76
0,0
Now,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()
{struct student *head,*stu;
1ong de1_num;
printf("input records:/n");
head=creat();
print (head);
printf("/ninput the deleted number:");
scanf("%1d",&del_num);
while (de1_num!=0)
{head=del(head,del_num);
print(head);
printf("input the deleted number:");
scanf("%ld",&del_num);
printf("\ninput the inserted record:");
stu=(struct student*)malloc(LEN);
scanf("%1d,%f,",&stu壹>num,&stu壹>scor);
while (stu壹>num!=0)
{head=insert(head,stu):
print(head);
prinif("input the inserted record:");
stu=(struct student*)malloc(LEN);
scanf("%1d,%f,&stu壹>num,&stu壹>score);
}
}
sum定義為指針變量,在需要插入時先用malloc函數開辟壹個內存區,將其起始地址經強制類型轉換後賦給stu,然後輸入此結構體變量中各成員的值.對不同的插入對象,stu的值是不同的,每次指向壹個新的結構體變量.在調用insert函數時,實參為head和stu,將已建立的鏈表起始地址傳給insert函數的形參,將stu(既新開辟的單元的地址)傳給形參stud,函數值返回經過插入之後的鏈表的頭指針(地址).
運行情況如下:
input records:
89101,99
89103,87
89105,77
0,0
Now, 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
對這個程序請讀者仔細消化.
指針的應用領域很寬廣,除了單向鏈表之外,還有環形鏈表,雙向鏈表.此外還有隊列,樹,棧,圖等數據結構.
有關這些問題的算法可以學習《數據結構>>課程,在此不作詳述.