NOIP初赛之链表的创建和增删改查

C语言基础知识复习2 链表的构建与链表的增、删、改、查 构建单向链表 ? 尾插法 ? 头插法 尾插法构建单向链表 header 头指针 NULL 0x8FF tail尾指针 NULL 0x8FF 0x7FF 0xEFF 3 NULL 0x7FF 4 NULL 0xEFF 5 NULL 内存地址:0x8FF 内存地址:0x7FF 内存地址:0xEFF 尾插法构建单向链表(链表节点和链表定义) 当链表为空时, header 和 tail 都为NULL 尾插法构建单向链表(添加节点到链表尾部) ?若list->tail 为NULL表示链表为空,只需 将头、尾指针都指向该节点 ?若list->tail不为NULL表示链表不为空, 则需将新节点链接到尾节点后。并将尾指 针指向新添加的节点 尾插法构建单向链表(显示链表中的所有元素) 若当前节点指向下一个节点的指针为NULL,则表示已经到达链表末尾 尾插法构建单向链表(释放链表所有节点占用的内存空间) 特别注意:每个使用malloc、calloc动态申请的空间,在使用完后都要使用 free释放。否则将会导致内存泄漏。这在实际软件开发中将属于重大BUG 尾插法构建单向链表(main函数) 若输入为:1 2 3 4 5 -1 请说出输出结果? 头插法构建单向链表 header 头指针 0x7FF NULL 0xEFF 0x8FF 3 0x7FF NULL 4 0xEFF NULL 5 NULL 内存地址:0x8FF 内存地址:0x7FF 内存地址:0xEFF 头插法构建单向链表(节点和链表定义) 头插法只需定义头指针 头插法构建单向链表(添加节点到链表头部) 头指针为空时,表示链表为空 头插法构建单向链表(显示和销毁链表中的所有元素) 与尾插法相同 头插法构建单向链表(main函数) 若输入为:1 2 3 4 5 -1 请说出输出结果? 单向链表的增、删、改、查 链表节点定义 往链表头部增加节点 header 头指针 0x7FF 0x8FF 4 30 0x7FF 0xEFF 5 NULL 内存地址:0x7FF 内存地址:0xEFF 内存地址:0x8FF Node *p = malloc(sizeof(Node)) ; // 申请新的节点空间 p->num = 30; // 设置新节点的值 p->next = header; header = p; 往链表尾部增加元素 header 头指针 0x7FF tail 尾指针 0x8FF 0xEFF 4 0xEFF 5 NULL 0x8FF 30 NULL 内存地址:0x7FF 内存地址:0xEFF 内存地址:0x8FF Node *p = malloc(sizeof(Node)) ; // 申请新的节点空间 p->num = 30; // 设置新节点的值 p->next = NULL; tail->next = p; tail = p; 在链表指定位置插入元素(在p指向的元素后插入元素) 指针p 4 0xEFF 5 0x9FF 0x8FF 30 NULL 内存地址:0x7FF 内存地址:0xEFF 内存地址:0x8FF Node *q = malloc(sizeof(Node)) ; q->num = 30; q->next = p->next; p->next = q; 30 0x8FF 内存地址:0x9FF 删除链表头部的元素 header 头指针 0x8FF 0x7FF 30 0x7FF 4 0xEFF 5 NULL 内存地址:0x8FF 指针p 内存地址:0x7FF 内存地址:0xEFF Node *p = header; header = header->next; free(p); 删除链表尾部的元素 指针p header头指针 0xAFF 30 0x8FF 30 0x7FF 4 NULL 0xEFF 5 NULL 内存地址:0xAFF 内存地址:0x8FF 内存地址:0x7FF 内存地址:0xEFF Node *p = header; for ( ; p->next->next != NULL; p = p->next ); Node *q = p->next; p->next = NULL; free(q); 指针q 删除链表指定位置的元素(删除指针p的下一个元素) 指针p header头指针 0xAFF 30 0x8FF 30 0x7FF 0xEFF 4 0xEFF 5 NULL 内存地址:0xAFF 内存地址:0x8FF 内存地址:0x7FF 内存地址:0xEFF Node *q = p->next; 指针q p->next = p->next->next; free(q); 交换链表中元素的位置(交换q和r指向的元素的位置) 指针p 指针q 指针r 18 0xAFF 内存地址:0xBFF 20 0x8FF 0x7FF 30 0x7FF 0xEFF 4 0x8FF 0xEFF 5 NULL 内存地址:0xAFF 内存地址:0x8FF 内存地址:0x7FF 内存地址:0xEFF p->next = r; // 或者 p->next = q->next q->next = r->next; r->next = q; 查找单链表中指定元素的位置 单向环形链表 18 28 代码实现详见: 03单向环形链表.c 12 68 5 9 单向环形链表(链表节点和链表定义) 单向环形链表(添加节点到环形链表的结束位置) 单向环形链表(显示链表) 单向环形链表(销毁链表) 双向链表

相关文档

c++课程设计《链表的实现-增删改查》
链表的增删改查
C语言指针链表(增、删、改、查)
链表的操作(增删改查)及逆置链表
链表的创建,查找,删除和插入操作(详解)
链表的创建、删除、逆置、查找及排序
双链表增删改查
实现链表的常用操作(包括:创建、插入、删除以及查询)
c言语链表的增删查改(最简单)
C语言链表实现增删改查
电脑版