《数据结构与算法》——线性表之静态链表（staticLinkList）总结

向右看齐 2021-11-09 01:22 166阅读 0赞

# 《数据结构与算法》——线性表之静态链表（staticLinkList）总结 #

本来不准备对这种数据结构进行实现，但是后来发现考纲里边有这个结构，而且我感觉这个结构还挺有意思，所以就实现并总结了一下。

定义

结构

函数列表

C++实现及测试代码

错误总结

参考文献

--------------------

## 定义 ##

什么是静态链表？顾名思义，首先它是一个线性结构——表，其次它在逻辑上属于链表，但它没有普通链表那样动态灵活，而是一个静态的结构。

在某些高级语言中（譬如VB）是没有指针这个概念存在的，那只能用顺序表进行存储线性表吗？这样的话增删操作就会很麻烦，所以人们想出一个办法——用数组来描述链表。（它是不是这样诞生的，我不知道，胡诌的）

## 结构 ##

struct Node{
    ElemType data;
    int next;
    };
    struct SLList{
    Node data[Max];
    int cur;//作为游标始终指向头位置
    };

在本文中为了方便操作，在原有定义上添加了部分变量，结构体定义如下：

struct staticLinkListNode{
 	int pre;//pre指针 
 	ElemType data;//数据值 
 	int next;//next指针 
 };
 typedef staticLinkListNode slListNode;
 
 struct staticLinkList{
 	slListNode *data;//单型数据 
 	int cur;//游标 
 	set<int> ssEmpty;//记录空位置 ，下标
 	int max;//当前链表最大容量
 	int len;//当前长度
 	set<int> ssNEmpty;//记录插入位置，下标 
 };
 typedef staticLinkList slList;

## 函数列表 ##

void InitList(slList &sls);//初始化 
    bool ListEmpty(slList sls);//判空 
    int ListLength(slList sls);//长度 
    void DeleteList(slList &sls , ElemType x);//删除元素
    ElemType LocateList(slList sls , int num);//定位
    int SerchList(slList sls , ElemType x);//查找值的位置 
    void DestroyList(slList &sls);//销毁栈
    void InsertList(slList &sls , ElemType &x , int loc = -65530);//插入值 
    void PrintList(slList sls);//打印链表

## C++实现及测试代码 ##

