STL list ALDS1_3_C: Doubly Linked List

刺骨的言语ヽ痛彻心扉 2022-11-25 14:29 189阅读 0赞

使用STL中的list来重写了这道题

STL中的链表数据结构，实际上是list，一般有人喜欢用vector来表示不定长的链表，实际上vector只是动态数组而已，长度在不够用是系统自动重新分配空间，并转移元素，以此来实现不定长的链表的效果。

由于vector不能高效前插元素（效率低），所以我们这里用list来实现。

#include <iostream>
    #include <cstdio>
    #include <list>
    #include <cstring>
    
    
    using namespace std;
    
    
    int main()
    {
        
        list<int> v;
        int n;
        scanf("%d",&n);
        char a[13];
        int b;
        char *str1="insert",*str2="delete",*str3="deleteFirst",*str4="deleteLast";
        while(n--)
        {
        
            scanf("%s",a);
            if(strcmp(a,str1)==0)
            {
        
                scanf("%d",&b);
                v.push_front(b);
            }
            else if(strcmp(a,str2)==0)
            {
        
                scanf("%d",&b);
                for(list<int>::iterator it=v.begin();it!=v.end();it++)
                {
        
                    if(*it==b)
                    {
        
                        v.erase(it);
                        break;
                    }
                }
            }
            else if(strcmp(a,str3)==0)
            {
        
                v.pop_front();
            }
            else if(strcmp(a,str4)==0)
            {
        
                v.pop_back();
            }
        }
    
        int i=0;
        for(list<int>::iterator it=v.begin();it!=v.end();it++)
        {
        
            if(i++)
            {
        
                printf(" %d",*it);
            }
            else
            {
        
                printf("%d",*it);
            }
    
        }
        printf("\n");
    
        return 0;
    }