本节知识点:
1.静态链表到底是什么:链表就是链式存储的线性表,但是它分为动态和静态两种,所谓动态就是长度不固定,可以根据情况自行扩展大小的,静态链表就是长度大小固定的,链式存储的线性表。
2.本节的静态链表和顺序表很像(其实和数组也很像),准确的来说就是利用顺序表实现的,只是这个顺序表,不是顺序排列的,是通过一个next变量,连接到下一个变量的。
如图:
3.唐老师说静态链表是在一些没有指针的语言中使用的,来实现链表的功能,但是我觉得链表的最大优势就在于它的伸缩,用多少开辟多少。但是静态链表就恰恰失去了这个优势。依我看,学习静态链表的目的是学习它这种类似内存管理的算法思想。
4.静态链表中值得学习的思想:就是在初始化链表的时候,把所以空间都标记成为可用-1,每次插入数据的时候,都在标记为可用的空间内挑取,再把-1改成next。当删除变量的时候在把next改成-1,标记为空间可用。
5.其实仔细想想 看看,静态链表只是一个思想,为什么这么说,首先在获取index的时候,你是顺序获取的,这导致你的next也是连续的,所以他其实就变成了一个顺序表。在这里我想到了一个唐老师的问题,为什么node[0]就可以当作头节点,还要再定义一个head变量。唐老师的解答是:顺序获得index的时候每次都要遍历太浪费时间了,所以最好应该在同一块空间再定义一个链表,来保存这些空闲空间,然后这样就需要两个链表的头节点了,所以需要一个head。然后让node[0]一会是空闲链表的链表头节点,一会是真实保存数据的链表的头节点。当插入的时候,只需要在那个空闲链表取空间就可以了,提高了算法的效率。
PS1:对于node[0]我真的想说,其实让node[0]当作头节点的使用真的很方便,比head方便很多,仅仅是个人体会。
PS2:对于两个链表的那个算法,我觉得如果还是顺序在链表中获得index,依然没有解决这个index是有顺序的且顺序是固定的问题。这里的顺序是指的是那个空闲链表的顺序。所以说这仅仅是一个思想。
6.本节最重要的知识点也是最大的难点:对于柔性数组的描述。
对于柔性数组的结构如下:
typedef struct _tag_StaticList //因为静态链表是基于顺序表改写的 这个就是顺序表中描述顺序表的那个结构
{
int capacity; //静态链表的大小是固定的 这是链表的容量
StaticListNode head; //链表 头节点
StaticListNode node[]; //利用柔性数组 创建静态链表
}StaticList;
然后:给柔性数组开辟空间
StaticList* ret = NULL;
ret = (StaticList*)malloc( sizeof(StaticList)*1 + sizeof(StaticListNode)*(capacity+1) );
其实柔性数组就是以数组的方式访问内存。对于 StaticList ret这个结构体的大小是不包括StaticLIstNode node[]的,StaticLIstNode node[]是没有大小的,StaticLIstNode node[0]访问的内存是StaticList ret这个结构体后面的第一个内存,StaticLIstNode node[1]访问的内存是StaticList ret这个结构体后面的第二个内存等等。
PS:StaticLIstNode node[]这个结构到底是个什么结构,不好说,不是数组,也不是指针。就把它当作为了柔性数组而产生的结构吧!!!
本节代码:
StaticList.c:
/**************************************************************************************************************
文件名:StaticList.c
头文件:StaticList.h
时间:2013/08/15
作者:Hao
功能:可以复用的 带有增 删 改 查 的静态链表
**************************************************************************************************************/
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "StaticList.h"
#define AVAILABLE -1
typedef struct _tag_StaticListNode //这个是静态链表的结构 用来保存链表元素的
{
unsigned int data; //这个是为了复用 保存数据地址的
int next; //这个是用来保存下一个节点位置的
}StaticListNode;
typedef struct _tag_StaticList //因为静态链表是基于顺序表改写的 这个就是顺序表中描述顺序表的那个结构
{
int capacity; //静态链表的大小是固定的 这是链表的容量
StaticListNode head; //链表 头节点
StaticListNode node[]; //利用柔性数组 创建静态链表
}StaticList;
/**************************************************************************************************************
函数名 : Creat_StaticList
函数功能:创建一个静态链表使用的空间
具体数据: StaticList这个结构是描述静态链表的结构 StaticListNode这个结构才是真正的静态链表的元素
每一个静态链表的元素都是由两个部分组成的 一个是数据data(即保存的地址) 另一个是下一个链表
元素的位置next
对于StaticList这个结构中的数据是capacity是静态链表的容量 head是链表的头节点
node[0]也是头节点 node[]是柔性数据 这里面保存的才是真的链表内容
参数: int capacity 链表容量 正确范围 0到无穷大 当为0的时候链表中仅仅有一个node[0]头节点
返回值:StaticList* ret 返回描述静态链表的结构 StaticList的地址 (SList*这个是为了封装)
**************************************************************************************************************/
SList* Creat_StaticList(int capacity)
{
int i=0;
StaticList* ret = NULL;
if( capacity >= 0) //参数合法性检测 一定要大于等于0 如果capacity为0 是给node[0]开辟空间 node[0]是链表头节点
{
ret = (StaticList*)malloc( sizeof(StaticList)*1 + sizeof(StaticListNode)*(capacity+1) );
}
if(NULL != ret) //判断malloc是否成功 内存是否分配成功
{
ret -> capacity = capacity; //静态链表的容量
ret -> head.data = 0; //头节点中保存的 链表长度 初始化为0
ret -> head.next = 0; //头节点中保存的 链表下一个节点的位置 初始化为NULL
for(i=1; i<=capacity; i++) //把链表中从node[1]开始 到node[capacity]中的next都标志为可用
{
ret -> node[i].next = AVAILABLE; //这个在插入函数的时候有用
}
}
return (SList*)ret;
}
/**************************************************************************************************************
函数名:Destroy_StaticList
函数功能:释放StaticList结构开辟的内存
参数:StaticList* Static_List (SList* Static_List这个是为了 封装)
返回值:void
**************************************************************************************************************/
void Destroy_StaticList(SList* Static_List)
{
free(Static_List); //释放静态链表创建的内存空间
}
/**************************************************************************************************************
函数名: Get_Lenth
函数功能:返回静态链表长度
参数:StaticList* Static_List (SList* List为了封装)
返回值:成功 int Static_List -> head.data 静态链表使用的长度 失败返回 0
**************************************************************************************************************/
int Get_Lenth(SList* List)
{
StaticList* Static_List = (StaticList*)List;
int ret = 0;
if(NULL != Static_List)
{
ret = Static_List -> head.data; //静态链表的长度
}
return ret;
}
/**************************************************************************************************************
函数名:Get_Capacity
函数功能:返回静态链表的容量
参数:StaticList* Static_List (SList* List为了封装)
返回值:成功返回 int Static_List -> capacity 静态链表的容量 失败返回 0
**************************************************************************************************************/
int Get_Capacity(SList* List)
{
StaticList* Static_List = (StaticList*)List;
int ret = 0;
if(NULL != Static_List)
{
ret = Static_List -> capacity; //静态链表的容量
}
return ret;
}
/**************************************************************************************************************
函数名: Clear_StaticList
函数功能:重置静态链表
参数:StaticList* Static_List (SList* List为了封装)
返回值:成功返回1 失败返回0
**************************************************************************************************************/
int Clear_StaticList(SList* List)
{
StaticList* Static_List = (StaticList*)List;
int i = 0;
int ret = 0;
if(NULL != Static_List)
{
Static_List -> head.data = 0;
Static_List -> head.next = 0;
for(i=1; i<=Static_List -> capacity; i++)
{
Static_List -> node[i].next = AVAILABLE;
}
ret = 1;
}
return ret;
}
/**************************************************************************************************************
函数名: Add_StaticList
函数功能: 在链表中的pos位置处插入一个链表元素 pos的规则跟上节单链表的规则一样 0和1为头插法 无穷大为尾插法
node[0]是链表头节点 其实是head的一个中间变量 使用node[0]真的很方便 此处记得更新头节点
参数:SList* List 要插入的链表地址 SListNode* Node要插入的数据地址 int pos插入的位置
返回值:返回1说明插入成功 返回0说明插入失败
**************************************************************************************************************/
int Add_StaticList(SList* List, SListNode* Node, int pos)
{
StaticList* Static_List = (StaticList*)List;
StaticListNode* node = (StaticListNode*)Node;
int ret = 0;
int num = 0;
int index = 0;
int i = 0;
ret = (NULL != Static_List)&&(NULL != node);
ret = ret&&(Static_List->head.data+1 <= Static_List->capacity)&&(pos >= 0);
if(ret) //参数合法性检测成功
{
for(i=1; i<=Static_List->capacity; i++) //轮询获得可用的位置index
{
if(-1 == Static_List->node[i].next)
{
index = i;
break;
}
}
Static_List->node[index].data = (unsigned int)node; //保存链表中的数据
Static_List->node[0] = Static_List->head; //此时node[0]变成了链表头节点
for(i=1; (i < pos)&&(0 != Static_List->node[num].next); i++)
{
num = Static_List->node[num].next;
}
Static_List->node[index].next = Static_List->node[num].next;
Static_List->node[num].next = index;
Static_List->node[0].data++;
Static_List->head = Static_List->node[0];//更新链表头节点
}
return ret;
}
/**************************************************************************************************************
函数名: Get_StaticListNode
函数功能:获得pos位置处的数据 pos的规则跟单向链表一样
范围是 0 到 head->data 0是头节点
参数: SList* List 要插入的链表地址 int pos插入的位置
返回值: 成功返回pos位置处的数据 失败返回NULL
**************************************************************************************************************/
SListNode* Get_StaticListNode(SList* List, int pos)
{
SListNode* ret = NULL;
int i = 0;
int num = 0;
StaticList* Static_List = (StaticList*)List;
if( (NULL != Static_List) && (pos <= Static_List->head.data) && (pos >= 0) )
{
Static_List->node[0] = Static_List->head;
for(i=0; i<pos; i++)
{
num = Static_List->node[num].next;
}
ret = (SListNode*)Static_List->node[num].data;
}
return ret;
}
/**************************************************************************************************************
函数名: Del_StaticListNode
函数功能:删除pos位置处的数据 pos的规则跟单向链表一样
范围是 1 到 head->data 0是头节点 不能删除
参数: SList* List 要插入的链表地址 int pos删除的位置
返回值:成功返回 pos位置的数据 (目的在于:因为此数据一般是数据的地址 便于释放内存) 失败返回NULL
**************************************************************************************************************/
SListNode* Del_StaticListNode(SList* List, int pos)
{
SListNode* ret = NULL;
int i = 0;
int num = 0;
int temp = 0;
StaticList* Static_List = (StaticList*)List;
if( (NULL != Static_List) && (pos <= Static_List->head.data) && (pos > 0) )
{
Static_List->node[0] = Static_List->head;
for(i=1; i<pos; i++)//得找到要删除的那个节点的上一个
{
num = Static_List->node[num].next;
}
temp = Static_List->node[num].next;
Static_List->node[num].next = Static_List->node[temp].next;
Static_List->node[0].data--;
Static_List->head = Static_List->node[0]; //更新链表头节点
Static_List->node[temp].next = AVAILABLE; //把删除的节点标志为可用节点
ret = (SListNode*)Static_List->node[temp].data;
}
return ret;
}
StaticList.h:
#ifndef __STATICLIST_H__
#define __STATICLIST_H__
typedef void SList;
typedef void SListNode;
SList* Creat_StaticList(int capacity);
void Destroy_StaticList(SList* Static_List);
int Get_Lenth(SList* List);
int Get_Capacity(SList* List);
int Clear_StaticList(SList* List);
int Add_StaticList(SList* List, SListNode* Node, int pos);
SListNode* Get_StaticListNode(SList* List, int pos);
SListNode* Del_StaticListNode(SList* List, int pos);
#endif
main.c:
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "StaticList.h"
int main()
{
SList* list = Creat_StaticList(10);
int *f = 0;
int i = 0;
int a = 1;
int b = 2;
int c = 3;
int d = 4;
int e = 5;
Add_StaticList(list, &a, 0);
Add_StaticList(list, &b, 0);
Add_StaticList(list, &c, 0);
Add_StaticList(list, &d, 0);
for(i=1; i<=Get_Lenth(list); i++)
{
f=(int* )Get_StaticListNode(list, i);
printf("%d\n",*f);
}
Add_StaticList(list, &e, 2);
printf("\n");
for(i=1; i<=Get_Lenth(list); i++)
{
f=(int* )Get_StaticListNode(list, i);
printf("%d\n",*f);
}
printf("\n");
f=(int* )Del_StaticListNode(list, 4);
printf("del %d\n",*f);
printf("\n");
for(i=1; i<=Get_Lenth(list); i++)
{
f=(int* )Get_StaticListNode(list, i);
printf("%d\n",*f);
}
Destroy_StaticList(list);
return 0;
}
分享到:
相关推荐
数据结构算法——1008.线性表去重 定义线性表节点的结构.pdf
数据结构 实验报告 实验一.线性表的操作
第一节 线性表-顺序存储-数组数据结构的一些基本概念时间复杂度概念可以理解为某算法代码执行次数 k 与数据规模 n 在渐进意义上成什么数学关系。用大O记号表示。
Java数据结构 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构
数据结构课件 线性表 单链表 栈和队列 串 数组和广义表 树和二叉树 C语言版 有大量程序代码
数据结构笔记之线性表(-):静态链表表示与实现
数据结构C语言版线性表算法2.4-数据结构c语言版严蔚敏顺序线性表12个基本操作及算法的实现... 定义线性表节点的结构.pdf数据结构C语言版线性表算法2.4-数据结构c语言版严蔚敏顺序线性表12个基本操作及算法的实现... ...
利用C++实现以下经典数据结构与算法:线性表(顺序表、链表、静态链表、三元组)、栈(双栈、共享栈)、队列(任务调度、循环队列、双向队列、链队列)、数组(特殊矩阵、稀疏矩阵压缩)、串(朴素模式匹配、KMP算法...
数据结构---线性表之单链表,包括单链表的创建、插入、删除等,C语言编写
数组实现线性表 数组实现线性表 数据结构 数组实现线性表 数据结构
数据结构 线性表 实验代码 C语言 数组 支持大部分线性表操作,hust 赵明 虽是菜鸟,努力坚持学习
数据结构---线性表之双链表,创建、插入、删除,完整的C代码
数据结构 线性表 实验代码 C++ 链表 C/C++的数组/链表四种都写了。虽说基本操作能实现,但感觉还有很多要改进的地方,下学期学数据结构这门课时再改了 hust 赵明
数据结构实验报告(1) 学院: 专业: 班级: "姓名 " "学号 " "实验组" " "实验时间 "2011-10-28 "指导教师" "成绩 " " "实验项目名称 "线性表的顺序存储结构 " "实 "1. 熟练掌握线性表的基本操作在顺序存储和链式...
2.线性表.ppt
数据结构 1-9章课程笔记 word版 详细介绍数据结构基础知识和相关实验 数据结构 C++版 电子笔记 线性表 栈、队 列 串 多维数组 广义表 树 二叉树 图 查找技术 排序技术 索引技术
包括数据结构课程的各种程序:队列、二叉树、数组、图、稀疏矩阵、线性表和链表、栈
c语言数组指定位置插入和删除-玩转C语言链表,单链表双向链表的建立遍历插入删除... 数组和链表.pdf
2.线性表子系统.pdf