顺序表的基本操作

发布时间: 更新时间: 总字数:2466 阅读时间:5m 作者: IP上海 分享 网址
专栏文章
  1. 顺序表的基本操作(当前)
  2. 链表
  3. C++ 单链表的基本操作
  4. 栈和队列的基本操作
  5. C++ 二叉树的基本操作
  6. 图的基本操作
  7. C++ 哈夫曼编码
  8. C++ 排序的基本操作
  9. C++ 双向链表的基本操作
  10. 顺序表的基本操作
  11. MFC中如何用ADO连接SQL Server 2005
  12. MFC使用ADO连接SQL Server数据库
  13. VC6 MFC中ClassView视图中无法显示某个类的问题
  14. rose生成C++源代码
  15. 解决<compilation debug="true" targetFramework="4.0"> 问题
  16. Cpp
  17. Cpp
  18. LLVM/Clang 介绍
  19. CMake 使用介绍

顺序表的基本操作。

顺序表的基本操作

编写一个完整的程序,实现顺序表的建立、插入、删除、输出等基本运算。

  1. 建立一个顺序表,含有n个数据元素。
  2. 输出顺序表及顺序表的长度。
  3. 在顺序表中删除值为x的结点或者删除给定位置i的结点。
  4. 将顺序表就地逆置,即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。
  5. 将顺序表按升序排序。
  6. 设顺序表中的数据元素递增有序,将x插入到顺序表的适当位置上,以保持该表的有序性。
  7. 将两个顺序有序表A和B合并为一个有序表C。
  8. 在主函数中设计一个简单的菜单,分别测试上述算法。

程序

#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define OVERFLOW -2
#define ERROR 0
typedef int ElemType;
typedef struct
{
    ElemType *elem;
    int length;
    int listsize;
} SqList;
int cmp(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

//创建一个空表
int InitList(SqList &L)
{
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); //分配空间

    if (!L.elem)
        return OVERFLOW;
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
}
//在创建的空表中插入数据
int ListInsert(SqList &L, int i, ElemType e)
{
    ElemType* newbase;
//ElemType* q;
    if (i < 0 ||
            i > L.length + 1)
        return ERROR;
    if (L.length >= L.listsize) //当前空间已满,增加新空间

    {
        newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));

        if (!newbase)
            return
                OVERFLOW;
        L.elem = newbase;
        L.listsize += LISTINCREMENT;

    }

    L.elem[i] = e;
//printf("%d ",L.elem[i]);
    L.length++;
    return OK;
}
//删除位置为i的节点
int ListDelete(SqList &L, int i)
{
    ElemType* p;
    ElemType* q;
    if (i < 0 ||
            i > L.length)
        return ERROR;
    p = &(L.elem[i - 1]);
//e=*p;
    q = L.elem + L.length - 1;
    for (++p; p <= q; p++)
        *(p - 1) = *p;
    L.length--;
    return OK;
}
//在顺序表中删除数据x
int DeleteX(SqList &L, int x)
{
    ElemType* p;
    int i;
    for (i = 0; i < L.length; i++)
        if (L.elem[i] == x)
        {
            break;
        }
    p = &L.elem[i];

//free(p);
    for (int
            j = i; j < L.length - 1; j++)
    {
        L.elem[j] = L.elem[j + 1];

    }
    L.length--;
    return OK;
}
//反转顺序表
int TurnArrond(SqList &L)//翻转顺序表
{
    ElemType* p;
    ElemType* q;
    int t;
    p = &(L.elem[0]);
    q = L.elem + L.length - 1;
    for (p; p < q; p++, q--)
    {
        t = *q;
        *q = *p;
        *p = t;
    }
    return OK;
}
//升序排列顺序表
int ABC(SqList &L)
{
    int a[10000];
    int i;
    for (i = 0; i < L.length; i++)
        a[i] = L.elem[i];
    qsort(a, L.length, sizeof(a[0]), cmp);

    for (i = 0; i < L.length; i++)
        L.elem[i] = a[i];
    return OK;
}
//把顺序表升序排列后插入元素e
int ListInsertABC(SqList &L, ElemType e)
{
    ElemType* newbase;
    int i, j;
    if (L.length + 1 >= L.listsize) //当前空间已满,增加新空间

    {
        newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));

        if (!newbase)
            return
                OVERFLOW;
        L.elem = newbase;
        L.listsize += LISTINCREMENT;

    }

    for (i = 0; i < L.length; i++)
        if (e < L.elem[i])

            break;

    for (j = L.length; j > i; j--)

    {
        L.elem[j] = L.elem[j - 1];

    }
    L.length++;
    L.elem[j] = e;
