首页 > 代码库 > 线性表的链式存储
线性表的链式存储
线性表的链式存储
- 线性表的链式存储
- 基本概念
- 设计与实现
- 实现代码
- 优缺点
1. 基本概念
链式存储定义
为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示其直接后继的信息。
表头结点
链表中的第一个结点,包含指向第一个数据元素的指针以及链表自身的一些信息- 数据结点
链表中代表数据元素的结点,包含指向下一个数据元素的指针和数据元素的信息 - 尾结点
链表中的最后一个数据结点,其下一元素指针为空,表示无后继。
2.设计与实现
- 在C语言中可以用结构体来定义链表中的指针域–数据节点/业务节点
链表中的表头结点也可以用结构体实现–表头结点
插入操作
- 获取
带头结点、位置从0的单链表返回链表中第3个位置处元素的值
LinkListNode* LinkList_Get(LinkList* list, int pos)
{
int i = 0;
TLinkList *tList = (TLinkList *)list;
LinkListNode *current = NULL;
LinkListNode *ret = NULL;
if (list==NULL ||pos<0 || pos>=tList->length)
{
return NULL;
}
current = (LinkListNode *)tList;
for (i=0; i<pos; i++)
{
current = current->next;
}
ret = current->next;
return ret ;
}
—返回第三个位置的
移动pos次以后,当前指针指向哪里?
答案:指向位置2,所以需要返回 ret = current->next;
备注:
循环遍历时, 遍历第1次,指向位置0
遍历第2次,指向位置1
遍历第3次,指向位置2
遍历第n次,指向位置n-1;
所以如果想返回位置n的元素的值,需要怎么做
ret = current->next;
此问题是:指向头结点的指针移动n次指向第n-1个元素。
- 删除
3.实现代码
- 头文件
#ifndef _MYLINKLIST_H_
#define _MYLINKLIST_H_
#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
typedef void LinkList;//数据类型的封装
/*线性表(链表)节点的数据结构--只含指向自身类型的指针(域)*/
typedef struct _tag_LinkListNode
{
struct _tag_LinkListNode* next;
}LinkListNode;
LinkList* LinkList_Create();
void LinkList_Destroy(LinkList* list);
void LinkList_Clear(LinkList* list);
int LinkList_Length(LinkList* list);
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);
LinkListNode* LinkList_Get(LinkList* list, int pos);
LinkListNode* LinkList_Delete(LinkList* list, int pos);
#endif
- 实现文件
#include "TLinkList.h"
/*线性表链式存储的表头数据结构*/
typedef struct _tag_LinkList
{
LinkListNode head;//表头节点(里面的指针域指向链表第一个节点)
int length;//节点个数
}TLinkList;//链表的抽象数据类型
/*链表创建*/
LinkList* LinkList_Create()
{
TLinkList * tmp = NULL;
tmp = (TLinkList*)malloc(sizeof(TLinkList));//为表头分配内存
if (NULL == tmp)//检查分配结果
{
printf("malloc error!\n");
return NULL;
}
/*表头数据成员初始化*/
memset(tmp, 0, sizeof(TLinkList));
/*返回表头地址*/
return tmp;
}
/*链表销毁*/
void LinkList_Destroy(LinkList* list)
{
if (list != NULL)//合法性检测
{
free(list);//释放内存
list = NULL;//避免野指针
}
else
{
printf("list is error!\n");
}
return ;
}
/*清空链表*/
void LinkList_Clear(LinkList* list)
{
TLinkList * tmp = NULL;
if (list == NULL)
{
printf("list is error!\n");
return;
}
tmp = (TLinkList*)list;
/*将长度置零*/
tmp->length = 0;
/*将指向第一个节点的指针置零*/
tmp->head.next= NULL;
return ;
}
/*获取链表中节点个数*/
int LinkList_Length(LinkList* list)
{
TLinkList * tmp = NULL;
if (list == NULL)
{
printf("list is error!\n");
return -1;
}
tmp = (TLinkList*)list;
return tmp->length;
}
/*插入节点*/
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
TLinkList * tmp = NULL;//指向链表表头
LinkListNode * current = NULL;//辅助指针变量
int i = 0;//循环用变量
/*合法性检测*/
if (list == NULL || node == NULL || pos < 0)
{
printf("argv is error!\n");
return -2;
}
tmp = (TLinkList*)list;
/*容错纠正*/
if (pos >= tmp->length)
{
pos = tmp->length;
}
/*将辅助指针变量指向表头节点*/
current = &(tmp->head);
/*辅助指针变量往后跳到指向要插入位置的前一个节点*/
for (i = 0; i < pos && current->next != NULL; i++)
{
current = current->next;
}
/*新节点的指针域指向后一个节点*/
node->next = current->next;
/*前一个节点的指针域指向新节点*/
current->next = node;
/*修改长度*/
tmp->length++;
return 0;
}
/*获取指定位置的元素*/
LinkListNode* LinkList_Get(LinkList* list, int pos)
{
TLinkList * tmp = NULL;
LinkListNode * current = NULL;
int i = 0;
if (list == NULL || pos < 0)
{
printf("argv is error!\n");
return NULL;
}
tmp = (TLinkList*)list;
if (pos >= tmp->length)
{
pos = tmp->length;
}
current = &(tmp->head);
for (i = 0; i < pos && current->next != NULL; i++)
{
current = current->next;
}
/*返回相应位置的业务节点的地址*/
return current->next;
}
/*删除指定位置的节点*/
LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
TLinkList * tmp = NULL;
LinkListNode * current = NULL;
LinkListNode * del_res = NULL;//第二个辅助指针变量,用于保存要删除的节点
int i = 0;
/*合法性检测*/
if (list == NULL || pos < 0)
{
printf("argv is error!\n");
return NULL;
}
tmp = (TLinkList*)list;
/*容错性纠正*/
if (pos >= tmp->length)
{
pos = tmp->length;
}
/*辅助指针变量指向表头结点*/
current = &(tmp->head);
/*辅助指针变量往后跳到指定位置的前一个位置*/
for (i = 0; i < pos && current->next != NULL; i++)
{
current = current->next;
}
/*保存要删除的节点以便上层应用回收内存*/
del_res = current->next;
/*将前一个位置的指针域指向指定位置的后一个节点*/
current->next = del_res->next;
/*修改长度*/
tmp->length--;
/*返回被删除的节点的地址*/
return del_res;
}
- 测试文件
#include "TLinkList.h"
typedef struct Teacher
{
LinkListNode node;
char name[64];
int age;
}Teacher;
int main()
{
Teacher t1, t2, t3;
int length, i = 0;
LinkList *list = NULL;
t1.age = 31;
t2.age = 32;
t3.age = 33;
list = LinkList_Create();
length = LinkList_Length(list);
//业务节点是teacher和算法分类的。。。。思想
LinkList_Insert(list, (LinkListNode *)&t1, LinkList_Length(list));
LinkList_Insert(list, (LinkListNode *)&t2, LinkList_Length(list));
LinkList_Insert(list, (LinkListNode *)&t3, LinkList_Length(list));
//遍历链表
for (i = 0; i<LinkList_Length(list); i++)
{
Teacher *tmp = (Teacher *)LinkList_Get(list, i);
if (tmp != NULL)
{
printf("age:%d ", tmp->age);
}
}
while (LinkList_Length(list) > 0)
{
Teacher *tmp = (Teacher *)LinkList_Delete(list, 0);
if (tmp != NULL)
{
printf("age:%d ", tmp->age);
}
}
LinkList_Destroy(list);
system("pause");
return 0;
}
4.优缺点
- 优点:
- 无需一次性定制链表的容量
- 插入和删除操作无需移动数据元素
- 缺点:
- 数据元素必须保存后继元素的位置信息
- 获取指定数据的元素操作需要顺序访问之前的元素
线性表的链式存储
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。