简简单单的循环链表C++

╰+哭是因爲堅強的太久メ 2022-12-01 15:39 111阅读 0赞

数据结构练习  
循环链表代码C++

首先，给出一遍链表的代码。

##### 链表 #####

#include <stdio.h>
    #include <malloc.h>
    
    //using namespace std;c语言中不能使用;
    #define bool short
    #define true 1
    #define false 0
    
    //! 元素为char类型
    typedef char ElemType;
    
    typedef struct Node
    {
        
        ElemType data;
        struct Node * next;
    }Node,*LinkList;
    
    
    //! LinkList已经是指针了，等价于struct Node **L;
    //! L为二级指针，赋值为指针的地址
    InitList(LinkList *L)
    {
        
        //! 用*L即P申请了一个内存空间，P指针指向了这样一个节点，即成功的为P赋了初值
        *L=(LinkList)malloc(sizeof(Node));
        //! set position next equal to null
        (*L)->next=NULL;
    }
    
    bool CreatFromHead(LinkList L)
    {
        
        Node *s;
        char c;
        while(1)
        {
        
            c=getchar();
            if(c=='$')
            {
        
                 //printf("Great success!\n");
                break;
            }
            else
            {
        
                s=(Node *)malloc(sizeof(Node));
                s->data=c;
                s->next=L->next;
                L->next=s;
                // printf("%c",s->data);
            }
        }
        //printf("success?\n");
        return true;
    }
    
    
    bool CreatFromTail(LinkList L)
    {
        
        //LinkList L;
        //L=(Node *)malloc(sizeof(Node));
        Node *r,*s;
        r=L;
        char c;
        while(1)
        {
        
            c=getchar();
            if(c=='$')
            {
        
                s->next=NULL;
                break;
            }
            else
            {
        
                s=(Node *)malloc(sizeof(Node));
                s->data=c;
                r->next=s;
                r=s;
            }
        }
        return true;
    }
    
    Node * Get(LinkList L,int n)
    {
        
        if(n<=0)
        {
        
            printf("Get position error!\n");
            return NULL;
        }
        int i=0;
        Node *P=L;
        while(i<n && P->next!=NULL)
        {
        
            ++i;
            P=P->next;
        }
        if(i==n)
        {
        
            return P;
        }
        else
        {
        
            printf("Get position error!\n");
            return NULL;
        }
    }
    
    Node *Locate(LinkList L,char key)
    {
        
        Node *P;
        P=L->next;
        while(P->data!=key && P->next!=NULL)
        {
        
            P=P->next;
        }
        if(P->data==key)
        {
        
            return P;
        }
        else
        {
        
            printf("Key value not int list.\n");
            return NULL;
        }
    }
    
    
    int ListLength(LinkList L)
    {
        
        Node *p;
        p=L->next;
        int ret=0;
        while(p!=NULL)
        {
        
            ++ret;
            p=p->next;
        }
        return ret;
    }
    
    void InsertList(LinkList L,int n,char e)
    {
        
        if(n<=0)
        {
        
            printf("Insert position error!");
            return;
        }
        Node *p,*s;
        p=L->next;
        int i=0;
        while(i<n-1 && p->next!=NULL)
        {
        
            ++i;
            p=p->next;
        }
    
        if(i==n-1)
        {
        
            s=(Node *)malloc(sizeof(Node));
            s->data=e;
            s->next=p->next;
            p->next=s;
            return;
        }
        else
        {
        
            printf("Insert position error!\n");
            return NULL;
        }
    }
    
    bool DelList(LinkList L,int k,ElemType *e)
    {
        
        if(k<=0)
        {
        
            printf("Delete position error!\n");
            return false;
        }
        Node *s,*p;
        s=L;
        p=L->next;
        //s=p;
        int i=1;
        while(p->next!=NULL && i<k)
        {
        
            s=p;
            p=p->next;
            ++i;
        }
        if(i==k)
        {
        
            *e=p->data;
            //printf("%c",e);
            s->next=p->next;
            free(p);
            return true;
        }
        else
        {
        
            printf("Delete position error\n");
            return false;
        }
    }
    
    bool ClearList(LinkList L)
    {
        
        int n=ListLength(L);
        ElemType tmp;
        int i;
        for(i=1;i<=n;++i)
        {
        
            //printf("?");
            DelList(L,1,&tmp);
            putchar(tmp);
        }
        putchar('\n');
        if(i==n)
        {
        
            return true;
        }
        else
        {
        
            return false;
        }
    }
    
    bool test1()
    {
        
        //! 建立一级指针P,用于指向某个Node节点，节点不定
        LinkList P;
        //!give position，将一个指针的地址值传入
        InitList(&P);
    
    
        //P=(Node *)malloc(sizeof(Node));
        if(!CreatFromHead(P))
        {
        
            printf("Creat from head fail");
        }
        printf("len:%d\n",ListLength(P));
        printf("list elems:\n");
        //CreatFromTail(P);
    
        ClearList(P);
        free(P);
        printf("Hello list!\n");
        return true;
    }
    
    bool test2()
    {
        
        //! 建立一级指针P,用于指向某个Node节点，节点不定
        LinkList P;
        //!give position，将一个指针的地址值传入
        InitList(&P);
    
    
        //P=(Node *)malloc(sizeof(Node));
        if(!CreatFromTail(P))
        {
        
            printf("Creat from head fail");
        }
        printf("len:%d\n",ListLength(P));
        printf("list elems:\n");
    
        Node *tmp;
        tmp=(Node *)malloc(sizeof(Node));
    
    
        tmp=Locate(P,'a');
        putchar(tmp->data);
        //CreatFromTail(P);
    
        ClearList(P);
        free(P);
        printf("Hello list!\n");
        return true;
    }
    
    int main()
    {
        
        if(test1())
        {
        
            printf("this test is build from head\n");
            printf("test1 run success\n\n\n");
        }
    
        if(test2())
        {
        
            printf("this test is build fron tail\n");
            printf("test2 run success\n");
        }
    
        return 0;
    }

##### 循环链表 #####

其实我只写了一部分，创建和结构题方面有点差别，剩下的感觉差别不大，跟前面的链表的代码差不多。

#include <stdlib.h>
    //#include <iostream.h>
    
    #define bool short
    #define true 1
    #define false 0
    
    typedef int ElemType;
    
    typedef struct Node
    {
        
        ElemType data;
        struct Node * next;
    }Node,*LinkList;
    
    
    //! 用尾指针表示循环链表
    InitCLinkList(LinkList *CL)
    {
        
        *CL=(LinkList)malloc(sizeof(Node));
        (*CL)->next=*CL;
    }
    
    
    bool CreatCLinkLIst(LinkList CL)
    {
        
        Node *rear,*s;
        int a;
        rear=CL;
        scanf("%d",&a);
        while(a!=0)
        {
        
            s=(Node *)malloc(sizeof(Node));
            s->data=a;
            rear->next=s;
            //s->next=rear->next;
            rear=s;
            scanf("%d",&a);
        }
        rear->next=CL;
        return true;
    }
    
    bool
    
    
    int main()
    {
        
    
        return 0;
    }