数据结构 day3

思维导图：

学习内容：

1. 顺序表

1.1 概念

1.2 有关顺序表的操作

1.2.1 创建顺序表

1.2.2 顺序表判空和判断满

1.2.3 向顺序表中添加元素

1.2.4 遍历顺序表

1.2.5 顺序表按位置进行插入元素

1.2.6 顺序表任意位置删除元素

1.2.7 按值进行查找位置函数

1.2.8 按位置修改函数

1.2.9 按值修改函数

课外作业：

思维导图：

学习内容：

1. 顺序表

1.1 概念

1. 顺序存储的线性表叫做顺序表

线性表：说明该容器对应的逻辑结构为线性结构

顺序存储：表示存储结构为顺序结构，就是使用连续的存储空间进行操作

2. 连续存储空间：可以使用数组来完成或者使用堆区空间

3. 顺序表的表示方式：除了使用一个连续的内存存储顺序表外，还需要外加一个表示顺序表实际长度的变量完成

4. 对顺序表长度的解析：

1、顺序表的长度能够表示顺序表中实际使用的元素个数

2、也能够表示数组中第一个没有存放数据元素的数组元素下标

3、要遍历整个顺序表时，顺序表的长度是最大上限

5. 顺序表结构体类型

#define MAX 20          //顺序表最大容量
typedef int datatype;   //数据元素类型//定义顺序表结构体类型
typedef struct
{datatype data[MAX];   //存放顺序表的数组int len;             //顺序表的长度
}SeqList, *SeqListPtr;

1.2 有关顺序表的操作

1.2.1 创建顺序表

1、可以在堆区申请一个顺序表，后面操作时，只需要将该顺序表的起始地址传递即可

2、申请出顺序表的空间后，至少需要对顺序表的长度初始化

例如：

//定义顺序表的创建函数
SeqListPtr list_create()
{//在堆区申请一个顺序表的大小空间SeqListPtr L = (SeqListPtr)malloc(sizeof(SeqList));if(NULL == L){printf("创建失败\n");return NULL;}//程序执行至此，表示顺序表创建成功memset(L->data, 0, sizeof(L->data));    //将数组初始化L->len = 0;           //顺序表长度为0printf("创建成功\n");return L;
}

1.2.2 顺序表判空和判断满

1、对于添加顺序表元素的操作而言，需要判断顺序表是否已经满了，如果满了的话，则添加失败

一般情况：len <= MAX

满：len == MAX

2、对于减少顺序表元素的操作而言，需要判断顺序表是否已经空了，如果空了的话，就减少失败

空：len == 0

int list_empty(SeqListPtr L)
{return L->len==0;
}//判满函数，满返回真，非满返回假
int list_full(SeqListPtr L)
{return L->len==MAX;
}

1.2.3 向顺序表中添加元素

1、判断条件：如果顺序表已经满了，就不能进行添加操作

2、每次添加的数据放入到顺序表的最后面，也就是放在len所在的位置

3、添加完元素后，需要将长度增加

//添加元素
int list_add(SeqListPtr L, datatype e)
{//判断逻辑if(NULL==L || list_full(L)){printf("添加失败\n");return -1;}//添加逻辑:将要添加的元素放到最后一个位置L->data[L->len] = e;//表的变化L->len++;printf("添加成功\n");return 0;
}

1.2.4 遍历顺序表

1、判断逻辑：表是否合法，表是否为空

2、本质上就是数组的遍历，只是遍历到顺序表的长度结束即可

//遍历顺序表
void list_show(SeqListPtr L)
{//判断逻辑if(NULL == L || list_empty(L)){printf("遍历失败\n");return ;}//遍历printf("顺序表中元素分别是：");for(int i=0; i<L->len; i++){printf("%d\t", L->data[i]);}printf("\n");
}

1.2.5 顺序表按位置进行插入元素

1、判断逻辑：顺序表不为空，顺序表不满，要插入位置不能小于0，也不能大于len

2、插入逻辑：需要将从最后一个元素到要插入位置的元素之间所有元素整体向后移动一格

将新元素放入到要插入位置即可

