リニア・テーブルの基本操作

リニアテーブルは最も簡単で、最も基本的なリニアデータ構造です.2つのストレージ方法があります.シーケンステーブルとチェーンテーブルです.一般的には12種類の基本操作があり、主な基本操作は挿入、削除、検索などです.私はここで順序表と単鎖表のこの12種類の操作を自分の理解で書いて、2つの対照的に見ると少し良いはずです.
リニアテーブル12の基本動作
準備(次もこのように比較して、説明はしません)
シーケンステーブル(Sq-SequenceList):

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef char ElemType;  //  ！
typedef struct{
    ElemType *elem;   //           
    int length;       //        
    int listsize;     //              （ ElemType   ）
    int incrementsize;//        （ ElemType   ）
}SqList;

void ErrorMassage(char *s)          //     s      
{
    cout<exit(1);
}
/*      &e *e   :      ，         ，     ，           ;
                      ，             */
//(SqList &L)              &，    

void ListIncrement(SqList &L)       //      L.incrementsize     
{
    realloc(L.elem,(L.listsize+L.incrementsize)*sizeof(ElemType));
    L.listsize+=L.incrementsize;
    return;
}

シングルチェーンテーブル(L-LinkList):
特に説明します:私が作成した単鎖表は空の頭の結点があって、直接最初の結点を取って頭の結点をするのではありませんて、この点は本科の本の上のと違います

typedef char ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

void ErrorMassage(char *s)                      //     s      
{
    cout<exit(1);
}

一、InitList(&L):空のシーケンステーブルLを構築する

void InitList_Sq(SqList &L)         //         L，         
{
    L.elem=new ElemType[LIST_INIT_SIZE];
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    L.incrementsize=LISTINCREMENT;
    return;
}

void InitList_L(LinkList &L,int n)              //            
{
    LNode *p,*q;
    L=new LNode;
    for(int i=0;i<n;i++)
    {
        q=new LNode;
        q->data='A'+i;   //->      
        if(i>0)
            p->next=q;
        else
            L->next=q;
        p=q;
    }
    q->next=NULL;                               //    z   ，            
    return;
}

二、ListInsert(&L,i,e):i番目の要素の前に新しい要素eを挿入する

void ListInsert_Sq(SqList &L,int i,ElemType e) //   e       i     
{
    if(i<1||i>L.length+1) ErrorMassage("i is invalid!");
    if(L.length>=L.listsize) ListIncrement(L);
    ElemType *p,*q;
    p=&L.elem[i-1];
    for(q=&L.elem[L.length-1];q>=p;q--)
        *(q+1)=*q;
    *p=e;
    L.length++;     //       L   1
    return;
}

void ListInsert_L(LinkList &L,LNode *q,LNode *s) // q      s
{
    LNode *p=L;
    for(;p->next!=q&&p->next;p=p->next);
    s->next=p->next;
    p->next=s;
    return;
}

三、ListDelete(&L,i,&e):i番目の要素を削除し、eに格納する

void ListDelete_Sq(SqList &L,int i,ElemType &e)  //  L  i   ，  e    
{
    if(i<1||i>L.length) ErrorMassage("i is invalid!");
    ElemType *q;
    e=L.elem[i-1];
    for(q=&L.elem[i-1];q<=&L.elem[L.length-1];q++)
        *q=*(q+1);
    L.length--;     //       L   1
    return;
}

void ListDelete_L(LinkList &L,LNode *q,ElemType &e) //  L  q  ，  e       
{
    LNode *p;
    p=L;
    for(;p->next!=q&&p->next;p=p->next);
    p->next=p->next->next;
    e=q->data;
    delete q;
    return;
}

四、LocateElem(L,e):eと等しい1番目の要素のビットシーケンスを返す

int LocateElem_Sq(SqList L,ElemType e) //  L  1  e        ，     0
{
    int i;
    for(i=0;ilength;i++)
        if(L.elem[i]==e) return i+1;
    if(i==L.length) return 0;
}

int LocateElem_L(LinkList L,ElemType e)         //  L  1  e       ，      0
{
    LNode *p;
    int i;
    p=L->next;
    for(i=1;p;i++,p=p->next)
        if(p->data==e)
            return i;
    return 0;
}

