静态链表相关算法学习

雨点打透心脏的1/2处 2022-06-03 05:45 286阅读 0赞

大话数据结构学习笔记—静态链表学习

c语言真是好东西，它具有指针能力，使得它可以非常容易地操作内存中的地址和数据，这比其他高级语言更加灵活方便。

后来的面向对象的语言，如java、C\#等，虽然不使用指针，但是因为启用了对象引用机制，从某种角度也间接实现了指针的  
某些作用。但是对一些Basic、Fortran等早期的编程高级语言，由于没有指针,链表结构按照前面我们的讲法，它就没法实现了。  
有人想出来用数组来代替指针。他们是怎么做到的呢？  
首先我们让数组的元素都是由2个数据域组成，data和cur。也就说，数组的每个下标都对应一个data和一个cur。数据域，用来  
存放数据元素，也就是我们要处理的数据；而游标相当于单链表中的next指针，存放该元素的后继在数组中的下标。  
我们把这种用数组描述的链表叫做静态链表。

为了方便插入数据，我们通常会把数据建立的大一些，以便有一些空闲空间可以便于插入时不溢出。

静态链表将数组第一个元素用来指向备用链表（链表中没用到的空间）中的第一元素，最后一个元素用来指向第一个存数据的元素相当于头结点的作用。

数据结构

1、        用结构体模拟数组成员

a)    typedef struct Element\{DataTypedata,int cur\}

2、        用结构体数组模拟静态链表相关算法，长度确定后不可变 。

a)    typedef Element StaticLinkStatic\[MAXSIZE\] ;

初始化

数组第一个元素指向第一个可用元素也就是第二个元素下标\[1\]。

数组最后一个元素，类似头指针作用，指向第一个存放数据元素的下标，空链表 cor 为0,其他空闲元素可初始化依次指向其后面一个元素。

插入操作

动态链表中分配空间使用malloc函数，但是静态链表中，实质上我们定义链表时，空间大小已经确定了，那么我们要插入数据同样也要一个空间，只不过空间已经在链表中分配了只不过是空闲的还没拿出来用了，我们需要一个类似的函数将空闲位置拿来存入我们需要的数据，这里涉及到几个要操作的地方

1)   取出一个备用元素后，那么第一个元素指向备用链表要改变指向，指向取出元素的后继元素。其实就是完成分配空间操作。

2)   插入元素时，要找到插入元素位置前一个元素 i-1，需要改变他的cur 指向改为插入元素的 下标，而插入元素 的cur指向 要改为 i-1指向元素的下标。

删除操作

删除元素空间，因为是静态链表空间已经固定，不能真正的在内存将其释放而是将其放到静态链表的备用链表中，可以继续供链表所使用。同样需要类似free函数来释放元素，操作和插入相反。

1）        将删除元素的 前置结点 cur 指向 删除元素的后置结点的下标

2）        释放删除元素所占位置，将其置为备用链中的第一个可用元素

其他操作

获取链表元素个数

最后一个元素cur为0 根据这个条件计数

打印链表元素

下面看下实现代码

