实验：顺序表的应用

一、实验目的

1．掌握如何将算法转换为程序； 2．熟悉顺序存储结构； 3．熟悉顺序表的操作； 4．熟悉顺序表的应用。

二、实验要求

1.程序要有注释，包括对总体功能、关键句、段的说明； 2.源程序必须调试通过，对每个输入的要求以及输出要有清晰的提示。程序要具有一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等。

三、实验内容

1．实验题目（1）完成顺序表的基本运算：初始化、显示、求长度、判空、判满、插入、删除、按位置取元素、按值查找等，并编写主函数测试算法。（2）)设计算法：将一个元素插入到有序的顺序表中，使顺序表仍有序，并编写主函数测试算法。

（3）设 A 和 B 两个顺序表，其元素按从小到大的顺序排列。编写一个算法将 A 和 B 的全部元素合并到有序顺序表 C 中，并编写主函数测试算法。提示：有序表的合并；有序表的产生，可以人为输入，也可以调用（2）的算法来实现。

2．数据结构的设计：所选数据结构为顺序表。 3．算法描述：（2）用循环给顺序表赋初值，将要插入的数据从前往后一个一个和原顺序表元素比较，当该数据比顺序表此该位置的值大，小于或等于原顺序表的后一个值时，记录该位置，然后将数据插入到该位置。（3）在 A，B 都没合并完的前提下，用 while 循环一个个比较 A 和 B 里边的元素值，谁小，就把谁放到 C 里，以此类推。

四、算法实现

头文件：table.h

cpp

#ifndef _TABLE_H_
#define _TABLE_H_
#include <stdio.h>
#include <stdlib.h>
#define Size 5

typedef struct Table{
    int * head;
    int length;
    int size;
}table;

table initTable();
int TableLength(table t);
int emptyTable(table t);
int fullTable(table t);
table addTable(table t,int elem,int add);
table insertTable(table t,int elem);
table mergeTable(table t1,table t2,table t3);
table delTable(table t,int add);
int selectTable(table t,int elem);
int getTable(table t,int add);
table amendTable(table t,int elem,int newElem);
void displayTable(table t);

#endif // TABLE_H

主函数：main.c

cpp

#include "table.h"

int main(){
    int i,add=0,elem=0;
    table t1=initTable();

    //初始化后赋值
    for (i=1; i<=Size; i++) {
        t1.head[i-1]=i;
        t1.length++;
    }
    printf("原顺序表：\n");
    displayTable(t1);
    printf("当前顺序表长度为：%d\n",TableLength(t1));
    if (fullTable(t1)){
        printf("当前顺序表已满\n");
    }
    printf("\n");

    //删除指定元素
    printf("请输入要删除的元素:");
    scanf("%d",&elem);
    t1=delTable(t1, elem);
    printf("删除%d元素后，顺序表为:",elem);
    displayTable(t1);
    printf("\n");

    //按位置插入元素
    printf("请输入要插入元素的位置和元素的值：");
    scanf("%d %d",&add,&elem);
    printf("在第%d的位置插入元素%d后，顺序表为:\n",add,elem);
    t1=addTable(t1, elem, add);
    displayTable(t1);
    printf("\n");

    //查找元素的位置
    printf("请输入要查找元素的值：");
    scanf("%d",&elem);
    printf("查找元素%d的位置为:\n",elem);
    add=selectTable(t1, elem);
    printf("%d\n",add);

    //修改元素的值
    printf("请输入要修改的元素：");
    scanf("%d",&elem);
    printf("请输入修改后的值：");
    scanf("%d",&add);
    printf("将元素%d改为%d:\n",elem,add);
    t1=amendTable(t1, elem, add);
    displayTable(t1);
    printf("\n");

    //按位置查找元素
    printf("请输入要查找元素的位置：\n");
    scanf("%d",&add);
    printf("位置%d的元素为：",add);
    printf("%d\n",getTable(t1,add));

    //有序顺序表的插入
    printf("有序顺序表如下\n");
    t1.length=0;
    for (i=1; i<=Size; i++) {
        t1.head[i-1]=i;
        t1.length++;
    }
    displayTable(t1);
    printf("请输入要插入的元素值：\n");
    scanf("%d",&elem);
    t1=insertTable(t1,elem);
    displayTable(t1);

    //有序顺序表的合并
    t1.length=0;
    for (i=1; i<=t1.size; i++) {
        t1.head[i-1]=i;
        t1.length++;
    }
    printf("顺序表A的值为：\n");
    displayTable(t1);//t1为A顺序表

    table t2=initTable();//t2为B顺序表
    for (i=t1.head[t1.size-1]+1; i<=t1.size+5; i++) {
        t2.head[i-t1.head[t1.size-1]-1]=i;
        t2.length++;
    }
    printf("顺序表B的值为：\n");
    displayTable(t2);
    table t3=initTable(); //t3用来存放合并后的顺序表
    t3=mergeTable(t1,t2,t3);
    printf("合并后的顺序表为：");
    displayTable(t3);
    return 0;
}

