数据结构

前言

熟悉数据结构单链表代码

结点定义

typedef struct node
{
    DataType data;     //每个元素数据信息
    struct node *next; //存放后继元素的地址
} LNode, *LinkList;

创建空单链表

LinkList Creat_LinkList(void)
{
    /*创建空单链表,入口参数:无,返回值:单链表的头指针,0代表创建失败,非0代表创建成功 */
    LinkList H;
    H = (LinkList)malloc(sizeof(LNode)); //申请内存空间
    if (H)                               //确认创建头结点是否成功,成功则修改单链表头结点的指针域为NULL代表空表
        H->next = NULL;
    return H;
}

销毁单链表

void Destroy_LinkList(LinkList *H)
{ //将头指针作为参数进行销毁
/*销毁单链表,入口参数:单链表头指针的地址 */
    LinkList p, q;
    p = *H;
    while (p) //释放单链表的所有结点
    {
        q = p;
        p = p->next;
        free(q);
    }
    *H = NULL;
}

求表长

int Length_LinkList(LinkList H)
{
/*求单链表表长,入口参数:单链表头指针,出口参数:表长,-1表示单链表不存在 */
    LinkList p = H; //*p指向头结点
    int count = -1; //*H带头节点所以从-1开始
    while (p)       //*p所知的是第count+1个结点
    {
        p = p->next;
        count++;
    }
    return count;
}

查询操作-按序号查找

LinkList Locate_LinkList(LinkList H, int i)
{
/*i不正确或者链表不存在,则返回NULL,i==0返回头指针,否则返回第i个结点的指针 */
    LinkList p;
    int j;
    p = H;
    j = 0;
    while (p && j < i) //查找第i个结点
    {
        p = p->next;
        j++;
    }
    if (j != i || !p)
    {
        printf("参数i错误或者单链表不存在n");
        return NULL;
    } //第i个结点不存在
    return p;
}

查找操作——按值查找

LinkList Locate_LinkList_Value(LinkList H, DataType x)
{
/*在单链表中查找值为x的结点,入口参数:单链表指针,检索元素 */
/*出口参数:找到后返回其指针,否则返回:NULL */
    LinkList p = H->next;
    while (p && p->data != x)
    {
        p = p->next;
    }
    return p;
}

插入操作

int Insert_LinkList(LinkList H, int i, DataType x)
{
/*在单链表H的第i个为之前插入值为x的结点,入口参数:单链表,插入位置,插入元素,返回参数:0表示失败,1表示成功 */
    LinkList p, q;
   p = Locate_LinkList(H, i - 1); //找到第i-1个结点地址
    if (!p)
    {
        printf("i有误n");
        return 0;
    }
    q = (LinkList)malloc(sizeof(LNode));
    if (!q)
    {
        printf("申请空间失败n"); //申请空间失败,不能插入
        return 0;
    }
   q->data = x;
    q->next = p->next; //新节点插入在第i-1个结点后面
    p->next = q;
    return 1;
}

删除操作

int Delete_LinkList(LinkList H, int i)
{
/*删除单链表H上的第i个结点,入口参数:单链表,删除元素序号,返回参数:0失败,1成功 */
    LinkList p, q;
    if (H == NULL || H->next == NULL)
    {
        printf("链表不存在或者空表不能删除n");
        return 0;
    }
    p = Locate_LinkList(H, i - 1); //找到第i-1个结点
    if (p == NULL || p->next == NULL)
    {
        printf("参数i错误n"); //第i个参数不存在
        return 0;
    }
    q = p->next;       //q指向第i个结点
    p->next = q->next; //从链表中删除
   free(q);           //释放q
   return 1;
}

单链表的完整代码

/*
 *  单链表相关操作
 */
#include "stdio.h"
typedef char DataType;

//定义节点
typedef struct node
{
    DataType data;     //每个元素数据信息
    struct node *next; //存放后继元素的地址
} LNode, *LinkList;

//创建空单链表
LinkList Creat_LinkList(void)
{
    /*创建空单链表,入口参数:无,返回值:单链表的头指针,0代表创建失败,非0代表创建成功 */
    LinkList H;
    H = (LinkList)malloc(sizeof(LNode)); //申请内存空间
    if (H)                               //确认创建头结点是否成功,成功则修改单链表头结点的指针域为NULL代表空表
        H->next = NULL;
    return H;
}

//销毁单链表
void Destroy_LinkList(LinkList *H)
{ //将头指针作为参数进行销毁
    /*销毁单链表,入口参数:单链表头指针的地址 */
    LinkList p, q;
    p = *H;
    while (p) //释放单链表的所有结点
    {
       q = p;
       p = p->next;
       free(q);
    }
    *H = NULL;
}

