链表的常见操作

 

　　链表是数据结构的重要内容，在计算机程序中应用广泛，同时也是各公司笔试题目的重点。

　　以下简单实现了链表的一些操作，包括创建、增加节点、删除节点、单链表逆置、合并有序链表等。

 

一、链表创建

　　链表主要有三种形式，包括单链表、双链表和循环链表。

　　单链表每个节点只包含一个后驱指针，双链表节点同时包含一个前驱指针和一个后驱指针，循环链表的尾节点的后驱指向头节点。

　　代码如下：

 

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*单链表节点结构*/
typedef struct NodeType
{
    char elem;
    NodeType *next;
}Node;


/*双链表节点结构*/
typedef struct DNodeType
{
    char elem;
    DNodeType *next;
    DNodeType *prev;
}DNode;

 

 

 

创建单链表

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*
创建链表
*/
Node * CreateList(Node *head)
{
    if(NULL == head)//分配头节点空间
        head=(Node*)malloc(sizeof(Node)),
        head->next=NULL;

    Node *current=head , *temp;
    char ch;

    while(1)
    {
        cout<<"\n input elem:";
        cin>>ch;
        if('#' == ch)            /*#结束输入*/
            break;
        temp=(Node *) malloc ( sizeof(Node) );
        temp->elem=ch;
        temp->next=NULL;
        current->next=temp;        /*当前节点的后驱指向新节点*/
        current=temp;            /*当前节点为链表尾节点*/

    }

    return head;
}

 

创建双链表

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*创建双链表*/
DNode * DoubleList(DNode *head)
{
    if(NULL == head)//分配头节点空间
        head=(DNode*)malloc(sizeof(DNode)) , head->prev=NULL , head->next=NULL;
        

    DNode *current=head , *temp;
    char ch;

    while(1)
    {
        cout<<"\n input elem:";
        cin>>ch;
        if('#' == ch)           /*#结束输入*/
            break;
        temp=(DNode *) malloc ( sizeof(DNode) );
        temp->elem=ch;
        temp->next=NULL;
        current->next=temp;        /*当前节点的后驱指向新节点*/
        temp->prev=current;        /*新节点的前驱指向当前节点*/
        current=temp;            /*当前节点为链表尾节点*/

    }

    return head;
}

 

创建循环链表

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*创建循环链表*/
Node* CycleList(Node *head)
{
    if(NULL == head)/*分配头节点空间*/
        head=(Node*)malloc(sizeof(Node)),head->next=NULL;

    Node *current=head , *temp;
    char ch;

    while(1)
    {
        cout<<"\n input elem:";
        cin>>ch;
        if('#' == ch)            /*#结束输入*/
            break;
        temp=(Node *) malloc ( sizeof(Node) );
        temp->elem=ch;
        temp->next=NULL;
        current->next=temp;        /*当前节点的后驱指向新节点*/
        current=temp;            /*当前节点为链表尾节点*/

    }
    current->next=head;            /*尾节点指向头节点*/
    return head;
}

 

二、链表操作

　　包括单链表的增加节点、删除节点、输出链表等

添加节点

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*插入节点*/

Node *InsertNode(Node *head , char elem)
{
    if( NULL == head || NULL == elem )
        return head;

    Node *current=head->next;    /*当前节点*/
    Node *prev=head;            /*前驱节点*/
    Node *temp;                    /*过渡节点*/
    
    while(current)                /*移动至尾节点*/
    {
        prev=current;
        current=current->next;    
    }

    temp=(Node*) malloc( sizeof(Node) );
    temp->elem=elem;
    temp->next=NULL;
    prev->next=temp;            /*尾节点的后驱指向新节点*/

    return head;

}

 

删除节点

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*删除节点*/
Node *DeleteNode(Node *head,char elem)
{
    if(NULL == head || NULL == elem)
        return head;
    if(NULL == head->next)
        return head;

    Node *prev,*current;
    prev=head;
    current=head->next;

    while(current)
    {
        if(current->elem == elem)        /*匹配节点元素*/
        {
            prev->next=current->next;    /*前驱节点的后驱指向当前节点的下一个节点*/
            free(current);                /*释放当前节点*/
            return head;
        }
        prev=current;
        current=current->next;            /*移动至下一个节点*/
    }

    return head;

}

 

