欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言 顺序表的实现 (动态)

程序员文章站 2022-05-16 10:15:50
给出顺序表的定义: typedef int datatype; typedef struct seqlistd { datatype *array; int size;// 记录有效元...

给出顺序表的定义:

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