从零开始的嵌入式系统开发学习Day9（数据结构）

目录

一、单链表

1.1 概念

 1.2 单链表的操作

1.2.1 定义结点结构体

1.2.2 创建一个空的单链表

1.2.3 头插法插入数据

1.2.4 遍历单链表

 1.2.5 尾插法插入数据

1.2.6 判断单链表是否为空

1.2.7 头删法删除数据（返回删除的数据）

1.2.8 按照数据修改数据

1.2.9 按照位置查找数据

1.2.10 按照数据查找位置

1.2.11 按照位置插入数据

1.2.12 直接插入排序

练习：实现单链表的反转

练习：单链表的整表删除

二、单向循环链表

2.1 概念

2.2 单向循环链表的操作

2.2.1 定义结点结构体

2.2.2 创建一个空的单向循环链表

2.2.3 插入数据

2.2.4 遍历循环单向链表

2.2.5 删除头结点

2.2.6 去头结点遍历循环链表

---

一、单链表

1.1 概念

        单链表：线性表的链式存储

                线性表：一对一的关系

                链式存储：不需要在内存中开辟一段连续的内存空间，所以每一个数据不再是一个基本数据，而是由两部分组成，数据域和指针域，数据域保存数据，指针域保存下一个结点的地址。

        单链表：就是单向链表，前者结点可以找到后者结点，但是后者无法找到前者。

 1.2 单链表的操作

1.2.1 定义结点结构体

#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
//定义数据类型
typedef int DataType;
//定义结点结构体
typedef struct linklist
{
    DataType data; //数据域
    struct linklist *st;    //指针域，为了能够操作后面结点
                            //所以指针的类型为当前结构体的类型
}linklist;


#endif

1.2.2 创建一个空的单链表

 

//创建一个空的单链表
linklist* LinkListCreate()
{
    //定义一个头结点，在堆区开辟空间
    linklist *head = (linklist *)malloc(sizeof(linklist));
    //初始化指针域标识为空
    head->next = NULL;
    return head;
}

1.2.3 头插法插入数据

//头插法插入数据
void LinkListInsert(linklist *head,DataType value)
{
    //开辟空间，分配一个新的结点
    linklist *tmp = (linklist *)malloc(sizeof(linklist));
    tmp->next = NULL;
    tmp->data = value;
    //将要插入的结点的指针域指向第一个结点
    //第一个结点的地址：head->next
    //新插入结点的指针域：tmp->next
    tmp->next = head->next;
    //头结点的指针域保存要插入的结点的地址
    //头结点的指针域：head->next
    //新插入结点的地址：tmp
    head->next = tmp;
    return;
}

1.2.4 遍历单链表

//遍历单链表
void LinkListPrint(linklist *head)
{
    //定义一个指针保存第一个结点的地址
    linklist *p = head;
    while (p->next != NULL)
    {
        //p指向下一个结点（p保存下一个结点的地址）
        p = p->next;
        //打印数据
        printf("%d ",p->data);   
    }
    putchar(10);
}

 1.2.5 尾插法插入数据

//尾插法插入数据
void LinkListInsertTail(linklist *head,DataType value)
{
    linklist *tmp = (linklist *)malloc(sizeof(linklist));
    tmp->next = NULL;
    tmp->data = value;
    //找到最后一个结点
    linklist *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    //将新插入的结点保存在最后一个结点的后面
    p->next = tmp;
    //将新插入的结点的指针域指向NULL
    tmp->next = NULL;
    return;
}

1.2.6 判断单链表是否为空

//判断单链表是否为空
int LinkListIsEmpty(linklist *head)
{
    return head->next == NULL ? 1 : 0;
}

1.2.7 头删法删除数据（返回删除的数据）

//头删法删除数据（返回删除的数据）
DataType LinkListDelete(linklist *head)
{
    if(LinkListIsEmpty(head))
    {
        printf("单链表为空，删除失败！\n");
        return (DataType)-1;
    }
    DataType value;
    value = head->next->data;
    linklist *tmp = head->next;
    head->next = head->next->next;
    free(tmp);
    tmp = NULL;
    return value;
}

1.2.8 按照数据修改数据

//按照数据修改数据
void LinkListUpdateByData(linklist *head,DataType OldValue,DataType NewValue)
{
    if(LinkListIsEmpty(head))
    {
        printf("单链表为空，修改失败！\n");
        return;
    }
    linklist *p = head;
    int flags = 0;
    while (p->next != NULL)
    {
        if(p->data == OldValue)
        {
            p->data = NewValue;
            flags = 1;
        }
        p = p->next;
    }
    if (flags == 0)
    {
        printf("修改失败，数据%d不存在",OldValue);
    }
    return;
}

1.2.9 按照位置查找数据

