单链表

• 概念

​ 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

​ 链表中的数据是以结点来表示的，每个结点的构成：元素 + 指针，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表结构.png

• 头指针head

  ​ 单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。

• 终端结点

  终端结点无后继，故终端结点的指针域为空，即NULL。

• 头结点

  数据结构中，在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点。

  
  单链表.png

• 代码实现

  • 结构

    typedef struct node{ //结点类型定义
     int data; //结点的数据域
    struct node *next;//结点的指针域
    }ListNode;
    
    typedef ListNode *LinkList;
    

  • 初始化

    /*
      初始化
     */
    void LinkListInit(LinkList *L){
        //设置头结点
        *L = (ListNode*)malloc(sizeof(ListNode));
        //为空 则return
        if ((*L) == NULL)
        {   
            printf("初始化失败\n");
            return;
        }
        (*L)->next = NULL;
        (*L)->data = -1;
        printf("初始化成功\n");
    }
    

  • 插入

    /*
       单链表插入
     */
    void insertNode(LinkList *L, int place, int num){
        if (place == 0)
        {
            printf("插入位置从1开始\n");
            return;
        }
    
        //找到前驱
        ListNode *pre = *L;
        for (int i = 0; i < place - 1 & pre != NULL; I++)
        {
            pre = pre->next;
        }
        if (pre == NULL)
        {
            printf("插入失败，索引越界\n");
            return;
        }
        
        //创建结点
        ListNode* current = (ListNode *)malloc(sizeof(ListNode));
        if (current == NULL)
        {
            printf("创建失败\n");
            return;
        }
        //赋值
        current->next = NULL;
        current->data = num;
    
    
        current->next = pre->next;
        pre->next = current;
    
        printf("插入成功\n");
    }
    
    

  • 删除

    /*
       删除
     */
    void deleteNode(LinkList *L, int place){
         if (place == 0)
        {
            printf("删除位置从1开始\n");
            return;
        }
    
        //找到前驱
        ListNode *pre = *L;
        for (int i = 0; i < place - 1 & pre ->next!= NULL; I++)
        {
            pre = pre->next;
        }
        if (pre->next == NULL)
        {
            printf("删除失败，索引越界\n");
            return;
        }
    
        ListNode* current = pre->next;
        pre->next = current->next;
        current->next = NULL;
        free(current);
        printf("删除成功\n");
    
    }
    

  • 查询

    /*
       返回匹配value 的第一个结点
     */
    ListNode* LocateElem(LinkList L,int value) {
        int i = 1;
       LinkList p=L->next->next; /* p指向第一个结点 */ 
        while(p!=L->next) {
            I++;
            if(p->data == value) /* 满足关系 */
            return p;
            p=p->next;
        }
        return NULL;
    }
    

• 头插法与尾插法

  区别在首元结点前插入 还是 尾节点插入，得到的结果是反向的还是正向的。