1.單向鏈表
6.鏈表的查找
在鏈表中找到指定的第一個元素
- 沿用遍歷思想，每次訪問一個節點元素判斷是否為要找的節點
- 符合條件返回該節點地址
- 到最后沒有找到符號條件的節NULL
linknode *find_linklist(linknode *phead, datatype tmpdata) {linknode *ptmpnode = NULL;ptmpnode = phead->pnext;while(ptmpnode != NULL){if(ptmpnode->data == tmpdata){return ptmpnode;}else{ptmpnode = ptmpnode->pnext;}}return NULL; }
7.鏈表的修改
沿用遍歷思想，找到需要修改的節點
/*更換鏈表老元素為新元素*/ int update_linklist(linknode *phead, datatype olddata, datatype newdata) {linknode *ptmpnode = phead->pnext;while(ptmpnode != NULL){if(ptmpnode->data == olddata){ptmpnode->data = newdata;ptmpnode = ptmpnode->pnext;}else{ ptmpnode = ptmpnode->pnext; }}return 0; }
8.尾插法
在鏈表結尾插入一個元素
- 申請節點空間
- 將數據存放到節點中
- 將節點中地址賦值為NULL
- 找到最后一個節點
- 最后一個節點的pnext賦值為新申請節點
int insert_tail_linklist(linknode *phead, datatype tmpdata) {linknode *ptmpnode = NULL;linknode *pnewnode = NULL;ptmpnode = phead; //從空白節點開始找pnewnode = malloc(sizeof(linknode));if(NULL == pnewnode){perror("fail to malloc");return -1;}while(ptmpnode->pnext != NULL){ptmpnode = ptmpnode->pnext;}pnewnode->data = tmpdata;pnewnode->pnext = NULL;ptmpnode->pnext = pnewnode;return 0; }
?9.鏈表的銷毀
- 定義兩個指針pfreenode和ptmpnode都指向頭結點
- ptmpnode向后走
- 再釋放pfreenode指向的節點
- 再將pfreenode指向ptmpnode指向的空間
void destroy_linklist(linknode **pphead) {linknode *ptmpnode = NULL;linknode *pfreenode = NULL;pfreenode = *pphead;ptmpnode = *pphead;while(ptmpnode != NULL){ptmpnode = ptmpnode->pnext;free(pfreenode);pfreenode = ptmpnode;}*pphead = NULL;return; }
10.查找鏈表的中間節點
- 快指針每次走2步，慢指針每次走1步
- 快指針走到末尾，慢指針走到中間
linknode *find_midnode(linknode *phead) {linknode *pfast = NULL;linknode *pslow = NULL;pfast = pslow = phead->pnext;while(pfast != NULL){pfast = pfast->pnext;if(pfast == NULL){break;} pfast = pfast->pnext;if(pfast == NULL){break;}pslow = pslow->pnext;}return pslow; }
11.查找鏈表倒數第k個節點
- 快指針先走k步
- 慢指針和快指針每次走一步
- 快指針到達末尾，慢指針少走k步，即倒數第k個元素
/*查找鏈表倒數第k個節點*/ linknode *find_last_kth_node(linknode *phead, int k) {int i = 0;linknode *pfast = NULL;linknode *pslow = NULL;pfast = phead->pnext;pslow = phead->pnext;for(i = 0; i < k && pfast != NULL; i++){pfast = pfast->pnext;}if(pfast == NULL){return NULL;}while(pfast != NULL){pfast = pfast->pnext;pslow = pslow->pnext;}return pslow; }
12.不知道頭節點地址，如何刪除鏈表中間節點
- 將指針指向的下一個節點的值覆蓋當前節點的值
- 刪除下一個節點
void delete_linknode(linknode *ptmpnode) {linknode *pnextnode = NULL;pnextnode = ptmpnode->pnext;ptmpnode->data = pnextnode->data;ptmpnode->pnext = pnextnode->pnext;free(pnextnode);return; }
13.鏈表的倒置
將鏈表所以元素倒置
- 將原鏈表斷開
- 將所有的元素依次使用頭插法插入
void reverse_linklist(linknode *phead) {linknode *ptmpnode = NULL;linknode *pinsertnode = NULL;//將鏈表從頭結點斷開ptmpnode = phead->pnext;phead->pnext = NULL;//依次將所有元素使用頭插法插入鏈表while(ptmpnode != NULL){pinsertnode = ptmpnode;ptmpnode = ptmpnode->pnext;pinsertnode->pnext = phead->pnext;phead->pnext = pinsertnode;}return; }
14.鏈表的排序
冒號排序
- 采用冒號排序思想，定義兩個指針，相鄰兩個元素比較
- 指針循環向后走，直到ptmnode2為NULL，即等于pend，循環停止
- pend賦值為ptmpnode1的節點地址
- 下一輪就可以少比一次
void bubble_sort_linklist(linknode *phead) {linknode *ptmpnode1 = NULL;linknode *ptmpnode2 = NULL;linknode *pend = NULL;datatype tmpdata;if(NULL == phead->pnext || NULL == phead->pnext->pnext){return;}while(1){ptmpnode1 = phead->pnext;ptmpnode2 = phead->pnext->pnext;if(ptmpnode2 == pend){break;}while(ptmpnode2 != pend){if(ptmpnode1->data > ptmpnode2->data){tmpdata = ptmpnode1->data;ptmpnode1->data = ptmpnode2->data;ptmpnode2->data = tmpdata;}ptmpnode1 = ptmpnode1->pnext;ptmpnode2 = ptmpnode2->pnext;}pend = ptmpnode1;}return; }選擇排序
- pswapnode指向要交換的節點
- pminnode假設的最小值
- ptmpnode和后續節點比較
void select_sort_linklist(linknode *phead) {linknode *pminnode = NULL;linknode *pswapnode = NULL;linknode *ptmpnode = NULL;datatype tmpdata;if(NULL == phead->pnext || NULL == phead->pnext->pnext){return;}pswapnode = phead->pnext;while(pswapnode->pnext != NULL){pminnode = pswapnode;ptmpnode = pswapnode->pnext;while(ptmpnode != NULL){if(ptmpnode->data < pminnode->data){pminnode = ptmpnode;}ptmpnode = ptmpnode->pnext;}if(pminnode != pswapnode){tmpdata = pminnode->data;pminnode->data = pswapnode->data;pswapnode->data = tmpdata;}pswapnode = pswapnode->pnext;}return; }
15.判斷鏈表是否有環
- 判斷鏈表是否有環
- 計算環長
- 找到環的入口位置
判斷是否有環
- 定義兩個指針：快指針（每次2步）和慢指針（每次走1步）
- 快指針-慢指針 == 環長即相遇， 快指針和慢指針相等即為鏈表有環
計算環長
- 定義一個指針從環相遇開始走一圈，知道走到該節點為止
- 每走一個節點計數，最終得到環長
獲得環的入口位置
- 定義一個指針，從相遇點開始每次走一步，定義一個指針，從開頭每次走一步
- 兩個指針相遇即為環入口
2.雙向鏈表
1.創建空鏈表
參考單向鏈表的創建
linknode *creat_empty_linlist(void) {linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));if(NULL == ptmpnode){perror("fail to malloc");return NULL;}ptmpnode->pnext = NULL;ptmpnode->ppre = NULL;return ptmpnode; }
)
