学习嵌入式第十九天

链表（续上）

1.单向链表

6.链表的查找

在链表中找到指定的第一个元素

• 遍历链表节点，判断是否为要找的节点
• 符合条件的返回该节点地址
• 如果遍历结束没有找到元素，返回空

linknode *search_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.链表的修改

将链表节点的旧元素改为新元素

void change_linklist(linknode *phead, datatype tmpdata,datatype overdata){linknode *ptmpnode = NULL;ptmpnode = phead->pnext;while(ptmpnode != NULL){if(ptmpnode->data == tmpdata){ptmpnode->data = overdata;}ptmpnode = ptmpnode->pnext;}return;}

8.链表的尾插法

• 申请节点空间，将节点中地址赋值为NULL，将数据存放到节点
• 找到最后一个节点
• 将最后一个节点的pnext赋值为新申请节点的地址

void insert_tail_linklist(linknode *phead,datatype tmpdata){linknode *ptmpnode = NULL;linknode *pnewnode = NULL;pnewnode = malloc(sizeof(linknode));pnewnode->data = tmpdata;pnewnode->pnext = NULL;ptmpnode = phead;while(ptmpnode->pnext != NULL){ptmpnode = ptmpnode->pnext;}ptmpnode->pnext = pnewnode; return;
}

9.链表的销毁

将链表节点全部释放

• 定义两个指针ptmpnode和pprenode指向头节点
• ptmpnode指向ptmpnode->pnext
• 释放掉pfreenode指向的节点
• 将pfreenode指向ptmpnode指向的空间

int destroy_linklist(linknode **pphead){linknode *pfreenode = NULL;linknode *ptmpnode = NULL;ptmpnode = *pphead;pfreenode = *pphead;while(ptmpnode != NULL){ptmpnode = ptmpnode->pnext;free(pfreenode);pfreenode = ptmpnode;}*pphead = NULL;return 0;
}

10.查找链表中间节点

• 快指针pfast每次走两步，慢指针pslow每次走一步
• 快指针走到末尾的时候，慢指针刚好走到中间

linknode *find_minnode_linklist(linknode *phead){linknode *pfast = NULL;linknode *pslow = NULL;pfast = phead->pnext;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个元素

linknode *find_knode_linklist(linknode *phead,int k){int i = 0;linknode *pfast = NULL;linknode *pslow = NULL;pfast = phead->pnext;while(i < k && pfast != NULL){pfast = pfast->pnext;i++;}if(NULL == pfast){return NULL;}pslow = phead->pnext;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);pnextnode = NULL;
}

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.链表的排序

1.冒泡排序

• 定义两个指针ptmpnode1，ptmpnode2用作比较，定义一个指针pend记录每轮排序的最后节点
• 指针循环向后走，直到ptmpnode2为NULL，即等于pend，循环停止
• pend赋值为ptmpnode1的节点地址，下一轮就可以少比一次
• 循环将所有大的元素找到，剩余一个最小元素

void bubblesort_linklist(linknode *phead){linknode *ptmpnode = NULL;linknode *pprenode = NULL;linknode *pend = NULL;int tmpdata = 0;int flag = 1;if(phead->pnext == NULL || phead->pnext->pnext == NULL){return;}while(flag){flag = 0;pprenode = phead->pnext;ptmpnode = phead->pnext->pnext;while(ptmpnode != pend){if(pprenode->data > ptmpnode->data){tmpdata = pprenode->data;pprenode->data = ptmpnode->data;ptmpnode->data = tmpdata;flag = 1;}pprenode = ptmpnode;ptmpnode = ptmpnode->pnext;}pend = pprenode;}return;
}   

2.选择排序

• pswapnode指向要交换的节点
• pminnode假设的最小值
• ptmpnode和后续节点比较

void selectsort_linklist(linknode *phead){linknode *ptmpnode = NULL;linknode *pswapnode = NULL;linknode *pminnode = NULL;datatype tmpdata;if(phead->pnext == NULL || phead->pnext->pnext == NULL){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 = pswapnode->data;pswapnode->data = pminnode->data;pminnode->data = tmpdata;}pswapnode = pswapnode->pnext;}return;
}

15.判断链表是否有环

1. 判断链表是否有环
   • 定义两个指针：快指针(每次走两步)和慢指针(每次走一步)
   • 快指针-慢指针 == 环长，快指针和慢指针相等即为链表有环
2. 计算环的环长
   • 定义一个指针从环相遇点开始走一圈，直到走到该节点为止
   • 每走一个节点计数，最终得到环长
3. 找到环入口的位置
   • 起点到环入口的距离 = 相遇点到环入口的距离 + （n-1） * 环长
   • 定义一个指针从相遇点开始每次走一步，定义一个指针从开头每次走一步
   • 两个指针相遇的位置几位环入口位置

