静态表 (C语言实现静态链表) ------- 算法笔记002

傷城~ 2023-06-30 15:57 13阅读 0赞

## 概念理解 ##

> 在c语言中我们可以通过创建结构体和指针来建立一个链表，但是有的编程语言不支持指针，如java，直接将指针封装起来。在这种编程语言的背景下我们创建一个链表可以通过数组的方式来模拟，称之为静态链表。为何说是静态的呢》因为数组模拟的链表的长度是固定的。

###### 静态链表的结构 ######

> 我们可以理解为一组结构体数组来模拟链表的情况

### 静态链表的创建插入原理图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]

### 静态链表实现增删的原理图 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70 1]

# 程序代码 #

> 静态链表的初始化

//结构体定义
    typedef struct { 
    	int data;
    	int cur;
    } List,StaticList[MaxNumOfNode];

//初始化链表
    void init(StaticList space){ 
    	int index;
    	for(index=0;index< MaxNumOfNode;index++){ 
    		space[index].cur=index+1;
    		space[index].data=-1;
    	}
    	space[MaxNumOfNode-1].cur=0;
    }

> 初始化数值2000

//put初始值2000
    
    void startPutData(StaticList space){ 
    	int i;
    	int count=1;
    	int data[4]={ 2,0,0,0,};
    	for(i=1;i<sizeof(data)/sizeof(int)+1;i++){ 
    		space[i].data=data[i-1]; 
    	}
    	space[0].cur=i;
    	space[i-1].cur=0;
    	space[MaxNumOfNode-1].cur=1;
    }

> 插入数据

//分配静态链表空间,在插入方法中调用
    //用来判断是否存在空间，存在则将第一个头数组中的cur值指向下一个 
    int Malloc_SLL(StaticList space){ 
    	int index=space[0].cur;
    	BOOL isend=false;
    	if(space[index].cur==1){ 
    		isend=true;
    	}else{ 
    		space[0].cur=space[index].cur;
    	}
    	if(end){ 
    		return -1;
    	}else{ 
    		return index;
    	}
    	
    } 
    
    //插入数据函数
    Status listInsert(StaticList List,int num,ElemtInt e){ 
    	int result=Malloc_SLL(List);
    	int index;
    	if(result!=-1){ 
    		index=result;
    	}else{ 
    		return -1;
    	}
    	List[index].data=e;
    	
    	int k= MaxNumOfNode-1;
    	int m=0;
    	//定位到要插入的节点前一个节点 
    	do{ 
    		k=List[k].cur;
    		m++;
    		
    	}while(m<num-1);
    	
        //假如要在数据 5 2 1 3 1 4 中的第3个地方插入0,则k是负责遍历到第三个数1的前一个数的下标即k是2的下标，在此基础上通过修改游标值实现数据的插入。
        List[index].cur=List[k].cur;
    	List[k].cur=index;
    	return 1;	
    }

> 删除数据的代码实现

//删除数据
     Status deleteList(StaticList List,int num){ 
     	//num为要删除的第几个数
     	//判断num是否超出范围
     	if(num<=0||num>=MaxNumOfNode-1){ 
     		return -1;
    	 }
    	 int k=MaxNumOfNode-1;
    	 int m=0;
    	 int index=0;
    	 //当要删除的数是第一个数的情况
    	 if(num==1){ 
    	 	index=List[k].cur;//index为第一个数的下标
    		List[k].cur=List[index].cur;//第二个数据变成第一个数据
    		List[index].data=-1;
    		List[index].cur=List[0].cur;
    		List[0].cur=index; 
    	 }else{ 
    	 //与上面一样，找到要删除的前一个数据
    	 	 do{ 
    		 	k=List[k].cur;//1
    		 	m++;//1
    		 }while(m<num-1);//m<1
    		 
    		 //如果要删除的是最后一个数据 
    		 if(List[List[k].cur].cur==0){ 
    		 	//删除操作 
    		 	index=List[k].cur;
    			List[k].cur=0;
    			List[index].data=-1;
    			List[index].cur=List[0].cur;
    			List[0].cur=index;
    		 	return 1;
    		 } 
    		 
    		 //删除操作
    		  
    		index=List[k].cur;
    		List[k].cur= List[index].cur;
    		List[index].cur=List[0].cur;
    		List[index].data=-1;
    		List[0].cur=index;
    	}
    		return 1;
    
     }

*注：完整的程序源码已上传资源*或者去我的博客下载：changlon.xyz

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200118195355751.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200118195501298.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1MzkyNzMz,size_16,color_FFFFFF,t_70