一个通用的双向链表
是在看《系统程序员成长计划》.(李先静).[PDF》第一章 编写一个通用的双向链表之后，觉得很有意义 便把自己的思路以及部分代码写成这篇博客
先说说要求：
所谓通用 ， 链表能够保存所有类型的值 不仅仅是 整型 char 型 字符串类型 还有结构体类型 ，
1.0 版本想法是 typedef ,重命名的方法很方便 但不是真正意义上的通用
2.0 版本想法是 void* ，空指针不指向任何类型的数据 ， 这是结构体的定义
typedef struct list_node
{
void * data;
struct list_node *pri;
struct list_node *next;
}db_list;
{
void * data;
struct list_node *pri;
struct list_node *next;
}db_list;
在使用 void * 的时候， 指针之间的赋值操作 需要稍稍多加注意，我老师讲过一个有趣的关于void* 的例子 ，void * 是大概念 ，int* 以及其他 都是小概念， 就像人 和男人 ，男人一定是人，但人并不一定是男人 ，还有女人 还有人妖。 任何int*以及其他指向特定格式的指针 都可以赋给 void * ，而且理所应当 不用强转，但是int *p=(int *)void *q 这里必须强转。大概念不能直接给小概念。
关于双向链表操作的函数 ，不是我这篇博客的重点，以下的 函数都比较容易，不做赘述。
db_list *init(); // 初始化链表
int getlenth(db_list *head); // 获得链表长度
bool insert(db_list* head, int pos, void *data); //插入元素
bool if_empty(db_list *head); //判空
bool delete_list(db_list *head, int pos, void *data); // 删除元素
int destory_list(db_list *head); // 销毁链表
int getlenth(db_list *head); // 获得链表长度
bool insert(db_list* head, int pos, void *data); //插入元素
bool if_empty(db_list *head); //判空
bool delete_list(db_list *head, int pos, void *data); // 删除元素
int destory_list(db_list *head); // 销毁链表
当我都编写完成之后， 该如何验证呢？ 作为一个初学者 我一般都是 再编写一个链表的打印函数 ，打印到终端上 自行检查 。
但是 现在是void * ，也就是 我的打印函数 应该怎么写呢 %d 还是 %c 还是别的什么 ，要做到通用，如果将每个类型的打印函数 都写一遍 ，这就代码重复率太高了，而且效率低 ， 并不是我想要的。 查阅了一些资料 都是使用回调函数， 这个我还没有去看的非常明白 ，等我弄懂回调函数 ，我会再重写一篇博客。
我使用的是前不久 学的 可变参函数，编写了一个 可以处理各种类型的 可变参打印函数， 以下是我的打印函数的代码：
int print_list(db_list *head,char *type)
{
if (if_empty(head))
{
printf("the linklist is empty!\n");
return 0;
}
db_list *p = head->next;
printf("head->");
while (p != NULL)
{
//printf("%d->", *(int *)(p->data)); //测试成功
myprintf(type, p->data);
//printf("%s->", (char *)(p->data));
printf("->");
p = p->next;
}
printf("NULL\n");
return 0;
}
{
if (if_empty(head))
{
printf("the linklist is empty!\n");
return 0;
}
db_list *p = head->next;
printf("head->");
while (p != NULL)
{
//printf("%d->", *(int *)(p->data)); //测试成功
myprintf(type, p->data);
//printf("%s->", (char *)(p->data));
printf("->");
p = p->next;
}
printf("NULL\n");
return 0;
}
void myprintf(char *fmt, ...)
{
va_list ap; //va_list是用于存放参数列表的数据结构。
int d;
double f;
char c;
char *s;
char flag;
va_start(ap, fmt); //根据fmt初始化可变参列表
while (*fmt)
{
flag = *fmt++;
if (flag != '%')
{
putchar(flag);
continue;
}
flag = *fmt++;
switch (flag)
{
case 's':
s = va_arg(ap, char*);//用于从参数列表中取出一个参数，其中的char *用于指定所取的参数的类型为字符串。每次调用va_arg后，参数列表ａｐ都会被更改，以使得下次调用时能得到下一个参数。
printf("%s", s);
break;
case 'd':
d = *(int *)va_arg(ap, int);
printf("%d", d);
break;
case 'f':
f = va_arg(ap, double);
printf("%f", f);
break;
case 'c':
c = *(char *)va_arg(ap, int);
printf("%c", c);
break;
default:
putchar(flag);
break;
{
va_list ap; //va_list是用于存放参数列表的数据结构。
int d;
double f;
char c;
char *s;
char flag;
va_start(ap, fmt); //根据fmt初始化可变参列表
while (*fmt)
{
flag = *fmt++;
if (flag != '%')
{
putchar(flag);
continue;
}
flag = *fmt++;
switch (flag)
{
case 's':
s = va_arg(ap, char*);//用于从参数列表中取出一个参数，其中的char *用于指定所取的参数的类型为字符串。每次调用va_arg后，参数列表ａｐ都会被更改，以使得下次调用时能得到下一个参数。
printf("%s", s);
break;
case 'd':
d = *(int *)va_arg(ap, int);
printf("%d", d);
break;
case 'f':
f = va_arg(ap, double);
printf("%f", f);
break;
case 'c':
c = *(char *)va_arg(ap, int);
printf("%c", c);
break;
default:
putchar(flag);
break;
}
}
va_end(ap); //清理列表
}
}
va_end(ap); //清理列表
}
初始，由程序员传给函数的其中一个参数是 链表里当前存放元素的类型。
即使是结构体类型 ，我要程序员在调用时通过参数告诉我 结构体的成员是什么类型。
这个程序也不是尽善尽美 ，以下是 我用 运行的结果：进行了插入、删除 销毁 以及几个函数：求链表中最大值，求链表所有元素的和，除了整型 也可以存放 字符串类型
并且将链表里的元素 进行了大写转换的函数：
最后附上一个 链表插入和删除的代码：
bool insert(db_list* head, int pos, void *data)
{
if (pos<1 || pos>getlenth(head) + 1)
{
printf("error pos!");
return false;
}
db_list *newnode = (db_list *)malloc(sizeof(db_list));
assert(newnode != NULL);
db_list *p = head;
if (pos == getlenth(head) + 1) //尾插
{
int i;
for (i = 1; i < pos; i++)
{
p = p->next;
}
newnode->data = data;
newnode->next = NULL;
newnode->pri = p;
p->next = newnode;
return true;
}
int i;
for (i = 0; i < pos; i++)
{
p = p->next;
}
newnode->data = data;
newnode->next = p;
newnode->pri = p->pri;
p->pri->next = newnode;
p->pri = newnode;
return true;
}
{
if (pos<1 || pos>getlenth(head) + 1)
{
printf("error pos!");
return false;
}
db_list *newnode = (db_list *)malloc(sizeof(db_list));
assert(newnode != NULL);
db_list *p = head;
if (pos == getlenth(head) + 1) //尾插
{
int i;
for (i = 1; i < pos; i++)
{
p = p->next;
}
newnode->data = data;
newnode->next = NULL;
newnode->pri = p;
p->next = newnode;
return true;
}
int i;
for (i = 0; i < pos; i++)
{
p = p->next;
}
newnode->data = data;
newnode->next = p;
newnode->pri = p->pri;
p->pri->next = newnode;
p->pri = newnode;
return true;
}
bool if_empty(db_list *head)
{
if (head->next == NULL)
return true;
else
return false;
}
{
if (head->next == NULL)
return true;
else
return false;
}
bool delete_list(db_list *head, int pos, void *data)
{
if (pos<1 || pos>getlenth(head))
{
printf("error pos!");
return false;
}
if (head->next == NULL)
{
// *data=NULL;
printf("the linklist is empty!\n");
return false;
}
db_list *p = head;
int i;
for (i = 0; i < pos; i++)
{
p = p->next;
}
data = p->data;
p->pri->next = p->next;
p->next->pri = p->pri;
free(p);
return true;
}
{
if (pos<1 || pos>getlenth(head))
{
printf("error pos!");
return false;
}
if (head->next == NULL)
{
// *data=NULL;
printf("the linklist is empty!\n");
return false;
}
db_list *p = head;
int i;
for (i = 0; i < pos; i++)
{
p = p->next;
}
data = p->data;
p->pri->next = p->next;
p->next->pri = p->pri;
free(p);
return true;
}
好的 总结和反思：
在编写代码当中 ，发现自己的动手能力还是不够好，写之前对于函数的边界条件 考虑的太少 ，写出来的代码效率也比较低 ，还可以更精简。