顺序表和单链表

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

顺序表

类似于数组，元素都是相邻的，这也决定了它比较容易和比较适合查询。但缺点就是长度有限。

时间复杂度

查询操作 O(1)

插入和删除操作 O(n)

代码实现

#include
    
     #include
     
      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)        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
       
        length-1;k++)            L->data[k] = L->data[k+1];        L->length--;        return "Deleted!";    }}int main(){    Sqlist sq;    sq.length = 10;        SetElem(sq);        cout<
        
         <

缺点

长度有限，不灵活

查询和删除操作太慢

会有多余的空间被浪费 :MAXSIZE-length

当改变长度时候，内存可能需要进行大面积的数值迁移，浪费内存资源

单链表

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

组成:结点

数据域:存储数据元素信息的域

指针域:存储直接后继位置的域

头指针:标志作用,无论链表是否为空，它不为空。且位于第一个元素之前，它的数据域一般无意义(可以用来存放链表长度)。

时间复杂度

查询操作:O(n)

插入/删除操作:O(1)

代码实现

#include
    
     #include
     
      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
      
       next;        j++;    }       //p&&j
       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
        
         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
         
          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"<
          
           data<<" "; p = p->next; } cout<