2024.7.19 作业

1.链表的排序

int list_sort(NodePtr L)
{if(NULL==L || L->len<=1){printf("排序失败");return -1;}int len=L->len+1;NodePtr p;int i,j;for( i=1;i<len;i++){for( j=0,p=L;j<len-i;j++,p=p->next){if( p->data > p->next->data ){datatype t=p->data;p->data=p->next->data;p->next->data=t;}}}printf("排序成功\n");return 0;
}

2.链表的反转（递归实现）

// 递归反转链表  
NodePtr list_fz(NodePtr L) 
{  // 基础情况：空链表或只有一个节点  if (L == NULL || L->next == NULL) {  return L;  }  NodePtr new_L = list_fz(L->next);  L->next->next = L;  L->next = NULL;return new_L; 
}

3.链表去重

// 去重函数
int list_dr(NodePtr L) 
{NodePtr current = L;NodePtr prev = NULL;while (current != NULL) {NodePtr runner = L;prev = NULL;int flag = 0;// 查找当前节点的重复项while (runner != current) {if (runner->data == current->data) {flag = 1;break;}prev = runner;runner = runner->next;}if (flag) {// 如果是重复节点，删除当前节点NodePtr temp = current;if (prev != NULL) {prev->next = current->next;} else {L = current->next; // 更新头节点}current = current->next;free(temp);} 	else 	{current = current->next;}}
}

linklist.h

#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 e);//链表判空
int list_empty(NodePtr L);//头插
int list_insert_head(NodePtr L,datatype e);//链表遍历函数
int list_show(NodePtr L);//通过位置查找节点
NodePtr list_search_pos(NodePtr L,int pos);//任意位置插入
int list_insert_pos(NodePtr L,int pos,datatype e);//链表头删
int list_delete_head(NodePtr L);//任意位置删除
int list_delete_pos(NodePtr L,int pos);//通过值查找返回位置
int list_search_value(NodePtr L,datatype e);//链表按位置进行修改
int list_update_pos(NodePtr L,int pos,datatype e);//链表按值进行修改
int list_update_value(NodePtr L,datatype old_e,datatype new_e);//将链表进行翻转
void list_reverse(NodePtr L);//释放链表
void list_destroy(NodePtr L);//链表排序
int list_sort(NodePtr L);// 去重函数
int list_dr(NodePtr head);// 递归反转链表 
NodePtr list_fz(NodePtr L);#endif

linklist.c

#include "linklist.h"NodePtr list_create()
{NodePtr L=(NodePtr)malloc(sizeof(Node));if(NULL==L){printf("创建失败\n");return NULL;}L->len=0;L->next=NULL;printf("链表创建成功\n");return L;
}//申请节点封装数据函数
NodePtr apply_node(datatype e)
{NodePtr p=(NodePtr)malloc(sizeof(Node));if(NULL==p){printf("申请失败\n");return NULL;}p->data = e;p->next = NULL;return p;
}//链表判空
int list_empty(NodePtr L)
{return L->next ==NULL;
}//头插
int list_insert_head(NodePtr L,datatype e)
{if(NULL==L){printf("链表不合法\n");return -1;}NodePtr p = apply_node(e);if(NULL==p){return -1;}p->next=L->next;L->next=p;L->len++;printf("头插成功\n");return 0;}//链表遍历函数
int list_show(NodePtr L)
{if(NULL==L || list_empty(L)){printf("遍历失败\n");return -1;}	NodePtr q = L->next;while(q!=NULL){printf("%d\t",q->data);q=q->next;}putchar(10);
}//通过位置查找节点
NodePtr list_search_pos(NodePtr L,int pos)
{if(NULL==L || list_empty(L) || pos<0 || pos>L->len){printf("查找失败\n");return NULL;}NodePtr q= L;for(int i=0;i<pos;i++){q=q->next;}return q;
}//任意位置插入
int list_insert_pos(NodePtr L,int pos,datatype e)
{if(NULL==L || pos<=0 ||pos>L->len+1){printf("插入失败\n");return -1;}NodePtr p = apply_node(e);if(NULL==p){return -1;}NodePtr q =list_search_pos(L,pos-1);p->next=q->next;q->next=p;L->len++;printf("插入成功\n");return 0;
}//链表头删
int list_delete_head(NodePtr L)
{if(NULL==L || list_empty(L)){printf("删除失败\n");return -1;}NodePtr p=L->next;L->next=p->next;free(p);p=NULL;L->len--;printf("头删成功\n");return 0;
}//任意位置删除
int list_delete_pos(NodePtr L,int pos)
{if(NULL==L || list_empty(L) || pos<1 || pos>L->len){printf("删除失败\n");return -1;}NodePtr q=list_search_pos(L,pos-1);NodePtr p=q->next;q->next =p->next;free(p);p=NULL;L->len--;printf("删除成功\n");return 0;
}//通过值查找返回位置
int list_search_value(NodePtr L,datatype e)
{if(NULL==L || list_empty(L)){printf("查找失败\n");return -1;}NodePtr q=L->next;for(int index=1;index<=L->len;index++){if(q->data==e){return index;}q=q->next;}printf("没找到\n");return -1;
}//链表按位置进行修改
int list_update_pos(NodePtr L,int pos,datatype e)
{if(NULL==L || list_empty(L) || pos<1 || pos>L->len ){printf("修改失败\n");return -1;}list_search_pos(L,pos)->data = e;printf("修改成功\n");return 0;
}//链表按值进行修改
int list_update_value(NodePtr L,datatype old_e,datatype new_e)
{if(NULL==L || list_empty(L)){printf("修改失败\n");return -1;}int res = list_search_value(L,old_e);if(res == -1){printf("没有要修改的值\n");return -1;}list_update_pos(L,res,new_e);printf("修改成功\n");return 0;}//将链表进行翻转
void list_reverse(NodePtr L)
{if(NULL==L || L->len<=1){printf("翻转失败\n");return;}NodePtr H = L->next;L->next = NULL;NodePtr p = NULL;while(H!=NULL){p=H;H=H->next;p->next =L->next;L->next =p;}printf("翻转成功\n");return;
}//释放链表
void list_destroy(NodePtr L)
{//判断逻辑if(NULL == L){return;}//将所有结点进行释放while(!list_empty(L)){//头删list_delete_head(L);}//释放头结点free(L);L = NULL;printf("释放成功\n");
}//链表排序
int list_sort(NodePtr L)
{if(NULL==L || L->len<=1){printf("排序失败");return -1;}int len=L->len+1;NodePtr p;int i,j;for( i=1;i<len;i++){for( j=0,p=L;j<len-i;j++,p=p->next){if( p->data > p->next->data ){datatype t=p->data;p->data=p->next->data;p->next->data=t;}}}printf("排序成功\n");return 0;
}// 递归反转链表  
NodePtr list_fz(NodePtr L) 
{  // 基础情况：空链表或只有一个节点  if (L == NULL || L->next == NULL) {  return L;  }  NodePtr new_L = list_fz(L->next);  L->next->next = L;  L->next = NULL;return new_L; 
} // 去重函数
int list_dr(NodePtr L) 
{NodePtr current = L;NodePtr prev = NULL;while (current != NULL) {NodePtr runner = L;prev = NULL;int flag = 0;// 查找当前节点的重复项while (runner != current) {if (runner->data == current->data) {flag = 1;break;}prev = runner;runner = runner->next;}if (flag) {// 如果是重复节点，删除当前节点NodePtr temp = current;if (prev != NULL) {prev->next = current->next;} else {L = current->next; // 更新头节点}current = current->next;free(temp);} 	else 	{current = current->next;}}
}

main.c

#include"linklist.h"int main(int argc, const char *argv[])
{//调用函数创建一个链表NodePtr L = list_create();if(NULL == L){return -1;}//调用头插函数list_insert_head(L, 520);list_insert_head(L, 1314);list_insert_head(L, 666);list_insert_head(L, 999);//调用遍历函数list_show(L);//调用任意位置插入函数list_insert_pos(L, 1, 100);list_insert_pos(L, 3, 100);list_insert_pos(L, L->len+1, 100);list_show(L);printf("排序: ");list_sort(L);list_show(L);printf("去重：");list_dr(L);list_show(L);printf("反转：");L->next=list_fz(L->next);list_show(L);return 0;
}

思维导图