静态顺序表接口的简单实现
程序员文章站
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;
}