首页 > 其他分享 >4、循环单链表

4、循环单链表

时间：2024-09-14 09:13:32浏览次数：1  
标签：node Node 单链 last list next 循环 first

1、代码实现

#include<stdio.h>
#include<malloc.h>
#include<assert.h>
typedef int ElemType;

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

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


void initSCList(SCList* list){
    //申请空间 创建虚拟头节点 
    Node* node = (Node*)malloc(sizeof(Node));
    assert(node != NULL);
    //第一个节点 和 最后一个节点 指向虚拟头节点 
    list->first = list->last = node;
    //虚拟头结点指向自己完成循环 
    node->next = node;
    //当前链表大小为0 
    list->size = 0;
}

//申请节点 
Node* malloc_node(ElemType e){
    Node* node = (Node* )malloc(sizeof(Node));
    assert(node != NULL);
    node->next = NULL;
    node->data = e;
    return node;
}

//尾插 
void push_back(SCList* list,ElemType e){
    //申请新节点 
    Node* node = malloc_node(e);
    //链表最后一个节点指向新节点 
    list->last->next = node;
    //更新last指针 
    list->last = node;
    //新节点的next指向第一个节点 形成循环 
    node->next = list->first;
    //元素数量+1 
    list->size++;
}

//头插 
void push_front(SCList* list,ElemType e){
    //申请新节点 
    Node* node = malloc_node(e);
    node->next = list->first->next;
    list->first->next = node;
    //判断当前链表是否为空 
    if(list->first == list->last){
        //为空当前插入的节点则为last所指向的节点 
        list->last = node;
    }
    list->size++;
}
//打印链表
void show_SCList(SCList* list){
    Node* p = list->first->next;
    while(p != list->first){
        printf("%d->",p->data);
        p = p->next;
    }
    printf("NULL .\n last=%d,size=%d",list->last->data,list->size);
} 

//删除尾部 
void pop_back(SCList* list){
    if(list->size == 0){
        //当前链表为空
        printf("当前链表为空,不可删除.\n");
        return; 
    }    
    PNode p = list->first;
    while(p->next != list->last){
        p = p->next;
    }
    free(list->last);
    list->last = p;
    p->next = list->first;
    list->size--;
}

//删除头部
void pop_front(SCList* list){
    if(list->size == 0){
        //当前链表为空
        printf("当前链表为空,不可删除.\n");
        return; 
    }
    
    Node* node = list->first->next;
    list->first->next = node->next;
    if(list->size == 1){
        //说明删除的是最后一个元素
        list->last = list->first; 
    }
    free(node);
    list->size--;
} 

//插入元素 [默认链表升序排序] 
void insert_val(SCList* list,ElemType e){
    Node* node = malloc_node(e);
    Node* p = list->first;
    while(p->next != list->first && p->next->data < e){
        p = p->next;
    } 
    node->next = p->next;
    p->next = node;
    if(node->next == list->first){
        //说明插入的位置是末尾
        list->last = node; 
    }
    list->size++;
}

//查找元素
Node* find(SCList* list,ElemType key){
    if(list->first == list->last){
        return NULL;
    } 
    Node* p = list->first->next;
    while(p != list->first){
        if(p->data == key){
            return p;
        }
        p = p->next;
    }
    return NULL;
} 

//返回链表长度
int length(SCList list){
    return list.size;
}

//按值删除
void delete_val(SCList* list,ElemType e){
    if(list->size == 0){
        return;
    }
    Node* p = find(list,e);
    if(p == NULL){
        return;
    }
    if(p->next == list->last){
        pop_back(list);
    }else{
        p->data = p->next->data;
        p->next = p->next->next; 
        free(p);
        list->size--;
    }
} 

//排序
void sort(SCList* list){
    if(list->size <= 1){
        return;
    }
    //指向第一个节点 
    Node* p = list->first->next;
    //指向第二个节点 
    Node* q = p->next;
    
    //将原链表最后一个节点指向NULL 
    list->last->next = NULL;
    //改变last指针指向第一个节点 
    list->last = p;
    //形成循环
    p->next = list->first; 
    
    while(q != NULL){
        p = q;
        q = q->next;
        Node* s = list->first; 
        //找到要插入的位置的上一个节点 
        while(s->next != list->first && s->next->data < p->data){
            s = s->next;
        } 
        //插入该节点
        p->next = s->next;
        s->next = p;
        if(s->next == list->first){
            //插入的位置是末尾
            list->last = p;
        }
    }
} 

