一、双向链表的描述
在单链表中，查找直接后继结点的执行时间为O(1)，而查找直接前驱的执行时间为O(n)。为克服单链表这种单向性的缺点，可以用双向链表。
在双向链表的结点中有两个指针域，一个指向直接后继，另一个指向直接前驱。
二、双向链表的存储结构
typedef char ElemType[20]; //重定义数据域的数据类型
typedef struct LNode //定义双向链表存储结构
{
ElemType data;
struct LNode *next;
struct LNode *prev;
}*DoubleLink;三、双向链表的操作
2.1 双向链表结点创建
DoubleLink Request_space() //在堆区申请一个结点空间
{
DoubleLink node=(DoubleLink)malloc(sizeof(struct LNode));
if(NULL==node)
return NULL;
strcpy(node->data,"");
node->next=node->prev=NULL;
return node;
}2.2 双向链表遍历
int Output(DoubleLink L_list) //实现输出
{
if(NULL==L_list)
return -1;
DoubleLink p=L_list;
do
{
printf("%s ",p->data);
p=p->next;
}while(p!=NULL);
puts("");
return 0;
}2.3 双向链表头插
DoubleLink insert_head(DoubleLink L_list,ElemType value) //实现头插
{
DoubleLink node=Request_space();
if(NULL==node)
return L_list;
strcpy(node->data,value);
if(NULL!=L_list)
{
node->next=L_list;
L_list->prev=node;
}
L_list=node;
return L_list;
}2.4 双向链表尾插
DoubleLink insert_rear(DoubleLink L_list,ElemType value) //实现尾插
{
DoubleLink node=Request_space();
strcpy(node->data,value);
if(NULL==L_list)
L_list=node;
else
{
DoubleLink rear=L_list;
while(rear->next!=NULL)
rear=rear->next;
rear->next=node;
node->prev=rear;
}
return L_list;
}2.5 双向链表头删
DoubleLink delete_head(DoubleLink L_list) //实现头删
{
if(NULL==L_list)
return NULL;
if(L_list->next==NULL)
{
free(L_list);
L_list=NULL;
}
else
{
DoubleLink p=L_list->next;
strcpy(L_list->data,p->data);
L_list->next=p->next;
if(p->next!=NULL)
p->next->prev=L_list;
free(p);
p=NULL;
}
return L_list;
}
2.6 双向链表尾删
DoubleLink delete_rear(DoubleLink L_list) //实现尾删
{
if(NULL==L_list)
return NULL;
if(L_list->next==NULL)
{
free(L_list);
L_list=NULL;
}
else
{
DoubleLink rear=L_list;
while(rear->next!=NULL)
rear=rear->next;
rear->prev->next=NULL;
free(rear);
rear=NULL;
}
return L_list;
}2.7 计算双向链表长度
int len_Llist(DoubleLink L_list) //计算双向链表长度
{
int count=0;
if(NULL==L_list)
return -1;
while(L_list!=NULL)
{
count++;
L_list=L_list->next;
}
return count;
}2.8 双向链表逆置
DoubleLink rev_list(DoubleLink L_list) //双向链表逆置
{
if(NULL==L_list||L_list->next==NULL)
return L_list;
int len=len_Llist(L_list)-1;
DoubleLink p=L_list->next;
L_list->next=NULL;
L_list->prev=L_list->next;
for(int i=0;i<len;i++)
{
DoubleLink q=p;
p=p->next;
q->prev=q->next;
q->next=L_list;
L_list=q;
}
return L_list;
}四、多文件编辑实现双向链表操作
头文件 head.h
#ifndef __HEAD_H__
#define __HEAD_H__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef char ElemType[20]; //重定义数据域的数据类型
typedef struct LNode //定义双向链表存储结构
{
ElemType data;
struct LNode *next;
struct LNode *prev;
}*DoubleLink;
DoubleLink Request_space(); //在堆区申请一个结点空间
int Output(DoubleLink L_list); //实现输出
DoubleLink insert_head(DoubleLink L_list,ElemType value); //实现头插
DoubleLink insert_rear(DoubleLink L_list,ElemType value); //实现尾插
DoubleLink delete_head(DoubleLink L_list); //实现头删
DoubleLink delete_rear(DoubleLink L_list); //实现尾删
DoubleLink rev_list(DoubleLink L_list); //双向链表逆置
#endif自定义函数 fun.c
#include "head.h"
DoubleLink Request_space() //在堆区申请一个结点空间
{
DoubleLink node=(DoubleLink)malloc(sizeof(struct LNode));
if(NULL==node)
return NULL;
strcpy(node->data,"");
node->next=node->prev=NULL;
return node;
}
int Output(DoubleLink L_list) //实现输出
{
if(NULL==L_list)
return -1;
DoubleLink p=L_list;
do
{
printf("%s ",p->data);
p=p->next;
}while(p!=NULL);
puts("");
return 0;
}
DoubleLink insert_head(DoubleLink L_list,ElemType value) //实现头插
{
DoubleLink node=Request_space();
if(NULL==node)
return L_list;
strcpy(node->data,value);
if(NULL!=L_list)
{
node->next=L_list;
L_list->prev=node;
}
L_list=node;
return L_list;
}
DoubleLink insert_rear(DoubleLink L_list,ElemType value) //实现尾插
{
DoubleLink node=Request_space();
strcpy(node->data,value);
if(NULL==L_list)
L_list=node;
else
{
DoubleLink rear=L_list;
while(rear->next!=NULL)
rear=rear->next;
rear->next=node;
node->prev=rear;
}
return L_list;
}
DoubleLink delete_head(DoubleLink L_list) //实现头删
{
if(NULL==L_list)
return NULL;
if(L_list->next==NULL)
{
free(L_list);
L_list=NULL;
}
else
{
DoubleLink p=L_list->next;
strcpy(L_list->data,p->data);
L_list->next=p->next;
if(p->next!=NULL)
p->next->prev=L_list;
free(p);
p=NULL;
}
return L_list;
}
DoubleLink delete_rear(DoubleLink L_list) //实现尾删
{
if(NULL==L_list)
return NULL;
if(L_list->next==NULL)
{
free(L_list);
L_list=NULL;
}
else
{
DoubleLink rear=L_list;
while(rear->next!=NULL)
rear=rear->next;
rear->prev->next=NULL;
free(rear);
rear=NULL;
}
return L_list;
}
int len_Llist(DoubleLink L_list) //计算双向链表长度
{
int count=0;
if(NULL==L_list)
return -1;
while(L_list!=NULL)
{
count++;
L_list=L_list->next;
}
return count;
}
DoubleLink rev_list(DoubleLink L_list) //双向链表逆置
{
if(NULL==L_list||L_list->next==NULL)
return L_list;
int len=len_Llist(L_list)-1;
DoubleLink p=L_list->next;
L_list->next=NULL;
for(int i=0;i<len;i++)
{
DoubleLink q=p;
p=p->next;
q->prev=q->next;
q->next=L_list;
L_list=q;
}
return L_list;
}主函数 main.c
#include "head.h"
int main(int argc, const char *argv[])
{
DoubleLink L_list=NULL; //定义头指针变量,注意定义时一定要指向NULL
int n; //定义循环输入次数
ElemType value; //定义数据域元素
int seat; //定义元素位置
printf("please enter n:");
scanf("%d",&n);
for(int i=0;i<n;i++) //头插
{
printf("please enter a value:");
scanf("%s",value);
L_list=insert_head(L_list,value);
}
for(int i=0;i<n;i++) //尾插
{
printf("please enter a value:");
scanf("%s",value);
L_list=insert_rear(L_list,value);
}
L_list=delete_head(L_list); //头删
L_list=delete_rear(L_list); //尾删
Output(L_list);
L_list=rev_list(L_list); //双向链表逆置
Output(L_list);
return 0;
}
