目录
定义
在单链表的每个结点中，在设置一个指向其前驱结点的指针域，最后一个结点又指向头结点，头节点的前驱指针指向最后一个结点，从而构成一个回路。
?双向链表的构建
typedef int LTDataType;
typedef struct ListNode
{
LTDataType data;
struct ListNode *next;
struct ListNode *prev;
}LtNode;初始化双链表
//初始化双链表
LtNode*ListInit()
{
LtNode* phead = (LtNode*)malloc(sizeof(LtNode));
phead->next = phead;
phead->prev = phead;
return phead;
}获得双链表节点函数?
//获得双链表节点函数
LtNode* BuyListNode(LTDataType x)
{
LtNode* newnode = (LtNode*)malloc(sizeof(LtNode));
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}双链表尾插建表
void ListPushBack(LtNode* phead)
{
assert(phead);
LTDataType x;
while (1)
{
scanf("%d", &x);
if (x == -1)
break;
ListNode* newnode = BuyListNode(x);
phead->prev->next = newnode;
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev = newnode;
}
}打印双链表
void ListPrint(LtNode* phead)
{
assert(phead);
LtNode* p = phead->next;
while (p!= phead)
{
printf("%d ", p->data);
p = p->next;
}
}查找双链表节点
LtNode* FindNode(LtNode*phead,int x)
{
LtNode* p = phead->next;
while (x>1 && p != phead)
{
p = p->next;
x--;
}
if (p == phead)//查找节点不存在
{
return NULL;
}
else
return p;
}双链表删除节点
void ListDel(LtNode*phead)
{
printf("您要删除第几个数据：");
int k;
scanf("%d",&k);
if (k == 1)
{
LtNode* p = phead->next;
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
return;
}
LtNode* p = FindNode(phead,k);
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
}双链表插入节点
void ListInsert(LtNode*phead)
{
printf("您要在第几个数据前插入：");
int k;
scanf("%d", &k);
printf("请输入你要插入的数据：");
int data;
scanf("%d", &data);
LtNode* newnode = BuyListNode(data);
if (k == 1)
{
LtNode* p = phead->next;
p->prev->next = newnode;
newnode->prev = p->prev;
newnode->next = p;
p->prev = newnode;
return;
}
LtNode* p = FindNode(phead, k);
p->prev->next = newnode;
newnode->prev = p->prev;
newnode->next = p;
p->prev = newnode;
}双链表销毁
void ListDistory(LtNode*phead)
{
LtNode* p = phead->next;
LtNode* q = NULL;
while (q!=phead)
{
q = p->next;
free(p);
p = q;
}
free(phead);
}