2018.10.2 数据结构学习---双向链表的实现
/*
* 学习时间:2018-10-2
* 学习内容:数据结构之尾插法实现双向链表,以及链表的增删查改
* 学习人:田超
* QQ:770925351
* Email:770925351@qq.com
* 开发环境:Ubuntu 16.04 + CLion
* */
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef struct DLNode //定义循环链表结构体
{
int data;
struct DLNode *prior;
struct DLNode *next;
}DLNode;
void createDList(DLNode *&L,int a[],int n) //创建双向链表
{
DLNode *s,*r; //s用于新建节点,r用于跟踪L的尾端节点
int i; //for循环临时变量
L=(DLNode*)malloc(sizeof(DLNode)); //开辟循环链表头结点空间
L->prior=NULL; //初始化头结点前驱指针
L->next=NULL; //初始化头结点后继指针
r=L; //初始化r
for(i=0;i<n;i++)
{
s=(DLNode*)malloc(sizeof(DLNode)); //开辟新节点空间
s->data=a[i]; //将数值赋值给新节点的数据域
r->next=s; //将r指向的后继变成s
s->prior=r; //将s指向的前趋设置为r
r=s; //r移位,变成链表的最后一个节点
}
r->next=NULL; //此时r为最后一个节点,将它的后继指针变成NULL,创建链表结束
}
void travelNode(DLNode *L)
{
DLNode *p=L->next;
while(p!=NULL)
{
printf("data=%d\n",p->data);
p=p->next;
}
}
DLNode* findNode(DLNode *L,int x) //在双向链表中查找x元素
{
DLNode *p=L->next; //p为指向链表的指针,并初始化指向除头节点第一个节点
while(p!=NULL) //当p不为空时候,一直循环
{
if(p->data==x) //比较值的大小,如果相等,则找到,立即结束循环
break;
p=p->next; //没有找到,p指向下一个节点
}
return p; //返回p指针,如果找到则会返回节点的地址,如果找不到,说明p到了最后一个节点,最后一个节点的next指针是NULL
}
void insertNode_tail(DLNode *L,int x) //在双向链表中插入x元素,尾插法
{
DLNode *p,*s; //s用来新建节点,p用来寻找当前链表中最后一个节点
p=L->next; //初始化p节点
while(p&&p->next!=NULL) //循环找到L的最后一个节点,并赋值给p,在这里判断的逻辑是:p不能为空且p的后继指针不能为空,当为空时候结束循环,说明p是最后一个节点
{
p=p->next;
}
s=(DLNode*)malloc(sizeof(DLNode)); //新建节点
s->data=x; //将传进来的数据赋值给s
if(p==NULL) //如果此时链表为空,则插入的节点是第一个节点
{
s->prior=L; //s节点的前趋指向头结点
s->next=p; //s节点的后继指向p,也就是NULL
L->next=s; //此时s作为链表的第一个节点,也就是L->next
}
else
{
s->prior=p; //将s的前趋指针指向p
s->next=p->next; //将s的后继指针指向原先p的后继,因为p是最后一个节点,所以是NULL,如果说是中间的节点的话,就不是NULL
p->next=s; //将p的后继重新指向s
}
}
void insertNode_head(DLNode *L,int x) //在双向链表中插入x元素,头插法
{
DLNode *s; //s用来新建节点
s=(DLNode*)malloc(sizeof(DLNode)); //为s开辟空间
s->data=x; //将数据赋值给新建的节点s的data域
s->prior=L; //将s的前趋指针指向头结点
s->next=L->next; //将s的后继指针指向原先的第一个节点
if(L->next==NULL) //如果此时链表为空,那么s节点将
L->next=s;
else
{
L->next->prior=s; //将原先第一个节点的前趋指针指向s
L->next=s; //将头节点的next指针指向s
}
}
int deleteNode(DLNode *L,int x) //在双向链表中删除节点
{
DLNode *p=L->next; //让p指向除头节点外的第一个节点
while(p!=NULL) //循环至最后一个节点
{
if(p->data==x) //如果找到节点
{
if(p->next==NULL) //如果找到的是最后一个节点
{
p->prior->next = p->next; //将p节点前趋的后继指针指向NULL
free(p); //释放空间
}
else
{
p->prior->next = p->next; //将p节点前趋的后继指针指向p的后继
p->next->prior = p->prior; //将p节点后继的前趋指针指向p的前趋
free(p); //释放空间
}
return TRUE; //返回真
}
p=p->next; //没有找到将p指向下一个节点
}
return FALSE; //循环结束,没有找到,返回假
}
int main()
{
int a[5]={1,2,3,4,5};
int n=5;
DLNode *L;
createDList(L,a,n);
travelNode(L);
printf("\n");
deleteNode(L,5);
travelNode(L);
printf("\n");
insertNode_tail(L,6);
travelNode(L);
printf("\n");
insertNode_head(L,7);
travelNode(L);
printf("\n");
return 0;
}
