Zi 字媒體

[C/C++ 演算法]-資料結構與演算法(文魁)：雙向鏈結串列以陣列為表示的使用範例   線上執行結果：http://www.tutorialspoint.com/compile_c_online.php code2html：http://tohtml.com/     /* =============== Program Description =============== */ /* 程式名稱 : 9_3.cpp */ /* 程式目的 : 雙向鏈結串列以陣列為表示的使用範例 */ /* 輸 入 : 整數陣列資料 */ /* 輸 出 : 反轉的整數陣列資料,搜尋鍵值的位置 */ /* =================================================== */ #define n 10 #define INVALID_LINK -2 /* 無效的連結 */ #define NULL_LINK -1 /* 結尾的連結 */ // 宣告標頭檔 #include "stdio.h" // 宣告全域變數 int A[n][3]; int head = -1; int tail = -1; // 宣告函式原型 // 利用傳值的方式把整數data傳進addDNode函式中 void addDNode(int data); // 利用傳值的方式把整數data傳進delDNode函式中 void delDNode(int data); // 從findDNode函式中回傳一個整數 int findDNode(int data); void main(void) { int D[n]={1,2,3,4,5,6,7,8,9,0}; int i,ret; for(i=0;i<n;i++) A[i][0]=0; for(i=0;i<n;i++) A[i][1]=INVALID_LINK; for(i=0;i<n;i++) A[i][2]=INVALID_LINK; // 輸入的資料 printf(" Input Data : "); for(i=0;i<n;i++) { printf("%d",D[i]); addDNode(D[i]); } printf("\n"); // 鏈結序列中的資料 printf(" Data in LinkList : "); i=head; do { if(i==NULL_LINK) break; printf("%d",A[i][0]); i=A[i][1]; }while((i!=INVALID_LINK)||(i!=NULL_LINK)); printf("\n"); // 尋找節點 ret = findDNode(D[4]); if(ret==-1) printf("%d is not find \n",D[4]); else printf(" Find %d from queue => array index %d\n",D[4],ret); // 刪除節點 printf(" Delete Data from queue "); for(i=0;i<n;i=i+2) { printf("%d",D[i]); delDNode(D[i]); } printf("\n"); // 鏈結序列中的資料 printf(" Data in LinkList : "); i=head; do { if(i==NULL_LINK) break; printf("%d",A[i][0]); i=A[i][1]; }while((i!=INVALID_LINK)||(i!=NULL_LINK)); printf("\n"); // 尋找節點 ret = findDNode(D[4]); if(ret==-1) printf("%d is not find \n",D[4]); else printf(" Find %d from queue = %d\n",D[4],ret); getchar(); } // 由開頭新增節點 void addDNode(int data) { int i; if(head==NULL_LINK) { head=0; A[head][0]=data; A[head][1]=NULL_LINK; A[head][2]=NULL_LINK; }else{ for(i=0;i<n;i++) { if(A[i][1]==INVALID_LINK) /* 空的節點 */ { A[i][0]=data; A[head][2]=i; /* 把原本開頭的上一個指向新增節點 */ A[i][1]=head; /* 把新增節點的下一個指向原本開頭節點 */ A[i][2]=NULL_LINK; /* 把新增節點的下一個指向尾巴 */ head=i; return; } } printf("LinkArray is Full!\n"); } } // 刪除節點 void delDNode(int data) { int pre=head,ptr=head,i; for(i=0;i<n;i++) { if(A[ptr][0]==data) break; pre = ptr; ptr=A[ptr][1]; } if(ptr==NULL_LINK) /* 沒有找到 */ printf("Node is not found!\n"); else{ if(ptr==head) /* 找到的節點��開頭 */ { head=A[ptr][1]; A[ptr][0]=0; A[ptr][1]=INVALID_LINK; }else{ /* 找到的節點不��開頭 */ A[pre][1]=A[ptr][1]; A[ptr][0]=0; A[ptr][1]=INVALID_LINK; A[ptr][2]=INVALID_LINK; } } } // 尋找節點,往後尋找 int findDNode(int data) { int i,ptr=head; /* 從鏈結串列的頭開始看 */ for(i=0;i<n;i++) { if(A[ptr][0]==data) /* 搜尋成功 */ return ptr; else if(A[ptr][1]==NULL_LINK) /* 沒有節點了 */ break; ptr=A[ptr][1]; /* 指向後一個節點 */ } return -1; /* 搜尋失敗 */ }