[数据结构与算法] 线性表中的头插法双链表的学习

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 线性表中的头插法双链表的学习 -> 正文阅读

[数据结构与算法]线性表中的头插法双链表的学习

#include <stdio.h>
#include <malloc.h>

/**
 * 线性表中的头插法双链表的学习
*/

/**
 * 人类
 */
typedef struct Person {
    int age;
    char *name;
} Person, P;

/**
 * 节点
 * 一个date
 * 一个指针
 *
 * Node节点类型
 *
 * *L头指针
 */
typedef struct LNode {
    P date;
    struct LNode *prior,*next;
} LNode, *HeadL;



HeadL createChars();

void printChars(HeadL pNode);

void createCharsHeadInsert(HeadL pNode, Person person);

void deleteNodeByIndex(HeadL pNode, int i);

void queryNodeByIndex(HeadL pNode, int i);

void queryNodeIndexByValue(HeadL pNode, int i);

void insertByIndex(HeadL pNode, int i, Person person);

void querySize(HeadL pNode);

void createCharsEndInsert(HeadL pNode, Person person);

void queryParentNodeByIndex(HeadL pNode, int i);

void insertBeforeByIndex(HeadL pNode, int i, Person person);

void checkCharByEnd(HeadL pNode);

void checkChar(HeadL pNode);

int main() {

    Person p1 = {1, "李一"};
    Person p2 = {2, "李二"};
    Person p3 = {3, "李三"};
    Person p4 = {4, "李四"};
    Person p5 = {5, "李五"};
    Person p6 = {6, "李六"};

//    创建链表
    HeadL headL = createChars();
    HeadL end = (LNode *) malloc(sizeof(LNode));
//    尾指针
    end->next=headL;

//    printf("\n尾部法插入链表\n");
//    createCharsEndInsert(end, p1);
//    createCharsEndInsert(end, p2);
//    createCharsEndInsert(end, p3);
//    createCharsEndInsert(end, p4);
//    createCharsEndInsert(end, p5);
//    createCharsEndInsert(end, p6);

    printf("\n头部法插入链表\n");
    createCharsHeadInsert(headL, p1);
    createCharsHeadInsert(headL, p2);
    createCharsHeadInsert(headL, p3);
    createCharsHeadInsert(headL, p4);
    createCharsHeadInsert(headL, p5);
    createCharsHeadInsert(headL, p6);


    printf("\n打印链表\n");
    printChars(headL);

    printf("\n删除指定位结点%d\n", 2);
    deleteNodeByIndex(headL, 2);


    printf("\n打印链表\n");
    printChars(headL);

    printf("\n查找结点%d\n", 2);
    queryNodeByIndex(headL, 2);

    printf("\n打印链表\n");
    printChars(headL);


    printf("\n查找结点%d的父节点\n", 2);
    queryParentNodeByIndex(headL, 2);

    printf("\n打印链表\n");
    printChars(headL);

    printf("\n查找结点%d的父节点\n", 5);
    queryParentNodeByIndex(headL, 5);

    printf("\n打印链表\n");
    printChars(headL);


    printf("\n查找值的位置-%s\n", "年龄是4岁的位置");
    queryNodeIndexByValue(headL, 4);

    printf("\n打印链表\n");
    printChars(headL);

    Person p7 = {7, "插班生王武"};
    printf("\n插入结点%d,%s,年龄%d岁\n",3,p7.name,p7.age);
    insertByIndex(headL,3,p7);

    printf("\n打印链表\n");
    printChars(headL);

    printf("\n查找结点%d的父节点\n", 3);
    queryParentNodeByIndex(headL, 3);

    printf("\n打印链表\n");
    printChars(headL);


    printf("\n打印链表长度\n");
    querySize(headL);

//    printf("\n通过尾部指针-检测链表是否存在断链\n");
//    checkCharByEnd(end);

    printf("\n通过正反序-检测链表是否存在断链\n");
    checkChar(headL);

    return 0;
}

void checkChar(HeadL pNode) {
    if(pNode->next==NULL){
        printf("链表为空\n");
        return;
    }
    int temp = 0;
    while (pNode->next){
        pNode = pNode->next;
    }
    while (pNode->prior){
        temp++;
        printf("倒数第%d个结点--%s--%d岁\n", temp, pNode->date.name, pNode->date.age);
        pNode = pNode->prior;
    }
    printf("表长-有效节点%d个\n",temp);

}

