ABC/实验六代码.txt

源.cpp
#include"标头.h"
int main()
{
    cout << "实验完成者:陈贤奇" << endl;
    cout << "-----------------------------------------"<<endl;
    int n, m, ID, i, j;
    Stulist L;
    InitList(L);
    cout << "输入要创建的学生人数:";
    cin >> n;
    CreatStu(n, L);
    cout << "-----------------------------------------" << endl;
    print(L);
    cout << "-----------------------------------------"<<endl;
    cout << "输入要插入的位置:";
    cin >> i;
    Insert(L,i);
    print(L);
    cout << "-----------------------------------------"<<endl;
    cout << "输入要删除的位置:";
    cin >> j;
    j = j - 1;
    Delete(L, j);
    print(L);
    cout << "-----------------------------------------"<<endl;
    cout << "当前表长:" << L.length << endl;
    cout << "-----------------------------------------" << endl;
    cout << "输入你需要的排序方式(0.按姓名;1.按学号):";
    cin >> m;
    if (m == 0)
    {
        Sortname(L);
        print(L);
    }
    else if (m == 1)
    {
        move1(L);
        SortID(L);
        move2(L);
        print(L);
    }
    else
    {
        cout << "输入错误";
        return ERROR;
    }
    cout << "-----------------------------------------"<<endl;
    cout << "输入你要查找的学号:";
    cin >> ID;
    if (FindID(L, ID) == 0)
    {
        cout << "查找失败,无该学生"<<endl;
    }
    else
        cout << L.elem[FindID(L, ID)].name << " " << L.elem[FindID(L, ID)].score<<endl;
    cout << "-----------------------------------------";
}

标头.h
#pragma once
#define OK 1
#define ERROR 0
#define MAXSIZE 100
#include<iostream>
#include<string.h>
using namespace std;
typedef struct student
{
    char name[20];
    int ID;
    int score;
}stu;
typedef struct
{
    stu* elem;
    int   length;
}Stulist;
int InitList(Stulist& L)//初始化
{
    L.elem = new stu[MAXSIZE];
    if (!L.elem)exit(ERROR);
    L.length = 0;
    return OK;
}
int CreatStu(int n, Stulist& L)
{
    int i;
    if (n >= MAXSIZE)
    {
        cout << "超过预设最大容量";
        return ERROR;
    }
    for (i = 0;i < n;i++)
    {
        cout << "输入第"<<i+1<<"个"<<"学生姓名:";
        cin >> L.elem[i].name;
        cout << "输入第" << i+1 << "个" << "学生学号:";
        cin >> L.elem[i].ID;
        cout << "输入第" << i+1 << "个" << "学生分数:";
        cin >> L.elem[i].score;
        L.length++;
    }
    return OK;
}
int print(Stulist L)
{
    int i;
    for (i = 0;i < L.length;i++)
    {
        cout << L.elem[i].name << " " << L.elem[i].ID << " " << L.elem[i].score << " " << endl;
    }
    return OK;
}
int Insert(Stulist& L,int i)
{
    if (L.length == MAXSIZE)
    {
        cout << "超过预设最大容量";
        return ERROR;
    }
    if (i<1 || i>L.length+1)
    {
        cout << "插入位置非法"<<endl;
        return ERROR;
    }
    int j;
    for (j = L.length;j>i-1;j--)
    {
        L.elem[j] = L.elem[j-1];
    }
    cout << "输入插入学生的姓名:";
    cin >> L.elem[i-1].name;
    cout << "输入插入学生的学号:";
    cin >> L.elem[i-1].ID;
    cout << "输入插入学生的成绩:";
    cin >> L.elem[i-1].score;
    cout << "-----------------------------------------" << endl;
    L.length++;
    return OK;
}
int Delete(Stulist& L, int i)
{
    if (i <= 0 || i >=L.length)
    {
        cout << "删除位置非法" << endl;
        return ERROR;
    }
    if (L.length == 0)
    {
        cout << "当前存放学生信息个数为0,无法删除"<<endl;
        return ERROR;
    }
    int j;
    for (j =i;j<L.length;j++)
    {
        L.elem[j-1] = L.elem[j];
    }
    L.length--;
    return OK;
}
int move1(Stulist& L)
{
    int i;
    for (i = L.length - 1;i >= 0;i--)
    {
        L.elem[i+1] = L.elem[i];
    }
    return OK;
}
int move2(Stulist& L)
{
    int i;
    for (i =0;i<L.length;i++)
    {
        L.elem[i] = L.elem[i+1];
    }
    return OK;
}
int Sortname(Stulist& L)//直接插入排序
{
    move1(L);
    int i,j;
    for (i = 2;i <= L.length;i++)
        if(strcmp(L.elem[i].name, L.elem[i-1].name)<0)
    {
            L.elem[0] = L.elem[i];
            L.elem[i]= L.elem[i-1];
            for (j = i - 2;strcmp(L.elem[0].name, L.elem[j].name)<0;j--)
            {
                L.elem[j + 1] = L.elem[j];
            }
            L.elem[j + 1] = L.elem[0];
    }
    move2(L);
    return OK;
}
int Patition(Stulist& L, int low, int high)
{
    //交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置
    //此时在它之前（后）的记录均不大于（小于）它
    L.elem[0] = L.elem[low];                //用子表的第一个记录作枢轴记录
    int pivotkey = L.elem[low].ID;      //枢轴记录关键字
    while (low < high) 
    {              //从表的两端向中间扫描
        while (low < high && L.elem[high].ID >= pivotkey)
            --high;
        L.elem[low] = L.elem[high];         //将比枢轴小的记录移动到低端
        while (low < high && L.elem[low].ID <= pivotkey)
            ++low;
        L.elem[high] = L.elem[low];         //将比枢轴大的记录移动到高端
    }
    L.elem[low] = L.elem[0];                //枢轴记录到位
    return low;                       //返回枢轴位置
}

void QSort(Stulist& L, int low, int high)
{
    //对顺序表L中的子序列L.r[low...high]做快速排序
    if (low < high) 
    {                          //长度大于等于1
        int pivotloc = Patition(L, low, high); //一分为二
        QSort(L, low, pivotloc - 1);           //对低子表递归排序
        QSort(L, pivotloc + 1, high);          //对高子表递归排序
    }
}
void SortID(Stulist& L)
{
    //对顺序表L做快速排序
    QSort(L, 1, L.length);
}
int FindID(Stulist L, int ID)
{
    int low = 1;
    int high = L.length;
    int mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (ID == L.elem[mid].ID)
            return mid;
        else if (ID < L.elem[mid].ID)
            high = mid - 1;
        else low = mid + 1;
    }
    return 0;
}