欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构线性表之顺序表的基本操作(C语言实现)(完美版)

程序员文章站 2024-03-20 14:29:22
...

//参考书是人民邮电出版社的数据结构(C语言版-第2版);

//由于书上伪代码不能直接编译运行;

//故博主使用自己学过C Primer Plus中的知识来实现代码;

//本程序是可移植性程序;

//能在Linux/Mac os/Windows下编译运行;

//若有不足之处请提出,博主会尽所能修改;

//若是对您有用的话请点赞或分享提供给它人;

//未经允许严禁抄袭以及转载;

//源代码奉上,希望能够对您有所启发;

//ArrayList.c

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAXSIZE 100

typedef int ElemType; //本程序使用的数据元素类型是最简单的整型元素;

typedef struct ARRAY
{
    ElemType *elem; //顺序表的首地址;
    int length;     //顺序表的总长度;
} ArrayList;

//1) 构造一个空的顺序表;
void Init_List(ArrayList *parr);
//2) 若顺序表已存在且非空表则销毁整个顺序表;
bool Destroy_List(ArrayList *parr);
//3) 若顺序表已存在且非空表则将其重置为空表;
bool Clear_List(ArrayList *parr);
//4) 若顺序表已存在则判断是否为空表;
bool List_Empty(ArrayList *parr);
//5) 若顺序表已存在则直接获取数据元素个数;
int List_Length(ArrayList *parr);
//6) 若顺序表已存在且非空表,位置满足1<=pos<=length,则用*val存取并返回第i个数据元素的值;
bool Get_Elem(ArrayList *parr, int pos, ElemType *val);
//7) 若顺序表已存在则返回第一个与val值相同的元素在表中的位置,若无相同元素则返回0;
int Locate_Elem(ArrayList *parr, ElemType val);
//8) 若顺序表已存在且非空表, val是表中数据元素且不是第一个则用*pre返回其前驱,若val在表中不存在则操作失败;
bool Prior_Elem(ArrayList *parr, ElemType val, ElemType *pre);
//9) 若顺序表已存在且非空表, val是表中数据元素且不是最后一个则用*next返回其后继,若val在表中不存在则操作失败;
bool Next_Elem(ArrayList *parr, ElemType val, ElemType *next);
//10) 若顺序表已存在且1<=pos=length+1则在第i个位置前插入新元素val,长度加1;
bool List_Insert(ArrayList *parr, int pos, ElemType val);
//11) 若顺序表已存在且非空表,位置满足1<=pos<=length则删除第i个数据元素,长度减1;
bool List_Delete(ArrayList *parr, int pos);
//12) 若顺序表已存在且非空表则遍历其中所有数据元素;
void Traverse_List(ArrayList *parr);
//13) 若顺序表已存在且非空表则使用选择排序来排序其中所有数据元素;
bool sort_array(ArrayList *parr);
//14) 显示主菜单;
int show_menu(void);
//15) 获取用户输入的第1个字符;
int get_first(void);
//16) 清空输入缓冲区;
void eatline(void);
//17) 获取用户输入的数据元素;
ElemType input(ElemType *ch);
//18) 获取用户输入的操作位置;
int input_pos(int *tp);
//19) 操作顺序表中的数据元素;
void choice(int ch, ArrayList *parr);
//前12个操作是书上的线性表的顺序实现,后面的操作是博主CLOVER~X的补充;

int main(void)
{
    int ch;
    ArrayList arr;

    Init_List(&arr);
    while ((ch = show_menu()) != 'q')
    {
        choice(ch, &arr);
    }
    free(arr.elem); //输入q时释放已分配的存储空间;
    puts("本程序完成!");

    return 0;
}

void Init_List(ArrayList *parr)
{
    parr->elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
    if (NULL == parr->elem)
    {
        fprintf(stderr, "动态内存分配失败!本程序退出!\n");
        exit(EXIT_FAILURE);
    }
    parr->length = 0;
    return;
}

bool Destroy_List(ArrayList *parr)
{
    if (parr->elem != NULL)
    {
        free(parr->elem);
        return true;
    }
    return false;
}

bool Clear_List(ArrayList *parr)
{
    if (!List_Empty(parr))
    {
        parr->length = 0;
        return true;
    }
    return false;
}

