唐山网站制作价格,表白小程序制作,wordpress自定义属性,权威的唐山网站建设C语言实现单链表 简单描述代码运行结果 简单描述 用codeblocks编译通过 源码参考连接 https://gitee.com/IUuaena/data-structures-c.git
代码 common.h
#ifndef COMMON_H_INCLUDED
#define COMMON_H_INCLUDED#define ELEM_TYPE int //! 链表元素类型/*! brief 返回值类… C语言实现单链表 简单描述代码运行结果 简单描述 用codeblocks编译通过 源码参考连接 https://gitee.com/IUuaena/data-structures-c.git
代码 common.h
#ifndef COMMON_H_INCLUDED
#define COMMON_H_INCLUDED#define ELEM_TYPE int //! 链表元素类型/*! brief 返回值类型 */
typedef enum
{OK, //! 成功/正确NON_ALLOCATED, //! 内存分配失败NON_EXISTENT, //! 不存在ERROR //! 错误
} status_t;#endif // COMMON_H_INCLUDEDlinked_list.h
#ifndef LINKED_LIST_H_INCLUDED
#define LINKED_LIST_H_INCLUDED#include common.h/*! brief 链表结点 */
typedef struct linked_node
{ELEM_TYPE data; //! 数据项struct linked_node* next; //! 下一结点
} linked_node_t;typedef linked_node_t* linked_list_t; //! 链表status_t LinkedListCreate(linked_node_t** linked_list_head, ELEM_TYPE* elements, int elem_count);status_t LinkedListGetElem(linked_node_t* linked_list_head, int pos, ELEM_TYPE* elem);status_t LinkedListInsert(linked_node_t* linked_list_head, int pos, ELEM_TYPE elem);status_t LinkedListDelete(linked_node_t* linked_list_head, int pos, ELEM_TYPE* elem);status_t LinkedListMergeTwoSortedList(linked_node_t* list_a_head,linked_node_t* list_b_head,linked_node_t** merged_list_head);void LinkedListPrint(linked_node_t* linked_list_head);#endif // LINKED_LIST_H_INCLUDED linked_list.c
/*!* file linked_list.c* author CyberDash计算机考研, cyberdash163.com(抖音id:cyberdash_yuan)* brief 单链表头文件* version 1.0.0* date 2022-07-10* copyright Copyright (c) 2021* CyberDash计算机考研*/#include stdlib.h
#include stdio.h
#include linked_list.h/*!* brief **链表创建*** param linked_list_head **链表头结点**(指针)* param elements **数据项数组*** param elem_count **数据项数量*** return **执行结果*** note** 链表创建* -------* -------** - 链表头结点分配内存 \n* emsp; **if** 内存分配失败 : \n* emsp;emsp; 返回NON_ALLOCATED \n* - 链表头节点next设置为NULL \n* - 遍历数据项数组并插入链表结点 \n* emsp; **for loop** 遍历数据项数组(从后向前) : \n* emsp;emsp; 分配当前链表结点内存 \n* emsp;emsp; **if** 内存分配失败 : \n* emsp;emsp;emsp; 返回NON_ALLOCATED \n* emsp;emsp; 当前数据项elements[i]赋给当前链表结点的data \n* emsp;emsp; 链表头的next指向当前链表结点 \n*/
status_t LinkedListCreate(linked_node_t** linked_list_head, ELEM_TYPE* elements, int elem_count)
{*linked_list_head (linked_node_t*)malloc(sizeof(linked_node_t)); // 链表头结点分配内存if (!(*linked_list_head)){return NON_ALLOCATED;}(*linked_list_head)-next NULL;for (int i elem_count - 1; i 0; i--){linked_node_t* linked_node (linked_node_t*)malloc(sizeof(linked_node_t)); // 新结点分配内存if (!linked_node){return NON_ALLOCATED;}linked_node-data elements[i]; // elements[i]赋给新结点数据项linked_node-next (*linked_list_head)-next; // 新结点next赋值(*linked_list_head)-next linked_node; // linked_list_head-next指向新结点}return OK;
}/*!* brief **链表获取某位置的结点数据*** param linked_list_head **链表头结点**(指针)* param pos **位置*** param elem **保存结点数据项的变量**(指针)* return **执行结果*** note* 链表获取某位置的结点数据* ---------------------* ---------------------** - 初始化遍历指针cur和起始位置cur_post(从1开始, 区别于数组的从0开始) \n* - 遍历链表至位置pos \n* emsp; **while** 未遍历至位置pos : \n* emsp;emsp; cur指向后一个结点 \n* emsp;emsp; cur_pos加1 \n* - 边界条件判断 \n* **if** 遍历指针cur指向NULL 或者 cur_pos大于pos : \n* emsp; 返回NON_EXISTENT(不存在该位置的元素) \n* - 将位置pos的元素的data赋给参数elem指向的变量*/
status_t LinkedListGetElem(linked_node_t* linked_list_head, int pos, ELEM_TYPE* elem)
{linked_node_t* cur linked_list_head-next;int cur_pos 1;while (cur cur_pos pos){cur cur-next;cur_pos;}// 位置pos的结点不存在, 返回NON_EXISTENTif (!cur || cur_pos pos){return NON_EXISTENT;}*elem cur-data; // 将位置pos的数据项赋给*elemreturn OK;
}/*!* brief **链表插入*** param linked_list_head **链表头结点**(指针)* param pos **位置**(在这个位置前执行插入)* param elem **待插入的数据项*** return **执行结果*** note* 链表插入* -------* -------** - 初始化指针cur和insert_pos_predecessor \n* emsp; cur用来遍历, 找到插入位置的前一节点, insert_pos_predecessor用来找该节点的位置 \n* - 找到插入位置 \n* emsp; **while** cur不为NULL 或者 尚未遍历完整个链表 \n* emsp;emsp; cur指向下一个结点 \n* emsp;emsp; insert_pos_predecessor加1 \n* - 处理没有插入位置的情况 \n* emsp; **if** 插入位置不存在 \n* emsp;emsp; 返回ERROR \n* - 执行插入 \n* emsp; 分配结点内存 \n* emsp; **if** 内存分配失败 : \n* emsp;emsp; 返回NON_ALLOCATED \n* emsp; 插入节点设置data和next \n* emsp; cur-next指向插入节点 \n*/
status_t LinkedListInsert(linked_node_t* linked_list_head, int pos, ELEM_TYPE elem)
{linked_node_t* cur linked_list_head;int insert_pos_predecessor 0; // 插入位置的前一位置, 初始化为0// 遍历到插入位置的前一位置while(!cur || insert_pos_predecessor pos - 1){cur cur-next;insert_pos_predecessor;}// 如果插入位置不存在, 返回ERRORif (!cur || insert_pos_predecessor pos - 1){return ERROR;}// 插入结点分配内存linked_node_t* insert_node (linked_node_t*)malloc(sizeof(linked_node_t));if (!insert_node){return NON_ALLOCATED;}// 插入节点设置data和nextinsert_node-data elem;insert_node-next cur-next;// cur-next指向插入节点cur-next insert_node;return OK;
}/*!* brief **链表删除结点*** param linked_list_head **链表头结点**(指针)* param pos **删除结点位置*** param elem **被删除结点数据项的保存变量**(指针)* return **执行结果*** note* 链表删除结点* ----------* ----------* - 初始化变量delete_node_predecessor和delete_pos_predecessor \n* emsp; delete_node_predecessor(删除节点的前一节点指针)指向表头 \n* emsp; delete_pos_predecessor(删除节点的前一节点的位置)初始值为0 \n* - 遍历至被删除结点 \n* - 处理不存在删除结点的情况 \n* - 删除结点 \n* emsp; 指针delete_node指向delete_node_predecessor-next(被删除结点) \n* emsp; delete_node_predecessor-next指向被删除结点的next \n* emsp; 被删除结点的数据项赋给item \n* emsp; 调用free释放被删除结点 \n*/
status_t LinkedListDelete(linked_node_t* linked_list_head, int pos, ELEM_TYPE* elem)
{linked_node_t* delete_node_predecessor linked_list_head; // 待删除结点前一结点(指针), 初始化指向链表头结点int delete_pos_predecessor 0; // 待删除结点前一结点的位置, 初始化为0// 遍历到待删除结点的前一结点while(!(delete_node_predecessor-next) || delete_pos_predecessor pos - 1){delete_node_predecessor delete_node_predecessor-next;delete_pos_predecessor;}// 位置pos的结点不存在, 返回NON_EXISTENTif (!(delete_node_predecessor-next) || delete_pos_predecessor pos - 1){return NON_EXISTENT;}linked_node_t* delete_node delete_node_predecessor-next; // delete_node指向待删除结点delete_node_predecessor-next delete_node-next;*elem delete_node-data;free(delete_node); // 释放结点delete_node NULL; // 避免野指针return OK;
}/*!* brief **链表合并两个有序链表*** param list_a_head **a链表的头结点**(指针)* param list_b_head **b链表的头结点**(指针)* param merged_list_head **合并链表的头结点**(二级指针)* return **执行结果*** note* 链表合并两个有序链表* -----------------* -----------------* **注**: 有序链表a和有序链表b合并, 合并至a链表 \n* - 初始化链表a的遍历指针a_cur和链表b的遍历指针b_cur \n* emsp; a_cur指向链表a首元素结点 \n* emsp; b_cur指向链表b首元素结点 \n* - 初始化合并链表的遍历指针 \n* emsp; cur指向链表a头结点 \n* - 执行合并 \n* emsp; **while** 链表a和链表b都未合并完 : \n* emsp;emsp; **if** 链表a当前元素 链表b当前元素 : \n* emsp;emsp;emsp; 合并链表当前元素(cur)的next指向链表a当前元素 \n* emsp;emsp;emsp; 合并链表当前元素(cur)更新为链表a当前元素 \n* emsp;emsp;emsp; 链表a当前元素向后移动一位(next) \n* emsp;emsp; **else** (链表a当前元素 链表b当前元素) : \n* emsp;emsp;emsp; 合并链表当前元素(cur)的next指向链表a当前元素 \n* emsp;emsp;emsp; 合并链表当前元素(cur)更新为链表a当前元素 \n* emsp;emsp;emsp; 链表a当前元素向后移动一位(next) \n* - 剩余链表处理 \n* emsp; 如果链表a有剩余, 将链表a加到合并链表尾部 \n* emsp; 如果链表b有剩余, 将链表b加到合并链表尾部 \n*/
status_t LinkedListMergeTwoSortedList(linked_node_t* list_a_head,linked_node_t* list_b_head,linked_node_t** merged_list_head)
{linked_node_t* a_cur list_a_head-next;linked_node_t* b_cur list_b_head-next;*merged_list_head list_a_head;linked_node_t* cur list_a_head;while (a_cur b_cur){if (a_cur-data b_cur-data){cur-next a_cur;cur a_cur;a_cur a_cur-next;}else{cur-next b_cur;cur b_cur;b_cur b_cur-next;}}if (a_cur){cur-next a_cur;}if (b_cur){cur-next b_cur;}return OK;
}/*!* brief **打印链表*** param linked_list_head **链表头结点*** note* 打印链表* -------* -------* 遍历链表, 打印每一结点的数据项data \n*/
void LinkedListPrint(linked_node_t* linked_list_head)
{for (linked_node_t* cur linked_list_head-next; cur ! NULL; cur cur-next){printf(%d , cur-data);}printf(\n);
} main.c
#include stdio.h
#include stdlib.h
#include linked_list.hvoid TestLinkedListCreate() {printf(\n);printf(|------------------------ CyberDash ------------------------|\n);printf(| 测试链表的创建 |\n);ELEM_TYPE arr[6] { 1, 4, 2, 8, 5, 7 }; // 数据项数组linked_node_t* linked_list_head NULL; // 链表头结点linked_list_head初始化为NULLprintf(创建链表: );// 调用LinkedListCreate创建链表LinkedListCreate(linked_list_head, arr, sizeof(arr)/ sizeof(ELEM_TYPE));// 打印链表LinkedListPrint(linked_list_head);printf(\n-------------------------------------------------------------\n\n);
}/*!* brief **测试链表获取结点数据*** note* 测试链表获取结点数据* -----------------* -----------------* - 创建链表 \n* emsp; 使用数组[1, 4, 2, 8, 5, 7]创建链表 \n* - 获取某位置结点数据 \n* emsp; 获取并打印 \n*/
void TestLinkedListGetElem() {printf(\n);printf(|------------------------ CyberDash ------------------------|\n);printf(| 测试链表的获取元素 |\n);ELEM_TYPE arr[6] { 1, 4, 2, 8, 5, 7 }; // 数据项数组linked_node_t* linked_list_head NULL; // 链表头结点linked_list_head初始化为NULLprintf(创建链表: );// 调用LinkedListCreate创建链表LinkedListCreate(linked_list_head, arr, sizeof(arr) / sizeof(ELEM_TYPE));// 打印链表LinkedListPrint(linked_list_head);int pos 3;ELEM_TYPE data;LinkedListGetElem(linked_list_head, pos, data);printf(位置%d的结点, 数据项: %d\n, pos, data);printf(\n-------------------------------------------------------------\n\n);
}/*!* brief **测试链表删除结点*** note* 测试链表删除结点* --------------* --------------* - 创建链表 \n* emsp; 使用数组[1, 4, 2, 8, 5, 7]创建链表 \n* - 删除结点 \n* - 打印链表 \n*/
void TestLinkedListDelete() {printf(\n);printf(|------------------------ CyberDash ------------------------|\n);printf(| 测试链表的删除结点 |\n);ELEM_TYPE arr[6] { 1, 4, 2, 8, 5, 7 }; // 数据项数组linked_node_t* linked_list_head NULL; // 链表头结点linked_list_head初始化为NULL// 调用LinkedListCreate创建链表printf(创建链表: );LinkedListCreate(linked_list_head, arr, sizeof(arr) / sizeof(ELEM_TYPE));// 打印链表LinkedListPrint(linked_list_head);int delete_pos 4; // 删除结点位置ELEM_TYPE delete_node_elem 0; // 被删除结点数据项的保存变量printf(\n删除位置%d的结点(从1开始计数)\n\n, delete_pos);LinkedListDelete(linked_list_head, delete_pos, delete_node_elem);// 打印链表printf(删除结点后的链表: );LinkedListPrint(linked_list_head);printf(\n-------------------------------------------------------------\n\n);
}/*!* brief **测试链表插入结点*** note* 测试链表插入结点* --------------* --------------* - 创建链表 \n* emsp; 使用数组[1, 4, 2, 8, 5, 7]创建链表 \n* - 插入结点 \n* - 打印链表 \n*/
void TestLinkedListInsert() {printf(\n);printf(|------------------------ CyberDash ------------------------|\n);printf(| 测试链表的插入结点 |\n);ELEM_TYPE arr[6] { 1, 4, 2, 8, 5, 7 }; // 数据项数组linked_node_t* linked_list_head NULL; // 链表头结点linked_list_head初始化为NULL// 调用LinkedListCreate创建链表printf(创建链表: );LinkedListCreate(linked_list_head, arr, sizeof(arr) / sizeof(ELEM_TYPE));// 打印链表LinkedListPrint(linked_list_head);// 插入新元素LinkedListInsert(linked_list_head, 2, 9);LinkedListInsert(linked_list_head, 2, 10);LinkedListInsert(linked_list_head, 2, 11);// 打印链表printf(插入3个新结点后的链表: );LinkedListPrint(linked_list_head);printf(\n-------------------------------------------------------------\n\n);
}/*!* brief **测试链表有序链表合并*** note** (有序)链表合并* ------------* ------------* - 创建链表1 \n* emsp; 2 -- 4 -- 6 -- 8 \n* - 创建链表2 \n* emsp; 1 -- 3 -- 5 -- 7 -- 9 -- 10 \n* - 合并链表 \n* emsp; 1 -- 2 -- 3 -- 4 -- 5 -- 6 -- 7 -- 8 -- 9 -- 10 \n*/
void TestLinkedListMerge() {printf(\n);printf(|------------------------ CyberDash ------------------------|\n);printf(| 测试有序链表的合并 |\n);ELEM_TYPE elements1[4] { 2, 4, 6, 8 };ELEM_TYPE elements2[6] { 1, 3, 5, 7 , 9, 10};linked_node_t* linked_list_head1 NULL;linked_node_t* linked_list_head2 NULL;linked_node_t* merged_linked_list_head NULL;printf(创建链表1:\n);LinkedListCreate(linked_list_head1, elements1, sizeof(elements1) / sizeof(ELEM_TYPE));LinkedListPrint(linked_list_head1);printf(创建链表2:\n);LinkedListCreate(linked_list_head2, elements2, sizeof(elements2) / sizeof(ELEM_TYPE));LinkedListPrint(linked_list_head2);printf(合并链表:\n);LinkedListMergeTwoSortedList(linked_list_head1, linked_list_head2, merged_linked_list_head);LinkedListPrint(merged_linked_list_head);printf(\n-------------------------------------------------------------\n\n);
}int main()
{printf(你好!\n);TestLinkedListCreate();TestLinkedListGetElem();TestLinkedListDelete();TestLinkedListInsert();TestLinkedListMerge();return 0;
}运行结果
你好!|------------------------ CyberDash ------------------------|
| 测试链表的创建 |
创建链表: 1 4 2 8 5 7-------------------------------------------------------------|------------------------ CyberDash ------------------------|
| 测试链表的获取元素 |
创建链表: 1 4 2 8 5 7
位置3的结点, 数据项: 2-------------------------------------------------------------|------------------------ CyberDash ------------------------|
| 测试链表的删除结点 |
创建链表: 1 4 2 8 5 7删除位置4的结点(从1开始计数)删除结点后的链表: 1 4 2 5 7-------------------------------------------------------------|------------------------ CyberDash ------------------------|
| 测试链表的插入结点 |
创建链表: 1 4 2 8 5 7
插入3个新结点后的链表: 1 11 10 9 4 2 8 5 7-------------------------------------------------------------|------------------------ CyberDash ------------------------|
| 测试有序链表的合并 |
创建链表1:
2 4 6 8
创建链表2:
1 3 5 7 9 10
合并链表:
1 2 3 4 5 6 7 8 9 10-------------------------------------------------------------