/定义任意位置插入函数 
int list_insert_pos(SeqListPtr L, int pos, datatype e)
{//判断逻辑if(NULL==L || list_full(L) || pos<0 || pos>L->len){printf("插入失败\n");return -1;}//腾空逻辑for(int i=L->len-1; i>=pos; i--){L->data[i+1] = L->data[i];//将前面的元素后移}//插入数据L->data[pos] = e;//表长变化L->len++;printf("插入成功\n");return 0;
}

1.2.6 顺序表任意位置删除元素

1、判断逻辑：表是否为空、表是否合法、删除位置是否合法

2、需要将要删除位置后面的元素开始到最后一个位置为止，整体前移动一格

//定义任意位置删除函数
int list_delete_pos(SeqListPtr L, int pos)
{//判断逻辑 if(NULL==L || list_empty(L) || pos<0 || pos>=L->len){printf("删除失败\n");return -1;}//删除逻辑for(int i=pos+1; i<L->len; i++){L->data[i-1] = L->data[i];      //将元素向前偏移}//表长变化L->len --;printf("删除成功\n");return 0;
}

1.2.7 按值进行查找位置函数

//定义按值查找位置函数
int list_search_value(SeqListPtr L, datatype e)
{//判断逻辑if(NULL==L || list_empty(L)){printf("查找失败\n");return -1;}//遍历整个顺序表for(int i=0; i<L->len; i++){if(L->data[i] == e){return i;        //返回查找到的数据下标}}printf("没找到\n");return -1;
}

1.2.8 按位置修改函数

//按位置进行修改
int list_update_pos(SeqListPtr L, int pos, datatype e)
{//判断逻辑if(NULL==L || pos<0 || pos>=L->len || list_empty(L)){printf("修改失败\n");return -1;}//正常进行修改L->data[pos] = e;printf("修改成功\n");return 0;
}

1.2.9 按值修改函数

//按值进行修改
int list_update_value(SeqListPtr L, datatype old_e, datatype new_e)
{//判断逻辑if(NULL==L || list_empty(L)){printf("修改失败\n");return -1;}//根据旧值找的位置int res = list_search_value(L, old_e);if(res == -1){printf("没有要修改的值\n");return -1;}//调用函数完成按位置修改list_update_pos(L, res, new_e);printf("修改成功\n");return 0;
}

课外作业：

上节课的作业，加上增删改查方法。

