那么什么是鏈表呢？鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)組成，即鏈表中的每個元素，結(jié)點(diǎn)可以在運(yùn)行時(shí)動態(tài)生成。每個結(jié)點(diǎn)均由兩個部分所組成：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲相鄰結(jié)點(diǎn)地址的指針域。相比于線性表順序結(jié)構(gòu)，鏈表比較方便插入和刪除操作。
對于鏈表我們可以將其分為單鏈表、雙向鏈表和循環(huán)鏈表等。首先我們先講講單鏈表。
所謂單鏈表，是指數(shù)據(jù)結(jié)點(diǎn)是單向排列的。一個單鏈表結(jié)點(diǎn)，其結(jié)構(gòu)類型分為兩部分：
1、數(shù)據(jù)域：用來存儲本身數(shù)據(jù)
2、指針域：用來存儲下一個結(jié)點(diǎn)地址或者說指向其直接后繼的指針。
如下圖所示：
注意：如果有圖中的紅色箭頭部分，則變?yōu)榱藛蜗蜓h(huán)鏈表。
那什么又是雙鏈表呢？雙向鏈表其實(shí)是單鏈表的改進(jìn)。當(dāng)我們對單鏈表進(jìn)行操作時(shí)，有時(shí)你要對某個結(jié)點(diǎn)的直接前驅(qū)進(jìn)行操作時(shí)，又必須從表頭開始查找。這是由單鏈表結(jié)點(diǎn)的結(jié)構(gòu)所限制的。因?yàn)閱捂湵砻總€結(jié)點(diǎn)只有一個存儲直接后繼結(jié)點(diǎn)地址的鏈域，那么能不能定義一個既有存儲直接后繼結(jié)點(diǎn)地址的鏈域，又有存儲直接前驅(qū)結(jié)點(diǎn)地址的鏈域的這樣一個雙鏈域結(jié)點(diǎn)結(jié)構(gòu)呢？這就是雙向鏈表。
在雙向鏈表中，結(jié)點(diǎn)除含有數(shù)據(jù)域外，還有兩個鏈域，一個存儲直接后繼結(jié)點(diǎn)地址，一般稱之為右鏈域；一個存儲直接前驅(qū)結(jié)點(diǎn)地址，一般稱之為左鏈域。
如下圖所示：
注意：如果有圖中的紅色箭頭部分，則變?yōu)榱穗p向循環(huán)鏈表。
看完了上面的介紹之后，我想讀者對于鏈表算是有了一個大致的了解。那么接下來我們的任務(wù)就是學(xué)習(xí)如何使用鏈表，我們從最簡單的代碼開始，教會讀者來學(xué)習(xí)使用鏈表，首先我們來看一個單鏈表的創(chuàng)建。為了便于講解，我在此就把所有的代碼放到一個源文件中來執(zhí)行了，當(dāng)然讀者在實(shí)際編寫代碼的過程中不管是為了維護(hù)還是閱讀都應(yīng)該使用頭文件，而不要在一個源文件中一條龍似地寫到底。
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#define N 3
#undef _EXAM_ASSERT_TEST_ //禁用
//#define _EXAM_ASSERT_TEST_ //啟用
#ifdef _EXAM_ASSERT_TEST_ //啟用斷言測試
void assert_report( const char * file_name, const char * function_name, unsigned int line_no )
{
printf( "\n[EXAM]Error Report file_name: %s, function_name: %s, line %u\n",
file_name, function_name, line_no );
abort();
}
#define ASSERT_REPORT( condition ) \
do{ \
if ( condition ) \
NULL; \
else \
assert_report( __FILE__, __func__, __LINE__ ); \
}while(0)
#else // 禁用斷言測試
#define ASSERT_REPORT( condition ) NULL
#endif /* end of ASSERT */
typedef enum _SListReturn
{
SLIST_RETURN_OK
}SListReturn;
typedef struct node
{
char name[10];
int score;
struct node *link;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("分配內(nèi)存空間失敗!");
exit(0);
}
h->name[0]='\0';
h->score=0;
h->link=NULL;
p=h;
for(i=0;i<n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("分配內(nèi)存空間失敗!");
exit(0);
}
p->link=s;
printf("請輸入第%d個人的姓名:",i+1);
scanf("%s",s->name);
printf("請輸入第%d個人的成績:",i+1);
scanf("%d",&s->score);
s->link=NULL;
p=s;
}
return h;
}
SListReturn destroy(stud* head)
{
stud* tmp,*next;
tmp=head;
while(tmp!=NULL)
{
next=tmp->link;
tmp->link=NULL;
free(tmp);
tmp=next;
}
return SLIST_RETURN_OK;
}
SListReturn print(stud* head)
{
stud* tmp=head->link;
while(tmp!=NULL)
{
printf("%s的成績?yōu)?d\t",tmp->name,tmp->score);
tmp=tmp->link;
}
return SLIST_RETURN_OK;
}
void main()
{
int number;
stud *head;
number=N;
head=creat(number);
ASSERT_REPORT(print(head)==SLIST_RETURN_OK);
ASSERT_REPORT(destroy(head)==SLIST_RETURN_OK);
}
運(yùn)行結(jié)果為：
root@ubuntu:/home/paixu# ./tt
請輸入第1個人的姓名:rewq
請輸入第1個人的成績:123
請輸入第2個人的姓名:fdsa
請輸入第2個人的成績:456
請輸入第3個人的姓名:vcxz
請輸入第3個人的成績:789
rewq成績?yōu)?23 fdsa成績?yōu)?56 vcxz成績?yōu)?89
看了上面的代碼，如果讀過我之前寫的那篇《C語言的那些小秘密之?dāng)嘌浴返淖x者就知道，在這段代碼的紅色部分我們使用了自己實(shí)現(xiàn)的斷言，學(xué)以致用嘛，所有特此在這里拿出來使用下，如果還沒有看那篇文章的讀者，我建議你看看，畢竟斷言還是很有用的。代碼的藍(lán)色部分也算是一個特色點(diǎn)，因?yàn)橐郧翱赡芪覀冊谧约旱拇a中都是返回一些int型值或者NULL之類的，使得代碼的返回值不能夠直觀的體現(xiàn)出運(yùn)行結(jié)果，也使得代碼的可讀性比較差，所有為了改善我們的代碼，我們要學(xué)習(xí)自己定義返回類型，做到盡可能的從各個方面去改善我們編寫的代碼。在這里我們自己用枚舉型的數(shù)據(jù)結(jié)構(gòu)來定義了返回類型，因?yàn)榇a的關(guān)系，我這里僅僅使用了一個返回類型SLIST_RETURN_OK，根據(jù)自己代碼的需要讀者可以自己添加編寫更多的返回值，我僅僅是在這里舉出一個例子。如：
typedef enum _SListReturn
{
SLIST_RETURN_OK,
SLIST_RETURN_STOP,
SLIST_RETURN_FAIL
}SListReturn;
現(xiàn)在我們從以上代碼中選出部分代碼來加注釋進(jìn)行講解。
stud *p,*h,*s; /* *h保存表頭結(jié)點(diǎn)的指針，*p指向當(dāng)前結(jié)點(diǎn)的前一個結(jié)點(diǎn)，*s指向當(dāng)前結(jié)點(diǎn)*/
h->link=NULL; /*把表頭結(jié)點(diǎn)的鏈域置空*/
p=h; /*p指向表頭結(jié)點(diǎn)*/
p->link=s; /*把s的地址賦給p所指向的結(jié)點(diǎn)的鏈域，這樣就把p和s所指向的結(jié)點(diǎn)連接起來了*/
在代碼中除了創(chuàng)建鏈表的函數(shù)外，我們還使用了兩個函數(shù)，一個是SListReturn print(stud* head)函數(shù)，通過該函數(shù)我們打印輸出鏈表中的數(shù)據(jù)。另一個函數(shù)是SListReturn destroy(stud* head)，通過該函數(shù)我們對申請的鏈表空間進(jìn)行釋放。通過以上函數(shù)我想讀者應(yīng)該知道了如何創(chuàng)建一個鏈表和處理鏈表中的數(shù)據(jù)，在這里我僅僅是對數(shù)據(jù)做了打印操作，如果讀者有興趣可以進(jìn)行其他的操作。
以上代碼實(shí)現(xiàn)了單鏈表的創(chuàng)建，但是鏈表的常用操作還有查找、插入、刪除等沒有講解，刪除操作與插入操作類似，就不在這里一一講解了，在此我們以查找和插入為例進(jìn)行講解，但是讀者在編寫刪除操作的時(shí)候別忘了把刪除的結(jié)點(diǎn)釋放掉。接下來我們就來看看一段查找和插入的操作。
代碼功能為在查找到的結(jié)點(diǎn)后面添加一個新的結(jié)點(diǎn)。
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#define N 3 /*N為人數(shù)*/
//#undef _EXAM_ASSERT_TEST_ //禁用
#define _EXAM_ASSERT_TEST_ //啟用
#ifdef _EXAM_ASSERT_TEST_ //啟用斷言測試
void assert_report( const char * file_name, const char * function_name, unsigned int line_no )
{
printf( "\n[EXAM]Error Report file_name: %s, function_name: %s, line %u\n",
file_name, function_name, line_no );
abort();
}
#define ASSERT_REPORT( condition ) \
do{ \
if ( condition ) \
NULL; \
else \
assert_report( __FILE__, __func__, __LINE__ ); \
}while(0)
#else // 禁用斷言測試
#define ASSERT_REPORT( condition ) NULL
#endif /* end of ASSERT */
typedef enum _SListReturn
{
SLIST_RETURN_OK,
}SListReturn;
typedef struct node
{
char name[20];
int score;
struct node *link;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("分配內(nèi)存空間失敗!");
exit(0);
}
h->name[0]='\0'; /*把表頭結(jié)點(diǎn)的數(shù)據(jù)域置空*/
h->score=0;
h->link=NULL; /*把表頭結(jié)點(diǎn)的鏈域置空*/
p=h; /*p指向表頭結(jié)點(diǎn)*/
for(i=0;i<n;i++)
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("分配內(nèi)存空間失敗!");
exit(0);
}
p->link=s; /*把s的地址賦給p所指向的結(jié)點(diǎn)的鏈域，這樣就把p和s所指向的結(jié)點(diǎn)連接起來了*/
printf("請輸入第%d個人的姓名:",i+1);
scanf("%s",s->name); /*姓名*/
printf("請輸入第%d個人的成績:",i+1);
scanf("%d",&s->score); /*分?jǐn)?shù)*/
s->link=NULL;
p=s;
}
return(h);
}
stud * search(stud *h,char *x) /*查找函數(shù)*/
{
stud *p;
char *y;
p=h->link;
while(p!=NULL)
{
y=p->name;
if(strcmp(y,x)==0)
return(p);
else p=p->link;
}
if(p==NULL)
printf("沒有查找到該數(shù)據(jù)!");
}
SListReturn insert(stud *p) /*插入函數(shù)，在指針p后插入*/
{
char stu_name[20];
int stu_score;
stud *s; /*指針s是保存新結(jié)點(diǎn)地址的*/
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("分配內(nèi)存空間失敗!");
exit(0);
}
printf("請輸入你要插入的人的姓名:");
scanf("%s",stu_name);
printf("請輸入你要插入的人的成績:");
scanf("%d",&stu_score);
strcpy(s->name,stu_name); /*把指針stuname所指向的數(shù)組元素拷貝給新結(jié)點(diǎn)的數(shù)據(jù)域*/
s->score=stu_score;
s->link=p->link; /*把新結(jié)點(diǎn)的鏈域指向原來p結(jié)點(diǎn)的后繼結(jié)點(diǎn)*/
p->link=s; /*p結(jié)點(diǎn)的鏈域指向新結(jié)點(diǎn)*/
return SLIST_RETURN_OK;
}
SListReturn destroy(stud* head)
{
stud* tmp,*next;
tmp=head;
int i=0;
while(tmp!=NULL)
{
next=tmp->link;
tmp->link=NULL;
free(tmp);
tmp=next;
i++;
printf("第%d次釋放\n",i);
}
return SLIST_RETURN_OK;
}
SListReturn print(stud* head)
{
stud* tmp=head->link;
while(tmp!=NULL)
{
printf("%s成績?yōu)?d\n",tmp->name,tmp->score);
tmp=tmp->link;
}
return SLIST_RETURN_OK;
}
void main()
{
int number; /*保存人數(shù)的變量*/
char fname[10]; /*保存輸入的要查找的人的姓名*/
stud *head,*searchpoint; /*head是保存單鏈表的表頭結(jié)點(diǎn)地址的指針*/
number=N;
head=creat(number); /*把所新建的單鏈表表頭地址賦給head*/
printf("請輸入你要查找的人的姓名:");
scanf("%s",fname);
searchpoint=search(head,fname); /*查找并返回查找到的結(jié)點(diǎn)指針*/
insert(searchpoint); /*調(diào)用插入函數(shù)*/
print(head);
destroy(head);
//ASSERT_REPORT(print(head)==SLIST_RETURN_OK);
//ASSERT_REPORT(destroy(head)==SLIST_RETURN_OK);
}
運(yùn)行結(jié)果為：
以防圖片打開失敗，在此特地加上文字描述。
請輸入第1個人的姓名:rewq
請輸入第1個人的成績:123
請輸入第2個人的姓名:fdsa
請輸入第2個人的成績:456
請輸入第3個人的姓名:vcxz
請輸入第3個人的成績:789
請輸入你要查找的人的姓名:fdsa
請輸入你要插入的人的姓名:ghjk
請輸入你要插入的人的成績:369
rewq成績?yōu)?23
fdsa成績?yōu)?56
ghjk成績?yōu)?69
vcxz成績?yōu)?89
第1次釋放
第2次釋放
第3次釋放
第4次釋放
第5次釋放
Press any key to continue
代碼中的關(guān)鍵部分都加了注釋來進(jìn)行說明，所以在此就不做一一講解了，只說幾個值得注意的地方，那就是destroy()函數(shù)的實(shí)現(xiàn)，可能有很多人對這兒的操作不是很熟悉，因?yàn)閷τ卺尫懦晒εc否都沒有能夠直觀的顯示出來，就算寫對了也還是不太確信，這個時(shí)候我們就要自己來加點(diǎn)東西了。所以在此特地教讀者一個方法，來進(jìn)行簡單的驗(yàn)證，通過i++;、 printf("第%d次釋放\n",i);語句來實(shí)現(xiàn)打印釋放了多少個結(jié)點(diǎn)，和我們創(chuàng)建的結(jié)點(diǎn)數(shù)目進(jìn)行比較即可，在本代碼中我們一開始創(chuàng)建了4個結(jié)點(diǎn)（注意：包括頭結(jié)點(diǎn)），之后又插入了一個結(jié)點(diǎn)，所以總需要釋放5個結(jié)點(diǎn)，看看打印的結(jié)果就知道我們的函數(shù)實(shí)現(xiàn)正確了，當(dāng)然還有很多驗(yàn)證的方法，在此僅是例舉一個簡單的方法。
總不能沒玩沒了的寫下去吧，所以暫時(shí)到此為止，到下一篇博客我們接著講。由于本人水平有限，博客中的不妥或錯誤之處在所難免，殷切希望讀者批評指正。同時(shí)也歡迎讀者共同探討相關(guān)的內(nèi)容，如果樂意交流的話請留下你寶貴的意見。
