广州 网站制作公司 网络服务,如何在yy做电影网站,pageadmin做网站,wordpress 记录访问ip博主介绍#xff1a;✌全网粉丝喜爱、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦#xff01; #x1f345;附上相关C语言版源码讲解#x1f345; #x1f44… 博主介绍✌全网粉丝喜爱、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦 附上相关C语言版源码讲解 精彩专栏推荐订阅 不然下次找不到哟 文章目录 一、链表定义 二、链表实战 1、单链表C语言实现版本 2、双链表C 三、分析总结 优点 应用 小结 大家点赞、收藏、关注、评论啦 谢谢哦如果不懂欢迎大家下方讨论学习哦。 一、链表定义
链表是一种数据结构它由一系列节点组成这些节点按顺序连接在一起形成链式结构。每个节点包含数据和指向下一个节点的引用指针。链表的最后一个节点通常指向一个特定的值如空值或null表示链表的结束。
链表是一种数据结构它由一系列节点组成这些节点按顺序连接在一起形成链式结构。每个节点包含数据和指向下一个节点的引用指针。链表的最后一个节点通常指向一个特定的值如空值或null表示链表的结束。
链表可以分为单链表和双链表两种主要类型 1. 单链表Singly Linked List每个节点包含数据和指向下一个节点的指针。链表的最后一个节点指向null。
节点1 节点2 节点3
| 数据1 | - | 数据2 | - | 数据3 | - null2. 双链表Doubly Linked List每个节点包含数据、指向下一个节点的指针以及指向前一个节点的指针。这使得在双链表中可以更方便地进行前向和后向遍历。
null - | 数据1 | - | 数据2 | - | 数据3 | - null链表优点 链表相对于数组的优势在于插入和删除操作的效率较高因为不需要移动大量元素只需调整节点的指针。然而链表的缺点是访问元素时需要按顺序遍历而数组可以通过索引直接访问元素。链表在内存中不需要连续的存储空间因此可以更灵活地分配内存。
二、链表实战
1、单链表C语言实现版本
#include stdio.h
#include stdlib.h// 定义节点结构
struct Node {int data; // 节点数据struct Node* next; // 指向下一个节点的指针
};// 定义链表结构
struct LinkedList {struct Node* head; // 链表头指针
};// 初始化链表
void initLinkedList(struct LinkedList* list) {list-head NULL; // 将头指针初始化为NULL表示链表为空
}// 在链表末尾添加节点
void append(struct LinkedList* list, int data) {// 创建新节点struct Node* new_node (struct Node*)malloc(sizeof(struct Node));new_node-data data;new_node-next NULL;// 判断链表是否为空if (list-head NULL) {// 如果为空将新节点设为头节点list-head new_node;} else {// 如果不为空找到链表末尾将新节点链接到末尾struct Node* current list-head;while (current-next ! NULL) {current current-next;}current-next new_node;}
}// 在链表开头添加节点
void prepend(struct LinkedList* list, int data) {// 创建新节点struct Node* new_node (struct Node*)malloc(sizeof(struct Node));new_node-data data;new_node-next list-head;// 将新节点设为头节点list-head new_node;
}// 删除节点
void deleteNode(struct LinkedList* list, int data) {struct Node* current list-head;struct Node* prev NULL;// 遍历链表找到待删除节点及其前一个节点while (current ! NULL current-data ! data) {prev current;current current-next;}// 如果找到待删除节点if (current ! NULL) {// 如果待删除节点不是头节点if (prev ! NULL) {prev-next current-next;} else {// 如果待删除节点是头节点list-head current-next;}free(current); // 释放内存}
}// 更新节点
void updateNode(struct LinkedList* list, int oldData, int newData) {struct Node* current list-head;// 遍历链表找到待更新节点while (current ! NULL current-data ! oldData) {current current-next;}// 如果找到待更新节点if (current ! NULL) {current-data newData; // 更新节点数据}
}// 搜索节点
struct Node* searchNode(struct LinkedList* list, int data) {struct Node* current list-head;// 遍历链表找到包含指定数据的节点while (current ! NULL current-data ! data) {current current-next;}return current; // 返回节点指针
}// 显示链表内容
void display(struct LinkedList* list) {struct Node* current list-head;while (current ! NULL) {printf(%d - , current-data);current current-next;}printf(NULL\n);
}// 释放链表内存
void freeLinkedList(struct LinkedList* list) {struct Node* current list-head;struct Node* next NULL;while (current ! NULL) {next current-next;free(current);current next;}list-head NULL;
}int main() {struct LinkedList myLinkedList;initLinkedList(myLinkedList);// 添加节点append(myLinkedList, 1);append(myLinkedList, 2);append(myLinkedList, 3);// 显示链表内容printf(链表内容);display(myLinkedList);// 在开头添加节点prepend(myLinkedList, 0);// 显示链表内容printf(在开头添加节点后的链表);display(myLinkedList);// 删除节点deleteNode(myLinkedList, 2);// 显示链表内容printf(删除节点后的链表);display(myLinkedList);// 更新节点updateNode(myLinkedList, 1, 10);// 显示链表内容printf(更新节点后的链表);display(myLinkedList);// 搜索节点int searchData 10;struct Node* searchResult searchNode(myLinkedList, searchData);if (searchResult ! NULL) {printf(找到数据为 %d 的节点。\n, searchData);} else {printf(未找到数据为 %d 的节点。\n, searchData);}// 释放链表内存freeLinkedList(myLinkedList);return 0;
}执行结果详细 2、双链表C
#include iostream
#include cstdlib
#include cstdio using namespace std;
typedef struct Node
{ int data; struct Node *prior; struct Node *next;
} LinkList; LinkList *Create()
{ LinkList *head; head(LinkList*)malloc(sizeof(LinkList)); if(head!NULL) { head-priorNULL; head-nextNULL; return head; } else return NULL;
} int Insert(LinkList *head,int e) //尾插法
{ LinkList *p; LinkList *qhead; p(LinkList*)malloc(sizeof(LinkList)); if(p!NULL) { p-datae; p-priorNULL; p-nextNULL; while(q-next!NULL) { qq-next; } q-nextp; return 1; } return 0;
} LinkList* Change(LinkList *head) //变成双向链表后返回一个尾指针
{ LinkList *p,*q; phead; qp-next; while(q!NULL) { q-priorp; pp-next; qq-next; } return p;
} void Output1(LinkList *head) //从头到尾遍历输出
{ LinkList *p; phead-next; while(p!NULL) { printf(%d ,p-data); pp-next; } printf(\n);
} void Output2(LinkList *tail) //从尾到头遍历输出
{ LinkList *p; ptail; while(p-prior!NULL) { printf(%d ,p-data); pp-prior; } printf(\n);
} void FreeLink(LinkList *head) //释放
{ LinkList *p,*q; phead; qNULL; while(p!NULL) { qp; pp-next; free(q); }
} int main()
{ LinkList *phead,*tail; int n,e,flag; pheadCreate(); if(phead!NULL) { cout请输入长度:;scanf(%d,n); for(int i0;in;i) { scanf(%d,e); flagInsert(phead,e); }cout从头到尾输出为: ;Output1(phead); tailChange(phead); cout从尾到头输出为: ;Output2(tail); FreeLink(phead); } return 0;
}代码执行结果 三、分析总结
链表是一种常见的数据结构具有一些优点和应用
优点
1. 动态内存分配链表允许在运行时动态分配内存这使得它更加灵活不需要预先指定存储空间大小通过动态分配内存可以实现降低时间运行成本。
2. 插入和删除效率高在链表中插入和删除节点相对容易且效率较高。相比之下数组在中间或开头插入/删除元素可能需要移动大量元素。
3. 大小可变*链表可以根据需要动态增长或缩小而不浪费内存。
应用
1. 实现动态数据结构链表常用于实现其他动态数据结构如栈、队列、图等。
2. 内存分配动态链表的能力使其在动态内存分配的场景中非常有用例如动态分配内存的链表可用于管理操作系统的进程列表。
3. 实现算法链表常用于算法实现例如链表在排序算法、图算法等方面有广泛的应用。
4. 嵌入式系统 在资源受限的嵌入式系统中链表可以更好地处理动态数据。
5. LRU缓存淘汰算法链表可以用于实现LRULeast Recently Used缓存淘汰算法用于管理缓存中的数据。
6. 数据库数据库中的索引通常使用链表实现以支持高效的插入和删除操作。
总的来说链表在许多场景中都是一种强大且灵活的数据结构特别适合那些需要频繁插入和删除操作的应用。 小结 大家点赞、收藏、关注、评论啦 谢谢哦如果不懂欢迎大家下方讨论学习哦。
