【 数据结构（C语言）】线性表——双向链表和双向循环链表
双向链表：每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点
1.双向链表的基本实现（带头尾指针）
/**
** 2017.11.1
** Ahthor:799
** 双向链表
**
***/
#include <bits/stdc++.h>
using namespace std;
#define ElemType int
#define Status int
#define ERROR -1
#define OK 1
typedef struct LNode
{
ElemType data;
struct LNode *prev;
struct LNode *next;
};
typedef struct DLinkList
{
int len;
LNode *head,*tail;
};
void InitLinkList (DLinkList &L)
{
L.len = 0;
L.head = (LNode * )malloc(sizeof(LNode));
L.tail = (LNode * )malloc(sizeof(LNode));
L.head->next = L.tail;
L.head->prev = NULL;
L.tail->prev = L.head;
L.tail->next = NULL;
return ;
}
int GetLengthLinkList(DLinkList &L)
{
LNode *index = L.head->next;
int ct = 0;
while (index != L.tail)
{
ct++;
index = index->next;
}
return ct;
}
LNode* GetLinkListElem(DLinkList &L,int i)
{
LNode *index = L.head;
int ct = 0;
while (ct < i)
{
ct++;
index = index->next;
}
return index;
}
Status InsertLinkList(DLinkList &L,int i,ElemType data)///* 前插入
{
if (i <0 || i > GetLengthLinkList(L) + 1) return ERROR;
LNode *pointer = GetLinkListElem(L,i);
LNode *newnode = (LNode *)malloc(sizeof(LNode)) ;
newnode->data = data;
newnode->prev = pointer->prev;
pointer->prev->next = newnode;
newnode->next = pointer;
pointer->prev = newnode;
L.len++;
return OK;
}
Status DeteleLinkListByPos(DLinkList &L,int i,ElemType &e)/// 按位删除
{
LNode *pointer = GetLinkListElem(L,i);
e = pointer->data;
pointer->prev->next = pointer->next;
pointer->next->prev = pointer->prev;
return OK;
}
Status DeteleLinkListByVal(DLinkList &L,ElemType e)/// 按位删除
{
LNode *pointer = L.head->next;
for (;pointer != L.tail; pointer = pointer->next)
{
if (pointer->data == e)
{
pointer->prev->next = pointer->next;
pointer->next->prev = pointer->prev;
}
}
return OK;
}
void TrverseLinkList(DLinkList &L)
{
LNode *index = L.head->next;;
for (; index != L.tail; index = index->next )
{
cout<<index->data<<" ";
}
cout<<endl;
}
int main()
{
int n;
cin>>n;
DLinkList *Dk = (DLinkList *) malloc(sizeof(DLinkList));
InitLinkList(*Dk);
for (int i=1; i <= n; i++)
{
int tmp;
cin>>tmp;
InsertLinkList(*Dk,i,tmp);
}
TrverseLinkList(*Dk);
int pos,val;
cin>>val;
DeteleLinkListByVal(*Dk,val);
TrverseLinkList(*Dk);
}
2.双向循环链表（带头结点）
/**
** 2017.11.1
** Ahthor:799
** 循环双向链表
**
***/
#include <bits/stdc++.h>
using namespace std;
#define ElemType int
#define Status int
#define ERROR -1
#define OK 1
typedef struct LNode
{
ElemType data;
struct LNode *prev;
struct LNode *next;
};
typedef struct DLinkList
{
int len;
LNode *head;
};
void InitLinkList (DLinkList &L)
{
L.len = 0;
L.head = (LNode * )malloc(sizeof(LNode));
L.head->next = L.head;
L.head->prev = L.head;
return ;
}
int GetLengthLinkList(DLinkList &L)
{
LNode *index = L.head->next;
int ct = 0;
while (index != L.head)
{
ct++;
index = index->next;
}
return ct;
}
LNode* GetLinkListElem(DLinkList &L,int i)
{
LNode *index = L.head;
int ct = 0;
while (ct < i)
{
ct++;
index = index->next;
}
return index;
}
Status InsertLinkList(DLinkList &L,int i,ElemType data)///* 前插入
{
if (i <0 || i > GetLengthLinkList(L) + 1) return ERROR;
LNode *pointer = GetLinkListElem(L,i);
LNode *newnode = (LNode *)malloc(sizeof(LNode)) ;
newnode->data = data;
newnode->prev = pointer->prev;
pointer->prev->next = newnode;
newnode->next = pointer;
pointer->prev = newnode;
L.len++;
return OK;
}
Status DeteleLinkListByPos(DLinkList &L,int i,ElemType &e)/// 按位删除
{
LNode *pointer = GetLinkListElem(L,i);
e = pointer->data;
pointer->prev->next = pointer->next;
pointer->next->prev = pointer->prev;
free(pointer);
return OK;
}
Status DeteleLinkListByVal(DLinkList &L,ElemType e)/// 按位删除
{
LNode *pointer = L.head->next;
for (;pointer != L.head; pointer = pointer->next)
{
if (pointer->data == e)
{
pointer->prev->next = pointer->next;
pointer->next->prev = pointer->prev;
free(pointer);
}
}
return OK;
}
void TrverseLinkList(DLinkList &L)
{
LNode *index = L.head->next;;
for (; index != L.head; index = index->next )
{
cout<<index->data<<" ";
}
cout<<endl;
}
int main()
{
int n;
cin>>n;
DLinkList *Dk = (DLinkList *) malloc(sizeof(DLinkList));
InitLinkList(*Dk);
for (int i=1; i <= n; i++)
{
int tmp;
cin>>tmp;
InsertLinkList(*Dk,i,tmp);
}
TrverseLinkList(*Dk);
int pos,val;
cin>>val;
DeteleLinkListByVal(*Dk,val);
TrverseLinkList(*Dk);
}