链表数据结构C实现(带头结点)

将链表(ADT LinkList)的数据对象,数据关系及基本操作(函数)用C语言实现,并测试。

手机用户点击代码查看未显示内容

LinkList.h内容

 

函数具体实现

① 链表的初始化

② 链表的输出

③ 插入一个值到链表中

④ 删除链表中的一个值

⑤ 链表的逆置

注释:在此使用的插入法逆置时间效率O(n)

⑥ 两个非递减链表的归并函数

⑦ 链表的清除和销毁

清除:

销毁:

注释:注意链表的清除和销毁的区别,将在实验小结中展现。

MAIN函数

小结

1. 注意在定义链表的时候,是否要带头结点,本人的链表实现的是带头结点的优化链表,即在链表初始化的时候给链表增加一个头结点,而不是像书上多使用一个typedef语句,同时,头结点的L->data元素存的是链表的长度,由此省去了定义Link-length。
2. 非递减链表的归并函数Merge要注意函数内部有初始化和赋值新链表,每增加一个都要为p->next申请空间。
3. 在插入和删除函数中要对链表的length动态更改。
4. 链表的逆置函数时间复杂度为0(n),要注意为了使其它函数能够使用,链表的逆置不光简单地调换位置,要注意头结点指向第一个元素,尾元素的下一个位置为NULL。即要增加 p->next = r; L->next->next = NULL;L->next = p;语句。
注意当p->next==NULL时,L->next仍然指向先前链表的第一个元素,而新链表该元素变为最后一个,因此要加L->next->next==NULL。
5. 关于链表的清除与销毁的区别。链表的清除销毁其它节点保留头结点,销毁全部free掉。

 

原创非商业转载请注明出处,商业转载请联系。

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注