静态链表(C语言数据结构)

2021-09-23

静态链表

线性存储结构的一种,兼顾顺序表和链表的优点,是顺序表和链表的升级;静态链表的数据全部存储在数组中(顺序表),但存储的位置是随机的,数据直接的一对一关系是通过一个整型变量(称为“游标”,类似指针的功能)维持。

优点:在插入和删除操作肘,只需要修改游标,不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点

缺点:没有解决连续存储分配(数组)带来的表长难以确定的问题。失去了顺序存储结构随机存取的特性。

分类:静态链表

静态链表的基本操作:

方法说明目的
InitList(LinkList  &L)初始化线性表构造一个空的顺序线性表
MallocSSL(StaticLinkList space)销毁线性表销毁顺序线性表L
FreeSSL(StaticLinkList space, int k)清空链表将L重置为空表
Empty(StaticLinkList L)判断链表是否为空判断是否为空表
ListLength(StaticLinkList L)返回值类型int返回L中数据元素个数
ListInsert(StaticLinkList L, int i, ElemType e)查找元素用e返回L中第i个数据元素的值
ListDelete(StaticLinkList L, int i)返回值类型int返回L中第1个与e满足关系的数据元素的位序
Status ListTraverse(StaticLinkList L)插入前驱结点在结点p位置插入一个前驱结点,数据域设为e
visit(ElemType c)插入后继结点在结点p位置插入一个后继结点,数据域设为e

代码实现

#include<stdio.h>

/* 状态码 */
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 1000

typedef int ElemType;  /* ElemType根据实际情况而定,这里假定为 int */
typedef int Status;   /* 状态代码 */

typedef struct {
 ElemType data;
 int cur;   /* 游标cursor 值为0时表示无指向 */
}Component, StaticLinkList[MAXSIZE];



/*初始化静态链表  建立一个空的线性表L
返回值类型 Status(自定义类型)
函数名 InitList 初始化表
参数列表 StaticLinkList space  */

Status InitList(StaticLinkList space) {
 int i;
 for (i = 0; i < MAXSIZE - 1; i++)
 {
  space[i].cur = i + 1;
 }
 space[MAXSIZE - 1].cur = 0;  /* 目前静态链表为空,最后一个元素的游标cur为空 */
 return TRUE;
}



/* 为了解决静态链表(数组)中的有些分量未被使用,我们可以将所有未被使用的以及已被删除的分量用游标链成一个备用的链表
我们通常把未被使用的的数组元素称为备用链表,数组的第一个元素,即下标为0的元素的cur存放备用链表的第一个结点的下标*/

/* 若备用空间链表为空,则返回分配的结点的下标,否则返回0
返回值类型 int
函数名 MallocSLL
参数列表 StaticLinkList space */

int MallocSSL(StaticLinkList space) {
 int i = space[0].cur;    /* 将当前数组第一个元素的游标cur存的值赋值给i,就是要返回的第一个备用空闲的下标 */
 if (space[0].cur)
 {
  space[0].cur = space[i].cur; /* 更新备用链表的第一个结点,这里是更新为分配结点的cur存放的下一个结点的下标 */
 }
 return i;       /* 返回分配的结点的下标 */
}


/* 将下标为k的空闲结点回收到备用链表
返回值类型 void
函数名 FreeSSL
参数列表 StaticLinkList space */

void FreeSSL(StaticLinkList space, int k) {
 space[k].cur = space[0].cur;  /* 把第一个元素的cur赋值给要删除的分量的cur */
 space[0].cur = k;     /* 把要删除的分量下标赋值给第一个元素的cur */
}

/*判断是否为空,就是判断首尾数组是否还原
返回值类型 Status
函数名 ListEmpty
参数列表 StaticLinkList space
*/

Status ListEmpty(StaticLinkList space) {
 if (space[0].cur != 1 || space[MAXSIZE - 1].cur != 0)
  return FALSE;
 return TRUE;
}

/* 初始条件:静态链表L已存在。操作结果:返回L中数据元素个数
* 数组的第一个元素的cur用来存放备用链表第一个结点的下标
* 数组的最后一个元素的cur则存放第一个有数值的元素的下标,相当于单链表中的头结点
返回值类型 int
函数名 ListLength
参数列表 StaticLinkList L */

