第C語言深入探索之單鏈表與typedef的用法目錄前言詳解typedef關(guān)鍵字含義具體使用詳解單鏈表參數(shù)形式指針知識補(bǔ)充單鏈表形參詳解單鏈表實戰(zhàn)案例完整代碼實現(xiàn)詳解頭插建表運(yùn)行效果

前言

昨天博主去本站問答貼子逛了逛，然后發(fā)現(xiàn)了好多關(guān)于數(shù)據(jù)結(jié)構(gòu)線性表，具體來說是單鏈表的問題。有的是沒有一點(diǎn)思路，無從下手；有的是看不懂代碼，不理解關(guān)鍵字以及被形參的形式氣的不行，我總結(jié)了一下常見問題來給大家?guī)砀韶?，到后面還有簡單案例來鞏固知識，弄透一題勝無腦刷百題，接下來是正文內(nèi)容。

詳解typedef關(guān)鍵字

含義

C語言允許用戶使用typedef關(guān)鍵字來定義自己習(xí)慣的數(shù)據(jù)類型名稱，來替代系統(tǒng)默認(rèn)的基本類型名稱、數(shù)組類型名稱、指針類型名稱與用戶自定義的結(jié)構(gòu)型名稱、共用型名稱、枚舉型名稱等。一旦用戶在程序中定義了自己的數(shù)據(jù)類型名稱，就可以在該程序中用自己的數(shù)據(jù)類型名稱來定義變量的類型、數(shù)組的類型、指針變量的類型與函數(shù)的類型等。

具體使用

單鏈表結(jié)點(diǎn)示例：

typedefstructnode

intdata;//數(shù)據(jù)域

structnode*next;//指針域

}Lnode,*SLinkList;

這里我們創(chuàng)建了node結(jié)構(gòu)體，結(jié)構(gòu)體里面包含了整型數(shù)據(jù)data，指針next指向下一個結(jié)點(diǎn)的地址?？梢钥吹较旅娲罄ㄌ柾庥蠰node和*SLinkList。他的意思就是我們給node起了一個別名叫Lnode，Lnode具有和node相同的結(jié)構(gòu)，structnoden1與Lnoden1效果完全相同；同時C語言還允許在結(jié)構(gòu)中包含指向它自己的指針，即SLinkListL等價于structnode*L或者Lnode*L；

詳解單鏈表參數(shù)形式

指針知識補(bǔ)充

示例：

//1、

int*getValue1(int*L)

inta=10;

L=

returnL;

int*getValue2(int*L)

inta=10;

L=

returnL;

intmain()

int*ptr=(int*)malloc(sizeof(int)*4);

getValue1(ptr);

getValue2(ptr);

cout*ptrendl;

}

我在主函數(shù)中為指針ptr動態(tài)分配了內(nèi)存空間，大小為4*4字節(jié)，不理解的可以參考我的這篇博文詳解數(shù)據(jù)結(jié)構(gòu)線性表里面的動態(tài)分布內(nèi)存函數(shù)malloc；然后將地址傳遞到上面兩個函數(shù)里面去，輸出getValue1的*ptr結(jié)果是10，但是getValue2中*ptr的結(jié)果卻是亂碼。那么原因很明顯，就是參數(shù)int*L和int*L的區(qū)別了。這個函數(shù)的返回值是一個地址，然而在棧區(qū)開辟的數(shù)據(jù)，在函數(shù)調(diào)用結(jié)束后就會被編譯器自動釋放掉，從而返回的地址不會是a，因此僅僅使用地址傳遞是不行的。那么加上為什么就可以了呢，這是因為我們的目的是改變傳入指針?biāo)赶虻牡刂罚谝环N只能改變該地址對應(yīng)的數(shù)值，第二種可以從本質(zhì)上更改地址，所以能得到a從而*ptr結(jié)果為10。

單鏈表形參詳解

示例：

typedefstructnode

intdata;//數(shù)據(jù)域

structnode*next;//指針域

}Lnode,*SLinkList;

SLinkListInit_List(Lnode*L)

L=(SLinkList)malloc(sizeof(Lnode));

L-next=NULL;

