前言
上一篇《C和指針》可能對關於C和指針的有些內容沒有說透,下來寫了一個鏈表的實現,當然,也是用C的函數指針來模擬OO的結構來做的。鏈表結構本身比較復雜(關於指針的使用方面),所以這個例子可能更清晰一些。之所以選List這個例子來說,是因為大家在學校裡肯定接觸過這個簡單數據結構,從一個比較熟悉的例子入手可能比較容易理解一些。
接口定義
可以先看看接口的定義,與Java或者C#類似:
/*
* File: IList.h
* Author: juntao.qiu
*
* Created on May 22, 2009, 2:51 PM
*/
#ifndef _ILIST_H
#define _ILIST_H
typedef struct node{
void *data;
struct node *next;
}Node; //定義List中的元素類型,void * 相當於C中的泛型,可以支持任何結構的節點
typedef struct list{
struct list *_this;
Node *head;
int size;
void (*insert)(void *node);
void (*drop)(void *node);
void (*clear)();
int (*getSize)();
void* (*get)(int index);
void (*print)();
}List; //用head (Node)來維護鏈表的鏈!
void insert(void *node);
void drop(void *node);
void clear();
int getSize();
void* get(int index);
void print();
#endif /* _ILIST_H */
接口中定義所有的公開的方法,正如所有的List結構一樣,我們定義了
void insert(node);//插入一個新的節點到List
void drop(node);//刪除一個指定的節點
void clear();//清空List
int getSize();//取到List的大小
void* get(int index);//取到指定位置的元素
void print();//打印整個List,用於調試
這樣幾個方法。
接口的實現
然後看看實現,同上篇一樣,引入一個標記鏈表自身的_this指針,通過對這個指針的引用來修改真實對象中的狀態。
#include <stdlib.h>
#include "IList.h"
Node *node = NULL;
List *list = NULL;
/* 函數聲明塊,作用已經在上邊解釋了*/
void insert(void *node);
void drop(void *node);
void clear();
int getSize();
void print();
void* get(int index);
/* 構造方法 */
List *ListConstruction(){
list = (List*)malloc(sizeof(List));
node = (Node*)malloc(sizeof(Node));
list->head = node;
list->insert = insert;
list->drop = drop;
list->clear = clear;
list->size = 0;
list->getSize = getSize;
list->get = get;
list->print = print;
list->_this = list;
return (List*)list;
}
void ListDeconstruction(){
}
//插入節點,size增加1
void insert(void *node){
Node *current = (Node*)malloc(sizeof(Node));
current->data = node;
current->next = list->_this->head->next;
list->_this->head->next = current;
(list->_this->size)++;
}
//刪除一個節點,size減1
void drop(void *node){
Node *t = list->_this->head;
Node *d = NULL;
int i = 0;
for(i;i < list->_this->size;i++){
d = list->_this->head->next;
if(d->data == ((Node*)node)->data){
list->_this->head->next = d->next;
free(d);
(list->_this->size)--;
break;
}else{
list->_this->head = list->_this->head->next;
}
}
list->_this->head = t;
}
//取到指定index的節點
void* get(int index){
Node *node = list->_this->head;
int i = 0;
if(index > list->_this->size){
return NULL;
}else{
for(i;i < index;i++){
node = node->next;
}
if(node != (Node*)0){
return node->data;
}else{
return NULL;
}
}
}
void clear(){
Node *node = NULL;
int i = 0;
for(i;i< list->_this->size;i++){
node = list->_this->head;
list->_this->head = list->_this->head->next;
free(node);
}
list->_this->size = 0;
list = NULL;
}
int getSize(){
return list->_this->size;
}
//調試用,像這種getSize(), print()這種調用,需要注意的是在調用過程中不能對原始指針做任何修改,
//否則可能出現無法預測的錯誤。
void print(){
Node *node = list->_this->head;
int i = 0;
for(i;i <= list->_this->size;i++){
if(node != (Node*)0){
printf("[%p] = {%s}\n",&node->data, node->data);
node = node->next;
}
}
}
測試
/*
* File: Main.c
* Author: juntao.qiu
*
* Created on May 21, 2009, 4:05 PM
*/
#include <stdio.h>
#include <stdlib.h>
s#include "IList.h"
int main(int argc, char** argv) {
List *list = (List*)ListConstruction();//構造一個新的list
list->insert("Apple");
list->insert("Borland");
list->insert("Cisco");
list->insert("Dell");
list->insert("Electrolux");
list->insert("FireFox");
list->insert("Google");//插入一些節點
list->print();//查看是否插入正確
printf("list size = %d\n",list->getSize());
//刪除兩個節點,並打印結果查看。
Node node;
node.data = "Electrolux";
node.next = NULL;
list->drop(&node);
node.data = "Cisco";
node.next = NULL;
list->drop(&node);
list->print();
printf("list size = %d\n",list->getSize());
list->clear();
return 0;
}
運行結果
$./ooc
[00489760] = {Google}
[00489730] = {FireFox}
[00489700] = {Electrolux}
[004896D0] = {Dell}
[004896A0] = {Cisco}
[00489670] = {Borland}
[00489640] = {Apple}
list size = 7
[00489760] = {Google}
[00489730] = {FireFox}
[004896D0] = {Dell}
[00489670] = {Borland}
[00489640] = {Apple}
list size = 5
可以看出,程序正如預期的那樣運行(前一項為節點在內存中的地址,後一項為節點的值),如果大家有興趣,可以將上一篇《C和指針》s中的Executor裝入一個List實現一個Executor的管理器,加入get方法,同時考慮多線程的狀態,即可自己完成一個線程池的實現。