int ListLength(StaticLinkList L)
{
 int j = 0;
 int i = L[MAXSIZE - 1].cur;
 while (i)
 {
  i = L[i].cur;
  j++;
 }
 return j;
}


/* 在静态链表L中第i个元素之前插入新的数据元素e
返回值类型 Status
函数名 ListInsert
参数列表 StaticLinkList L,int i,ElemType e */

Status ListInsert(StaticLinkList L, int i, ElemType e) {
 int l, j, k;
 k = MAXSIZE - 1;    /* k为静态链表中末结点的下标,这里为999 */
 if (i<1 || i>ListLength(L) + 1)
 {
  return ERROR;
 }
 j = MallocSSL(L);    /* 获得空闲分量的下标 */
 if (j) /* 分配成功 */
 {
  L[j].data = e;    /* 将数据赋值给此分量的data */
  for (l = 1; l <= i - 1; l++)  /* 找到第i个元素之前的位置 */
  {
   k = L[k].cur;
  }
  L[j].cur = L[k].cur;  /* 将第i个元素之前的cur赋值给新元素的cur */
  L[k].cur = j;    /* 将新元素的下标赋值给第i个元素之前元素的cur */
  return OK;
 }
 return ERROR;
}

/* 删除静态链表L中的第i个数据元素e
返回值类型 Status
函数名 ListDelete
参数列表 StaticLinkList L, int i */

Status ListDelete(StaticLinkList L, int i) {
 int j, k;
 k = MAXSIZE - 1;    /* k为静态链表中末结点的下标,这里为999 */
 if (i<1 || i>ListLength(L) + 1)
 {
  return ERROR;
 }
 for (j = 0; j <= i - 1; j++)
 {
  k = L[k].cur;
 }
 j = L[k].cur;
 L[k].cur = L[j].cur;
 FreeSSL(L, j);
 return OK;
}



Status ListTraverse(StaticLinkList L)
{
 int j = 0;
 int i = L[MAXSIZE - 1].cur;
 while (i)
 {
  visit(L[i].data);
  i = L[i].cur;
  j++;
 }
 return j;
 printf("\n");
 return OK;
}

Status visit(ElemType c)
{
 printf("%d ", c);
 return OK;
}


int main()
{
 StaticLinkList L;
 Status i;
 i = InitList(L);
 printf("初始化L后:L.length=%d", ListLength(L));

 i = ListInsert(L, 1'F');
 i = ListInsert(L, 1'E');
 i = ListInsert(L, 1'D');
 i = ListInsert(L, 1'B');
 i = ListInsert(L, 1'A');

 printf("\n在L的表头依次插入FEDBA后:\nL.data=");
 ListTraverse(L);

 i = ListInsert(L, 3'C');
 printf("\n在L的“B”与“D”之间插入“C”后:\nL.data=");
 ListTraverse(L);

 i = ListDelete(L, 1);
 printf("\n在L的删除“A”后:\nL.data=");
 ListTraverse(L);

 printf("\n");

 return 0;
}


相关文章

【数据结构】C语言排序方法——快速排序详解!

2021-09-23
其他的数据依次后移.这样将8小的数据移动到8的前面,比8大的数据在8后面保持不变.移动完成后如下:接下来比较的基准变为数字...

静态链表(C语言数据结构)

2021-09-23
静态链表线性存储结构的一种,兼顾顺序表和链表的优点,是顺序表和链表的升级;静态链表的数据全部存储在数组中(顺序表),但...

数据结构之栈(C语言实现)

2021-09-23
什么是栈 栈其实就是一种线性表.只不过它有点特殊,它的特殊性主要体现在它是一种后进先出(Last In First Out)的线性表...栈的基本操作 栈的基本操作只有两个: 入栈(push):即将数据保存在栈顶.进行该操作前,先修改栈顶指针,使其向上移动一个元素位置...两种栈 一般地,栈使用两种存储表示方法. 顺序栈:使用一组连续的内存单元依次保存栈中的数据.一般情况下使用数组作为顺序栈...

C 语言数据结构的封装方法

2021-09-23
本文介绍C语言中如何封装数据结构,让调用者可以引用这个数据结构,但无法获知这个数据结构的内部构成,也无法读写这个数据结...

