静态顺序表的一系列操作

时间：2022-03-02 23:30:40

自定义头文件部分：

#define _CRT_SECURE_NO_WARNINGS 1
#ifndef __SEQLIST_H__
#define __SEQLIST_H__

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define MAX_SIZE 1000//最大容量
typedef int DataType;
typedef struct SeqList
{
    DataType a[MAX_SIZE];
int sz;     // 记录有效元素的个数
}SeqList, *PSeqList;

void InitSeqList(PSeqList pSeqList);//初始化顺序表
void PushBack(PSeqList pSeqList, DataType data);//尾部插入数据
void PopBack(PSeqList pSeqList);//尾部删除数据
void PushFront(PSeqList pSeqList, DataType data);//头部插入数据
void PopFront(PSeqList pSeqList);//头部删除数据
void Insert(PSeqList pSeqList, int pos, DataType data);//向指定位置插入数据
void Erase(PSeqList pSeqList, int pos);//删除指定位置数据
int Find(PSeqList pSeqList, DataType data);//查找指定数据
void Remove(PSeqList PseqList, DataType data);//删除指定的一个数据
void RemoveAll(PSeqList pSeqList, DataType data);//删除所有相同的指定数据
void Empty(PSeqList pSeqList);//判断顺序表是否为空
void Print(PSeqList pSeqList);//打印顺序表中的数据
void BubbleSort(PSeqList pSeqList);//冒泡排序顺序表中数据
void SelectSort(PSeqList pSeqList);//选择排序顺序表中数据
int BinarySearch(PSeqList pSeqList,DataType data);//二分查找顺序表中指定的数据（数据有序）
enum seqlist
{
    EXIT,
    PUSHBACK,
    POPBACK,
    PUSHFRONT,
    POPFRONT,
    INSERT,
    ERASER,
    REMOVE,
    REMOVEALL,
    EMPTY,
    PRINT,
    BUBBLESORT,
    SELECTSORT,
    BINARYSEARCH
};

#endif

函数实现部分：

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"

void InitSeqList(PSeqList pSeqList)
{
    assert(pSeqList);
    pSeqList->sz = 0;
    memset(pSeqList->a, 0, MAX_SIZE*sizeof(DataType));
}
void PushBack(PSeqList pSeqList, DataType data)
{
    assert(pSeqList);
if (pSeqList->sz == MAX_SIZE)
    {
        printf("该顺序表已满，不能插入！\n");
    }
else
    {
        pSeqList->a[pSeqList->sz] = data;
        pSeqList->sz++;
        printf("尾部插入成功！\n");
    }
}
void PopBack(PSeqList pSeqList)
{
    assert(pSeqList);
if (pSeqList->sz == 0)
    {
        printf("顺序表已空，不能删除！\n");
    }
else
    {
        pSeqList->sz--;
        printf("尾部删除成功！\n");
    }
}
void PushFront(PSeqList pSeqList, DataType data)
{
    assert(pSeqList);
if (pSeqList->sz == MAX_SIZE)
    {
        printf("顺序表已满，不能插入!\n");
    }
else
    {
        int i = 0;
        for (i = pSeqList->sz-1; i>=0; i--)
        {
            pSeqList->a[i+1] = pSeqList->a[i];
        }
        pSeqList->a[0] = data;
        pSeqList->sz++;
        printf("头部插入成功！\n");
    }
}
void PopFront(PSeqList pSeqList)
{
    assert(pSeqList);
if (pSeqList->sz == 0)
    {
        printf("顺序表已空，不能删除！\n");
    }
else
    {
        int i = 0;
        for (i = 0; i < pSeqList->sz-1; i++)
        {
            pSeqList->a[i] = pSeqList->a[i+1];
        }
        pSeqList->sz--;
        printf("头部删除成功！\n");
    }
}
void Insert(PSeqList pSeqList, int pos, DataType data)//pos代表下标的位置.(0 - sz-1)
{
if (pSeqList->sz == MAX_SIZE)
    {
        printf("顺序表已满，不能进行插入！\n");
    }
else
    {
        int i = 0;
        assert(pSeqList);
        assert((pos >= 0) && (pos < pSeqList->sz));
        for (i = pSeqList->sz - 1; i >= pos; i--)
        {
            pSeqList->a[i + 1] = pSeqList->a[i];
        }
        pSeqList->a[pos] = data;
        pSeqList->sz++;
        printf("插入成功！\n");
    }
    }
