C语言 顺序表的实现 （动态）

给出顺序表的定义：

typedef int datatype;
typedef struct seqlistd {
	datatype *array;
	int size;// 记录有效元素的个数
	int capacity;// 空间总大小
}seqlistd, *pseqlistd;

将函数的声明放在head.h的头文件里面：

#ifndef _head_h_
#define _head_h_

#define init_size 10
#define increment 5
typedef int datatype;
typedef struct seqlistd {
	datatype *array;
	int size;// 记录有效元素的个数
	int capacity;// 空间总大小
}seqlistd, *pseqlistd;

void checkcapacity(pseqlistd pseqlist);//检查当前线性表的容量，不够的话申请内存
void initseqlist(pseqlistd pseqlist);//线性表初始化
void pushback(pseqlistd pseqlist, datatype data);//在线性表后面插入元素
void popback(pseqlistd pseqlist);//在线性表后面删除元素
void pushfront(pseqlistd pseqlist, datatype data);//在线性表前面插入元素
void popfront(pseqlistd pseqlist);//在线性表前面删除元素
void insert(pseqlistd pseqlist, int pos, datatype data);//在线性表指定位置插入元素
void erase(pseqlistd pseqlist, int pos);//在线性表指定位置删除元素
int find(pseqlistd pseqlist, datatype data);//在线性表查找元素，返回下标
void remove(pseqlistd pseqlist, datatype data);//在线性表删除值为data的元素
void removeall(pseqlistd pseqlist, datatype data);//在线性表删除所有值为data的元素
int empty(pseqlistd pseqlist);//判别线性表是否为空
void printseqlist(pseqlistd pseqlist);//打印线性表
void bubblesort(pseqlistd pseqlist, int(*cmp)(const void *elem1, const void *elem2));//冒泡排序，升序和降序两种版本，用了函数指针以及回调函数
void selectsort(pseqlistd pseqlist, int(*cmp)(const void *elem1, const void *elem2));//选择排序，升序和降序两种版本，用了函数指针以及回调函数
int cmpinascendingorder(const void *elem1, const void *elem2);//升序比较
int cmpindescendingorder(const void *elem1, const void *elem2);//降序比较
void swap(datatype *a, datatype *b);//交换
int binarysearch(pseqlistd pseqlist, datatype data);//二分查找
int binarysearchrecursion(pseqlistd pseqlist, int left, int right, datatype data);//二分查找的递归版本
int size(pseqlistd pseqlist);//求线性表的大小
void clear(pseqlistd pseqlist);//清空线性表
void destroyseqlist(pseqlistd pseqlist);//销毁线性表

#endif 

具体的实现

test（）函数为测试代码，只写出了其中的一部分

#include 
#include 
#include 
#include "head.h"

void test0();
void test1();
void test2();
void test3();

int main()
{
	//test0();
	//test1();
	//test2();
	test3();
	getchar();
	return 0;
}

void test0()
{
	seqlistd seqlist;
	pseqlistd p = &seqlist;
	initseqlist(p);
	pushback(p, 1);
	pushback(p, 2);
	pushback(p, 3);
	printseqlist(p);
	popback(p);
	popback(p);
	printseqlist(p);

}

void test1()
{
	seqlistd seqlist;
	pseqlistd p = &seqlist;
	initseqlist(p);
	pushback(p, 1);
	pushback(p, 2);
	pushback(p, 3);
	pushback(p, 5);
	printseqlist(p);
	insert(p, 4, 4);
	erase(p, 1);
	printseqlist(p);
}

void test2()
{
	seqlistd seqlist;
	pseqlistd p = &seqlist;
	initseqlist(p);
	pushback(p, 1);
	pushback(p, 6);
	pushback(p, 3);
	pushback(p, 4);
	pushback(p, 2);
	pushback(p, 5);
	printseqlist(p);
	//bubblesort(p, cmpinascendingorder);
	//selectsort(p, cmpinascendingorder);
	printseqlist(p);
	//bubblesort(p, cmpindescendingorder);
	//selectsort(p, cmpindescendingorder);

	//int pos = binarysearch(p, 20) + 1;
	//printf("%d\n", pos);
}

void test3()
{
	seqlistd seqlist;
	pseqlistd p = &seqlist;
	initseqlist(p);
	pushback(p, 1);
	pushback(p, 2);
	pushback(p, 3);
	pushback(p, 5);
	pushback(p, 2);
	pushback(p, 2);
	pushback(p, 4);
	printseqlist(p);
	removeall(p, 2);
	printseqlist(p);

}

void checkcapacity(pseqlistd pseqlist)
{
	assert(pseqlist);
	if (pseqlist->size >= pseqlist->capacity) {
		datatype *p = (datatype *)realloc(pseqlist->array, (init_size + increment) * sizeof(datatype));
		if (!p)
			exit(exit_failure);
		pseqlist->array = p;
		pseqlist->capacity += increment;
	}
}

void initseqlist(pseqlistd pseqlist)
{
	assert(pseqlist);
	pseqlist->array = (datatype *)malloc(init_size * sizeof(datatype));
	if (!(pseqlist->array)) {
		exit(exit_failure);
	}
	pseqlist->size = 0;
	pseqlist->capacity = init_size;
}

void pushback(pseqlistd pseqlist, datatype data)
{
	assert(pseqlist);
	checkcapacity(pseqlist);
	pseqlist->array[pseqlist->size++] = data;
}

void popback(pseqlistd pseqlist)
{
	assert(pseqlist);
	pseqlist->size--;
}

