21.C语言 单链表

 链表中数据元素的构成

每个元素本身由两部分组成：

1. 本身的信息，称为“数据域”；
2. 指向直接后继的指针，称为“指针域”。

图2 结点的构成

这两部分信息组成数据元素的存储结构，称之为“结点”（node（结点））。n个结点通过指针域相互链接，组成一个链表。

图3 含有n个结点的链表
 

图 3 中，由于每个结点中只包含一个指针域，生成的链表又被称为 线性链表 或 单链表。

链表中存放的不是基本数据类型，需要用结构体实现自定义：

struct Node{
    int data;               //数据域
    struct Node* next;     //指针域
};

 什么是链表？

 链表是结构体变量与结构体变量连接在一起

动态创建一个链表：动态内存申请+模块化设计

1.创建链表（创建一个表头表示整个链表）

2.创建结点 

3.插入结点

4.删除结点

5.打印遍历链表（测试）

表头法插入

1.创建链表

struct Node* createlist()
{
   struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));
   //headNode变成了结构体变量
   //变量使用前必须被初始化 
   headNode->next = NULL;
   return headNode;  
} 

2.创建结点

struct Node* creatNode(int data)
{
  struct Node* newNode = (struct Node *)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->Node = NULL;
  return newNode;  
} 

3.插入结点

void insertNodeByHead(struct Node* headNode,int data)
{
    //1.创建插入的结点
    struct Node* newNode = creatNode(data);
    newNode->next= headNode->next;
    headNode->next = newNode;
}

4.删除结点

void deleteNodeByAppoin(struct Node* headNode,int posData)
{
    struct Node* posNode=headNode->next;
    struct Node* posNodeFront = headNode;
    if(posNode==NULL)
        printf("无法删除链表n");
    else
    {
        while(posNode->data != posData)
        {
            posNodeFront=posNode;
            posNode = posNodeFront;
            if(posNode==NULL)
            {
                printf("没有找到相关信息，无法删除n");
                return;
            }
        }
        posNodeFront->next = posNode->next;
        free(posNode);
    }
}

5.打印遍历链表（测试）

void printList(struct Node* headNode )
{
    struct Node* pMove = headNode->next;
    while(pMove)
    {
        printf("%i",pMove->data);
        pMove = pMove->next;
    }
    printf("n");
}

#include 
#include 
#include 
struct Node{
    int data;               //数据域
    struct Node* next;     //指针域
};
//创建链表
struct Node* createlist()
{
   struct Node* headNode = (struct Node*)malloc(sizeof(struct Node));
   //headNode变成了结构体变量
   //变量使用前必须被初始化
   headNode->next = NULL;
   return headNode;
}

//创建结点
struct Node* creatNode(int data)
{
  struct Node* newNode = (struct Node *)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = NULL;
  return newNode;
}

//
void printList(struct Node* headNode )
{
    struct Node* pMove = headNode->next;
    while(pMove)
    {
        printf("%it",pMove->data);
        pMove = pMove->next;
    }
    printf("n");
}
//插入结点，参数：插入那个链表，插入结点的数据是多少
void insertNodeByHead(struct Node* headNode,int data)
{
    //1.创建插入的结点
    struct Node* newNode = creatNode(data);
    newNode->next= headNode->next;
    headNode->next = newNode;

}
void deleteNodeByAppoin(struct Node* headNode,int posData)
{
    struct Node* posNode=headNode->next;
    struct Node* posNodeFront = headNode;
    if(posNode==NULL)
        printf("无法删除链表n");
    else
    {
        while(posNode->data != posData)
        {
            posNodeFront=posNode;
            posNode = posNodeFront;
            if(posNode==NULL)
            {
                printf("没有找到相关信息，无法删除n");
                return;
            }
        }
        posNodeFront->next = posNode->next;
        free(posNode);
    }
}

int main()
{
    struct Node* list = createlist();
    insertNodeByHead(list,1);
    insertNodeByHead(list,2);
    insertNodeByHead(list,3);
    printList(list);
    deleteNodeByAppoin(list,2);
    printList(list);
    system("pause");

    return 0;
}

---

链表的删除：指定位置删除

的内存空间供顺序表使用时，可能使用链表能解决问题。（链表每次申请的都是单个数据元素的存储空间，可以利用上一些内存碎片）

1. 链表中结点之间采用指针进行链接，当对链表中的数据元素实行插入或者删除操作时，只需要改变指针的指向，无需像顺序表那样移动插入或删除位置的后续元素，简单快捷。

链表和顺序表相比，不足之处在于，当做遍历操作时，由于链表中结点的物理位置不相邻，使得计算机查找起来相比较顺序表，速度要慢。