bool List_Empty(ArrayList *parr)
{
    return 0 == parr->length ? true : false;
}

int List_Length(ArrayList *parr)
{
    return parr->length;
}

bool Get_Elem(ArrayList *parr, int pos, ElemType *val)
{
    if (List_Empty(parr))
    {
        printf("此顺序表为空表!无法获取数据!\n");
        return false;
    }
    if ((pos < 1) || (pos > parr->length))
    {
        printf("您输入的位置有误!获取数据失败!\n");
        return false;
    }
    *val = parr->elem[pos - 1];
    return true;
}

int Locate_Elem(ArrayList *parr, ElemType val)
{
    int i;

    if (List_Empty(parr))
    {
        printf("此顺序表为空表!查找失败!\n");
        return 0;
    }
    for (i = 0; i < parr->length; i++)
    {
        if (parr->elem[i] == val)
        {
            return i + 1;
        }
    }
    return 0;
}

bool Prior_Elem(ArrayList *parr, ElemType val, ElemType *pre)
{
    int i;

    if (List_Empty(parr))
    {
        printf("此顺序表为空表!无法查找前驱元素!\n");
        return false;
    }
    for (i = 0; i < parr->length; i++)
    {
        if (val == parr->elem[i])
        {
            break;
        }
    }
    if (0 == i)
    {
        printf("%d是顺序表第一个数据元素!无前驱元素!\n");
        return false;
    }
    if (parr->length == i)
    {
        printf("数据元素%d不在此顺序表中!\n", val);
        return false;
    }
    *pre = parr->elem[i - 1];
    return true;
}

bool Next_Elem(ArrayList *parr, ElemType val, ElemType *next)
{
    int i;

    if (List_Empty(parr))
    {
        printf("此顺序表为空表!无法查找后继元素!\n");
        return false;
    }
    for (i = 0; i < parr->length; i++)
    {
        if (val == parr->elem[i])
        {
            break;
        }
    }
    if (parr->length - 1 == i)
    {
        printf("%d是顺序表最后一个数据元素!无后继元素!\n", val);
        return false;
    }
    if (parr->length == i)
    {
        printf("数据元素%d不在此顺序表中!\n", val);
        return false;
    }
    *next = parr->elem[i + 1];
    return true;
}

bool List_Insert(ArrayList *parr, int pos, ElemType val)
{
    int i;

    if (MAXSIZE == parr->length)
    {
        printf("此顺序表存储空间不足!插入失败!\n");
        return false;
    }
    if ((pos < 1) || (pos > parr->length + 1))
    {
        printf("您输入的位置不合理!插入失败!\n");
        return false;
    }
    for (i = parr->length - 1; i >= pos - 1; i--)
    {
        parr->elem[i + 1] = parr->elem[i];
    }
    parr->elem[pos - 1] = val;
    ++parr->length;
    return true;
}

bool List_Delete(ArrayList *parr, int pos)
{
    int i;

    if (List_Empty(parr))
    {
        printf("此顺序表为空表!删除失败!\n");
        return false;
    }
    if ((pos < 1) || (pos > parr->length))
    {
        printf("您输入的位置不合理!删除失败!\n");
        return false;
    }
    for (i = pos; i < parr->length; i++)
    {
        parr->elem[i - 1] = parr->elem[i];
    }
    --parr->length;
    return true;
}

void Traverse_List(ArrayList *parr)
{
    int i;

    if (List_Empty(parr))
    {
        printf("此顺序表为空表!无法进行遍历!\n");
        return;
    }
    else
    {
        printf("此顺序表中%d个数据元素是:\n", parr->length);
        for (i = 0; i < parr->length; i++)
        {
            printf("%-8d", parr->elem[i]);
            if (0 == (i + 1) % 10)
            {
                putchar('\n');
            }
        }
    }
    return;
}

bool sort_array(ArrayList *parr)
{
    int i, j;
    ElemType t;

    if (List_Empty(parr))
    {
        printf("此顺序表为空表!无法排序!\n");
        return false;
    }
    for (i = 0; i < parr->length - 1; i++)
    {
        for (j = i + 1; j < parr->length; j++)
        {
            if (parr->elem[i] > parr->elem[j])
            {
                t = parr->elem[i];
                parr->elem[i] = parr->elem[j];
                parr->elem[j] = t;
            }
        }
    }
    return true;
}

