链表容器库论文

链表容器库摘要：容器库的设计以及实现，通过应用宏定义传递数据类型和void*指针指向数据域来实现容器库的任意类型的兼容从而达到容器库的需要， 对两种方式的实现形式进行举例说明；两种方法各有优劣，对两种方式做了分析、对比说明；最终选择void*指针指向数据域来实现整个容器的创建、插入、删除、清空等必要功能和一些更细小的功能；每种容器都有其缺点，由于 void*指针抹去原有数据类型，故该容器无法检测添加到同一个容器里的数据是否是同一个类型， 所以在使用时需要注意添加同一种类型的数据，以免出现程序崩溃。本文参照现有的容器库，利用基础编程语言编写实现线性表容器库，并验证其结果。关键字：关键词：容器库；宏定义；void*指针；任意类型兼容引言：线性表是最基本、最简单、也是最常用的一种数据结构。其中的数据元素之间的关系是一对一的关系，其大多数关系是：除第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。它具有均匀性和有序性的结构特点。均匀性描述的是：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。对于有序性来说，各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素(直接后继)。1数据类型兼容在程序设计的过程中，不同的数据类型有不同的使用方法。当应用一个double型数据存储一个数据，而当我们要就将该数据赋值给一个 int型时，数据会出现丢失，因此，对于不同的数据类型需要采用不同的处理方式， 线性也是这样。但是应该怎么来实现这个功能呢？这里采用以下两种方法：宏方法：采用宏方法，定义相关函数的使用方法。并将函数的参数设置为void类型。在使用该函数时，只须使用强制类型转换为需要的数据类型， 就能够正常使用。如在线性容器库中的表示：#defineLIST_POISON1((void*)x)void*方法：除去上面的宏方法，另外一种方法就是(void*)方法。在运用这种方法时，其设计的方式与“宏方法”大致相同，我们在不知道需要知道希望的数据的类型，只需要将方法实现即可。如：taticinlinevoidhlist_del(structhlist_node*n){__hlist_del(n);n->next=LIST_POISON1;n->pprev=LIST_POISON2;}以上就是常常需要用到的方法，在了解这两种方法后，编写程序时的数据类型的问题就可以解决了。2常见容器类库提供的方法一览表方法名称功能Creat()创建容器Insert()想容器中插入数据Remove()删除容器中的数据Length()查询容器中的数据个数Clear()清空容器Front()传回容器的第一个数据3现有方法存在的冋题和改进建议觉得没有问题就不要乱写4一个新的容器库实现实现的容器接口为了能更好的使用容器当然得给容器定义许多接口，以方便使用接口描述Insert()在给定位置之后插入新元素接口描述Next()取后继元素Erase()删除给定位置之后的元素Free()释放节点4.4容器使用演示代码：#inelude<stdio.h>#include"list.h"〃#inelude<string.h>voidprint_nod(void*data){Iman*x=(Iman*)data;if(x->name&&x->age&&x->xingbie){printf("姓名：");printStr(x->name);printf("年龄：％d",*(x->age));printf("性别：");printStr(x->xingbie);}printf("\n");}//释放节点数据的函数voidfree_nod(void*data){lman*m=(lman*)data;free(m->name);free(m->age);free(m->xingbie);}//节点比较函数intcompare.nod(void*iter1,void*iter2){Iman*x1=(Iman*)iter1;Iman*x2=(Iman*)iter2;return*(x1->age)-*(x2->age);}//节点匹配是否完全相同数据类型intcompare,nod12(void*iter1,void*iter2){lman*x1=(Iman*)iter1;Iman*x2=(Iman*)iter2;if(x1->name==x2->name&&x1->age==x2->age&&x1->xingbie==x2->xingbie)return1;}//链接字符串函数char*lstrcat(char*s1,char*s2){inti;char*x;x=malloc(sizeof(s1)+sizeof(s2));for(i=0;i<sizeof(s1);i++){x[i]=s1[i];}for(i=sizeof(s1);i<sizeof(s2)+sizeof(s1);i++){x[i]=s2[i-sizeof(s1)];}returnx;}//拷贝字符串函数char*lstrdup(char*s){char*x;inti;x=malloc(sizeof(s));for(i=0;i<sizeof(s);i++)x[i]=s[i];returnx;}//节点信息创建函数voiddataln(char*name,int*age,char*xb){printf("请输入姓名：");scanf("%s",name);printf("请输入年龄：");scanf("%d",age);printf("请输入性别：");scanf("%s",xb);}//主函数intmain(){llist*list;//定义一个链表引用list=llist_new();//新建一个链表void*data;//定义空类型指针，用于指向节点数据lman*man1;//定义一个节点数据类型的引用int*age;//定义一个节点数据char*xb;//一个节点数据char*lnam;//一个节点数据intn=2;//控制添加节点元素的个数//链表数据的添加while(1){if(n<1)break;n--;manl=malloc(sizeof(lman));age=malloc(sizeof(int));xb=malloc(sizeof(char)*6);Inam=malloc(80*sizeof(char));dataln(lnam,age,xb);man1->name=Inam;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",llist_length(list));〃删除元素dat=llist_first(list);//获取头节点，用于删除llist_remove(list,dat,compare_nod12,free_nod);

//遍历链表的全部数据printf（"\n打印链表：\n"）;llist_view(list,print_nod);printf("长度为:%d\n",llist_length(list));〃删除链表，并检验是否删除llist_distory(list,free_nod);printf("\n删除链表后长度为:%d",llist_length(list));llist_view(list,print_nod);//检验是否还能打印数据printf("\n******thanks*********H);printf("\n******thanks*********H);}#include<stdlib.h>typedefstructl_listllist;//创建一个链表llist*llist_new();//定为到头，返回链表的头void*llist_first(llist*list);//定为到尾，返回链表的尾void*llist_last(llist*list);〃定为到当前元素，返回链表的头void*llist_now(llist*list);//定为下一个，返回该元素void*llist_next(llist*list);〃修改当前元素的值voidllist_setNow(llist*list,void*data,void(*free_data)(void*s));//返回链表的元素个数intllist_length(llist*list);//向链表头插入元素intllist_insert_top(llist*list,void*data);//向链表尾插入元素intllist_insert_last(llist*list,void*data);〃删除链表中的某个元素intllist_remove(llist*list,void*data,int(*compare_nod)(void*,void*),void(*free_data)(void*s));//遍历链表，voidllist_view(llist*list,void(*view)(void*));//释放链表，需要传入元素的释放函数voidllist_distory(llist*list,void(*data_free)(void*s));//链表排序函数，llist*llist_upSort(llist*list,int(*compare_nod)(void*iter1,void