首页 > 其他分享 >线性表之单循环链表实现

线性表之单循环链表实现

时间：2023-04-09 22:44:42浏览次数：41  
标签：Node last 线性表 List list next 链表 单循环 first

main.cpp

#include "SCList.h"

int main(){
    List mylist;
    InitList(mylist);
    int select=1;
    ElemType Item;
    Node *p=NULL;
    while(select){
        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] resver       [12] clear     *\n");
        printf("* [13*] destory      [0] quit_sys  *\n");
        printf("************************************\n");
        printf("请选择:>");
        scanf("%d",&select);
        if(select == 0 )
            break;
        switch (select) {
            case 1:
                printf("请输入要插入的数据(-1结束):>");
                while (scanf("%d",&Item),Item != -1){
                    push_back(mylist,Item);
                }
                break;
            case 2:
                printf("请输入要插入的数据(-1结束):>");
                while (scanf("%d",&Item),Item != -1){
                    push_front(mylist,Item);
                }
                break;
            case 3:
               show_list(mylist);
                break;
            case 4:
                pop_back(mylist);
                break;
            case 5:
                pop_front(mylist);
                break;
            case 6:
                printf("请输入要插入的数据:>");
                scanf("%d",&Item);
                insert_val(mylist,Item);
                break;
            case 7:
                printf("请输入要查找的数据:>");
                scanf("%d",&Item);
                p=find(mylist,Item);
                if(p==NULL)
                {
                    printf("要查找的数据在链表中不存在\n");
                }
                break;
            case 8:
                printf("单链表的长度为 %d\n",length(mylist));
                break;
            case 9:
                printf("请输入要删除的值:>");
                scanf("%d",&Item);
                delete_val(mylist,Item);
                break;
            case 10:
                sort(mylist);
                break;
            case 11:
                resver(mylist);
                break;
            case 12:
                clear(mylist);
                break;
                //case 13:
                //    destory(&mylist);
                //    break;
            default:
                printf("输入的命令错误，请重新输入。\n");
                break;
        }
    }
    destory(mylist);
}

SCList.h(头文件)

#ifndef SCLIST_SCLIST_H
#define SCLIST_SCLIST_H

#define ElemType int

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

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

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

void InitList(List &list);

Node *_buynode(ElemType x);

void push_back(List &list, ElemType x);

void show_list(List &list);

void push_front(List &list, ElemType x);

void pop_back(List &list);

void pop_front(List &list);

void insert_val(List &list, ElemType x);

Node *find(List &list, ElemType key);

int length(List &list);

void delete_val(List &list, ElemType x);

void sort(List &list);

void resver(List &list);

void clear(List &list);

void destory(List &list);
#endif //SCLIST_SCLIST_H

SCList.cpp

#include "SCList.h"

void InitList(List &list) {
    Node *s = (Node *) malloc(sizeof(Node));
    assert(s != NULL);
    list.first = list.last = s;
    list.last->next = list.first;
    list.size = 0;
}

Node *_buynode(ElemType x) {
    Node *s = (Node *) malloc(sizeof(Node));
    assert(s != NULL);
    s->data = x;
    s->next = NULL;
    return s;
}

void push_back(List &list, ElemType x) {
    Node *s = _buynode(x);
    list.last->next = s;
    list.last = s;
    list.last->next = list.first;
    list.size++;

}

void push_front(List &list, ElemType x) {
    Node *s = _buynode(x);
    s->next = list.first->next;
    list.first->next = s;
    if (list.first == list.last) {
        list.last = s;
    }
    list.size++;
}

void show_list(List &list) {
    Node *p = list.first->next;
    while (p != list.first) {
        printf("%d-->", p->data);
        p = p->next;
    }
    printf("Null\n");
}