int circle_linklist(linknode *phead,int *pis_circle,int *pcirlen,linknode **ppnode){linknode *pfast = NULL;linknode *pslow = NULL;linknode *ptmpnode = NULL;linknode *pstartnode = NULL;int cnt = 1;
/*判断是否有环*/pfast = phead->pnext;pslow = phead->pnext;while(1){pfast = pfast->pnext;if(NULL == pfast){break;}pfast = pfast->pnext;if(NULL == pfast){break;}pslow = pslow->pnext;if(pfast == pslow){break;}}if(NULL == pfast){*pis_circle = 0;return 0;}else{*pis_circle = 1;}/*计算环长*/ptmpnode = pslow->pnext;while(ptmpnode != pslow){cnt++;ptmpnode = ptmpnode->pnext;}*pcirlen = cnt;/*找到环的起始节点*/pstartnode = phead->pnext;ptmpnode = pslow;while(pstartnode != ptmpnode){pstartnode = pstartnode->pnext;ptmpnode = ptmpnode->pnext;}*ppnode = ptmpnode;return 0;
}

2.双向链表

1.节点定义

typedef int datatype;typedef struct node{datatype data;struct node *ppre;struct node *pnext;
}linknode;

2.创建节点

参考单向链表创建

• 申请节点空间
• 对pnext和ppre赋值为NULL
• 返回空白节点地址

linknode *create_empty_linklist(void){linknode *ptmpnode = NULL;ptmpnode = alloc(sizeof(linknode));if(NULL == ptmpnode){perror("fail to malloc");return NULL;}ptmpnode->ppre = NULL;ptmpnode->pnext = NULL;return ptmpnode;
}

3.链表的头插法

• 申请节点
• 存放数据
• pnext赋值为phead->pnext
• ppre赋值为phead的地址
• phead->pnext赋值为新申请节点地址
• 如果有后一个节点，需要让后一个节点的ppre指向该节点

习题

实现双向链表的基本操作

1. 创建

   代码实现：

   linknode *create_empty_linklist(void){linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));if(ptmpnode == NULL){perror("fail to malloc");return NULL;}ptmpnode->ppre = NULL;ptmpnode->pnext = NULL;return ptmpnode; 
   }
   

2. 销毁

   代码实现：

   int destory_linklist(linknode **pphead){linknode *ptmpnode = NULL;linknode *pnextnode = NULL;ptmpnode = *pphead;pnextnode = *pphead;while(ptmpnode != NULL){pnextnode = pnextnode->pnext;free(ptmpnode);ptmpnode = pnextnode;}*pphead = NULL;
   }
   

3. 头插法

   代码实现：

   int insert_head_linklist(linknode *phead,datatype tmpdata){linknode *ptmpnode = NULL;ptmpnode = malloc(sizeof(linknode));if(ptmpnode == NULL){perror("fail to malloc");return -1;}ptmpnode->data = tmpdata;ptmpnode->pnext = phead->pnext;phead->pnext = ptmpnode;ptmpnode->ppre = phead;if(ptmpnode->pnext != NULL){ptmpnode->pnext->ppre = ptmpnode;}return 0;
   }
   

4. 遍历

   代码实现：

   int show_linklist(linknode *phead){linknode *ptmpnode = NULL;ptmpnode = phead->pnext;while(ptmpnode != NULL){printf("%d ",ptmpnode->data);ptmpnode = ptmpnode->pnext;}printf("\n");
   }
   

5. 查找

   代码实现：

   linknode *find_linklist(linknode *phead,datatype tmpdata){linknode *ptmpnode = NULL;ptmpnode = phead->pnext;while(ptmpnode != NULL){if(ptmpnode->data == tmpdata){printf("%d ",ptmpnode->data);}ptmpnode = ptmpnode->pnext;}printf("\n");return NULL;
   }
   

6. 修改

   代码实现：

   int update_linklist(linknode *phead, datatype olddata, datatype
   newdata){linknode *ptmpnode = NULL;ptmpnode = phead->pnext;while(ptmpnode != NULL){if(ptmpnode->data == olddata){ptmpnode->data = newdata;}ptmpnode = ptmpnode->pnext;}return 0;
   }
   

7. 删除

   代码实现：

   int delete_linklist(linknode *phead, datatype tmpdata){linknode *ptmpnode = NULL;linknode *pprenode = NULL;ptmpnode = phead->pnext;pprenode = phead;while(ptmpnode != NULL){if(ptmpnode->data == tmpdata){pprenode->pnext = ptmpnode->pnext;free(ptmpnode);pprenode->pnext->ppre = pprenode;ptmpnode = pprenode->pnext;}else{pprenode = ptmpnode;ptmpnode = ptmpnode->pnext;}}return 0;