双向链表_C语言

/* 以下循环单链表操作纯本人原创,转载请注明来源 */

/***********************************************************************************************************************

File Name       : 双向链表.c

Date Created  : 2019-10-22

Author             : 大竹竿

Description      : 实现双向链表各类操作

***********************************************************************************************************************/

 

/*带头节点的循环双向链表 */

 

/*

头节点;首节点前的节点(头节点永远指向首节点,头节点不存在左指针)

头指针:指向头节点的指针

首节点:链表第一个节点

尾节点:链表最后一个节点

*/

 

 

#include <stdio.h>

#include <stdlib.h>

 

#define true 1

#define false 0

#define num 3

typedef int datatype;

typedef int bool;

 

 

/* 定义节点结构体 */

typedef struct list {

    datatype data;        // 数据域

    struct list *Lnext;    // 左指针

    struct list *Rnext;   // 右指针

}List, *pList;

 

 

/* 函数声明 */

pList init();                             // 初始化

void build(pList h);                // 创建

int isEmpty(pList h);             // 判空   

int length(pList h);                // 测长

void print(pList h);                // 打印

 

/* 增 */    

void head_Insert(pList h);                // 头插     

void tail_Insert(pList h);                   // 尾插

void first_head_Value_Insert(pList h);    // 指定值头插(只插第一个)

void all_head_Value_Insert(pList h);      // 指定值头插(所有的)

void first_tail_Value_Insert(pList h);       // 指定值尾插(只插第一个)

void all_tail_Value_Insert(pList h);         // 指定值尾插(所有的)

void head_Order_Insert(pList h);           // 指定序号头插

void tail_Order_Insert(pList h);               // 指定序号尾插

   

/* 删 */

void head_Delete(pList h);                // 头删   

void tail_Delete(pList h);                   // 尾删    

void first_Value_Delete(pList h);      // 指定值删除(只删除第一个)

void all_Value_Delete(pList h);        // 指定值删除(删除所有的)

void order_Delete(pList h);              // 指定序号删除

   

/* 改 */

void first_Value_Revise(pList h);        // 指定值修改(只修改第一个)

void all_Value_Revise(pList h);          // 指定值修改(修改所有的)

void order_Revise(pList h);                // 指定序号修改

   

/* 查 */

void first_Value_Query(pList h);          // 指定值查询(只查询第一个)

void all_Value_Query(pList h);            // 指定值查询(查找所有的)

void order_Query(pList h);                  // 指定序号查询

   

void Destroy(pList h);                       // 销毁 

 

/* 函数定义 */

/* 初始化 */

pList init()

{

    pList h = (pList)malloc((sizeof(List)));    // 创建头结点

    h->Rnext = NULL;        // 初始化时,头节点右指针为空

   

    return h;

}

 

/* 创建 */

void build(pList h)

{

    pList p = h;    // 声明一个移动指针

   

    int i, arr[num];

    printf("请输入%d个数:", num);

    for (i = 0; i < num; i++) {

        scanf("%d", &arr[i]);

    }

    

    for (i = 0; i < num; i++) {

        pList node = (pList)malloc(sizeof(List));    // 创建节点

        node->data = arr[i];        // 节点数据域

        node->Lnext = p;             // 新节点左指针指向上一个节点

        node->Rnext = NULL;            // 新节点右指针为空

        p->Rnext = node;            // 上一个节点指向下一个节点(对于首节点而言,为头结点指向首节点)

        p = p->Rnext;                // 指针后移

    }

   

    return;

}

 

/* 判空 */

bool isEmpty(pList h)

{

    if (h->Rnext == NULL) {

        return true;

    }

    return false;

}

 

/* 测长 */

int length(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return 0;

    }

   

    int len = 0;

    pList p = h;

    while (p->Rnext != NULL) {

        len++;

        p = p->Rnext;

    }

    printf("当前链表长度为:%d\n", len);

   

    return len;

}

 

/* 打印 */

void print(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

    

    printf("当前链表为:");

    pList p = h->Rnext;   

    while (p != NULL) {

        printf("%d ", p->data);

        p = p->Rnext;

    }

    printf("\n\n");

   

    return;

}

 

/* 头插 */

void head_Insert(pList h)

{   

    printf("请输入头插的值:");

    datatype ele;

    scanf("%d", &ele);

   

    pList node = (pList)malloc(sizeof(List));

    node->data = ele;

    node->Lnext = h;

    node->Rnext = h->Rnext;

    h->Rnext = node;

   

    return;

 }

 

/* 尾插 */

void tail_Insert(pList h)

