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

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

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

算法

面试

数据结构

5星 · 超过95%的资源需积分: 16 201 浏览量更新于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页未读，继续阅读

彭蔚喆

2013-12-24

算法大全确实挺有帮助的可惜是C#的

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

以下是一个较为完整的数据结构与算法的学习框架： ### 数据结构 1. 线性结构 - 数组 - 链表 - 栈 - 队列 2. 树形结构 - 二叉树 - 堆 - 并查集 - 哈夫曼树 - Trie 树 3. 图 - 邻接矩阵 - 邻接表 - 图的遍历算法 - 最短路径算法 - 最小生成树算法 4. 其它数据结构

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

### 回答1：算法6-1：二叉链表存储的二叉树的结构定义二叉链表存储的二叉树是一种常见的二叉树存储方式，其结构定义如下： typedef struct BiTNode{ TElemType data; // 数据域 struct BiTNode *lchild, *rchild; // 左右孩子指针 }BiTNode, *BiTree; 其中，TElemType为二叉树

#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;}

这段代码有一个小错误，就是while循环后面多余了一个分号。在while循环的后面应该是一个大括号，表示循环体的开始，而不是分号。将分号改为大括号即可，修改后的代码如下： ``` #include <stdio.h> #include <string.h> void help(void){ printf("****************************\n"); pr

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

好的，以下是对您的问题的回答： a. 动态分配内存的方法有很多，可以使用C语言的malloc函数，也可以使用C++中的new操作符，具体方法如下： C语言的malloc函数： ```c struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)); ``` C++中的new操作符： ```c++ Lis

用c语言递归的方法实现以下算法： 1．以二叉链表表示二叉树，建立一棵二叉树（算法5.3）； 2．输出二叉树的中序遍历结果（算法5.1）； 3．输出二叉树的前序遍历结果（见讲稿）； 4．输出二叉树的后序遍历结果（见讲稿）； 5．计算二叉树的深度（算法5.5）； 6．统计二叉树的结点个数（算法5.6）； 7．统计二叉树的叶结点个数； 8．统计二叉树的度为1的结点个数；

好的，以下是您所提出的问题的回答： 1. 二叉树的建立算法，使用C语言递归实现： ```c typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; void CreateBiTree(BiTree *T) { char c; scanf("

粉丝: 13
资源: 18

上传资源快速赚钱

我的内容管理收起

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

我的收益

登录查看自己的收益

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

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

我的收藏

我的下载

下载帮助

会员权益专享

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

评论3

会员权益专享

最新资源

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

评论3

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

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

数据结构与算法面试题

课设报告-“贪吃蛇_C语言_链表实现”-CSDN~.docx

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

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

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

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

数据结构实验报告6-树-二叉树的遍历算法-实验内容及要求.docx

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

数据结构与算法八股文

7-1 数据结构实验之链表一：顺序建立链表

实验三 树和二叉树的基本操作\n实验目的：明确了解二叉树的链表存储结构；熟练掌握二叉树的先序遍历算法；通过本次实习加深对高级语言c语言的使用，熟悉数组在c语言中的实现。\n实验要求：\n设计二叉链表类型\n利

数据结构综合课设二叉树的建立与遍历.docx

用递归的方法实现以下算法:\n1以二叉链表表示二叉树，建立一棵二叉树;\n2.输出二叉树的中序遍历结果;\n3.输出二叉树的前序遍历结果;\n4.输出二叉树的后序遍历结果;\n5.计算二叉树的深度;26.统计二

用递归的方法实现以下算法: 1.以二叉链表表示二叉树,建立一棵二叉树(算法5.3); 2.输出二叉树的中序遍历结果(算法5.1); 3.输出二叉树的前序遍历结果; 4.输出二叉树的后序遍历结果; 5.计算二叉树的深度

面试数据结构与常用算法

会员权益专享

最新资源

实验三树和二叉树的基本操作\n实验目的：明确了解二叉树的链表存储结构；熟练掌握二叉树的先序遍历算法；通过本次实习加深对高级语言c语言的使用，熟悉数组在c语言中的实现。\n实验要求：\n设计二叉链表类型\n利