华清数据结构day4 24-7-19

链表的相关操作

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);
//链表的排序
int list_sort(NodePtr L);
//链表的翻转（递归函数实现）
NodePtr list_reserve1(NodePtr L);
//释放链表
void list_destroy(NodePtr L);
#endif

linklist.c

#include "linklist.h"
NodePtr list_create() //链表的创建
{NodePtr L = (NodePtr)malloc(sizeof(Node));if (L == NULL){printf("创建失败\n");return NULL;}L->len = 0;L->next = NULL;printf("链表创建成功\n");return L;
}NodePtr apply_node(datatype e) //申请新元素
{NodePtr new = (NodePtr)malloc(sizeof(Node));if (new == NULL){printf("申请失败\n");}new->data = e;new->next = NULL;return new;
}
int list_empty(NodePtr L) //判空
{return L->next == NULL;
}//头插
int list_insert_head(NodePtr L, datatype e)
{if (L == NULL){printf("没有创建表\n");return -1;}NodePtr new = apply_node(e);if (new == NULL){return -1;}new->next = L->next;L->next = new;L->len++;printf("头插成功\n");return 0;
}
//链表遍历函数
int list_show(NodePtr L)
{if (L == NULL){printf("遍历失败\n");return -1;}printf("元素分别为");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 p = L;for (int i = 0; i < pos; i++){p = p->next;}return p;
}
//任意位置插入
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 = L;for (int i = 0; i < pos - 1; i++){p = p->next;}NodePtr new = apply_node(e);if (NULL == new){return -1;}new->next = p->next;p->next = new;L->len++;printf("插入成功\n");return 0;
}
//链表头删
int list_delete_head(NodePtr L)
{if (L == NULL || 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 p = list_search_pos(L, pos - 1);NodePtr q = p->next;p->next = p->next->next;free(q);q = 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 p = L->next;for (int i = 0; i < L->len; i++){if (p->data == e){return i;}p = p->next;}printf("没找到\n");return -1;
}
//链表按位置进行修改
int list_update_pos(NodePtr L, int pos, datatype e)
{if (L == NULL || list_empty(L) || pos < 1 || pos > L->len){printf("修改失败\n");return -1;}NodePtr p = list_search_pos(L, pos);p->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;}NodePtr p = L->next;for (int i = 0; i < L->len; i++){if (p->data == old_e){p->data = new_e;}p = p->next;}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");
}
//链表的排序
int list_sort(NodePtr L)
{if (NULL == L || L->len <= 1){printf("排序失败\n");return -1;}NodePtr p = L->next;for (int i = 1; i < L->len; i++){for (int j = 0; j < L->len - i; j++){if (p->data > p->next->data){int temp = p->data;p->data = p->next->data;p->next->data = temp;}p = p->next;}p = L->next;}printf("排序成功\n");return 0;
}
//链表的翻转（递归函数实现）
NodePtr list_reserve1(NodePtr L)
{if(NULL == L || L->next->next == NULL){return L;}NodePtr q = list_reserve1(L->next);L->next->next = L;L->next = NULL;return q;
}
//释放链表
void list_destroy(NodePtr L)
{if (NULL == L){return;}while (!list_empty(L)){list_delete_head(L);}free(L);L = NULL;printf("销毁成功\n");
}

main.c

#include "linklist.h"
int main(int argc, const char *argv[])
{NodePtr L = list_create();if (L == NULL){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);//调用排序函数list_sort(L);list_show(L);//调用头删函数list_delete_head(L);list_delete_head(L);list_show(L);//调用按位置查找位置NodePtr res = list_search_pos(L, 2);if (res != NULL){printf("您要找的数据的值是%d\n", res->data);}//调用删除函数list_delete_pos(L, 1);list_delete_pos(L, 2);list_delete_pos(L, L->len);list_show(L);//调用按值查找位置int index = list_search_value(L, 666);if (index != -1){printf("您要找的数据在链表的第%d个位置\n", index + 1);}//调用按位置进行修改函数list_update_pos(L, 1, 12345);list_show(L);//调用按值修改函数list_update_value(L, 12345, 6789);list_show(L);//调用翻转函数list_reverse(L);list_show(L);//调用翻转函数NodePtr retPtr = list_reserve1(L);list_show(retPtr);//调用释放函数list_destroy(L);L = NULL;return 0;
}
a