//初始化函数
table initTable(){
    table t;
    t.head=(int*)malloc(Size*sizeof(int));
    if (!t.head)
    {
        printf("初始化失败\n");
        exit(0);
    }
    t.length=0;
    t.size=Size;
    return t;
}

//求长度
int TableLength(table t){
    return t.length;
}

//判空函数
int emptyTable(table t){
    if (!t.length)
        return 1;
    return 0;
}

//判满
int fullTable(table t){
    int temp=0;
    if (t.length==t.size)
        temp=1;
    return temp;
}

//插入函数，其中，elem为插入的元素，add为插入到顺序表的位置
table addTable(table t,int elem,int add)
{
    //判断插入本身是否存在问题
    if (add>t.length+1||add<1) {
        printf("插入位置有问题\n");
        return t;
    }
    //判断是否需要申请内存空间
    if (fullTable(t)) {
        t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int));
        if (!t.head) {
            printf("存储分配失败\n");
            return t;
        }
        t.size++;
    }
    //后移操作
    for (int i=t.length-1; i>=add-1; i--) {
        t.head[i+1]=t.head[i];
    }
    //将所需插入元素，添加到顺序表的相应位置
    t.head[add-1]=elem;
    t.length++;
    return t;
}

//按顺序插入，找插入位置
table insertTable(table t,int elem){
    int i=0;
    while(i < t.length && elem >= t.head [i])//从小到大排列
    {
        i++;//注意i从0开始的 ，所以后面不用i - 1 ,这里的i即为下标
    }
    t=addTable(t,elem,++i);
    return t;
}

table mergeTable(table t1,table t2,table t3){
    int i=0,j=0,k=0;
    while(i<t1.length || j<t2.length){

        if(j == t2.length || i<t1.length && t1.head[i]<t2.head[j])

            t3.head[k++] = t1.head[i++];
        else
            t3.head[k++] = t2.head[j++];
    }
    t3.length = k;
    return t3;
}

table delTable(table t,int add){
    if (add>t.length || add<1) {
        printf("被删除元素的位置有误\n");
        return t;
    }
    //删除操作
    for (int i=add; i<t.length; i++) {
        t.head[i-1]=t.head[i];
    }
    t.length--;
    return t;
}

//按值查找函数，其中，elem表示要查找的数据元素的值
int selectTable(table t,int elem){
    for (int i=0; i<t.length; i++) {
        if (t.head[i]==elem) {
            return i+1;
        }
    }
    return -1;//如果查找失败，返回-1
}

//按位置取元素
int getTable(table t,int add){
    if (add>t.length || add<1) {
        printf("被查找元素的位置有误\n");
        return 0;
    }
    return t.head[add-1];
}

//更改函数，其中，elem为要更改的元素，newElem为新的数据元素
table amendTable(table t,int elem,int newElem){
    int add=selectTable(t, elem);
    t.head[add-1]=newElem;//由于返回的是元素在顺序表中的位置，所以-1就是该元素在数组中的下标
    return t;
}

void displayTable(table t){
    for (int i=0;i<t.length;i++) {
        printf("%d ",t.head[i]);
    }
    printf("\n");
}

五、实验运行结果

cpp

原顺序表：
1 2 3 4 5
当前顺序表长度为：5
当前顺序表已满

请输入要删除的元素:3
删除3元素后，顺序表为:1 2 4 5

请输入要插入元素的位置和元素的值：4
5
在第4的位置插入元素5后，顺序表为:
1 2 4 5 5

请输入要查找元素的值：5
查找元素5的位置为:
4
请输入要修改的元素：3
请输入修改后的值：4
将元素3改为4:
1 2 4 5 5

请输入要查找元素的位置：
3
位置3的元素为：4
有序顺序表如下
1 2 3 4 5
请输入要插入的元素值：
4
1 2 3 4 4 5
顺序表A的值为：
1 2 3 4 5 6
顺序表B的值为：
7 8 9 10 11
合并后的顺序表为：1 2 3 4 5 6 7 8 9 10 11

Process returned 0 (0x0)   execution time : 18.143 s
Press any key to continue.

顺序表的增删改查