void Erase(PSeqList pSeqList, int pos)
{
    assert(pSeqList);
    assert((pos >= 0) && (pos < pSeqList->sz));
if (pSeqList->sz == 0)
    {
        printf("顺序表已空,不能删除！\n");
    }
else
    {
        int i = 0;
        for (i = pos; i < pSeqList->sz - 1; i++)
        {
            pSeqList->a[i] = pSeqList->a[i + 1];
        }
        pSeqList->sz--;
        printf("删除成功！\n");
    }
}
int Find(PSeqList pSeqList, DataType data)
{
    assert(pSeqList);
    int i = 0;
    for (i = 0; i < pSeqList->sz; i++)
    {
if (pSeqList->a[i] == data)
            return i;
    }
    return -1;
}
void Remove(PSeqList pSeqList, DataType data)
{
    assert(pSeqList);
if (pSeqList->sz == 0)
    {
        printf("顺序表已空,不能进行移除操作！\n");
    }
else
    {
        int ret = Find(pSeqList, data);
if (ret == -1)
        {
            printf("要删除的数据不存在！\n");
        }
else
        {
            int i = 0;
            for (i = ret; i < pSeqList->sz - 1; i++)
            {
                pSeqList->a[i] = pSeqList->a[i + 1];
            }
        }
        pSeqList->sz--;
        printf("删除指定数据成功！\n");
    }
}
void RemoveAll(PSeqList pSeqList, DataType data)
{
    assert(pSeqList);
#if 0
if (pSeqList->sz == 0)
    {
        printf("顺序表已空！\n");
    }
else
    {
        int count = 0;
        int i = 0;
        for (i = 0; i < pSeqList->sz; i++)
        {
if (pSeqList->a[i] == data)
            {
                count++;
            }
            pSeqList->a[i] = pSeqList->a[i + count];
        }
        pSeqList->sz = pSeqList->sz - count;
        printf("删除所有指定的数据成功！\n");
    }
#endif

if (pSeqList->sz == 0)
    {
        printf("顺序表为空，不能进行删除！\n");
    }
else
    {
        int i = 0;
        int j = 0;
        while (i < pSeqList->sz)
        {
if (pSeqList->a[i] == data)
            {
                int pos = i;
                for (j = pos; j < pSeqList->sz - 1; j++)
                {
                    pSeqList->a[j] = pSeqList->a[j + 1];
                }
                pSeqList->sz--;
            }
else
            {
                i++;
            }
        }
    }
}
void Empty(PSeqList pSeqList)//判断顺序表是否为空
{
    assert(pSeqList);
if (pSeqList->sz == 0)
    {
        printf("顺序表为空！\n");
    }
}
void Print(PSeqList pSeqList)
{
    int i = 0;
    assert(pSeqList);
    for (i = 0; i < pSeqList->sz; i++)
    {
        printf("%d ", pSeqList->a[i]);
    }
    printf("\n");
}
void BubbleSort(PSeqList pSeqList)
{
if (pSeqList == 0)
    {
        printf("顺序表为空，不能进行排序！\n");
    }
else
    {
        int i = 0;
        int j = 0;
        for (i = 0; i < pSeqList->sz-1; i++)
        {
            for (j = 0; j < pSeqList->sz-1-i; j++)
            {
if (pSeqList->a[j]>pSeqList->a[j + 1])
                {
                    int tmp = pSeqList->a[j];
                    pSeqList->a[j] = pSeqList->a[j+1];
                    pSeqList->a[j+1] = tmp;
                }
            }
        }
        printf("排序成功！\n");
    }
}
void SelectSort(PSeqList pSeqList)
{
if (pSeqList == 0)
    {
        printf("顺序表为空，不能进行排序！\n");
    }
else
    {
        int i = 0;
        int j = 0;
        for (i = 0; i < pSeqList->sz - 1; i++)
        {
            int min = i;
            for (j = i + 1; j < pSeqList->sz; j++)
            {
if (pSeqList->a[i] > pSeqList->a[j])
                {
                    min = j;
                    int tmp = pSeqList->a[i];
                    pSeqList->a[i] = pSeqList->a[j];
                    pSeqList->a[j] = tmp;
                }
            }
        }
        printf("排序成功！\n");
    }
}
int BinarySearch(PSeqList pSeqList,DataType data)
{
    int left = 0;
    int right = pSeqList->sz - 1;
    while (left <= right)
    {
        int mid = left - ((left - right) >> 1);
if (pSeqList->a[mid] > data)
        {
            right = mid - 1;
        }
else if (pSeqList->a[mid] < data)
        {
            left = mid + 1;
        }
else
        {
            return mid;
        }
    }
    return -1;
}

