C言語はデータ構造と双方向リンク操作を実現する.

4591 ワード

データ構造  双方向チェーンの実現
双方向リンクテーブルの各ノードは、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("
"); }
双方向チェーンの他の操作については、位置決めのように、単一チェーンテーブルの操作と類似しています.
読んでくれてありがとうございます.みなさんのご協力をお願いします.ありがとうございます.