文章目录
1. 静态链表
静态链表是供缺少指针的高级语言实现链表结构的一种方式。
静态链表融合顺序表和链表的优点，既能快速访问元素，又能快速增加或删除数据元素。
1.1 静态链表的结构概述
静态链表就是用数组来实现链表一对一的线性逻辑结构，数组元素是自定义的结构体。该结构体定义如下：
typedef struct
{
SLDataType data;//数据域：存储数据
int index;//游标：存储直接后继数组中的相对位置。
}SLNode,SList[MAXSIZE];
用数组实现链表关系就称为静态链表。数据域存储数据，游标记录直接后继在数组中的相对位置，模拟实现链表的线性逻辑关系。静态链表内部模拟两个链表：一个是用于存储数据的数据链链表，另一个是用于记录数组中空闲位置的的备用链表。使用备用链表记录数组中的空闲位置，以便数据链表添加新数据时使用。若静态链表中数组下标为0的位置上存有数据，则证明数组已满。
两个链表相应的表头分别叫做备用链表表头和数据链表表头，一般的，备用链表的表头位于数组下标为0的位置且数据域没有存储数值，而数据链表的表头位于数组下标为1的位置。
但数据链表表头是会更改位置的，所以需要一个存储数据链表表头的数值，静态链表第一个位置数据域存储数据链表表头的位置，游标存储下一个空闲位置更加高效，本文以下都是如此存储，在图下：
静态链表头节点data域存储的是数据链表的头，next域存储的时备用链表的头
图中，备用链表上连接的依次是 a[0]、a[2] 和 a[4]，而数据链表上连接的依次是 a[1]、a[3] 和 a[5]。
1.2 静态链表实现过程分析
数据链表未初始化：数组中所有位置被链接在备用链表上
向静态链表中添加数据时，需要从备用链表中摘除结点，供新数据使用
静态链表添加数据需提前摘除结点，供新数据添加。静态链表添加元素1，添加元素2
1.3 静态链表的基本操作
静态链表基本操作重点就在于添加删除操作，其余都是小问题，所以本文重点解决添加删除操作
1.3.1 静态链表添加元素
首先清楚静态链表中的数据不是按顺序存储的，这个数组知识一个存储数据的工具，我们应该关注的是游标所代表的静态链表的逻辑结构，而非静态链表的存储结构
在静态链表逻辑结构中第n位置插入元素x，实现思路：
从备用链表中取除空闲位置存储x，构成新的结点，这里用newNode指代。更改静态链表逻辑结构中第n-1和newNode两个结点中的游标，实现逻辑结构的更改。
实现：
//将data放入就被用链表中空闲位置，返回对应下标
int newNode(SList sp, int data)
{
assert(sp[0].next);//断言是否还有空余位置
//data放入空闲位置
int cur = sp[0].next;
sp[cur].data = data;
//重新设置备用链表
sp[0].next = sp[cur].next;
//将包装好的结点，next置空
sp[cur].next = 0;
return cur;
}
//静态链表逻辑结构第index个位置插入元素
void SListPush(SList sp, int index, SLDataType data)
{
assert(sp);
if (index == 1 )
{
//备用链表获取空间存储data,并返回静态链表中数组下标
int cur = newNode(sp, data);
sp[cur].next = sp[0].data;//其实该数值在函数里为0了
sp[0].data = cur;
return;
}
else
{
int dest = sp[0].data;//指向数据链表头
for (int i = 1; dest != 0;)
{
if (i != index - 1)
{
dest = sp[dest].next;
i++;
}
else
{
//备用链表获取空间存储data,并返回静态链表中数组下标
int cur = newNode(sp, data);
sp[cur].next = sp[dest].next;
sp[dest].next = cur;
return;
}
}
}
printf("index值不合规\n");
return;
}
1.3.2 静态链表的删除操作
//静态链表逻辑结构第index个位置删除
void SListPop(SList sp, int index)
{
int prev = sp[0].data;
if (index == 1&&prev!=0)//头删需要特殊处理
{
sp[0].data = sp[prev].next;
//重新设置备用链表
int dest = prev;
int last = sp[0].next;//指向备用数据链表的头
while (sp[last].next)
{
last = sp[last].next;
}
sp[last].next = dest;
sp[dest].next = 0;
return;
}
else
{
for (int i = 1; prev != 0;)
{
if (i = index - 1)//找到第index的前一个
{
int dest = sp[prev].next;
sp[prev].next = sp[dest].next;
//重新设置备用链表
int last = sp[0].next;//指向备用数据链表的头
while (sp[last].next)
{
last = sp[last].next;
}
sp[last].next = dest;
sp[dest].next = 0;
return;
}
else
{
prev = sp[prev].next;
i++;
}
}
}
printf("index值不合规\n");
return;
}
1.3.3 静态链表总实现
SListArray.h
#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#define MAXSIZE 10
typedef int SLDataType;
typedef struct
{
SLDataType data;//数据
int next;//游标，
}SLNode, SList[MAXSIZE];
//静态链表初始化
void SListInit(SList sp);
//静态链表逻辑结构第index个位置插入元素
void SListPush(SList sp, int index, SLDataType data);
//静态链表逻辑结构第index个位置删除
void SListPop(SList sp, int index);
//静态链表查找指定位置元素，并返回该元素的在数组中的下标
int SListSearch(SList sp, SLDataType data);
//将静态链表中第index位置数据修改为dest
void SListAlter(SList sp, int index, SLDataType dest);
//打印静态链表
void SListPrint(SList sp);
SListArrays.c
#include"SListArray.h"
//静态链表初始化
void SListInit(SList sp)
{
//备用链表初始化
for (int i = 0; i < MAXSIZE; i++)
{
sp[i].next = i + 1;
}
sp[MAXSIZE - 1].next = 0;
sp[0].data = 0;
//静态链表的备用链表表头指向sp[0],数据链表表头为0表示未插入数据，此时数据链表为空;
}
//将data放入就被用链表中空闲位置，返回对应下标
int newNode(SList sp, int data)
{
assert(sp[0].next);//断言是否还有空余位置
//data放入空闲位置
int cur = sp[0].next;
sp[cur].data = data;
//重新设置备用链表
sp[0].next = sp[cur].next;
//将包装好的结点，next置空
sp[cur].next = 0;
return cur;
}
//静态链表逻辑结构第index个位置插入元素
void SListPush(SList sp, int index, SLDataType data)
{
assert(sp);
if (index == 1 )
{
//备用链表获取空间存储data,并返回静态链表中数组下标
int cur = newNode(sp, data);
sp[cur].next = sp[0].data;//其实该数值在函数里为0了
sp[0].data = cur;
return;
}
else
{
int dest = sp[0].data;//指向数据链表头
for (int i = 1; dest != 0;)
{
if (i != index - 1)
{
dest = sp[dest].next;
i++;
}
else
{
//备用链表获取空间存储data,并返回静态链表中数组下标
int cur = newNode(sp, data);
sp[cur].next = sp[dest].next;
sp[dest].next = cur;
return;
}
}
}
printf("index值不合规\n");
return;
}
//静态链表逻辑结构第index个位置删除
void SListPop(SList sp, int index)
{
int prev = sp[0].data;
if (index == 1&&prev!=0)//头删需要特殊处理
{
sp[0].data = sp[prev].next;
//重新设置备用链表
int dest = prev;
int last = sp[0].next;//指向备用数据链表的头
while (sp[last].next)
{
last = sp[last].next;
}
sp[last].next = dest;
sp[dest].next = 0;
return;
}
else
{
for (int i = 1; prev != 0;)
{
if (i = index - 1)//找到第index的前一个
{
int dest = sp[prev].next;
sp[prev].next = sp[dest].next;
//重新设置备用链表
int last = sp[0].next;//指向备用数据链表的头
while (sp[last].next)
{
last = sp[last].next;
}
sp[last].next = dest;
sp[dest].next = 0;
return;
}
else
{
prev = sp[prev].next;
i++;
}
}
}
printf("index值不合规\n");
return;
}
//静态链表查找指定位置元素
int SListSearch(SList sp, SLDataType data)
{
int cur = sp[0].data;
while (cur)
{
if (sp[cur].data == data)return cur;
else cur = sp[cur].next;
}
printf("所找元素不存在\n");
}
//将静态链表中第index位置数据修改为dest
void SListAlter(SList sp, int index, SLDataType dest)
{
sp[index].data = dest;
}
//打印静态链表
void SListPrint(SList sp)
{
assert(sp);
assert(sp[0].data);//如果为零说明是空静态链表
int index = sp[0].data;
while (index)
{
printf("%d ", sp[index].data);
index = sp[index].next;
}
printf("\n");
}
main测试
#include"SListArray.h"
void test()
{
SList S;
SListInit(S);
SListPush(S, 1, 1);
SListPush(S, 2, 2);
SListPush(S, 3, 3);
SListPrint(S);
SListPush(S, 1, 4);
SListPrint(S);
SListPush(S, 2, 5);
SListPrint(S);
SListPop(S, 1);
SListPrint(S);
SListPop(S, 2);
SListPrint(S);
SListPush(S, 3, 8);
SListPrint(S);
int temp = SListSearch(S, 5);
printf("%d\n", temp);
SListAlter(S, temp, 666);
SListPrint(S);
}
int main()
{
test();
}
测试结果：
本文含有隐藏内容，请 开通VIP 后查看