一窥--顺序表和单链表

深藏阁楼爱情的钟 2022-05-16 01:26 138阅读 0赞

# 顺序表和单链表 #

> 真正意义上自己弄出来的，发篇博客记录一下

*  **顺序表**
 *  **单链表**

## 顺序表 ##

> 类似于数组，元素都是相邻的，这也决定了它比较容易和比较适合查询。但缺点就是在插入和删除的时候需要移动大量的元素。

时间复杂度

*  查询操作 O(1)
 *  插入和删除操作 O(n)

代码实现

#include<iostream>
    #include<string>
    using namespace std;
    const int MAXSIZE = 20; //线性表最大长度 
    
    typedef int ElemType;
    typedef struct{
        ElemType data[MAXSIZE];
        int length; //线性表长度 
        
    } Sqlist;
    
    //按照1,2,...,n进行计数 
    void SetElem(Sqlist &L){
        for (int i=0;i<L.length;i++)
            L.data[i] = i+1;
    }
    
    int GetElem(Sqlist L,int i){
        if(L.length == 0 || i<1 || i>L.length)
            return -1;
        return L.data[i-1];
    }
    
    string ListInsert(Sqlist *L,int index,ElemType num){
        if( L->length == MAXSIZE)
            return "List is already full";
        if(index<1 || index>=L->length+1)
            return "Index is out of range";
        if(index<=L->length){
            int k;
            //元素后移 
            for (k=L->length-1;k>=index-1;k--){
                //error这样长度不变:L->data[k] = L->data[k-1];
                L->data[k+1] = L->data[k];
            }
            L->data[index-1] = num;
            L->length++;
            return "Inserted!";
        }
    }
    
    string ListDelete(Sqlist *L,int index){
        if (L->length==0)
            return "List is empty";
        if (index<1 || index >L->length)
            return "Index is out of range";
        if (index<=L->length){
            int k;
            for (k=index-1;k<L->length-1;k++)
                L->data[k] = L->data[k+1];
            L->length--;
            return "Deleted!";
        }
    }
    int main(){
        Sqlist sq;
        sq.length = 10;
        
        SetElem(sq);
        
        cout<<ListInsert(&sq,10,100)<<endl;
        
        for (int i=0;i<sq.length;i++)
            cout<<GetElem(sq,i+1)<<" ";
        cout<< endl;
        
        cout<<ListDelete(&sq,1)<<endl;
        for (int i=0;i<sq.length;i++)
            cout<<GetElem(sq,i+1)<<" ";
        cout<< endl;
        return 0;
    }

缺点

1.  长度有限，不灵活
2.  查询和删除操作太慢
3.  会有多余的空间被浪费 :`MAXSIZE-length`
4.  当改变长度时候，内存可能需要进行大面积的数值迁移，浪费内存资源

--------------------

## 单链表 ##

> 长度随心，非常灵活，创建麻烦些，但是一劳永逸

组成:结点

1.  **数据域**:存储数据元素信息的域
2.  **指针域**:存储直接后继位置的域
3.  **头指针**:标志作用,无论链表是否为空，它不为空。且位于第一个元素之前，它的数据域一般无意义(*可以用来存放链表长度*)。

时间复杂度

*  查询操作:O(n)
 *  插入/删除操作:O(1)

代码实现

#include<iostream>
    #include<string>
    using namespace std;
    
    typedef int ElemType;
    struct Node{
        ElemType data;//数据域 node->data
        struct Node *next;//指针域 node->next
    }; 
    string CreateListHead(Node *L){//L是现在是空表的头指针 
        L->next = NULL;//头结点初始化 
        Node *p = new Node;
        if(!p)
            return "Create fail";
        cin>>p->data;
        while(p->data){//当输入为0，停止创建 
            p->next = L->next;
            L->next = p;
            p = new Node;
            cin>>p->data;
        }
        delete p;
        return "Create list from head!"; 
    }
    
    string CreateListTail(Node *L){
        L->next = NULL;
        Node *p = new Node;
        Node *t = L;//指向尾结点 
        if(!p)
            return "Create fail (from tail)";
        cin>>p->data;
        while(p->data){
            t->next = p;
            t = p;
            p = new Node;
            cin>>p->data;
        }
        t->next = NULL;//最后指向NULL 
        delete p;
        return "Create list from tail!";
    }
    
    int GetElem(Node *L,int index){
        int j=1;
        Node *p = new Node;
        p = L->next;//指向头结点 
        while(p && j<index){
            p = p->next;
            j++;
        }   
        //p&&j<i 条件取反 
        if (!p){
            return -1;
        }
        return p->data;
    }
    
    string ListInsert(Node *L,int index,ElemType e){
        int j;
        Node *p,*s;
        p = new Node;
        s = new Node;
        if(!p && !s)
            return "Insert fail";
        p = L; //注意插入操作，体现头结点的好处：统一处理的代码 
        j = 1;
        while(p && j<index){
            p = p->next;
            j++;
        }
        if (!p)
            return "Index out of change";
        
        s->data = e;
        s->next = p->next;
        p->next = s;
        //这里p和s不能删除 
        return "Inserted!";
    }
    
    string ListDelete(Node *L,int index,ElemType e){
        int j;
        Node *p,*s= new Node;
        p = L;//p指向头 
        j = 1;
        while(p->next && j<index){ //p->next 是要删除的，这样，p就保存了删除的结点前一个结点的信息 
            p = p->next;
            ++j;
        }
        if(!(p->next)){
            return "Index out of change";
        }
        
        s = p->next;
        p->next = s->next;
        
        delete s; //删除结点 
        return "Deleted!";
    }
    
    void ShowList(Node *L){
        Node *p = L->next;
        if(!p)
            cout<<"List is empty"<<endl;
        while(p){
            cout<<p->data<<" ";
            p = p->next;
        }
        cout<<endl;
    }
    int main(){
        
        Node *node = new Node;
        CreateListHead(node); //头插法，倒着插入 ,1,2,3
        ShowList(node);
        cout<<ListInsert(node,2,-10)<<endl;
        ShowList(node);
    
        Node *_node = new Node;
        CreateListTail(_node);
        ShowList(_node);
        cout<<ListInsert(_node,2,-10)<<endl;
        ShowList(_node);
        
        delete node;
        delete _node;
        return 0;
    }

缺点

1.  查询消耗时间
2.  在中间位置插入时候，时间复杂度大