五、GetElem(L,i,&e):i番目の要素の値をeで返す

void GetElem_Sq(SqList L,int i,ElemType &e) // e  L  i     
{
    if(i<1||i>L.length) ErrorMassage("i is invalid!");
    e=L.elem[i-1];
    return;
}

void GetElem_L(LinkList L,int i,ElemType &e)    // e  L  i        
{
    if(i<1||i>ListLength_L(L))
        ErrorMassage("i is invalid!");
    LNode *p;
    p=L->next;
    for(int j=1;j!=i&&p;p=p->next,j++);
    e=p->data;
    return;
}

六、DestroyList(&L):リニアテーブルLを破棄する

void DestroyList_Sq(SqList &L)      //     
{
    delete []L.elem;
    L.length=0;     //         0，     0
    L.listsize=0;
    return;
}

void DestroyList_L(LinkList &L)                 //    
{
    LNode *p,*q;
    q=L->next;
    while(q)
    {
        p=q->next;
        delete q;
        q=p;
    }
    delete L;
    return;
}

七、ListLength(L):L中の要素の個数を返す

int ListLength_Sq(SqList L)         //     L     
{
    return L.length;
}

int ListLength_L(LinkList L)                    //  L       
{
    LNode *q;
    int l=0;
    q=L->next;
    while(q)
    {
        l++;
        q=q->next;
    }
    return l;
}

八、ListTraverse(L):Lの各要素を順次出力する

void ListTraverse_Sq(SqList L)      //    L      
{
    int i=0;
    if(L.length<=0) return;
    for(i=0;ilength-1;i++)
        cout<"  ";
    cout<return;
}

void ListTraverse_L(LinkList L)                 //          
{
    LNode *q;
    q=L->next;
    while(q)
    {
        cout<<q->data<<"  ";
        q=q->next;
    }
    cout<<endl;
    return;
}

九、ClearList(&L):Lを空のテーブルにリセット

void ClearList_Sq(SqList &L)         // L    
{
    for(int i=0;ilength;i++)
        L.elem[i]='\0';
    L.length=0;     //        0
    return;
}

void ClearList_L(LinkList &L)                   // L    ，       
{
    DestroyList_L(L->next);
    L->next=NULL;
    return;
}

十、LIstEmpty(L):Lが空のテーブルである場合はTrueを返し、そうでない場合はFalseを返す

bool ListEmpty_Sq(SqList L)         //  L     ，    true，    false
{
    if(L.length==0) return true;
    else return false;
}

bool ListEmpty_L(LinkList L)                    //  L     ，      
{
    int i;
    LNode *p;
    p=L->next;
    for(i=0;p;p=p->next,i++);
    if(i)
        return false;
    else
        return true;
}

十一、PriorElem(L,cur_e,&pre_e):用pre_eはcur_を返すeの前駆

ElemType PriorElem_Sq(SqList L,ElemType e)  //  e     ， e        L          
{
    int i=LocateElem_Sq(L,e);
    if(i<=1) ErrorMassage("No priorelem!");
    else return L.elem[i-2];
}

LNode* PriorElem_L(LinkList L,ElemType cur_e) //  cur_e     ，         
{
    LNode *p;
    p=L->next;
    if(LocateElem_L(L,cur_e)<=1)    // cur_e  L     e L      
        ErrorMassage("No priornode!");
    while(p->next->data!=cur_e)
        p=p->next;
    return p;
}

十二、NextElem(L,cur_e,&next_e):後継を返す

ElemType NextElem_Sq(SqList L,ElemType e)   //  e     ， e         L          
{
    int i=LocateElem_Sq(L,e);
    if(i==0||i==L.length) ErrorMassage("No nextelem!");
    else return L.elem[i];
}

LNode* NextElem_L(LinkList L,ElemType cur_e)  //  cur_e     ，         
{
    LNode *p;
    p=L->next;
    int i=LocateElem_L(L,cur_e);
    if(i<1||i>=ListLength_L(L))     // cur_e  L          
        ErrorMassage("No nextelem!");
    for(;p->data!=cur_e;p=p->next);
    return p->next;
}