文章目录

• slist头文件
• slist.cpp文件

slist头文件

#pragma once
//静态链表,利用顺序表模拟链表
//静态链表保护两条链表,一条为有效数据链表,另一条为空闲节点链表
//有效数据链表为带头结点的循环链表,且头结点在0下标
//空闲节点链表为带头结点的循环链表,且头结点在1下标
//注意,添加一条空闲节点链表的目的是让插入数据时找空闲节点的速度变为O(1)
//静态链表的优点:和顺序表对比,插入和删除数据时不需要移动数据O(1)
//静态链表的优点:和链表对比,不需要频繁的创建和删除节点
//静态链表的缺点:和顺序表对比需要增加一个next
//静态链表可以动态增长,满后扩容,只是需要将扩容的内存添加到空闲链表中

#define MAXSIZE 10
typedef struct SNode
{
	int data;//数据
	int next;//后继指针(下标)
}SNode, SLinkList[MAXSIZE];

//SLinkList s;//s长度为MAXSIZE的结构体数组

//typedef SNode Arr[MAXSIZE];//长度为MAXSIZE的结构体数组类型
//Arr a;//a是长度为MAXSIZE的结构体数组

//初始化
void InitList(SNode* ps);

//头插
bool Insert_head(SNode* ps, int val);

//尾插
bool Insert_tail(SNode* ps, int val);

//判空
bool IsEmpty(SNode* ps);

//获取数据节点个数
int GetLength(SNode* ps);

//在ps中查找第一个key,找到返回节点地址,没有找到返回NULL
SNode* Search(SNode* ps, int key);

//删除第一个val值
bool DelVal(SNode* ps, int val);

//输出
void Show(SNode* ps);

//清空数据
void Clear(SNode* ps);

slist.cpp文件

#include <stdio.h>
#include <assert.h>
#include "slist.h"

//初始化
void InitList(SNode* ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;
	//处理有效链表
	ps[0].next = 0;//0下标为有效数据链表的表头,且该链为循环链表

	//处理空闲链表
	for (int i = 1; i < MAXSIZE; i++)
	{
		ps[i].next = i + 1;
	}
	ps[MAXSIZE - 1].next = 1;//1下标为空闲链表的表头
}

//判满
static bool IsFull(SNode* ps)
{
	//ps->next;
	//(ps+1)->next;
	return ps[1].next == 1;//空闲链表没有数据节点
}

//头插
bool Insert_head(SNode* ps, int val)
{
	if (IsFull(ps))
		return false;
	//获取一个空闲节点,空闲链表的第一个数据节点
	int p = ps[1].next;

	//将空闲节点从空闲链中剔除 ***
	ps[1].next = ps[p].next;

	//放入数据
	ps[p].data = val;

	//将空闲节点插入到有效数据链中
	ps[p].next = ps[0].next;
	ps[0].next = p;

	return true;
}

//尾插
bool Insert_tail(SNode* ps, int val)
{
	int p = 0;
	for (; ps[p].next != 0; p = ps[p].next)
	{
		;
	}

	int q = ps[1].next;
	ps[1].next = ps[q].next;
	ps[q].data = val;
	ps[q].next = ps[p].next;
	ps[p].next = q;

	
	return true;
}

//判空
bool IsEmpty(SNode* ps)
{
	return ps[0].next == 0;//有效链表没有数据节点
}

//获取数据节点个数
int GetLength(SNode* ps)
{
	int i = 0;
	for(int p = ps[0].next; p != 0; p = ps[p].next)
	{
		i++;
	}
	return i;
}

//在ps中查找第一个key,找到返回节点地址,没有找到返回NULL
SNode* Search(SNode* ps, int key)
{
	for (int p = ps[0].next; p != 0; p = ps[p].next)
	{
		if (ps[p].data == key)
			return &ps[p];
	}
	return NULL;
}

//获取val的前驱下标
int GetPrio(SNode* ps, int key)
{
	for (int p = 0; ps[p].next != 0; p = ps[p].next)
	{
		//if(ps[p].data == key)
		//if(ps[ps[p].next].data == key)//p的后继的data是否和key相同
		int q = ps[p].next;//p的后继
		if (ps[q].data == key)
		{
			return p;
		}
	}
	return -1;//无效下标
}

//删除第一个val值
bool DelVal(SNode* ps, int val)
{
	//获取val的前驱
	int p = GetPrio(ps, val);
	if (p < 0)
		return false;
	//将节点q从有效链中删除
	int q = ps[p].next;
	ps[p].next = ps[q].next;

	//将节点q添加到空闲链中
	ps[q].next = ps[1].next;//1是空闲链的头结点下标
	ps[1].next = q;

	return true;
}


//输出
void Show(SNode* ps)
{
	for (int p = ps[0].next; p != 0; p = ps[p].next)//0是优先链的头结点下标
	{
		printf("%d ", ps[p].data);
	}
	printf("\n");
}

//清空数据
//将有效链中的所有数据节点剔除,全部插入到空闲链中
void Clear(SNode* ps)
{
	int p = 0;
	for (; ps[p].next != 0; p = ps[p].next)
	{
		;
	}
	int q = ps[1].next;
	ps[p].next = q;
	ps[1].next = ps[0].next;
	ps[0].next = 0;
	
}