当前位置: 首页 > >

双向链表的C语言实现与基本操作(一)

发布时间:

本文的主要目录:


一、双向链表的基本概念


二、双向链表的简单实现




一、双向链表的基本概念


双向链表和上一节博客中的单向链表相比,只是在结点元素中多了一个指向前一个结点元素的指针。为什么需要双向链表,因为在实际的工程项目当中,有时候为了提高单向链表访问结点元素的效率,需要在链表结点元素中增加一个指向前驱的指针,提高对链表元素结点的访问速度。


一个基本的双向链表结点的C语言表示如下:



/* 双向链表结点元素 */
struct dList{
struct dList *next;
struct dList *prev;
};



二、双向链表的基本实现


? ? ? ?在上一节单向链表实现的基础上来实现这个双向链表。


1、表示链表的结构体定义如下:



/* 定义一个表示链表的结构体指针 */
struct list {
int id; /* 标识这个元素方便查找 */
char data[20]; /* 链表中包含的元素 */
struct list *next; /* 指向下一个结点的指针 */
struct list *prev; /* 指向前一个结点的指针 */
};

2、因为是双向链表所以定义了两个全局链表结点,一个用来指向链表头部,一个用来指向链表尾部



/* 定义一个链表头部 */
static struct list *list_head = NULL;
/* 定义一个链表尾部 */
static struct list *list_tail = NULL;

3、头结点容易找到,但尾结点相对难一点,所以实现了一个找到尾结点元素的方法,并把尾结点的指针赋值给前面定义的全局尾部结点指针list_tail。



/** 通过链表的头部找到链表的尾部
* head : 链表的头部的地址
* 返回值 : 返回链表尾部的地址
*/
static struct list *find_list_tail(struct list **head)
{
struct list *temp = *head;
struct list *p = NULL;

/* 判断链表是否为空 */
if(NULL == temp) /* 为空 */
{
return NULL;
}
else /* 不为空 */
{
while(temp)
{
p = temp;
temp = temp->next;
if(NULL == temp) return p;
}
}

return NULL;
}

这个函数的思路是通过头结点找到尾结点,首先判断链表是否为空,不为空时对链表进行遍历,返回下一个结点为空的上一个结点,该结点即使结点的尾部。(注意:在使用这个函数获得尾结点指针时,必须在每次插入结点元素后重新获得,因为链表尾部结点是会随着结点的插入而发生变化)


4、仿照上一节单向链表遍历元素的方法,现在实现从尾部开始遍历结点元素的方法,把结点元素的内容倒序打印出来,原理和之前函数的实现类似。



/** 遍历一个链表,打印链表中每个元素所包含的数据
* tail : 表示要遍历的链表的尾部的指针
*/
static void list_print_tail(struct list **tail)
{
struct list *temp;

temp = *tail;

printf("list information form tail:
");
while(temp)
{
printf(" list %d : %s
", temp->id, temp->data);
temp = temp->prev;
}
}

5、在main函数中实现如下功能:动态分配是个元素并把元素加入到链表当中,先从链表头部打印结点元素数据,再从尾部打印结点元素数据。



/* 主函数,程序的入口 */
int main(int argc, char *argv[])
{
int i = 0;
struct list *lists = NULL;

/* 分配10个元素 */
lists = malloc(sizeof(struct list) * 10);
if(NULL == lists)
{
printf("malloc error!
");
return -1;
}

/* 将分配的10个元素依次填充数据并加入到链表当中 */
for(i = 0; i < 10; i++)
{
lists[i].id = list_id++;
sprintf(lists[i].data, "TECH-PRO - %d", i);

list_add(&list_head, &lists[i]);
}

/* 从头部遍历链表,把链表中每个元素的信息都打印出来 */
list_print_head(&list_head);

/* 找到链表尾部 */
list_tail = find_list_tail(&list_head);

/* 从尾部遍历链表,把链表中每个元素的信息都打印出来 */
list_print_tail(&list_tail);

return 0;
}

编译运行结果如下所示:







对于双向链表的基本操作(插入元素,删除元素,修改元素,查看元素)放在下一篇博客中来讲。




附录:本篇文章实现的完整的双向链表的基本实现的代码如下所示:



/* 包含的头文件 */
#include
#include
#include

/* 定义一个表示链表的结构体指针 */
struct list {
int id; /* 标识这个元素方便查找 */
char data[20]; /* 链表中包含的元素 */
struct list *next; /* 指向下一个结点的指针 */
struct list *prev; /* 指向前一个结点的指针 */
};

/* 定义一个链表头部 */
static struct list *list_head = NULL;

/* 定义一个链表尾部 */
static struct list *list_tail = NULL;

/* 为了保证每一个链表元素的id不同,特意把id定义成一个全局静态变量 */
static int list_id = 0;

/** 将指定元素插入到聊表尾部
* head : 表示要插入元素的链表的头部的地址
* list : 表示要插入到链表中的元素
*/
static void list_add(struct list **head, struct list *list)
{
struct list *temp;

/* 判断链表是否为空 */
if(NULL == *head)
{
/* 为空 */
*head = list;
(*head)->next = NULL;
(*head)->prev = NULL;
}
else
{
/* 不为空 */
temp = *head;
while(temp)
{
/* 将新结点插入到链表尾部 */
if(NULL == temp->next)
{
temp->next = list;
list->next = NULL;
list->prev = temp;
return;
}
temp = temp->next;
}
}
}

/** 通过链表的头部找到链表的尾部
* head : 链表的头部的地址
* 返回值 : 返回链表尾部的地址
*/
static struct list *find_list_tail(struct list **head)
{
struct list *temp = *head;
struct list *p = NULL;

/* 判断链表是否为空 */
if(NULL == temp) /* 为空 */
{
return NULL;
}
else /* 不为空 */
{
while(temp)
{
p = temp;
temp = temp->next;
if(NULL == temp) return p;
}
}

return NULL;
}

/** 遍历一个链表,打印链表中每个元素所包含的数据
* head : 表示要遍历的链表的头部的指针
*/
static void list_print_head(struct list **head)
{
struct list *temp;

temp = *head;

printf("list information form head:
");
while(temp)
{
printf(" list %d : %s
", temp->id, temp->data);
temp = temp->next;
}
}

/** 遍历一个链表,打印链表中每个元素所包含的数据
* tail : 表示要遍历的链表的尾部的指针
*/
static void list_print_tail(struct list **tail)
{
struct list *temp;

temp = *tail;

printf("list information form tail:
");
while(temp)
{
printf(" list %d : %s
", temp->id, temp->data);
temp = temp->prev;
}
}


/* 主函数,程序的入口 */
int main(int argc, char *argv[])
{
int i = 0;
struct list *lists = NULL;

/* 分配10个元素 */
lists = malloc(sizeof(struct list) * 10);
if(NULL == lists)
{
printf("malloc error!
");
return -1;
}

/* 将分配的10个元素依次填充数据并加入到链表当中 */
for(i = 0; i < 10; i++)
{
lists[i].id = list_id++;
sprintf(lists[i].data, "TECH-PRO - %d", i);

list_add(&list_head, &lists[i]);
}

/* 从头部遍历链表,把链表中每个元素的信息都打印出来 */
list_print_head(&list_head);

/* 找到链表尾部 */
list_tail = find_list_tail(&list_head);

/* 从尾部遍历链表,把链表中每个元素的信息都打印出来 */
list_print_tail(&list_tail);

return 0;
}












友情链接: