作者: 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