7.22数据结构

笔记

链表

一.链表的引入

1.1总结顺序表的优缺点

        1）优点：能够直接通过下表进行定位元素，访问效率高，对元素进行查找修改比较快

        2）不足：插入和删除元素需要移动大量的元素，效率较低

        3）缺点：存储数据元素有上限，当达到MAX后，就不能再添加元素了、

1.2链表的概念

        1）链式存储的线性表叫做链表

                1.链式存储：表示数据元素的存储地址不一定连续

                2.线性表：数据元素之间不存在一对一的关系

        2）链表的基础概念

                1.节点：节点是链表的基本单位，由数据域和指针域组成

                2.数据域：存放数据元素的部分

                3.指针域：存放下一个节点地址的部分

                4.前驱节点：当前节点的上一个节点

                5.后继节点：当前节点的下一个节点

                6.头节点：虚设的一个节点，数据域不存放数据元素，可以存放链表的长度

                7.头指针：指向第一个节点的指针称为头指针

                8.第一个节点：实际存储数据元素的链表上的第一个节点

                9.注意：头节点的指针域其实就是头指针，也可以单独定义一个指针，指向第一个节点

        3）链表的分类

                1.单向链表：只能从头节点或第一个节点出发，单向访问其后继结点的链表称为单向链表

                2.双向链表：从头部出发，既可以访问前驱节点，也可以访问后继结点

                3.循环链表：首尾相接的链表称为循环链表

二.单向链表

2.1节点结构体类型

        1）头节点和普通节点数据域可以合到一起，使用一格共用体表示

        2）指针域都是指向普通节点的地址

定义数据类型

        typedef int datatype

定义节点类型

        typedef struct Node

        {

                union

                {

                        int len;//头节点数据域

                        datatype data;//普通节点数据域

                }；

                struct Node *next；//指针域

        }；

2.2创建链表

        1）在堆区申请一格头节点的空间，就创建了一个链表

        2）需要对头结点的数据初始化链表长度，指针域初始化NIULL

三.双向链表

        1）所谓双向链表，就是从任意一个节点既能存储其前驱节点信息也能存储后继节点信息

        2）节点结构体中增加一个指向前驱节点的指针

        3）头节点没有前驱，最后一个节点没有后继

四.循环链表

        1）循环链表，就是首尾相接的链表

        2）单向循环链表：只需要将最后一个节点的指针域指向头节点即可

        3）双向循环链表：需要将最后一个阶段的指针域指向头节点，头节点的前驱指针指向最后一个阶段

作业

使用循环链表完成约瑟夫环问题

#include<myhead.h>
typedef int datatype;
typedef struct List
{
    union 
    {
        datatype data;
        int len;
    };
    struct List* next;
    
}List,*ListPtr;
ListPtr list_create_apply(datatype e)
{
    ListPtr temp1=(ListPtr)malloc(sizeof(List));

    if(temp1==NULL)
    {
        printf("创建失败！\n");
        return NULL;
    }
    temp1->next=NULL;
    temp1->data=e;

    return temp1;
}  
ListPtr  list_search_pos(ListPtr  L, int pos)
{
    //判断逻辑
    if(NULL==L || pos<0 || pos>L->len)
    {
        printf("查找失败\n");
        return NULL;
    }

    //查找逻辑
    ListPtr  q = L;
    for(int i=0; i<pos; i++)
    {
        q = q->next;
    }

    return q;
}
int list_insert_tail(ListPtr  L, datatype e)
{
    //判断逻辑
    if(NULL == L)
    {
        printf("插入失败\n");
        return -1;
    }
    
    //找到最后一个节点
    ListPtr  q = list_search_pos(L, L->len);
    
    //封装节点
    ListPtr p = list_create_apply(e);
    if(NULL == p)
    {
        return -1;
    }
    
    //插入逻辑
    p->next = q->next;
    q->next = p;
    
    //表的变化
    L->len++;
    printf("插入成功\n");
    return 0;

}
int main(int argc, char const *argv[])
{
    int num=0;
    int flag=0;
    ListPtr L=(ListPtr)malloc(sizeof(List));
    if(NULL==L)
    {
        printf("失败！\n");
        return 0;
    }
    L->next=L;
    L->len=0;
    printf("请输入约瑟夫环的人数：\n");
    scanf("%d",&num);
    printf("请输入要报数的数：\n");
    scanf("%d",&flag);
    for (int  i = 2; i <= num; i++)
    {
        list_insert_tail(L,i);
    }
    printf("%d",L->len);
    printf("出局的结果为：\n");
        L->data=1;
    while(L->next!=L)
    {

        for (int  i = 1; i < flag-1; i++)
        {
            L=L->next;
        }
        ListPtr temp=L->next;
        printf("%d\t",temp->data);
        L->next=temp->next;
        L=L->next;

    }
}