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

静态顺序表接口的简单实现

程序员文章站 2024-03-20 13:55:40
...

此次我们对于顺序表的概念不多过多陈述(想了解详情请点击这里)此次我们通过对顺序表几个简单接口代码的注释,让我们对顺序表有直观的感受。

Seqlist.h

#ifndef __SEQLIST_H__
#define __SEQLIST_H__
#include <stdio.h>
#include <string.h>
#include <assert.h>

#define MAX 100
typedef int DataType; //int重命名 方便之后存储类型的改变

typedef struct Seqlist 
{
    DataType Data[MAX]; 
    int sz; //有效个数
}Seqlist, *pSeqlist;  

void InitSeqlist(pSeqlist ps);  //初始化
void PushBack(pSeqlist ps, DataType d); //尾部插入元素
void PrintSeqist(const pSeqlist ps); //打印
void PopBack(pSeqlist ps);  //尾部删除元素
void PushFront(pSeqlist ps, DataType d); //头部插入元素
void PopFrint(pSeqlist ps); //头部删除元素
void Insert(pSeqlist ps, int pos, DataType d); //在pos前面插入目标元素
int Find(pSeqlist ps, DataType d); //查找目标元素并返回下标
void Remove(pSeqlist ps, DataType d); //删除目标元素
void RemoveAll(pSeqlist ps, DataType d); //删除所有元素d
void ReverseSeqlist(pSeqlist ps); //逆序
void SortSeqlist(pSeqlist ps); //排序
int BinarySearch(pSeqlist ps, DataType d); //二分查找目标元素

#endif

Seqlist.c

#include "Seqlist.h"

void InitSeqlist(pSeqlist ps) //初始化
{
    assert(ps);
    ps->sz = 0;
    memset(ps->Data, 0, sizeof(ps->Data));//把Data的内容按字节的方式初始化为0
}

void PushBack(pSeqlist ps, DataType d)//尾部插入元素
{
    assert(ps);
    if (ps->sz == MAX)
    {
        return;
    }
    ps->Data[ps->sz] = d;
    ps->sz += 1;
}

void PrintSeqist(const pSeqlist ps) //打印
{
    int i = 0;
    assert(ps);
    for (i=0; i<ps->sz; i++)
    {
        printf("%d ", ps->Data[i]);
    }
    printf("\n");
}

void PopBack(pSeqlist ps) //删除
{
    assert(ps);
    if (ps->sz == 0)
    {
        return;
    }
    ps->sz--;
}

void PushFront(pSeqlist ps, DataType d)//头部插入元素
{
    int i = 0;
    assert(ps);
    if (ps->sz == MAX)
    {
        return;
    }   
    for (i=ps->sz; i>0; i--)
    {
        ps->Data[i] = ps->Data[i-1]; 
    }
    ps->Data[0] = d;
    ps->sz++;
}

void PopFrint(pSeqlist ps)//删除第一个元素
{
    assert(ps);

    if(ps->sz != 0)
    {
        int i = 0;
        for(i=0; i<ps->sz; i++)
        {
            ps->Data[i] = ps->Data[i+1];
        }
    }
    ps->sz--;
}

void Insert(pSeqlist ps, int pos, DataType d)//在pos前插入元素
{
    int i = 0;
    assert(ps);
    if (ps->sz == MAX)
    {
        return;
    }
    for(i=ps->sz; i>pos; i--)
    {
        ps->Data[i]=ps->Data[i-1];
    }
    ps->Data[pos] = d;
    ps->sz++;
} 

int Find(pSeqlist ps, DataType d) //查找目标元素并返回下标
{
    int i = 0;
    assert(ps);
    for(i=0; i<ps->sz; i++)
    {
        if (ps->Data[i] == d)
        {
            return i;
        }
    }
    return -1;
}

void Remove(pSeqlist ps, DataType d) //删除目标元素
{
    int ret = 0;
    int i = 0;
    assert(ps);
    if(ps->sz == 0)
        return;
    //1.查找
    ret = Find(ps, d);
    if(ret != -1)//2.删除
    {       
        for(i=ret; i<ps->sz-1; i++)
        {
            ps->Data[i] = ps->Data[i+1];
        }
        ps->sz--;
    }
}

void RemoveAll(pSeqlist ps,DataType d) //删除所有元素d   
{
    int i = 0;
    assert(ps);
    while(1)
    {
        int ret = 0;
        ret = Find(ps, d);
        if (ret != -1)
        {
            Remove(ps,d);
            i++;
        }
        else
        {
            return;
        }
    }
    ps->sz-=i;
}

void ReverseSeqlist(pSeqlist ps) //逆序
{
    int left = 0;
    int right = ps->sz-1;
    assert(ps);
    while (left<right)
    {
        DataType tmp = ps->Data[left];
        ps->Data[left] = ps->Data[right];
        ps->Data[right] = tmp;
        left++;
        right--;
    }
}

void SortSeqlist(pSeqlist ps) //排序
{
    int i = 0;
    int j = 0;
    assert(ps);
    for(i=0; i<ps->sz; i++)
    {
        for (j=0; j<ps->sz-i-1; j++)
        {
            if(ps->Data[j]>ps->Data[j+1])
            {
                DataType tmp = ps->Data[j];
                ps->Data[j] = ps->Data[j+1];
                ps->Data[j+1] = tmp;
            }
        }
    }
}

int BinarySearch(pSeqlist ps, DataType d) //二分查找目标元素
{
    int left = 0;
    int right = ps->sz-1;
    assert(ps);
    SortSeqlist(ps);
    while (left <= right)
    {
        int mid = left +((right-left)>>1);
        if (d > ps->Data[mid])
        {
            left = mid+1;
        }
        else if(d < ps->Data[mid])
        {
            right = mid-1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

test.c

#include "Seqlist.h"

void test() //我们通过和PrintSeqlist函数的不同组合对目标接口进行验证
{
    int pos = 0;
    Seqlist mylist;
    InitSeqlist(&mylist);//初始化,结构体传参时最好传地址,效率较高
    PushBack(&mylist, 1);
    PushBack(&mylist, 1);
    PushBack(&mylist, 3);
    PushBack(&mylist, 4);
    PushBack(&mylist, 5);
    PrintSeqist(&mylist);
    RemoveAll(&mylist, 1);
    PrintSeqist(&mylist);
    Remove(&mylist, 3);
    PrintSeqist(&mylist);
    ReverseSeqlist(&mylist);
    PrintSeqist(&mylist);
    SortSeqlist(&mylist);
    PrintSeqist(&mylist);
    PopFrint(&mylist);
    PrintSeqist(&mylist);
    Insert(&mylist, 1, 5);
    PrintSeqist(&mylist);
    pos =Find(&mylist,3);
    if(pos != -1)
        Insert(&mylist, pos, 5);
    PrintSeqist(&mylist);
}

int main()//测试部分可根据要验证的函数进行设计
{
    test();
    return 0;
}