//求表长
int Length_LinkList(LinkList H)
{
    /*求单链表表长,入口参数:单链表头指针,出口参数:表长,-1表示单链表不存在 */
    LinkList p = H; //*p指向头结点
    int count = -1; //*H带头节点所以从-1开始
   while (p)       //*p所知的是第count+1个结点
    {
        p = p->next;
        count++;
    }
    return count;
}

//查找操作——按序号查找
LinkList Locate_LinkList(LinkList H, int i)
{
    /*i不正确或者链表不存在,则返回NULL,i==0返回头指针,否则返回第i个结点的指针 */
    LinkList p;
    int j;
    p = H;
    j = 0;
    while (p && j < i) //查找第i个结点
    {
        p = p->next;
        j++;
    }
    if (j != i || !p)
    {
        printf("参数i错误或者单链表不存在n");
        return NULL;
    } //第i个结点不存在
    return p;
}

//查找操作——按值查找
LinkList Locate_LinkList_Value(LinkList H, DataType x)
{
    /*在单链表中查找值为x的结点,入口参数:单链表指针,检索元素 */
    /*出口参数:找到后返回其指针,否则返回:NULL */
    LinkList p = H->next;
    while (p && p->data != x)
    {
        p = p->next;
    }
    return p;
}

//插入操作
int Insert_LinkList(LinkList H, int i, DataType x)
{
    /*在单链表H的第i个为之前插入值为x的结点,入口参数:单链表,插入位置,插入元素,返回参数:0表示失败,1表示成功 */
    LinkList p, q;
    p = Locate_LinkList(H, i - 1); //找到第i-1个结点地址
    if (!p)
    {
        printf("i有误n");
        return 0;
    }
    q = (LinkList)malloc(sizeof(LNode));
    if (!q)
    {
        printf("申请空间失败n"); //申请空间失败,不能插入
        return 0;
    }
    q->data = x;
    q->next = p->next; //新节点插入在第i-1个结点后面
    p->next = q;
    return 1;
}

//删除操作
int Delete_LinkList(LinkList H, int i)
{
    /*删除单链表H上的第i个结点,入口参数:单链表,删除元素序号,返回参数:0失败,1成功 */
    LinkList p, q;
    if (H == NULL || H->next == NULL)
    {
        printf("链表不存在或者空表不能删除n");
        return 0;
    }
    p = Locate_LinkList(H, i - 1); //找到第i-1个结点
    if (p == NULL || p->next == NULL)
    {
        printf("参数i错误n"); //第i个参数不存在
        return 0;
    }    
    q = p->next;       //q指向第i个结点
    p->next = q->next; //从链表中删除
    free(q);           //释放q
    return 1;
}

//主函数
int main()
{
    LinkList H;
    int i = 1;
    char x = '0';
    H = Creat_LinkList(); //创建链表
    printf("请问需要插入几个元素:");
    scanf("%d", &i);
    getchar(); //接收回车字符,不可缺
    printf("请输入字符:");
    for (int j = 1; j <= i; j++)
    {
        scanf("%c", &x);          //不能写在函数里面,否则会出错
        getchar();                //接收回车字符,不可缺
        Insert_LinkList(H, j, x); //插入结点数据——如果不确定i的大小而用i++,最后表长会错误(表长大于i的实际值)
    }
    for (int j = 1; j <= i; j++)    //输出所有结点数据
    {
        printf("%ct", Locate_LinkList(H, j)->data);
    }

    printf("n请输入您想查询的结点位置:n"); //位置查找
    scanf("%d", &i);
    printf("结点元素为:%cn", Locate_LinkList(H, i)->data);
    getchar();                            //接受回车字符
    printf("请输入您想查询的结点的值:"); //值查找
    scanf("%c", &x);
    if (Locate_LinkList_Value(H, x))
    {    
        printf("查询成功n");
    }
    else
    {
        printf("查询失败n");
    }
    printf("表长为:%dn", Length_LinkList(H)); //求表长
    printf("请输入想要删除结点的位置:");
    scanf("%d", &i);
    int m = Delete_LinkList(H, i); //删除结点
    if (m == 1)
        printf("删除成功n");
    Destroy_LinkList(&H); //销毁链表
    return 0;
}

应用

这里的应用是用单链表解决约瑟夫问题

首先创建循环单链表

    //定义节点
typedef struct node
{
    DataType data;     //每个元素数据信息
    struct node *next; //存放后继元素的地址
} LNode, *LinkList;

