Linking-List Implement

[轉載] from: http://www.cnblogs.com/oomusou/archive/2008/03/22/1117686.html
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上去。

For C語言:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SLEN 255
 
struct list {
  int  no;
  char name[SLEN];
  struct list *next;
};
int main() {
  int no;
  char s[255];
  struct list *head    = NULL;
  struct list *current = NULL;
  struct list *prev    = NULL;
 
  while(1) {
    printf("No. = ");
    scanf("%d", &no);
    if (no == 0)
      break;
 
    printf("Name = ");
    scanf("%s", s);
 
    current = (struct list *)malloc(sizeof(struct list));
    if (current == NULL)
      exit(EXIT_FAILURE);
 
    current->next = NULL;
 
    current->no = no;
    strncpy(current->name, s, SLEN -1);
    current->name[SLEN -1] = '\0';
 
    if (head == NULL)
      head = current;
    else
      prev->next = current;
 
    prev = current;
  }
 
  // display linked list
  current = head;
  while(current != NULL) {
    printf("No. = %d, Name = %s\n", current->no, current->name);
    current = current->next;
  }
 
  // free linked list
  current = head;
  while(current != NULL) {
    prev = current;
    current = current->next;
    free(prev);
  }
  return 0;
}

執行結果:

1
ssss
2
kkkk
3
gggg
4
llll
0
No. = Name = No. = Name = No. = Name = No. = Name = No. = No. = 1, Name = ssss
No. = 2, Name = kkkk
No. = 3, Name = gggg
No. = 4, Name = llll

好吧，我承認怪怪的，可以Work了!

For C++:

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
class List {
public:
  int no;
  string name;
};
 
int main() {
  vector<list> vec;
 
  while(1) {
    List list;
    cout << "No. = ";
    cin >> list.no;
 
    if (list.no == 0)
      break;
 
    cout << "Name = ";
    cin >> list.name;
 
    vec.push_back(list);
  }
 
  vector<list>::iterator iter = vec.begin();
  for(; iter != vec.end(); ++iter)
    cout << "No. = " << iter->no << ", Name = " << iter->name << endl;
  return 0;
}

C++看起來簡單多了!