当前位置：移动技术网 > IT编程>开发语言>C/C++ > C语言顺序表的实现（动态）

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

2018年10月14日 | 移动技术网IT编程 | 我要评论

诺记吧,青春之歌txt,北师大版六年级数学下册教案

给出顺序表的定义：

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

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！点击进行留言回复

C++ 作用域

作用域：名称在翻译单元（包括文件）的可见范围局部：只在定义它的代码块中可用，如自动变量全局（文件作用域）：从定义位置到文件结尾都可用注意：静... [阅读全文]
Prim计算最小生成树权值 C语言

题目描述现在，你被委托在一个广阔区域里面为某些确定的结点设计连接网络。首先，你会给定在区域里面的一系列结点，和连接这些结点的一组线路。对于每条可能使用... [阅读全文]
C打印楼梯，同时在楼梯上方打印两个笑脸

题目：打印楼梯，同时在楼梯上方打印两个笑脸。程序分析：用 ASCII 1 来输出笑脸；用i控制行，j来控制列，j根据i的变化来控制输出黑方格的个数。 ... [阅读全文]
算法笔记刷题6 ( PAT 1003我要通过 )

算法笔记刷题6 ( PAT1003我要通过 ) 题目本体 “ 答案正确 ”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“ 答案正确 ”大派... [阅读全文]
聚合类型与POD类型

Lippman在《深度探索C++对象模型》的前言中写道： I have heard a number of people over the years ... [阅读全文]
GetAsyncKeyState 获取键盘按键消息

1 #include <Windows.h> 2 #include <iostream> 3 using namespace s... [阅读全文]
c primer plus(中文版)第一章的一处错误

c primer plus(中文版)1.8.8 第三段第三段第一句：“UNIX系统内置Mac OS X”。这句话讲不通，UNIX系统内置MAC OS ... [阅读全文]
如何在没有core文件的情况下用dmesg+addr2line定位段错误

前言在现网环境下，程序奔溃后不一定会留下core文件，原因有很多，比如存储空间不足就是其中一个常见的原因。此时我们只能依据linux记录的错误日志来定位... [阅读全文]
用QT制作3D点云显示器——QtDataVisualization

因为QT的三维显示模块QtDataVisualization已经对个人开发免费开放了，所以在制作点云，地图，表格之类的东西的时候，其实我们都不需要使用Q... [阅读全文]
判断一个数是否为素数（质数）

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 ... [阅读全文]

网友评论


验证码：

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

2018年10月14日 | 移动技术网IT编程 | 我要评论

您可能感兴趣的文章:

相关文章:

网友评论

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