C++论文

链表容器库

摘要：

容器库的设计以及实现，通过应用宏定义传递数据类型和void*指针指向数据域来实现容器库的任意类型的兼容从而达到容器库的需要，对两种方式的实现形式进行举例说明；两种方法各有优劣，对两种方式做了分析、对比说明；最终选择void*指针指向数据域来实现整个容器的创建、插入、删除、清空等必要功能和一些更细小的功能；每种容器都有其缺点，由于void*指针抹去原有数据类型，故该容器无法检测添加到同一个容器里的数据是否是同一个类型，所以在使用时需要注意添加同一种类型的数据，以免出现程序崩溃。本文参照现有的容器库，利用基础编程语言编写实现线性表容器库，并验证其结果。 关键字：关键词：容器库；宏定义；void*指针；任意类型兼容 引言：

线性表是最基本、最简单、也是最常用的一种数据结构。其中的数据元素之间的关系是一对一的关系，其大多数关系是：除第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。它具有均匀性和有序性的结构特点。均匀性描述的是：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。对于有序性来说，各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素（直接后继）。 1 数据类型兼容

在程序设计的过程中，不同的数据类型有不同的使用方法。当应用一个double型数据存储一个数据，而当我们要就将该数据赋值给一个int型时，数据会出现丢失，因此，对于不同的数据类型需要采用不同的处理方式，线性也是这样。但是应该怎么来实现这个功能呢？这里采用以下两种方法：

宏方法：采用宏方法，定义相关函数的使用方法。并将函数的参数设置为void

类型。在使用该函数时，只须使用强制类型转换为需要的数据类型，就能够正常使用。如在线性容器库中的表示：

#define LIST_POISON1 ((void *) x)

void *方法：除去上面的宏方法，另外一种方法就是(void *)方法。在运用这

种方法时，其设计的方式与“宏方法”大致相同，我们在不知道需要知道希望的数据的类型，只需要将方法实现即可。如：

tatic inline void hlist_del(struct hlist_node *n) { }

以上就是常常需要用到的方法，在了解这两种方法后，编写程序时的数据类 型的问题就可以解决了。

2 常见容器类库提供的方法一览表

方法名称 Creat（） Insert（） Remove（） Length() Clear() Front（）

3 现有方法存在的问题和改进建议

觉得没有问题就不要乱写

4 一个新的容器库实现 实现的容器接口

为了能更好的使用容器当然得给容器定义许多接口，以方便使用。

接口 Insert()

__hlist_del(n);

n->next = LIST_POISON1; n->pprev = LIST_POISON2;

功能 创建容器 想容器中插入数据 删除容器中的数据 查询容器中的数据个数 清空容器 传回容器的第一个数据 描述 在给定位置之后插入新元素

接口 Next() Erase() Free()

4.4 容器使用演示

代码:

#include #include \"list.h\" //#include void print_nod(void *data){ lman *x = (lman *)data; }

//释放节点数据的函数 void free_nod(void *data){ }

//节点比较函数

描述 取后继元素 删除给定位置之后的元素 释放节点 if(x->name&&x->age&&x->xingbie){ }

