没有合适的资源？快使用搜索试试~ 我知道了~

首页算法大全-面试题-链表-栈-二叉树-数据结构.docx

算法大全-面试题-链表-栈-二叉树-数据结构.docx

数据结构

5星 · 超过95%的资源需积分: 16 29 下载量 97 浏览量更新于2023-03-16 评论收藏 47KB DOCX 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

64页

算法大全-面试题-链表-栈-二叉树-数据结构.docx 一、单链表目录 1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。 7.单链表交换任意两个元素（不包括表头） 8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？ 9.判断两个单链表是否相交 10.两个单链表相交，计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素

资源详情

资源评论

资源推荐

一、单链表

1.单链表反转

2.找出单链表的倒数第 4 个元素

3.找出单链表的中间元素

4.删除无头单链表的一个节点

5.两个不交叉的有序链表的合并

6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序

把这个二级链表称一级单链表。

7.单链表交换任意两个元素（不包括表头）

8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？

9.判断两个单链表是否相交

10.两个单链表相交，计算相交点

11.用链表模拟大整数加法运算

12.单链表排序

13.删除单链表中重复的元素

首先写一个单链表的 C#实现，这是我们的基石：

public class Link

{

public Link Next;

public string Data;

public Link(Link next, string data)

{

this.Next = next;

this.Data = data;

}

其中，我们需要人为地在单链表前面加一个空节点，称其为 head。例如，一个

单链表是 1->2->5，如图所示：

对一个单链表的遍历如下所示：

static void Main(string[] args)

{

Link head = GenerateLink();

Link curr = head;

while (curr != null)

{

Console.WriteLine(curr.Data);

curr = curr.Next;

}

1.单链表反转

这道题目有两种算法，既然是要反转，那么肯定是要破坏原有的数据结构的：

算法 1：我们需要额外的两个变量来存储当前节点 curr 的下一个节点 next、再

下一个节点 nextnext：

public static Link ReverseLink1(Link head)

{

Link curr = head.Next;

Link next = null;

Link nextnext = null;

//if no elements or only one element exists

if (curr == null || curr.Next == null)

{

return head;

}

//if more than one element

while (curr.Next != null)

{

next = curr.Next; //1

nextnext = next.Next; //2

next.Next = head.Next; //3

head.Next = next; //4

curr.Next = nextnext; //5

}

return head;

}

算法的核心是 while 循环中的 5 句话

我们发现，curr 始终指向第 1 个元素。

此外，出于编程的严谨性，还要考虑 2 种极特殊的情况：没有元素的单链表，

以及只有一个元素的单链表，都是不需要反转的。

算法 2：自然是递归

如果题目简化为逆序输出这个单链表，那么递归是很简单的，在递归函数之后

输出当前元素，这样能确保输出第 N 个元素语句永远在第 N+1 个递归函数之后

执行，也就是说第 N 个元素永远在第 N+1 个元素之后输出，最终我们先输出最

后一个元素，然后是倒数第 2 个、倒数第 3 个，直到输出第 1 个：

public static void ReverseLink2(Link head)

{

if (head.Next != null)

{

ReverseLink2(head.Next);

Console.WriteLine(head.Next.Data);

}

但是，现实应用中往往不是要求我们逆序输出（不损坏原有的单链表），而是

把这个单链表逆序（破坏型）。这就要求我们在递归的时候，还要处理递归后

的逻辑。

首先，要把判断单链表有 0 或 1 个元素这部分逻辑独立出来，而不需要在递归

中每次都比较一次：

public static Link ReverseLink3(Link head)

{

//if no elements or only one element exists

if (head.Next == null || head.Next.Next == null)

return head;

head.Next = ReverseLink(head.Next);

return head;

}

我们观测到：

head.Next = ReverseLink(head.Next);

这句话的意思是为 ReverseLink 方法生成的逆序链表添加一个空表头。

接下来就是递归的核心算法 ReverseLink 了：

static Link ReverseLink(Link head)

{

if (head.Next == null)

return head;

Link rHead = ReverseLink(head.Next);

head.Next.Next = head;

head.Next = null;

return rHead;

}

算法的关键就在于递归后的两条语句：

head.Next.Next = head; //1

head.Next = null; //2

啥意思呢？画个图表示就是：

这样，就得到了一个逆序的单链表，我们只用到了 1 个额外的变量 rHead。

2.找出单链表的倒数第 4 个元素

这道题目有两种算法，但无论哪种算法，都要考虑单链表少于 4 个元素的情况：

第 1 种算法，建立两个指针，第一个先走 4 步，然后第 2 个指针也开始走，两

个指针步伐（前进速度）一致。

static Link GetLast4thOne(Link head)

{

Link first = head;

Link second = head;

for (int i = 0; i < 4; i++)

{

if (first.Next == null)

throw new Exception("Less than 4 elements");

first = first.Next;

}

while (first != null)

{

first = first.Next;

second = second.Next;

}

return second;

}

第 2 种算法，做一个数组 arr[4]，让我们遍历单链表，把第 0 个、第 4 个、第 8

剩余63页未读，继续阅读

wyj0305

2013-01-24

非常不错，解答的也很清楚，值得收藏

#include <stdio.h>#include <string.h>void help(void){ printf("****************************\n"); printf("help:帮助信息 \n"); printf("insert:插入链表节点 \n"); printf("print:遍历链表节点 \n"); printf("search:查询链表某个节点 \n"); printf("delet:删除链表某个节点 \n"); printf("free:释放整个链表 \n"); printf("quit:退出程序 \n"); printf("****************************\n");}int main(int argc,char const *argv[]){ help(); while(1); { char cmd[128] =""; printf("请输入操作命令:"); scanf("%s",cmd); if(strcmp(cmd,"help") == 0) { help(); } else if(strcmp(cmd,"insert") == 0) { printf("-------链表插入-------\n"); } else if(strcmp(cmd,"print") == 0) { printf("-------链表遍历-------\n"); } else if(strcmp(cmd,"search") == 0) { printf("-------链表查询-------\n"); } else if(strcmp(cmd,"delet") == 0) { printf("-------链表删除-------\n"); } else if(strcmp(cmd,"free") == 0) { printf("-------链表释放-------\n"); } else if(strcmp(cmd,"quit") == 0) { break; } } return 0;}

printf("*insert:插入链表节点 *\n"); printf("*print:遍历链表节点 *\n"); printf("*search:查询链表某个节点 *\n"); printf("*delet:删除链表某个节点 *\n"); printf("*free:释放整个链表 *\n"); printf("*...

粉丝: 13
资源: 18

上传资源快速赚钱

我的内容管理收起

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

会员权益专享

算法大全-面试题-链表-栈-二叉树-数据结构.docx

评论3

会员权益专享

最新资源

算法大全-面试题-链表-栈-二叉树-数据结构.docx

评论3

算法大全-面试题-链表-栈-二叉树-数据结构

算法大全-面试题-数据结构

C语言程序设计-职工信息管理系统(链表).docx

数据结构与算法：理解数组、链表与栈的应用

测试输入： 9 8 10 2 0 // 0是结束输入的信号 预期输出： 输入结点数据中... --------循环链表初始元素------ 9 8 10 2 --------删除第二个结点后------ 9 10 2

列出数据结构与算法的学习框架

算法2.1-算法2.12顺序表和链表模拟

python常用算法结构图

算法6-1~6-4：二叉链表存储的二叉树

使用二叉链表存储结构建立一棵二叉树，完成如下功能： 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数

用c语言实现二叉树的基本操作 内容：使用二叉链表存储结构建立一棵二叉树，完成如下功能： 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数

二叉树的基本操作 内容：使用二叉链表存储结构建立一棵二叉树，完成如下功能： 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数数据结构C语言版

C++数据结构与算法 面试题

数据结构与算法面试题

算法2-8~2-11：链表的基本操作

经典的数据结构和算法题有哪些？

数据结构与算法面试题java

java中数据结构】.数组、链表、栈、队列、树【二叉树、红黑树、B+树】？

1.构造一个链表L-|||-a.对链表动态分配内存-|||-b.初始化单链表-|||-c.创建单链表(头插法创建、尾插法创建)-|||-d.完成链表某一位的取值-|||-e.在链表的某一位进行插入操作-|||-f.对于链表中元素进行遍历,

会员权益专享

最新资源

测试输入： 9 8 10 2 0 // 0是结束输入的信号预期输出：输入结点数据中... --------循环链表初始元素------ 9 8 10 2 --------删除第二个结点后------ 9 10 2

用c语言实现二叉树的基本操作内容：使用二叉链表存储结构建立一棵二叉树，完成如下功能： 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数

二叉树的基本操作内容：使用二叉链表存储结构建立一棵二叉树，完成如下功能： 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数数据结构C语言版

C++数据结构与算法面试题