jmu-ds-单链表的基本运算

怼烎@ 2022-05-09 04:58 247阅读 0赞

实现单链表的基本运算：初始化、插入、删除、求表的长度、判空、释放。  
（1）初始化单链表L，输出L->next的值；  
（2）依次采用尾插法插入元素：输入分两行数据，第一行是尾插法需要插入的字符数据的个数，第二行是具体插入的字符数据。  
（3）输出单链表L；  
（4）输出单链表L的长度；  
（5）判断单链表L是否为空；  
（6）输出单链表L的第3个元素；  
（7）输出元素a的位置；  
（8）在第4个元素位置上插入‘x’元素；  
（9）输出单链表L；  
（10）删除L的第3个元素；  
（11）输出单链表L；  
（12）释放单链表L。

## 输入格式: ##

两行数据，第一行是尾插法需要插入的字符数据的个数，第二行是具体插入的字符数据。

## 输出格式: ##

按照题目要求输出

## 输入样例: ##

5
    a b c d e

## 输出样例: ##

0
    a b c d e
    5
    no
    c
    1
    a b c x d e
    a b x d e

#include <bits/stdc++.h>
    using namespace std;
    
    #define TRUE        1
    #define FALSE       0
    #define OK          1
    #define ERROR       0
    #define INFEASIBLE -1
    #define OVERFLOW   -2
    
    typedef int  Status;
    typedef char  ElemType; 
    
    typedef struct LNode
    {
        
        ElemType data;
        struct LNode *next;
    } LNode,*LinkList; 
    Status ListCreate_CL(LinkList &CL);
    void ListPrint_CL(LinkList &L)
    {
        
        LNode* curPtr;
        curPtr = L->next;
        while(curPtr != NULL)
        {
        
            if(L->next == curPtr)
                printf("%c",curPtr->data);
            else
                printf(" %c",curPtr->data);
            curPtr = curPtr->next;
        }
        printf("\n");
    }
    Status InitList(LinkList &L)
    {
        
        L = new LNode;
        L->next = NULL;
        return 1;
    }
    int ListEmpty(LinkList L)
    {
        
        if(L->next) return TRUE;
        else return FALSE;
    }
    Status Get_L(LinkList L,char &e)
    {
        
        LNode* p;
        p = L->next;
        int j = 1;
        while(p && j < 3) {
        
            p = p->next;
            ++j;
        }
        e = p->data;
        return OK;
    }
    Status Locate_L(LinkList &L,ElemType e)
    {
        
        LNode *cur;
        cur=L->next;
        int num=1;
        while(cur&&cur->data!=e){
        
            cur=cur->next;
            num++;
        }
        if(!cur) return FALSE;
        cout<<num<<endl;
        return OK;
    }
    Status Insert_L(LinkList &L,ElemType e)
    {
        
    LNode * p;
        p = L->next;
        int j = 1;
        while(p && j < 3) {
        
            p = p->next;
            ++j;
        }
        if(!p || j > 3) return ERROR;
        LNode* t= (LNode* )malloc (sizeof(LNode));
        t->data = e;
        t->next = p->next;
        p->next = t;
        return OK;
    }
    Status DeleteList(LinkList & L,char &e)
    {
        
        LNode * p,*q;
        p = L->next;
        int j = 1;
        while(p && j < 2)
        {
        
            p = p->next;
            j++;
        }
        if(p!=NULL && j > 2) return ERROR;
        q = p->next->next;
        p->next = q;
        return OK;
    }
    Status Length_L(LinkList L)
    {
        
        int t=0;
        while(L)
        {
        
            t++;
            L=L->next;
        }
        return t-1;
    }
    int main()
    {
        
        LinkList L;
        InitList(L);
         cout<<L->next<<endl;
        ListCreate_CL(L);
        ListPrint_CL(L);
        cout<<Length_L(L)<<endl;
        if(ListEmpty(L))cout<<"no"<<endl;
        else cout<<"yes"<<endl;
        char w;
        Get_L(L,w);
        cout<<w<<endl;
        Locate_L(L,'a');
        Insert_L(L,'x');
        ListPrint_CL(L);
        DeleteList(L,w);
        ListPrint_CL(L);
        free(L);
        return 0;
    }
    Status ListCreate_CL(LinkList &L)
    {
        
        int n;
        cin>>n;
        LNode * curPtr, * rearPtr;
        rearPtr = L; 
        for (int i = 1;i <= n;i ++){
        
            curPtr = (LNode*)malloc(sizeof(LNode));
            if(!curPtr) exit(OVERFLOW);
            scanf(" %c",&curPtr->data);
            curPtr->next = NULL; 
            rearPtr->next = curPtr;
            rearPtr = curPtr;
        }
        return OK;
    }