首页 > 其他分享 >5、循环双链表

5、循环双链表

时间：2024-09-16 15:47:22浏览次数：10  
标签：last list next prior 循环 printf 双链 first 

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

typedef int ElemType;

typedef struct Node{
    ElemType data;
    struct Node* prior;
    struct Node* next; 
}Node,*PNode;

typedef struct DCList{
    PNode first;
    PNode last;
    int size;
}DCList;

Node* malloc_node(ElemType e){
    Node* node = (Node*)malloc(sizeof(Node));
    assert(node != NULL);
    node->next = node->prior = NULL;
    node->data = e;
    return node;
}

//初始化循环链表
void init_DCList(DCList* list){
    Node* node = malloc_node(-1);
    list->first = list->last = node;
    list->first->prior = list->last;
    list->last->next = list->first;
    list->size = 0;
} 

//尾插
void push_back(DCList* list,ElemType e){
    Node* s = malloc_node(e);
    
    s->next = list->last->next;
    s->next->prior = s;
    s->prior = list->last;
    list->last->next = s;
    list->last = s;
    list->size++;
} 

//头插
void push_front(DCList* list,ElemType e){
    Node* s = malloc_node(e);
    
    s->next = list->first->next;
    s->prior = list->first;
    list->first->next = s;
    s->next->prior = s;
    if(list->first == list->last){
        list->last = s;
    }
    list->size++;
}
//打印链表
void show_list(DCList* list){
    Node* p = list->first->next;
    while(p != list->first){
        printf("%d<=>",p->data);
        p = p->next;
    }
    printf("NULL .\n");
} 

//删除末尾节点
void pop_back(DCList* list){
    if(list->size == 0){
        printf("当前链表没有元素,不可删除.\n");
        return;
    }
    Node* p = list->last;
    list->last = list->last->prior;
    
    p->next->prior = p->prior;
    p->prior->next = p->next;
    free(p);
    list->size--;    
}

//删除首节点
void pop_front(DCList* list){
    if(list->size == 0){
        printf("当前链表没有元素,不可删除.\n");
        return;
    }
    Node* p = list->first->next;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    if(p == list->last){
        list->last = list->first;
    } 
    free(p);
    list->size--;
}

//插入节点[默认链表已升序排序]
void insert_val(DCList* list,ElemType e){
    Node* s = malloc_node(e);
    Node* p = list->first;
    while(p->next != list->first && p->next->data < s->data)
        p = p->next;
    s->next = p->next;
    s->prior = p;
    s->next->prior = s;
    s->prior->next = s;
    //处理插入最后一个位置的情况
    if(p == list->last){
        list->last = s;
    } 
    list->size++; 
}

//查找节点
Node* find(DCList* list,ElemType key){
    Node* p = list->first->next;
    while(p != list->first){
        if(p->data == key){
            return p;
        }
        p = p->next;
    }
    return NULL;
} 

//返回链表长度
int length(DCList* list) {
    return list->size;
}

//按值删除
void delete_val(DCList* list,ElemType e){
    if(list->size == 0){
        return;
    }
    Node* p = find(list,e);
    if(p == NULL){
        printf("删除节点不存在,不可删除. \n");
        return;
    }
    p->next->prior = p->prior;
    p->prior->next = p->next;
    if(p == list->last){
        list->last = p->prior;
    }
    free(p);
    list->size--;
}

//排序
void sort(DCList* list){
    if(list->size <= 1){
        return;
    }
    Node* s = list->first->next;
    Node* q = s->next;
    
    list->last->next = NULL;
    list->last = s;
    list->last->next = list->first;
    list->first->prior = list->last;
    
    while(q !=     NULL){
        s = q;
        q = q->next;
        Node* p = list->first;
        while(p->next != list->first && p->next->data < s->data){
            p = p->next; 
        }
        s->next = p->next;
        s->prior = p;
        s->next->prior = s;
        s->prior->next = s;
        if(p == list->last){
            list->last = s;
        }
    }
}

//逆置链表
void reverse(DCList* list){
    if(list->size <= 1)
        return;
    Node* s = list->first->next;
    Node* q = s->next;
    
    list->last->next = NULL;
    list->last = s;
    list->last->next = list->first;
    list->first->prior = list->last;
    
    while(q != NULL){
        s = q;
        q = q->next;
        
        s->next = list->first->next;
        s->prior = list->first;
        s->next->prior = s;
        s->prior->next = s;
    } 
}

//清空链表
void clear(DCList* list){
    if(list->size == 0){
        return;
    }
    Node* p = list->first->next;
    while(p != list->first){
        p->next->prior = p->prior;
        p->prior->next = p->next;
        free(p);
        p = list->first->next;
    }
    list->last = list->first;
    list->size = 0; 
} 

//销毁链表
void destroy(DCList* list){
    clear(list);
    free(list->first);
    list->first = list->last = NULL;
}

