(11)王道数据结构-双链表的基本操作

双链表基本操作

#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)