时间戳

首页 > 技术文章 > C/C++中创建(带头结点、不带头结点的)单链表

C/C++中创建(带头结点、不带头结点的)单链表

komean 2019-04-13 10:18 原文

1、带头结点的单链表（推荐使用带头结点的单链表）（采用尾插法）

  • 了解单链表中节点的构成

    从上图可知，节点包含数据域和指针域，因此，在对节点进行定义时，我们可以如下简单形式地定义：
/* 定义链表 */
typedef struct Node{    
    int data;    // 数据域
    struct Node *next;    // 指针域(后节点)
    //  struct Node *next;    // 指针域(前节点)，这里暂时不考虑双链表表
}Node, *LinkedList;
  • 尾插法思想
    尾插法的思想其实很简单，通俗来讲就是每创建一个新节点都插到原来链表的后面。

    !
Node *Head, *L, *LNew;
/* 申请节点 */
Head = (Node *)malloc(sizeof(Node));
/* 带头结点 */
L = Head;
L->next = NULL;

 /* 初始赋值 */
for(int i = 0; i < 3; ++i){
     /* 申请节点 */
     LNew = (Node *)malloc(sizeof(Node));        
     LNew->data = i;
     L->next = LNew;
     LNew->next = NULL;
     L = LNew;
}
  • 简单的代码
#include <iostream>
using namespace std;

/* 定义链表 */
typedef struct Node{
    int data;
    struct Node *next;
}Node, *LinkedList;

/* 链表初始化 */
LinkedList LinkedListInit(){
    Node *Head, *L, *LNew;
    /* 申请节点 */
    Head = (Node *)malloc(sizeof(Node));
    /* 带头结点 */
    L = Head;
    L->next = NULL;

    /* 初始赋值 */
    for(int i = 0; i < 10; ++i){
        /* 申请节点 */
        LNew = (Node *)malloc(sizeof(Node));        
        LNew->data = i;
        L->next = LNew;
        LNew->next = NULL;
        L = LNew;
    }

    /* 返回头结点指针 */
    return Head;
}

int main()
{
    Node *p;
    p = LinkedListInit();
    p = p->next;
    while(p != NULL){
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;
    return 0;
}

2、不带头结点的单链表（原理与带头结点类似）

  • 不带头结点与带头结点的区别
    由于不带头结点的单链表第一个节点需要有效，因此，在处理第一个节点时，需要做节点迁移。


Node *Head, *L, *LNew;
/* 申请节点 */
Head = (Node *)malloc(sizeof(Node));
/* 不带头结点 */    
L = Head = NULL;  

 /* 初始赋值 */
for(int i = 0; i < 4; ++i){
     /* 申请节点 */
     LNew = (Node *)malloc(sizeof(Node));        
     LNew->data = i;
     LNew->next = NULL;
     if(L == NULL){
         L = Head = LNew;
     }else{            
         L->next = LNew;             
     }
     L = LNew;                   
}
  • 简单的代码
#include <iostream>
using namespace std;

/* 定义链表 */
typedef struct Node{
    int data;
    struct Node *next;
}Node, *LinkedList;

/* 链表初始化 */
LinkedList LinkedListInit(){
    Node *Head, *L, *LNew;
    /* 申请节点 */
    Head = (Node *)malloc(sizeof(Node));
    /* 不带头结点 */    
    L = Head = NULL;  

    /* 初始赋值 */
    for(int i = 0; i < 5; ++i){
        /* 申请节点 */
        LNew = (Node *)malloc(sizeof(Node));        
        LNew->data = i;
        LNew->next = NULL;
        if(L == NULL){
            L = Head = LNew;
        }else{            
            L->next = LNew;             
        }
        L = LNew;                   
    }
    
    /* 返回头结点指针 */
    return Head;
}

int main()
{
    Node *p;
    p = LinkedListInit();    
    while(p != NULL){
        cout << p->data << ' ';
        p = p->next;
    }
    cout << endl;
    return 0;
}

推荐阅读