单链表:无法逆向检索,有时候不太方便
双链表:可进可退,存储密度低一点点
typedef struct DNode{ // 定义一个双链表
int data; // 数据域
struct DNode *prior, *next; // 前驱和后继节点
}DNode,*DLinkList;
初始化
// 初始化双链表(带头节点)
bool InitDLinkList(DLinkList &L) {
L = (DNode*)malloc(sizeof(DNode));
if (L==NULL) { // 内存不足,分配失败
return false;
}
L->prior = NULL; // 头节点的prior永远指向NULL;
L->next = NULL; // 头节点之后还没有节点
return true;
}
判断为空
// 判断双链表是否为空(带头节点)
bool Empty(DLinkList L) {
if (L->next==NULL) {
return true;
}
else {
return false;
}
}
插入节点
// 在p结点之后插入s节点
bool InsertNextDNode(DNode *p,DNode *s) {
if (p==NULL||s==NULL) { // 非法参数
return false;
}
s->next = p->next; // 将节点*s插入到节点*p之后
if (p->next!=NULL ) { // 如果p节点之后有后继节点
p->next->prior = s;
}
s->prior = p;
p->next = s;
return true;
}
删除节点
//删除p的后继节点
bool DeleteNextDNode(DNode *p) {
if (p==NULL) {
return false;
}
DNode *q = p->next; // 找到p的后继节点
if (q==NULL) {
return false; // p没有后继节点
}
p->next = q->next;
if (q->next!=NULL) { // q节点不是最后一个节点
q->next->prior = p;
}
free(q); // 释放q
return true;
}
销毁双链表
// 销毁双链表
void DestoryList(DLinkList &L) {
// 循环释放各个数据节点
while (L->next!=NULL) {
DeleteNextDNode(L);
}
free(L); // 释放头节点
L = NULL; // 头指针指向NULL;
}
遍历双链表
// 双链表的遍历
void PrintDLinkList(DNode *p) {
//DNode *p = L->next;
while (p->prior!=NULL)
{
printf("%d", p->prior);
p = p->prior;
}
}
创建双链表
// 双链表的创建
DNode * Create(DNode *L){
int x;
scanf("%d", &x);
while (x!=999){
DNode *s = (DNode*)malloc(sizeof(DNode));
s->data = x;
InsertNextDNode(L, s);
scanf("%d", &x);
}
return L;
}
版权声明:文章转载请注明来源,如有侵权请联系删除!