returnL;

}

同樣的，根據(jù)我前面講的知識，我定義了一個SLinkList指針型的初始化鏈表函數(shù)Init_List()，傳入的是結(jié)構(gòu)體指針變量L，接下來為L分配內(nèi)存空間，這里sizeof(Lnode)是計算了結(jié)構(gòu)體Lnode所占內(nèi)存大小并將此內(nèi)存分配給L，接下來讓初始化L，讓其指針域為空。實際上L-data=NULL，L就是單鏈表中的頭結(jié)點(diǎn)。這段代碼是沒有問題的，但是如果把形參中的Lnode*L，改為Lnode*L,那么編譯器必然會提示我們，取消對NULL指針的使用，這就是為什么我們要加上的原因，不加返回的不是我們分配的指針變量L的地址，那這樣我們的初始化毫無意義，雖然不報錯，但是毫無作用。所以提醒你們寫數(shù)據(jù)結(jié)構(gòu)的時候記住這個小細(xì)節(jié)，很重要的！

單鏈表實戰(zhàn)案例

完整代碼實現(xiàn)

#includeiostream

usingnamespacestd;

#defineSIZE10

typedefstructnode

intdata;//數(shù)據(jù)域

structnode*next;//指針域

}Lnode,*SLinkList;

SLinkListInit_List(Lnode*L)

L=(SLinkList)malloc(sizeof(Lnode));

L-next=NULL;

returnL;

SLinkListCreat_List(Lnode*L,intn)//頭插建表

srand((unsignedint)time(NULL));

SLinkListp=L;

for(inti=0;ii++)

inte=rand()%20+1;

SLinkLists=(SLinkList)malloc(sizeof(Lnode));

s-next=p-next;

p-next=s;

s-data=e;

returnL;

intcount_List(Lnode*L)

intcount=0;

SLinkListp=L-next;

while(p)

count++;

p=p-next;

returncount;

intfind_List(SLinkListL,intv)

SLinkListp=L-next;

inti=1;

while(ivp-next)

p=p-next;

i++;

returnp-data;

voiddisplay_List(SLinkListL)

SLinkListp=L-next;

while(p)

coutp-data"";

p=p-next;

intmain()

srand((unsignedint)time(NULL));

intn=rand()%5+5,count=0,v=0;

SLinkListL;

L=Init_List(L);

cout"隨機(jī)插入元素完成："endl;

L=Creat_List(L,n);

count=count_List(L);

cout"單鏈表長度為："countendl;

cout"遍歷單鏈表結(jié)果為："endl;

display_List(L);

coutendl;

cout"要查找元素的位置為：";cinv;

intvalue=find_List(L,v);

cout"查找結(jié)果為："valueendl;

}

詳解頭插建表

把頭插建表方法復(fù)制過來

SLinkListCreat_List(Lnode*L,intn)//頭插建表

srand((unsignedint)time(NULL));

SLinkListp=L;

for(inti=0;ii++)

inte=rand()%20+1;

SLinkLists=(SLinkList)malloc(sizeof(Lnode));

s-next=p-next;

p-next=s;

s-data=e;

returnL;

}

這里不用管srand((unsignedint)time(NULL));這段代碼是為了產(chǎn)生不同隨機(jī)數(shù)，和我講的內(nèi)容沒有什么聯(lián)系；往下看，創(chuàng)建建構(gòu)體指針變量p并把p設(shè)置為頭指針：L是頭結(jié)點(diǎn)，p=L，p指向鏈表第一個帶值結(jié)點(diǎn)。進(jìn)入循環(huán)語句，循環(huán)語句n我會利用隨機(jī)數(shù)產(chǎn)生；e是1~20范圍內(nèi)隨機(jī)的一個數(shù)值，結(jié)構(gòu)體指針變量s被動態(tài)分配內(nèi)存空間s-next=pnext;p-next=s;s-data=e;這三行代碼是頭插法的核心。首先待插入原色s指針指向頭結(jié)點(diǎn)指向的結(jié)點(diǎn)，然后頭指針指向s，這樣鏈表的鏈就連好了，最后給s的數(shù)