欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 文旅 > 旅游 > 数据结构------线性表(链表)

数据结构------线性表(链表)

2025/3/18 13:39:38 来源:https://blog.csdn.net/2401_84382970/article/details/146321461  浏览:    关键词:数据结构------线性表(链表)

单向链表:

一、链式存储核心概念

1. 节点结构定义
// 数据元素类型(与顺序表相同)
typedef struct person {char name[32];char sex;int age;int score;
} DATATYPE;// 单向链表节点
typedef struct node {DATATYPE data;struct node *next;  // 后继指针(单向链表只需此指针)
} LinkNode;// 链表管理结构
typedef struct list {LinkNode *head;     // 头节点指针int clen;           // 当前元素个数
} LinkList;

二、核心操作实现要点

1. 创建链表
LinkList *CreateLinkList() {LinkList *list = (LinkList*)malloc(sizeof(LinkList));list->head = NULL;  // 空链表初始化list->clen = 0;return list;
}
2. 头部插入
int InsertHeadLinkList(LinkList *list, DATATYPE data) {LinkNode *newnode = (LinkNode*)malloc(sizeof(LinkNode));newnode->data = data;newnode->next = list->head;list->head = newnode;list->clen++;return 0;
}
3. 尾部插入
int InsertTailLinkList(LinkList *list, DATATYPE data) {LinkNode *newnode = (LinkNode*)malloc(sizeof(LinkNode));newnode->data = data;newnode->next = NULL;if(!list->head) {list->head = newnode;} else {LinkNode *cur = list->head;while(cur->next) cur = cur->next;cur->next = newnode;}list->clen++;return 0;
}
4. 节点查找
LinkNode *FindLinkList(LinkList *list, char *name) {LinkNode *cur = list->head;while(cur) {if(strcmp(cur->data.name, name) == 0)return cur;cur = cur->next;}return NULL;
}

三、存储结构对比分析

对比维度顺序表链表
存储方式连续内存空间离散内存节点
容量管理固定大小,需预分配动态增长,按需分配
随机访问O(1)O(n)
插入/删除O(n)(需移动元素)O(1)(已知节点位置)
内存利用率可能存在空间浪费无内存浪费(精确分配)
缓存友好性优秀(空间局部性)较差(节点离散存储)


四、内存管理实践

1. 节点删除示例
int DelLinkList(LinkList *ll,char*name)
{if (NULL == ll || NULL == name){return 1;}LinkNode *tmp = ll->head;if(0 == strcmp(tmp->data.name,name))//head del{ll->head = ll->head->next;free(tmp);}else{while (strcmp(tmp->next->data.name,name)){tmp = tmp->next;if(NULL == tmp->next){return 1;}}LinkNode *free_node = tmp->next;tmp->next = tmp->next->next;}ll->clen--;return 0;
}
2. 链表销毁
int DestroyLinkList(LinkList *ll)
{LinkNode *tmp = ll->head;while(1){ll->head = ll->head->next;free(tmp);tmp = ll->head;if(NULL == tmp){break;}free(ll);return 0;}
}

五、应用场景指南

场景特征推荐结构原因
高频随机访问顺序表直接下标访问优势
频繁插入删除链表无需数据移动
内存资源紧张链表精确分配无浪费
数据规模固定顺序表缓存友好性优势
实现简单优先级队列链表方便动态调整元素位置

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词