博客文章

顺序存储——线性表设计和实现

作者: andy.      时间: 2016-07-25 00:43:35

今天讲讲线性表存储结构的设计和实现。 

线性表,只讲一点儿简单的东西~

为了到达一点点儿的通用,整个线性表只对用户创建的数据进行相应的管理。比如:创建、插入、删除等等。同样为了通用,我们使用void指针存储用户的数据。

这样子,我们就可以写出相应函数的申明了。如下:

#ifndef _MY_SQUENCE_LIST_
#define _MY_SQUENCE_LIST_

typedef void MySquence;
typedef void SquenceNode;

MySquence * CreateSquence(int);
void DisposeSquence(MySquence **);
void ClearSquence(MySquence *);
int GetLength(MySquence *);
int GetCapacity(MySquence *);
int InsertNewNode(MySquence *, SquenceNode *);
int InsertNewNodeByPosition(MySquence *, SquenceNode *, int);
SquenceNode* GetNodeByPosition(MySquence *, int);
SquenceNode* DeleteNodeByPosition(MySquence *, int);

#endif // !_MY_SQUENCE_LIST_

因为函数申明相对比较简单,这儿就不一一解释了。

先看线性表的结构定义:

typedef struct __sequence_list {
	int capacity;
	int length;
	void **node;
}MySequenceList;

Capacity为总长度,length为先用数据个数,node当然是存用户传进来的数据的地址的,为啥是二级指针?给出两个缘由,1、node是一个数据,里面存的是用户数据的地址,指向指针的指针,二级指针。2、在读取返回、插值的时候可以直接按照数组的方式读取。当然这里可以用int一级指针,类似于一维整型数组。整型和指针都只占四个字节,步长一样。

看函数实现,一个一个的解释。

创建,分配一个线性表结构+存用户数据指针的内存大小。比较简单,代码如下:

MySquence * CreateSquence(int count) {
	if (count <= 0)
		return NULL;
	MySequenceList* list = malloc(sizeof(MySequenceList) + sizeof(void *)*count);
	if (list == NULL)
		return NULL;
	list->capacity = count;
	list->length = 0;
	list->node = (void **)(list + 1);
	return list;
}

释放,判断指向的内存空间时候为空,不为空就释放,再将指针置为空,防止野指针。代码如下:

void DisposeSquence(MySquence **squence) {
	if (*squence == NULL)
		return;
	free(*squence);
	*squence = NULL;
	return;
}

清空比较简单,基本错误判断后。将长度置为0就行了~。看代码:

void ClearSquence(MySquence *squence) {
	MySequenceList* list = NULL;
	if (squence == NULL)
		return;
	list = (MySequenceList*)squence;
	list->length = 0;
}

获取长度和数据个数不解释了。代码:

int GetLength(MySquence *squence) {
	MySequenceList* list = NULL;
	if (squence == NULL)
		return -1;
	list = (MySequenceList*)squence;
	return list->length;
}
int GetCapacity(MySquence *squence) {
	MySequenceList* list = NULL;
	if (squence == NULL)
		return -1;
	list = (MySequenceList*)squence;
	return list->capacity;
}

插入有两个函数,分开讲。第一个比较简单,简单的错误判断过后,在表的尾部插入就行了。代码:

int InsertNewNode(MySquence *squence, SquenceNode *node) {
	MySequenceList* list = NULL;
	unsigned int * temp = NULL;
	if (squence == NULL || node == NULL)
		return -1;
	list = (MySequenceList*)squence;
	if (list->length >= list->capacity)
		return -2;

	list = (MySequenceList*)squence;
	list->node[list->length] = node;
	list->length++;
	return 1;
}

第二个根据用户指定的位置插入,想将从插入位置开始到尾部的元素向后移动一个位置,再将要插入的节点复制为指定位置完成。代码:

int InsertNewNodeByPosition(MySquence *squence, SquenceNode *node, int position) {
	MySequenceList* list = NULL;
	unsigned int * temp = NULL;
	int i = -1;

	if (squence == NULL || node == NULL)
		return -1;
	list = (MySequenceList*)squence;
	if (list->length >= list->capacity)
		return -2;

	list = (MySequenceList*)squence;
	if (position >= list->length)
		return InsertNewNode(squence, node);

	for (i = list->length - 1; i >= position - 1; i--)
		list->node[i + 1] = list->node[i];

	list = (MySequenceList*)squence;
	list->node[++i] = node;
	list->length++;
	return 1;
}

根据位置返回节点,没讲的。删除指定位置的元素,和第二个插入反着的。也非常简单。代码:

SquenceNode* GetNodeByPosition(MySquence *squence, int position) {
	MySequenceList* list = NULL;
	unsigned int * temp = NULL;
	int i = -1;

	if (squence == NULL || position <= 0)
		return NULL;
	list = (MySequenceList*)squence;
	if (list->length == 0 || position > list->length)
		return NULL;
	return list->node[position - 1];
}
SquenceNode* DeleteNodeByPosition(MySquence *squence, int position) {
	MySequenceList* list = NULL;
	unsigned int * temp = NULL;
	int i = -1;

	if (squence == NULL)
		return NULL;
	list = (MySequenceList*)squence;
	if (position > list->length)
		return NULL;

	SquenceNode *node = list->node[position - 1];
	for (i = position - 1; i < list->length - 1; i++)
		list->node[i] = list->node[i + 1];
	list->length--;

	return node;
}

测试代码:

#include <stdio.h>
#include "sequence_list.h"

typedef struct _Person
{
	int xxoo;
	int age;
}Person;

void Print(MySquence *squence) {
	Person *person;
	for (int i = 0; i < GetLength(squence); i++)
	{
		person = (Person *)GetNodeByPosition(squence, i + 1);
		printf("%d ", person->xxoo);
	}
	printf("\n");
}

void main() {
	Person person1 = { 1,1 };
	Person person2 = { 2,2 };
	Person person3 = { 3,3 };
	Person person4 = { 4,4 };
	Person person5 = { 5,5 };
	Person person6 = { 6,6 };
	Person person7 = { 7,7 };

	MySquence *s = CreateSquence(10);
	InsertNewNode(s, &person1);
	InsertNewNode(s, &person2);
	InsertNewNode(s, &person3);
	InsertNewNode(s, &person4);
	InsertNewNode(s, &person5);
	InsertNewNode(s, &person6);
	//Print(s);
	InsertNewNodeByPosition(s, &person7, 5);
	Print(s);
	DeleteNodeByPosition(s, 2);
	Print(s);


	getchar();
}

测试结果如下:

1 2 3 4 7 5 6
1 3 4 7 5 6

因为代码不多(难道不是代码多给出下载吗?主要还是流量啊...),这里直接给出线性表和测试代码下载:

sequence_list.7z