C语言数据结构之队列

2021-09-23
顺序队列,采用顺序存储,当长度确定时使用. 顺序队列又有两种情况: ①使用数组存储队列的称为静态顺序队列...链式队列,采用链式存储,长度不确定时使用(由链表实现). 由于链式队列跟链表差不多,所以在这里只针对循环(环形)队列来说明并实践...队列的操作 入队(尾部入队) ①将值存入rear所代表的位置. ②rear = (rear+1)%数组的长度...

低价好课:经典数据结构合集(C语言版)(七日成蝶)_CC++开发培训课程百度云高清完整

2021-09-23
经典数据结构合集(C语言版)(七日成蝶)_CC++开发培训课程高清完整百度云网课资源 认准QQ:1679184397 有能...

低价好课:经典数据结构合集(C语言版)(七日成蝶)_CC++开发培训课程百度云高清完整

2021-09-23
经典数据结构合集(C语言版)(七日成蝶)_CC++开发培训课程高清完整百度云网课资源 生活如酒,或芳香,或浓烈它变得醇厚...

严蔚敏《数据结构》(C语言版)精讲班【教材精讲+考研真题串讲】

2021-09-23
官 网 地 址:http://fangcai.100xuexi.com/本文观看地址:http://fangcai.100xuexi.com/Ebook/998852.html内容简介长按上方二维码识别...

C语言 | 什么叫做数据结构

2021-09-23

数据结构与算法(C语言) | 图的基本定义及存储结构

2021-09-23
–线性表中,相邻的数据元素之间具有线性关系,树结构中,相邻两层的结点具有层次关系,而图结构中,任意两个顶点之间都可能有...

随机推荐

教资面试必备干货丨面试试讲真题(小学)

2021-05-13
初识FrontPage2.内容:依次单击开始➝所有程序➝Microsoft Office FrontPage 2003➝运行FrontPage后,其界面如下图所示:3.基本...

Trump, Saudi Arabia warn Iran against Middle East conflict

2021-05-03
Javad Zarif at Diaoyutai State Guesthouse in Beijing, China, May 17, 2019. /Reuters Photo"We are not pursuing war but we are also not...

外卖卷免费领 ,天天领红包~ 外卖卷免费领

2021-04-25
领到后避免过期,要速速使用呦~ 美团外卖老客: 早晨红包:满20减3 可用时间:06:00-09:00这也会吸引一大批顾客来购买将要过期...

8款替代Dreamweaver的开源网页开发工具

2021-04-13
如果你正在寻找Dreamweaver的替代品,下面这8款软件你应该优先尝试一下.注意,没有先后顺序,并不是第一位就是最好的.1....

DCEP的小思考

2021-04-12
DCEP相关理论我也说不少了,如果连基本的学习认识都懒得去做,就想不劳而获跟风炒作的话,我只能劝那些把它当成投机品的同学...

《PHP与MySql高性能应用开发》分享赠书活动

2020-04-01
图书介绍本次活动的图书是:《PHP与MySql高性能应用开发》内容简介本书内容主要围绕PHP应用的性能、可扩展、可伸缩性、可靠...

10 Android Studio开发实战:仿微信的发现功能

2019-05-07
Android中的二维码扫描可用谷歌的zxing工具包结合zxing的开源框架完成扫码与识别操作.扫一扫的效果如图所示,此时手机在进行图...

北大青鸟幼儿园2020年春季招生开始啦!

2018-09-26
北大青鸟幼儿园——招生啦! 北大青鸟幼儿园在北京具有三所校址,分别是天通苑西二校区、天通苑北一校区、北苑奥运村校区,其...

py圈炫富骗了4亿,我差点也上当!

2017-06-16
我猜,你们的朋友圈一定都有一个这样的人.你可能不知道他是干嘛的,但是每天看他发的朋友圈,几乎都是吃着奢华大餐,开着豪车...

Java中的 Switch 是如何支持 String 的?为什么不支持 long?

2017-03-22
Java Switch 支持byte、short、int 类型,在 JDK 1.5 时,支持了枚... case MALE: return 2; default: return 3; } } } 将这几个类反编译...