//printf("%d
    ",L.elem[i]);
    return OK;
}
//合并顺序表L,L1为L2
int MergeList(SqList L, SqList L1, SqList &L2)
{
    ElemType* pa;
    ElemType* pb;
    ElemType* pc;
    ElemType* pa_last;
    ElemType* pb_last;
    pa = L.elem;
    pb = L1.elem;
// L2.elem=pc;
    L2.listsize = L.listsize + L1.listsize;
    pc = L.elem = (ElemType*)malloc(L2.listsize *
                                    sizeof(ElemType));

    pa_last = L.elem + L.length - 1;
    pb_last = L1.elem + L1.length - 1;
    while (pa <= pa_last && pb <= pb_last)
    {
        if (*pa <= *pb)

            *pc++ = *pa++;

        else
            *pc++ = *pb++;

    }
    while (pa <= pa_last)
        *pc++ = *pa++;
    while (pb <= pb_last)
        *pc++ = *pb++;
    for (int
            i = 0; i < L2.length; i++)
        printf("%d ", L2.elem[i]);
    return OK;
}
//打印菜单
void printScreen()
{
//printf("1.建立一个顺序表,含有n个数据元素。\n");
    printf("1.输出顺序表L1及其长度\n");
    printf("2.删除给定位置i的结点\n");
    printf("3.在顺序表中删除值为x的结点\n");
    printf("4.逆置顺序表\n");
    printf("5.将顺序表按升序排序\n");
    printf("6.设顺序表中的数据元素递增有序,将x插入到顺序表的适当位置上,以保持该表的有序性\n");

    printf("7.将两个顺序有序表L和L1合并为一个有序表L2\n");
    printf("0.退出操作系统。\n");
    printf("请输入需要的操作序号:");
}
//输出顺序表L
void printSqList(SqList &L)
{
    int i;
    for (i = 0; i < L.length; i++)
        printf("%d ", L.elem[i]);
    printf("\n");
}
int main()
{
    SqList L, L1, L2;
    InitList(L);
    InitList(L1);
    InitList(L2);
    int n, e, muse, i, x;
    bool flag;
//建立第一个的顺序表
    printf("请输入第一个数据表的长度:");
    scanf("%d", &n);
    printf("请以次输入长度为%d的顺序表:", n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &e);

        ListInsert(L, i, e); //依次在第i个位置插入顺序表

    }
    printf("第一个顺序表的次序为:");
    printSqList(L);

//建立第二个顺序表
    printf("建立第二个顺序表,请输入要第二个建立数据表的长度:");
    scanf("%d", &n);
    printf("请以次输入长度为%d的顺序表:", n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &e);

        ListInsert(L1, i, e); //依次在第i个位置插入顺序表

    }
    printf("第二个顺序表的次序为:");
    printSqList(L1);

//打印菜单
    printScreen();
    scanf("%d", &muse);
    flag = true;
    while (1)
    {
        switch (muse)
        {
        case 0:
            flag = false;

            break;
        case 1:
            printf("顺序表的长度为:");

            printf("%d\n", L.length);

            break;
        case 2:
            printf("请输入要删除的节点:");

            scanf("%d", &i); //删除顺序表的节点

            if (ListDelete(L, i))

            {
                printf("删除成功!\n");

                printSqList(L);

            }
            else
                printf("删除失败!\n");

            break;
        case 3:
            printf("请输入要删除的节点x的值:");

            scanf("%d", &x);

            if (DeleteX(L, x))

            {
                printf("删除成功!\n顺序表为:");

                printSqList(L);

            }
            else
                printf("删除失败!\n");

            break;
        case 4:
            //逆序顺序表
            if (TurnArrond(L))

            {
                printf("逆序成功!\n");

                printf("顺序表的次序为:");

                printSqList(L);

            }
            else
                printf("逆序失败!\n");

            break;
        case 5:
            //顺序表升序排列

            if (ABC(L))

            {
                printf("顺序表升序排列成功!\n");

                printf("顺序表的次序为:");

                printSqList(L);

            }
            else
                printf("顺序表升序排列失败!\n");


            printf("请输入要插入的数据:");

            scanf("%d", &e);

            if (ListInsertABC(L, e))

            {
                printf("顺序插入成功!\n");

                printf("顺序表的次序为:");

                printSqList(L);

            }
            else
                printf("顺序插入失败!\n");

            break;
        case 6:
            ABC(L);
            printf("请输入要插入的数字x的值:");

            scanf("%d", &x);

            if (ListInsertABC(L, x))

            {
                printf("操作成功!\n");

                printf("顺序表的次序为:");

                printSqList(L);

            }
            else
                printf("操作失败!\n");
            break;
        case 7:
            if (MergeList(L, L1, L2))

            {
                printf("顺序表L,L1合并成功!\n");

                //printf("顺序表的次序为:");

                //printSqList(L2);

            }
            else
                printf("顺序表合并失败!\n");

            break;
        default:
            break;
        }
        if (!flag)
            break;
        printf("\n请输入你要的下一步操作序号:");

        scanf("%d", &muse);

    }

    if (L.elem)
        free(L.elem);
    if (L1.elem)
        free(L1.elem);
    if (L2.elem)
        free(L2.elem);

    return 0;
}
Home Archives Categories Tags Statistics
本文总阅读量 次 本站总访问量 次 本站总访客数