数据结构_数据结构_数据结构_数据结构_初级_顺序表_静态
代码实现顺序表的操作函数
// 值类型
typedef int DataType;
typedef struct SeqList {
DataType data; // 值
int size; // 数量
} SeqList;
// 初始化
void SeqListInit(SeqList *pSL);
// 尾部插入
void SeqListPushBack(SeqList *pSL, DataType data);
// 头部插入
void SeqListPushFront(SeqList *pSL, DataType data);
// 尾部删除
void SeqListPopBack(SeqList *pSL);
// 头部删除
void SeqListPopFront(SeqList *pSL);
// 按下标插入,pos 的范围是 [0, size]
void SeqListInsert(SeqList *pSL, int pos, DataType data);
// 按下标删除,pos 的范围是 [0, size)
void SeqListErase(SeqList *pSL, int pos);
// 按值删除,只删遇到的第一个
void SeqListRemove(SeqList *pSL, DataType data);
// 按值删除,删除所有的
void SeqListRemoveAll(SeqList *pSL, DataType data);
// 清空
void SeqListClear(SeqList *pSL);
// 按值查找,返回第一个找到的下标,如果没找到,返回 -1
int SeqListFind(SeqList *pSL, DataType data);
// 判断是否为空,1 表示空, 0 表示不空
int SeqListEmpty(SeqList *pSL);
// 返回数量
int SeqListSize(SeqList *pSL);
// 销毁
void SeqListDestroy(SeqList *pSL);
test.h
#pragma once
#include<stdio.h>
#include<windows.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
typedef int DataType;
#define MAX_SIZE (100)
typedef struct SeqList {
DataType array[MAX_SIZE]; // 存数据的空间
int size; // 1) 有效数据有多少个 2) 当前可用的数组下标
} SeqList;
// 初始化
void SeqListInit(SeqList *pSL);
// 销毁
void SeqListDestroy(SeqList *pSL);
// 增删改查
// 增
// 尾插
void SeqListPushBack(SeqList *pSL, DataType data);
// 头插
void SeqListPushFront(SeqList *pSL, DataType data);
// 根据下标插入
void SeqListInsert(SeqList *pSL, int pos, DataType data);
// 删
// 尾删
void SeqListPopBack(SeqList *pSL);
// 头删
void SeqListPopFront(SeqList *pSL);
// 根据下标删除
void SeqListErase(SeqList *pSL, int pos);
// 根据数据删除,只删除遇到的第一个
void SeqListRemove(SeqList *pSL, DataType data);
// 根据数据删除,删除所有遇到的
void SeqListRemoveAll(SeqList *pSL, DataType data);
// 根据下标更新
void SeqListUpdate(SeqList *pSL, int pos, DataType data);
// 查询
// 返回遇到的第一个下标,如果没有遇到,返回 -1
int SeqListFind(SeqList *pSL, DataType data);
//输出打印
void SeqListprint(SeqList *pSL);
void SeqListInit(SeqList *pSL)
{
//内容初始化
//size=0
assert(pSL != NULL);
memset(pSL->array, 0, MAX_SIZE*sizeof(DataType));
pSL->size = 0;
}
void SeqListDestroy(SeqList *pSL)
{
assert(pSL != NULL);
pSL->size = 0;
}
// 尾插
void SeqListPushBack(SeqList *pSL, DataType data)
{
assert(pSL != NULL);
assert(pSL->size < MAX_SIZE);
pSL->array[pSL->size] = data;
pSL->size++;
}
//头插
void SeqListPushFront(SeqList *pSL, DataType data)
{
assert(pSL != NULL);
assert(pSL->size < MAX_SIZE);
//将已有数据往后搬移
//以条件写循环
#if 0
//1.1以要搬移的数做循环的指示
int pose;
for (pose = pSL->size-1; pose >= 0; pose--)
{
pSL->array[pose + 1] = pSL->array[pose];
}
#endif
//#if 0
//以要搬到的位置做循环指示
int space;
for (space = pSL->size; space > 0; space--)
{
pSL->array[space] = pSL->array[space-1];
}
//#endif
/*int i = 0;
for (i = 0; i < pSL->size; i++)
{
pSL->array[pSL->size - i] =pSL->array[pSL->size - 1 - i];
}*/
pSL->array[0] = data;
pSL->size++;
}
//根据下标插入
void SeqListInsert(SeqList *pSL, int pos, DataType data)
{
assert(pSL!=NULL);
assert(pSL->size < MAX_SIZE);
assert(pos>0 && pos < pSL->size);
//把[pose,size)数据往后搬移一个(从后往前)
int space;
for (space = pSL->size; space>pos; space--)
{
pSL->array[space] = pSL->array[space-1];
}
pSL->array[pos] = data;
pSL->size++;
}
// 删
// 尾删
void SeqListPopBack(SeqList *pSL)
{
assert(pSL != NULL);
assert(pSL->size > 0);
pSL->size--;
}
// 头删
void SeqListPopFront(SeqList *pSL)
{
assert(pSL != NULL);
assert(pSL->size > 0);
//把 [1, pSL->size) 的数据往前搬移一格
int pos;
for (pos = 1; pos< pSL->size; pos++)
{
pSL->array[pos-1] = pSL->array[pos];
}
pSL->size--;
}
// 根据下标删除
void SeqListErase(SeqList *pSL, int pos)
{
assert(pSL != NULL);
assert(pSL->size < MAX_SIZE);
assert(pos>=0 && pos < pSL->size);
#if 0 // 以 要搬运到的位置下标作为循环指示
// 要搬运到的位置下标
int space;
for (space = pos; space < pSL->size-1; space++)
{
pSL->array[space] = pSL->array[space + 1];
}
#endif pSL->size--;
// 以 要搬运的数据下标作为循环指示
int p; // 要搬运的数据下标
for (p = pos + 1; p < pSL->size; p++)//从后往前
{
pSL->array[p - 1] = pSL->array[p];
}
pSL->size--;
}
// 根据数据删除,只删除遇到的第一个
void SeqListRemove(SeqList *pSL, DataType data)
{
assert(pSL != NULL);
assert(pSL->size < MAX_SIZE);
int pos = SeqListFind(pSL, data);
if (pos != -1)
{
SeqListErase(pSL, pos);//根据下标删除
}
}
// 根据数据删除,删除所有遇到的
void SeqListRemoveAll(SeqList *pSL, DataType data)
{
assert(pSL != NULL);
assert(pSL->size < MAX_SIZE);
#if 0
while (1)
{
int pos = SeqListFind(pSL, data);
if (pos == -1)
{
break;
}
SeqListErase(pSL, pos);//根据下标删除
}//时间复杂度大
#endif
#if 0
int pos;
while ((pos = SeqListFind(pSL, data)) != -1)//不等于-1表示找到了
{
SeqListErase(pSL, pos);//根据下标删除
}
#endif
#if 0
int i, j;
for (i = 0, j = 0; i < pSL->size; i++)
{
if (pSL->array[i] != data)
{
pSL->array[j] = pSL->array[i];
j++;
}
}
pSL->size=j;
#endif
DataType *NewArray = (DataType*)malloc(sizeof(DataType)*pSL->size);
assert(NewArray);
int i, j, k;
for (i = 0, j = 0; i < pSL->size; i++)
{
if (pSL->array[i] != data)
{
NewArray[j] = pSL->array[i];
j++;
}
}
pSL->size = j;
// 把数据从 newArray 放回到 array
for (k = 0; k < pSL->size; k++)
{
pSL->array[k] = NewArray[k];
}
free(NewArray);
}
// 根据下标更新
void SeqListUpdate(SeqList *pSL, int pos, DataType data)
{
assert(pSL != NULL);
assert(pos >= 0 && pos < pSL->size);
pSL->array[pos] = data;
}
// 查询
// 返回遇到的第一个下标,如果没有遇到,返回 -1
int SeqListFind(SeqList *pSL, DataType data)
{
assert(pSL != 0);
int i;
for (i = 0; i < pSL->size; i++)
{
if (pSL->array[i] == data)
{
return i;
}
}
return -1;
}
void SeqListprint(SeqList *pSL)
{
int i = 0;
for (i = 0; i < pSL->size; i++)
{
printf("%d ",pSL->array[i]);
}
printf("\n");
}
void TestSeqList()
{
SeqList s1;
SeqListInit(&s1);
SeqListDestroy(&s1);
//尾插
SeqListPushBack(&s1, 1);
SeqListPushBack(&s1, 2);
SeqListPushBack(&s1, 3);
SeqListPushBack(&s1, 4);
SeqListprint(&s1);
//头插
SeqListPushFront(&s1, 5);
SeqListPushFront(&s1, 6);
SeqListPushFront(&s1, 7);
SeqListPushFront(&s1, 8);
SeqListprint(&s1);
//根据下标插入
SeqListInsert(&s1, 2,0);
SeqListprint(&s1);
//尾删
SeqListPopBack(&s1);
SeqListprint(&s1);
//头删
SeqListPopFront(&s1);
SeqListprint(&s1);
// 根据下标删除
SeqListErase(&s1, 2);
SeqListprint(&s1);
//查询
SeqListFind(&s1, 7);
// 根据下标更新
SeqListUpdate(&s1, 2, 78);
SeqListprint(&s1);
// 根据数据删除,只删除遇到的第一个
SeqListRemove(&s1, 7);
SeqListprint(&s1);
// 根据数据删除,删除所有遇到的
SeqListRemoveAll(&s1, 78);
SeqListprint(&s1);
SeqListDestroy(&s1);
}
main.c
#include "test.h"
int main()
{
TestSeqList();
system("pause");
return 1;
}
上一篇: JAVA操作SQL插入小技巧
下一篇: 顺序表的基本操作