数据结构day4

一、思维导图

二、课后练习

头文件

#ifndef LINKLIST_H
#define LINKLIST_H
#include <myhead.h>//定义数据类型
typedef int datatype;//定义节点类型
typedef struct Node
{union{int len; 			//头结点数据域datatype data; 		//普通节点数据域};struct Node *next; 		//指针域
}Node,*NodePtr;//创建链表
NodePtr list_create();//申请结点封装数据函数
NodePtr apply_node(datatype element);//链表判空
int list_empty(NodePtr L);//链表的头插
int list_insert_head(NodePtr L,datatype element);//链表的遍历
int list_show(NodePtr L);//通过位置查找
NodePtr list_search_pos(NodePtr L,int pos);//任意位置插入元素
int list_insert_pos(NodePtr L,int pos,datatype element);//链表的头删
int list_delete_head(NodePtr L);//任意位置删除元素
int list_delete_pos(NodePtr L,int pos);//按值查找返回位置
int list_search_element(NodePtr L,datatype element);//按位置修改元素
int list_update_pos(NodePtr L,int pos,datatype element);//按值修改元素
int list_update_element(NodePtr L,datatype target,datatype element);//链表的反转
void list_reverse(NodePtr L);//链表的反转(递归实现)
NodePtr list_reverse_recursion(NodePtr L);//链表去重
void list_delete_repeat(NodePtr L);//链表的排序
void list_sort(NodePtr L);//链表的销毁
void list_destroy(NodePtr L);#endif

链表的排序

//链表的排序
void list_sort(NodePtr L)
{//判断逻辑if(NULL == L || list_empty(L)){printf("排序失败\n");return;}//定义指针记录排序轮数NodePtr N = L;//定义两个指针分别指向新一轮排序的前面两个元素NodePtr p = N;NodePtr q = N->next;//冒泡排序交换数据域while(N){while(q->next){if(p->next->data < q->next->data){//交换数据域datatype temp = p->next->data;p->next->data = q->next->data;q->next->data = temp;}p = p->next;q = q->next;}N = N->next; 	//排序一轮，指针向后偏移}printf("排序成功\n");
}

链表逆序（递归）

//链表的反转(递归实现)
NodePtr list_reverse_recursion(NodePtr head)
{//head为第一个结点//判断逻辑if(NULL == head || head->next ==NULL){return head; 		//递归出口}//如果L不是最后一个节点，先找到最后一个节点NodePtr N = list_reverse_recursion(head->next);//下一个结点指针域指向自己head->next->next = head;//当前结点指针域置空head->next = NULL;//将最后一个结点地址向前传递return N;
}

链表去重

//链表去重
void list_delete_repeat(NodePtr L)
{//判断逻辑if(NULL == L || L->next ==NULL){printf("去重失败\n");return;}NodePtr p = L;while(p != NULL && p->next !=NULL){if(p->data == p->next->data){NodePtr temp = p->next;p->next = p->next->next;free(temp);//表长变化L->len--;}else{p = p->next;}}printf("去重成功\n");}