//逆置链表
void reverse(SCList* list){
    if(list->size <= 1){
        return;
    }
    
    //指向第一个节点 
    Node* p = list->first->next;
    //指向第二个节点 
    Node* q = p->next;
    
    //将原链表最后一个节点指向NULL 
    list->last->next = NULL;
    //改变last指针指向第一个节点 
    list->last = p;
    //形成循环
    list->last->next = list->first;
     
    while(q != NULL){
        p = q;
        q = q->next;
    
        //头插法插入节点 
        p->next = list->first->next;
        list->first->next = p;
    } 
} 

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

//销毁链表
void destroy(SCList* list){
    clear(list);
    free(list->first);
    list->first = list->last = NULL;
} 
int main(){
    SCList list;
    initSCList(&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_SCList(&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;
}

2、排序和逆置代码画图演示

 

标签：node,Node,单链,last,list,next,循环,first
From： https://www.cnblogs.com/xpp3/p/18413303

相关文章

  • Js基础之循环分支
    1.if语句单分支：除了0所有的数字都为真除了空字符串，所有的数字都为真if(0){console.log();//不执行，负数也执行，只要不为0就行}题目：单分支课堂案例1:用户输入高考成绩，如果分数大于700，则提示恭喜考入黑马程序员//1.用户输入letscore=+prompt('请输入成绩')//12、进......
  • Laravel Blade：如何在表循环中迭代模型的belongsToMany关系？
    一、引言（一）介绍是一种流行的PHP模板引擎，用于构建动态网页。在本文中，我们将探讨如何在表循环中迭代模型的belongsToMany关系。通过使用LaravelBlade，我们可以轻松地处理这种复杂的关系，并在模板中显示相关的数据。本文将介绍如何设置关系、如何在模板中访问关系数据以及如何使用......
  • Python第四章节——循环语句
    学习循环语句的原因：循环在程序中和判断一样广泛存在，同样是非常多功能实现的基础一.while循环1.while循环的使用方法：while条件:    条件满足时完成的事件1    条件满足时完成的事件2    条件满足时完成的事件3    ...注意：1.只要条......
  • 鹏哥C语言(进阶)27-30---循环语句 while
    #define_CRT_SECURE_NO_WARNINGS//--------------------------------------------------------------------------------------------------------------3.循环语句//while //for//dowhile#include<stdio.h>//------------------------------------------------......
  • Java 假设有一个对象list 有4列，4和3比较name 如果name不相同则记录4的version值string
    可以使用传统循环或Java8的流（Stream）API来实现这一逻辑。以下是这两种方法的示例代码：1.使用传统循环importjava.util.List;publicclassMain{publicstaticvoidmain(String[]args){List<MyObject>list=...;//初始对象列表String......
  • 小白学懂C语言---分支循环语句（下）
    循环语句这章我们来谈谈三种循环语句（for循环，while循环，do-while循环）1.for循环for循环应该是平时用的比较多的一种，也是一种容易理解的循环。for循环语法：for(表达式1;表达式2;表达式3){ 语句}强调一下：1.表达式1表达式2表达式3，两两之间用;隔开，记住不要写成逗......
  • 28 Java中的循环结构
    Java中的循环结构在Java编程中，循环结构是实现重复执行代码块的关键工具。通过循环结构，程序员可以高效地处理大量数据、执行重复任务，从而简化代码并提高程序的效率。本文将深入探讨Java中的循环结构，帮助你全面理解其工作原理及实际应用。1.前置知识在深入探讨循环结构之......
  • c++primer第五章循环和关系表达式学习笔记
    for循环简单for循环#include<iostream>usingnamespacestd;intmain(){//5.1inti;for(i=0;i<5;i++)cout<<"C++knowsloops.\n";cout<<"C++knowswhentostop.\n";return0;}for循环组成部分#......
  • Java 入门指南：Java 并发编程 —— 同步工具类 CyclicBarrier（循环屏障）
    文章目录同步工具类CyclicBarrier构造函数常用方法工作机制使用步骤适用场景CyclicBarrier与CountDownLatch的区别示例代码同步工具类JUC（Java.util.concurrent）是Java提供的用于并发编程的工具类库，其中包含了一些通信工具类，用于在多个线程之间进行协调和通信，特别......
  • 网络编程day05（循环服务器、并发服务器）
    目录服务器模型 1》循环服务器 2》并发服务器1>多进程：每有一个客户端连接创建一个进程进行通信2> 多线程：每有一个客户端连接创建一个线程进行通信 3>IO多路复用4>总结服务器模型在网络通信中，通常一个服务器要连接多个客户端为了处理多个客户端的请求，通常......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99