|
鏈表，一個對于學習過C語言的人都是再熟悉不過的概念了，可能很多學習過鏈表的人都覺得鏈表沒什么值得太在意的地方，可是如果你走進linux內核，去看看linux內核里面鏈表的實現方式，你不得不為之驚嘆。可能有人會覺得linux內核鏈表實現方式僅此而已，但是你要知道，如果你沒有見到這樣的實現方式之前，能寫出那樣的鏈表嘛?所以在寫鏈表的文章時，我深知自己不可能用一篇文章來講解完鏈表的知識點，所以我特地分為三個部分(單鏈表、雙鏈表、linux內核鏈表，而其中linux內核鏈表單獨拿出來講是因為它的特殊性，在后面的博客中我們再來細談它)來進行講解，盡可能用簡短的文字描述加上簡單易懂的代碼來向讀者講解我所理解的鏈表，希望我所講的鏈表能都對你有所幫助。接下來言歸正傳，開始我們的鏈表之旅。 那么什么是鏈表呢?鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點組成，即鏈表中的每個元素，結點可以在運行時動態生成。每個結點均由兩個部分所組成：一個是存儲數據元素的數據域，另一個是存儲相鄰結點地址的指針域。相比于線性表順序結構，鏈表比較方便插入和刪除操作。 對于鏈表我們可以將其分為單鏈表、雙向鏈表和循環鏈表等。首先我們先講講單鏈表。 所謂單鏈表，是指數據結點是單向排列的。一個單鏈表結點，其結構類型分為兩部分： 1、數據域：用來存儲本身數據 2、指針域：用來存儲下一個結點地址或者說指向其直接后繼的指針。 如下圖所示： 注意：如果有圖中的紅色箭頭部分，則變為了單向循環鏈表。 那什么又是雙鏈表呢?雙向鏈表其實是單鏈表的改進。當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接后繼結點地址的鏈域，那么能不能定義一個既有存儲直接后繼結點地址的鏈域，又有存儲直接前驅結點地址的鏈域的這樣一個雙鏈域結點結構呢?這就是雙向鏈表。 在雙向鏈表中，結點除含有數據域外，還有兩個鏈域，一個存儲直接后繼結點地址，一般稱之為右鏈域;一個存儲直接前驅結點地址，一般稱之為左鏈域。 如下圖所示： 注意：如果有圖中的紅色箭頭部分，則變為了雙向循環鏈表。 看完了上面的介紹之后，我想讀者對于鏈表算是有了一個大致的了解。那么接下來我們的任務就是學習如何使用鏈表，我們從最簡單的代碼開始，教會讀者來學習使用鏈表，首先我們來看一個單鏈表的創建。為了便于講解，我在此就把所有的代碼放到一個源文件中來執行了，當然讀者在實際編寫代碼的過程中不管是為了維護還是閱讀都應該使用頭文件，而不要在一個源文件中一條龍似地寫到底。 #include #include #include #include #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("分配內存空間失敗!"); exit(0); } h->name[0]='\0'; h->score=0; h->link=NULL; p=h; for(i=0;i { if((s= (stud *) malloc(sizeof(stud)))==NULL) { printf("分配內存空間失敗!"); 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的成績為%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); } 運行結果為： root@ubuntu:/home/paixu# ./tt 請輸入第1個人的姓名:rewq 請輸入第1個人的成績:123 請輸入第2個人的姓名:fdsa 請輸入第2個人的成績:456 請輸入第3個人的姓名:vcxz 請輸入第3個人的成績:789 rewq成績為123 fdsa成績為456 vcxz成績為789 看了上面的代碼，如果讀過我之前寫的那篇《C語言的那些小秘密之斷言》的讀者就知道，在這段代碼的紅色部分我們使用了自己實現的斷言，學以致用嘛，所有特此在這里拿出來使用下，如果還沒有看那篇文章的讀者，我建議你看看，畢竟斷言還是很有用的。代碼的藍色部分也算是一個特色點，因為以前可能我們在自己的代碼中都是返回一些int型值或者NULL之類的，使得代碼的返回值不能夠直觀的體現出運行結果，也使得代碼的可讀性比較差，所有為了改善我們的代碼，我們要學習自己定義返回類型，做到盡可能的從各個方面去改善我們編寫的代碼。在這里我們自己用枚舉型的數據結構來定義了返回類型，因為代碼的關系，我這里僅僅使用了一個返回類型SLIST_RETURN_OK，根據自己代碼的需要讀者可以自己添加編寫更多的返回值，我僅僅是在這里舉出一個例子。如： typedef enum _SListReturn { SLIST_RETURN_OK, SLIST_RETURN_STOP, SLIST_RETURN_FAIL }SListReturn; 現在我們從以上代碼中選出部分代碼來加注釋進行講解。 stud *p,*h,*s; /* *h保存表頭結點的指針，*p指向當前結點的前一個結點，*s指向當前結點*/ h->link=NULL; /*把表頭結點的鏈域置空*/ p=h; /*p指向表頭結點*/ p->link=s; /*把s的地址賦給p所指向的結點的鏈域，這樣就把p和s所指向的結點連接起來了*/ 在代碼中除了創建鏈表的函數外，我們還使用了兩個函數，一個是SListReturn print(stud* head)函數，通過該函數我們打印輸出鏈表中的數據。另一個函數是SListReturn destroy(stud* head)，通過該函數我們對申請的鏈表空間進行釋放。通過以上函數我想讀者應該知道了如何創建一個鏈表和處理鏈表中的數據，在這里我僅僅是對數據做了打印操作，如果讀者有興趣可以進行其他的操作。 以上代碼實現了單鏈表的創建，但是鏈表的常用操作還有查找、插入、刪除等沒有講解，刪除操作與插入操作類似，就不在這里一一講解了，在此我們以查找和插入為例進行講解，但是讀者在編寫刪除操作的時候別忘了把刪除的結點釋放掉。接下來我們就來看看一段查找和插入的操作。 代碼功能為在查找到的結點后面添加一個新的結點。 #include #include #include #include #define N 3 /*N為人數*/ //#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("分配內存空間失敗!"); exit(0); } h->name[0]='\0'; /*把表頭結點的數據域置空*/ h->score=0; h->link=NULL; /*把表頭結點的鏈域置空*/ p=h; /*p指向表頭結點*/ for(i=0;i { if((s= (stud *) malloc(sizeof(stud)))==NULL) { printf("分配內存空間失敗!"); exit(0); } p->link=s; /*把s的地址賦給p所指向的結點的鏈域，這樣就把p和s所指向的結點連接起來了*/ printf("請輸入第%d個人的姓名:",i+1); scanf("%s",s->name); /*姓名*/ printf("請輸入第%d個人的成績:",i+1); scanf("%d",&s->score); /*分數*/ s->link=NULL; p=s; } return(h); } stud * search(stud *h,char *x) /*查找函數*/ { 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("沒有查找到該數據!"); } SListReturn insert(stud *p) /*插入函數，在指針p后插入*/ { char stu_name[20]; int stu_score; stud *s; /*指針s是保存新結點地址的*/ if((s= (stud *) malloc(sizeof(stud)))==NULL) { printf("分配內存空間失敗!"); exit(0); } printf("請輸入你要插入的人的姓名:"); scanf("%s",stu_name); printf("請輸入你要插入的人的成績:"); scanf("%d",&stu_score); strcpy(s->name,stu_name); /*把指針stuname所指向的數組元素拷貝給新結點的數據域*/ s->score=stu_score; s->link=p->link; /*把新結點的鏈域指向原來p結點的后繼結點*/ p->link=s; /*p結點的鏈域指向新結點*/ 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成績為%d\n",tmp->name,tmp->score); tmp=tmp->link; } return SLIST_RETURN_OK; } void main() { int number; /*保存人數的變量*/ char fname[10]; /*保存輸入的要查找的人的姓名*/ stud *head,*searchpoint; /*head是保存單鏈表的表頭結點地址的指針*/ number=N; head=creat(number); /*把所新建的單鏈表表頭地址賦給head*/ printf("請輸入你要查找的人的姓名:"); scanf("%s",fname); searchpoint=search(head,fname); /*查找并返回查找到的結點指針*/ insert(searchpoint); /*調用插入函數*/ print(head); destroy(head); //ASSERT_REPORT(print(head)==SLIST_RETURN_OK); //ASSERT_REPORT(destroy(head)==SLIST_RETURN_OK); } 運行結果為： 以防圖片打開失敗，在此特地加上文字描述。 請輸入第1個人的姓名:rewq 請輸入第1個人的成績:123 請輸入第2個人的姓名:fdsa 請輸入第2個人的成績:456 請輸入第3個人的姓名:vcxz 請輸入第3個人的成績:789 請輸入你要查找的人的姓名:fdsa 請輸入你要插入的人的姓名:ghjk 請輸入你要插入的人的成績:369 rewq成績為123 fdsa成績為456 ghjk成績為369 vcxz成績為789 第1次釋放 第2次釋放 第3次釋放 第4次釋放 第5次釋放 Press any key to continue 代碼中的關鍵部分都加了注釋來進行說明，所以在此就不做一一講解了，只說幾個值得注意的地方，那就是destroy()函數的實現，可能有很多人對這兒的操作不是很熟悉，因為對于釋放成功與否都沒有能夠直觀的顯示出來，就算寫對了也還是不太確信，這個時候我們就要自己來加點東西了。所以在此特地教讀者一個方法，來進行簡單的驗證，通過i++;、 printf("第%d次釋放\n",i);語句來實現打印釋放了多少個結點，和我們創建的結點數目進行比較即可，在本代碼中我們一開始創建了4個結點(注意：包括頭結點)，之后又插入了一個結點，所以總需要釋放5個結點，看看打印的結果就知道我們的函數實現正確了，當然還有很多驗證的方法，在此僅是例舉一個簡單的方法。 總不能沒玩沒了的寫下去吧，所以暫時到此為止，到下一篇博客我們接著講。由于本人水平有限，博客中的不妥或錯誤之處在所難免，殷切希望讀者批評指正。同時也歡迎讀者共同探討相關的內容，如果樂意交流的話請留下你寶貴的意見。 |
