注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mr.Right

不顾一切的去想,于是我们有了梦想。脚踏实地的去做,于是梦想成了现实。

 
 
 

日志

 
 
关于我

人生一年又一年,只要每年都有所积累,有所成长,都有那么一次自己认为满意的花开时刻就好。即使一时不顺,也要敞开胸怀。生命的荣枯并不是简单的重复,一时的得失不是成败的尺度。花开不是荣耀,而是一个美丽的结束,花谢也不是耻辱,而是一个低调的开始。

网易考拉推荐

很好的Linked List實現 (C/C++)  

2012-08-12 20:57:04|  分类: 摘录 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

Abstraction
使用C語言簡單的實現linked list,並用C++的std::vector實作出相同的功能作比較。

Introduction
學習資料結構,第一個要學的就是linked list,本文示範最簡單的linked list實現,包含建立與顯示,可把它當成linked list的標準範本,畢竟步驟都差不多。

一個基本的問題:為什麼需要linked list?若要將大量資料存到記憶體,你會想到什麼?第一個想到的就是array,但C語言是個靜態語言,array必須事先宣告大小,這樣compiler才能進行最佳化,若到時候沒用這麼多記憶體,就白白浪費記憶體了。或許你會說array可以配合malloc()變成動態array,但前提是你必須告訴malloc()要建立多大的array,若連要建立多大的陣列也不確定,而是在run-time看有多少資料就建立多大,這時連malloc()的動態array也不能用了,此時就得靠linked list。

linked list是資料結構的基礎,基本上就是靠struct如火車車廂那樣連在一起,run-time有需要時,在動態掛一個struct上去。

C語言

1 /* 
2 (C) OOMusou 2008 http://oomusou.cnblogs.com
3 
4 Filename    : DS_linked_list_simple.c
5 Compiler    : Visual C++ 8.0
6 Description : Demo how to use malloc for linked list
7 Release     : 03/22/2008 1.0
8 */
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <string.h>
12 
13 #define SLEN 255
14 
15 struct list {
16   int  no;
17   char name[SLEN];
18   struct list *next;
19 };
20 
21 int main() {
22   int no;
23   char s[255];
24  
25   struct list *head    = NULL;
26   struct list *current = NULL;
27   struct list *prev    = NULL;
28  
29   while(1) {
30     printf("No. = ");
31     scanf("%d", &no);
32    
33     if (no == 0)
34       break;
35  
36     printf("Name = ");
37     scanf("%s", s);
38    
39     current = (struct list *)malloc(sizeof(struct list));
40     if (current == NULL)
41       exit(EXIT_FAILURE);
42      
43     current->next = NULL;
44    
45     current->no = no;
46     strncpy(current->name, s, SLEN -1);
47     current->name[SLEN -1] = '\0';
48    
49     if (head == NULL)
50       head = current;
51     else
52       prev->next = current;
53      
54     prev = current;
55   }
56  
57   // display linked list
58   current = head;
59   while(current != NULL) {
60     printf("No. = %d, Name = %s\n", current->no, current->name);
61     current = current->next;
62   }
63  
64   // free linked list
65   current = head;
66   while(current != NULL) {
67     prev = current;
68     current = current->next;
69     free(prev);
70   }
71 }


執行結果

No. = 1
Name
= clare
No.
= 2
Name
= jessie
No.
= 0
No.
= 1, Name = clare
No.
= 2, Name = jessie


15行

struct list {
 
int  no;
 
char name[SLEN];
 
struct list *next;
};


linked list的基礎就是struct,所以先建立一個自訂的struct型別,因為linked list是靠struct串聯起來,所以最後要多一個struct pointer指向下一個struct。

25行

struct list *head    = NULL;
struct list *current = NULL;
struct list *prev    = NULL;


建立linked list最基本需要三個指標,head指向linked list的第一個struct,current指向目前剛建立的struct,prev則指向前一個struct,目的在指向下一個struct,對於未使用的pointer,一律指定為NULL,這是一個好的coding style,可以藉由判斷是否為NULL判斷此pointer是否被使用。

