顺序表 C语言

发布时间:2020-04-11 05:24:24 作者:2013221
来源:网络 阅读:549

SeqList.h文件:

#pragma once

#include<string.h>


#include<assert.h>


#define MAX_SIZE 5

typedef int DataType;


typedef struct SeqList

{

DataType array[MAX_SIZE];

size_t size;

}SeqList;


//打印单链表

void PrintSeqList(SeqList* pSeq);

//初始化

void InitSeqList(SeqList* pSeq);

//尾插,尾删,前插,前删

void PushBack(SeqList* pSeq, DataType x);

void PopBack(SeqList* pSeq);

void PushFront(SeqList* pSeq, DataType x);

void PopFront(SeqList* pSeq);



//数据的 插入,查找,删除

void Insert(SeqList* pSeq,size_t pos,DataType x);

int Find(SeqList* pSeq, size_t pos, DataType x);

void Erase(SeqList *p, DataType x);

//移动

int Remove(SeqList *pSeq, DataType x);

void RemoveAll(SeqList* pSeq,DataType x);

//交换

void Swap(DataType* left, DataType* right);

void BubbleSort(SeqList* pSeq);

void SelectSort(SeqList* pSeq);

//折半查找,顺序表是排好顺序的

int BinarySearch(SeqList* pSeq, DataType x);



Function.cpp文件:

#include"SeqList_S.h"

void Swap(DataType* left, DataType* right)

{

DataType tmp = *left;

*left = *right;

*right = tmp;

}

//冒泡排序

void BubbleSort(SeqList* pSeq)

{

assert(pSeq);

for (int i = 0; i < pSeq->size; i++)

{

int exchange = 0;

for (int j = 0; j < ((pSeq->size) - i - 1); j++)

{

if (pSeq->array[j]>pSeq->array[j + 1])

{

Swap(&pSeq->array[j], &pSeq->array[j + 1]);

exchange = 1;

}

}

if (exchange == 0)

{

return;

}

}


}

//一次选出最大最小的数据分别放在序列的两端

void SelectSort(SeqList* pSeq)

{

assert(pSeq);

int left = 0; int right = pSeq->size - 1;

while (left < right)

{

for (int i = left + 1; i < right; i++)

{

if (pSeq->array[i]>pSeq->array[right])

{

Swap(&pSeq->array[i], &pSeq->array[right]);

}

if (pSeq->array[i] < pSeq->array[left])

{

Swap(&pSeq->array[i], &pSeq->array[left]);

}

}

++left;

--right;

}


}

//折半查找,顺序表是排好顺序的

int BinarySearch(SeqList* pSeq, DataType x)

{

assert(pSeq);

int left = 0;

int right = pSeq->size;

while (left < right)

{

int mid = left + (right - left) / 2;

if (x>pSeq->array[mid])

{

left = mid + 1;

}

else if (x < pSeq->array[mid])

{

right = mid;

}

else

{

return mid;

}

}

return -1;

}

//初始化

void InitSeqList(SeqList* pSeq)

{

assert(pSeq);

memset(pSeq->array, 0, sizeof(DataType)*MAX_SIZE);

pSeq->size = 0;

}

// 1.检查参数

// 2.边界条件检查

// 3.完成功能逻辑

void PushBack(SeqList* pSeq, DataType x)

{

assert(pSeq);

if (pSeq->size >= MAX_SIZE)

{

printf("SeqList is full");

return;

}

pSeq->array[pSeq->size++] = x;

//assert(pSeq,pSeq->size,x);

}

void PopBack(SeqList* pSeq)

{

assert(pSeq);

if (pSeq->size == 0)

{

printf("SeqList is empty");

return;

}

pSeq->array[--pSeq->size]=0;

/*--pSeq->size;*/

}

void PushFront(SeqList* pSeq, DataType x)

{

assert(pSeq);

if (pSeq->size >= MAX_SIZE)

{

printf("SeqList is full!\n");

return;

}

int begin = pSeq->size;

for (; begin > 0; --begin)

{

pSeq->array[begin] = pSeq->array[begin - 1];

}

pSeq->array[0] = x;

++pSeq->size;

//Insert(pSeq,0,x);

}

void PopFront(SeqList* pSeq)

