大话数据结构学习②线性表的单链表存储结构
2022/2/26 23:27:20
本文主要是介绍大话数据结构学习②线性表的单链表存储结构,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#define OK 1 #define ERROR 0 typedef int Status; typedef struct { ElemType data; struct Node *next; } Node; typedef struct Node *LinkList; // 定义单链表 // 获取单链表的长度 Status GetElem(LinkList L, int i, ElemType *e) { in j; // 用于记录当前位置 LinkList p; // 用于指向当前位置 p = L->next; // p指向第一个结点 j = 1; // j初始化为1 while (p && j < i) // 当p不为空且j小于i时 { p = p->next; // p后移一个结点 j++; // j加1 } if (!p || j > i) // 当p为空或者j大于i时 return ERROR; // 返回错误 *e = p->data; // 将p的值赋给e return OK; // 返回OK } // 在单链表中插入元素 Status ListInsert(LinkList *L, int i, ELemType e) { int j; // 用于记录当前位置 LinkList p, s; // p指向当前结点,s指向新结点 p = *L; // p指向第一个结点 j = 1; // j初始化为1 while (p && j < i) // 当p不为空且j小于i时 { p = p->next; // p后移一个结点 j++; // j加1 } if (!p || j > i) // 当p为空或者j大于i时 return ERROR; // 返回错误 s = (LinkList)malloc(sizeof(Node)); // 分配空间 s->data = e; // 将e赋给新结点 s->next = p->next; // 将新结点插入到p的后面 p->next = s; // 将p的后继指向新结点 return OK; // 返回OK } // 删除单链表中的第i个元素 Status ListDelete(LinkList *L, int i, ElemType *e) { int j; // 用于记录当前位置 LinkList p, q; // p指向当前结点,s指向待删除结点 p = *L; // p指向第一个结点 j = 1; // j初始化为1 while (p->next && j < i) //遍历寻找第i个元素 { p = p->next; // p后移一个结点 j++; // j加1 } if (!(p->next) || j > i) // 当p为空或者j大于i时 return ERROR; // 返回错误 q = p->next; // q指向待删除结点 p->next = q->next; // 将q的后继指向p的后继 *e = q->data; // 将q的值赋给e free(q); // 释放q,free函数的作用是释放内存 return OK; // 返回OK } /* 插入和删除算法都是由2部分组成,第一部分就是查找第i个元素,第二部分就是插入或删除元素。 对于插入或删除数据越频繁的操作,单链表比起顺序存储来说,单链表的优势是很明显的。 */
单链表与结构与顺序结构的优缺点:
①存储分配的方式不同,顺序存储结构用一段连续存储单元一次存储线性表的数据元素,单链表则采用链式存储结构,用一组任意的存储单元存放线性表的元素。
②时间性能:查找:顺序存储结构:O(1),单链表O(n),
插入和删除:顺序存储结构需要平均移动表长一半的元素,时间复杂度为O(n);单链表在找出位置的指针后,插入和删除时间复杂度仅为O(1)
③空间性能:顺序存储结构需要预分配存储空间,分大了就浪费,分小了,就容易发生溢出;单链表不需要分配空间,只要有就分配,元素个数也不收限制。
这篇关于大话数据结构学习②线性表的单链表存储结构的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?