数据结构（C++）—

顺序表和链表的比较

　　1.存取方式

　　　　顺序表可以随机访问，而链表只能从表头顺序查找。（因此经常查找顺序表某一个元素时，顺序表更适合）

　　2.逻辑结构与物理结构

　　　　顺序表中，逻辑上相邻的元素，其物理存储位置也相邻。链表中，逻辑相邻的元素，其物理存储位置不相邻。

　　3.查找、插入和删除操作

　　　　按值查找时，顺序表链表时间复杂度都为O(n)。

　　　　按序号查找时，顺序表时间复杂度为O(1)，而链表时间复杂度为O(n)。

　　　　插入和删除元素中，顺序表平均移动半个表的长度，而链表只需要改变一下指针域的值就可以了。

　　　　（因此，当线性表经常进行插入和删除元素时，选链表更合适）

　　4.空间分配

　　　　顺序表在静态存储分配的情形下，存储空间装满了就不能扩充；链表就不存在这个问题。

链表结构

typedef int ElemType; 

typedef struct Node{

    ElemType data;

    struct Node *next;

}*LinkList,*PNode;

头插法创建单链表

LinkList HeadInsertList(LinkList L){

    //头插法创建单链表，头插法简单，但元素的顺序是插入顺序的逆序

    L=new Node;    //分配头节点空间

    L->next=NULL;  //头结点的next指针刚开始指向NULL 

    if(!L){        //分配失败时，返回NULL

        return L;

    }

    LinkList s;

    ElemType x;

    cin>>x;

    while(x!=9999){     //输入9999停止输入

        s=new Node;    //插入的节点

        if(!s){

            cout<<"内存分配失败!"<<endl;

            return NULL;

        }

        s->data=x;

        s->next=L->next;

        L->next=s;

        cin>>x;

    }

    return L;

}

尾插法创建单链表

LinkList TailInsertList(LinkList L){

    //尾插法创建单链表，链表的顺序和插入顺序一样，但需要尾指针

    L=new Node;

    if(!L){

        cout<<"内存分配失败！"<<endl;

        return L;

    }

    LinkList r,s;

    r=L;            //r为尾节点，每次指向最后一个节点 

    ElemType x;

    cin>>x;

    while(x!=9999){

        s=new Node;

        if(!s){

            cout<<"内存分配失败！"<<endl;

            return NULL;

        }

        s->data=x;

        r->next=s;

        r=s;

        cin>>x;

    }

    r->next=NULL;   //最后要将尾节点指针指控 

    return L;

}

按序号返回节点的指针

PNode GetElem(LinkList L,int i){

    //按序号返回节点的指针

    int j=0;     //刚开始p指向头节点

    PNode p=L;

    if(i<0){

        return NULL;

    }

     while(j<i&&p!=NULL){  //节点和序号一起移动

         p=p->next;

         j++;

     }  

     return p;  //查找失败时，p为NULL

}

返回链表中第一个元素为e节点的指针

PNode FindElem(LinkList L,ElemType e){

    //返回链表中第一个元素为e节点的指针

    PNode p=L->next;

     while(p&&p->data!=e){  //从第一个节点开始，元素不为e时，就向后推一位

         p=p->next;

     }

     return p;   //没找到元素时，返回NULL

}

将e插入第i个节点上

void InsertList(LinkList L,ElemType e,int i){

    //将e插入第i个节点上

    PNode p=GetElem(L,i-1);  //找到前驱元的位置

    if(!p){

        return ;

    } 

    PNode s;

    s=new Node;

    if(s==NULL){

        cout<<"内存分配失败！"<<endl;

        return ;

    } 

    s->data=e;

    s->next=p->next;

    p->next=s;

}

删除第i个节点

void DeleteList(LinkList L,int i){

    //删除第i个节点

    PNode p=GetElem(L,i-1);

    PNode q=p->next;

    p->next=q->next;

    delete q; 

}

求链表的长度

int LengthList(LinkList L){

    //求链表的长度

    PNode p=L;

    int i=0;    //计数器变量 

    if(L==NULL){

        return 0;

    }

    while(p->next!=NULL){

        p=p->next;

        i++;

    } 

    return i;

}

利用递归删除链表中值为x的节点

void Delete1(LinkList &L,ElemType x){

    //利用递归删除链表中值为x的节点

    PNode p;

    if(L==NULL){

        return ;

    }

    if(L->data==x){

        p=L;

        L=L->next;

        delete p;

        Delete1(L,x);

    }else {

        Delete1(L->next,x);

    }

}

删除链表中值为x的节点

void Delete2(LinkList &L,ElemType x){

    //删除链表中值为x的节点

    PNode p=L->next,pre=L,det;

     while(p!=NULL){

         if(p->data==x){

             det=p;         //det指向的是要删除的节点

             pre->next=p->next;  //pre指向的是要删除结点的前一个结点

             p=p->next;

             delete det;

         }

         else{

             p=p->next;

             pre=pre->next;

         }

     }

}

巴特西

数据结构（C++）——链表

最新文章

热门文章