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

刺骨的言语ヽ痛彻心扉 2021-09-29 11:52 168阅读 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 <map>
    #include <set>
    #include <list>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <cstdio>
    #include <vector>
    #include <iomanip>
    #include <cstdlib>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define ll long long
    #define LIST_INIT_SIZE 100000
    #define LISTINCREMENT 10
    #define mod 256
    #define lowbit(x) (x&(-x))
    #define mem(a,b) memset(a,b,sizeof(a))
    #define FRER() freopen("in.txt","r",stdin);
    #define FREW() freopen("out.txt","w",stdout);
    using namespace std;
    const int maxn = 100000 + 7;
    char s[maxn];
    int n;
    typedef struct LNode{
        char c;
        struct LNode* next;
    }LNode,*LinkList;
    void InitList(LinkList &L){
        L = (LinkList)malloc(sizeof(LNode));
        L->next = NULL;
        printf("0\n");
    }
    void CreateList(LinkList L){
        for(int i=n-1;i>=0;--i){
            LinkList p = (LinkList)malloc(sizeof(LNode));
            p->c = s[i];
            p->next = L->next;
            L->next = p;
        }
    }
    void print(LinkList L){
        LinkList p = L->next;
        int i = 0;
        while(p!=NULL){
            if(i++) printf(" ");
            printf("%c",p->c);
            p = p->next;
        }
        printf("\n");
    }
    int GetLinkListLength(LinkList L){
        int ans = 0;
        LinkList p = L;
        while(p->next!=NULL){
            p = p->next;
            ans++;
        }
        return  ans;
    }
    char GetElem(LinkList L,int pos){
        int ans = 1;
        LinkList p = L->next;
        while(p&&ans<pos){
            p = p->next;
            ans++;
        }
        return  p->c;
    }
    int GetPos(LinkList L,char a){
        int ans = 1;
        LinkList p = L->next;
        while(p&&p->c!=a){ p = p->next;ans++;}
        return  ans;
    }
    void LinkListInsrt(LinkList L,int pos,char a){
        LinkList p,q;
        p = L;
        q = (LinkList)malloc(sizeof(LNode));
        q->c = a;
        int ans = 1;
        while(p->next&&ans<pos){
            ans++;
            p = p->next;
        }
        q->next = p->next;
        p->next = q;
    }
    void ListDstroy(LinkList&L){
        LinkList p = L;
        LinkList q;
        while(p->next){
            q = p->next;
            p->next = q->next;
            free(q);
        }
        free(L);
    }
    void LinkListDelete(LinkList L,int pos){
        LinkList p = L;
        int ans = 1;
        while(p->next&&ans<pos){
            ans++;
            p = p->next;
        }
        LinkList q = p->next;
        p->next = p->next->next;
        free(q);
    }
    bool IsEmpty(LinkList L){
        if(L->next==NULL) return  true;
        return  false;
    }
    int main(){
        LinkList L;
        InitList(L);
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf(" %c",&s[i]);
        }
        CreateList(L);
        print(L);
        cout<<GetLinkListLength(L)<<endl;
        printf("%s\n",IsEmpty(L)?"yes":"no");
        printf("%c\n",GetElem(L,3));
        printf("%d\n",GetPos(L, 'a'));
        LinkListInsrt(L, 4, 'x');
        print(L);
        LinkListDelete(L, 3);
        print(L);
        ListDstroy(L);
    }

转载于:https://www.cnblogs.com/seven7777777/p/10278688.html