Zi 字媒體

[C/C++ 演算法]-資料結構與演算法(文魁)：鏈結串列以陣列為表示的使用範例   線上執行結果：http://www.tutorialspoint.com/compile_c_online.php code2html：http://tohtml.com/   /* =============== Program Description =============== */ /* 程式名稱 : 9_2.cpp */ /* 程式目的 : 鏈結串列以陣列為表示的使用範例 */ /* 輸 入 : 整數陣列資料 */ /* 輸 出 : 反轉的整數陣列資料,搜尋鍵值的位置 */ /* =================================================== */ #define n 10 #define INVALID_LINK -2 /* 無效的連結 */ #define NULL_LINK -1 /* 結尾的連結 */ // 宣告標頭檔 #include "stdio.h" // 宣告全域變數 int A[n][2]; int head = -1; // 宣告函式原型 // 利用傳值的方式把整數data傳進addNode函式中 void addNode(int data); // 利用傳值的方式把整數data傳進delNode函式中 void delNode(int data); // 從findNode函式中回傳一個整數 int findNode(int data); // 無回傳值,無傳入值 void inverse(void); 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; // 輸入的資料 printf(" Input Data : "); for(i=0;i<n;i++) { printf("%d",D[i]); addNode(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"); // 反轉鏈結序列中的資料 printf(" Inverse Data in LinkList : "); inverse(); 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 = findNode(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]); delNode(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 = findNode(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 addNode(int data) { int i; if(head==NULL_LINK) { head=0; A[head][0]=data; A[head][1]=NULL_LINK; }else{ for(i=0;i<n;i++) { if(A[i][1]==INVALID_LINK) /* 空的節點 */ { A[i][0]=data; A[i][1]=head; head=i; return; } } printf("LinkArray is Full!\n"); } } // 刪除節點 void delNode(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; } } } // 尋找節點 int findNode(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; /* 搜尋失敗 */ } void inverse(void) { int ptr0,ptr1,ptr2; if(head==NULL_LINK) return; else { ptr0=head; /* 第0個節點的位置 */ if(A[ptr0][1]==NULL_LINK) return; ptr1=A[ptr0][1]; /* 第1個節點的位置 */ ptr2=A[ptr1][1]; /* 第2個節點的位置 */ A[ptr0][1]=NULL_LINK; /* 第0個節點的連結指向尾巴 */ do { A[ptr1][1]=ptr0; /* 第1個節點的連結指向第0個節點 */ ptr0 = ptr1; ptr1 = ptr2; ptr2 = A[ptr1][1]; }while(ptr2!=NULL_LINK); A[ptr1][1]=ptr0; head=ptr1; } }