/*****************************
 Copyright:Kwzc4 
 Author:Kwzc4
 Date:2019-08-06
 Description:对静态链表以结构体
 的存储方式进行定义并对增删改查
 等功能进行实现 
 ******************************/
 
 /*编译环境：
 win10专业版
 DEV C++ 5.11
 TDM-GCC 4.9.2 64bit
 */
 #include<iostream>
 #include<set>
 #include<stdlib.h>
 using namespace std;
 typedef int ElemType;
 #define MAX 100
 
 struct staticLinkListNode{
 	int pre;//pre指针 
 	ElemType data;//数据值 
 	int next;//next指针 
 };
 typedef staticLinkListNode slListNode;
 
 struct staticLinkList{
 	slListNode *data;//单型数据 
 	int cur;//游标 
 	set<int> ssEmpty;//记录空位置 ，下标
 	int max;//当前链表最大容量
 	int len;//当前长度
 	set<int> ssNEmpty;//记录插入位置，下标 
 };
 typedef staticLinkList slList;
 
 
 void InitList(slList &sls);//初始化 
 bool ListEmpty(slList sls);//判空 
 int ListLength(slList sls);//长度 
 void DeleteList(slList &sls , ElemType x);//删除元素
 ElemType LocateList(slList sls , int num);//定位
 int SerchList(slList sls , ElemType x);//查找值的位置 
 void DestroyList(slList &sls);//销毁栈
 void InsertList(slList &sls , ElemType &x , int loc = -65530);//插入值 
 void PrintList(slList sls);//打印链表 
 
 void InitList(slList &sls){//初始化 
 	sls.cur = -1;
 	sls.len = 0;
 	sls.max = MAX;
 	sls.data = (slListNode*)malloc(sls.max*sizeof(slListNode));
 	for(int i = 0;i<MAX;i++){
 		sls.data[i].next = -1;
 		sls.data[i].pre = -1;
 		sls.ssEmpty.insert(i);//添加空位置	
 	}
 }
 
 bool ListEmpty(slList sls){//判空 
 	return (sls.len == 0 );
 }
 
 int ListLength(slList sls){//长度 
 	return sls.len;
 }
 
 void DeleteList(slList &sls , ElemType x){//删除元素
 	if(ListEmpty(sls))
 		return ;
 	int loc=-65530;
 	for(set<int>::iterator it = sls.ssNEmpty.begin();it!=sls.ssNEmpty.end();it++)//遍历集合
 		if(sls.data[*it].data==x){
 			loc = *it ;
 			break;
 		}
 	if(loc!=-65530){
 		sls.data[sls.data[loc].pre].next = sls.data[loc].next;
 		sls.data[sls.data[loc].next].pre = sls.data[loc].pre;
 		sls.data[loc].next = -1;
 		sls.data[loc].pre = -1;
 		sls.ssEmpty.insert(loc);
 		sls.ssNEmpty.erase(loc);
 		sls.len --;
 	}
 	else 
 		cout<<"No data"<<endl;		
 }
 
 ElemType LocateList(slList sls , int num){//定位
 	if(num<=0||num>sls.len)
 		return -65530;
 	int cur = sls.cur;
 	int i = 1 ;
 	while(i++<num)
 		cur = sls.data[cur].next;
 	return sls.data[cur].data;
 }
 
 int SerchList(slList sls , ElemType x){//查找值的位置 
 	int loc = -65530;
 	int cur = sls.cur;
 	int i = 1 ;
 	while(i++<sls.len && sls.data[cur].data!=x )
 		cur = sls.data[cur].next;
 	if (sls.data[cur].data==x)
 		loc = i; 
 	return loc-1;
 }
 
 void DestroyList(slList &sls){//销毁 
 	free(sls.data);
 	sls.ssEmpty.clear();
 	sls.ssNEmpty.clear();
 	sls.len = 0;
 	sls.max = 0;
 }
 
 void InsertList(slList &sls , ElemType x , int loc = -65530){//插入值
 /*当 loc为默认值-65530时，则进行头插法*/
 	if(loc==-65530)//确定下标位置
 		loc = 1;
 	else if(loc<1||loc>sls.len+1)
 		return;
 	int temp = sls.cur; //当前头结点 
 	//cout<<temp<<endl;
 	int i = 1;//记录顺序数下标 
 	while(i++<loc)//查找应插入的位置 
 		temp = sls.data[temp].next; 
 	
 	if(sls.max<sls.len+1){//重新分配空间 
 		slListNode *sl = (slListNode *)realloc(sls.data,(sls.max+50)*sizeof(slListNode));
 		if(!sl){
 			cout<<"realloc fail"<<endl;
 			exit(-1);
 		}
 		sls.data = sl;
 		for(int j = sls.max;j<sls.max+50;j++)
 			sls.ssEmpty.insert(j);
 		sls.max +=50;
 	}
 	i = *sls.ssEmpty.begin();//选出一个空位置
 	sls.data[i].next = temp;
 	sls.data[i].data = x;
 	sls.data[i].pre = sls.data[temp].pre;
 	if(loc!=1)
 		sls.data[sls.data[temp].pre].next = i;
 	else 
 		sls.cur = i;
 	sls.data[temp].pre = i; 
 	sls.len++;
 	sls.ssEmpty.erase(i);
 	sls.ssNEmpty.insert(i);
 }
 
 void PrintList(slList sls){//打印链表 
 	if (ListEmpty(sls)){
 		cout<<"[ ]"<<endl;
 		return;
 	}	
 	int i = sls.cur;
 	cout<<"[ ";
 	while(sls.data[i].next!=-1){
 		cout<<sls.data[i].data<<" ";
 		i = sls.data[i].next;
 	}
 	cout<<sls.data[i].data<<" ]"<<endl;;
 }
 
 int main(){
 	slList sls;
 	InitList(sls);
 	cout<<"初始化链表......";PrintList(sls);
 	cout<<"链表长度：\t"<<ListLength(sls)<<endl;
 	cout<<"头插法: \t"; InsertList(sls,1);PrintList(sls);
 	cout<<"头插法: \t"; InsertList(sls,2);PrintList(sls);
 	cout<<"头插法: \t"; InsertList(sls,3);PrintList(sls);
 	cout<<"头插法: \t"; InsertList(sls,4);PrintList(sls);
 	cout<<"头插法: \t"; InsertList(sls,5);PrintList(sls);
 	cout<<"第3位插入:\t"; InsertList(sls,6,3);PrintList(sls);
 	cout<<"第4位查找:\t"<<LocateList(sls,4)<<endl;
 	cout<<"查找元素1位置:\t"<<SerchList(sls,1)<<endl;
 	cout<<"删元素除4: \t"; DeleteList(sls,4);PrintList(sls);
 	cout<<"链表此时长度：\t"<<ListLength(sls)<<endl;
 	cout<<"销毁链表: \t"; DestroyList(sls);PrintList(sls);
 	cout<<"链表最终长度：\t"<<ListLength(sls)<<endl;
 	return 0;
 }

运行结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0t3emM0_size_16_color_FFFFFF_t_70][]

## 错误总结 ##

1.第一次使用集合set，对于其中的方法不熟悉，其中begin()和end()函数的返回值为指针，需要取内容才可使用；

2.malloc()函数需要引入头文件stdlib.h；

## 参考文献 ##

严蔚敏，吴伟民. 数据结构（C语言版）\[M\]. 北京： 清华大学出版社，2013.

**如有错误，还请朋友不吝指正。**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0t3emM0_size_16_color_FFFFFF_t_70]: /images/20211108/10cdaa8917e34b27960ac128a2ec5f97.png