数据结构第一次上机题

2024-02-01 20:19:34

累

麻了麻了，累死了，才把代码敲完，结果发现数据结构上机只用补全代码……
白白敲了好久代码做了一个单链表以及顺序表的操作库出来，气死了

GOOD！！

一看见清爽的代码我就喜欢，有小些BUG，主要出在错误校验部分代码，健壮性不是很好，但是累的不想再改了，有人看见了要用自己改改吧

/*
 * @Author: LIXINTAO
 * @Version: 1.0.0
 * @Date: 2021-10-06 13:40:44
 * @LastEditTime: 2021-10-07 01:03:52
 * @LastEditors: LIXINTAO
 * @Description: The bsp .c of linklist's file
 */
#include "linklist_bsp.h"
#include <stdio.h>
/**
 * @description: 头插法建立链表，即c->a->b
 * @param {*}
 * @return {linklist *}
 */
linklist *CreateListF()
{
        linklist *head, *p;
        char ch;
        head = (linklist *)malloc(sizeof(linklist));
        head->next =NULL;
        while((ch = getchar())!='\n')
        {
            p = (linklist *)malloc(sizeof(linklist));
            p->data = ch;
            p ->next = head ->next;
            head ->next = p;
        }
        return head;
}
/**
 * @description: 尾插法建立链表，即a->b->c
 * @param {*}
 * @return {linklist *}
 */
linklist *CreateListR()
{
        linklist *head, *p, *r;
        char ch;
        head = (linklist *)malloc(sizeof(linklist));
        head->next =NULL;
        r = head;
        // scanf("%c",&ch);
        while((ch=getchar())!=EOF&&ch != '\n')
        {
            p = (linklist *)malloc(sizeof(linklist));
            p->data = ch;
            r ->next = p;
            r = p;
            // scanf("%c",&ch);
        }
        r->next=NULL;
        return head;
}
/**
 * @description: 置空表
 * @param {linklist} *head
 * @return none
 */
void Link_SetNull(linklist *head)
{
	int i;
    if (head == NULL)
    {
            return;
    }
    linklist *p,*r;
    int lenth=Link_Length(head);
    p=head;

    for(i = -1;i<lenth;i++)
    {
        r=p->next;
        free(p);
        p=r;
    }
}
/**
 * @description: 返回表长,若表为空，则返回-1
 * @param {linklist} *head
 * @return 链表的长度
 */
int Link_Length(linklist *head)
{
        if (head == NULL)
        {
                return -1;
        }
        int i = 0;
        linklist *r;
        r=head;

        if(r->next==NULL)
        {
            return 0;
        }

        while(r->next != NULL)
        {
            i++;
            r=r->next;
        }
        return i+1;

}
/**
 * @description: 按序号查找单链表
 * @param {linklist} *head
 * @param {int} i
 * @return {linklist *}表为空或者未找到返回空表，否则返回该结点
 */
