這個禮拜最令我傷神的，不過幸好很久以前有想過一次，所以要回復記憶比較沒有那麼困難。首先我先把C++版本的linked list刻出來，當然骨幹是參考別人的，然後自己有改了些東西，沒花多久時間很快就用出來了。
以下是標頭檔：
class CKLinkList{
private:
struct node {
int x;
int y;
int z;
node *link;
} *p;
int count_i;
public:
CKLinkList();
void append(int);
void insert_after(int,int);
void insert_first(int);
void display(void);
void display_line(void);
int length(void);
void del(int);
~CKLinkList();
};
接下來是實作
#include <iostream>
#include "linklist.h"
using namespace std;
CKLinkList::CKLinkList(){
p = NULL;
count_i = 0;
};
int CKLinkList::length(){
return count_i;
};
void CKLinkList::del(int num){
node *q, *r;
q = p;
// No node
if (p == NULL) return;
// Delete the first node
if (q->x == num){
p = q->link;
delete q;
count_i--;
return;
}
// Delete the remainder
r = q;
while( q != NULL){
if (q->x == num){
r->link = q->link;
delete q;
count_i--;
return;
}
r = q;
q = q->link;
}
};
void CKLinkList::insert_first(int num){
node *q, *t;
q = p;
t = new node;
t->x = num;
t->y = num*2;
t->z = num*3;
t->link = q;
p = t;
count_i++;
};
void CKLinkList::insert_after(int start_val,int num){
node *q, *t;
if (start_val != 0){
q = p;
while(q->link != NULL){
if (q->x == start_val){
t = new node;
t->x = num;
t->y = num*2;
t->z = num*3;
t->link = q->link;
q->link = t;
count_i++;
return;
}
q = q->link;
}
}
};
void CKLinkList::append(int num){
node *q, *t;
if (p == NULL){
p = new node;
p->x = num;
p->y = num*2;
p->z = num*3;
p->link = NULL;
} else {
q = p;
while(q->link != NULL){
q = q->link;
}
t = new node;
t->x = num;
t->y = num*2;
t->z = num*3;
t->link = NULL;
q->link = t;
}
count_i++;
};
void CKLinkList::display_line(void){
node *q;
for(q = p; q != NULL; q = q->link){
cout << " <- " << q->x;
}
cout << endl;
};
void CKLinkList::display(void){
node *q;
for(q = p; q != NULL; q = q->link){
cout << "This is : " << q->x << ", " << q->y << ", " << q->z << endl;
}
};
CKLinkList::~CKLinkList(){
node *q;
if (p == NULL) return;
while (p != NULL){
q = p->link;
delete p;
p = q;
}
};
接下來我看到了一個使用C++ template去實作的版本，應該說是某個老師的
教學課程(參考第10,11,12章)，我就順便把她的課程講義看過一遍，然後把他的版本做出來。第一次使用C++的template，雖然滿麻煩的，但是真的是很強大，看來以後搞不好我的每個程式都要用template去做出來。以下是template的版本：
#include <iostream>
using namespace std;
template <class T>
class ChainNode {
private:
public:
T data;
ChainNode<T> *link;
ChainNode(void){};
ChainNode(const T& data){ this->data = data; };
ChainNode(const T& data, ChainNode<T> *link){
this->data = data;
this->link = link;
};
};
template <class T>
class Chain {
private:
ChainNode<T> *first;
int count;
public:
Chain(void){ first = NULL; count = 0; };
bool isEmpty() const {return first == NULL;}
int IndexOf(const T&) const;
int size(void){return count;}
void Delete(int);
void Insert(int,const T&);
void Display(void);
~Chain();
};
// Destruction
template <class T>
Chain<T>::~Chain() {
while (first != NULL){
ChainNode<T> *next = first->link;
delete first;
first = next;
}
};
template <class T>
int Chain<T>::IndexOf(const T& theElement) const{
ChainNode<T> *currentNode = first;
int index = 0;
while(currentNode != NULL && currentNode->data != theElement){
currentNode = currentNode->link;
index++;
}
if (currentNode == NULL)
return -1;
else
return index;
};
template <class T>
void Chain<T>::Delete(int theIndex){
if (first == NULL) throw "Can not delete empty chain";
ChainNode<T> *deleteNode;
if (theIndex == 0){
deleteNode = first;
first = first->link;
delete deleteNode;
count--;
} else {
ChainNode<T> *p = first;
for(int i =0; i< theIndex-1; i++){
if (p == NULL) throw "Element not exist";
p = p->link;
}
deleteNode = p->link;
p->link = p->link->link;
delete deleteNode;
count--;
}
}
template <class T>
void Chain<T>::Insert(int theIndex, const T& theElement){
if (theIndex < 0) throw "Bad";
if (theIndex == 0){
first = new ChainNode<T>(theElement,first);
count++;
} else {
ChainNode<T> *p = first;
for(int i = 0; i < theIndex-1; i++){
if (p == NULL) throw "Not Exist";
p = p->link;
}
p->link = new ChainNode<T>(theElement, p->link);
count++;
}
};
template <class T>
void Chain<T>::Display(void){
ChainNode<T> *p = first;
while(p != NULL){
cout << " <- " << p->data;
p = p->link;
}
cout << endl;
};
int main() {
cout << "This is LinkList .." << endl;
Chain<int> *list = new Chain<int>;
cout << "Size: " << list->size() << endl;
list->Insert(0,1);
list->Display();
list->Insert(0,2);
list->Display();
list->Insert(1,3);
list->Display();
list->Insert(1,4);
list->Display();
list->Insert(0,5);
list->Display();
list->Delete(2);
list->Display();
cout << "Size: " << list->size() << endl;
}
繼續努力加油吧，這星期把linked list搞完之後還有很多要充實的，以上的source code都公布在
github上看(其實blog根本不適合看這麼多程式碼是吧XD)。