{

    printf("请输入尾插的值:");

    datatype ele;

    scanf("%d", &ele);

   

    pList p = h;        // 移动指针

    while (p->Rnext != NULL) {        // 找到尾节点

        p = p->Rnext;

    }

   

    pList node = (pList)malloc(sizeof(List));

    node->data = ele;

    node->Lnext = p;

    node->Rnext = NULL;

    p->Rnext = node;

   

    return;

 }

 

/* 指定值头插(只插第一个) */

void first_head_Value_Insert(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要在哪个数值前插入(只插第一个):");

    datatype ele;

    scanf("%d", &ele);

   

    printf("请输入需要插入的值;");

    datatype val;

    scanf("%d", &val);

   

    pList p = h;     // 移动指针

    while (p->Rnext != NULL){

        if (p->Rnext->data == ele) {  // 找到指定值的前驱

            break;

        }

        p = p->Rnext;

    }

   

    if (p->Rnext == NULL) {

        printf("输入的值%d不存在!\n", ele);

        return;

    }

   

    pList node = (pList)malloc(sizeof(List));

    node->data = val;

    node->Lnext = p;

    node->Rnext = p->Rnext;

    p->Rnext->Lnext = node;

    p->Rnext = node;

   

    return;

}

 

/* 指定值头插(所有的) */

void all_head_Value_Insert(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要在哪个数值前插入(所有的):");

    datatype ele;

    scanf("%d", &ele);

   

    printf("请输入需要插入的值;");

    datatype val;

    scanf("%d", &val);

   

    pList p = h;

    bool flag = true;

    while (p->Rnext != NULL) {            // 找到指定值的前驱

        if (p->Rnext->data == ele) {

            flag = false;

            pList node = (pList)malloc(sizeof(List));

            node->data = val;

            node->Lnext = p;

            node->Rnext = p->Rnext;

            p->Rnext->Lnext = node;

            p->Rnext = node;

            p = p->Rnext->Rnext;

            continue;

        }

        p = p->Rnext;

    }

    if (flag) {

        printf("输入的值%d不存在!\n", ele);

        return;

    }

    return;

}

 

/* 指定值尾插(只插第一个) */

void first_tail_Value_Insert(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要在哪个值后插入(只插第一个):");

    datatype ele;

    scanf("%d", &ele);

   

    printf("请输入需要插入的值:");

    datatype val;

    scanf("%d", &val);

   

    pList p = h->Rnext;        // 移动指针

    while (p != NULL) {            // 找到指定值节点

        if (p->data == ele) {

            break;

        }

        p = p->Rnext;

    }

   

    if (p == NULL) {

        printf("输入的值%d不存在!\n", ele);

        return;

    }

   

    pList node = (pList)malloc(sizeof(List));

    node->data = val;

    node->Lnext = p;

    node->Rnext = p->Rnext;

    p->Rnext->Lnext = node;

    p->Rnext = node;

   

    return;

}

 

/* 指定值尾插(所有的) */

void all_tail_Value_Insert(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要在哪个值后插入(所有的):");

    datatype ele;

    scanf("%d", &ele);

   

    printf("请输入需要插入的值:");

    datatype val;

    scanf("%d", &val);

   

    pList p = h->Rnext;

    bool flag = true;

    while (p != NULL) {                // 找到指定值节点

        if (p->data == ele) {

            flag = false;

            pList node = (pList)malloc(sizeof(List));

            node->data = val;

            node->Lnext = p;

            node->Rnext = p->Rnext;

            p->Rnext->Lnext = node;

            p->Rnext = node;

            p = p->Rnext->Rnext;

            continue;

        }

        p = p->Rnext;

    }

   

    if (flag) {

        printf("输入的值%d不存在!\n", ele);

        return;

    }

    return;

}

 

/* 指定序号头插 */

void head_Order_Insert(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入在第几个元素前插入:");

    int n;

    scanf("%d", &n);

   

    if ((n < 1) || (n > length(h))) {

        printf("输入的序号非法!\n");

        return;

    }

   

    printf("请输入需要插入的值:");

    datatype ele;

    scanf("%d", &ele);

   

    pList p = h;

    int i = 1;

    while (i != n) {        // 找到序号节点的前驱节点

        p = p->Rnext;

        i++;

    }

    pList node = (pList)malloc(sizeof(List));

    node->data = ele;

    node->Lnext = p;

    node->Rnext = p->Rnext;

    p->Rnext->Lnext = node;

    p->Rnext = node;

   

    return;

 }

 

/* 指定序号尾插 */

