02_线性表的静态链表和实现

版权声明：本文为博主原创文章，未经博主允许不得转载

是时候重新系统的学习/复习一遍《数据结构》了！教材用的是清华出版社严蔚敏的《数据结构》，但众所周知，这本教材中给出的都是伪C代码，没法直接在PC上编译、运行。为了自己复习以及给那些刚开始学习数据结构的小白们一些参考，我花了点时间把书中的一些代码改为C语言程序，大神请绕过！！！当然我早就了解到了，很久之前已经有人做过该事情了，不过也许自己做一遍会更有意思。

在某些编程语言中，没有提供像C/C++中的指针类型，因此按照http://www.cnblogs.com/weixiaochao/p/6247015.html这种方式是没法实现的，不过可以通过数组来实现。该数组中的元素可以看做线性表的结点，而数组元素的下标则可以看做该元素（结点)的“位置”，因此只需要定义一个结构体来表示该数组的元素，而每个元素都包含了数据项和他的后继结点的位置，通过这种抽象后就可以达到模拟指针的功能，进而实现前面所讲的链式表示和存储功能。

用数组描述的链表叫做静态链表，也叫做游标实现法。

存储结构定义

#define MAXSIZE 1000    // 链表的最大长度
typedef int ElemType;

// ----------线性表的静态单链表存储结构----------
typedef struct LNode {
    ElemType data;
    int cur;
}component, SLickList[MAXSIZE];

线性表的初始化

初始化过程主要是将数组中的各元素链成一个备用链表，也就是内存池。该数组的第1个元素的cur成员用来保存备用链表的地址，最后一个元素的cur成员用来保存链表的第1个元素的地址，因此数组的最后一个元素的cur可以认为是头指针。

// ----------初始化----------
void InitSpace_SL(SLickList space) {
	// 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，0表示空指针
	for (int i = 0; i < MAXSIZE - 1; ++i) {
		space[i].cur = i + 1;
	}
	space[MAXSIZE - 1].cur = 0;
} // InitSpace_SL

模拟malloc()和free()函数

这里我们需要模拟malloc()函数和free()函数，因为在线性表的插入和删除操作中需要建立新的结点和释放结点。

// ----------分配结点----------
int Malloc_SL(SLickList space) {
	// 若备用链表非空，则返回分配的结点下标，否则返回0
	 int i = space[0].cur;							// 取得备用链表的位置
	if (space[0].cur) {								// 如果备用链表不为空，则把备用链表的第一个结点的直接后继结点设置为当前备用链表的第一个结点，而之前备用链表的第一个结点则分配出去使用
		space[0].cur = space[i].cur;
	}
	return i;										// 返回新分配的结点下标
} // Malloc_SL

// ----------释放结点----------
void Free_SL(SLickList space, int k) {
	// 将下标为k的空闲结点回收到备用链表
	space[k].cur = space[0].cur;					// 这行代码和下一行代码实质上是将下标为k的结点插入到备用链表的表头作为新的备用链表的表头，因此相当于回收该结点
	space[0].cur = k;
} // Free_SL

线性表的插入操作

// ----------插入操作----------
Status ListInsert(SLickList space, int i, ElemType e) {
	// 在space中第i个元素之前插入新的数据元素e
	int j, k, l;
	k = MAXSIZE - 1;								// 获取最后一个元素的下标
	if (i < 1 || i > ListLength(space) + 1) {		// i的值不合法
		return ERROR;
	}
	j = Malloc_SL(space);							// 获取备用链表中可用结点的下标
	if (j) {										// 如果备用链表中有未分配的结点
		space[j].data = e;								// 将要插入的数据值赋值给新分配结点的data
		for (l = 1; l <= i - 1; ++l) {					// 跳出该循环时，k的值为第i-1个结点的下标
			k = space[k].cur;
		}
		space[j].cur = space[k].cur;
		space[k].cur = j;
		return OK;
	}
	return ERROR;
} // ListInsert

线性表的删除操作

// ----------删除操作----------
Status ListDelete(SLickList space, int i) {
	// 删除在space中第i个数据元素
	int j, k;
	if (i < 1 || i > ListLength(space)) {
		return ERROR;
	}
	k = MAXSIZE - 1;
	for (j = 1; j <= i - 1; j++) {					// 找到第i-1个元素的位置，然后赋值给k
		k = space[k].cur;
	}
	j = space[k].cur;								// 由于此时k等于i-1，因此j为第i个元素的位置
	space[k].cur = space[j].cur;					// 让第i+1个元素成为第i-1个元素的直接后继
	Free_SL(space, j);
	return OK;
} // ListDelete

获取数据元素

// ----------获取数据元素----------
Status GetElem_SL(SLickList space, int i, ElemType *e) {
	int j, k;
	if (i < 1 || i > ListLength(space)) {
		return ERROR;
	}
	k = MAXSIZE - 1;
	for (j = 1; j <= i; j++) {					// 找到第i个元素的位置
		k = space[k].cur;
	}
	*e = space[k].data;
    return OK;
}

源代码

#include <stdio.h>