void pop_back(List &list) {
    if (list.size == 0) {
        return;
    }
    Node *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(List &list) {
    if (list.size == 0)
        return;
    Node *p = list.first->next;
    list.first->next = p->next;
    free(p);
    if (list.size == 1) {
        list.last = list.first;
    }
    list.size--;
}

void insert_val(List &list, ElemType x) {
    Node *p = list.first;
    while (p->next != list.last && p->next->data < x) {
        p = p->next;
    }
    if (p->next == list.last && p->next->data < x) {
        push_back(list, x);
    } else {
        Node *s = _buynode(x);
        s->next = p->next;
        p->next = s;
        list.size++;
    }
}

Node *find(List &list, ElemType key) {
    if (list.size == 0)
        return NULL;
    Node *p = list.first->next;
    while (p != list.first && p->data != key)
        p = p->next;
    if (p == list.first)
        return NULL;
    return p;
}

void delete_val(List &list, ElemType key) {
    if (list.size == 0)
        return;
    Node *p = find(list, key);
    if (p == NULL) {
        printf("要删除的数据不存在.\n");
    }
    if (p == list.last) {
        pop_back(list);
    } else {
        Node *q = p->next;
        p->data = q->data;
        p->next = q->next;
        free(q);
        list.size--;
    }
}

void sort(List &list) {
    if (list.size == 0 || 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;

    while (q != NULL) {
        s = q;
        q = q->next;
        Node *p = list.first;
        while (p->next != list.last && p->next->data < s->data) {
            p = p->next;
        }
        if (p->next == list.last && p->next->data < s->data) {
            s->next = list.last->next;
            list.last->next = s;
            list.last = s;
        } else {
            s->next = p->next;
            p->next = s;
        }
    }
}

void resver(List &list) {
    if (list.size == 0 || list.size == 1)
        return;
    Node *p = list.first->next;
    Node *q = p->next;

    list.last->next = NULL;
    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(List &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;
    list.last->next = list.first;
    list.size =0;
}

void destory(List &list){
    clear(list);
    free(list.first);
    list.first = list.last = NULL;
}
int length(List &list) {
    return list.size;
}

标签：Node,last,线性表,List,list,next,链表,单循环,first
From： https://www.cnblogs.com/hekang520/p/17301342.html

相关文章

  • 搜索二叉树转换成双向链表
    搜索二叉树：每个节点的左子树的值都小于当前节点，右子树的节点值都大于当前节点。其中序遍历就是一个有序的序列转化成双向链表，需要记录一下头节点，和前一个节点，将前一个节点和当前节点相连preheadconvert(pRoot){if(pRoot==null)returnnull;convert(pRoot.left);......
  • 剑指 Offer 36. 二叉搜索树与双向链表
    题目链接：剑指Offer36.二叉搜索树与双向链表方法一：回溯解题思路代码classSolution{private:intmx=INT_MIN,mi=INT_MAX;Node*start=NULL,*end=NULL;public:voidLrotate(Node*root,Node*last_root){//针对左子树，左旋if(!ro......
  • PAT Basic 1075. 链表元素分类
    PATBasic1075.链表元素分类1.题目描述：给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而[0,K]区间内的元素都排在大于K的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为18→7→-4→0→5→-6→10→11→-2，K为......
  • 链表中的节点每k个一组翻转
    classSolution{publicListNodereverseKGroup(ListNodehead,intk){ListNodedummy=newListNode(0);//定义虚拟节点dummy.next=head;ListNodeprev=dummy;//定义一个前置节点prev，用于保存已经翻转完成的部分的尾部节点......
  • 带头节点的单链表的思路及代码实现
    带头节点的单链表的思路及代码实现（JAVA）一、什么是的单链表①标准定义单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象)+指针(指示后继元素存储位置，元素就是存储数据的存储单......
  • 节点加入到单链表时按需求排序
    JAVA实现节点加入到单链表时按需求排序回顾在上文《带头节点的单链表的思路及代码实现（JAVA）》中我们想要去实现让数据节点不考虑加入顺序实现数据节点排序效果。那么我们要如何实现这一需求呢？一、实现思路①理论思路假设我们要根据数据节点的ID进行排序，那么我们可以通过使用......
  • JAVA实现单链表修改和删除数据节点
    JAVA实现单链表修改和删除数据节点一、修改单链表中的一个节点①实现思路因为带头节点的链表中头节点的next域不能发生改变（始终指向单链表的头节点），否则将找不到该链表。所以我们需要先找一个辅助节点temp来进行节点代理操作。通过遍历链表，使辅助节点temp后移，找到要修改的节点......
  • 链表linklist
       LinkList.hLinkList.cLinkList.h#pragmaonce#include<stdbool.h>typedefintData;//定义节点结构typedefstructlinkNode{Datadata;structlinkNode*next;}linkNode;//创建链表linkNode*createList();//创建节点linkNode*create......
  • Redis 源码解析之通用双向链表(adlist)
    Redis源码解析之通用双向链表(adlist)概述Redis源码中广泛使用adlist(Agenericdoublylinkedlist)，作为一种通用的双向链表，用于简单的数据集合操作。adlist提供了基本的增删改查能力，并支持用户自定义深拷贝、释放和匹配操作来维护数据集合中的泛化数据value。adlist的数......
  • 链表的回文判断—Java实现
    对于这个题，主要是老是局限于方法内的变量，未想到借助外部变量辅助：具如下，不可用数除法，会溢出异常：即使是取最大的long也会溢出，常规方法不再赘述，具体以代码如下：1packageProblemSolve;23publicclassSolution5{4privateListNodefrontNode;5publicboolean......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99