#define MAXSIZE 500
    #define OK 1
    #define ERROR 0
    #include <stdio.h>
    
    typedef int Status;
    typedef char DataType;
    typedef struct Element Element;
    typedef Element StaticLinkList[MAXSIZE];//结构体数组
    struct Element {
    	DataType data;//数据
    	int cur;//游标，后继结点的下标
    };
    //初始化静态链表
    //静态链表将数组第一个元素用来指向备用链表中的第一元素，最后一个元素用来指向第一个存数据的元素 相当于头结点的作用,下标0和num-1 作为对外展示的链表元素。
    Status initSLL(StaticLinkList sll) {
    	int i = 0;
    	//由于是空链表，list[0].cur 指向下标为2到MAXSIZE-2元素备用链表，这样刚好一个指向一个
    	//[0].cur为1 指向下标为1的元素，[1].cur位2指向下标为2的元素，依次类推
    	//注意[MAXSIZE-2]为最后一个可用元素，指向[MAXSIZE-1]元素，做特殊处理，大话数据结构中 没有做处理。
    	for (i = 0; i < MAXSIZE; i++) {
    		sll[i].cur = i + 1;
    	}
    	sll[MAXSIZE - 2].cur = 0;
    	sll[MAXSIZE - 1].cur = 0;//空链表，它的cur是存储元的第一个位置的下标。
    	return OK;
    }
    //创建一个可以使用的下标元素,将备用链中的第一个元素下标返回，让静态链表第一个元素重新指向下一个备用元素。
    int mollocEle(StaticLinkList sll) {
    	int i = (sll)[0].cur;
    	if (i) {//有可用的备用元素
    		(sll)[0].cur = (sll)[i].cur;
    	}
    	return i;
    }
    //释放第k个元素的让其成为备用链表中的元素，让静态链表第一个元素（下标为0）的元素指向它，它指向原来备用链第一个元素 
    void freeEle(StaticLinkList sll,int p) {
    	sll[p].cur = sll[0].cur;
    	sll[0].cur = sll[p].cur;
    	return;
    }
    
    //打印静态链表内容
    void printStaticLinkList(StaticLinkList sll)
    {
    	int begin = sll[MAXSIZE - 1].cur;//找到起始元素
    	Element e;
    	//begin为0 要么为空链表 要么链表数据遍历完毕
    	while(begin) {
    		e = sll[begin];
    		printf("%c ", e.data);
    		begin = e.cur;
    	}
    	return;
    }
    int lengthSSL(StaticLinkList sll) {
    	int begin = sll[MAXSIZE - 1].cur;
    	int i = 0;
    	//begin 为0 要么为空链表 要么链表遍历完毕
    	while (begin)
    	{
    		begin = sll[begin].cur;
    		i++;
    	}
    	return i;
    }
    //插入位置i，找到i-1元素，将i元素的cur指向i-1的后继元素，将i-1元素指向插入元素即可
    //i不是数组下标而是链表中的第i个元素，cur存储的才是下标
    Status insertSLL(StaticLinkList sll, int i, DataType data) {
    	if (i<1 || i>lengthSSL(sll)+1) {//可以插在元素末尾！比如说有5个元素可以插在第6位置，但不能插入到第7个以及后面
    		return ERROR;
    	}
    	int j = mollocEle(sll);
    	if (!j) {//分配空间失败
    		return ERROR;
    	}
    	int begin = MAXSIZE - 1;//第一次进入循环，找到第一个数据元素
    	for (size_t k = 1; k <= i-1; k++)
    	{
    		begin = sll[begin].cur;
    	}
    	//循环结束 begin为i-1个元素的下标
    	sll[j].cur = sll[begin].cur;
    	sll[j].data = data;
    	sll[begin].cur = j;
    
    	return OK;
    }
    //删除位置i，找到i-1个元素，将第i个元素的cur指向i-1的后继元素，将i-1元素指向插入元素即可
    Status delSLLEle(StaticLinkList sll, int i) {
    	if (i<1 || i>lengthSSL(sll)) {
    		return ERROR;
    	}
    	int begin = MAXSIZE - 1;//第一次进入循环，找到第一个数据元素
    	for (size_t k = 1; k <= i - 1; k++)
    	{
    		begin = sll[begin].cur;
    	}
    	//循环结束 begin为i-1个元素的下标
    	int curE = sll[begin].cur;//删除元素的下标
    	sll[begin].cur = sll[curE].cur;//i-1个元素指向 i+1个元素
    	freeEle(sll,curE);//释放i元素，放回备用链表
    	return OK;
    }
    int main() {
    	StaticLinkList L;
    	Status i;
    	i = initSLL(L);
    	printf("初始化L后：L.length=%d\n", lengthSSL(L));
    	/*
    	注意第一个元素必须插入到第一位置！
    	因为空表里面没有元素，插入位置不在范围内同样不能插入
    	插入范围 1 ~ 现有元素个数+1 都可以
    	*/
    	i = insertSLL(L, 1, 'A');
    	i = insertSLL(L, 2, 'B');
    	i = insertSLL(L, 3, 'C');
    	i = insertSLL(L, 4, 'D');
    	i = insertSLL(L, 5, 'E');
    
    	printf("\n在L的表尾依次插入ABCDE后：\nL.data=");
    	printStaticLinkList(L);
    
    	i = insertSLL(L, 3, 'Y');
    	printf("\n在L的“B”与“C”之间插入“Y”后：\nL.data=");
    	printStaticLinkList(L);
    
    	i = delSLLEle(L, 2);
    	printf("\n在L的删除“B”后：\nL.data=");
    	printStaticLinkList(L);
    
    	printf("\n");
    	
    	return 0;
    }

验证结果截图：

![Center][]

[Center]: /images/20220603/1df29f1c33d04485bc52a8b43efd1a1e.png