数据结构之静态顺序表的实现
静态顺序表
特点：
静态数据表的增改删查
//静态顺序表的增改删查
#include<stdio.h>
#include<assert.h>
#include<memory.h>
#include <stdlib.h>
typedef int DataType;//顺序表元素类型
#define MAX 100//顺序表的数组的大小
typedef struct SeqList
{
DataType arr[MAX];
int sz;//顺序表当前储存元素的个数
}Seqlist, *pSeqList;
//函数声明
void InitSeq(pSeqList pSeq);//初始化顺序表
void PrintfSeq(pSeqList pSeq);//打印顺序表内容
void PushBack(pSeqList pSeq, DataType x);//尾插
void PopBack(pSeqList pSeq);//尾删
void PushFront(pSeqList pSeq, DataType x);//头插
void PopFront(pSeqList pSeq);//头删
void Insert(pSeqList pSeq, int pos, DataType x);//在顺序表某位置插入某个特定元素
void Remove(pSeqList pSeq, DataType x);//删除在顺序表第一次出现的某个特定元素
void RemoveAll(pSeqList pSeq, DataType x);//删除顺序表中某个所有出现的元素
1、尾插：
代码图
效果图：
2、尾删
代码图 （由于篇幅原因只附主要代码图）
3.头插
4.头删
5.在顺序表某位置插入某个特定元素
6.删除在顺序表第一次出现的某个特定元素
7.删除顺序表中某个所有出现的元素
附上完整代码：
Seqlist.h
- //静态顺序表的增改删查
- #include<stdio.h>
#include<assert.h>
#include<memory.h>
#include <stdlib.h>
typedef int DataType;//顺序表元素类型
#define MAX 100//顺序表的数组的大小
typedef struct SeqList
{
DataType arr[MAX];
int sz;//顺序表当前储存元素的个数
}Seqlist, *pSeqList;
void InitSeq(pSeqList pSeq);//初始化顺序表
void PrintfSeq(pSeqList pSeq);//打印顺序表内容
void PushBack(pSeqList pSeq, DataType x);//尾插
void PopBack(pSeqList pSeq);//尾删
void PushFront(pSeqList pSeq, DataType x);//头插
void PopFront(pSeqList pSeq);//头删
void Insert(pSeqList pSeq, int pos, DataType x);//在顺序表某位置插入某个特定元素
void Remove(pSeqList pSeq, DataType x);//删除在顺序表第一次出现的某个特定元素
void RemoveAll(pSeqList pSeq, DataType x);//删除顺序表中某个所有出现的元素
void Sort(pSeqList pSeq);//排序--升序
void BinarySearch(pSeqList pSeq, DataType x);//二分查找
main.c
#include"SeqList.h"
void Test()
{
Seqlist s;//用结构体创建一个顺序表
InitSeq(&s);
PushBack(&s, 1);
PushBack(&s, 2);
PushBack(&s, 3);
PushBack(&s, 3);
PushBack(&s, 3);
PushBack(&s, 3);
PushBack(&s, 4);
PushBack(&s, 3);
PushBack(&s, 5);
PushBack(&s, 2);
PushBack(&s, 3);
PushBack(&s, 6);
printf("尾插：");
PrintfSeq(&s);
PushFront(&s, 9);
PushFront(&s, 8);
PushFront(&s, 7);
printf("头插三个数：");
PrintfSeq(&s);
PopBack(&s);
printf("尾删一个数：");
PrintfSeq(&s);
PopFront(&s);
printf("头删一个数：");
PrintfSeq(&s);
Insert(&s, 3, 99);
printf("给顺序表第三个位置删插入99：");
PrintfSeq(&s);Remove(&s, 2);
printf("删除顺序表中第一个出现的2：");
PrintfSeq(&s);RemoveAll(&s, 3);
printf("删除顺序表中所有的3：");
PrintfSeq(&s);Sort(&s);
printf("排序：");
PrintfSeq(&s);printf("查找6：");
BinarySearch(&s, 6);
}
int main()
{
Test();
system("pause");
}
test.c
#include"SeqList.h"
void InitSeq(pSeqList pSeq)//初始化顺序表
{
assert(pSeq);
memset(pSeq->arr, 0, sizeof(DataType)*MAX);
pSeq->sz = 0;
}
void PrintfSeq(pSeqList pSeq)//打印顺序表内容
{
int i = 0;
assert(pSeq);
if (pSeq->sz == 0)
{
printf("顺序表没有元素");
exit(EXIT_FAILURE);
}
for (i = 0; i<pSeq->sz; ++i)
{
printf("%d ", pSeq->arr[i]);
}
printf("\n");
}
void PushBack(pSeqList pSeq, DataType x)//尾插
{
assert(pSeq);
if (pSeq->sz == MAX)
{
printf("顺序表已满\n");
exit(EXIT_FAILURE);
}
pSeq->arr[pSeq->sz] = x;
++pSeq->sz;
}
void PopBack(pSeqList pSeq)//尾删
{
assert(pSeq);
if (pSeq->sz == 0)
{
printf("顺序表没有元素；不可删除\n");
exit(EXIT_FAILURE);
}
--pSeq->sz;
}
void PushFront(pSeqList pSeq, DataType x)//头插
{
int i = 0;
assert(pSeq);
if (pSeq->sz == MAX)
{
printf("顺序表已满\n");
exit(EXIT_FAILURE);
}
for (i = pSeq->sz; i>0; --i)
{
pSeq->arr[i] = pSeq->arr[i - 1];
}
pSeq->arr[0] = x;
++pSeq->sz;
}
void PopFront(pSeqList pSeq)//头删
{
int i = 0;
assert(pSeq);
if (pSeq->sz == 0)
{
printf("顺序表没有元素；不可删除\n");
exit(EXIT_FAILURE);
}
for (i = 0; i<pSeq->sz - 1; ++i)
{
pSeq->arr[i] = pSeq->arr[i + 1];
}
--pSeq->sz;
}
void Insert(pSeqList pSeq, int pos, DataType x)//在顺序表某位置插入某个特定元素
{
int i = 0;
assert(pSeq);
if (pSeq->sz == MAX)
{
printf("顺序表已满\n");
exit(EXIT_FAILURE);
}
if (pos >= MAX)
{
printf("插入位置不合适\n");
exit(EXIT_FAILURE);
}
for (i = pSeq->sz; i>pos; --i)
{
pSeq->arr[i] = pSeq->arr[i - 1];
}
pSeq->arr[pos] = x;
++pSeq->sz;
}
void Remove(pSeqList pSeq, DataType x)//删除在顺序表第一次出现的某个特定元素
{
int i = 0;
int j = 0;
assert(pSeq);
if (pSeq->sz == 0)
{
printf("顺序表为空；不可删除\n");
exit(EXIT_FAILURE);
}
for (i = 0; i < (pSeq->sz); ++i)
{
if (pSeq->arr[i] == x)
{
for (j = i; j<pSeq->sz - 1; ++j)
{
pSeq->arr[j] = pSeq->arr[j + 1];
}
--pSeq->sz;
break;
}
}
return;
}
void RemoveAll(pSeqList pSeq, DataType x)//删除顺序表中某个所有出现的元素
{
int i = 0;
int j = 0;
assert(pSeq);
if (pSeq->sz == 0)
{
printf("顺序表没有元素；不可删除\n");
exit(EXIT_FAILURE);
}
for (i = 0; i<pSeq->sz; ++i)
{
if (pSeq->arr[i] == x)
{
for (j = i; j<pSeq->sz - 1; ++j)
{
pSeq->arr[j] = pSeq->arr[j + 1];
}
--pSeq->sz;
i = i - 1;
}
}
return;
}
void Sort(pSeqList pSeq)//排序--升序
{
int i = 0;
int j = 0;
int mark = 0;
DataType tmp = 0;
assert(pSeq);
if (pSeq->sz == 0)
{
printf("顺序表没有元素,不用排序\n");
exit(EXIT_FAILURE);
}
for (j = 0; j<pSeq->sz - 1; ++j)//趟数
{
for (i = 0; i<pSeq->sz - 1 - j; ++i)//没趟比较次数
{
if (pSeq->arr[i]>pSeq->arr[i + 1])//交换
{
mark = 1;
tmp = pSeq->arr[i];
pSeq->arr[i] = pSeq->arr[i + 1];
pSeq->arr[i + 1] = tmp;
}
}
if (mark == 0)
break;
}
}
void BinarySearch(pSeqList pSeq, DataType x)//二分查找
{
int left = 0;
int right = pSeq->sz - 1;
int mid = 0;
assert(pSeq);
if (pSeq->sz == 0)
{
printf("顺序表没有元素,不用排序\n");
exit(EXIT_FAILURE);
}
Sort(pSeq);
while (left <= right)
{
mid = (left + right) / 2;
if (x>pSeq->arr[mid])
{
left = mid + 1;
}
if (x<pSeq->arr[mid])
{
right = mid - 1;
}
if (x == pSeq->arr[mid])
{
printf("该元素存在，且在顺序表的第%d位置\n", mid);
return;
}
}
printf("该元素不存在");
}
效果图：
顺序表最主要的问题就是要求长度是固定的，可以使用倍增-复制的办法来支持动态扩容，将顺序表变成“可变长度”的。