博客文章

链式存储——线性表设计和实现

作者: andy.      时间: 2016-07-26 17:13:31

我懵逼了,我也不晓得最近两天怎么老是在写这些~不过写了就发出来吧。都是一些非常简单的东西。

链式存储,分为单链、循环、双向。本人偷懒,写就把这三个东西揉在一起写好了。

先把上一篇文章:顺序存储——线性表设计和实现 的代码拷贝过来,然后改改就行了。

如果要直接看代码,直接拉到文章最后就好了~

说说稍微有意思点儿的地方吧。第一个是插入的,每次添加到链表到链表尾部,有两种可能,1、开始本来就是空链表。2、开始不是空链表。要分开处理,是比较简单的,看代码吧:

int InsertNewNode(MyLink *Link, LinkNode *node) {
	MyLinkList* list = NULL;
	unsigned int * temp = NULL;
	if (Link == NULL || node == NULL)
		return -1;
	list = (MyLinkList*)Link;

	if (list->header == NULL) {
		list->header = node;
		list->tail = node;

		list->header->next = list->tail;
		list->header->pre = list->tail;

		list->tail->next = list->header;
		list->tail->pre = list->header;

		list->cursor = list->header;
	}
	else {
		node->next = list->header;
		list->header->pre = node;

		list->tail->next = node;
		node->pre = list->tail;

		list->tail = node;
	}
	list->length++;
	return 1;
}

第二种插入,在用户指定的位置插入。也要分情况,1、如果用户要插入第一个位置,比较简单,调用第一种插入方式,然后将头指针指向新传入的节点就行。2、第二种情况,找到要插入的位置。比如在位置5插入,位置5的元素是temp,那么

1、 插入节点node的next就要指向temp。

2、 node的pre就要指向temp的pre。

3、 原来temp的前驱结点的next指向node。

4、 temp的pre指向node就行了。

int InsertNewNodeByPosition(MyLink *Link, LinkNode *node, int position) {
	MyLinkList* list = NULL;
	LinkNode* temp = NULL;

	if (Link == NULL || node == NULL&&position > 0)
		return -1;
	list = (MyLinkList*)Link;
	if (position > list->length)
		return InsertNewNode(Link, node);

	if (position == 1)
	{
		InsertNewNode(Link, node);
		list->header = list->header->pre;
		return 1;
	}

	temp = list->header;
	while (--position)
		temp = temp->next;

	node->next = temp;
	node->pre = temp->pre;
	temp->pre->next = node;
	temp->pre = node;

	list->length++;
	return 1;
}

删除的话,第一种删除指定位置的节点。要判断删掉后链表是否还有节点。如果删除后还有其他节点的话,还要判断删除的是否是头节点、是否是尾节点、是否为游标指向的节点,因为这意味着要改变这三个指针的指向,所以要进行判断并做出处理。也是很简单的,只需要进行相应判断就行了。看代码:

LinkNode* DeleteNodeByPosition(MyLink *Link, int position) {
	MyLinkList* list = NULL;
	LinkNode* temp = NULL;

	if (Link == NULL)
		return NULL;
	list = (MyLinkList*)Link;
	if (position<1 || position > list->length)
		return NULL;

	if (list->length == 1)
	{
		temp = list->header;
		list->header = NULL;
		list->tail = NULL;
		list->cursor = NULL;
	}
	else {
		while (--position)
			temp = list->header;
		if (temp == list->header)
			list->header = list->header->next;
		if (temp == list->tail)
			list->tail = list->tail->pre;
		if (temp == list->cursor)
			list->cursor = list->cursor->next;

		temp->pre->next = temp->next;
		temp->next->pre = temp->pre;
	}
	list->length--;
	return temp;
}

还有删除指定节点,也比较简单,找到该节点的位置,再调用上面的那个删除函数就行了。非常简单。就不看代码了。

最后放出链表和测试代码吧:link_list.7z