int main(){
    DCList list;
    init_DCList(&list);
    int select = 1;
    ElemType item = 0;
    while(select){
        printf("\n");
        printf("***********************************\n");
        printf("* [1] push_back   [2] push_front  *\n");        
        printf("* [3] show_list   [4] pop_back    *\n");
        printf("* [5] pop_front   [6] insert_val  *\n");
        printf("* [7] find        [8] length      *\n");
        printf("* [9] delete_val  [10] sort       *\n");
        printf("* [11] reverse    [12] clear      *\n");
        printf("* [13] destroy    [0] exit_system *\n");
        printf("***********************************\n");
        printf("请选择> ");
        scanf("%d",&select);
        if(!select){
            break;
        }
        PNode p = NULL;
        switch(select){
            case 1:
                printf("请输入要输入的数据(-1结束):>");
                while(scanf("%d",&item),item != -1){
                    push_back(&list,item);
                }
                break;
            case 2:
                printf("请输入要输入的数据(-1结束):>");
                while(scanf("%d",&item),item != -1){
                    push_front(&list,item);
                }
                break;
            case 3:
                show_list(&list);
                break;
            case 4:
                pop_back(&list);
                break;
            case 5:
                pop_front(&list);
                break;
            case 6:
                printf("请输入要插入的数据:>");
                scanf("%d",&item);
                insert_val(&list,item);
                break;
            case 7:
                printf("请输入要查找的数据:>");
                scanf("%d",&item);
                p = find(&list,item);
                if(p == NULL){
                    printf("查找的数据不存在.\n");
                }
                break;
            case 8:
                printf("该链表长度为: %d.\n",length(&list));
                break;
            case 9:
                printf("请输入要删除的数据:>");
                scanf("%d",&item);
                delete_val(&list,item);
                break;    
            case 10:
                sort(&list);
                break;
            case 11:
                reverse(&list);
                break;
            case 12:
                clear(&list);
                break;
            case 13:
                destroy(&list);
                break; 
        }    
    }
    destroy(&list);
    return 0;
}

 

标签：last,list,next,prior,循环,printf,双链,first
From： https://www.cnblogs.com/xpp3/p/18416326

相关文章

  • 鹏哥C语言39---分支/循环语句练习：猜数字游戏
    #define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<time.h>//voidfun(inta[]) //因为传过来的是地址，所以应该用一个指针变量来接收，故这里的a本质上是个指针变量//{//   printf("%zu",sizeof(a));//输出8 在x64下，指针大小是......
  • Vue框架；Vue中的选择和循环结构；Vue数据类型；Vue中的事件和动态属性；Vue子组件通过导入在
    一，Vue简介        前端现在比较火的三大框架就是：vue，React，Angular。在国内使用最多的还是：    vue>React >Angular        Vue(发音为/vjuː/，类似view)是一款用于构建用户界面的JavaScript框架。它基于标准HTML、CSS和JavaScript构建，并提......
  • 【CTF MISC】XCTF GFSJ1086 [简单] 简单的base编码 Writeup（Base64编码+循环解码+Base9
    [简单]简单的base编码你懂base编码吗？工具在线BASE92编码解码：https://ctf.bugku.com/tool/base92解法Vm0wd2QyUXlVWGxWV0d4V1YwZDRWMVl3WkRSV01WbDNXa1JTVjAxV2JETlhhMUpUVmpBeFYySkVUbGhoTVVwVVZtcEJlRll5U2tWVWJHaG9UVlZ3VlZadGNFSmxSbGw1VTJ0V1ZXSkhhRzlVVmxaM1ZsW......
  • 循环语句与条件语句的细节与思想 --进阶C语言
    目录if-else组合if的执行顺序操作符的执行顺序测试方法C语言的布尔类型switchcase组合(补充)屏蔽警告的方法在case中执行多条语句,建议case后都带上花括号.多个case执行同样语句do、while、for循环的基本结构continue跳转的位置循环设计的思想推荐推荐使用for的前闭后开写法null......
  • 鹏哥C语言36-37---循环/分支语句练习（折半查找算法）
    #define_CRT_SECURE_NO_WARNINGS//----------------------------------------------------------------------------------------------------3.4分支，循环练习//用代码解决问题=先想办法(编程思维)+再写代码(按照语法形式)//--------------------------------------------......
  • 鹏哥C语言34---循环语句 do while
    //-------------------------------------------------------------------------------------------------3.3dowhile循环#include<stdio.h>//---------------------------------------------------------------------------------------------3.3.1do语句的语法/*do......
  • 定时循环任务执行
    定时循环任务执行1usingSystem.Timers;23///<summary>4///如果要实现更复杂的功能参见以下5///Cron在线表达式生成器(https://cron.ciding.cc/)6///</summary>7publicclassScheduledTaskExecutor8{9privateList<TaskInfo>tasks......
  • 5.1.1 第三种循环----for循环
    如图结果闺女买了两袋包子,一袋十二个,一共24个包子.为啥?4!=24.n!表示阶乘,n!=1*2*3*...*n如果我们要写一个程序,计算一个数n的阶乘并打印结果,要怎么设计呢?变量:我们需要输入一个整数n.然后需要一个fac来记录n累乘得结果,最后一个整数i,来让他在fac累乘之后每次加1,在i大......
  • 4、循环单链表
    1、代码实现#include<stdio.h>#include<malloc.h>#include<assert.h>typedefintElemType;typedefstructNode{ElemTypedata;structNode*next;}Node,*PNode;typedefstructSCList{PNodefirst;PNodelast;intsize;}S......
  • Js基础之循环分支
    1.if语句单分支：除了0所有的数字都为真除了空字符串，所有的数字都为真if(0){console.log();//不执行，负数也执行，只要不为0就行}题目：单分支课堂案例1:用户输入高考成绩，如果分数大于700，则提示恭喜考入黑马程序员//1.用户输入letscore=+prompt('请输入成绩')//12、进......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99