输出链表

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*
输出链表
*/
void PrintList(Node *head)
{
    Node * current=head->next;
    cout<<"\n List are:";
    while(NULL != current)
    {
        if(NULL != current->elem)
            cout<<setw(5)<<current->elem;
        current=current->next;
    }

    cout<<"\n";
}

 

三、单链表逆置

　　单链表逆置在各公司的笔试题中比较常见，以下是其中一种实现。

　　算法描述：将链表中每一个节点插入到头结点之后。

　　

　　代码如下：

单链表逆置

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*单链表逆置*/
Node *ReverseList(Node *head)
{
    if(NULL == head)
        return head;
    if(NULL == head->next)
        return head;
    if(NULL == head->next->next)
        return head;

    Node *curr=head->next;  /*当前节点*/
    head->next=NULL;
    Node *temp;

    while(curr)
    {
        temp=curr->next;    /*暂存下一个节点*/
        /*把当前节点插入到head节点后*/
        curr->next=head->next;
        head->next=curr;

        curr=temp;            /*移动至下一个节点*/
    }

    return head;

}

 

四、求单链表中间节点

　　在笔试题中比较常见，通常题目描述是：给出一个单链表，不知道节点N的值，怎样只遍历一次就可以求出中间节点。

　　算法描述：设立两个指针p1,p2，p1每次移动1个节点位置，p2每次移动2个节点位置，当p2移动到尾节点时，p1指向中间节点。

　　

　　代码如下：

求中间节点

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*求中间节点*/
Node * MiddleNode(Node *head)
{
    if(NULL == head)
        return head;
    if(NULL == head->next)
        return head->next;

    Node *p1,*p2;
    p1=head;
    p2=head;

    while(p2->next)
    {
        /*p2节点移动2个节点位置*/
        p2=p2->next;
        if(p2->next)                    /*判断p2后驱节点是否存在，存在则再移动一次*/
            p2=p2->next;
        /*p1节点移动1个节点位置*/
        p1=p1->next;

    }
    return p1;

}

 

五、合并有序单链表

　　问题描述：合并2个有序单链表，合并后的链表也是排好序的。

　　算法描述：对链表A中的每一个节点元素，查找其在链表B中的插入位置，并在B中插入该元素。

　　代码如下：

合并有序单链表

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*合并有序单链表*/
Node * MergeList(Node * h1,Node * h2)
{
    if(NULL == h1 || NULL == h2)
        return h1;
    if(NULL == h1->next )
        return h2;
    if(NULL == h2->next)
        return h1;


    Node * curr1,*curr2,*prev1,*temp;
    prev1=h1;        /*链表1的前驱节点*/
    curr1=h1->next;    /*链表1的当前节点*/
    curr2=h2->next;    /*链表2的当前节点*/
    temp=h2;
    while(curr2)
    {
        while(curr1 && curr1->elem < curr2->elem)/*链表1指针移动至大或等于链表2当前元素的位置*/
            prev1=curr1,curr1=curr1->next;


        /*在链表1中插入链表2的当前元素*/
        temp=curr2->next;/*暂存链表2的下一个节点*/
        prev1->next=curr2;
        curr2->next=curr1;

        /*链表1移动至新节点*/
        curr1=curr2;
        /*链表2移动至下一个节点*/
        curr2=temp;
    }

    return h1;


}

 

六、判断链表是否有环

　　判断链表是否有环即是判断链表是否为循环链表，算法较为简单，一次遍历判断尾指针是否指向头指针即可。

　　代码如下：

 

判断链表是否有环

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->/*判断链表是否有环(循环链表)*/
bool IsCycleList(Node *head)
{
    if(NULL== head)
        return false;
    if(NULL == head->next)
        return false;
    Node *current=head->next;
    while(current)
    {
        if(head == current->next)
            return true;
        current=current->next;
    }
    return false;
}

 

 