主函数的测试部分：

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
#include <stdio.h>
#include <stdlib.h>
void meun()
{
printf("********** 0.不再对顺序表进行任何操作 **********\n");
printf("********** 1.从顺序表尾部进行插入 **************\n");
printf("********** 2.从顺序表尾部进行删除 **************\n");
printf("********** 3.从顺序表头部进行插入 **************\n");
printf("********** 4.从顺序表头部进行删除 **************\n");
printf("********** 5.从顺序表任意位置进行插入 **********\n");
printf("********** 6.从顺序表任意位置进行删除 **********\n");
printf("********** 7.从顺序表删除指定元素 **************\n");
printf("********** 8.从顺序表删除指定全部元素 **********\n");
printf("********** 9.清空顺序表 ************************\n");
printf("********** 10.打印顺序表 ************************\n");
printf("********** 11.冒泡排序顺序表 ************************\n");
printf("********** 12.选择排序顺序表 ************************\n");
printf("********** 13.二分查找顺序表 ************************\n");
}
int main()
{
    meun();
    SeqList seq;
    InitSeqList(&seq);
int input = 1;
while (input)
    {
printf("请输入要执行的操作：");
scanf("%d",&input);
switch (input)
        {
case PUSHBACK:
        {
            DataType num = 0;
printf("请输入要插入的数字：");
scanf("%d",&num);
            PushBack(&seq,num);
        }
break;
case POPBACK:
        {
            PopBack(&seq);
        }
break;
case PUSHFRONT:
        {
            DataType num = 0;
printf("请输入要插入的数字：");
scanf("%d", &num);
            PushFront(&seq, num);
        }
break;
case POPFRONT:
        {
            PopFront(&seq);
        }
break;
case INSERT:
        {
            DataType num = 0;
int pos = 0;
printf("请输入要插如的下标以及数字：");
scanf("%d%d",&num,&pos);
            Insert(&seq,num,pos);
        }
break;
case ERASER:
        {
int pos = 0;
printf("请输入要删除的数字的下标：");
scanf("%d",&pos);
            Erase(&seq, pos);
        }
break;
case REMOVE:
        {
            DataType num = 0;
printf("请输入要删除的数字：");
scanf("%d",&num);
            Remove(&seq, num); 
        }
break;
case REMOVEALL:
        {
            DataType num = 0;
printf("请输入要删除的数字：");
scanf("%d", &num);
            RemoveAll(&seq, num);
        }
break;
case EMPTY:
        {
            Empty(&seq);
        }
break;
case PRINT:
        {
            Print(&seq);
        }
break;
case BUBBLESORT:
        {
           BubbleSort(&seq);
        }
break;
case SELECTSORT:
        {
            SelectSort(&seq);
        }
break;
case BINARYSEARCH:
        {
int num = 0;
int ret = 0;
printf("请输入要查找的数字：");
scanf("%d",&num);           
            ret=BinarySearch(&seq, num);
if (ret != -1)
            {
printf("查找成功！\n");
            }
else
printf("没有找到！\n");
        }
break;
case EXIT:
        {
printf("结束对顺序表的操作！\n");
        }
break;
default:
break;
        }
    }
     system("pause"); 
return 0;
}
标签：

相关文章