单链表的建立,测长,打印,删除,插入,排序,逆置

2024-03-07 19:32
文章标签 排序 删除 插入 建立 单链 打印 逆置 测长

本文主要是介绍单链表的建立,测长,打印,删除,插入,排序,逆置，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、编程实现一个单链表的建立/测长/打印。

       答案：

#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、编程实现单链表删除节点。

 解析：如果删除的是头节点，如下图：

QQ截图20111106194807

 

     则把head指针指向头节点的下一个节点。同时free p1，如下图所示：

QQ截图20111106194959

 

    如果删除的是中间节点，如下图所示：

QQ截图20111106195116

则用p2的next指向p1的next同时，free p1 ，如下图所示：

QQ截图20111106195254

 

//单链表删除节点
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、编写程序实现单链表的插入。

      解析：单链表的插入，如下图所示：

QQ截图20111106201812

 

     如果插入在头结点以前，则p0的next指向p1，头节点指向p0，如下图所示：

QQ截图20111106202019

 

   

 如果插入中间节点，如下图所示：

QQ截图20111106202158

 

    则先让p2的next指向p0，再让p0指向p1，如下图所示：

QQ截图20111106202318

 

    如果插入尾节点，如下图所示：

QQ截图20111106202516

则先让p1的next指向p0，再让p0指向空，如下图所示：

QQ截图20111106202635

 

//单链表插入节点
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、编程实现单链表的排序。

     答案：

[cpp] view plain copy print ?
  1. //单链表排序   
  2. node *sort(node *head)  
  3. {  
  4.     node *p,*p2,*p3;  
  5.     int n;  
  6.     int temp;  
  7.     n=length(head);  
  8.     if(head==NULL ||head->next==NULL)//如果只有一个或者没有节点  
  9.         return head;  
  10.     p=head;  
  11.     for(int j=1;j<n;++j)  
  12.     {  
  13.         p=head;  
  14.         for(int i=0;i<n-j;++i)  
  15.         {  
  16.             if(p->data > p->next->data) //每趟排序都把最大的数放到最后  
  17.             {  
  18.                 temp=p->data;  
  19.                 p->data=p->next->data;  
  20.                 p->next->data=temp;  
  21.             }  
  22.             p=p->next;  
  23.         }  
  24.     }  
  25.     return (head);  
  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，如下图所示：

QQ截图20111106213740

 

    再由p1指向p2，p2指向p3，如下图所示：

QQ截图20111106213748

 

    让后重复p2的next指向p1，p1指向p2，p2指向p3。

QQ截图20111106213759

[cpp] view plain copy print ?
  1. //单链表逆置   
  2. node *reverse(node *head)  
  3. {  
  4.     node *p1,*p2,*p3;  
  5.     if(head==NULL || head->next==NULL)  
  6.         return head;  
  7.     p1=head;  
  8.     p2=p1->next;  
  9.     while(p2)  
  10.     {  
  11.         p3=p2->next;  
  12.         p2->next=p1;  
  13.         p1=p2;  
  14.         p2=p3;  
  15.     }  
  16.     head->next=NULL;  
  17.     head=p1;  
  18.     return head;  
  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;
}

这篇关于单链表的建立,测长,打印,删除,插入,排序,逆置的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/784580。

相关文章

C#实现添加/替换/提取或删除Excel中的图片

C#实现添加/替换/提取或删除Excel中的图片

《C#实现添加/替换/提取或删除Excel中的图片》在Excel中插入与数据相关的图片,能将关键数据或信息以更直观的方式呈现出来,使文档更加美观,下面我们来看看如何在C#中实现添加/替换/提取或删除E... 在Excandroidel中插入与数据相关的图片，能将关键数据或信息以更直观的方式呈现出来，使文档更
阅读更多...
大数据小内存排序问题如何巧妙解决

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法：数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高；分治法高效但实现复杂；位图法可读性差,但存储空间受限... 目录三种方法：方法概要数据库排序（http://www.chinasem.cn对数据库设备要求较高）分治法（常
阅读更多...
Python脚本实现自动删除C盘临时文件夹

Python脚本实现自动删除C盘临时文件夹

《Python脚本实现自动删除C盘临时文件夹》在日常使用电脑的过程中,临时文件夹往往会积累大量的无用数据,占用宝贵的磁盘空间,下面我们就来看看Python如何通过脚本实现自动删除C盘临时文件夹吧... 目录一、准备工作二、python脚本编写三、脚本解析四、运行脚本五、案例演示六、注意事项七、总结在日常使用
阅读更多...
Git中恢复已删除分支的几种方法

Git中恢复已删除分支的几种方法

《Git中恢复已删除分支的几种方法》：本文主要介绍在Git中恢复已删除分支的几种方法,包括查找提交记录、恢复分支、推送恢复的分支等步骤,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录1. 恢复本地删除的分支场景方法2. 恢复远程删除的分支场景方法3. 恢复未推送的本地删除分支场景方法4. 恢复
阅读更多...
使用Python实现在Word中添加或删除超链接

使用Python实现在Word中添加或删除超链接

《使用Python实现在Word中添加或删除超链接》在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能,本文将为大家介绍一下Python如何实现在Word中添加或... 在Word文档中，超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能。通过添加超
阅读更多...
Oracle数据库使用 listagg去重删除重复数据的方法汇总

Oracle数据库使用 listagg去重删除重复数据的方法汇总

《Oracle数据库使用listagg去重删除重复数据的方法汇总》文章介绍了在Oracle数据库中使用LISTAGG和XMLAGG函数进行字符串聚合并去重的方法,包括去重聚合、使用XML解析和CLO... 目录案例表第一种：使用wm_concat() + distinct去重聚合第二种：使用listagg，
阅读更多...
Python中lambda排序的六种方法

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序
阅读更多...
Redis过期键删除策略解读

Redis过期键删除策略解读

《Redis过期键删除策略解读》Redis通过惰性删除策略和定期删除策略来管理过期键,惰性删除策略在键被访问时检查是否过期并删除,节省CPU开销但可能导致过期键滞留,定期删除策略定期扫描并删除过期键,... 目录1.Redis使用两种不同的策略来删除过期键，分别是惰性删除策略和定期删除策略1.1惰性删除策略
阅读更多...
SpringBoot项目删除Bean或者不加载Bean的问题解决

SpringBoot项目删除Bean或者不加载Bean的问题解决

《SpringBoot项目删除Bean或者不加载Bean的问题解决》文章介绍了在SpringBoot项目中如何使用@ComponentScan注解和自定义过滤器实现不加载某些Bean的方法,本文通过实... 使用@ComponentScan注解中的@ComponentScan.Filter标记不加载。@C
阅读更多...
MySQL中删除重复数据SQL的三种写法

MySQL中删除重复数据SQL的三种写法

《MySQL中删除重复数据SQL的三种写法》：本文主要介绍MySQL中删除重复数据SQL的三种写法,文中通过代码示例讲解的非常详细,对大家的学习或工作有一定的帮助,需要的朋友可以参考下... 目录方法一：使用 left join + 子查询删除重复数据(推荐)方法二：创建临时表(需分多步执行，逻辑清晰，但会
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2