データ構造C(4):循環チェーンテーブル、双方向チェーンテーブル、双方向チェーンテーブルの挿入、削除
5554 ワード
一、循環チェーンテーブル循環チェーンテーブルは、ヘッダと終端が接続するチェーンテーブル(すなわち、テーブルの最後のノードのポインタ領域がヘッダノードを指し、チェーンテーブル全体がリングを形成する) である.の利点:テーブルのいずれかのノードからテーブルの他のノード を見つけることができる.注意:ループチェーンテーブルにNULLポインタがないため、ループ操作に関わる場合、その終了条件は非ループチェーンテーブルのようにpまたはp->nextが空であるか否かを判断するのではなく、ヘッダポインタ に等しいか否かを判断する.サイクル条件p!=NULL → p!=L p->next!=NULL → p->next!=L単鎖フォーム循環チェーンテーブル テールポインタ付きループチェーンテーブルのマージ
二、双方向チェーンテーブル双方向チェーンテーブル:単一チェーンテーブルの各ノードにその前駆を指すポインタドメインpriorを追加することで、チェーンテーブルに2つの方向の異なるチェーンが形成されるので、双方向チェーンテーブル と呼ぶ.双方向ループチェーンテーブル:単一チェーンのループテーブルと同様に、双方向チェーンテーブルにもループテーブルがあります. ヘッドノードの前駆体ポインタをチェーンテーブルの最後のノード に向ける.最後のノードの後続ポインタをヘッドノード に向ける.
双方向チェーンテーブル構造の対称性:p->prior->next=p=p->next->prior 三、双方向チェーンテーブルの挿入
四、双方向チェーンテーブルの削除
LinkList Connect(LinkList Ta,LinkList Tb)
{
p=Ta->next;
Ta->next=Tb->next->next;
delete Tb->next;
Tb->next=p;
return Tb;
}
二、双方向チェーンテーブル
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;
}