解析：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100            //最大容量//定义学生类型
struct stu
{char name[20];int age;int score;
};
//定义班级类型
struct Class
{struct stu student[MAX];       //存放学生的容器int size;                      //实际人数
};
struct Class *create(int count){struct Class *cls = (struct Class *)malloc(sizeof(struct Class));cls->size = count;if(NULL == cls){printf("申请失败\n");return NULL;}//程序执行至此，表示内存申请成功//给内存空间进行初始化memset(cls, 0, sizeof(int)*(count));//将内存地址返回return cls;
}int list_empty(struct Class *stu)
{return stu->size ==0;
}int list_full(struct Class *stu)
{return stu->size == MAX;
}//菜单
void print_menu(){printf("\n学生管理系统\n");printf("功能1：完成对学生信息的录入\n");printf("功能2：完成对学生信息的输出\n");printf("功能3：输出成绩最高和最低学生的信息\n");printf("功能4：班级的销毁\n");printf("功能5：对学生信息按成绩进行降序排序\n");printf("功能6：增加一个学生信息\n");printf("功能7：删除一个学生信息\n");printf("功能8：修改一个学生信息\n");printf("功能9：查询一个学生信息\n");printf("功能0：退出\n");printf("请选择操作（0-5）：");
}
//定义学生录用信息函数
int enterstu(struct Class *stu){                  for (int i = 0; i < stu->size; i++)            // 循环遍历输入各个学生信息{printf("输入学生 %d 的姓名：", i + 1);scanf("%s",stu->student[i].name);printf("输入学生 %d 的年龄：", i + 1);scanf("%d",&stu->student[i].age);printf("输入学生 %d 的成绩：", i + 1);scanf("%d",&stu->student[i].score);}
}
//求出学生成绩最大最小值函数
void maxminstu(struct Class *stu){int maxscore=0;             //定义初始值int minscore=0;              //定义初始值for (int i = 0; i < stu->size; i++)          {//判断最大值if(stu->student[i].score >stu->student[maxscore].score)            {                                                   maxscore = i;}//判断最小值if(stu->student[i].score < stu->student[minscore].score){minscore = i;}}//打印输出成绩最大最小值的信息printf("最高成绩的名字为%s,年龄为%d,成绩为%d\n",stu->student[maxscore].name,stu->student[maxscore].age,stu->student[maxscore].score);printf("最低成绩的名字为%s,年龄为%d,成绩为%d\n",stu->student[minscore].name,stu->student[minscore].age,stu->student[minscore].score);
}
//打印学生信息函数
void print_stu(struct Class *stu){if(NULL == stu){printf("error\n");return ;}printf("姓名\t年龄\t成绩\n");for (int i = 0; i < stu->size; i++)           // 循环遍历学生信息，打印出来{printf("%s\t%d\t%d\n",stu->student[i].name,stu->student[i].age,stu->student[i].score);}
}
//排序函数
void sortstu(struct Class *stu){for(int i = 1; i < stu->size; i++){                  //交换三部曲for(int j = 0; j < stu->size-i; j++){if(stu->student[j].score > stu->student[j+1].score){struct stu temp = stu->student[j];stu->student[j] = stu->student[j+1];stu->student[j+1] = temp;}}}print_stu(stu);
}
//释放内存的函数
void destroy(struct Class *stu)
{//释放内存if(NULL != stu){free(stu);       //释放空间stu = NULL;}
}
int stu_insert(struct Class *stu,int pos){if(NULL == stu || list_full(stu) || pos <0 || pos >stu->size){printf("插入失败\n");return -1;}for (int i = stu->size; i > pos; i--){stu->student[i] = stu->student[i-1];}printf("输入学生的姓名：");scanf("%s",stu->student[pos].name);printf("输入学生的年龄：");scanf("%d",&stu->student[pos].age);printf("输入学生的成绩：");scanf("%d",&stu->student[pos].score);stu->size++;printf("插入成功\n");print_stu(stu);return 0;
}
int stu_delete(struct Class *stu,char *value)
{int pos=0;if(NULL == stu || list_empty(stu)){printf("删除失败\n");return -1;}for (int i = 0; i < stu->size; i++){if(strcmp(stu->student[i].name,value) == 0){pos=i;}}for(int i=pos;i<stu->size;i++){stu->student[i]=stu->student[i+1];}stu->size--;printf("删除成功\n");print_stu(stu);return 0;
}
int stu_update(struct Class *stu ,char *value)
{if(NULL == stu || list_empty(stu) ){printf("修改失败\n");return -1;}for (int i = 0; i < stu->size; i++){if(strcmp(stu->student[i].name,value) == 0){printf("输入学生的年龄：");scanf("%d",&stu->student[i].age);printf("输入学生的成绩：");scanf("%d",&stu->student[i].score);}}printf("修改成功\n");print_stu(stu);return 0;
}
int stu_seach(struct Class *stu,char *value){if(NULL == stu || list_empty(stu) ){printf("查找失败\n");return -1;}for (int i = 0; i < stu->size; i++){if(strcmp(stu->student[i].name,value) == 0){printf("找到了\n");printf("学生姓名为：%s，年龄为%d，成绩为%d\n",stu->student[i].name,stu->student[i].age,stu->student[i].score);}else{printf("未找到");}}return 0;
}
int main(int argc, char const *argv[])
{int menu=0;  int size =0 ;printf("请输入班级实际人数：");scanf("%d",&size);                 //输入实际人数struct  Class *cls = create(size);             //获取Classwhile (1){//提示用户输入功能print_menu();scanf("%d",&menu);switch (menu){case 1:enterstu(cls);break;case 2:print_stu(cls);break;case 3:maxminstu(cls);break;case 4:{destroy(cls);cls = NULL;print_stu(cls);}break;case 5:sortstu(cls);break;case 6:{int n=0;printf("请输入你要插入第几个位置：");scanf("%d",&n);stu_insert(cls,n-1);}break;case 7:{char value[MAX]="";printf("请输入你要删除信息的姓名");scanf("%s",value);stu_delete(cls,value);}break;case 8:{char value[MAX]="";printf("请输入你要修改信息的姓名");scanf("%s",value);stu_update(cls,value);}break;case 9:{char value[MAX]="";printf("请输入你要查找的姓名");scanf("%s",value);stu_seach(cls,value);}break;case 0: goto END;default:printf("您输入的功能有误，请重新输入\n");}}END:return 0;
}