本教程来自本人博客越行勤‘sBlog,欢迎大家访问域名https:yingwiki.top文章目录静态链表算法解析题目初步理解代码InitSpace_SLMalloc
本教程来自 本人博客 越行勤‘s Blog ,欢迎大家访问 域名 https://yingwiki.top
文章目录 静态链表 算法解析 题目 代码 InitSpace _SL Malloc_SL Free_SL difference 静态链表代码
静态链表 我在《 数据结构 第二章 :双链表,循环链表,静态链表以及对比总结》,初步认识了静态链表。
第一次去理解代码,其实有一点点费力。但是也不是那么复杂,主要抓住下面这一点
静态链表:分配一整个连续内存空间每个节点,每个节点集中安置;静态链表中没有用指针,但是数组的索引值 Index充当了指针的作用。
静态链表就是为那行没有指针的编程语言二存在的,存储数据用的是连续的空间,但是逻辑上连续的空间,在物理上无需连续,还是抓住了链表的特点。
typedef struct { ElemType data; int cur; } SLinkList[ MaxSize] ;
cur: 就是下一个结点的数组下标,其实可以把它看着指针,指针也不少一个数吗?
算法解析 第一次实现静态链表,我面对的一个问题就是 如何寻找到没有使用的数据结点 ,我给出的解决方案是:
cur = 0,表示结尾 cur =MaxSize ,表示没有使用该段空间 所以需要开辟一个没有存储数据(插入结点等操作需要开辟空间)的结点就需要使用循环 扫描出cur== MaxSize 的结点(没有使用的结点)。
有没有不需要循环的方法呢?当然是有的,我们来看看书上的一个例子。
题目 实现集合运算 (A−B)U(B−U)(A-B)U(B-U) ( A − B ) U ( B − U ) 来讨论静态链表的算法。
初步理解 为了更好的理解,我想提讲述出它的具体原理
在静态链表中 存着两个链表
链表1(备用链表). 头节点 为 SLinkList[0],存储着没有数据的结点 链表2(数据链表). 头结点为 SLinkList[1] (也可以不是 SLinkList[1] ,只要是空闲结点就可以了),存储着有数据的结点, 当然它是如何他是如何存储两个链表在一个数组中呢?
回想我们单链表是如何找到链表的呢? 找到头结点
那很简单,我们也只需要规定, L[0]为备用链表的头结点,L[1]为存储数据的头结点
开辟一个存储数据的结点:从备用链表中取出–>一个结点到数据链表中
删除回收一个存储数据的结点:从将被删除的结点–>插入到备用链表中
是不是很有启发性呢,经典的空间换取时间,当然我们这样多花费了1个空间(备用链表的头结点),就避免了时间复杂度为O(n)的大循环。
代码 InitSpace _SL 函数功能:初始化链表,由于此时没有存储数据,其实就是创建 备用链表
void InitSpace _SL ( SLinkList & space) { for ( i&#61; 0 ; i< MaxSize- 1 ; i&#43;&#43; ) space[ i] . cur&#61; i&#43; 1 ; space[ MaxSize - 1 ] &#61;&#61; 0 ; }
如上图&#xff0c;每个cur指向下一个结点。
Malloc_SL 函数功能&#xff1a;从备用链表中取出&#xff08;拿出来并在备用链表中删除&#xff09;一个可以存储数据的新结点&#xff0c;返回其的数组下标&#xff08;地址&#xff09;&#xff0c;返回0表示分配空间失败
int Malloc_SL ( SLinkList & space) { i&#61; space[ 0 ] . cur; if ( space[ 0 ] . cur) space[ 0 ] . cur&#61; space[ i] . cur; return i; }
Free_SL 函数功能&#xff1a; 将被删除的结点k,连接到备用链表的头结点之后&#xff08;回收K结点&#xff09;
Free_SL ( SLinkList & space , int k) { space[ k] . cur&#61; space[ 0 ] . cur; sapce[ 0 ] . cur&#61; k; }
画的太丑了
difference 函数作用&#xff1a;依次此输入 A,B的元素&#xff0c;计算(A−B)U(B−U)(A-B)U(B-U) ( A − B ) U ( B − U ) &#xff0c; &#xff0c;计算结果到space ,S返回数据链表的头结点。
此函数使用许多功能&#xff0c;插入元素&#xff0c;删除元素等功能都在这里有体现
当然你要理解 (A−B)U(B−U)(A-B)U(B-U) ( A − B ) U ( B − U )
void difference ( SLinkList & space, int & S) { InitSpace_SL ( space) ; S&#61; Malloc_SL ( space) ; r&#61; S; scanf ( m, n) ; for ( j&#61; 1 ; j<&#61; m; &#43;&#43; j) { i&#61; Malloc_SL ( space) ; Scanf ( space[ i] . data) ; space[ r] . cur&#61; i; r&#61; i; } space[ r] . cur&#61; 0 ; for ( j&#61; 1 ; j<&#61; n; j&#43;&#43; ) { scanf ( b) ; p&#61; S; k&#61; space[ S] . cur; while ( k!&#61; space[ r] . cur&& space[ k] . data!&#61; b) { p&#61; k; k&#61; space[ k] . cur; } if ( k&#61;&#61; Space[ r] . cur) { i&#61; Malloc_SL ( space) ; space[ i] . data&#61; b; space[ i] . cur&#61; space[ r] . cur; space[ r] . cur&#61; i; } else { space[ p] . cur&#61; space[ k] . cur; if ( r&#61;&#61; k) r&#61; p; } } }
看不明白&#xff0c;多阅读几遍&#xff0c;就明白了。
假设A集合为 {c,b,e,g,f,d} B为 {a,b,n,f}
那样运行结构为
静态链表代码 上述算法&#xff0c;创建链表&#xff0c;插入数据都是整合在difference() 中的。根据上述算法的基本思路&#xff0c;可以实现一下静态链表的基本操作。可以对比我在《 数据结构 第二章 :双链表&#xff0c;循环链表&#xff0c;静态链表以及对比总结》,中实现的静态链表&#xff0c;插入数据平均时间复杂度不在是O(n)&#xff0c;经典的空间换时间 。
对于链表&#xff0c;无非就三种操作&#xff0c;遍历元素&#xff0c;插入元素&#xff0c;删除元素&#xff0c;
在我实现的方法中&#xff0c;规定
链表1&#xff08;备用链表&#xff09;. 头节点 为 SLinkList[0],存储着没有数据的结点 链表2&#xff08;数据链表&#xff09;. 头结点为 SLinkList[1],存储着有数据的结点&#xff0c; 代码
#include #define MaxSize 100 typedef struct { char data; int cur; } SLinkList[ MaxSize] ; bool Init_SLinkList ( SLinkList& L) ; bool Insert_SLinkList ( SLinkList& L, int i, char e) ; int Locate_SLinkList ( SLinkList L, char e) ; bool GetElem_SLinkList ( SLinkList L, int i, char & e) ; bool Delte_SLinkList ( SLinkList& L, int i, char & e) ; int MallocNode ( SLinkList& L) ; bool GetNode_SLinkList ( SLinkList L, int i, int & k) ; bool InsertNext_SLinkList ( SLinkList& L, char e, int k) ; bool DeleteNode_SLinkList ( SLinkList& L, int k) ; void test ( ) { SLinkList L; Init_SLinkList ( L) ; char e; for ( int i&#61; 1 ; i < 10 ; i&#43;&#43; ) { InsertNext_SLinkList ( L, &#39;a&#39; &#43; i- 1 , i) ; } printf ( "插入数据完成^_^\n \n" ) ; int i&#61; L[ 1 ] . cur; int j&#61; 1 ; while ( i) { printf ( "第%3d个数据为 %3c cur为%3d\n" , j, L[ i] . data, L[ i] . cur ) ; i &#61; L[ i] . cur; j&#43;&#43; ; } GetElem_SLinkList ( L, 4 , e) ; printf ( "第 4个数据为 %3c\n\n" , e) ; Insert_SLinkList ( L, 3 , &#39;z&#39; ) ; printf ( "在第3个数据插入 z 完成\n" ) ; GetElem_SLinkList ( L, 3 , e) ; printf ( "第 3个数据为 %3c\n\n" , e) ; GetElem_SLinkList ( L, 4 , e) ; printf ( "第 4个数据为 %3c\n\n" , e) ; printf ( "z是第%3d个元素\n" , Locate_SLinkList ( L, &#39;z&#39; ) ) ; printf ( "删除第 3个元素\n" ) ; Delte_SLinkList ( L, 3 , e) ; i &#61; L[ 1 ] . cur; j &#61; 1 ; while ( i) { printf ( "第%3d个数据为 %3c cur为%3d\n" , j, L[ i] . data, L[ i] . cur) ; i &#61; L[ i] . cur; j&#43;&#43; ; } getchar ( ) ; } int main ( ) { test ( ) ; return 0 ; } bool Init_SLinkList ( SLinkList& L) { for ( int i &#61; 2 ; i < MaxSize - 1 ; i&#43;&#43; ) L[ i] . cur &#61; i&#43; 1 ; L[ 0 ] . cur &#61; 2 ; L[ MaxSize- 1 ] . cur &#61; 0 ; L[ 1 ] . cur &#61; 0 ; return true; } int MallocNode ( SLinkList& L) { int i &#61; L[ 0 ] . cur; if ( L[ 0 ] . cur) L[ 0 ] . cur &#61; L[ i] . cur; return i; } bool DeleteNode_SLinkList ( SLinkList& L, int k) { int p &#61; L[ k] . cur; L[ k] . data &#61; L[ p] . data; L[ k] . cur&#61; L[ p] . cur; L[ p] . cur &#61; L[ 0 ] . cur; L[ 0 ] . cur &#61; p; return true; } bool GetNode_SLinkList ( SLinkList L, int i, int & k) { if ( i< 1 || i> MaxSize - 2 ) return false; int p &#61; L[ 1 ] . cur; int j &#61; 1 ; while ( p && j < i) { p &#61; L[ p] . cur; j&#43;&#43; ; } if ( ! p && j > i) return false; k &#61; p; return true; } bool InsertNext_SLinkList ( SLinkList& L, char e, int k) { if ( k< 1 || k >&#61; MaxSize) return false; int p &#61; MallocNode ( L) ; if ( ! p) return false; L[ p] . data &#61; e; L[ p] . cur &#61; L[ k] . cur; L[ k] . cur &#61; p; return false; } bool Insert_SLinkList ( SLinkList& L, int i, char e) { int k; if ( ! GetNode_SLinkList ( L, i- 1 , k) ) return false; return InsertNext_SLinkList ( L, e, k) ; } int Locate_SLinkList ( SLinkList L, char e) { int k &#61; L[ 1 ] . cur; int i &#61; 1 ; while ( k && L[ k] . data !&#61; e) { k &#61; L[ k] . cur; i&#43;&#43; ; } if ( k &#61;&#61; 0 ) i &#61; 0 ; return i; } bool GetElem_SLinkList ( SLinkList L, int i, char & e) { int k; if ( ! GetNode_SLinkList ( L, i, k) ) return false; e &#61; L[ k] . data; return false; } bool Delte_SLinkList ( SLinkList& L, int i, char & e) { int k; if ( ! GetNode_SLinkList ( L, i, k ) ) return false; e &#61; L[ k] . data; DeleteNode_SLinkList ( L, k) ; return false; }