双向链表:
即可以从头遍历到尾部和从尾部遍历到头部的链表,每个结点包括两个链域:前驱指针域和后继指针域,所以比起单向链表,其可以在任意一个结点访问前后两个结点
关于双向链表的一个完整步骤为:
创建一个表头结构体,包括两个部分:指向表结点的指针,结点个数
创建表结点结构体,包括三部分:数据部分,指向前驱结点的指针,指向后继结点的指针。
//双向链表结点类型
typedef struct node
{
DATA_TYPE data; //数据域
struct node *ppre; //指向前驱结点的指针
struct node *pnext; //指向后继结点的指针
}DOU_NODE;
//描述双向链表属性的表头类型
typedef struct list
{
DOU_NODE *phead; //双向链表头结点地址
int clen; //当前链表结点个数
}DOU_LIST;
双向链表也包括以下步骤:创建-插入-删除-查找-修改-销毁-遍历
创建:
先用表头结构体定义一个表头函数,在函数中,继续用表头结构体定义一个指针P,指针大小为表头结构体的大小,同时让P的头结点地址指向空,个数初始化为0,最后将该指针返回。
DOU_LIST *create_dou_link()
{
DOU_LIST *plist = malloc(sizeof(DOU_LIST));
if (NULL == plist)
{
perror("fail malloc");
return NULL;
}
plist->phead = NULL;
plist->clen = 0;
return plist;
}
插入:
1.先用结点结构体定义一个结点函数,
函数中,用结点结构体定义一个指针P,大小为表头结构体的大小,P的前驱与后继指针都指向空,数据为输入函数的参数。
DOU_NODE *create_node(DATA_TYPE data)
{
DOU_NODE *pnode = malloc(sizeof(DOU_NODE));
if (NULL == pnode)
{
perror("fail malloc");
return NULL;
}
pnode->data = data;
pnode->pnext = NULL;
pnode->ppre = NULL;
return pnode;
}
2.将返回的结点与表头链接
先判断表头是否指向空值,如果指向,则将表头的指针赋值为结点,如果不指向空值(即不是空链表),则新结点的后端指向表头的头(即旧结点)(1),表头的头的前驱指向新结点(2),表头的头指向结点(3),clen加一:
代码如下:
int push_head_dou_link(DOU_LIST *plist, DOU_NODE *pnode)
{
if (NULL == plist || NULL == pnode)
{
return -1;
}
if (is_empty_dou_link(plist))
{
plist->phead = pnode;
}
else
{
pnode->pnext = plist->phead;
plist->phead->ppre = pnode;
plist->phead = pnode;
}
plist->clen++;
return 0;
}
删除:
用结点结构体创建一个指针,其值初始化为表头的头(即所有结点),表头的头指向新的指针的下一个结点(即空出一个结点),用free函数释放新指针,同时clen减一。
nt pop_head_dou_link(DOU_LIST *plist)
{
if (is_empty_dou_link(plist))
{
return 0;
}
DOU_NODE *ptmp = plist->phead;
plist->phead = ptmp->pnext;
if (NULL != plist->phead)
{
plist->phead->ppre = NULL;
}
free(ptmp);
plist->clen--;
return 0;
}
遍历、销毁:
遍历的步骤为:用结点的结构体定义一个结点指针,初始化值为表头的头,然后打印结点指针的data,使结点指针的值等于结点指针的后驱结点,然后循环以上步骤即完成了遍历(正向遍历)。打印结点指针的data,使结点指针的值等于结点指针的前驱结点,然后循环以上步骤即完成了反向遍历。
销毁即是只要表头不指向空,就一直进行删除操作,等表头指向空时,free表头即可。
查找、修改:
查找建立在遍历的基础上,首先定义一个结点指针,初始化值为表头的头,然后将输入的值(查找值)与结点指针的data对比,相同则返回该值,不同则使结点指针的值等于结点指针的后驱结点,并循环,直到相同为止。
修改步骤与查找相同,只不过是在找到后,把返回改为将结点指针的data修改为自己想改成的值。