void pushfront(pseqlistd pseqlist, datatype data)
{
	assert(pseqlist);
	checkcapacity(pseqlist);
	for (int i = pseqlist->size; i > 0; --i) {
		pseqlist[i] = pseqlist[i - 1];
	}
	pseqlist->array[0] = data;
	pseqlist->size++;
}

void popfront(pseqlistd pseqlist)
{
	assert(pseqlist);
	pseqlist->size--;
	for (int i = 0; i < pseqlist->size; i++) {
		pseqlist->array[i] = pseqlist->array[i + 1];
	}
}

void printseqlist(pseqlistd pseqlist)
{
	assert(pseqlist);
	printf("the elements in the seqlist:");
	for (int i = 0; i < pseqlist->size; ++i) {
		printf("%d ", pseqlist->array[i]);
	}
	printf("\n");
}

void insert(pseqlistd pseqlist, int pos, datatype data)
{
	assert(pseqlist);
	checkcapacity(pseqlist);
	if (1 <= pos <= pseqlist->size) {
		int truepos = pos - 1;
		for (int i = pseqlist->size; i > truepos; --i) {
			pseqlist->array[i] = pseqlist->array[i - 1];
		}
		pseqlist->array[truepos] = data;
		pseqlist->size++;
	}
	else {
		printf("the pos is wrong\n");
	}
}

void erase(pseqlistd pseqlist, int pos)
{
	assert(pseqlist);
	if (1 <= pos <= pseqlist->size) {
		int truepos = pos - 1;
		pseqlist->size--;
		for (int i = truepos; i < pseqlist->size; ++i) {
			pseqlist->array[i] = pseqlist->array[i + 1];
		}
	}
	else {
		printf("the pos is wrong\n");
	}
}

int find(pseqlistd pseqlist, datatype data)
{
	assert(pseqlist);
	for (int i = 0; i < pseqlist->size; ++i) {
		if (pseqlist->array[i] == data)
			return i + 1;
	}
	return 0;
}

void remove(pseqlistd pseqlist, datatype data)
{
	assert(pseqlist);
	int pos = find(pseqlist, data);
	if (pos != 0) {
		erase(pseqlist, pos);
	}
}

void removeall(pseqlistd pseqlist, datatype data)
{
	assert(pseqlist);
	int count = 0;
	for (int i = 0; i < pseqlist->size; ++i) {
		if (pseqlist->array[i] == data)
			count++;
		else
			pseqlist->array[i - count] = pseqlist->array[i];
	}
	pseqlist->size -= count;
	//while (count--) {
	//	remove(pseqlist, data);
	//}

}


int empty(pseqlistd pseqlist)
{
	return pseqlist->size == 0;
}

void swap(datatype *a, datatype *b)
{
	datatype tmp = *a;
	*a = *b;
	*b = tmp;
}

int cmpinascendingorder(const void *elem1, const void *elem2)
{
	return *(int *)elem1 - *(int *)elem2;
}

int cmpindescendingorder(const void *elem1, const void *elem2)
{
	return *(int *)elem2 - *(int *)elem1;
}

void bubblesort(pseqlistd pseqlist, int(*cmp)(const void *elem1, const void *elem2))
{
	assert(pseqlist);
	int i = 0; 
	int j = 0;
	for (i = 0; i < pseqlist->size - 1; ++i) {
		for (j = 0; j < pseqlist->size - 1 - i; ++j) {
			if (cmp(&pseqlist->array[j], &pseqlist->array[j + 1]) > 0)
				swap(&pseqlist->array[j], &pseqlist->array[j + 1]);
		}
	}
}

void selectsort(pseqlistd pseqlist, int(*cmp)(const void *elem1, const void *elem2))
{
	assert(pseqlist);
	int pos = 0;
	int i = 0; 
	int j = 0;
	for (i = 0; i < pseqlist->size - 1; ++i) {
		pos = i;
		for (j = i + 1; j < pseqlist->size; ++j) {
			if (cmp(&pseqlist->array[j], &pseqlist->array[pos]) > 0) {
				pos = j;
			}
		}
		if (pos != i) {
			swap(&pseqlist->array[i], &pseqlist->array[pos]);
		}
	}
}

int binarysearch(pseqlistd pseqlist, datatype data)
{
	int left = 0;
	int right = pseqlist->size - 1;
	while (left <= right) {
		int mid = left + ((right - left) >> 1);
		if (pseqlist->array[mid] < data)
			left = mid + 1;
		else if (pseqlist->array[mid] > data)
			right = mid - 1;
		else
			return mid;
	}
	return -1;
}

int binarysearchrecursion(pseqlistd pseqlist, int left, int right, datatype data)
{
	if (left <= right) {
		int mid = left + (right - left) / 2;
		if (data > pseqlist->array[mid])
			return binarysearchrecursion(pseqlist, mid + 1, right, data);
		else if (data < pseqlist->array[mid])
			return binarysearchrecursion(pseqlist, left, mid - 1, data);
		else
			return mid;
	}
	else
		return -1;
}

int size(pseqlistd pseqlist)
{
	return pseqlist->size;
}

void clear(pseqlistd pseqlist)
{
	for (int i = 0; i < pseqlist->size; ++i) {
		pseqlist->array[i] = 0;
	}
}

void destroyseqlist(pseqlistd pseqlist)
{
	free(pseqlist->array);
	pseqlist->capacity = 0;
	pseqlist->size = 0;
}