void tail_Order_Insert(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入在第几个元素后插入:");

    int n;

    scanf("%d", &n);

   

    if ((n < 1) || (n > length(h))) {

        printf("输入的序号非法!\n");

        return;

    }

   

    printf("请输入需要插入的值:");

    datatype ele;

    scanf("%d", &ele);

   

    pList p = h;

    int i = 0;

    while (i != n) {        // 找到序号节点

        p = p->Rnext;

        i++;

    }

    pList node = (pList)malloc(sizeof(List));

    node->data = ele;

    node->Lnext = p;

    node->Rnext = p->Rnext;

    p->Rnext->Lnext = node;

    p->Rnext = node;

   

    return;

}

 

/* 头删 */

void head_Delete(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("头删...\n");

    pList p = h->Rnext;

    p->Rnext->Lnext = h;

    h->Rnext = p->Rnext;

    free(p);

   

    return;

 }

 

/* 尾删 */

void tail_Delete(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("尾删...\n");

    pList p = h;

    while (p->Rnext->Rnext != NULL) {        // 找到尾节点的前驱

        p = p->Rnext;

    }

    free(p->Rnext);

    p->Rnext = NULL;

   

    return;

}

 

/* 指定值删除(删除第一个) */

void first_Value_Delete(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要删除的值(只删第一个):");

    datatype ele;

    scanf("%d", &ele);

   

    pList p = h, p1;

    while (p->Rnext != NULL) {        // 找到指定值的前驱

        if (p->Rnext->data == ele) {

            break;

        }

        p = p->Rnext;

    }

   

    if (p->Rnext == NULL) {

        printf("输入的值%d不存在!\n", ele);

        return;

    }

    p1 = p->Rnext;

    p1->Rnext->Lnext = p;

    p->Rnext = p1->Rnext;

    free(p1);

   

    return;

 }

 

/* 指定值删除(删除所有的) */

void all_Value_Delete(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要删除的值(删除所有):");

    datatype ele;

    scanf("%d", &ele);

 

    pList p = h, p1;

    bool flag = true;

    while (p->Rnext != NULL) {            // 找到指定值的前驱

        if (p->Rnext->data == ele) {

            flag = false;

            p1 = p->Rnext;

            p1->Rnext->Lnext = p;

            p->Rnext = p1->Rnext;

            free(p1);

            continue;

        }   

        p = p->Rnext;

    }

   

    if (flag) {

        printf("输入的值%d不存在!\n", ele);

        return;

    }

   

    return;

 }

 

/* 指定序号删除 */

void order_Delete(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要删除第几个元素:");

    int n;

    scanf("%d", &n);

   

    if ((n < 1) || (n > length(h))) {

        printf("输入的序号非法!\n");

        return;

    }

   

    pList p = h, p1;

    int i = 1;

    while (i != n) {        // 找到序号节点的前驱

        p = p->Rnext;

        i++;

    }

    p1 = p->Rnext;

    p1->Rnext->Lnext = p;

    p->Rnext = p1->Rnext;

    free(p1);

   

    return;

}

 

/* 指定值修改(只改第一个) */

void first_Value_Revise(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要修改的值(修改第一个):");

    datatype ele;

    scanf("%d", &ele);

   

    printf("请输入改为哪个值:");

    datatype val;

    scanf("%d", &val);

   

    pList p = h;

    while (p->Rnext != NULL) {            // 找到指定值的前驱

        if (p->Rnext->data == ele) {

            p->Rnext->data = val;

            return;

        }

        p = p->Rnext;

    }

   

    if (p->Rnext == NULL) {

        printf("输入的值%d不存在!\n", ele);

        return;

    }

   

    return;

}

 

/* 指定值修改(修改所有) */

void all_Value_Revise(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要修改的值(修改所有的):");

    datatype ele;

    scanf("%d", &ele);

   

    printf("请输入改为哪个值:");

    datatype val;

    scanf("%d", &val);

   

    pList p = h;

    bool flag = true;

    while (p->Rnext != NULL) {        // 找到指定值的前驱

        if (p->Rnext->data == ele) {

            flag =false;

            p->Rnext->data = val;

        }

        p = p->Rnext;

    }

   

    if (flag) {

        printf("输入的值%d不存在!\n", ele);

        return;

    }

   

    return;

 }

 

/* 指定序号修改 */

void order_Revise(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要修改第几个元素:");

    int n;

    scanf("%d", &n);

   

    if ((n < 1) || (n > length(h))) {

        printf("输入的序号非法!\n");

        return;

    }

   

    printf("请输入改为哪个值:");

    datatype val;

    scanf("%d", &val);

   

    pList p = h;

    int i = 0;

    while (i != n) {        // 找到序号节点

        p = p->Rnext;

        i++;

    }

    p->data = val;

   

    return;

}

 