七、总结

　　以上实现了链表的一些常见操作，源文件LinkList.cpp全部代码如下：　

LinkList.cpp

<!--

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->
/*
 * 作者：     达闻东
 * 修改日期： 2010-04-28 17:10
 * 描述：     实现链表的常见操作
 * 
 */
#include<iostream>
#include<iomanip>
using namespace std;

/*单链表节点结构*/
typedef struct NodeType
{
    char elem;
    NodeType *next;
}Node;


/*双链表节点结构*/
typedef struct DNodeType
{
    char elem;
    DNodeType *next;
    DNodeType *prev;
}DNode;


/*=============================================================================*/
/*
创建链表
*/
Node * CreateList(Node *head)
{
    if(NULL == head)//分配头节点空间
        head=(Node*)malloc(sizeof(Node)),
        head->next=NULL;

    Node *current=head , *temp;
    char ch;

    while(1)
    {
        cout<<"\n input elem:";
        cin>>ch;
        if('#' == ch)            /*#结束输入*/
            break;
        temp=(Node *) malloc ( sizeof(Node) );
        temp->elem=ch;
        temp->next=NULL;
        current->next=temp;        /*当前节点的后驱指向新节点*/
        current=temp;            /*当前节点为链表尾节点*/

    }

    return head;
}
/*=============================================================================*/
/*
输出链表
*/
void PrintList(Node *head)
{
    Node * current=head->next;
    cout<<"\n List are:";
    while(NULL != current)
    {
        if(NULL != current->elem)
            cout<<setw(5)<<current->elem;
        current=current->next;
    }

    cout<<"\n";
}


/*=============================================================================*/


/*插入节点*/

Node *InsertNode(Node *head , char elem)
{
    if( NULL == head || NULL == elem )
        return head;

    Node *current=head->next;    /*当前节点*/
    Node *prev=head;            /*前驱节点*/
    Node *temp;                    /*过渡节点*/
    
    while(current)                /*移动至尾节点*/
    {
        prev=current;
        current=current->next;    
    }

    temp=(Node*) malloc( sizeof(Node) );
    temp->elem=elem;
    temp->next=NULL;
    prev->next=temp;            /*尾节点的后驱指向新节点*/

    return head;

}


/*=============================================================================*/

/*删除节点*/
Node *DeleteNode(Node *head,char elem)
{
    if(NULL == head || NULL == elem)
        return head;
    if(NULL == head->next)
        return head;

    Node *prev,*current;
    prev=head;
    current=head->next;

    while(current)
    {
        if(current->elem == elem)        /*匹配节点元素*/
        {
            prev->next=current->next;    /*前驱节点的后驱指向当前节点的下一个节点*/
            free(current);                /*释放当前节点*/
            return head;
        }
        prev=current;
        current=current->next;            /*移动至下一个节点*/
    }

    return head;

}

/*=============================================================================*/


