阅读量:0
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; } 思维导图
