华清数据结构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

原文地址：https://blog.csdn.net/m0_62859255/article/details/140574732

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！