函数接口之快排:
void QuickSort(SeqList* ps,int left,int right) { if (left > right) return; int begin = left, end = right; int keyi = left; while (left < right) { while (left < right && (strcmp(ps->student[right].id,ps->student[keyi].id)>= 0)) { right--; } while (left < right && (strcmp(ps->student[left].id, ps->student[keyi].id)<= 0)) { left++; } Swap(&ps->student[left], &ps->student[right]); } int meeti = left; Swap(&ps->student[meeti], &ps->student[keyi]); QuickSort(ps, begin, meeti - 1); QuickSort(ps, meeti + 1, end); }
函数调用之交换:
void Swap(Student* a, Student* b)//这个类型开始写的时候有点难受就是 { Student temp = *a; *a = *b; *b = temp; }
4-7按学号查找学生信息(题目要求使用使用二分查找,二分查找前提是有序,因此我们要先进行排序)
case 7: printf("查找学生信息\n"); QuickSort(&ST, 0, ST.size - 1);//复用上个给学号排序的快排函数接口进行排序 char findId[18]={0}; printf("请输入你要查找的学生的学号:>"); scanf("%s", findId); int ret=SeqListBinarySearch(&ST,findId);//调用二分查找函数接口 if (ret == -1) { printf("统计表中不存在学号为%s的学生\n", findId); } else { printf("找到了!该学号为:%s的同学的姓名:%s\t成绩:%d\n", findId,ST.student[ret].name, ST.student[ret].grade); } printf("\n"); break;
函数接口:
int SeqListBinarySearch(SeqList* ps, char* findId) { int left = 0, right = ps->size - 1; while (left <= right) { int mid = left + (right - left) / 2; if (strcmp(ps->student[mid].id, findId) == 0) { return mid; break; } else if (strcmp(ps->student[mid].id, findId) > 0) { right = mid - 1; } else { left = mid + 1; } } return -1; }
4-8指定位置删除学生信息
case 8: printf("删除学生信息\n"); int locate = 0; printf("请输入你要删除的学生位置(目前可删除位置必须小于等于%d):>",ST.size); scanf("%d", &locate); SeqListDelete(&ST, locate-1);//删除元素函数接口 printf("删除成功\n"); printf("\n"); break;
函数接口:
void SeqListDelete(SeqList* ps, int locate) { int begin = locate+1; while (begin <= ps->size-1)//前移从前面那端开始移动 { ps->student[begin-1] = ps->student[begin]; begin++; } ps->size--;//勿漏 }
4.顺序表的销毁:题目虽然没有要求,但是这个必须加上!老师和我们说过动态内存开辟的空间要手动释放,毕竟谁开辟谁释放嘛,否则会损害公司的服务器!!!
函数接口:
void SeqListDestory(SeqList* ps) { free(ps->student); ps->student = NULL; ps->size = 0; ps->capacity = 0; }
5.打印结果
6.源码分享共有两个文件(test,c文件和seqlist.c文件)
test.c文件
#define _CRT_SECURE_NO_WARNINGS 1 #include"seqlist.h" int main() { SeqList ST; SeqListInit(&ST); int input = 0; //打印列表并且做出选择 meau(); do { printf("请输入你的选择:>"); scanf("%d", &input); //根据菜单选择执行相应操作 switch (input) { case 0: printf("退出程序\n"); printf("\n"); break; case 1: printf("录入学生信息\n"); int n = 0; printf("请输入待插入学生的个数;>"); scanf("%d", &n); for (int i = 0; i < n; i++) { Student stu; printf("请输入待插入学生的学号,姓名,分数:>"); scanf("%s%s%d", stu.id, stu.name, &stu.grade); SeqListPushBack(&ST, stu); } printf("插入成功\n"); printf("\n"); break; case 2: printf("打印学生信息\n"); SeqListPrint(&ST); printf("\n"); break; case 3: printf("插入学生信息\n"); //插入学生的位置 int pos = 0; printf("请输入你要待插入学生信息的位置(目前可插入位置必须小于等于%d):>", ST.size); scanf("%d", &pos); //待插入学生的信息 Student stu; printf("请输入待插入学生的学号,姓名,分数:>"); scanf("%s%s%d", stu.id, stu.name, &stu.grade); SeqListInsert(&ST, stu, pos - 1); printf("插入成功\n"); printf("\n"); break; case 4: printf("统计学生个数\n"); int sz = SeqListSize(&ST); printf("当前统计表中学生的个数为:%d\n", sz); printf("\n"); break; case 5: printf("按姓名来排序\n"); InsertSort(&ST); SeqListPrint(&ST); printf("\n"); break; case 6: printf("按学号来排序\n"); QuickSort(&ST, 0, ST.size - 1); SeqListPrint(&ST); printf("\n"); break; case 7: printf("查找学生信息\n"); QuickSort(&ST, 0, ST.size - 1); char findId[18]={0}; printf("请输入你要查找的学生的学号:>"); scanf("%s", findId); int ret=SeqListBinarySearch(&ST,findId); if (ret == -1) { printf("统计表中不存在学号为%s的学生\n", findId); } else { printf("找到了!该学号为:%s的同学的姓名:%s\t成绩:%d\n", findId,ST.student[ret].name, ST.student[ret].grade); } printf("\n"); break; case 8: printf("删除学生信息\n"); int locate = 0; printf("请输入你要删除的学生位置(目前可删除位置必须小于等于%d):>",ST.size); scanf("%d", &locate); SeqListDelete(&ST, locate-1); printf("删除成功\n"); printf("\n"); break; default: printf("输入有误,请重新输入\n"); printf("\n"); break; } } while (input); SeqListDestory(&ST); }
seqlist,h文件
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<string.h> typedef struct Student { char id[18]; char name[18]; int grade; }Student; typedef struct SeqList { Student* student; int size; int capacity; }SeqList; void meau() { printf("************************\n"); printf("***** 0.退出程序 *****\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"); } void SeqListInit(SeqList* ps) { ps->student = (Student*)malloc(sizeof(Student)*4); if (ps->student == NULL) { printf("malloc fail\n"); exit(-1); } ps->size = 0; ps->capacity = 4; } void CheckCapacity(SeqList* ps) { if (ps->size == ps->capacity) { int newcapacity = 2 * ps->capacity; Student* temp = realloc(ps->student, sizeof(Student) * newcapacity); assert(!temp); ps->student = temp; ps->capacity = newcapacity; } } void SeqListPushBack(SeqList* ps, Student stu) { CheckCapacity(ps); ps->student[ps->size] = stu; ps->size++; } void SeqListPrint(SeqList* ps) { for (int i = 0; i < ps->size; i++) { printf("学号:%s\t名字:%s\t分数:%d\n", ps->student[i].id, ps->student[i].name, ps->student[i].grade); } } void SeqListInsert(SeqList* ps, Student stu, int pos) { CheckCapacity(ps); int end = ps->size - 1; while (end >= pos) { ps->student[end + 1] = ps->student[end]; end--; } ps->student[pos] = stu; ps->size++; } int SeqListSize(SeqList* ps) { return ps->size; } void InsertSort(SeqList* ps) { for (int i = 0; i < ps->size - 1; i++) { int end = i; Student temp = ps->student[i + 1]; while (end >= 0) { if ((strcmp(ps->student[end].name,temp.name))>0) { ps->student[end + 1] = ps->student[end]; end--; } else { break; } } ps->student[end + 1] = temp; } } void Swap(Student* a, Student* b) { Student temp = *a; *a = *b; *b = temp; } void QuickSort(SeqList* ps,int left,int right) { if (left > right) return; int begin = left, end = right; int keyi = left; while (left < right) { while (left < right && (strcmp(ps->student[right].id,ps->student[keyi].id)>= 0)) { right--; } while (left < right && (strcmp(ps->student[left].id, ps->student[keyi].id)<= 0)) { left++; } Swap(&ps->student[left], &ps->student[right]); } int meeti = left; Swap(&ps->student[meeti], &ps->student[keyi]); QuickSort(ps, begin, meeti - 1); QuickSort(ps, meeti + 1, end); } int SeqListBinarySearch(SeqList* ps, char* findId) { int left = 0, right = ps->size - 1; while (left <= right) { int mid = left + (right - left) / 2; if (strcmp(ps->student[mid].id, findId) == 0) { return mid; break; } else if (strcmp(ps->student[mid].id, findId) > 0) { right = mid - 1; } else { left = mid + 1; } } return -1; } void SeqListDelete(SeqList* ps, int locate) { int begin = locate+1; while (begin <= ps->size-1) { ps->student[begin-1] = ps->student[begin]; begin++; } ps->size--; } void SeqListDestory(SeqList* ps) { free(ps->student); ps->student = NULL; ps->size = 0; ps->capacity = 0; }