//创建循环单链表
LinkList Creat_LinkList(int n)
{
    LinkList head;
    LinkList p;
    LinkList q;
    p = (LinkList)malloc(sizeof(LNode));
    p->data = 1;
    head = p;
    for(int i=2;i<=n;i++)
    {
        q = (LinkList)malloc(sizeof(LNode));
        q->data = i;
        p->next = q;
        p = q; //p永远指向最后一个节点
    }
    p->next = head;
    return head;
}

约瑟夫问题的单链表完整代码

    /*
    约瑟夫问题——单链表
*/
#include "stdio.h"
typedef int DataType;

//定义节点
typedef struct node
{
    DataType data;     //每个元素数据信息
    struct node *next; //存放后继元素的地址
} LNode, *LinkList;

//创建循环单链表
LinkList Creat_LinkList(int n)
{
    LinkList head;
    LinkList p;
    LinkList q;
    p = (LinkList)malloc(sizeof(LNode));
    p->data = 1;
    head = p;
    for (int i = 2; i <= n; i++)
    {
        q = (LinkList)malloc(sizeof(LNode));
        q->data = i;
        p->next = q;
        p = q; //p永远指向最后一个节点
    }
    p->next = head;
    return head;
}

//查找操作——按序号查找
LinkList Locate_LinkList(LinkList H, int i)
{
    /*i不正确或者链表不存在,则返回NULL,i==0返回头指针,否则返回第i个结点的指针 */
    LinkList p;
    int j;
    p = H;
    j = 0;
    while (p && j < i) //查找第i个结点
    {
        p = p->next;
        j++;
    }
    if (j != i || !p)
    {
        printf("参数i错误或者单链表不存在n");
        return NULL;
    } //第i个结点不存在
    return p;
}

//插入操作
int Insert_LinkList(LinkList H, int i, DataType x)
{
    /*在单链表H的第i个为之前插入值为x的结点,入口参数:单链表,插入位置,插入元素,返回参数:0表示失败,1表示成功 */
    LinkList p, q;
    p = Locate_LinkList(H, i - 1); //找到第i-1个结点地址
    if (!p)
    {
        printf("i有误n");
        return 0;
    }
    q = (LinkList)malloc(sizeof(LNode));
    if (!q)
    {
        printf("申请空间失败n"); //申请空间失败,不能插入
        return 0;
    }
    q->data = x;
    q->next = p->next; //新节点插入在第i-1个结点后面
    p->next = q;
    return 1;
}

//约瑟夫问题-链表解决(这里需要循环链表)
int josephus_LinkList(LinkList josephus_Link, int s, int m)
{
    /*求约瑟夫问题得出列元素序列,入口参数:已经存放数据的链表头指针,起始位置s,从1报数到m,出口参数:1成功,0表示表中没有元素 */
    LinkList pre, p; //p表示当前结点,pre指向其前驱结点
    int count;
    if (!josephus_Link)
    {
        printf("表中无元素!n");
        return 0;
    }
    /*找到第i个元素 */
    p = josephus_Link;
    for (count = 1; count < s; count++) //查找第s个结点,用p作为第s个结点的指针
    {
        p = p->next;
    }
    printf("输出约瑟夫序列:n");
    while (p != p->next) //输出n-1个结点
    {
        pre = p->next;
        while (pre->next != p)
        {
            pre = pre->next; //pre指针初始化,pre是p的前驱指针(单链表,使之让pre成为p的前驱结点)
        }
        for (count = 1; count < m; count++)
        {
            pre = p;
            p = p->next;
        }
        printf("%dt", p->data);
        pre->next = p->next; //进行删除操作
        free(p);
        p = pre->next;
    }
    printf("%dt", p->data); //输出最后一个结点
    free(p);
    return 1;
}

//主函数
int main()
{
    LinkList H;
    LinkList pre;
    int s, m, x;
    int i = 1;
    printf("请问需要插入几个元素:");
    scanf("%d", &i);
    H = Creat_LinkList(i); //创建链表
    pre = H->next;
    while (pre->next != H)
    {
        pre = pre->next; //pre指针初始化,pre是H的前驱指针(单链表,使之让pre成为H的前驱结点)
    }
    for (int j = 1; j <= i; j++) //输出所有结点数据
    {
        printf("%dt", Locate_LinkList(pre, j)->data); //如使查询顺序正确,第一个数据的结点应该是头结点的前驱结点
    }
    printf("n请输入起始的序列号s、以及计数值m:n");
    scanf("%d%d", &s, &m);
    josephus_LinkList(H, s, m);
}