/*单链表逆置*/
Node *ReverseList(Node *head)
{
    if(NULL == head)
        return head;
    if(NULL ==<span 

  


  

    
    
分享到：
      
      
    
  

  

    

      单向链表操作详解（一）
      |
      VC快捷键
    
  
  

    

      
2011-03-10 17:00
      
浏览 1150
      
评论(0)
      
      
      
分类:编程语言
      
      
查看更多
    
    
  
    
  

  
  
  

相关推荐

链表基本操作

4. **算法效率**：链表的操作涉及到时间复杂度和空间复杂度的考虑，如查找操作的时间复杂度为O(n)，而插入和删除操作在链表头部的时间复杂度为O(1)，在中间或尾部则为O(n)。 综上所述，链表的基本操作涵盖了链表的...

数据结构：单向循环链表源码

**单向循环链表常见操作** 1. **创建链表**：初始化链表，通常创建一个节点作为链表的首节点。 2. **插入节点**：在链表的特定位置（如头部、尾部或指定节点后）插入新节点。 3. **删除节点**：根据节点值或位置删除...

静态链表的操作

在计算机科学中，数据结构是组织、存储和...而更常见的线性数据结构可能是数组或动态链表，它们在插入、删除和查找方面提供了更灵活的选择。了解并掌握各种数据结构的特性，对于设计高效算法和优化程序性能至关重要。

《代码随想录》链表算法详解及实现

此外，《代码随想录》系列文章进一步剖析了具体的LeetCode题目，包括链表常见操作（删除指定元素、设计自定义链表）、链表的反转方法、两两交换链表节点以及删除倒数第N个节点等问题，并提供了详细的解题思路和技术...

链表的操作 C#

链表是一种常见的线性数据结构，它是由一系列节点组成，每个节点包含两个部分：数据域和指针域。其中数据域用于存储实际的数据值，而指针域则存储指向下一个节点的地址。在单向链表中，每个节点只有一个指向其后继...

数据结构，顺序表和链表的操作

顺序表和链表的操作 在计算机科学中，数据结构是指计算机存储、组织和管理数据的一种方式。顺序表和链表是两种常见的数据结构，分别用于存储和管理顺序排列的数据和链式排列的数据。 顺序表 顺序表是一种线性表，...

C++链表基本操作(有源代码)

4. **链表反序**：链表反序是一个常见的操作，它将链表的顺序颠倒。这可以通过三个指针——前驱、当前和后继——来实现。遍历链表时，将当前节点的指针改为指向前驱，然后移动这三个指针。最后，将头节点设置为原...

C++链表基本操作.doc

以上就是C++中链表的基本操作，这些操作是ACM竞赛和算法设计中常见的基础工具，理解和掌握它们对于提升编程能力至关重要。通过灵活运用这些操作，我们可以解决更复杂的问题，如排序、搜索、合并链表等。

C#链表操作

本教程将深入探讨C#中的链表操作，包括其基本概念、常见操作以及如何在实际编程中应用。 链表不同于数组，它不连续存储元素，而是通过节点（Node）之间的引用关系来组织数据。每个节点包含两部分：数据部分和指向下...

操作单链表的函数 学习链表操作

根据给定的信息，本文将详细解释单链表的基本操作，包括创建新节点、添加节点到链表、打印链表中的所有节点以及清除整个链表。这些操作是使用C语言实现的，适用于学习数据结构和算法的基础阶段。 ### 操作单链表的...

利用C++中的类实现线性链表的常见操作

 带表头结点（存放的是该线性链表的长度），结点存放的是整型数值；  实现以下操作 ：  置空MakeEmpty（）  求长度Length（）  插入Insert（int x，... 编写一个函数，使用户通过选择进行相关链表操作。

链表操作链表的基本操作

链表的其他常见操作包括： 1. **求长度**：`lengthlist`函数用于计算链表的长度。它遍历链表直到找到尾部，计数器`j`记录了节点的数量。 2. **修改元素**：`modifylist`函数允许用户指定链表中某个位置的元素进行...

lianbiao.rar_链表基本操作_链表操作

在链表的头部、尾部或指定位置插入节点是常见的操作。在头部插入节点只需修改头节点，而在尾部插入需要遍历链表找到最后一个节点。例如，在链表头部插入节点的函数可以这样实现： ```c void insertAtHead...

数据结构中链表及常见操作.docx

链表的常见用途在于处理需要频繁添加、删除和遍历数据的情况，但较少涉及随机检索。例如，在实现动态数组、队列、栈等数据结构时，链表往往是一个很好的选择。 链表与数组的主要区别在于： 1. 存储方式：数组的元素...

算法__链表的操作

通过以上介绍，我们可以看到，链表的逆序和有序链表的合并都是链表操作中的常见任务，掌握这些操作对于理解和运用链表至关重要。无论是迭代还是递归方法，都体现了链表灵活多变的特点和强大的应用能力。

链表的各种操作富有源代码

最后，合并两个链表是一个常见的操作，常用于合并排序后的链表。这个过程通常需要创建一个新的链表，然后依次从两个输入链表中取出最小元素并添加到新链表中。 对称矩阵的判断则可能涉及到二维数组或链表的二维表示...

C语言-链表基本操作源码

本教程将深入探讨C语言中链表的基本操作。 一、链表的定义与结构 在C语言中，链表由一系列节点组成，每个节点包含两部分：数据域（用于存储数据）和指针域（指向下一个节点）。节点通常用结构体来定义，例如： ```...

C语言链表操作函数

在C语言中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和一个指向下一个节点的指针。链表可以动态地增长或缩短，非常适合实现多种数据管理任务。在本篇中，我们将详细探讨如何用C语言进行...

链表的基本操作及应用

链表是一种常用的数据结构，它在计算机科学中扮演着...链表的这些基本操作在实际编程中非常常见，特别是在需要动态调整数据存储空间或高效执行插入和删除操作的情况下。了解并掌握这些操作对于理解和使用链表至关重要。

数据结构中链表及常见操作.pdf

链表的常见用途包括需要频繁添加或删除元素的情况，因为这些操作在链表上执行非常高效。然而，如果频繁需要访问特定位置的元素，数组可能更为合适，因为数组提供了随机访问的能力。 链表与数组的主要区别： 1. ...

• C++STL轻松导学（2）

  2011-09-27 17:02 1320
  2.2.2 第二版：工业时代- ...

• C++ STL轻松导学

  2011-09-27 16:59 1177
  作为C++标准不可缺少的� ...

• Chapter 6 Exceptions(JAVA EXCEPTION IN NATIVE CODE)

  2011-09-26 09:53 1495
  Contents | Prev | Next | Index ...

• JNI编程中如何传递参数和返回值。

  2011-09-14 17:51 1792
  首先要强调的是，native方法不但可以传递Java的基本类型 ...

• Windows Mobile与Android应用开发对比

  2011-09-06 11:44 1291
  Windows Mobile在经历过最初的Wince系列，po ...

• android和JNI经典blog.doc

  2011-09-01 15:29 1750
  Android JNI调用 2011-02-24 1 ...

• 定义VC 消息映射函数小结

  2011-08-21 22:15 1318
  定义VC 消息映射函数小� ...

• 多线程中的事件对象

  2011-08-21 14:23 1442
  Using Event Objects 使用事件对象 Appl ...

• VC++多线程调用webservice实例

  2011-08-21 12:04 1587
  一、开始多线程 1.开始� ...

• 多线程同步机制（Vc++）

  2011-08-21 09:46 1740
  Synchronizing Execution of Mult ...

• 如何结束线程VC++

  2011-08-21 09:20 2796
  Terminating a Thread Terminati ...

• VS2005使用多字节字符集问题

  2011-08-03 13:27 2083
  1>------ 已启动生成: 项目: psgdatat ...

• matlab的作图函数(二维） 星号，点号 颜色

  2011-07-27 14:57 10028
  zz matlab的作图函数(二维 ...

• android 调用C++的so

  2011-07-08 18:36 4391
  第一步：开发环境的安� ...

• windows异常处理__try__except

  2011-07-07 14:24 1972
  try-except用法 　　 try except是win ...

• Java中的一个byte

  2011-06-30 14:34 1012
  Java中的一个byte，其范围是-128~127的，而Int ...

• NDK中char*如何转换成jstring

  2011-06-30 13:05 1874
  JNIEXPORT jstring JNICALLJava_T ...

• CFileDialog多选文件时的最大数量

  2011-06-25 20:29 2280
  system("explorer d:\我的 ...

• C++信号处理编程风格规范

  2011-06-24 10:07 2163
  1.背景：        C++做数字信号处理很普遍，如何 ...

• C++如何获取系统时间

  2011-06-22 11:31 655
  //方案— 优点：仅使用C标准库；缺点：只能精确到秒级 #in ...

Global site tag (gtag.js) - Google Analytics