/* 指定值查找(查找第一个) */

void first_Value_Query(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要查找的值(只查第一个):");

    datatype ele;

    scanf("%d", &ele);

   

    pList p = h;

    int n = 0;

    while (p->Rnext != NULL) {            // 找到指定值的前驱

        n++;

        if (p->Rnext->data == ele) {

            printf("元素%d在第%d号位置上!\n", ele, n);

            return;   

        }

        p = p->Rnext;

    }

   

    if (p->Rnext == NULL) {

        printf("输入的值%d不存在!\n", ele);

        return;

    }

   

    return;

 }

 

/* 指定值查找(查找所有) */

void all_Value_Query(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要查询的值(查找所有的):");

    datatype ele;

    scanf("%d", &ele);

   

    printf("%d所处的位置分别为:", ele);

    pList p = h;

    int i = 0;

    bool flag = true;

    while (p->Rnext != NULL) {            // 找到指定值的前驱

        i++;

        if (p->Rnext->data == ele) {

            printf("%d ", i);

            flag = false;

        }

        p = p->Rnext;

    }

   

    if (flag) {

        printf("输入的值%d不存在!\n", ele);

        return;

    }

    else {

        printf("\n");

    }

    return;

}

 

/* 指定序号查询 */

void order_Query(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

   

    printf("请输入需要查询第几个位置的元素:");

    int n;

    scanf("%d", &n);

   

    if ((n < 1) || (n > length(h))) {

        printf("输入的序号非法!\n");

        return;

    }

   

    pList p = h;

    int i = 0;

    while (i != n) {        // 找到序号节点

        p = p->Rnext;

        i++;

    }

    printf("第%d号位置的元素为:%d\n", n, p->data);

    return;

 }

 

/* 销毁 */

void Destroy(pList h)

{

    if (isEmpty(h)) {

        printf("链表为空!\n");

        return;

    }

    

    printf("销毁链表...\n");

    pList p = h, p1;

    while (!(isEmpty(h))) {

        p1 = p->Rnext;

        p->Rnext = p->Rnext->Rnext;

        free(p1);

    }

   

    return;

 }

 

int main()

{

    /* 初始化 */

    pList head = init();     // 创建头结点

   

    /* 创建 */

    build(head);

    length(head);

    print(head);

   

    /* 头插 */

    head_Insert(head);     

    length(head);

    print(head);

   

    /* 尾插 */

    tail_Insert(head);

    length(head);

    print(head);

   

    /* 指定值头插(只插第一个) */

    first_head_Value_Insert(head);

    length(head);

    print(head);

   

    /* 指定值头插(所有的) */

    all_head_Value_Insert(head);

    length(head);

    print(head);

   

    /* 指定值尾插(只插第一个) */

    first_tail_Value_Insert(head);

    length(head);

    print(head);

   

    /* 指定值尾插(所有的) */

    all_tail_Value_Insert(head);

    length(head);

    print(head);

   

    /* 指定序号头插 */

    head_Order_Insert(head);

    length(head);

    print(head);

   

    /* 指定序号尾插 */

    tail_Order_Insert(head);

    length(head);

    print(head);

   

    /* 头删 */

    head_Delete(head);

    length(head);

    print(head);

   

    /* 尾删 */

    tail_Delete(head);

    length(head);

    print(head);

   

    /* 指定值删除(删除第一个) */

    first_Value_Delete(head);

    length(head);

    print(head);

   

    /* 指定值删除(删除所有的) */

    all_Value_Delete(head);

    length(head);

    print(head);

   

    /* 指定序号删除 */

    order_Delete(head);

    length(head);

    print(head);

   

    /* 指定值修改(只修改第一个) */

    first_Value_Revise(head);

    length(head);

    print(head);

   

    /* 指定值修改(修改所有) */

    all_Value_Revise(head);

    length(head);

    print(head);

   

    /* 指定序号修改 */

    order_Revise(head);

    length(head);

    print(head);

   

    /* 指定值查询(只查第一个) */

    first_Value_Query(head);

    length(head);

    print(head);

   

    /* 指定值查询(查找所有的) */

    all_Value_Query(head);

    length(head);

    print(head);

   

    /* 指定序号查询 */

    order_Query(head);

    length(head);

    print(head);

   

    /* 销毁 */

    Destroy(head);

    length(head);

    print(head);

    return 0;

}

上一篇:VUE ele,emt-ui定时器不生效原因


下一篇:自动化测试po模式是什么?自动化测试po分层如何实现?-附详细源码