linklist *Link_Get(linklist *head, int i)
{
    if (head==NULL)
    {
        return NULL;
    }
    
    linklist *p=head;
    int j=0;
    while(p->next!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    if(i==j) return p;
    else return NULL;
}
/**
 * @description: 查找x的结点
 * @param {linklist} *head
 * @param {datatype} x  当前查找值
 * @return  若表L中存在一个或者多个值x的元素，如果查找到，返回该结点；否则，返回NULL
 *          表为空返回NULL
 */
linklist *Link_Locate(linklist *head, datatype x)
{
        if (head == NULL)
        {
                return NULL;
        }

        linklist *p=head->next;
        while(p!=NULL&&p->data!=x)
        {
            p=p->next;
        }
        return p;
}
/**
 * @description: 在位序为i的结点插入x
 * @param {sequenlist} *L
 * @param {datatype} x
 * @param {int} i
 * @return 插入成功返回true，失败返回false
 */
_Bool Link_Insert(linklist *L, datatype x, int i)
{
    linklist *p,*s;
    p=Link_Get(L,i-1);
    if(p==NULL) return false;
    else 
    {
        s=(linklist *)malloc(sizeof(linklist));
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
    return true;
}
/**
 * @description: 删除位序为i的结点
 * @param {sequenlist} *L
 * @param {int} i
 * @return 成功返回true
 *         失败返回false
 */
_Bool Link_Delete(linklist *L, int i)
{
    linklist *p,*r;
    p=Link_Get(L,i-1);
    if(p==NULL) return false;
    if(p!=NULL&&p->next!=NULL)
    {
        r=p->next;
        p->next=r->next;
        free(r);
    }
    return true;
}

/**
 * @description: 在循环链表中插入,将插入链表h中
 * @param {linklist} *h
 * @param {linklist} *p
 * @return {*}
 */
void Link_Roll_Insert(linklist *h, linklist *p)
{
    linklist *q = h;
    while (q->next != h)
        q = q->next;
    q->next = p;
    p->next = h;
}

/*
 * @Author: LIXINTAO
 * @Version: 1.0.0
 * @Date: 2021-10-06 13:41:35
 * @LastEditTime: 2021-10-07 01:57:42
 * @LastEditors: LIXINTAO
 * @Description: The bsp .h of linklist's file
 */
#ifndef __LINKLIST_BSP_H
#define __LINKLIST_BSP_H

#include <stdbool.h>
#include "stdlib.h"

typedef char datatype;
typedef struct node
{
    datatype data;
    struct node *next;
}linklist;


extern linklist *CreateListF();//头插法建立链表
extern linklist *CreateListR();//尾插法建立链表
extern void Link_SetNull(linklist *head);//置空表
extern int Link_Length(linklist *head);//返回表长
extern linklist *Link_Get(linklist *head, int i);//按序号查找单链表
extern linklist *Link_Locate(linklist *head, datatype x);//定位，按值查找
extern _Bool Link_Insert(linklist *L,datatype x,int i);//插入
extern _Bool Link_Delete(linklist *L,int i);//删除i结点
extern void Link_Roll_Insert(linklist *h, linklist *p);//在循环链表中插入结点

#endif /*__LINKLIST_BSP_H*/

seqlist_bsp.h

/*
 * @Author: LIXINTAO（LOGOTAO）
 * @Version: 1.0.0
 * @Date: 2021-10-06 13:38:59
 * @LastEditTime: 2021-10-06 20:35:15
 * @LastEditors: LIXINTAO
 * @Description: The bsp .c file of sequenlist's study
 */

#include "seqlist_bsp.h"

/**
 * @description: 创建一个顺序表
 * @param        none
 * @return       sequenlist *L
 * note          none
 */
sequenlist *Seq_InitList()
{
        sequenlist *L = (sequenlist *)malloc(sizeof(sequenlist));
        L->last = 0;
        return L;
}
/**
 * @description: 置空表
 * @param {sequenlist} *L
 * @return none
 */
void Seq_SetNull(sequenlist *L)
{
        if (L == NULL)
        {
                return;
        }
        free(L);
}
/**
 * @description: 返回表长,若表为空，则返回-1
 * @param {sequenlist} *L
 * @return 顺序表的长度
 */
int Seq_Length(sequenlist *L)
{
        if (L == NULL)
        {
                return -1;
        }
        return L->last;
}
/**
 * @description: 取第i个元素的值，如果发生上溢，则返回2^31-1，即int类型最大值；
 *               若表为空，返回int类型最小值-2^31;
 * @param {sequenlist} *L
 * @param {int} i
 * @return {datatype}
 */
datatype Seq_Get(sequenlist *L, int i)
{
        if (L == NULL)
        {
                return -2147483648; //-2^31
        }

        if (L->last < i || i <= 0)
        {
                return 2147483647; //2^31-1
        }
        return L->data[i - 1];
}
/**
 * @description: 查找x的位序，找到返回位序号，没找到返回-2，表为空返回-1
 * @param {sequenlist} *L
 * @param {datatype} x  当前查找值
 * @return  若表L中存在一个或者多个值x的元素，如果查找到，返回第一个元素
 *          的位序；否则，返回-2
 *          表为空返回-1
 */
int Seq_Locate(sequenlist *L, datatype x)
{
        if (L == NULL)
        {
                return -1;
        }

        int i;
        for (i = 0; i < L->last; i++)
        {
                if (x == L->data[i])
                {
                        return i + 1;
                }
        }
        return -2;
}
/**
 * @description: 在位序为i的结点插入x
 * @param {sequenlist} *L
 * @param {datatype} x
 * @param {int} i
 * @return 插入成功返回true，失败返回false
 */
_Bool Seq_Insert(sequenlist *L, datatype x, int i)
{
	int j;
    for (j = L->last; j >= i; j--)
    {
            L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = x;
    L->last++;
    return true;
}
/**
 * @description: 删除位序为i的结点
 * @param {sequenlist} *L
 * @param {int} i
 * @return 成功返回true
 *         失败返回false
 */
_Bool Seq_Delete(sequenlist *L, int i)
{
	int j ;
        if (L == NULL || L->last < i || i <= 0)
        {
                return false;
        }
        for (j= i; j <= L->last - 1; j++)
        {
                L->data[j - 1] = L->data[j];
        }
        L->last--;
        return true;
}

seqlist_bsp.c

/*
 * @Author: LIXINTAO（LOGOTAO）
 * @Version: 1.0.0
 * @Date: 2021-10-06 13:38:59
 * @LastEditTime: 2021-10-06 20:35:15
 * @LastEditors: LIXINTAO
 * @Description: The bsp .c file of sequenlist's study
 */

#include "seqlist_bsp.h"

/**
 * @description: 创建一个顺序表
 * @param        none
 * @return       sequenlist *L
 * note          none
 */
sequenlist *Seq_InitList()
{
        sequenlist *L = (sequenlist *)malloc(sizeof(sequenlist));
        L->last = 0;
        return L;
}
/**
 * @description: 置空表
 * @param {sequenlist} *L
 * @return none
 */
void Seq_SetNull(sequenlist *L)
{
        if (L == NULL)
        {
                return;
        }
        free(L);
}
/**
 * @description: 返回表长,若表为空，则返回-1
 * @param {sequenlist} *L
 * @return 顺序表的长度
 */
int Seq_Length(sequenlist *L)
{
        if (L == NULL)
        {
                return -1;
        }
        return L->last;
}
/**
 * @description: 取第i个元素的值，如果发生上溢，则返回2^31-1，即int类型最大值；
 *               若表为空，返回int类型最小值-2^31;
 * @param {sequenlist} *L
 * @param {int} i
 * @return {datatype}
 */
datatype Seq_Get(sequenlist *L, int i)
{
        if (L == NULL)
        {
                return -2147483648; //-2^31
        }

        if (L->last < i || i <= 0)
        {
                return 2147483647; //2^31-1
        }
        return L->data[i - 1];
}
/**
 * @description: 查找x的位序，找到返回位序号，没找到返回-2，表为空返回-1
 * @param {sequenlist} *L
 * @param {datatype} x  当前查找值
 * @return  若表L中存在一个或者多个值x的元素，如果查找到，返回第一个元素
 *          的位序；否则，返回-2
 *          表为空返回-1
 */
int Seq_Locate(sequenlist *L, datatype x)
{
        if (L == NULL)
        {
                return -1;
        }

        int i;
        for (i = 0; i < L->last; i++)
        {
                if (x == L->data[i])
                {
                        return i + 1;
                }
        }
        return -2;
}
/**
 * @description: 在位序为i的结点插入x
 * @param {sequenlist} *L
 * @param {datatype} x
 * @param {int} i
 * @return 插入成功返回true，失败返回false
 */
_Bool Seq_Insert(sequenlist *L, datatype x, int i)
{
	int j;
    for (j = L->last; j >= i; j--)
    {
            L->data[j] = L->data[j - 1];
    }
    L->data[i - 1] = x;
    L->last++;
    return true;
}
/**
 * @description: 删除位序为i的结点
 * @param {sequenlist} *L
 * @param {int} i
 * @return 成功返回true
 *         失败返回false
 */
_Bool Seq_Delete(sequenlist *L, int i)
{
	int j ;
        if (L == NULL || L->last < i || i <= 0)
        {
                return false;
        }
        for (j= i; j <= L->last - 1; j++)
        {
                L->data[j - 1] = L->data[j];
        }
        L->last--;
        return true;
}

main.c(分类字符作业)

/*
 * @Author: LIXINTAO
 * @Version: 1.0.0
 * @Date: 2021-10-06 13:36:44
 * @LastEditTime: 2021-10-07 02:19:11
 * @LastEditors: LIXINTAO
 * @Description: 将储存混合字符的单链表分为字母、数字、其他字符的混合链表
 */
#include <stdio.h>

#include "bsp\linklist_bsp.h"
// #include "bsp\seqlist_bsp.h"
#include "bsp\linklist_bsp.c"
// #include "bsp\seqlist_bsp.c"

/**
 * @description: 单链表打印
 * @param {linklist} *head
 * @return {void}
 */
void U1_printf(linklist *head);

/**
 * @description: 循环链表打印
 * @param {linklist} *head
 * @return {void}
 */
void U2_printf(linklist *head);
/**
 * @description: 分类字符
 * @param {linklist} *head
 * @param {linklist} *letter
 * @param {linklist} *digit
 * @param {linklist} *other
 * @return {void}
 */
void Link_Resolve(linklist *head, linklist *letter, linklist *digit, linklist *other);

int main()
{
    linklist *head, *letter, *digit, *other;
    head = CreateListR();
    U1_printf(head);
    letter = (linklist *)malloc(sizeof(linklist)); //建立3个空循环链表
    letter->next = letter;
    digit = (linklist *)malloc(sizeof(linklist));
    digit->next = digit;
    other = (linklist *)malloc(sizeof(linklist));
    other->next = other;
    Link_Resolve(head, letter, digit, other); //调用分解单链表的函数
    U2_printf(letter);                        //输出循环链表
    U2_printf(digit);
    U2_printf(other);
    getchar();
}
/**
 * @description: 单链表打印
 * @param {linklist} *head
 * @return {void}
 */
void U1_printf(linklist *head)
{
    linklist *p = head->next;
    while (p != NULL)
    {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

/**
 * @description: 循环链表打印
 * @param {linklist} *head
 * @return {void}
 */
void U2_printf(linklist *head)
{
    linklist *p = head->next;
    while (p != head)
    {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\n");
}

/**
 * @description: 分类字符
 * @param {linklist} *head
 * @param {linklist} *letter
 * @param {linklist} *digit
 * @param {linklist} *other
 * @return {void}
 */
void Link_Resolve(linklist *head, linklist *letter, linklist *digit, linklist *other)
{
    linklist *p,*r;
    p=head->next;
    //head->next=NULL;
    
    while (p != NULL)
    {
        r=p;//紧接着就要将p重新赋值，因为这个要是在下面写的话，就是把p改变了
        p = p->next;
        if (r->data <= '9' && r->data >= '0')
        {
            Link_Roll_Insert(letter, r);
        }
        else if ((r->data >= 'a' && r->data <= 'z') || (r->data >= 'A' && r->data <= 'Z'))
        {
            Link_Roll_Insert(digit, r);
        }
        else
        {
            Link_Roll_Insert(other, r);
        }
    }
}

main.c(排序作业)

/*
 * @Author: LIXINTAO
 * @Version: 1.0.0
 * @Date: 2021-10-06 13:36:44
 * @LastEditTime: 2021-10-07 00:31:19
 * @LastEditors: LIXINTAO
 * @Description: 使用顺序表和单链表颠倒排列顺序，要求逆线性表占用原线性表的存储空间
 *               使用条件编译区分顺序表模式（SEQUEN_MODE）和单链表模式（LINK_MODE）
 */
#include <stdio.h>

#include "bsp\linklist_bsp.h"
#include "bsp\seqlist_bsp.h"
#include "bsp\linklist_bsp.c"
#include "bsp\seqlist_bsp.c"

#define LISTLENTH 10 //线性表数据长度

#define SEQUEN_MODE 1//顺序表模式代码
//#define LINK_MODE 2 //单链表模式代码

/**
 * @description: 顺序表元素反转
 * @param {sequenlist} *L
 * @return {*}
 */
void Seq_Reverse(sequenlist *L);

linklist *Link_Reverse_R(linklist *head);
int main()
{
#ifdef SEQUEN_MODE //顺序表模式
    printf("This is SEQUEN_MODE.\n");

    int i;
    sequenlist sequen;
    datatype data;
    sequen = *Seq_InitList(); //初始化顺序表

    for (i = 1; i <= LISTLENTH; i++) //顺序表赋值
    {
        scanf("%d", &data);
        Seq_Insert(&sequen, data, i);
    }

    Seq_Reverse(&sequen); //反转顺序表

    for (i = 1; i <= LISTLENTH; i++) //顺序表的打印
    {
        printf("%d\n", Seq_Get(&sequen, i));
    }

    getchar();
    getchar();
#elif LINK_MODE //单链表模式
    printf("This is LINK_MODE.\n");

    linklist *link, *readlink;
    datatype data;
    int i;

    link = CreateListF();        //创建链表
    link = Link_Reverse_R(link); //链表反转

    readlink = link;
    while (readlink->next != NULL) //链表打印
    {
        printf("%c\n", readlink->data);
        readlink = readlink->next;
    }

    getchar();
#endif
}
/**
 * @description: 顺序表元素反转
 * @param {sequenlist} *L
 * @return {*}
 */
void Seq_Reverse(sequenlist *L)
{
    int i;
    datatype temp;
    for (i = 0; i < L->last / 2; i++)
    {
        temp = L->data[i];
        L->data[i] = L->data[L->last - i - 1];
        L->data[L->last - i - 1] = temp;
    }
}
/**
 * @description: 递归法反转链表
 * @param {linklist} *head
 * @return {linklist *}
 */
linklist *Link_Reverse_R(linklist *head)
{
    linklist *r;
    if (head == NULL || head->next == NULL)
        return head;
    r = Link_Reverse_R(head->next);
    head->next->next = head; //将a->b->NULL，转化为b->a->NULL形式
    head->next = NULL;
    return r;
}

效果

数据结构第一次上机题

数据结构第一次上机题

数据结构第一次上机题

数据结构第一次上机题

数据结构第一次上机题

数据结构第一次上机题

数据结构第一次上机题

好康！！！

上一篇：数据结构与算法C程序（2单链表）


下一篇：合并两个有序单链表