C言語はデータ構造と双方向リンク操作を実現する.
4591 ワード
データ構造 双方向チェーンの実現
双方向リンクテーブルの各ノードは、2つのポインタドメインを含み、1つのポインタドメインは、その後続のノードの記憶アドレスを保存し、他のポインタ領域は、その前駆ノードの記憶アドレスを保存する.
双方向リンク結点のタイプ説明:
ここで、prorドメインは、その前駆者ノードの記憶アドレスであり、nextドメインは、その後継者ノードの記憶アドレスである.
双方向チェーンは二つの特徴があります.
一つは二つの方向からある結点を検索することができます.これにより、チェーンのいくつかの操作(挿入や削除など)が簡単になります.第二に、前のチェーンを利用しても、後のチェーンを使っても、全双方向チェーンを巡回することができます.
双方向チェーンの操作は基本的にシングルチェーンの操作と同じです.
1.ヘッド挿入法によって率先して接合する双方向チェーン表Create_DinkListF(int n)
3.結点指定前に新しい結点Insert_を挿入するDlinkListBefore(DuLink List p,ElemType x)
読んでくれてありがとうございます.みなさんのご協力をお願いします.ありがとうございます.
双方向リンクテーブルの各ノードは、2つのポインタドメインを含み、1つのポインタドメインは、その後続のノードの記憶アドレスを保存し、他のポインタ領域は、その前駆ノードの記憶アドレスを保存する.
双方向リンク結点のタイプ説明:
//
typedef int ElemType;
typedef struct node{
ElemType data;
struct node *prior,*next;
}DuLNode,*DuLinkList;
ここで、prorドメインは、その前駆者ノードの記憶アドレスであり、nextドメインは、その後継者ノードの記憶アドレスである.
双方向チェーンは二つの特徴があります.
一つは二つの方向からある結点を検索することができます.これにより、チェーンのいくつかの操作(挿入や削除など)が簡単になります.第二に、前のチェーンを利用しても、後のチェーンを使っても、全双方向チェーンを巡回することができます.
双方向チェーンの操作は基本的にシングルチェーンの操作と同じです.
1.ヘッド挿入法によって率先して接合する双方向チェーン表Create_DinkListF(int n)
//
DuLinkList Create_DLinkListF(int n){
DuLinkList L,p;
int i = n - 1;
ElemType x;
//
L = (DuLinkList)malloc(sizeof(DuLNode));
L->prior = NULL;
L->next = NULL;
//
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
L->next = p;
p->prior = L;
p->next = NULL;
//
while(i > 0){
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
p->next = L->next;
L->next->prior = p;
p->prior = L;
L->next = p;
i--;
}
return L;
}
2.テールインサート法によって率先して接合する双方向リンク表Create_DinkListR(int n)
//
DuLinkList Create_DLinkListR(int n){
DuLinkList L,p,lastNode;
int i = n - 1;
ElemType x;
//
L = (DuLinkList)malloc(sizeof(DuLNode));
L->prior = NULL;
L->next = NULL;
//
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
L->next = p;
p->prior = L;
p->next = NULL;
lastNode = p;
//
while(i > 0){
scanf("%d",&x);
p = (DuLinkList)malloc(sizeof(DuLNode));
p->data = x;
lastNode->next = p;
p->prior = lastNode;
p->next = NULL;
lastNode = p;
i--;
}
return L;
}
3.結点指定前に新しい結点Insert_を挿入するDlinkListBefore(DuLink List p,ElemType x)
//
void Insert_DLinkListBefore(DuLinkList p,ElemType x){
DuLinkList newNode;
// p :
if(p->prior == NULL)
printf(" ,
");
else{
newNode = (DuLinkList)malloc(sizeof(DuLNode));
newNode->data = x;
newNode->next = p;
p->prior->next = newNode;
newNode->prior = p->prior;
p->prior = newNode;
}
}
4.結点指定後に新たな結点Insert_を挿入するDlinkListAfter(DuLink List p,ElemType x)
//
void Insert_DLinkListAfter(DuLinkList p,ElemType x){
DuLinkList newNode;
newNode = (DuLinkList)malloc(sizeof(DuLNode));
newNode->data = x;
//
if(p->next == NULL){
p->next = newNode;
newNode->prior = p;
newNode->next = NULL;
}
else{
newNode->next = p->next;
p->next->prior = newNode;
p->next = newNode;
newNode->prior = p;
}
}
5.指定された結点Delete_を削除する.DlinkList(DulinkList p)
//
void Delete_DLinkList(DuLinkList p){
//
if(p->next == NULL)
p->prior->next = NULL;
else{
p->prior->next = p->next;
p->next->prior = p->prior;
}
free(p);
}
6.後鎖出力双方向チェーン表Print_DlinkListN(DulinkList L)
//
void Print_DLinkListN(DuLinkList p){
while(p != NULL){
printf("%d\t",p->data);
p = p->next;
}
printf("
");
}
7.前鎖出力双方向チェーン表Print_DlinkListP(DulinkList p)
//
void Print_DLinkListP(DuLinkList p){
while(p != NULL){
printf("%d\t",p->data);
p = p-prior;
}
printf("
");
}
双方向チェーンの他の操作については、位置決めのように、単一チェーンテーブルの操作と類似しています.読んでくれてありがとうございます.みなさんのご協力をお願いします.ありがとうございます.