データ構造C(4):循環チェーンテーブル、双方向チェーンテーブル、双方向チェーンテーブルの挿入、削除

一、循環チェーンテーブル

循環チェーンテーブルは、ヘッダと終端が接続するチェーンテーブル(すなわち、テーブルの最後のノードのポインタ領域がヘッダノードを指し、チェーンテーブル全体がリングを形成する)

である.

の利点:テーブルのいずれかのノードからテーブルの他のノード

を見つけることができる.

注意:ループチェーンテーブルにNULLポインタがないため、ループ操作に関わる場合、その終了条件は非ループチェーンテーブルのようにpまたはp->nextが空であるか否かを判断するのではなく、ヘッダポインタ

に等しいか否かを判断する.

サイクル条件p!=NULL → p!=L p->next!=NULL → p->next!=L単鎖フォーム循環チェーンテーブル

テールポインタ付きループチェーンテーブルのマージ

LinkList Connect(LinkList Ta,LinkList Tb)
{
    p=Ta->next;
    Ta->next=Tb->next->next;
    delete Tb->next;
    Tb->next=p;
    return Tb;
}

二、双方向チェーンテーブル

双方向チェーンテーブル:単一チェーンテーブルの各ノードにその前駆を指すポインタドメインpriorを追加することで、チェーンテーブルに2つの方向の異なるチェーンが形成されるので、双方向チェーンテーブル

と呼ぶ.

双方向ループチェーンテーブル:単一チェーンのループテーブルと同様に、双方向チェーンテーブルにもループテーブルがあります.

ヘッドノードの前駆体ポインタをチェーンテーブルの最後のノード

に向ける.

最後のノードの後続ポインタをヘッドノード

に向ける.

双方向チェーンテーブル構造の対称性:p->prior->next=p=p->next->prior

三、双方向チェーンテーブルの挿入

void ListInsert_DuL(DuLinkList &L,int i,ElemTyoe e)
{
    if(!(p=GetElemP_DuL(L,i)))
        return ERROR;
    s=new DuLNode;
    s->date=e;
    s->prior=p->prior;
    p->prior->next=s;
    s->next=p;
    p->prior=s;
    return OK;
}

四、双方向チェーンテーブルの削除

void ListDelete_DuL(DuLink &L,int i,ElemType &e)
{
    if(!(p=GetElemP_DuL(L,i)))
        return ERROR;
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    return OK;
}