wordpress 网站主题,大良营销网站建设精英,wordpress离线写文章,网红网站建设官网目录
1 链表的优势#xff1a;
2 链表的组成:
3.一般使用结构体的形式来实现链表#xff1a;
4.单向链表实现(创建#xff0c;遍历#xff0c;释放)#xff1a;
4.1代码关键点备注#xff1a;
5.查找节点#xff1a;
5.1.按值查找节点
5.2.按位置查找节点
5.3 …目录
1 链表的优势
2 链表的组成:
3.一般使用结构体的形式来实现链表
4.单向链表实现(创建遍历释放)
4.1代码关键点备注
5.查找节点
5.1.按值查找节点
5.2.按位置查找节点
5.3 查找是否存在某个值
5.4. 查找链表中最后一个节点
5.5 查找链表中倒数第 k 个节点
6.删除节点
6.1 删除头节点
6.2删除尾节点
6.3.删除指定位置的节点
6.4.删除指定值的节点
6.5.释放整个链表 1 链表的优势
动态大小链表的大小可以根据需要动态调整而数组在声明时大小固定。插入和删除操作高效在链表中插入和删除操作不需要移动元素只需修改指针即可效率更高。内存利用率高链表可以根据需要分配内存不会浪费空间。
2 链表的组成: 节点结构链表由多个节点组成每个节点通常包含两部分 数据域存储实际的数据。指针域指向下一个节点的指针在双向链表中还会有指向前一个节点的指针第一个节点的指针域保存第二个节点的地址。 头指针链表通常有一个头指针指向链表的第一个节点。如果链表为空头指针为NULL。 尾指针可选在某些实现中链表还可能包含一个指向最后一个节点的指针以便于在尾部插入节点时提高效率
3.一般使用结构体的形式来实现链表
struct Node {int data; // 数据域struct Node* next; // 指针域指向下一个节点
};在正式手搓单向链表前先复习一下二级指针
指针一个变量它存储另一个变量的地址。例如Node* head 是一个指向 Node 类型的指针。
二级指针一个指向指针的指针。比如Node** head 表示这是一个指向 Node* 的指针通常用于传递指针的地址以便在函数内可以修改这个指针的值。在链表的实现中使用二级指针来传递指向头指针的地址这样就可以在函数内部修改头指针的值。
4.单向链表实现(创建遍历释放)
下面是一个代码的示例
#include stdio.h
#include stdlib.h// 定义链表节点结构体
struct Node {int data; // 节点数据struct Node* next; // 指向下一个节点的指针
};// 创建链表节点并添加到链表末尾
void createNode(struct Node** head, int value) {struct Node* newNode (struct Node*)malloc(sizeof(struct Node)); // 分配新节点内存newNode-data value; // 设置节点的数据newNode-next NULL; // 新节点的下一个指针初始化为 NULL// 检查链表是否为空if (*head NULL) {*head newNode; // 如果链表为空则将新节点设置为头节点} else {struct Node* temp *head; // 使用 *head 访问当前头节点while (temp-next ! NULL) { // 遍历链表到最后一个节点temp temp-next;}temp-next newNode; // 将新节点链接到链表末尾}
}// 打印链表中的所有节点
void printList(struct Node* head) {struct Node* temp head; // struct Node* temp head; 这一行定义了一个
//新的指针变量 temp并将 head 的值即头节点的地址赋给它。while (temp ! NULL) {printf(%d - , temp-data); // 打印当前节点的数据temp temp-next; // 移动到下一个节点}printf(NULL\n); // 链表结束标志
}// 释放链表内存
void freeList(struct Node** head) {struct Node* temp;while (*head ! NULL) {temp *head; // 备份当前头节点*head (*head)-next; // 移动头指针到下一个节点free(temp); // 释放备份的节点内存}
}int main() {struct Node* head NULL; // 初始化链表头节点为空int n, value;// 输入节点的个数printf(请输入链表节点的个数: );scanf(%d, n);// 使用 for 循环创建链表for (int i 0; i n; i) {printf(请输入第 %d 个节点的值: , i 1);scanf(%d, value);createNode(head, value); // 通过二级指针传入头指针}// 打印链表内容printf(链表内容: );printList(head);// 释放链表内存freeList(head);return 0;
}4.1代码关键点备注
在void createNode中:
head 是一个指向链表 头节点 的 指针的地址。head通过传入二级指针createNode 函数可以在链表为空时直接修改头指针的值让新节点成为链表的头节点即 *head newNode; 的情况。
在void printList(struct Node* head)中
head 是指向链表 头节点 的 指针用于从链表的第一个节点开始进行遍历。struct Node* temp head; 这一行定义了一个新的指针变量 temp并将 head 的值即头节点的地址赋给它。headprintList 函数并不修改链表的结构或内容只是逐一访问每个节点的数据并打印。因此只需传入一个指向头节点的普通指针而不需要使用二级指针不需要修改头指针的值。
5.查找节点
5.1.按值查找节点
在链表中查找第一个数据与指定值匹配的节点并返回该节点的指针。如果找不到该值通常返回 NULL。
struct Node* searchByValue(struct Node* head, int value) {struct Node* temp head;while (temp ! NULL) {if (temp-data value) {return temp; // 找到匹配值的节点返回指针}temp temp-next; // 移动到下一个节点}return NULL; // 没有找到
}5.2.按位置查找节点
按照链表中的位置索引查找节点。位置通常从 0 开始即第 0 个节点是头节点。如果位置超出链表长度可以返回 NULL。
struct Node* searchByPosition(struct Node* head, int position) {struct Node* temp head;int currentIndex 0;while (temp ! NULL) {if (currentIndex position) {return temp; // 找到指定位置的节点}temp temp-next;currentIndex;}return NULL; // 位置超出链表长度
}5.3 查找是否存在某个值
在链表中查找是否存在某个值只返回 1找到或 0未找到而不返回节点。
int containsValue(struct Node* head, int value) {struct Node* temp head;while (temp ! NULL) {if (temp-data value) {return 1; // 找到该值返回 1}temp temp-next;}return 0; // 没找到该值返回 0
}5.4. 查找链表中最后一个节点
可以用来获取链表的尾节点。
struct Node* getLastNode(struct Node* head) {if (head NULL) return NULL; // 链表为空struct Node* temp head;while (temp-next ! NULL) {temp temp-next;}return temp; // 返回最后一个节点
}5.5 查找链表中倒数第 k 个节点
经典问题常用 双指针 方法实现。用两个指针 fast 和 slow它们都从链表的头节点 head 出发但 fast 会比 slow 先走 k 步。然后让两个指针同时移动直到 fast 到达链表的末尾。此时slow 就刚好停在倒数第 k 个节点的位置。 struct Node* getKthFromEnd(struct Node* head, int k) {struct Node *fast head, *slow head;// 让 fast 指针先走 k 步for (int i 0; i k; i) {if (fast NULL) return NULL; // 链表长度小于 kfast fast-next;}// 同时移动 fast 和 slow 指针直到 fast 到达链表末尾while (fast ! NULL) {fast fast-next;slow slow-next;}return slow; // slow 指针就是倒数第 k 个节点
}6.删除节点
6.1 删除头节点
void deleteHead(struct Node** head) {if (*head NULL) return; // 链表为空无法删除struct Node* temp *head; // 备份头节点*head (*head)-next; // 更新头节点为下一个节点free(temp); // 释放备份的头节点内存
}6.2删除尾节点
删除链表的最后一个节点。需要遍历链表找到倒数第二个节点并将其 next 指针设为 NULL。
void deleteTail(struct Node** head) {if (*head NULL) return; // 链表为空无法删除if ((*head)-next NULL) { // 如果只有一个节点free(*head);*head NULL; // 更新头指针为 NULLreturn;}struct Node* temp *head;while (temp-next-next ! NULL) { // 遍历到倒数第二个节点temp temp-next;}free(temp-next); // 释放最后一个节点temp-next NULL; // 将倒数第二个节点的 next 设为 NULL
}1 - 2 - 3 - NULL
在执行删除尾节点的操作时
temp 会遍历到节点 2倒数第二个节点temp-next 会指向节点 3最后一个节点。当我们执行 free(temp-next);节点 3 被释放。然后执行 temp-next NULL;使得节点 2 变成链表的新尾节点链表现在变为
1 - 2 - NULL 6.3.删除指定位置的节点
根据给定的位置删除节点。
void deleteAtPosition(struct Node** head, int position) {if (*head NULL) return; // 链表为空无法删除if (position 0) { // 如果要删除的是头节点deleteHead(head);return;}struct Node* temp *head;for (int i 0; i position - 1; i) {if (temp NULL || temp-next NULL) {printf(位置超出链表长度\n);return; // 位置超出链表长度无法删除}temp temp-next; // 遍历到要删除节点的前一个节点}struct Node* nodeToDelete temp-next; // 要删除的节点if (nodeToDelete NULL) return; // 如果没有下一个节点无法删除temp-next nodeToDelete-next; // 将前一个节点的 next 指向要删除节点的下一个节点free(nodeToDelete); // 释放要删除的节点内存
}6.4.删除指定值的节点
删除链表中第一个值匹配指定值的节点
void deleteByValue(struct Node** head, int value) {if (*head NULL) return; // 链表为空无法删除struct Node* temp *head;// 如果头节点的值就是要删除的值if (temp-data value) {deleteHead(head);return;}// 遍历链表查找匹配的节点while (temp-next ! NULL) {if (temp-next-data value) { // 找到匹配的节点struct Node* nodeToDelete temp-next; // 备份要删除的节点temp-next nodeToDelete-next; // 链接前一个节点与后一个节点free(nodeToDelete); // 释放要删除的节点内存return; // 删除完毕退出函数}temp temp-next; // 移动到下一个节点}
}6.5.释放整个链表
如果需要删除整个链表释放所有节点内存。
void freeList(struct Node** head) {struct Node* temp;while (*head ! NULL) {temp *head; // 备份当前头节点*head (*head)-next; // 移动头指针到下一个节点free(temp); // 释放备份的节点内存}
} 文章转载自： http://www.morning.qtryb.cn.gov.cn.qtryb.cn http://www.morning.zyrp.cn.gov.cn.zyrp.cn http://www.morning.jypqx.cn.gov.cn.jypqx.cn http://www.morning.wqkfm.cn.gov.cn.wqkfm.cn http://www.morning.bgzgq.cn.gov.cn.bgzgq.cn http://www.morning.trffl.cn.gov.cn.trffl.cn http://www.morning.wxrbl.cn.gov.cn.wxrbl.cn http://www.morning.jwwfk.cn.gov.cn.jwwfk.cn http://www.morning.xflzm.cn.gov.cn.xflzm.cn http://www.morning.pfggj.cn.gov.cn.pfggj.cn http://www.morning.zylzk.cn.gov.cn.zylzk.cn http://www.morning.xuejitest.com.gov.cn.xuejitest.com http://www.morning.mnpdy.cn.gov.cn.mnpdy.cn http://www.morning.nnykz.cn.gov.cn.nnykz.cn http://www.morning.nqfxq.cn.gov.cn.nqfxq.cn http://www.morning.dkqr.cn.gov.cn.dkqr.cn http://www.morning.bpyps.cn.gov.cn.bpyps.cn http://www.morning.zwzwn.cn.gov.cn.zwzwn.cn http://www.morning.hhnhb.cn.gov.cn.hhnhb.cn http://www.morning.kyytt.cn.gov.cn.kyytt.cn http://www.morning.rfpxq.cn.gov.cn.rfpxq.cn http://www.morning.jtrqn.cn.gov.cn.jtrqn.cn http://www.morning.rlwgn.cn.gov.cn.rlwgn.cn http://www.morning.lwzgn.cn.gov.cn.lwzgn.cn http://www.morning.lcbt.cn.gov.cn.lcbt.cn http://www.morning.dxzcr.cn.gov.cn.dxzcr.cn http://www.morning.mnwb.cn.gov.cn.mnwb.cn http://www.morning.rnyhx.cn.gov.cn.rnyhx.cn http://www.morning.mkyxp.cn.gov.cn.mkyxp.cn http://www.morning.pmdzd.cn.gov.cn.pmdzd.cn http://www.morning.ktlxk.cn.gov.cn.ktlxk.cn http://www.morning.c7513.cn.gov.cn.c7513.cn http://www.morning.qrpx.cn.gov.cn.qrpx.cn http://www.morning.wslpk.cn.gov.cn.wslpk.cn http://www.morning.xyjlh.cn.gov.cn.xyjlh.cn http://www.morning.nqlnd.cn.gov.cn.nqlnd.cn http://www.morning.pjrql.cn.gov.cn.pjrql.cn http://www.morning.fgqbx.cn.gov.cn.fgqbx.cn http://www.morning.rswfj.cn.gov.cn.rswfj.cn http://www.morning.hlppp.cn.gov.cn.hlppp.cn http://www.morning.wnrcj.cn.gov.cn.wnrcj.cn http://www.morning.rlqqy.cn.gov.cn.rlqqy.cn http://www.morning.qjghx.cn.gov.cn.qjghx.cn http://www.morning.rzmsl.cn.gov.cn.rzmsl.cn http://www.morning.hqlnp.cn.gov.cn.hqlnp.cn http://www.morning.knrgb.cn.gov.cn.knrgb.cn http://www.morning.ckhry.cn.gov.cn.ckhry.cn http://www.morning.xhftj.cn.gov.cn.xhftj.cn http://www.morning.psxcr.cn.gov.cn.psxcr.cn http://www.morning.xoaz.cn.gov.cn.xoaz.cn http://www.morning.bnrff.cn.gov.cn.bnrff.cn http://www.morning.sgbsr.cn.gov.cn.sgbsr.cn http://www.morning.lfsmf.cn.gov.cn.lfsmf.cn http://www.morning.leyuhh.com.gov.cn.leyuhh.com http://www.morning.ldcsw.cn.gov.cn.ldcsw.cn http://www.morning.kgnrh.cn.gov.cn.kgnrh.cn http://www.morning.shxmr.cn.gov.cn.shxmr.cn http://www.morning.wjqbr.cn.gov.cn.wjqbr.cn http://www.morning.lkfhk.cn.gov.cn.lkfhk.cn http://www.morning.lgwjh.cn.gov.cn.lgwjh.cn http://www.morning.qmkyp.cn.gov.cn.qmkyp.cn http://www.morning.kyzja.com.gov.cn.kyzja.com http://www.morning.dcmnl.cn.gov.cn.dcmnl.cn http://www.morning.kdrjd.cn.gov.cn.kdrjd.cn http://www.morning.plznfnh.cn.gov.cn.plznfnh.cn http://www.morning.hkpn.cn.gov.cn.hkpn.cn http://www.morning.fqssx.cn.gov.cn.fqssx.cn http://www.morning.zwzlf.cn.gov.cn.zwzlf.cn http://www.morning.rcjqgy.com.gov.cn.rcjqgy.com http://www.morning.jhrkm.cn.gov.cn.jhrkm.cn http://www.morning.ntqnt.cn.gov.cn.ntqnt.cn http://www.morning.fjzlh.cn.gov.cn.fjzlh.cn http://www.morning.srckl.cn.gov.cn.srckl.cn http://www.morning.nywrm.cn.gov.cn.nywrm.cn http://www.morning.qsdnt.cn.gov.cn.qsdnt.cn http://www.morning.yqpzl.cn.gov.cn.yqpzl.cn http://www.morning.qdcpn.cn.gov.cn.qdcpn.cn http://www.morning.ntqlz.cn.gov.cn.ntqlz.cn http://www.morning.srhqm.cn.gov.cn.srhqm.cn http://www.morning.tpbhf.cn.gov.cn.tpbhf.cn
