加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
115-数据结构-链表.c 2.41 KB
一键复制 编辑 原始数据 按行查看 历史
zhangjing 提交于 2020-03-15 22:09 . [Modify]整理完一部分题目
====
5、将一个链表逆序
答:思路为先定义链表结构体,并假定输入的链表是已经初始化好的
typedef struct _LIST {
int data;
LIST_T *ps_next;
} LINKED_LIST_T
LINKED_LIST *linked_list_reverse(LINKED_LIST * ps_list) // 直接修改该链表中的指针
{
LINKED_LIST * ps_tmp1= NULL;
LINKED_LIST * ps_tmp2= NULL;
while (ps_list->ps_next != NULL) {
ps_tmp2 = ps_list->ps-next; // 将原来的下一个暂存
ps_list->ps-next = ps_tmp; // 赋值上一个
ps_tmp = ps_list; // 更新上一个
ps_list = ps_tmp2 ; // 继续计算下一个
}
ps_list->ps_next = ps_tmp;
return ps_list;
}
权重:中
备注:C语言中一般链表和循环缓存都是需要自己写的,没有现成的库函数可用。
链表可以用来做人机交互的菜单,这样方便增删条目,也可以用来做队列,便于数据缓存。
====
16 判断单向链表是否存在循环?
方法1:单链表判断是否存在循环,即判断是否有两个指针指向同一位置,即判断海量指针中是否有相同数据。然后对所有指针选择插入排序或者快速排序。
方法2:设置两个指针互相追逐。一个指针每次前进一步,第二个指针每次前进两步,如果有相遇,则说明有环。(如果一个单链表中有环,用一个指针去遍历,永远不会结束,所以可以用两个指针,一个指针一次走一步,另一个指针一次走两步,如果存在环,则这两个指针会在环内相遇,时间复杂度为O(n)
权重:较高
====
4、数组与链表的区别。
  数组中的数据在内存中的按顺序存储的,而链表是随机存储的!
要访问数组中的元素可以按下标索引来访问,速度比较快,如果对他进行插入操作的话, 就得移动很多元素,所以对数组进行插入操作效率很低!由于连表是随机存储的,
链表在插入,删除操作上有很高的效率(相对数组),如果要访问链表中的某个元素的话,
那就得从链表的头逐个遍历,直到找到所需要的元素为止,
所以链表的随机访问的效率就比数组要低
权重:中
====
5、试编写3个函数实现
a.建立一个双向链表
b.插入一个节点
c.删除一个节点
其实明白了链表的概率,知道怎么用结构体来表示,指针如何指,编程就简单些了。
权重:高
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化