一、实验内容

设计一个程序，使其用顺序表建立一个学生的成绩表，并能实现创建录入，存储，按序号查找，遍历，计算平均成绩，及格率，查找最高分等功能。

二、实验程序

/******************************************************************
> File Name : 顺序表的简单应用程序
> Author : foreverlong
> Mail : admin@foreverlong.cn
> Website : www.foreverlong.cn
> Created Time : 2019-04-02 21:00
******************************************************************/

#include 
#include "stdlib.h"
#include 
#include "ctype.h"
#include  //引入头文件stdbool.h来使用bool类型
#include
using namespace std;
#define Null  0
#define MaxSize 100 
typedef int ElemType;   
typedef  struct {
    ElemType  *list;    
    int  size;      
    int maxsize;        
} SqList;

void init_sq(SqList &L);
int againMalloc(SqList &L);
void traverse(SqList L);
int delete_sq(SqList &L, int i, ElemType &e);
int CreateList(SqList &L);
int insert_sq(SqList &L, int i, ElemType e);
void find(SqList L, ElemType a);
int main() {
    SqList L;
    char cmd;
    int i;
    int f;
    ElemType e;
    init_sq(L);
    do {
        do {
            system("cls");
            printf("\n\tc,C......创建顺序表");
            printf("\n\ti,I .....数据插入");
            printf("\n\td,D......数据删除");
            printf("\n\ts,S......数据显示");
            printf("\n\tf,F......数据查找");
            printf("\n\tq,Q......退出\n\t请选择:");
            cmd = getchar();
        } while ((toupper(cmd) != 'D') && (toupper(cmd) != 'Q') && (toupper(cmd) != 'I') && (toupper(cmd) != 'C') && (toupper(cmd) != 'S') && (toupper(cmd) != 'F'));
        switch (cmd) {
        case 'c':
        case 'C':CreateList(L);
            break;
        case 'i':
        case 'I':printf("\n请输入插入的数据:");
            scanf("%d", &e);
            printf("\n请输入数据的插入位置:");
            printf("\n(1--%d)\n", (L.size + 1));
            scanf("%d", &i);
            insert_sq(L, i, e);
            traverse(L);
            _getch();
            break;
        case 'd':
        case 'D':if (L.size == 0) printf("\n顺序表为空，无法进行删除操作!\n");
                 else {
            printf("\n请输入删除数据的位置:\n");
            printf("\n(1---%d):\n", L.size);
            scanf("%d", &i);
            delete_sq(L, i, e);
            traverse(L);
        }
                 _getch();
                 break;
        case 's':
        case 'S':if (L.size == 0) printf("\n顺序表为空!\n");
                 else           traverse(L);
            _getch();
            break;
        case 'f':
        case 'F':if (L.size == 0) printf("\n顺序表为空，无法进行查找操作!\n");
                 else
                {
                    printf("输入想要查找的数:");
                    scanf("%d",&f);
                    find(L, f);
                }
                 _getch();
        default:  break;
        }
    } while ((cmd != 'q') && (cmd != 'Q'));
}

void init_sq(SqList &L) {
    L.list = (ElemType *)malloc(MaxSize * sizeof(ElemType));
    L.size = 0;
    L.maxsize = MaxSize;
}

int againMalloc(SqList &L) {
    ElemType *newbase = (ElemType *)realloc(L.list, (L.maxsize * 2) * sizeof(ElemType));
    if (!newbase) {
        printf("存储空间分配失败！");
        _getch();
        return 0;
    }
    L.list = newbase;
    L.maxsize = 2 * L.maxsize;
    return 1;
}

int insert_sq(SqList &L, int i, ElemType e) {
    int j;
    if ((i < 1) || (i > L.size + 1)) {
        printf("插入位置不合法!");
        _getch();
        return Null;
    }
    if (L.size >= L.maxsize) {
        j = againMalloc(L);
        if (!j) return -1;
    }
    for (j = L.size; j >= i; j--)    L.list[j] = L.list[j - 1];
    L.list[i - 1] = e;
    ++L.size;
    return 1;
}

void traverse(SqList L) {
    for (int i = 0; i < L.size; i++) {
        printf("L.list[%d]=%d; ", i, L.list[i]);
    }
    printf("\n");
}

int delete_sq(SqList &L, int i, ElemType &e) {
    if (i<1 || i>L.size)  return 0;
    e = L.list[i - 1];
    for (int j = i; j < L.size; j++) {
        L.list[j - 1] = L.list[j];
    }
    --L.size;
    return 1;
}

int CreateList(SqList &L) {
    int n, i, j;
    int mydata;
    printf("\n请输入数据元素个数:\n");
    scanf("%d", &n);
    if (n > L.maxsize) {
        j = againMalloc(L);
        if (!j) return -1;
    }
    for (i = 0; i < n; i++) {
        printf("list[%d]=", i + 1);
        scanf("%d", &mydata);
        L.list[i] = mydata;
    }
    L.size = n;
    printf("\n按任意键继续!\n");
    _getch();
    return 1;
} 

void find(SqList L, ElemType a)
{
    bool b = false;
    for (int i = 0; i < L.size; i++)
    {
        if (L.list[i] == a)
        {
            printf("L.list[%d]=", i);
            b = true;
        }
    }
    if (b)
    {
        cout << a;
    }
    else
    {
        cout << "莫得啊 兄dei!";
    }
}

三、测试结果

四、顺序存储结构和链式存储结构的比较

1. 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
   • 优点：存储密度大（＝1），存储空间利用率高。
   • 缺点：插入或删除元素时不方便。
2. 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
   • 优点：插入或删除元素时很方便，使用灵活。
   • 缺点：存储密度小（<1），存储空间利用率低。

五、思考题

如何修改“有序表合并程序”，实现两个有序表按递减顺序进行合并的功能？

答：将函数MergeList中ab互换位置即可。如下：

   void MergeList(SqList La,SqList Lb,SqList &Lc) {
    int i=1,j=1,k=0;
    int a,b;
    init_sq(Lc);
    while(i<=length_sq(La)&&j<=length_sq(Lb)) {
        get(La,i,a);
        get(Lb,j,b);
        if(a>b) {
            insert_sq(Lc,++k,a);
            i++;
        }
        else if(a

如何修改“多项式求和运算程序”，确保两个多项式的创建能够按指数递增顺序进行排列？[提示：参考“有序表合并程序”主函数中的数据输入部分]

答：La和Lb在多项式录入之后的时候入对前后结点指数大小判断，如非递增则互换顺序。

如何实现两个多项式的相减运算？

答：分别计算两个多项式的和，再去计算两个多项式的和的差。

六、实验体会

通过本次实验了解了顺序表的各种功能及应用。增长了这种算法相关程序的编写。