搜狐快站生成app,公司标志设计,seo营销推广费用,网页设计素材景区结束链表是一种物理存储单元上非连续、非顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点#xff08;链表中每一个元素称为结点#xff09;组成#xff0c;结点可以在运行时动态生成。每个结点包括两个部分#xff1a;一个是…链表是一种物理存储单元上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点链表中每一个元素称为结点组成结点可以在运行时动态生成。每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域。 优点可以克服数组链表需要预先知道数据大小的缺点链表结构可以充分利用计算机内存空间实现灵活的内存动态管理。缺点链表失去了数组随机读取的优点同时链表由于增加了结点的指针域空间开销比较大。 一般链表中只有一个表头元素不是顺序存储的不能随机访问元素相互依赖串联而成 构造一个链表 首先创建两个模板类一个用来创建链表节点对象另一个用来创建链表 1 template typename Type class Node {2 public:3 Type data;4 NodeType *next;5 6 Node(const Type _data) {7 data _data;8 next nullptr;9 }
10 };
11
12 template typename Type class LinkedList {
13 private:
14 NodeType *head;
15 public:
16 LinkedList() {
17 head nullptr;
18 }
19 ~LinkedList() {
20 NodeType *current_node head;
21 while (current_node ! nullptr) {
22 NodeType *delete_node current_node;
23 current_node current_node-next;
24 delete delete_node;
25 }
26 }
27 } 接下来给链表类添加如下的函数操作 插入函数 insert(node, index)将node插入到链表中下标为index的位置 实现方法 1. 遍历到链表中要插入的位置的前一位。 2. 令待插入结点的 next 指针指向插入位置的当前结点。 3. 令插入位置之前的当前结点的 next 指针指向待插入结点。 1 bool insert(NodeType * node, int index) {2 if (head nullptr) {3 if (index ! 0) {4 return false;5 }6 head node;7 return true;8 }9 if (index 0) {
10 node - next head;
11 head node;
12 return true;
13 }
14 NodeType * current_node head;
15 int count 0;
16 while (current_node - next ! nullptr count index - 1) {
17 current_node current_node - next;
18 count ;
19 }
20 if (count index - 1) {
21 node - next current_node - next;
22 current_node - next node;
23 return true;
24 }
25 return false;
26 } 遍历函数output()从头结点开始通过当前结点的指针找到下一节点直至表尾,并输出所有结点的值 实现方法 1. 定义一个用于遍历的变量初始指向头结点。 2. 输出遍历变量所在结点的值并更新遍历变量为当前结点的下一个结点。 3. 重复操作 2直到遍历完所有结点。 1 void output() {2 if (head nullptr) {3 return;4 }5 NodeType * current_node head;6 while (current_node ! nullptr) {7 cout current_node - data ;8 current_node current_node - next;9 }
10 cout endl;
11 } 删除函数delete_node(index)删除链表中下标为index的元素 实现方法 1. 从表头遍历找到要删除的位置的前一位。 2. 令删除位置前一个结点的next指针指向待删除位置后一个结点。 3. 删除结点。 1 bool delete_node(int index) {2 if (head nullptr) {3 return false;4 }5 NodeType * current_node head;6 int count 0;7 if (index 0) {8 head head - next;9 delete current_node;
10 return true;
11 }
12 while (current_node - next ! nullptr count index - 1) {
13 current_node current_node - next;
14 count ;
15 }
16 if (current_node - next ! nullptr count index - 1) {
17 NodeType * delete_node current_node - next;
18 current_node - next delete_node - next;
19 delete delete_node;
20 return true;
21 }
22 return false;
23 } 翻转函数reverse()翻转整个链表 实现方法 1. 定义一个用于遍历的指针初始指向头结点后一个结点。 2. 让头结点的 next 指针置空。 3. 从当前遍历指针所指的结点开始遍历链表将遍历到的结点 next 指针指向头结点。遍历过程中借助另外一个指针保存下一个遍历到的结点。 4. 重复步骤 3 直至表尾此时新的链表就是原链表反转后的链表。 1 void reverse() {2 if (head nullptr) {3 return;4 }5 NodeType * current_node, * next_node;6 current_node head - next;7 head - next nullptr;8 while (current_node ! nullptr) {9 next_node current_node - next;
10 current_node - next head;
11 head current_node;
12 current_node next_node;
13 }
14 } 转载于:https://www.cnblogs.com/xudongwei/p/7493092.html