printf(\"\\n\");

printf(\" 姓名：\"); printStr(x->name);

printf(\" 年龄：%d\printf(\" 性别：\"); printStr(x->xingbie);

lman *m = (lman *)data; free(m->name); free(m->age); free(m->xingbie);

int compare_nod(void *iter1,void *iter2){ }

//节点匹配是否完全相同数据类型 int compare_nod12(void *iter1,void *iter2){ }

//链接字符串函数

char *lstrcat(char *s1,char *s2){ }

//拷贝字符串函数 char *lstrdup(char* s){

lman *x1 = (lman *)iter1; lman *x2 = (lman *)iter2; return *(x1->age) - *(x2->age);

lman *x1 = (lman *)iter1; lman *x2 = (lman *)iter2; if(x1->name==x2->name&&

x1->age==x2->age&& x1->xingbie==x2->xingbie) return 1;

int i; char *x;

x = malloc(sizeof(s1)+sizeof(s2)); for(i=0;ifor(i=sizeof(s1);ix[i] = s2[i-sizeof(s1)]; x[i] = s1[i];

char *x;

}

int i;

x = malloc(sizeof(s)); for(i=0;ix[i] = s[i];

return x;

//节点信息创建函数

void dataIn(char *name ,int *age ,char *xb){ } //主函数 int main(){

printf(\" 请输入姓名：\"); scanf(\"%s\printf(\" 请输入年龄：\"); scanf(\"%d\printf(\" 请输入性别：\"); scanf(\"%s\

llist *list; // 定义一个链表引用 list = llist_new(); // 新建一个链表

void *data; // 定义空类型指针，用于指向节点数据 lman *man1; //定义一个节点数据类型的引用 int *age; // 定义一个节点数据 char *xb; // 一个节点数据 char *lnam;// 一个节点数据 int n=2; // 控制添加节点元素的个数 //链表数据的添加 while(1){

if(n<1) n--;

break;

man1 = malloc(sizeof(lman)); age = malloc(sizeof(int)); xb = malloc(sizeof(char)*6); lnam = malloc(80*sizeof(char)); dataIn(lnam,age,xb); man1->name = lnam; man1->age = age; man1->xingbie = xb;

data = man1; // 将空类型指针指向节点数据

// llist_insert_top(list,data); //头部添加

llist_insert_last(list,data); //尾部添加

}

void *dat; //临时接受数据变量 dat = llist_first(list); //获取链表头 printf(\"\\n 表头: \");

print_nod(dat); // 打印表头数据 dat = llist_last(list); //获取链表尾 printf(\"\\n 表尾: \");

print_nod(dat); // 打印表尾数据 dat = llist_now(list); // 获取当前值 printf(\"\\n 当前 \");

print_nod(dat); // 打印当前数据

//遍历链表的全部数据

printf(\"\\n 打印链表： \\n\"); llist_view(list,print_nod);

printf(\" 长度为 :%d \\n\//删除元素

dat = llist_first(list); //获取头节点，用于删除 llist_remove(list,dat,compare_nod12,free_nod);

//遍历链表的全部数据 printf(\"\\n 打印链表： \\n\"); llist_view(list,print_nod);

printf(\" 长度为 :%d \\n\//删除链表，并检验是否删除 llist_distory(list,free_nod);

printf(\"\\n 删除链表后长度为 :%d \

llist_view(list,print_nod); //检验是否还能打印数据

printf(\"\\n****** thanks！********* \"); }

#include typedef struct l_list llist; //创建一个链表 llist *llist_new();

//定为到头，返回链表的头 void *llist_first(llist *list); //定为到尾，返回链表的尾 void *llist_last(llist *list);

//定为到当前元素，返回链表的头 void *llist_now(llist *list); //定为下一个，返回该元素 void *llist_next(llist *list); //修改当前元素的值

void llist_setNow(llist *list,void *data,void (*free_data)(void *s)); //返回链表的元素个数 int llist_length(llist *list); //向链表头插入元素

int llist_insert_top(llist *list ,void *data); //向链表尾插入元素

int llist_insert_last(llist *list ,void *data);

//删除链表中的某个元素

int llist_remove(llist *list ,void *data,int (*compare_nod)(void *,void *),void (*free_data)(void *s));

//遍历链表，

void llist_view(llist *list,void (*view)(void *)); //释放链表,需要传入元素的释放函数

void llist_distory(llist *list,void (*data_free)(void *s)); //链表排序函数，

llist *llist_upSort(llist *list,int (*compare_nod)(void *iter1,void *iter2)); 5 小结

本次编写的链表容器，实现任意类型的兼容，链表可以存储任意类型的数据，达到了容器的多样性标准；该容器应用void*指针可以只想任意类型数据的功能来实现了任意类型的兼容；该容器实现了数据的插入，删除，遍历等接口； 但是由于是利用void*指针可以指向任意类型的数据的引用，实现了任意类型的兼容；在向链表中添加数据时是可以添加任意类型的数据，故当向容器中添加了不同类型的数据时，可能因为数据类型的不同意而导致程序的崩溃，由于数据类型被void*指针抹去所以无从判断。