39行

current = (struct list *)malloc(sizeof(struct list));
if (current == NULL)
  exit(EXIT_FAILURE);
     
current
->next = NULL;


每當有新資料,需要建立一個新的struct時,就用malloc()要一塊記憶體,由於malloc()傳回的是void *,所以要手動轉型成struct list *。但malloc()並不是一定會成功,若記憶體不足時,仍然會失敗,所以必須判斷是否傳回NULL。

由於一個新的node,一定是linked list最後一個node,所以將current->next接null。

45行

current->no = no;
strncpy(current
->name, s, SLEN -1);
current
->name[SLEN -1] = '\0';


正式將輸入的資料填進struct,至於為什麼要用strncpy()而不用strcpy()呢?雖然strcpy()也可以,但strncpy()比較安全,若輸入的字串大小超過struct所定義的字串大小,則會只接受struct所接受的字串大小,而不會因為找不到'\0'而造成程式錯誤。

49行

if (head == NULL)
  head
= current;
else
  prev
->next = current;
     
prev
= current;


判斷若是第一個node,則將目前的node當成head,若不是第一個node,則將前一個node指向目前的node,完成linked list的連接。最後將目前的node當成前一個node,以備指向下一個node。

58行

// display linked list
current = head;
while(current != NULL) {
  printf(
"No. = %d, Name = %s\n", current->no, current->name);
  current
= current->next;
}


要重新顯示linked list,所以將指標再度指向第一個node,每當顯示一個node後,就指向下一個node,直到指到NULL為止。

64行

// free linked list
current = head;
while(current != NULL) {
  prev
= current;
  current
= current->next;
  free(prev);
}


由於malloc()是將記憶體放在heap,而不是放在stack,所以並不會隨著function的結束而釋放,必須要手動使用free()釋放記憶體,否則會造成memory leak。

再來看C++,由於STL已內建一些容器,所以不需再重新實作linked list,有兩個選擇:std::vector或者std::list。std::vector的優點是non-sequential access超快,新增資料於後端超快,但insert和erase任意資料則超慢;std::list則剛好相反,insert和erase速度超快,但non-sequential access超慢,由於本例只有新增與non-sequential access,所以適合std::vector。不過由於STL使用泛型技術,若將來需求改變,想改用std::list也沒關係,只要將容器改掉即可,剩下的都不用改,因為STL的演算法並不挑容器,這正是泛型偉大之處。

C++

1 /* 
2 (C) OOMusou 2008 http://oomusou.cnblogs.com
3 
4 Filename    : DS_linked_list_simple_vector_class.cpp
5 Compiler    : Visual C++ 8.0
6 Description : Demo how to use vector instead of linked list
7 Release     : 03/22/2008 1.0
8 */
9 #include <iostream>
10 #include <string>
11 #include <vector>
12 
13 using namespace std;
14 
15 class List {
16 public:
17   int no;
18   string name;
19 };
20 
21 int main() {
22   vector<List> vec;
23  
24   while(1) {
25     List list;
26     cout << "No. = ";
27     cin >> list.no;
28    
29     if (list.no == 0)
30       break;
31  
32     cout << "Name = ";
33     cin >> list.name;
34    
35     vec.push_back(list);
36   }
37  
38   vector<List>::iterator iter = vec.begin();
39   for(; iter != vec.end(); ++iter)
40     cout << "No. = " << iter->no << ", Name = " << iter->name << endl;
41 }


執行結果

No. = 1
Name
= clare
No.
= 2
Name
= jessie
No.
= 0
No.
= 1, Name = clare
No.
= 2, Name = jessie


15行由struct改用了class,不過若繼續使用struct亦可,至於其他的程式都很直觀,就不再多做解釋。

Conclusion
本文主要是討論使用C語言透過malloc()實現資料結構的linked list,以彌補靜態語言的不足,同時亦討論C++使用STL的替代方案與便利性,C與C++各擅勝場,你可自行決定使用C或C++。

  评论这张
 
阅读(2299)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016