線性表(鏈式存儲)

順序表包括兩種存儲方式:1.順序存儲，隨機讀取(順序表).2.隨機存儲，順序讀取(鏈式表)  
[cpp] view plaincopy
//單鏈表的實現 
#include <iostream> 
#include <stdlib.h> 
using namespace std; 
typedef int ElemType; 
struct List 
{ 
    ElemType data; 
    List *next; 
}; 
void InitList(List *&HL)//初始化線性表 
{ 
    HL=NULL; 
} 
void ClearList(List *&HL)//刪除線性表 
{ 
    List *cp,*np; 
    cp=HL; 
    while(cp) 
    { 
        np=cp->next; 
        delete cp; 
        cp=np; 
    } 
    HL=NULL; 
} 
int LengthList(List *HL)//得到單鏈表的長度 
{ 
    int i=0; 
    while(HL) 
    { 
        i++; 
        HL=HL->next; 
    } 
    return i; 
} 
bool EmptyList(List *HL)//檢測單鏈表是否為空 
{ 
    return HL==NULL; 
} 
ElemType GetList(List *HL,int pos)//得到單鏈表中第pos個結點中的元素 
{ 
    if(pos<1) 
    { 
        cout<<"pos is invalid"<<endl; 
        exit(1); 
    } 
    int i=0; 
    while(HL) 
    { 
        i++; 
        if(i==pos) break; 
        HL=HL->next; 
    } 
    if(HL) 
        return HL->data; 
    else 
    { 
        cout<<"pos is out range"<<endl; 
        exit(1); 
    } 
} 
void TraverseList(List *HL)//遍歷單鏈表 
{ 
    while(HL) 
    { 
        cout<<HL->data<<" "; 
        HL=HL->next; 
    } 
    cout<<endl; 
} 
bool FindList(List *HL,ElemType &item)//查找是否具有該元素 
{ 
    while(HL) 
    { 
        if(HL->data==item) 
        { 
            item=HL->data; 
            return true; 
        } 
        else HL=HL->next; 
    } 
    return false; 
} 
bool UpdateList(List *HL,const ElemType &item)//更新某個元素 
{ 
    while(HL) 
    { 
        if(HL->data==item) break; 
        else HL=HL->next; 
    } 
    if(!HL) return false; 
    else 
    { 
        HL->data=item; 
        return true; 
    } 
} 
bool InsertList(List *&HL,ElemType item,int pos)//插入一個元素 
{ 
    if(pos<-1) 
    { 
        cout<<"pos is invalid"<<endl; 
        return false; 
    } 
    List *newpt; 
    newpt=new List; 
    newpt->data=item; 
    List *cp=HL,*ap=NULL; 
    if(pos==0) 
    { 
        while(cp) 
        { 
            if(item<cp->data) break; 
            else 
            { 
                ap=cp; 
                cp=cp->next; 
            } 
        } 
    } 
    else if(pos==-1) 
    while(cp) 
    { 
        ap=cp; 
        cp=cp->next; 
    } 
    else 
    { 
        int i=0; 
        while(cp) 
        { 
            i++; 
            if(i==pos) break; 
            else 
            { 
                ap=cp; 
                cp=cp->next; 
            } 
        } 
        if(cp==NULL&&i+1<pos) 
        { 
            cout<<"pos is rang out"<<endl; 
            return false; 
        } 
    } 
    if(ap==NULL) 
    { 
        newpt->next=HL; 
        HL=newpt; 
    } 
    else 
    { 
        newpt->next=cp; 
        ap->next=newpt; 
    } 
    return true; 
} 
bool DeleteList(List *&HL,ElemType &item,int pos) 
{ 
    if(HL==NULL) 
    { 
        cout<<"List is Empty!"<<endl; 
        return false; 
    } 
    if(pos<-1) 
    { 
        cout<<"pos is invalid"<<endl; 
        return false; 
    } 
    List *cp=HL,*ap=NULL; 
    if(pos==0) 
    { 
        while(cp!=NULL) 
        { 
            if(item==cp->data) break; 
            else 
            { 
                ap=cp; 
                cp=cp->next; 
            } 
        } 
        if(cp==NULL) 
        { 
            cout<<"List is not node to delete!"<<endl; 
            return false; 
        } 
    } 
    else if(pos==-1) 
    while(cp) 
    { 
        ap=cp; 
        cp=cp->next; 
    } 
    else 
    { 
        int i=0; 
        while(cp!=NULL) 
        { 
            i++; 
            if(i==pos) break; 
            else 
            { 
                ap=cp; 
                cp=cp->next; 
            } 
        } 
        if(cp==NULL) 
        { 
            cout<<"pos value is invalid"<<endl; 
            return false; 
        } 
    } 
    if(ap==NULL) HL=HL->next; 
    else ap->next=cp->next; 
    delete cp; 
    return true; 
} 
int main() 
{ 
    return 0; 
}