{

assert(pSeq);

if (pSeq->size == 0)

{

printf("SeqList is empty");

return;

}

int begin = 1;

for (; begin < pSeq->size; begin++)

{

pSeq->array[begin - 1] = pSeq->array[begin];

}

pSeq->array[--pSeq->size]=0;

}

void Insert(SeqList* pSeq, size_t pos, DataType x)

{

assert(pSeq);

/*assert(pSeq->size=>pos)*/

if (pSeq->size >= MAX_SIZE)

{

printf("SeqList is full!");

return;

}

if (pos > pSeq->size)

{

printf("插入位置不合理");

return;

}

for (int begin = pSeq->size; begin > pos; --begin)

{

pSeq->array[begin] = pSeq->array[begin - 1];

}

pSeq->array[pos] = x;

++pSeq->size;

}

int Find(SeqList* pSeq, size_t pos, DataType x)

{

assert(pSeq);

int i = pos;

for (; i < pSeq->size; ++i)

{

if (pSeq->array[i] == x)

{

return i;

}

}

return -1;


}


void Erase(SeqList* pSeq, size_t pos)

{

assert(pSeq);

if (pSeq->size <= 0)

{

printf("SeqList is empty!");

return;

}

if (pos > (pSeq->size) || pos<0)

{

printf("删除位置不合理");

return;

}

int begin = pos + 1;

for (; begin <pSeq->size; ++begin)

{

pSeq->array[begin - 1] = pSeq->array[begin];

}

--pSeq->size;

}



//删除顺序表中第一个 X

int Remove(SeqList* pSeq, DataType x)

{

int pos;

assert(pSeq);

pos = Find(pSeq, 0, x);

if (pos != -1)

{

Erase(pSeq, pos);

}

return pos;

}

//删除所有的 

//void RemoveAll(SeqList* pSeq, DataType x)

//{

//assert(pSeq);

//int pos = Find(pSeq, 0, x);

//while (pos != -1)

//{

//Erase(pSeq, pos);

//pos = Find(pSeq, pos, x);

//}

//}

void RemoveAll(SeqList* pSeq, DataType x)

{

assert(pSeq);

int count = 0;

int begin = 0;

for (; begin < pSeq->size; ++begin)

{

if (pSeq->array[begin] == x)

{

++count;

}

else

{

pSeq->array[begin - count] = pSeq->array[begin];

}

}

pSeq->size -= count;

}

void PrintSeqList(SeqList* pSeq)

{

assert(pSeq);

for (int i = 0; i<pSeq->size; ++i)

{

printf("%d ", pSeq->array[i]);

}

printf("\n");

}


测试案例:

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

#include<stdlib.h>

#include"Seqlist_S.h"

//#include"function.c"

void test1()//顺序表前插,尾插测试用例

{

SeqList l;

InitSeqList(&l);

PushBack(&l, 1);

PushBack(&l, 2);

PushBack(&l, 3);

PushBack(&l, 4);

PushBack(&l, 5);

PushBack(&l, 6);

PrintSeqList(&l);

PopBack(&l);

PopBack(&l);


PopBack(&l);


PopBack(&l);


PopBack(&l);

}

void test2()//顺序表前尾插尾删测试用例

{

SeqList l;

InitSeqList(&l);

PushFront(&l, 1);

PushFront(&l, 2);

PushFront(&l, 3);

PushFront(&l, 4);

PushFront(&l, 5);

PushFront(&l, 6);

PrintSeqList(&l);

PopFront(&l);

PopFront(&l);

PopFront(&l);

PopFront(&l);

PopFront(&l);

}

void test3()//数据的插入查找删除测试用例

{

SeqList l;

InitSeqList(&l);

PushBack(&l, 1);

Insert(&l,0, 2);

Insert(&l,3, 3);

PushBack(&l, 4);

PushBack(&l, 5);

PushBack(&l, 6);

Insert(&l, 0, 2);

PrintSeqList(&l);

int pos1=Find(&l,0,2);

int pos2 = Find(&l,0,3);

Erase(&l, 2);

Erase(&l, 3);


}

int main()

{

test3();

system("pause");

return 0;

}


推荐阅读:
  1. C语言实现顺序表
  2. C语言怎么实现顺序表的顺序查找和折半查找

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

顺序表

上一篇:指针4-指针的运算和指针变量占几个字节

下一篇:thinkPHP 5.0 学习笔记

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》