做一个个人网站,山西省住房和城乡建设部网站,青海住房和建设厅网站,网站地图灰色效果的怎么做的在学习算法时#xff0c;发现用什么数据结构来存储数据是很重要的#xff0c;所以学习数据结构也是必须的#xff0c;先从基础数据结构#xff1a;数组#xff0c;字符串#xff0c;链表#xff0c;栈#xff0c;队列#xff0c;树#xff0c;矩阵#xff0c;邻接表… 在学习算法时发现用什么数据结构来存储数据是很重要的所以学习数据结构也是必须的先从基础数据结构数组字符串链表栈队列树矩阵邻接表哈希表等数组和字符串我们已经了解的很多了所以我们从链表开始学习了解什么是链表链表存储数据的方式以及如何对链表进行各种操作如何用数组来模拟链表如何用栈来做链表相关的题目。
1.何为链表 由于顺序表的插入删除操作需要移动大量的元素影响了运行效率因此引入了线性表的链式存储——单链表。单链表通过一组任意的存储单元来存储线性表中的数据元素不需要使用地址连续的存储单元因此它不要求在逻辑上相邻的两个元素在物理位置上也相邻。同时因为单链表是非随机的存储结构即不能直接找到表中某个特定的结点。查找某个特定的结点时需要从表头开始遍历依次查找。 我们再看链表是什么 链表其实是由一个个结点组成每个结点之间通过链接更新串联起来每个结点都有一个后继结点最后一个结点的后继结点为空结点 图中就是一个链表其中橙色结点被称为黄色结点的前驱结点黄色结点被称为橙色结点的后继结点链表其实有单向链表、双向链表、循环链表等这里先只介绍单向链表。那既然结点存储数据怎么找到后驱结点呢下面一起来看看吧
2.链表结点的定义
typedef struct ListNode
{int data;struct ListNode* next;
}ListNode; 这就是一个结点的定义我们把一个结点看成一个结构体其中data是数据域可以是任意类型而struct ListNode* next定义了一个指向ListNode结构体的指针这个指针的地址是后继结点将指向下一个结点这就是指针域如下图所示 下面看看具体怎么创建一个链表的结点
3.链表结点创建
ListNode* ListCreateNode(int data)
{ListNode* node(List*)malloc(sizeof(ListNode));node-datadata;node-nextNULL;return node;
} 我们先用malloc函数分配一块内存空间用来存放ListNode即链表对象将数据域置为函数传参data将指针域置为NULL代表这是一个孤立的链表结点最后返回这个结点的指针。
4.虚拟头结点 为了方便对链表进行操作避免第一个结点无法操作的问题我们往往会建立一个虚拟头结点这个头结点上不存储数据只是指向链表的第一个结点
ListNode* headListCreateNode(-1);5.链表的创建及初始化 单链表有两种一种是带虚拟头结点的一种不带虚拟头结点。总的来说带头结点的单链表相对于不带头结点的单链表来说更加方便对链表进行操作所以很多时候我们都是用带头结点的单链表这里我们也只用学习带头结点的即可
5.1初始化带头结点的单链表
void InitList(ListNode* head) {head(ListNode*)malloc(sizeof(ListNode));head-nextNULL;
}
5.2创建带头结点的单链表
5.2.1头插法 头插法顾名思义就是从链表开头插入先插入的后输出后插入的先输入例如我想创建一个链表479输出就是(974)。
ListNode* HeadInsert(ListNode* head) {initlist(head); //初始化int n;scanf_s(%d,n);for(int i0;in;i) {ListNode* node (ListNode*)malloc(sizeof(ListNode));int data;scanf_s(%d, data);node-data data;node-next head-next;head-next node;}return head;
} 5.2尾插法 尾插法顾名思义就是从链表末尾开始插入先插入的先输出后插入的后输出
ListNode* TailInsert(ListNode* head) {initlist(head); //初始化ListNode* cur (ListNode*)malloc(sizeof(ListNode));cur head;int n,data;scanf_s(%d,n);for(int i0;in;i) {ListNode* node (ListNode*)malloc(sizeof(ListNode));scanf_s(%d, data)node-data data;node-next NULL;cur-next node;cur cur-next; }return head;
}
6.链表基础操作 创建完链表之后我们就要对链表进行操作了常见的操作就是增删改查
6.1遍历操作
void PrintList(ListNode* head) {ListNode* cur head-next;while (cur) {printf(%d , cur-data);cur cur-next;}printf(\n);
}
6.2求单链表的长度
int Length(ListNode* head) {ListNode* cur head-next;int len 0;while (cur) {len;cur cur-next;}return len;
}
6.3查找操作
6.3.1按值查找
ListNode* locateElem(ListNode* head, int data)
{ListNode* cur head-next;while (cur cur-data ! data){cur cur-next;}return cur;
}
6.3.2按位查找
ListNode* getElem(ListNode* head, int i)
{int j 1;ListNode* cur head-next;if (i 0)return head;if (i 1)return NULL;while (cur j i){cur cur-next;j;}return cur;
}
6.4插入操作
void Insert(ListNode* head, int i, int data)
{ListNode* pre getElem(head, i - 1);ListNode* cur (ListNode*)malloc(sizeof(ListNode));cur-data data;cur-next pre-next;pre-next cur;
}
6.5删除操作 将链表的第i个结点删除
void Delete(ListNode* head, int i) {if (i1 || iLength(head))return;ListNode* pre getElem(head, i - 1);ListNode* cur pre-next;pre-next cur-next;free(cur);
}
6.6判空操作
bool Empty(ListNode* head) {if (head-next NULL) {printf(Head is null\n);return true;}else {printf(Head is not null\n);return false;}
}
