静态链表

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

记住：

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;
}