//按照位置查找数据
DataType LinkListSearchByPos(linklist *head,int pos)
{
    if(pos < 1)
    {
        printf("查找失败，位置错误！\n");
        return (DataType)-1;
    }
    else
    {
        linklist *p = head;
        int i;    
        for(i = 0;i < pos;i++)
        {
            if(p->next == NULL)
            {
                printf("位置有误！\n");
                return (DataType)-1;
            }
            p = p->next;
        }
        return p->data;
    }
}

1.2.10 按照数据查找位置

//按照数据查找位置
int LinkListSearchByData(linklist *head,DataType value)
{
    if(LinkListIsEmpty(head))
    {
        printf("查找失败，单链表为空！\n");
        return -1;
    }
    else
    {
        int i = 0;
        linklist *p =head;
        while (p->next != NULL)
        {
            if (p->data != value)
            {
                p = p->next;
                i++;
            }
            else
            {
                printf("查找成功，位置是第%d个",i);
                return 0;
            }
        }
        printf("查找失败，数据%d不存在",value);
        return 0;
    }   
}

1.2.11 按照位置插入数据

//按照位置插入数据
void LinkListInsertByPos(linklist *head,int pos,DataType vaule)
{
    if(pos < 1)
    {
        printf("插入失败，位置错误！\n");
        return;
    }
    linklist *tmp = (linklist *)malloc(sizeof(linklist));
    tmp->data = vaule;
    tmp->next = NULL;
    if(LinkListIsEmpty(head))
    {
        tmp->next = head->next;
        head->next = tmp;
    }
    else
    {
        linklist *p = head;
        int i;    
        for(i = 0;i < pos;i++)
        {
            if(p->next == NULL)
            {
                printf("位置有误！\n");
            }
            p = p->next;
        }
        tmp->next = p->next;
        p->next = tmp;
    }
}

1.2.12 直接插入排序

//直接插入排序
void LinkListInsertSort(linklist *head,DataType value)
{
    linklist *tmp = (linklist *)malloc(sizeof(linklist));
    tmp->data = value;
    tmp->next = NULL;
    linklist *p = head;
    while (p->next != NULL && p->next->data < tmp->data)
    {
        p = p->next;
    }
    tmp->next = p->next;
    p->next = tmp;
}

练习：实现单链表的反转

h1: 10->20->30->40->NULL

......

h2:40->30->20->10->NULL

//实现单链表的翻转
void LinkListReverse(linklist *head)
{
    if(LinkListIsEmpty(head))
    {
        printf("翻转失败，单链表为空！\n");
        return;
    }
    else
    {
        linklist *p = NULL,*q = NULL;
        p = head->next;
        head->next = NULL;
        while (p != NULL)
        {
            q = p;
            p = p->next;
            q->next = head->next;
            head->next = q;
        }
        
    }
}
//实现单链表的翻转2
void LinkListReverse2(linklist *head)
{
    if(LinkListIsEmpty(head))
    {
        printf("翻转失败，单链表为空！\n");
        return;
    }
    else
    {
        linklist *tmp = LinkListCreate();
        linklist *p = head;
        DataType value;
        while (p->next != NULL)
        {
            value = LinkListDelete(head);
            LinkListInsert(tmp,value);
        }
        head->next = tmp->next;
    }
}

练习：单链表的整表删除

//单链表的整表删除
void LinkListClean(linklist *head)
{
    linklist *p = NULL,*q = NULL;
    p = head->next;
    while (p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    head->next = NULL;
}

二、单向循环链表

2.1 概念

2.2 单向循环链表的操作

2.2.1 定义结点结构体

//定义结点结构体
typedef struct looplist
{
    DataType value;
    struct looplist *next;
}looplist;

2.2.2 创建一个空的单向循环链表

//创建一个空的单向循环链表
looplist* LoopListCreate()
{
    looplist *head = (looplist *)malloc(sizeof(looplist));
    head->next = head;
    return head;
}

2.2.3 插入数据

//插入数据
void LoopListInsert(looplist *head,DataType value)
{
    looplist *tmp = (looplist *)malloc(sizeof(looplist));
    tmp->data = value;
    tmp->next = NULL;
    tmp->next = head->next;
    head->next = tmp;
    return;
}

2.2.4 遍历循环单向链表

//遍历单向循环链表
void LoopListPrint(looplist *head)
{
    looplist *p = head;
    while (p->next != head)
    {
        p = p->next;
        printf("%d ",p->data);
    }
    putchar(10);
    return;
}

2.2.5 删除头结点

//删除头结点
looplist* LoopListDeleteHead(looplist *head)
{
    looplist *p = head;
    while (p->next != head)
    {
        p = p->next;
    }
    p->next = head->next;
    free(head);
    head = NULL;
    return p->next;
}

2.2.6 去头结点遍历循环链表

//去头结点遍历单向循环链表
void LoopListPrint2(looplist *head)
{
    looplist *p = head;
    while (p->next != head)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("%d ",p->data);
}