[数据结构]：02 |
您所在的位置：网站首页 › c语言实现链表结构 › [数据结构]：02 |
[数据结构]：02
|
目录 前言 已完成内容 单链表实现 01-开发环境 02-文件布局 03-代码 01-主函数 02-头文件 03-LinkedListCommon.cpp 04-LinkedListPositionOperation.cpp 05-LinkedListValueOperation.cpp 结语 前言此专栏包含408考研数据结构全部内容，除其中使用到C++引用外，全为C语言代码。使用C++引用主要是为了简化指针的使用，避免二重指针的出现。 已完成内容[数据结构]：01-顺序表（C语言实现）_Chandni.的博客-CSDN博客 [数据结构]：17-双链表（带头结点）（C语言实现）_Chandni.的博客-CSDN博客 单链表实现 01-开发环境语言：C/C++14 编译器：MinGW64 集成开发环境：CLion2022.1.3 02-文件布局请在CLion集成开发环境中创建C++可执行程序，否则无法运行，原因上面已解释。 用于测试和初始化单链表。 #include "./Head/LinkedListData.h" #include "./Source/LinkedListCommon.cpp" #include "./Source/LinkedListPositionOperation.cpp" #include "./Source/LinkedListValueOperation.cpp" int main() { LinkedList L; // 为方便测试，这里选择使用数组形式创建单链表 int array[MaxSize] = {1, 2, 3, 4, 5, 2, 2, 3, 0}; int select = 1;// 0表示头插法创建；1表示尾插法创建 LinkedListCreate(L, array, select); LinkedListPrint(L); printf("-----------------------------\n"); // 按位置操作 // // 查询 int position = 2, value; // LinkedListSearchPosition(L, position, value); // printf("Search Value = %d\n", value); // printf("-----------------------------\n"); // // // 插入 // ElemType insertValue = 80; // position = 3; // LinkedListInsertPosition(L, position, insertValue); // LinkedListPrint(L); // printf("-----------------------------\n"); // // // 修改 // ElemType modifyValue = 30; // position = 1; // LinkedListModifyPosition(L, position, modifyValue); // LinkedListPrint(L); // printf("-----------------------------\n"); // // // 删除 // position = 3; // ElemType deleteValue; // LinkedListDeletePosition(L, position, deleteValue); // LinkedListPrint(L); // printf("-----------------------------\n"); // 按值操作 // 插入 // LinkedListInsertValue(L, 6, 80); // LinkedListInsertAllValue(L, 2, 80); // LinkedListPrint(L); // printf("-----------------------------\n"); // 删除 // LinkedListDeleteValue(L, 2); // LinkedListDeleteAllValue(L, 2); // LinkedListPrint(L); // printf("-----------------------------\n"); // 修改 // LinkedListModifyValue(L, 2, 80); // LinkedListModifyAllValue(L, 2, 80); // LinkedListPrint(L); // 查找 ElemType sourceValue = 2; // LinkedListSearchValue(L, sourceValue, position); // printf("%d at position %d\n", sourceValue, position); int pos[MaxSize] = {0}; LinkedListSearchAllValue(L, sourceValue, pos); for (int i = 0; pos[i]; i++) { printf("%d at position %d\n", sourceValue, pos[i]); } return 0; } 02-头文件用于存储结构体和常量等。 // // Created by 24955 on 2023-02-22. // #ifndef LINKEDLIST_LINKEDLISTDATA_H #define LINKEDLIST_LINKEDLISTDATA_H #include #include #include // 常量 #define MaxSize 50 typedef int ElemType; // 结构体 typedef struct Node { ElemType data; struct Node *next; } LNode, *LinkedList; #endif //LINKEDLIST_LINKEDLISTDATA_H 03-LinkedListCommon.cpp用于存储公共函数以及单链表的创建。 // // Created by 24955 on 2023-02-22. // // 头插法创建单链表 void LinkedListHeadCreate(LinkedList &List, int array[]) { /* * 1. 创建头结点，并将头指针指向头结点 * 2. 为新节点分配空间并初始化 * 3. 将头结点指针域赋值给新节点指针域 * 4. 将头结点指针域指向新结点*/ List = (LinkedList) malloc(sizeof(LNode)); List->next = NULL; LinkedList newNode; for (int i = 0; array[i]; i++) { newNode = (LinkedList) malloc(sizeof(LNode)); newNode->data = array[i]; newNode->next = List->next; List->next = newNode; } } // 尾插法创建单链表 void LinkedListTailCreate(LinkedList &List, int array[]) { /* * 1. 创建头结点，并将头指针指向头结点 * 2. 创建尾结点并初始化尾结点（指向头结点） * 3. 创建新结点并初始化 * 4. 将新结点地址赋值给尾结点指针域 * 5. 更新尾结点位置（指向新结点） * 6. 将最后一个元素指针域设为NULL*/ List = (LinkedList) malloc(sizeof(LNode)); List->next = NULL; LinkedList tailPointer; tailPointer = List; LinkedList newNode; for (int i = 0; array[i]; i++) { newNode = (LinkedList) malloc(sizeof(LNode)); newNode->data = array[i]; tailPointer->next = newNode; tailPointer = newNode; } tailPointer->next = NULL; } // 创建模式选择函数 void LinkedListCreate(LinkedList &List, int array[], int HeadTail) { /* * 1. 选择创建单链表的模式 * 2. 调用相应函数创建单链表*/ if (HeadTail == 0) { LinkedListHeadCreate(List, array); } else { LinkedListTailCreate(List, array); } } // 打印输出函数 void LinkedListPrint(LinkedList List) { List = List->next; while (List) { printf("%3d", List->data); List = List->next; } printf("\n"); } 04-LinkedListPositionOperation.cpp用于存储按位置操作的函数。 // // Created by 24955 on 2023-02-22. // // 按位置插入元素 void LinkedListInsertPosition(LinkedList List, int position, ElemType insertValue) { /* * 1. 定位到插入位置前一个指针处 * 2. 判断指针状态并插入元素*/ if (position > 0 && List) { for (int i = 0; i < position - 1 && List; i++) { List = List->next; } LinkedList newNode; if (List) { newNode = (LinkedList) malloc(sizeof(LNode)); newNode->data = insertValue; newNode->next = List->next; List->next = newNode; printf("Insert Success.\n"); } else { printf("Insert False.\n"); } } else { printf("Insert False.\n"); } } // 按位置删除元素 void LinkedListDeletePosition(LinkedList List, int position, ElemType &deleteValue) { /* * 1. 定位到要删除位置前一个结点出 * 2. 定义新指针并指向要删除元素 * 3. 若要删除元素非NULL，则获取当前元素指针域并释放当前元素*/ if (position > 0 && List) { for (int i = 0; i < position - 1 && List; i++) { List = List->next; } if (List) { LinkedList p = List->next; if (p) { List->next = p->next; deleteValue = p->data; printf("Delete Success.\n"); } else { printf("Delete False.\n"); } } else { printf("Delete False.\n"); } } else { printf("Delete False.\n"); } } // 按位置修改元素 void LinkedListModifyPosition(LinkedList List, int position, ElemType modifyValue) { /* * 1. 定位到要修改位置获取其指针 * 2. 修改元素值*/ if (position > 0 && List) { for (int i = 0; i < position && List; i++) { List = List->next; } if (List) { List->data = modifyValue; printf("Modify Success.\n"); } else { printf("Modify False.\n"); } } else { printf("Modify False.\n"); } } // 按位置查找,并返回查找到的值 void LinkedListSearchPosition(LinkedList List, int position, ElemType &value) { /* * 1. 判断位置是否合法，单链表是否创建 * 2. 将制定定位到指定位置 * 3. 判断指针状态，并赋值或输出*/ if (position > 0 && List) { for (int i = 0; i < position && List; i++) { List = List->next; } if (List) { value = List->data; printf("Search Success.\n"); } else { printf("Search False.\n"); } } else { printf("Search False.\n"); } } 05-LinkedListValueOperation.cpp用于存储按值操作的函数。 // // Created by 24955 on 2023-02-22. // // 按值插入元素,在第一个匹配元素前插入 void LinkedListInsertValue(LinkedList List, ElemType sourceValue, ElemType insertValue) { /* * 1. 遍历查找第一个匹配元素所在位置 * 2. 调用LinkedListInsertPosition实现插入功能*/ LinkedList ListCopy = List->next; for (int pos = 1; ListCopy; pos++) { if (ListCopy->data == sourceValue) { LinkedListInsertPosition(List, pos, insertValue); break; } ListCopy = ListCopy->next; } if (!ListCopy) { printf("Insert False.\n"); } } // 按值插入元素,在所有匹配元素前插入 void LinkedListInsertAllValue(LinkedList List, ElemType sourceValue, ElemType insertValue) { /* * 1. 遍历查找所有匹配元素所在位置 * 2. 调用LinkedListInsertPosition实现插入功能*/ LinkedList ListCopy = List->next; for (int pos = 1; ListCopy; pos++) { if (ListCopy->data == sourceValue) { LinkedListInsertPosition(List, pos, insertValue); pos++; // 插入元素后更新位置信息 } ListCopy = ListCopy->next; } } // 按值删除元素，删除第一个匹配元素 void LinkedListDeleteValue(LinkedList List, ElemType sourceValue) { /* * 1. 遍历查找第一个匹配元素所在位置 * 2. 调用LinkedListDeletePosition实现删除功能*/ LinkedList ListCopy = List->next; ElemType deleteValue; for (int pos = 1; ListCopy; pos++) { if (ListCopy->data == sourceValue) { LinkedListDeletePosition(List, pos, deleteValue); break; } ListCopy = ListCopy->next; } } // 按值删除元素，删除所有匹配元素 void LinkedListDeleteAllValue(LinkedList List, ElemType sourceValue) { /* * 1. 遍历查找所有匹配元素所在位置 * 2. 调用LinkedListDeletePosition实现删除功能*/ LinkedList ListCopy = List->next; ElemType deleteValue; for (int pos = 1; ListCopy; pos++) { if (ListCopy->data == sourceValue) { LinkedListDeletePosition(List, pos, deleteValue); pos--; // 删除元素后更新位置信息 } ListCopy = ListCopy->next; } } // 按值修改元素，修改第一个匹配元素 void LinkedListModifyValue(LinkedList List, ElemType sourceValue, ElemType modifyValue) { /* * 1. 遍历查找第一个匹配元素所在位置 * 2. 调用LinkedListModifyPosition实现修改功能*/ LinkedList ListCopy = List->next; for (int pos = 1; ListCopy; pos++) { if (ListCopy->data == sourceValue) { LinkedListModifyPosition(List, pos, modifyValue); break; } ListCopy = ListCopy->next; } } // 按值修改元素，修改所有匹配元素 void LinkedListModifyAllValue(LinkedList List, ElemType sourceValue, ElemType modifyValue) { /* * 1. 遍历查找所有匹配元素所在位置 * 2. 调用LinkedListModifyPosition实现修改功能*/ LinkedList ListCopy = List->next; for (int pos = 1; ListCopy; pos++) { if (ListCopy->data == sourceValue) { LinkedListModifyPosition(List, pos, modifyValue); } ListCopy = ListCopy->next; } } // 按值查找元素，返回第一个匹配元素所在位置 void LinkedListSearchValue(LinkedList List, ElemType sourceValue, int &position) { /* * 1. 遍历查找第一个匹配元素所在位置并返回其位置*/ LinkedList ListCopy = List->next; for (int pos = 1; ListCopy; pos++) { if (ListCopy->data == sourceValue) { position = pos; break; } ListCopy = ListCopy->next; } } // 按值查找元素，返回所有匹配元素所在位置 void LinkedListSearchAllValue(LinkedList List, ElemType sourceValue, int position[]) { /* * 1. 遍历查找所有匹配元素所在位置并返回其位置数组*/ LinkedList ListCopy = List->next; int index = 0; for (int pos = 1; ListCopy; pos++) { if (ListCopy->data == sourceValue) { position[index] = pos; index++; } ListCopy = ListCopy->next; } } 结语此博客主要用于408考研数据结构C语言实现记录，内有不足，可留言，可讨论。 |
【本文地址】