一个通用的双向链表
是在看《系统程序员成长计划》.(李先静).[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后,参数列表ap都会被更改,以使得下次调用时能得到下一个参数。
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后,参数列表ap都会被更改,以使得下次调用时能得到下一个参数。
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;
}
好的 总结和反思:
在编写代码当中 ,发现自己的动手能力还是不够好,写之前对于函数的边界条件 考虑的太少 ,写出来的代码效率也比较低 ,还可以更精简。