双链表基本操作
#include<stdio.h>
#include<stdlib.h>
typedef struct DNode { //定义双链表节点类型
int data; //数据域
struct DNode *prior, *next; //前驱和后继指针
}DNode, *DLinkList;
DNode* InitDLinkList(DLinkList &L);
bool InsertNextDNode(DNode *p, DNode *s);
bool DListInsert(DNode *head, int i, int e);
DNode* GetElem(DNode *head, int i);
bool DeleteNextDNode(DNode *p);
void DestoryList(DLinkList &L);
void ShowList(DNode *head);
DNode * DelData(DNode * head, int data);
int main(void) {
//创建头结点
DNode *head = NULL;
DLinkList List;
//初始化链表
head = InitDLinkList(List);
DListInsert(head, 1, 11);
DListInsert(head, 2, 22);
DListInsert(head, 3, 33);
DListInsert(head, 4, 44);
DListInsert(head, 5, 55);
DListInsert(head, 6, 66);
DListInsert(head, 7, 77);
DListInsert(head, 8, 88);
//获取元素,判断是否插入成功
int num = -1;
num = GetElem(head, 8)->data;
printf("最后一个元素是%d\n", num);
ShowList(head);
//DestoryList(List);
DelData(head, 66);
ShowList(head);
return 0;
}
//初始化双链表
DNode* InitDLinkList(DLinkList &head) {
head = (DNode *)malloc(sizeof(DNode)); //分配一个头结点
if (head == NULL) { //内存不足,分配失败
return NULL;
}
head->prior = NULL; //头结点prior永远指向NULL
head->next = NULL; //头结点之后暂时没有节点
return head; //返回头结点
}
//在p节点之后插入s节点
bool InsertNextDNode(DNode *p, DNode *s) {
if (p==NULL || s==NULL) {
return false;
}
s->next = p->next;
if (p->next != NULL) {
p->next->prior = s;
}
s->prior = p;
p->next = s;
return true;
}
//链表中插入数据
bool DListInsert(DNode *head, int i, int e) {
//声明一个指向首元节点的指针,方便后期向链表中添加新创建的节点
DNode * list = head;
DNode * body = (DNode*)malloc(sizeof(DNode));
//创建新的节点并初始化
if (i == 1) {
//头结点赋值
head->prior = NULL;
head->next = NULL;
head->data = e;
} else {
int j = 2;
while ( j < i ) {
j++;
list = list->next;
}
body->prior = NULL;
body->next = NULL;
body->data = e;
//新节点与链表最后一个节点建立关系
InsertNextDNode(list,body);
}
return true; //p后插入新元素e
}
//按位查找,返回第i个元素(带头结点)
DNode* GetElem(DNode *head, int i) {
if (i < 0) {
return NULL;
}
DNode *p; //指针p指向当前扫描到的节点
int j = 1; //当前p指向的是第几个节点
p = head; //L指向头结点,头结点是第0个节点(不存数据)
while (p!=NULL && j < i) { //循环找到第i个节点
p = p->next;
j++;
}
return p;
}
//删除p结点的后继节点
bool DeleteNextDNode(DNode *p) {
if (p == NULL) {
return false;
}
DNode *q = p->next; //找到p的后继节点q
if (q == NULL) { //p没有后继节点
return false;
}
p->next = q->next;
if (q->next != NULL) { //q节点不是最后一个节点
q->next->prior = p;
}
free(q);
return true;
}
//清空双链表
void DestoryList(DLinkList &L) {
//循环释放各个数据节点
while (L->next != NULL) {
DestoryList(L);
}
free(L); //释放头结点
L = NULL; //头指针指向NULL
}
//双链表的遍历
void ShowList(DNode *head) {
printf("后向遍历:\n");
DNode * temp = head;
while (temp != NULL) {
/*如果该节点无后继节点,说明此节点是链表的最后一个节点*/
if (temp->next == NULL) {
printf("%d\n",temp->data);
} else {
printf("%d->",temp->data);
}
temp = temp->next;
}
/*
后向遍历:
while (p != NULL) {
p = p->next;
}
前向遍历:
while (p != NULL) {
p = p->prior;
}
前向遍历(忽略头结点):
while (p != NULL) {
p = p->prior;
}
*/
}
//删除结点的函数,data为要删除结点的数据域的值
DNode * DelData(DNode * head, int data) {
DNode * temp = head;
//遍历链表
while (temp != NULL) {
//判断当前结点中数据域和data是否相等,若相等,摘除该结点
if (temp->data == data) {
temp->prior->next = temp->next;
temp->next->prior = temp->prior;
free(temp);
return head;
}
temp=temp->next;
}
printf("链表中无该数据元素");
return head;
}
注意事项
双向链表不可随机读取,按位查找、按值查找都只能用遍历的方式实现。时间复杂度为O(n)