`

静态链表

 
阅读更多

其实静态链表不太好理解的是备用链表。

记住:

1、第一个元素不放数据,存放下一次要新加的元素在数组中的位置。

2、最后一个元素不放数据,存放第一个元素的索引。

这样,相当于静态链表中实际上有两个链表。

初始化的时候,一定要将数组的所有元素链接起来(当然第一个和最后元素除外),也就是初始化备用链表。


/*
 * StaticLinkList.h
 *
 *  Created on: 2013年7月16日
 *      Author: Administrator
 */

#ifndef STATICLINKLIST_H_
#define STATICLINKLIST_H_

#define ELEM_TYPE	int
#define MAX_SIZE	1000

typedef struct {
	ELEM_TYPE 	data;
	int			cur;
}StaticLinkList;

extern StaticLinkList ssl[];

void initStaticLinkList	(StaticLinkList *);
int	 malloc_ssl			(StaticLinkList *);
void free_ssl			(StaticLinkList *, int);
void insert				(StaticLinkList *, ELEM_TYPE);
void delete				(StaticLinkList *, int);
int locate				(StaticLinkList *, int , ELEM_TYPE *);

#endif /* STATICLINKLIST_H_ */

/*
 * StaticLinkList.c
 *
 *  Created on: 2013年7月16日
 *      Author: Administrator
 */
#include <stddef.h>
#include "StaticLinkList.h"

StaticLinkList ssl[MAX_SIZE];

void initStaticLinkList(StaticLinkList *pSSL) {
	int i = 0;

	if(pSSL == 0) {
		return;
	}

	for(i = 0; i < MAX_SIZE - 1; ++i) {
		pSSL[i].cur = i + 1;
	}
	pSSL[MAX_SIZE - 1].cur = 0;
}

int	 malloc_ssl(StaticLinkList * pSSL) {
	int k = pSSL[0].cur;

	if(k) {
		pSSL[0].cur = pSSL[k].cur;
	}
	else {
		return -1;
	}

	return k;
}

void free_ssl(StaticLinkList * pSSL, int cur) {
	pSSL[cur].cur 	= pSSL[0].cur;
	pSSL[0].cur 	= cur;
}

void insert(StaticLinkList *pSSL, ELEM_TYPE data) {
	int newCur = malloc_ssl(pSSL);

	if(!newCur) {
		return;
	}

	pSSL[newCur].data		= data;
	pSSL[newCur].cur		= pSSL[MAX_SIZE - 1].cur;
	pSSL[MAX_SIZE - 1].cur 	= newCur;
}

void delete(StaticLinkList *pSSL, int index) {
	int j = 0;
	int i = pSSL[MAX_SIZE - 1].cur;
	int previous = MAX_SIZE - 1;

	while(i && j < index) {
		previous = i;
		i = pSSL[i].cur;
		++j;
	}

	if(i && j == index) {
		pSSL[previous].cur = pSSL[i].cur;
		free_ssl(pSSL, i);
	}
}

int locate(StaticLinkList *pSSL, int index, ELEM_TYPE *pData) {
	int i = pSSL[MAX_SIZE - 1].cur;
	int j = 0;

	while(i && j < index) {
		i = pSSL[i].cur;
		++j;
	}

	if(i && j == index) {
		*pData = pSSL[i].data;
		return 1;
	}

	return 0;
}

/*
 * main.c
 *
 *  Created on: 2013年7月16日
 *      Author: Administrator
 */
#include <stdio.h>
#include "StaticLinkList.h"

void print(StaticLinkList * pSSL) {
	int cur = pSSL[MAX_SIZE - 1].cur;

	while(cur) {
		printf("%3d", pSSL[cur].data);
		cur = pSSL[cur].cur;
	}

	printf("\n");
}

int main(int argc, char **argv) {
	int i = 0;
	ELEM_TYPE data;

	initStaticLinkList(ssl);
	for(i = 0; i < 10; ++i) {
		insert(ssl, i);
	}
	print(ssl);
	delete(ssl, 0);
	delete(ssl, 1);
	delete(ssl, 4);
	print(ssl);

	if(locate(ssl, 0, &data)) {
		printf("%d ", data);
	}

	return 0;
}




分享到:
评论

相关推荐

    静态链表 C实现

    静态链表是一种在内存中预先分配好固定大小的存储空间,并通过指针链接节点的数据结构。在C语言中,静态链表的实现通常涉及到结构体、指针和数组的运用。下面将详细介绍静态链表的概念、优点、缺点以及如何用C语言...

    静态链表C语言实现

    静态链表是一种特殊形式的数据结构,通常在内存空间有限或者需要预分配所有元素的情况下使用。相较于动态链表,静态链表在内存管理上有所不同,因为它的节点是在编译时静态分配的。下面将详细讨论静态链表的实现及其...

    C语言数据结构 静态链表

    静态链表的实现和操作 静态链表是一种常用的数据结构,静态链表是指在程序设计中,链表的结点是预先分配的,且链表的长度固定不变。静态链表的优点是可以快速地插入、删除元素,并且可以避免动态分配内存带来的开销...

    静态链表的创建

    在C语言中,静态链表是一种特殊的链表实现方式,与传统的动态链表不同,它在编译时就分配了所有节点的内存空间。这种数据结构在某些情况下能提供更高效的内存管理和操作,尤其是在内存有限或者对内存分配有特殊要求...

    c语言实现静态链表

    c语言实现的静态链表

    静态链表的操作

    静态链表是一种特殊类型的数据结构,主要用于实现线性数据集合。与动态链表不同,静态链表的存储空间在编译时就已经固定,这使得它在某些场景下具有一定的优势。以下是对静态链表操作的详细说明: 1. 增加元素:在...

    数据结构笔记之线性表(-):静态链表表示与实现

    静态链表与传统的动态链表不同,动态链表中的节点在内存中是分散存储的,而静态链表的所有节点存储在预先分配的连续内存空间中。这种设计提供了更高效的内存管理,但同时也限制了表的大小,因为必须在编译时就确定表...

    静态链表的使用

    ### 静态链表的使用 #### 一、静态链表的概念与特点 静态链表是一种特殊的数据结构,它结合了链表和数组的特点。通常,在编程中链表是通过指针连接各个节点实现的,而静态链表则是利用数组来模拟链表的行为。在...

    静态链表和动态链表详细讲解教程

    静态链表和动态链表详细讲解教程 本资源讲解了链表的基本概念和实现方式,着重介绍了静态链表和动态链表的区别和应用场景。链表是一种常见的数据结构,它由多个节点组成,每个节点都包含一个数据域和一个指向下一个...

    静态链表基本操作

    静态链表是一种在内存中预先分配好固定数量节点的数据结构,与动态链表不同,它不依赖于堆内存的分配。这种数据结构在某些特定情况下,如资源受限或需要高效预分配的情况,可能会有优势。在本场景中,我们探讨的是...

    一、静态链表的定义 二、静态链表的设计 三、静态链表的操作 总结 附录 前言 你认识静态链表吗?听起来是不是很陌

    静态链表一、静态链表的定义 二、静态链表的设计 三、静态链表的操作 总结 附录 前言 你认识静态链表吗?听起来是不是很陌生呢?本文将较为详细的向你介绍它,感兴趣的话就一起来看看吧。 一、静态链表的定义 ...

    数据结构之静态链表的实现

    静态链表是一种特殊的链式存储结构,它与传统的动态链表不同,因为它在编译时就固定了存储空间,常用于内存有限或者需要预先分配所有元素的场合。在这个实现中,我们将探讨静态链表的基本操作,包括初始化、查找、...

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

    静态链表是一种特殊的链式数据结构,它与常规动态链表有所不同,主要在于存储方式和内存分配。 静态链表,顾名思义,与动态链表相对,其链表节点是在编译时静态分配的,而不是在运行时动态分配。这种设计减少了动态...

    静态链表的实现

    对于线性链表,也可用一维数组来进行描述。这种描述方法便于在没有指针类型的高级程序设计...用数组描述的链表,即称为静态链表。在C语言中,静态链表的表现形式即为结构体数组,结构体变量包括数据域data和游标CUR。

    静态链表的删除 静态

    本程序适合初学者学习和模仿的一个静态链表的删除的生成过程。。。。

    静态链表实现

    静态链表是一种特殊形式的数据结构,它在C和C++编程中被用于组织和操作数据。与传统的动态链表不同,静态链表的节点不是在运行时动态分配内存,而是在编译时就预设了存储空间。这种实现方式使得静态链表在某些情况下...

    静态链表C语言代码实现

    关于严蔚敏版数据结构的静态链表的代码实现,C语言实现

Global site tag (gtag.js) - Google Analytics