网站后台管理系统进度,高端旅游网站制作,河东手机网站建设,wordpress menu 插件目录
前文、线性表的定义及其基本操作#xff08;顺序表插入、删除、查找、修改#xff09;
四、线性表的链接存储结构
1. 单链表#xff08;C语言#xff09;
a. 链表节点结构
b. 创建新节点
c. 在链表末尾插入新节点
d. 删除指定节点
e. 修改指定节点的数据
f. …目录
前文、线性表的定义及其基本操作顺序表插入、删除、查找、修改
四、线性表的链接存储结构
1. 单链表C语言
a. 链表节点结构
b. 创建新节点
c. 在链表末尾插入新节点
d. 删除指定节点
e. 修改指定节点的数据
f. 遍历链表并打印
g. 主函数
C语言代码整合
Cpp代码整合 前文、线性表的定义及其基本操作顺序表插入、删除、查找、修改 按照线性表结点间的逻辑顺序依次将它们存储于一组地址连续的存储单元中的存储方式被称为线性表的顺序存储方式。 按顺序存储方式存储的线性表具有顺序存储结构一般称之为顺序表。换言之在程序中采用定长的一维数组按照顺序存储方式存储的线性表被称为顺序表。若顺序表中的元素按其值有序则称其为有序顺序表。 在高级程序设计语言中“数组”这种数据类型同样具有随机存储的特性因此用高级程序设计语言实现线性表的顺序存储结构时通常选择数组。因此数组的长度就是顺序表的最大长度MaxSize顺序表的实际长度为length其值必须小于等于MaxSize。 【数据结构】线性表一线性表的定义及其基本操作顺序表插入、删除、查找、修改-CSDN博客https://blog.csdn.net/m0_63834988/article/details/132089038?spm1001.2014.3001.5501 四、线性表的链接存储结构 顺序表的优点是存取速度快。但是无论是插入一个结点还是删除一个结点都需要调整一批结点的地址。要克服该缺点就必须给出一种不同于顺序存储的存储方式。用链接存储方式存储的线性表被称为链表可以克服上述缺点。 链表中的结点用存储单元若干个连续字节来存放存储单元之间既可以是存储空间上连续的也可以是不连续的甚至可以零散地分布在存储空间中的任何位置。换言之链表中结点的逻辑次序和物理次序之间并无必然联系。最重要的是链表可以在不移动结点位置的前提下根据需要随时添加删除结点动态调整。 1. 单链表C语言 在链接存储结构中插入和删除操作相对于顺序存储结构而言更加高效时间复杂度为O(1)。而查找操作的时间复杂度为O(n)。
a. 链表节点结构
typedef struct Node {int data;struct Node* next;
} Node; 链表节点的结构体 Node包含一个整数数据 data 和一个指向下一个节点的指针 next
b. 创建新节点
Node* createNode(int data) {Node* newNode (Node*)malloc(sizeof(Node));if (newNode ! NULL) {newNode-data data;newNode-next NULL;}return newNode;
}
创建一个新的节点并返回指向该节点的指针 使用 malloc 分配了节点的内存空间将传入的数据赋值给节点的 data 字段并将 next 字段设置为 NULL。 c. 在链表末尾插入新节点
void insertAtEnd(Node** head, int data) {Node* newNode createNode(data);if (newNode NULL) {printf(内存分配失败\n);return;}if (*head NULL) {*head newNode;} else {Node* temp *head;while (temp-next ! NULL) {temp temp-next;}temp-next newNode;}printf(已在链表末尾插入节点%d, data);
}
调用 createNode 函数创建一个新节点检查内存分配是否成功 如果成功则根据链表是否为空来确定新节点的位置。若链表为空则将新节点设置为头节点否则遍历链表找到最后一个节点并将最后一个节点的 next 指针指向新节点。 d. 删除指定节点
void deleteNode(Node** head, int data) {if (*head NULL) {printf(链表为空\n);return;}Node* temp *head;Node* prev NULL;if (temp ! NULL temp-data data) {*head temp-next;free(temp);printf(已删除节点%d, data);return;}while (temp ! NULL temp-data ! data) {prev temp;temp temp-next;}if (temp NULL) {printf(节点 %d 不存在\n, data);return;}prev-next temp-next;free(temp);printf(已删除节点%d, data);
}
检查链表是否为空如果为空则输出相应的提示信息。遍历链表找到要删除的节点。 如果找到了节点则修改前一个节点的 next 指针使其跳过要删除的节点并释放该节点的内存空间。如果没有找到要删除的节点则输出相应的提示信息。 e. 修改指定节点的数据
void modifyNode(Node* head, int oldData, int newData) {if (head NULL) {printf(链表为空\n);return;}Node* temp head;while (temp ! NULL) {if (temp-data oldData) {temp-data newData;printf(已将节点 %d 修改为 %d\n, oldData, newData);return;}temp temp-next;}printf(节点 %d 不存在\n, oldData);
}
查找~删除~修改……这里不重复介绍懂的都懂不懂我也没办法 f. 遍历链表并打印
void printList(Node* head) {if (head NULL) {printf(链表为空\n);return;}Node* temp head;printf(链表节点数据);while (temp ! NULL) {printf(%d , temp-data);temp temp-next;}printf(\n);
}
检查链表是否为空如果为空则输出相应的提示信息。使用一个临时指针变量 temp 来遍历链表依次访问每个节点并打印其数据。 g. 主函数
nt main() {Node* head NULL; // 头节点insertAtEnd(head, 1);insertAtEnd(head, 2);insertAtEnd(head, 3);printList(head);deleteNode(head, 2);printList(head);deleteNode(head, 4);return 0;
}
创建了一个头节点 head调用 insertAtEnd 函数三次在链表末尾插入了三个节点调用 printList 函数打印链表的节点数据调用 deleteNode 函数删除链表中的一个节点并再次打印链表的节点数据调用 deleteNode 函数尝试删除一个不存在的节点。 C语言代码整合
#include stdio.h
#include stdlib.h// 定义链表节点结构
typedef struct Node {int data;struct Node* next;
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode (Node*)malloc(sizeof(Node));if (newNode ! NULL) {newNode-data data;newNode-next NULL;}return newNode;
}// 在链表末尾插入新节点
void insertAtEnd(Node** head, int data) {Node* newNode createNode(data);if (newNode NULL) {printf(内存分配失败\n);return;}if (*head NULL) {*head newNode;} else {Node* temp *head;while (temp-next ! NULL) {temp temp-next;}temp-next newNode;}printf(已在链表末尾插入节点%d, data);
}// 删除指定节点
void deleteNode(Node** head, int data) {if (*head NULL) {printf(链表为空\n);return;}Node* temp *head;Node* prev NULL;if (temp ! NULL temp-data data) {*head temp-next;free(temp);printf(已删除节点%d, data);return;}while (temp ! NULL temp-data ! data) {prev temp;temp temp-next;}if (temp NULL) {printf(节点 %d 不存在\n, data);return;}prev-next temp-next;free(temp);printf(已删除节点%d, data);
}
// 修改指定节点的数据
void modifyNode(Node* head, int oldData, int newData) {if (head NULL) {printf(链表为空\n);return;}Node* temp head;while (temp ! NULL) {if (temp-data oldData) {temp-data newData;printf(已将节点 %d 修改为 %d\n, oldData, newData);return;}temp temp-next;}printf(节点 %d 不存在\n, oldData);
}
// 遍历链表并打印节点数据
void printList(Node* head) {if (head NULL) {printf(链表为空\n);return;}Node* temp head;printf(链表节点数据);while (temp ! NULL) {printf(%d , temp-data);temp temp-next;}printf(\n);
}// 主函数测试链表操作
int main() {Node* head NULL; // 头节点insertAtEnd(head, 1);insertAtEnd(head, 2);insertAtEnd(head, 3);printList(head);deleteNode(head, 2);printList(head);deleteNode(head, 4);return 0;
} Cpp代码整合 与C语言基本相同这里不再过多介绍
#include iostream// 定义链表节点结构
class Node {
public:int data;Node* next;// 构造函数Node(int data) : data(data), next(nullptr) {}
};// 链表类
class LinkedList {
private:Node* head;public:// 构造函数LinkedList() : head(nullptr) {}// 析构函数用于释放链表内存~LinkedList() {Node* current head;while (current ! nullptr) {Node* next current-next;delete current;current next;}}// 在链表末尾插入新节点void insertAtEnd(int data) {Node* newNode new Node(data);if (head nullptr) {head newNode;} else {Node* temp head;while (temp-next ! nullptr) {temp temp-next;}temp-next newNode;}std::cout 已在链表末尾插入节点 data std::endl;}// 删除指定节点void deleteNode(int data) {if (head nullptr) {std::cout 链表为空 std::endl;return;}Node* temp head;Node* prev nullptr;if (temp ! nullptr temp-data data) {head temp-next;delete temp;std::cout 已删除节点 data std::endl;return;}while (temp ! nullptr temp-data ! data) {prev temp;temp temp-next;}if (temp nullptr) {std::cout 节点 data 不存在 std::endl;return;}prev-next temp-next;delete temp;std::cout 已删除节点 data std::endl;}// 修改指定节点的数据void modifyNode(int oldData, int newData) {if (head nullptr) {std::cout 链表为空 std::endl;return;}Node* temp head;while (temp ! nullptr) {if (temp-data oldData) {temp-data newData;std::cout 已将节点 oldData 修改为 newData std::endl;return;}temp temp-next;}std::cout 节点 oldData 不存在 std::endl;}// 遍历链表并打印节点数据void printList() {if (head nullptr) {std::cout 链表为空 std::endl;return;}Node* temp head;std::cout 链表节点数据;while (temp ! nullptr) {std::cout temp-data ;temp temp-next;}std::cout std::endl;}
};int main() {LinkedList list;list.insertAtEnd(1);list.insertAtEnd(2);list.insertAtEnd(3);list.printList();list.deleteNode(2);list.printList();list.deleteNode(4);return 0;
}
