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

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