int show_menu(void)
{
    int ch;

    puts("========================================");
    puts("a) 销毁顺序表");
    puts("b) 清空顺序表");
    puts("c) 判断顺序表是否为空");
    puts("d) 查看顺序表长度");
    puts("e) 获取顺序表中的指定位置的数据");
    puts("f) 查找用户输入的数据在此顺序表中是否存在");
    puts("g) 查看顺序表中指定位置的前驱元素");
    puts("h) 查看顺序表中指定位置的后继元素");
    puts("i) 在指定位置插入新的数据元素");
    puts("j) 删除指定位置的数据元素");
    puts("k) 对当前顺序表进行遍历");
    puts("m) 对当前线性表进行排序(选择排序)");
    puts("q) 退出本程序");
    puts("========================================");
    printf("请您输入选择:");
    ch = get_first();
    while (strchr("abcdefghijkmq", ch) == NULL)
    {
        printf("您的输入无效!请重新输入:");
        ch = get_first();
    }
    return ch;
}

int get_first(void)
{
    int ch;

    do
    {
        ch = tolower(getchar());
    } while (isspace(ch));
    eatline();

    return ch;
}

void eatline(void)
{
    while (getchar() != '\n')
        continue;
    return;
}

ElemType input(ElemType *ch)
{
    printf("请您输入一个数据元素:");
    while (scanf("%d", ch) != 1)
    {
        eatline();
        printf("数据无效!请重新输入:");
    }
    eatline();
    return *ch;
}

int input_pos(int *tp)
{
    printf("请您输入一个需要操作的位置:");
    while (scanf("%d", tp) != 1)
    {
        eatline();
        printf("数据无效!请重新输入:");
    }
    eatline();
    return *tp;
}

void choice(int ch, ArrayList *parr)
{
    int pos;
    ElemType val, pre, next;

    switch (ch)
    {
    case 'a':
    {
        if (Destroy_List(parr))
        {
            printf("销毁顺序表成功!退出本程序!\n");
            exit(EXIT_SUCCESS);
        }
        else
        {
            printf("顺序表是空表!无法销毁!\n");
        }
        break;
    }
    case 'b':
    {
        if (Clear_List(parr))
        {
            printf("清空顺序表成功!\n");
        }
        else
        {
            printf("顺序表是空表!无法清空!\n");
        }
        break;
    }
    case 'c':
    {
        if (List_Empty(parr))
        {
            printf("顺序表是空表!\n");
        }
        else
        {
            printf("顺序表不是空表!\n");
        }
        break;
    }
    case 'd':
    {
        printf("顺序表中元素个数:%d个\n", List_Length(parr));
        break;
    }
    case 'e':
    {
        if (Get_Elem(parr, input_pos(&pos), &val))
        {
            printf("顺序表中第%d个数据元素是%d\n", pos, val);
        }
        break;
    }
    case 'f':
    {
        pos = Locate_Elem(parr, input(&val));
        if (pos != 0)
        {
            printf("%d是顺序表中是第%d个数据元素", val, pos);
        }
        else
        {
            printf("数据元素%d不在此顺序表中!\n", val);
        }
        break;
    }
    case 'g':
    {
        if (Prior_Elem(parr, input(&val), &pre))
        {
            printf("第%d个数据元素的前驱元素是%d\n", val, pre);
        }
        break;
    }
    case 'h':
    {
        if (Next_Elem(parr, input(&val), &next))
        {
            printf("第%d个数据元素的后继元素是%d\n", val, next);
        }
        break;
    }
    case 'i':
    {
        if (List_Insert(parr, input_pos(&pos), input(&val)))
        {
            printf("在第%d个位置插入数据元素%d成功!\n", pos, val);
        }
        break;
    }
    case 'j':
    {
        if (List_Delete(parr, input_pos(&pos)))
        {
            printf("删除第%d个数据元素成功!\n", pos);
        }
        break;
    }
    case 'k':
    {
        Traverse_List(parr);
        break;
    }
    case 'm':
    {
        if (sort_array(parr))
        {
            printf("顺序表排序成功!\n");
        }
        break;
    }
    }
    printf("\n\n\n\n\n\n\n\n\n\n\n\n");
    return;
}

//-------------

//----------------------------2020年5月4日 -------------------------------