数据结构第一次上机题
2021/10/7 6:11:12
本文主要是介绍数据结构第一次上机题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
累
麻了麻了，累死了，才把代码敲完，结果发现数据结构上机只用补全代码……
白白敲了好久代码做了一个单链表以及顺序表的操作库出来，气死了
GOOD！！
一看见清爽的代码我就喜欢，有小些BUG，主要出在错误校验部分代码，健壮性不是很好，但是累的不想再改了，有人看见了要用自己改改吧
linklist_bsp.c
/*
* @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;
}
linklist_bsp.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;
}
效果
好康！！！
这篇关于数据结构第一次上机题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-12-22项目：远程温湿度检测系统
- 2024-12-21《鸿蒙HarmonyOS应用开发从入门到精通（第2版）》简介
- 2024-12-21后台管理系统开发教程：新手入门全指南
- 2024-12-21后台开发教程：新手入门及实战指南
- 2024-12-21后台综合解决方案教程：新手入门指南
- 2024-12-21接口模块封装教程：新手必备指南
- 2024-12-21请求动作封装教程：新手必看指南
- 2024-12-21RBAC的权限教程：从入门到实践
- 2024-12-21登录鉴权实战：新手入门教程
- 2024-12-21动态权限实战入门指南
