本意是整理和复习,理解不深或者有错误的评论区提出即可。
只有第一关的代码里面有结构体的定义,其余我只放了功能函数。
初始代码
#include <stdio.h>
#include <stdlib.h>
/*此处是顺序线性表数据结构定义*/
typedef int DataType;
struct seqList
{//有3个数据成员
int MAXNUM;//用于记录顺序线性表中能存放的最大元素个数的 整型 MAXNUM
int curNum;//用于存放顺序线性表中数据元素的个数 整型 curNum
DataType *element;//用于存放顺序线性表数据元素的连续空间的起始地址
};
typedef struct seqList *PseqList;
//第一关
PseqList createNullList_seq(int m)
{//此处填写代码,创建一个空的顺序线性表,能存放的最大元素个数为 m
//若m=0,则返回NULL
}
//第二关
int isFullList_seq(PseqList L)
{
//判断顺序线性表是否已满,若已满,返回值为1,否则返回值为0
}
int insertP_seq(PseqList L , int p ,int x)
{// 在线性表L中下标为p的位置插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
//如果线性表满了, 还需输"list is full"的提示
//如果插入位置非法,需输出提示"position is illegel"
}
int insertPre_seq(PseqList L , int p ,int x)
{
// 在线性表L中下标为p的位置的前面插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
//提示:直接调用insertP函数实现即可
}
int insertPost_seq(PseqList L , int p ,int x)
{
// 在线性表L中下标为p的位置的后面插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
//提示:直接调用insertP函数实现即可
}
void printList_seq(PseqList L)
{//逐个输出线性表的元素,相邻的两个数据元素之间以一个空格为分隔符隔开
}
//第三关
int destroyList_seq(PseqList L)
{
//返回值为销毁的线性表中现有数据元素的个数,若待销毁的线性表不存在,则返回0
}
//第四关
int locate_seq(PseqList L,int x)
{//在顺序表L中查找给定值x首次出现的位置,若不存在给定值,则返回-1
}
DataType locatePos_seq(PseqList L,int pos)
{// 在顺序表L中查找指定位置pos处的数据元素,若位置非法,则返回第0个数据元素
}
//第五关
int deletePos_seq(PseqList L,int pos)
{//在顺序表L中删除与下标pos处的数据元素,若pos非法,则返回-1;否则返回1
}
int delete_seq(PseqList L,int x)
{//在顺序表L中删除与参数x值相同的数据元素,返回删除数据元素的个数
//可以使用之前已完成的操作
}
//第六关
void replace_seq(PseqList L,int x,int y)
{//将顺序表L中值为x的数据元素替换为y
}
void delDuplicate_seq(PseqList L)
{//移除线性表中的所有重复元素;不要使用额外的数组空间,必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成
//使用常规删除即可,已修改测试用例
}
1.创建空顺序线性表
题目
任务描述
本关要求按照完成顺序表数据类型定义,并初始化一个顺序线性表。
编程要求
顺序线性表数据结构定义如下:
typedef int DataType;
struct seqList {
int MAXNUM;//用于记录顺序线性表中能存放的最大元素个数的 整型 MAXNUM
int curNum;//用于存放顺序线性表中数据元素的个数 整型 curNum
DataType *element;//用于存放顺序线性表数据元素的连续空间的起始地址
};
本关的编程任务是补全文件中createNullList_seq
函数,以实现初始化一个空的顺序线性表的要求。
开始你的任务吧,祝你成功!
测试
输入:4
输出:success to create a seqlist of 4 elements,current item 0
输入:0
输出:fail to create
输入:6
输出:success to create a seqlist of 6 elements,current item 0
已通过代码
功能函数文章来源:https://www.toymoban.com/news/detail-424457.html
#include <stdio.h>
#include <stdlib.h>
/*此处是顺序线性表数据结构定义*/
typedef int DataType;
struct seqList
{ //有3个数据成员
int MAXNUM;//用于记录顺序线性表中能存放的最大元素个数的 整型 MAXNUM
int curNum;//用于存放顺序线性表中数据元素的个数 整型 curNum
DataType *element;//用于存放顺序线性表数据元素的连续空间的起始地址
};
typedef struct seqList *PseqList;
//第一关
PseqList createNullList_seq(int m)
{//此处填写代码,创建一个空的顺序线性表,能存放的最大元素个数为 m
//若m=0,则返回NULL
if(m == 0){
return NULL;
}
else{
PseqList palist = (PseqList)malloc(sizeof(struct seqList));
if(palist != NULL){//判断创建是否成功
palist->element = (DataType *)malloc(sizeof(DataType)*m);//创建m个元素的空间
if(palist->element){//判断创建是否成功
palist->MAXNUM = m;
palist->curNum = 0;
return palist;
}
else
free(palist); //如果创建元素空间失败则要释放线性表空间
//指针的空间释放之后,指针的值没有改变
}
}
}
main函数
int main(void)
{
int m;
scanf("%d",&m);
PseqList head = createNullList_seq(m);
if(head == NULL)
printf("fail to create");
else
printf("success to create a seqlist of %d elements,current item %d",m,head->curNum);
}
2.顺序表插入
题目
任务描述
本关任务: 你需要实现不同的插入操作: 在顺序线性表中下标为p位置、p位置之前、p位置之后插入数据元素
编程要求
为了实现线性表插入操作,你需要实现判断线性表是否为满的判断函数,另外你需要根据提示,在右侧编辑器补充代码,完成操作insertP_seq,insertPre_seq,insertPost_seq三个插入函数,以及遍历输出线性表数据元素的操作printList_seq。具体说明见操作注释。
开始你的任务吧,祝你成功!
测试
输入:5 1 2 3 4
输出:position is illegel4 1 4 3 2
输入:2 1 4
输出:position is illegel1 4
输入:6 1 2 3 4 5 6
输出:position is illegellist is fulllist is full5 1 5 4 2 3
已通过代码块
功能函数
//第二关
int isFullList_seq(PseqList L)
{
//判断顺序线性表是否已满,若已满,返回值为1,否则返回值为0
return (L->curNum >= L->MAXNUM);
}
int insertP_seq(PseqList L , int p ,int x)
{// 在线性表L中下标为p的位置插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
//如果线性表满了, 还需输"list is full"的提示
//如果插入位置非法,需输出提示"position is illegel"
int q;//记录p的位置
if(isFullList_seq(L)){//线性表已满
printf("list is full");
return 0;
}
else if(p < 0 || p > L->curNum){
//输入非法
printf("position is illegel");
return 0;
}
else{
for(q = L->curNum - 1; q >= p; q--){//q以及q位置以后的元素后移一位
L->element[q+1] = L->element[q];
}
L->element[p] = x;
L->curNum ++;
return 1;
}
}
int insertPre_seq(PseqList L , int p ,int x)
{
// 在线性表L中下标为p的位置的前面插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
//提示:直接调用insertP函数实现即可
return insertP_seq(L , p-1 , x);
}
int insertPost_seq(PseqList L , int p ,int x)
{
// 在线性表L中下标为p的位置的后面插入数据元素x,若下标p非法或线性表已满无法插入数据,返回0;插入成功返回值为1
//提示:直接调用insertP函数实现即可
return insertP_seq(L , p+1 , x);
}
void printList_seq(PseqList L)
{//逐个输出线性表的元素,相邻的两个数据元素之间以一个空格为分隔符隔开
for(int i=0; i < L->curNum; i++){
printf("%d ", L->element[i]);
}
}
main函数
int main(void)
{
int m ,x;
scanf("%d",&m);
PseqList head = createNullList_seq(m);
for(int i=0;i<m/2;i++)
{
scanf("%d",&x);
insertP_seq(head,i,x);
}
for(int i=0;i<m/2;i++)
{
scanf("%d",&x);
insertPre_seq(head,i,x);
insertPost_seq(head,i,x);
}
printList_seq(head);
}
3.销毁线性表
题目
任务描述
本关任务:销毁线性表的实质时实现动态分配的线性表空间回收。
相关知识
使用malloc函数分配的内存空间应该在程序退出时使用free将空间回收还给操作系统。 由于顺序线性表创建时使用了malloc为线性表结构、线性表数据元素动态分配了存储空间,我们应使用free将相应空间回收。
编程要求
根据提示,在右侧编辑器补充代码,实现销毁线性表的功能。
开始你的任务吧,祝你成功!
测试
输入:4 1 3 5 7
输出:4
输入:0
输出:0
输入:5 1 2 3 4 5
输出:5
已通过代码块
功能函数
//第三关
int destroyList_seq(PseqList L)
{
//返回值为销毁的线性表中现有数据元素的个数,若待销毁的线性表不存在,则返回0
if(L == NULL)
return 0;
else{
free(L->element);
return L->curNum;
}
}
主函数
int main(void)
{
int m ,x;
scanf("%d",&m);
PseqList head = createNullList_seq(m);
for(int i=0;i<m;i++)
{
scanf("%d",&x);
insertP_seq(head,i,x);
}
printf("%d", destroyList_seq(head));
}
4.查找
题目
任务描述
本关任务: 1.在顺序线性表中查找第一个值为x的元素下标。 2.在顺序线性表中查找某个位置pos处的数据元素
开始你的任务吧,祝你成功!
测试
输入:8 12 3 23 -12 89 6 67 123 6
输出:
67
5
输入:4 123 4 45 23 10
输出:
123
-1
已通过代码块
功能函数
//第四关
int locate_seq(PseqList L,int x)
{//在顺序表L中查找给定值x首次出现的位置,若不存在给定值,则返回-1
for(int i = 0; i < L->curNum; i++){
if(x == L->element[i])
return i;
}
return -1;
}
DataType locatePos_seq(PseqList L,int pos)
{// 在顺序表L中查找指定位置pos处的数据元素,若位置非法,则返回第0个数据元素
//位置非法
if(pos < 0 || pos > L->curNum)
return L->element[0];
else
return L->element[pos];
}
主函数
int main(void)
{
int m ,x;
scanf("%d",&m);
PseqList head = createNullList_seq(m);
for(int i=0;i<m;i++)
{
scanf("%d",&x);
insertP_seq(head,i,x);
}
scanf("%d",&m);
printf("%d\n",locatePos_seq(head,m));
printf("%d\n",locate_seq(head,m));
destroyList_seq(head);
}
5.删除
题目
任务描述
本关任务: (1)在顺序表L中删除下标pos处的数据元素 (2)在顺序表L中删除与参数x值相同的数据元素
编程要求
根据提示,在右侧编辑器补充第五关的代码。
开始你的任务吧,祝你成功!
测试
输入:6 12 34 56 3 4 12 3 12
输出:
1
2
34 56 4
已通过代码块
功能函数
//第五关
int deletePos_seq(PseqList L,int pos)
{//在顺序表L中删除下标pos处的数据元素,若pos非法,则返回-1;否则返回1
//pos非法
if(pos < 0 || pos > L->curNum - 1)
return -1;
else{
for(int i = pos; i < L->curNum - 1 ; i++)
L->element[i] = L->element[i+1];//pos位置后面的元素均前移一位
L->curNum--;
return 1;
}
}
int delete_seq(PseqList L,int x)
{//在顺序表L中删除与参数x值相同的数据元素,返回删除数据元素的个数
//可以使用之前已完成的操作
int n = 0;//记录删除的元素个数
int p;
for(p = 0; p < L->curNum; p++){
if(L->element[p] == x){
deletePos_seq(L, p);
n++;
}
}
return n;
}
主函数
int main(void)
{
int m ,x;
scanf("%d",&m);
PseqList head = createNullList_seq(m);
for(int i=0;i<m;i++)
{
scanf("%d",&x);
insertP_seq(head,i,x);
}
scanf("%d",&m);
printf("%d\n",deletePos_seq(head,m));
scanf("%d",&m);
printf("%d\n",delete_seq(head,m));
printList_seq(head);
destroyList_seq(head);
}
6.顺序表应用
题目
任务描述
本关任务: (1)使用将顺序表L中值为x的数据元素替换为y; (2)此处假设线性表中的元素用于表示集合,不考虑线性表中元素的位置,移除线性表中的所有重复元素;不要使用额外的数组空间,必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
编程要求
根据提示,在右侧编辑器补充代码,完成第六关的两个函数。
开始你的任务吧,祝你成功!
测试
输入:5 1 5 -1 5 9 5 1
输出:-1 9
输入:6 12 4 3 3 3 3 3 12
输出:4
已通过代码块
功能函数
//第六关
void replace_seq(PseqList L,int x,int y)
{//将顺序表L中值为x的数据元素替换为y
for(int i = 0; i < L->curNum; i++)
if(L->element[i] == x)
L->element[i] = y;
}
void delDuplicate_seq(PseqList L)
{//移除线性表中的所有重复元素;不要使用额外的数组空间,必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成
//使用常规删除即可,已修改测试用例
int t, flag = 0;
//t:记录最开始用来比较的下标
//flag:记录有没有与他重复的元素
for(int i = 0; i < L->curNum; i++){
t = i;
for(int j = i + 1; j < L->curNum; j++){
if(L->element[i] == L->element[j])
deletePos_seq(L, j); //删除重复元素
flag = 1;
}
if(flag)
deletePos_seq(L, t); //如果有重复的元素就把原来用来比较的元素也删掉
flag = 0; //flag清零
}
}
主函数文章来源地址https://www.toymoban.com/news/detail-424457.html
int main(void)
{
int m ,x;
scanf("%d",&m);
PseqList head = createNullList_seq(m);
for(int i=0;i<m;i++)
{
scanf("%d",&x);
insertP_seq(head,i,x);
}
scanf("%d%d",&m,&x);
replace_seq(head,m,x);
delDuplicate_seq(head);
printList_seq(head);
destroyList_seq(head);
}
到了这里,关于数据结构与算法-头歌【1】顺序线性表--课上练的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!