void checkCharByEnd(HeadL pNode) {
    if(pNode->next==NULL){
        printf("链表为空\n");
        return;
    }
    int temp = 0;
    while (pNode->next->prior){
        temp++;
        printf("倒数第%d个结点--%s--%d岁\n", temp, pNode->next->date.name, pNode->next->date.age);
        pNode->next = pNode->next->prior;
    }
    printf("表长-有效节点%d个\n",temp);

}

void insertBeforeByIndex(HeadL pNode, int i, Person person) {
    if(pNode->next==NULL&&i>=1){
        printf("链表为空/或者插入位置有误\n");
        return;
    }

    //创建一个节点
    HeadL insert = (LNode*)malloc(sizeof (LNode));
    insert->date=person;
    insert->next=NULL;

    int temp = 0;
    while (pNode->next){
        temp++;
        if(temp==i){
            insert->next = pNode->next;
            pNode->next->prior=insert;
            pNode->next=insert;
            insert->prior=pNode;
            printf("成功插入%s,年龄%d岁\n",person.name,person.age);
            return;
        }
        pNode=pNode->next;
    }
    pNode->next=insert;
    printf("成功插入%s,年龄%d岁\n",person.name,person.age);

}

void queryParentNodeByIndex(HeadL pNode, int i) {
    if (pNode->next == NULL) {
        printf("链表为空");
        return;
    }
    int temp = 0;
    while (pNode->next) {
        temp++;
        if (i == temp) {
            printf("第%d个结点的父节点--%s--%d岁", temp, pNode->next->prior->date.name, pNode->next->prior->date.age);
            return;
        }
        pNode = pNode->next;
    }
}

void querySize(HeadL pNode) {
    if(pNode->next==NULL){
        printf("链表为空\n");
        return;
    }
    int temp = 0;
    while (pNode->next){
        temp++;
        pNode = pNode->next;
    }
    printf("表长-有效节点%d个\n",temp);

}

void insertByIndex(HeadL pNode, int i, Person person) {
    if(pNode->next==NULL&&i>=1){
        printf("链表为空/或者插入位置有误\n");
        return;
    }

    //创建一个节点
    HeadL insert = (LNode*)malloc(sizeof (LNode));
    insert->date=person;
    insert->next=NULL;

    int temp = 0;
    while (pNode->next){
        temp++;
        if(temp==i){
            insert->next = pNode->next;
            pNode->next->prior=insert;
            pNode->next=insert;
            insert->prior=pNode;
            printf("成功插入%s,年龄%d岁\n",person.name,person.age);
            return;
        }
        pNode=pNode->next;
    }
    pNode->next=insert;
    printf("成功插入%s,年龄%d岁\n",person.name,person.age);
}

void queryNodeIndexByValue(HeadL pNode, int i) {
    if(pNode->next==NULL){
        printf("链表为空\n");
        return;
    }
    int temp = 0;
    while (pNode->next){
        temp++;
        if(pNode->next->date.age==i){
            printf("第%d个结点--%s--%d岁\n",temp,pNode->next->date.name,i);
            return;
        }
        pNode = pNode->next;
    }
    printf("没有在该链表找到年龄为%d的人\n",i);
}

void queryNodeByIndex(HeadL pNode, int i) {
    if (pNode->next == NULL) {
        printf("链表为空");
        return;
    }
    int temp = 0;
    while (pNode->next) {
        temp++;
        if (i == temp) {
            printf("第%d个结点--%s--%d岁", temp, pNode->next->date.name, pNode->next->date.age);
            return;
        }
        pNode = pNode->next;
    }

}

void deleteNodeByIndex(HeadL pNode, int i) {
    if (pNode->next == NULL) {
        printf("链表为空");
        return;
    }
//    当前结点序号
    int temp = 0;
    while (pNode->next) {
        temp++;
        if (temp == i) {
            HeadL temp = pNode->next->next;
            free(pNode->next);
            pNode->next = temp;
            temp->prior=pNode;
            printf("删除成功");
            return;
        }
        pNode = pNode->next;
    }
    printf("删除失败");

}

