双向链表的实现
双向链表与之前的链表之间的区别是双向链表的每个节点既有指向后面节点的指针,又有指向前面节点的指针.
#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1
typedef int ElemType;
/*
待完成任务:实现双向链表定义,双向链表的插入及删除
在双向链表的结构体定义时,使用typedef定义*DuLinkList 是为了更方便的调用结构体内的变量,
并且在调用函数时只需要输入通过*DuLinkList定义的结构体即可直接传入地址进入函数,从而使题目简化.
*/
typedef struct DuLNode{
ElemType data;
struct DuLNode *Prior;
struct DuLNode *Next;
}DuLNode,*DuLinkList;
//双向链表的初始化
int InitDuList(DuLinkList &L){
L=(DuLinkList)malloc(sizeof(DuLinkList));
L->Prior=L;
L->Next=L;
if(L)
{
return OK;
}
else
{
return ERROR;
}
}
//双向链表的尾插法
void TailCreatDuList(DuLinkList &L){
int i,n;
DuLinkList Head=L,Tail=L;
printf("请输入需要插入的元素的数量:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
int a;
DuLinkList Insert =(DuLinkList)malloc(sizeof(DuLinkList));
scanf("%d",&a);
Insert->data=a;
Insert->Prior=Tail;
Tail->Next=Insert;
Insert->Next=Head;
Head->Prior=Insert;
Tail=Insert;
}
}
//双向链表的遍历
void TravelList(DuLinkList L)
{
int i=1;
DuLinkList Head=L,Travel=L->Next;
do
{
printf("第%d个元素的值为:%d\n",i,Travel->data);
i++;
Travel=Travel->Next;
}while(Travel!=Head);
}
//双向链表的删除
void DeleteList(DuLinkList &L)
{
int i;
DuLinkList Move=L;
printf("输入删除元素的位置");
scanf("%d",&i);
//通过for循环将Move节点移动到需要删除的节点位置
for(;i>0;i--)
{
Move=Move->Next;
}
/*
先将move前面节点的next指向move后面的节点
再将move节点的next的prior指向move前面的节点
以此来完成节点的删除
*/
Move->Prior->Next=Move->Next;
Move->Next->Prior=Move->Prior;
//删除Move节点
delete Move;
}
int main()
{
DuLinkList A;
InitDuList(A);
TailCreatDuList(A);
TravelList(A);
DeleteList(A);
TravelList(A)
return 0;
}
[参考文献]
数据结构c语言版