順序表 C語言

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);

//數(shù)據(jù)的 插入，查找，刪除

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

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

void Erase(SeqList *p, DataType x);

//移動(dòng)

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;

}

}

}

//一次選出最大最小的數(shù)據(jù)分別放在序列的兩端

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.檢查參數(shù)

// 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;

}

//刪除順序表中第一個(gè) 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()//數(shù)據(jù)的插入查找刪除測試用例

{

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;

}