1、编程实现一个单链表的建立/测长/打印。
答案:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
using
namespace
std;
//单链表结构体
typedef
struct
student
{
int
data;
struct
student *next;
}node;
//建立单链表
node *create()
{
node *head,*p,*s;
int
x,cycle=1;
head=(node*)
malloc
(
sizeof
(node));
//建立头节点
p=head;
while
(cycle)
{
printf
(
"\nPlease input the data:"
);
scanf
(
"%d"
,&x);
if
(x!=0)
{
s=(node*)
malloc
(
sizeof
(node));
//每次新建一个节点
s->data=x;
printf
(
"\n%d"
,s->data);
p->next=s;
p=s;
}
else
{
cycle=0;
}
}
head=head->next;
p->next=NULL;
printf
(
"\n yyy %d"
,head->data);
return
(head);
}
//单链表测长
int
length(node *head)
{
int
n=0;
node *p;
p=head;
while
(p!=NULL)
{
p=p->next;
n++;
}
return
(n);
}
//单链表打印
void
print(node *head)
{
node *p;
int
n;
n=length(head);
printf
(
"\nNow,These %d records are :\n"
,n);
p=head;
if
(head!=NULL)
p=p->next;
while
(p!=NULL)
{
printf
(
"\n uuu %d "
,p->data);
p=p->next;
}
}
2、编程实现单链表删除节点。
解析:如果删除的是头节点,如下图:
则把head指针指向头节点的下一个节点。同时free p1,如下图所示:
如果删除的是中间节点,如下图所示:
则用p2的next指向p1的next同时,free p1 ,如下图所示:
答案:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//单链表删除节点
node *
remove
(node *head ,
int
num)
{
node *p1,*p2;
p1=head;
while
(num!=p1->data && p1->next!=NULL)
//查找data为num的节点
{
p2=p1;
p1=p1->next;
}
if
(num==p1->data)
//如果存在num节点,则删除
{
if
(p1==head)
{
head=p1->next;
free
(p1);
}
else
{
p2->next=p1->next;
}
}
else
{
printf
(
"\n%d could not been found"
,num);
}
return
(head);
}
3、编写程序实现单链表的插入。
解析:单链表的插入,如下图所示:
如果插入在头结点以前,则p0的next指向p1,头节点指向p0,如下图所示:
如果插入中间节点,如下图所示:
则先让p2的next指向p0,再让p0指向p1,如下图所示:
如果插入尾节点,如下图所示:
则先让p1的next指向p0,再让p0指向空,如下图所示:
答案:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//单链表插入节点
node *insert(node *head,
int
num)
{
node *p0,*p1,*p2;
p1=head;
p0=(node *)
malloc
(
sizeof
(node));
p0->data=num;
while
(p0->data > p1->data && p1->next!=NULL)
{
p2==p1;
p1=p1->next;
}
if
(p0->data<=p1->data)
{
if
(head==p1)
{
p0->next=p1;
head=p0;
}
else
{
p2->next=p0;
p0->next=p1;
}
}
else
{
p1->next=p0;
p0->next=NULL;
}
return
(head);
}
4、编程实现单链表的排序。
答案:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//单链表排序
node *sort(node *head)
{
node *p,*p2,*p3;
int
n;
int
temp;
n=length(head);
if
(head==NULL ||head->next==NULL)
//如果只有一个或者没有节点
return
head;
p=head;
for
(
int
j=1;j<n;++j)
{
p=head;
for
(
int
i=0;i<n-j;++i)
{
if
(p->data > p->next->data)
{
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
}
p=p->next;
}
}
return
(head);
}
5、编写实现单链表的逆置。
解析:单链表模型如下图所示:
进行单链表逆置,首先要让p2的next指向p1,如下图所示:
再由p1指向p2,p2指向p3,如下图所示:
让后重复p2的next指向p1,p1指向p2,p2指向p3。
答案:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//单链表逆置
node *reverse(node *head)
{
node *p1,*p2,*p3;
if
(head==NULL || head->next==NULL)
return
head;
p1=head;
p2=p1->next;
while
(p2)
{
p3=p2->next;
p2->next=p1;
p1=p2;
p2=p3;
}
head->next=NULL;
head=p1;
return
head;
}
6、编程实现删除单链表的头元素。
答案:
1
2
3
4
5
6
7
8
//删除单链表的头元素
void
RemoveHead(node *head)
{
node *p;
p=head;
head=head->next;
free
(p);
}
7、给出一个单链表,不知道节点N的值,怎么只遍历一次就可以求出中间节点,写出算法。
解析:设立两个指针,比如*p和*q。p每次移动两个位置,即p=p->next->next,q每次移动一个位置,即q=q->next。当p达到最后一个节点时,q就是中间节点了。
答案:
1
2
3
4
5
6
7
8
9
10
11
12
13
//给出一个单链表,不知道节点N的值,怎么只遍历一次就可以求出中间节点
void
searchmid(node *head,node *mid)
{
node *p,*q;
p=head;
q=head;
while
(p->next->next!=NULL)
{
p=p->next->next;
q=q->next;
mid=q;
}
}
8、给定一个单向链表,设计一个时间优化并且空间优化的算法,找出该链表的倒数第m个元素。实现您的算法,注意处理相关的出错情况。m定义为当m=0时,返回链表最后一个元素。
解析:这是一个难题,我们需要的是倒数第m个元素,所以如果我们从某个元素开始,遍历了m个元素之后刚好到达链表末尾,那么这个元素就是要找的元素。也许从链表的尾部倒推回去不是最好的办法,那么我们可以从链表头开始计数。
思路一:我们可以先一次遍历求出链表的总长度n,然后顺序变量求出第n-m个元素,那么这个就是我们要找的元素了。
思路二:我们用两个指针,一个当前位置指针p和一个指向第m个元素的指针q,需要确保两个指针之间相差m个元素,然后以同样的速度移动它们,如果当q到达链表末尾时,那么p指针就是指向倒数第m个元素了。
答案:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//思路一
node *searchLastElement1(node *head,
int
m)
{
if
(head==NULL)
return
NULL;
node *p=head;
int
count=0;
while
(p!=NULL)
{
p=p->next;
count++;
}
if
(count<m)
return
NULL;
p=head;
for
(
int
i=0;i<count-m;i++)
{
p=p->next;
}
return
p;
}
//思路二
node *searchLastElement2(node *head,
int
m)
{
if
(head==NULL)
return
NULL;
node *p,*q;
p=head;
for
(
int
i=0;i<m;i++)
{
if
(p->next!=NULL)
{
p=p->next;
}
else
{
return
NULL;
}
}
q=head;
while
(p->next!=NULL)
{
p=p->next;
q->next;
}
return
q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
#include<iostream> using namespace std;
//单链表结构体 typedef struct student
{ int data;
struct student *next;
}node; //建立单链表 node *create() { node *head,*p,*s;
int x,cycle=1;
head=(node*) malloc ( sizeof (node)); //建立头节点
p=head;
while (cycle)
{
printf ( "\nPlease input the data:" );
scanf ( "%d" ,&x);
if (x!=0)
{
s=(node*) malloc ( sizeof (node)); //每次新建一个节点
s->data=x;
printf ( "\n%d" ,s->data);
p->next=s;
p=s;
}
else
{
cycle=0;
}
}
head=head->next;
p->next=NULL;
printf ( "\n yyy %d" ,head->data);
return (head);
} //单链表测长 int length(node *head)
{ int n=0;
node *p;
p=head;
while (p!=NULL)
{
p=p->next;
n++;
}
return (n);
} //单链表打印 void print(node *head)
{ node *p;
int n;
n=length(head);
printf ( "\nNow,These %d records are :\n" ,n);
p=head;
if (head!=NULL)
p=p->next;
while (p!=NULL)
{
printf ( "\n uuu %d " ,p->data);
p=p->next;
}
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
//单链表删除节点 node * remove (node *head , int num)
{ node *p1,*p2;
p1=head;
while (num!=p1->data && p1->next!=NULL) //查找data为num的节点
{
p2=p1;
p1=p1->next;
}
if (num==p1->data) //如果存在num节点,则删除
{
if (p1==head)
{
head=p1->next;
free (p1);
}
else
{
p2->next=p1->next;
}
}
else
{
printf ( "\n%d could not been found" ,num);
}
return (head);
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
//单链表插入节点 node *insert(node *head, int num)
{ node *p0,*p1,*p2;
p1=head;
p0=(node *) malloc ( sizeof (node));
p0->data=num;
while (p0->data > p1->data && p1->next!=NULL)
{
p2==p1;
p1=p1->next;
}
if (p0->data<=p1->data)
{
if (head==p1)
{
p0->next=p1;
head=p0;
}
else
{
p2->next=p0;
p0->next=p1;
}
}
else
{
p1->next=p0;
p0->next=NULL;
}
return (head);
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
//单链表排序 node *sort(node *head) { node *p,*p2,*p3;
int n;
int temp;
n=length(head);
if (head==NULL ||head->next==NULL) //如果只有一个或者没有节点
return head;
p=head;
for ( int j=1;j<n;++j)
{
p=head;
for ( int i=0;i<n-j;++i)
{
if (p->data > p->next->data)
{
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
}
p=p->next;
}
}
return (head);
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
//单链表逆置 node *reverse(node *head) { node *p1,*p2,*p3;
if (head==NULL || head->next==NULL)
return head;
p1=head;
p2=p1->next;
while (p2)
{
p3=p2->next;
p2->next=p1;
p1=p2;
p2=p3;
}
head->next=NULL;
head=p1;
return head;
} |
1
2
3
4
5
6
7
8
|
//删除单链表的头元素 void RemoveHead(node *head)
{ node *p;
p=head;
head=head->next;
free (p);
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
|
//给出一个单链表,不知道节点N的值,怎么只遍历一次就可以求出中间节点 void searchmid(node *head,node *mid)
{ node *p,*q;
p=head;
q=head;
while (p->next->next!=NULL)
{
p=p->next->next;
q=q->next;
mid=q;
}
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
//思路一 node *searchLastElement1(node *head, int m)
{ if (head==NULL)
return NULL;
node *p=head;
int count=0;
while (p!=NULL)
{
p=p->next;
count++;
}
if (count<m)
return NULL;
p=head;
for ( int i=0;i<count-m;i++)
{
p=p->next;
}
return p;
} //思路二 node *searchLastElement2(node *head, int m)
{ if (head==NULL)
return NULL;
node *p,*q;
p=head;
for ( int i=0;i<m;i++)
{
if (p->next!=NULL)
{
p=p->next;
}
else
{
return NULL;
}
}
q=head;
while (p->next!=NULL)
{
p=p->next;
q->next;
}
return q;
} |
发表评论
-
析构函数为虚函数的原因
2012-09-09 11:42 830我们知道,用C++开发的时候,用来做基类的类的析构函数 ... -
hash的应用
2012-08-31 23:02 959第一部分为一道百度面试题Top K算法的详解;第二部分为关 ... -
微软智力题
2012-08-29 19:59 565第一组1.烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有 ... -
C++不能被继承的类
2012-08-27 20:16 1055一个类不能被继承, ... -
括号对齐问题
2012-08-27 10:47 1406解法一:左右括号成一对则抵消 可以 ... -
树的遍历
2012-08-19 10:43 717/****************************** ... -
堆排序
2012-08-16 14:24 882堆:(二叉)堆数据结构是一种数组对象。它可以被视为一棵完全 ... -
多态赋值
2012-08-14 16:16 828#include <iostream> usi ... -
static变量与static函数(转)
2012-08-13 10:15 743一、 static 变量 static变量大致分为三种用法 ... -
不用sizeof判断16位32位
2012-08-10 15:21 1700用C++写个程序,如何判断一个操作系统是16位还是3 ... -
找出连续最长的数字串(百度面试)
2012-08-09 15:15 1144int maxContinuNum(const char*in ... -
顺序栈和链栈
2012-08-06 10:01 796顺序栈:话不多说直接上代码 #include ... -
队列的数组实现和链表实现
2012-08-05 16:20 1023话不多少,数组实现上代码: #include<i ... -
KMP算法详解
2012-08-02 21:40 880KMP算法: 是在一个“主文本字符串” ... -
字符串的最长连续重复子串
2012-08-01 15:05 9768两种方法: 循环两次寻找最长的子串: <方法一> ... -
寻找一个字符串连续出现最多的子串的方法(转)
2012-07-31 21:19 974算法描述首先获得后缀数组,然后1.第一行第一个字符a,与第二行 ... -
字符串的循环移位
2012-07-31 16:52 974假设字符串:abcdefg 左循环两位:cdefgab 右 ... -
一次谷歌面试趣事(转)
2012-07-31 15:26 763很多年前我进入硅谷 ... -
约瑟夫环问题(循环链表)
2012-07-30 21:31 1286题目描述:n只猴子要选大王,选举方法如下:所有猴子按 1, ... -
多重继承内存地址问题
2012-07-30 15:55 725[cpp] view plaincopy ...
相关推荐
在面试中,对单链表的基本操作是衡量开发者对数据结构理解和编程能力的重要指标。以下是关于单链表建立、查找、插入、删除及特殊操作——检查环、找中间元素和反转的详细知识点。 1. **建立单链表**: 建立单链表...
这里我们深入探讨一下"面试单链表问题总结-反转,逆序输出,判环,求交点"这四个核心知识点。 首先,**单链表反转**是一个常见的面试题。单链表的基本结构由节点组成,每个节点包含数据和指向下一个节点的指针。...
### 单链表基本操作-面试必备 #### 知识点概述 单链表是数据结构中的一个重要概念,尤其在编程面试中极为常见。本文将详细介绍单链表的基本操作及其在C语言中的实现方法,包括创建、遍历、释放、计数、查找以及...
本篇将详细探讨单链表相关的13道面试题,涵盖其基本操作、查找、反转等重要知识点。 1. **单链表反转**:单链表反转是一项常见的算法题目,主要考察对链表节点操作的理解。通过改变节点间的指向关系,将原链表的...
单链表的各种操作,适合于初学,也适合于复习 单链表操作介绍 1. 创建头节点 ...12. 面试中常见:单链表翻转 13. 已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序,要求用递归方法
文章目录求单链表中有效节点的个数查找单链表中倒数第k个节点【新浪面试题】单链表的反转【腾讯面试题】从尾到头打印单链表【百度面试题,要求方式1:反向遍历。方式2:Stack栈】 单链表的常见面试题有如下: 1.求...
面试中,特别是针对初级到中级的C++开发者,单链表的逆序操作是一个常见的问题,因为它考察了对数据结构的理解、指针操作以及算法设计的能力。本篇将深入探讨如何用C++实现单链表的倒序。 首先,让我们定义一个...
此外,掌握链表还有助于在面试中展示我们的编程能力和解决问题的能力。 最后,单链表和循环链表的实现及应用是数据结构中的重要内容,也是每一位计算机科学与技术专业学生必须掌握的基础知识。对于在校学生来说,这...
本文将对单链表的一些常见面试算法进行总结,并提供具体的C++实现代码。 #### 二、知识点概述 1. **创建单链表 (creat_list)** 2. **打印单链表 (print_list)** 3. **计算单链表长度 (list_length)** 4. **删除指定...
许多C语言基础面试题都涉及单链表的实现和构造,其目的就是考察面试者对C语言基础数据类型是否有足够的了解,对C语言指针是否掌握。链表的实现可以简单也可以很复杂,只是我们对待问题的态度不同,回想起了大学刚...
该文件包括单链表的所有操作的C++源代码。 比如: 单链表的创建;单链表的长度;单链表的打印;单链表的删除结点;单链表的插入;单链表的排序;单链表的逆置;求单链表的中结点。 希望对数据结构爱好者有帮助。
单链表是一种基础的数据结构,...而逆转链表是一个经典的算法问题,经常出现在面试和编程竞赛中,对提高解决问题的能力非常有帮助。在实际项目中,单链表也被广泛应用于各种场景,例如在实现队列、栈或者自定义容器时。
在计算机科学领域,数据结构是组织、管理和存储数据的有效方式之一,它使数据访问和修改更为高效。其中,链表是一种常见的线性数据结构,由一系列节点组成,每个节点包含数据元素和指向下一个节点的链接。单链表是非...
在单链表中,头部插入节点是常见的操作之一,尤其在面试和笔试中常被用来考察对数据结构的理解和编程能力。 首先,我们要了解头插入节点的基本思想。在单链表的头部插入一个新节点意味着新节点将成为链表的第一个...
实现了一个简单的java版本的单链表,链表反转和链表是否相交如果相交求相交节点。关于链表是否相交是一次阿里的面试的在线试题,挂的很彻底。然后就在网上找了几个实现思路自己用java做了一个简单的实现....
单链表作为最简单、最常见的数据结构之一,是每位程序员都应该掌握的基本技能。本文以“我的Java单链表练习”为主题,通过博主baby69yy2000在iteye上的博客分享,深入探讨了Java中实现单链表的相关知识。 首先,...
对于求职者而言,掌握单链表的相关算法不仅能够提高自己的编程能力,还能在面试中脱颖而出。本文将详细介绍几种常见的单链表逆置与排序算法,并提供Java代码示例。 #### 基础概念 在深入探讨具体算法之前,我们先来...
在本压缩包中,我们关注的是一个Python编程相关的面试题,源自著名的在线编程挑战平台LeetCode。题目编号为第369题,题目是“给单链表加一”。这是一道涉及数据结构和算法的问题,主要考察的是链表操作和数值计算。...
编程题目则涉及算法设计与实现,例如单链表的反转、数组中的公共元素查找以及逻辑推理题目,如确定最少老鼠数量以在一周内找出毒酒桶的问题。 ### 知识点三:百度面试题目分享 面试题目涵盖研发、QA、运维DBA等...
本文将深入探讨标题和描述中提到的两个关键概念:有无头结点的单链表的逆序以及插入排序,这些都是在面试中,尤其是像微软这样的顶级科技公司面试时常见的问题。 首先,我们来理解单链表的概念。单链表是一种线性...