#define OK 1
#define ERROR 0
#define MAXSIZE 1000

typedef int ElemType;
typedef int Status;

// ----------线性表的静态单链表存储结构----------
typedef struct LNode {
    ElemType data;
    int cur;
}component, SLickList[MAXSIZE];

// ----------获取线性表的长度----------
int ListLength(SLickList space) {
	int j = 0;
	int i = space[MAXSIZE - 1].cur;					// 获取第一个元素的位置
	while(i) {
		i = space[i].cur;
		j++;
	}
	return j;
} // ListLength

// ----------初始化----------
void InitSpace_SL(SLickList space) {
	// 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，0表示空指针
	for (int i = 0; i < MAXSIZE - 1; ++i) {
		space[i].cur = i + 1;
	}
	space[MAXSIZE - 1].cur = 0;
} // InitSpace_SL

// ----------分配结点----------
int Malloc_SL(SLickList space) {
	// 若备用链表非空，则返回分配的结点下标，否则返回0
	 int i = space[0].cur;							// 取得备用链表的位置
	if (space[0].cur) {								// 如果备用链表不为空，则把备用链表的第一个结点的直接后继结点设置为当前备用链表的第一个结点，而之前备用链表的第一个结点则分配出去使用
		space[0].cur = space[i].cur;
	}
	return i;										// 返回新分配的结点下标
} // Malloc_SL

// ----------释放结点----------
void Free_SL(SLickList space, int k) {
	// 将下标为k的空闲结点回收到备用链表
	space[k].cur = space[0].cur;					// 这行代码和下一行代码实质上是将下标为k的结点插入到备用链表的表头作为新的备用链表的表头，因此相当于回收该结点
	space[0].cur = k;
} // Free_SL

// ----------插入操作----------
Status ListInsert(SLickList space, int i, ElemType e) {
	// 在space中第i个元素之前插入新的数据元素e
	int j, k, l;
	k = MAXSIZE - 1;								// 获取最后一个元素的下标
	if (i < 1 || i > ListLength(space) + 1) {		// i的值不合法
		return ERROR;
	}
	j = Malloc_SL(space);							// 获取备用链表中可用结点的下标
	if (j) {										// 如果备用链表中有未分配的结点
		space[j].data = e;								// 将要插入的数据值赋值给新分配结点的data
		for (l = 1; l <= i - 1; ++l) {					// 跳出该循环时，k的值为第i-1个结点的下标
			k = space[k].cur;
		}
		space[j].cur = space[k].cur;
		space[k].cur = j;
		return OK;
	}
	return ERROR;
} // ListInsert

// ----------删除操作----------
Status ListDelete(SLickList space, int i) {
	// 删除在space中第i个数据元素
	int j, k;
	if (i < 1 || i > ListLength(space)) {
		return ERROR;
	}
	k = MAXSIZE - 1;
	for (j = 1; j <= i - 1; j++) {					// 找到第i-1个元素的位置，然后赋值给k
		k = space[k].cur;
	}
	j = space[k].cur;								// 由于此时k等于i-1，因此j为第i个元素的位置
	space[k].cur = space[j].cur;					// 让第i+1个元素成为第i-1个元素的直接后继
	Free_SL(space, j);
	return OK;
} // ListDelete

// ----------获取数据元素----------
Status GetElem_SL(SLickList space, int i, ElemType *e) {
	int j, k;
	if (i < 1 || i > ListLength(space)) {
		return ERROR;
	}
	k = MAXSIZE - 1;
	for (j = 1; j <= i; j++) {					// 找到第i个元素的位置
		k = space[k].cur;
	}
	*e = space[k].data;
    return OK;
}

// ----------遍历静态链表----------
Status ListTraverse(SLickList space) {
    int j = 0;
    int i = space[MAXSIZE - 1].cur;
    while (i) {
        printf("%c 
", space[i].data);
        i = space[i].cur;
    }
    printf("
");
    return OK;
}

int main() {
	SLickList list;									// 建立静态链表数组list
	InitSpace_SL(list);								// 初始化

	// 在第1~4个位置依次插入'A'、'B'、'C'、'D'4个数据元素
	ListInsert(list, 1, 'A');
	ListInsert(list, 2, 'B');
	ListInsert(list, 3, 'C');
	ListInsert(list, 4, 'D');
	printf("插入ABCD4个元素后：
");
	ListTraverse(list);

	printf("删除第4个元素后：
");
	ListDelete(list, 4);
	ListTraverse(list);

	printf("删除第2个元素后：
");
	ListDelete(list, 2);
	ListTraverse(list);

	printf("在第2个位置插入一个元素后：
");
	ListInsert(list, 2, 'b');
	ListTraverse(list);

	int temp;
	GetElem_SL(list, 3, &temp);
	printf("第3个元素为：%c
", temp);

	return 0;
}

输出结果

插入ABCD4个元素后：
A 
B 
C 
D 

删除第4个元素后：
A 
B 
C 

删除第2个元素后：
A 
C 

在第2个位置插入一个元素后：
A 
b 
C 

第3个元素为：C