单向链结串列的反转.ppt

單向鏈結串列 Singly Linked Lists 定義及表示法 節點包含資料（data）及鏈結（link）兩個欄位。 其資料結構表示，如下圖所示 head：指向串列前端之指標 tail：指向串列尾端之指標 鏈結串列透過儲存元素在記憶體之位址為指標(Pointer)或鏈結(Link)取得下一個節點。故 節點=資料+指標鏈結 假設有一節點結構如下圖所示： 則其節點結構可定義如下： typedef struct node{ /*以結構體表示節點*/ int data; /*data儲存節點資料項目*/ struct node *next; } NODE; /*next儲存下一個節點位址*/ /*NODE表新定義之節點結構資料型態*/ 一個指標變數head當作鏈結串列之起始指標，其宣告如下： NODE *head;  /*head為一個指標，指向鏈結串列之起始節點*/ 基本運作及圖解 單向鏈結串列的釋放 當使用malloc配置了記憶體之後，記憶體會一直存在直到程式結束，所以當不使用時必須釋放，釋放的方法為free(變數名稱)；請務必記得釋放記憶體，雖然不會發生錯誤訊息，可是會一直在記憶體中，導致記憶體的浪費。 單向鏈結串列插入 如果打算在鏈結中加入一個新的節點，可以使用以下的方法，比方說有一個鏈結串列如下： 單向鏈結串列刪除 如果打算在鏈結中刪除節點，可以使用以下的方法： 比方說有一個鏈結串列如下： 單向鏈結串列的反轉 如果鏈結串列如下： 每一次迴圈次需要使用3個節點，把第2個節點的next指向第1個節點， 下一次的第一個節點是這一次的第二個節點 下一次的第二個節點是這一次的第三個節點 下一次的第三個節點是這一次的第三個節點的next 基本運算的演算法與程式 產生新節點 C語言程式 NODE *getnode (void) /* 此函數產生一個新節點*/ { NODE *p; p　= (NODE *) malloc(sizeof(NODE)); /* malloc會動態地配置大小為sizeof 的記憶體*/ /* sizeof會傳回一個型態為NODE之值*/ if ( p == NULL) { printf (“記憶體不足”); exit(1); } return(p); } 歸還一個節點 C語言程式 void *freenode(NODE*p) /*此函數將節點還給記憶體*/ { free(p); } 尋找一個節點 C語言程式 NODE search_node (NODE *p, int num ) /*自節點p之後尋找一個節點其data項目為 search_data之值*/ { 　 NODE *q; q = p-next; 　 /*q指向節點p之後第一個節點*/ while( q!= NULL q-data != num) q = q-next; /*q改指向下一個節點*/ 　return(q); } 鍵結串列的節點走訪 C語言程式 NODE find_node(NODE *head, int num) { NODE *ptr; ptr = head; /*指向串列起始*/ while ( ptr != NULL ) /*走訪串列*/ { if ( ptr-num == num ) /*找尋data*/ return (ptr); ptr = ptr-next; } /*指向下一節點*/ return (ptr); } 計算鏈結串列之長度 C語言程式 int length (NODE *p ) /*此函數計算節點p之後之長度*/ { int num=0; NODE *q = p-next; While (q != NULL) { num ++; q = q-next; } return(num); } 節點之插入 由鏈結串列加入一個節點一個節點之插入有三種情況： 節點加於第一個節點之前 節點加於最後一個節點之後 加於節點中間任何一個位置 圖解 虛擬碼 NODE *insert_node ( NODE *head, NODE *ptr, int value) { 配置記憶體給new; if (ptr is NULL) 插入第一個節點； else if ( ptr-next = = NULL ) 插入最後一個節點； else