void createCharsHeadInsert(HeadL pNode, Person person) {
//    printf("需要插入的结点\n");
    LNode *insertNode = (LNode *) malloc(sizeof(LNode));
    insertNode->date = person;
    insertNode->next = NULL;


//    printf("判断是否有数据\n");
    HeadL body = pNode->next;
    if (body == NULL) {
//        printf("空链表数据添加\n");
        pNode->next = insertNode;
        insertNode->prior=pNode;
        printf("成功插入%s,年龄%d岁\n",person.name,person.age);
        return;
    }
    insertNode->next = body;
    body->prior=insertNode;
    pNode->next = insertNode;
    insertNode->prior=pNode;
    printf("成功插入%s,年龄%d岁\n",person.name,person.age);
}


void createCharsEndInsert(HeadL end, Person person) {
//    printf("需要插入的结点\n");
    LNode *insertNode = (LNode *) malloc(sizeof(LNode));
    insertNode->date = person;
    insertNode->next = NULL;

    end->next->next=insertNode;
    insertNode->prior=end->next;
    end->next=insertNode;
    printf("成功插入%s,年龄%d岁\n",person.name,person.age);


}


void printChars(HeadL headL) {
    HeadL headL1 = headL->next;
    int i = 0;
    while (headL1 != NULL) {
        printf("第%d个结点--%s--%d岁\n", ++i, headL1->date.name, headL1->date.age);
        headL1 = headL1->next;
    }
    if (i == 0) {
        printf("链表为空\n");
    }

}

HeadL createChars() {
    HeadL L = (HeadL) malloc(sizeof(LNode));
    L->next = NULL;
    L->prior = NULL;
    return L;
}

I:\20220321-day\cmake-build-debug\20220321_day.exe

头部法插入链表
成功插入李一,年龄1岁
成功插入李二,年龄2岁
成功插入李三,年龄3岁
成功插入李四,年龄4岁
成功插入李五,年龄5岁
成功插入李六,年龄6岁

打印链表
第1个结点--李六--6岁
第2个结点--李五--5岁
第3个结点--李四--4岁
第4个结点--李三--3岁
第5个结点--李二--2岁
第6个结点--李一--1岁

删除指定位结点2
删除成功
打印链表
第1个结点--李六--6岁
第2个结点--李四--4岁
第3个结点--李三--3岁
第4个结点--李二--2岁
第5个结点--李一--1岁

查找结点2
第2个结点--李四--4岁
打印链表
第1个结点--李六--6岁
第2个结点--李四--4岁
第3个结点--李三--3岁
第4个结点--李二--2岁
第5个结点--李一--1岁

查找结点2的父节点
第2个结点的父节点--李六--6岁
打印链表
第1个结点--李六--6岁
第2个结点--李四--4岁
第3个结点--李三--3岁
第4个结点--李二--2岁
第5个结点--李一--1岁

查找结点5的父节点
第5个结点的父节点--李二--2岁
打印链表
第1个结点--李六--6岁
第2个结点--李四--4岁
第3个结点--李三--3岁
第4个结点--李二--2岁
第5个结点--李一--1岁

查找值的位置-年龄是4岁的位置
第2个结点--李四--4岁

打印链表
第1个结点--李六--6岁
第2个结点--李四--4岁
第3个结点--李三--3岁
第4个结点--李二--2岁
第5个结点--李一--1岁

插入结点3,插班生王武,年龄7岁
成功插入插班生王武,年龄7岁

打印链表
第1个结点--李六--6岁
第2个结点--李四--4岁
第3个结点--插班生王武--7岁
第4个结点--李三--3岁
第5个结点--李二--2岁
第6个结点--李一--1岁

查找结点3的父节点
第3个结点的父节点--李四--4岁
打印链表
第1个结点--李六--6岁
第2个结点--李四--4岁
第3个结点--插班生王武--7岁
第4个结点--李三--3岁
第5个结点--李二--2岁
第6个结点--李一--1岁

打印链表长度
表长-有效节点6个

通过正反序-检测链表是否存在断链
倒数第1个结点--李一--1岁
倒数第2个结点--李二--2岁
倒数第3个结点--李三--3岁
倒数第4个结点--插班生王武--7岁
倒数第5个结点--李四--4岁
倒数第6个结点--李六--6岁
表长-有效节点6个

Process finished with exit code 0