PTA-数据结构单链表的基本运算

た入场券 2022-05-09 08:14 285阅读 0赞

7-1 jmu-ds-单链表的基本运算 （15 分）

实现单链表的基本运算：初始化、插入、删除、求表的长度、判空、释放。  
（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<stdio.h>
    #include<malloc.h>
    #include<stdlib.h>
    
    
    //函数状态码定义
    #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 InitList(Linklist &L);
    Status InputList(Linklist &L,int n);
    void PrintList(Linklist L);
    int GetLength(Linklist L);
    Status IsEmpty(Linklist L);
    void PrintElem(Linklist L,int n);
    int LocateElem(Linklist L,ElemType a);
    Status InsertElem(Linklist &L,ElemType x,int pos);
    Status DeleteElem(Linklist &L,int pos);
    Status GetElem(Linklist L,int n,ElemType &e);
    
    int main()
    {
        Linklist L;
    
        InitList(L);
        printf("%d\n",L->next);
    
        int n;
        scanf("%d",&n);
    
        InputList(L,n);
        PrintList(L);
    
        printf("%d\n",GetLength(L));
    
        if(IsEmpty(L))
            printf("yes\n");
        else
            printf("no\n");
    
        ElemType e;
        GetElem(L,3,e);
        printf("%c\n",e);
        
        printf("%d\n",LocateElem(L,'a'));
    
        InsertElem(L,'x',4);
        PrintList(L);
    
        DeleteElem(L,3);
        PrintList(L);
    
        free(L);
        return 0;
    }
    Status InitList(Linklist &L)
    {
        L = (Linklist)malloc(sizeof(LNode));
        if(!L)
            exit(OVERFLOW);
        L->next = NULL;
        return OK;
    }
    Status InputList(Linklist &L,int n)
    {
        Linklist p,tail;
        tail = L;
        while(n--)
        {
            p = (Linklist)malloc(sizeof(LNode));
            if(!p)
                exit(OVERFLOW);
            scanf(" %c",&p->data);
            tail->next = p;
            p->next = NULL;
            tail = p;
        }
        return OK;
    }
    void PrintList(Linklist L)
    {
        Linklist p = L->next;
        int flag = 0;
        while(p)
        {
            if(!flag)
            {
                printf("%c",p->data);
                flag++;
            }
            else
                printf(" %c",p->data);
            p = p->next;
        }
        printf("\n");
    }
    int GetLength(Linklist L)
    {
        int len = 0;
        L = L->next;
        while(L)
        {
            L = L->next;
            len++;
        }
        return len;
    }
    Status IsEmpty(Linklist L)
    {
        if(L->next)
            return FALSE;
        return TRUE;
    }
    Status GetElem(Linklist L,int n,ElemType &e)
    {
        int len=1;
        LNode* p = L->next;
        while(p && len<n)
        {
            p = p->next;
            len++;
        }
        if(!p || len>n)
            return ERROR;
        e = p->data;
        return OK;
    }
    int LocateElem(Linklist L,ElemType a)
    {
        LNode* p = L->next;
        int pos = 1;
        while(p && p->data != a)
        {
            p = p->next;
            pos++;
        }
        if(!p)
            return 0;
        return pos;
    }
    Status InsertElem(Linklist &L,ElemType x,int pos)
    {
        LNode* p = L->next;
        int i=1;
        while(p && i<pos-1)
        {
            p = p->next;
            i++;
        }
        if(!p || i>pos-1)
            return ERROR;
        LNode* pNew = (Linklist)malloc(sizeof(LNode));
        if(!pNew)
            exit(OVERFLOW);
        pNew->data = x;
        pNew->next = p->next;
        p->next = pNew;
        return OK;
    }
    Status DeleteElem(Linklist &L,int pos)
    {
        LNode* p = L->next;
        LNode* prep = L;
        int i=1;
        while(p && i<pos)
        {
            p = p->next;
            prep = prep->next;
            i++;
        }
        if(p && i>pos)
            return ERROR;
        prep->next = p->next;
        free(p);
        return OK;
    }