1.3.1 变长结构体的实现
以上文数据结构C语言——双向链表及其实现的双向环链为例,具体封装方法如下:
在上述双向环链中节点中不可避免地引入了数据指针 void *data占用了8byte的空间,那么能不能在链表每个节点中省去这8byte的空间呢?我们可以使用一个长度为0的字符串指针作为一个不占空间的指示符(数据域的入口地址),在申请节点空间时就需要申请节点结构体空间大小加上头结点中用户设置的size大小的空间,这样每个节点的下方就会附加上一段数据域的空间用于存放数据。
简单示例
struct node_st{
struct node_st *prev;
struct node_st *next;
char data[0];//长度为0的数组仅作为一个地址知识的作用不占用内存空间
};
struct node_st *node = malloc(sizeof(*node) + head->size);//申请节点空间
/*
* 除此之外还需要改动一些其他操作
*/
改进版本
//llist,h :10
struct llist_node_st{
//void *data;
struct llist_node_st *prev;
struct llist_node_st *next;
char data[0];
};
//llist.c :15
//new->head.data = NULL;
//llist.c :30
//newnode->data = malloc(ptr->size);
//llist.c :56
struct llist_node_st *cur = NULL;
for(cur = ptr->head.next; cur != &ptr->head; cur = cur->next){
if(cmp(key, cur->data) == 0)
break;
}
return cur;
//llist.c :83
//free(node->data);
//llist.c :105
//free(node->data);
//llist.c :124
//free(cur->data);
/*
* 其他部分不需要改动
*/
1.3.2 面向对象的封装方法
在封装C的函数时可以采用面向对象的封装方法,将结构体类化,以实现对用户隐藏函数的效果。集体方法如下:
在结构体中定义一组对应方法的函数指针,将需要隐藏的函数方法声明转移到.c文件中并在结构体的初始化过程中添加对应函数指针的赋值操作,用户使用方法时仅需要使用 结构体指针->函数指针(参数表)
的方法即可实现对函数的调用。
llist.h
#ifndef LLIST_H__
#define LLIST_H__
#define LLIST_FORWARD 0x0
#define LLIST_BACKWARD 0x1
typedef void llist_op(const void *);
typedef int llist_cmp(const void *, const void *);
struct llist_node_st{
//void *data;
struct llist_node_st *prev;
struct llist_node_st *next;
char data[0];
};
typedef struct llist_head{
int size;
struct llist_node_st head;
int (*insert)(struct llist_head *, const void *, unsigned char );
void *(*find)(struct llist_head *, const void *, llist_cmp *);
int (*delete)(struct llist_head *, const void *, llist_cmp *);
int (*fetch)(struct llist_head *, const void *, llist_cmp *, void *);
void (*travel)(struct llist_head *, llist_op *);
}LLIST;
LLIST *llist_creat(int size);
void llist_destroy(LLIST *);
#endif
llist.c的前几行
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "llist.h"
int llist_insert(LLIST *, const void *data, unsigned char mode);
void *llist_find(LLIST *, const void *key, llist_cmp *);
int llist_delete(LLIST *, const void *key, llist_cmp *);
int llist_fetch(LLIST *, const void *key, llist_cmp *, void *data);
void llist_travel(LLIST *, llist_op *);
LLIST *llist_creat(int size){
LLIST *new;
new = malloc(sizeof(*new));
if(new == NULL){
return NULL;
}
new->size = size;
//new->head.data = NULL;
new->head.prev = &new->head;
new->head.next = &new->head;
new->insert = llist_insert;
new->find = llist_find;
new->delete = llist_delete;
new->fetch = llist_fetch;
new->travel = llist_travel;
return new;
}
main.c 中的函数方法调用
handler = llist_creat(sizeof(SCORE));
handler->insert(handler, &tmp, LLIST_BACKWARD);
handler->travel(handler, print_s);
... ...
1.3.2 隐藏数据类型的封装方法
隐藏数据类型的封装方法是基于可变长结构体的封装基础实现的,与面向对象的封装方法不兼容。
思想:将头文件中的数据结构定义到.c文件中,然后在.h文件中 typedef
一个空类型的的形式化类型,然后在.c文件中所有涉及该数据类型的函数中接受参数后都来一个强转,这样就实现了对数据结构的隐藏。
在 1.3.1的基础上修改文件如下
Makefile、main.c不变
llist.h
#ifndef LLIST_H__
#define LLIST_H__
typedef void LLIST;
#define LLIST_FORWARD 0x0
#define LLIST_BACKWARD 0x1
typedef void llist_op(const void *);
typedef int llist_cmp(const void *, const void *);
LLIST *llist_creat(int size);
int llist_insert(LLIST *, const void *data, unsigned char mode);
void *llist_find(LLIST *, const void *key, llist_cmp *);
int llist_delete(LLIST *, const void *key, llist_cmp *);
int llist_fetch(LLIST *, const void *key, llist_cmp *, void *data);
void llist_travel(LLIST *, llist_op *);
void llist_destroy(LLIST *);
#endif
llist.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "llist.h"
struct llist_node_st{
//void *data;
struct llist_node_st *prev;
struct llist_node_st *next;
char data[0];
};
struct llist_head_st{
int size;
struct llist_node_st head;
};
LLIST *llist_creat(int size){
struct llist_head_st *new;
new = malloc(sizeof(*new));
if(new == NULL){
return NULL;
}
new->size = size;
//new->head.data = NULL;
new->head.prev = &new->head;
new->head.next = &new->head;
return new;
}
int llist_insert(LLIST *p, const void *data, unsigned char mode){
struct llist_head_st *ptr = p;
struct llist_node_st *newnode;
newnode = malloc(sizeof(*newnode) + ptr->size);
if(newnode == NULL){
return -1;
}
//newnode->data = malloc(ptr->size);
if(newnode->data == NULL){
return -2;
}
memcpy(newnode->data, data, ptr->size);
if(mode == LLIST_FORWARD){
newnode->prev = &ptr->head;
newnode->next = ptr->head.next;
}
else if(mode == LLIST_BACKWARD){
newnode->prev = ptr->head.prev;
newnode->next = &ptr->head;
}
else{
return -3;
}
newnode->next->prev = newnode;
newnode->prev->next = newnode;
return 0;
}
static struct llist_node_st *find_(LLIST *p, const void *key, llist_cmp *cmp){
struct llist_head_st *ptr = p;
struct llist_node_st *cur = NULL;
for(cur = ptr->head.next; cur != &ptr->head; cur = cur->next){
if(cmp(key, cur->data) == 0)
break;
}
return cur;
}
void *llist_find(LLIST *p, const void *key, llist_cmp *cmp){
struct llist_head_st *ptr = p;
struct llist_node_st *node;
node = find_(ptr, key, cmp);
if(node == &ptr->head){
return NULL;
}
return node->data;
}
int llist_delete(LLIST *p, const void *key, llist_cmp* cmp){
struct llist_head_st *ptr = p;
struct llist_node_st *node;
node = find_(ptr, key, cmp);
if(node == &ptr->head){
return -1;
}
node->prev->next = node->next;
node->next->prev = node->prev;
//free(node->data);
free(node);
return 0;
}
int llist_fetch(LLIST *p, const void *key, llist_cmp *cmp, void *data){
struct llist_head_st *ptr = p;
struct llist_node_st *node;
node = find_(ptr, key, cmp);
if(node == &ptr->head){
return -1;
}
node->prev->next = node->next;
node->next->prev = node->prev;
if(node->data != NULL){
//memset(data, 0, ptr->size);
memcpy(data, node->data, ptr->size);
}
//free(node->data);
free(node);
return 0;
}
void llist_travel(LLIST *p, llist_op *op){
struct llist_head_st *ptr = p;
struct llist_node_st *cur, *next;
for(cur = ptr->head.next; cur != &ptr->head; cur = cur->next){
op(cur->data);
}
}
void llist_destroy(LLIST *p){
struct llist_head_st *ptr = p;
struct llist_node_st *cur, *next;
for(cur = ptr->head.next; cur != &ptr->head; cur = next){
next = cur->next;
//free(cur->data);
free(cur);
}
free(ptr);
ptr = NULL;
}
结果测试仍然正确有效。