C语言实现动态顺序表

news/2024/5/20 6:44:59 标签: 顺序表, 动态顺序表, C语言, 增删查改

前边已经实现了静态顺序表，现在来实现一下动态的。其实动态的就只是将静态定义的数组改为动态开辟一块内存来存放一组数据。

具体代码

头文件及函数声明（SeqList.h）部分

#ifndef __SEQLIST_H__
#define __SEQLIST_H__

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#define MAX 3//数组元素个数
#define INC 2

typedef int DataType;//数组元素类型重命名

typedef struct SeqList
{
	DataType* data;//创建一个数组
	int capacity;
	int sz;     //用于记住元素的个数
}SeqList, *pSeqList;

void InitSeqlist(pSeqList ps);//初始化函数
void PushBack(pSeqList ps, DataType x);//从后边添加的函数
void PrintSeqlist(pSeqList ps);//打印数组的函数
void PopBack(pSeqList ps);//从后往前删除的函数
void PushFront(pSeqList ps, DataType x);//从前边添加的函数
void PopFront(pSeqList ps);//从前往后删除的函数
void Insert(pSeqList ps, int pos, DataType x);//指定位置添加的函数
int Find(pSeqList ps, DataType x);//查找函数
void Remove(pSeqList ps, DataType x); //删除指定某个数的函数
void RemoveAll(pSeqList ps, DataType x);//删除所有的指定的某个值的函数
void ReverseList(pSeqList ps);//逆序函数
void SortList(pSeqList ps);//排序函数
int BinarySearch(pSeqList ps, DataType x);//二分查找函数
void Distroy(pSeqList ps);//销毁并释放动态开辟的内存

#endif
每一个函数的具体实现（SeqList.c）部分 

#include "SeqList.h"

void InitSeqlist(pSeqList ps)
{
	//memset(ps->data, 0, MAX*sizeof(DataType));
	ps->data = (DataType *)malloc(MAX*sizeof(DataType));
	if (ps->data == NULL)
	{
		perror("malloc");
		exit(EXIT_FAILURE);
	}
	memset(ps->data, 0, MAX*sizeof(DataType));
	ps->sz = 0;
	ps->capacity = MAX;
}
//检查是否需要增容，若需要则增容
void Check(pSeqList ps)
{
	assert(ps != NULL);
	if (ps->sz == ps->capacity)
	{
		DataType* tmp = (DataType *)realloc(ps->data, (ps->capacity + INC)*sizeof(DataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(EXIT_FAILURE);
		}
		ps->data = tmp;
		ps->capacity += INC;
	}
}
//后加
void PushBack(pSeqList ps, DataType x)
{
	assert(ps != NULL);
	Check(ps);
	ps->data[ps->sz] = x;
	ps->sz++;
}
//打印
void PrintSeqlist(pSeqList ps)
{
	assert(ps != NULL);
	int i = 0;
	if (ps->sz == 0)
	{
		return;
	}
	for (i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->data[i]);
	}
	printf("\n");
}
//后删
void PopBack(pSeqList ps)
{
	assert(ps != NULL);
	if (ps->sz == 0)
	{
		return;
	}
	ps->sz--;
}
//前加
void PushFront(pSeqList ps, DataType x)
{
	assert(ps != NULL);
	Check(ps);
	memmove(ps->data + 1, ps->data, (ps->sz)*sizeof(DataType));
	ps->data[0] = x;
	ps->sz++;
}
//前删
void PopFront(pSeqList ps)
{
	assert(ps != NULL);
	if (ps->sz == 0)
	{
		return;
	}
	memmove(ps->data, ps->data + 1, (ps->sz - 1)*sizeof(DataType));
	ps->sz--;
}
//指定位置添加
void Insert(pSeqList ps, int pos, DataType x)
{
	assert(ps != NULL);
	Check(ps);
	memmove(ps->data + pos + 1, ps->data + pos, (ps->sz - pos)*sizeof(DataType));
	ps->data[pos] = x;
	ps->sz++;
}
//查找
int Find(pSeqList ps, DataType x)
{
	int i = 0;
	assert(ps != NULL);
	if (ps->sz == 0)
	{
		return -1;
	}
	for (i = 0; i < ps->sz; i++)
	{
		if (ps->data[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//指定删除
void Remove(pSeqList ps, DataType x)
{
	int ret = -1;
	assert(ps != NULL);
	if (ps->sz == 0)
	{
		return;
	}
	ret = Find(ps, x);
	if (ret != -1)
	{
		memmove(ps->data + ret, ps->data + ret + 1, (ps->sz - ret)*sizeof(DataType));
		ps->sz--;
	}
}
//指定删除全部
void RemoveAll(pSeqList ps, DataType x)
{
	int i = 0;
	assert(ps != NULL);
	if (ps->sz == 0)
	{
		return;
	}
	for (i = 0; i < ps->sz; i++)
	{
		if (x == ps->data[i])
		{
			memmove(ps->data + i, ps->data + i + 1, (ps->sz - i-1)*sizeof(DataType));
			ps->sz--;
			i--;//防止被删除位置新的数被漏掉
		}
	}
}
//逆序
void ReverseList(pSeqList ps)
{
	int left = 0;
	int right = ps->sz - 1;
	assert(ps != NULL);
	if (ps->sz == 0)
	{
		return;
	}
	while (left < right)
	{
		int tmp = ps->data[left];
		ps->data[left] = ps->data[right];
		ps->data[right] = tmp;
		left++;
		right--;
	}

}
//排序
void SortList(pSeqList ps)
{
	int i = 0;
	int j = 0;
	assert(ps != NULL);
	if (ps->sz == 0)
	{
		return;
	}
	for (i = 0; i < ps->sz - 1; i++)
	{
		for (j = 0; j < ps->sz - i - 1; j++)
		{
			if (ps->data[j]>ps->data[j + 1])
			{
				int tmp = ps->data[j];
				ps->data[j] = ps->data[j + 1];
				ps->data[j + 1] = tmp;
			}
		}
	}
}
//二分查找
int BinarySearch(pSeqList ps, DataType x)
{
	int left = 0;
	int right = ps->sz - 1;
	int mid = 0;
	assert(ps != NULL);
	if (ps->sz == 0)
	{
		return -1;
	}
	while (left < right)
	{
		mid = left + (right - left) / 2;
		if (ps->data[mid] > x)
		{
			right = mid - 1;
		}
		else if (ps->data[mid] < x)
		{
			left = mid + 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}
//销毁
void Distroy(pSeqList ps)
{
	assert(ps != NULL);
	free(ps->data);
	ps->data = NULL;
	ps->sz = 0;
	ps->capacity = 0;
}


测试函数（test.c）部分

 下边的注意一定要认真看！！！

下边的注意一定要认真看！！！


#define _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
void test1()
{
	struct SeqList plist;
	InitSeqlist(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	
	PrintSeqlist(&plist);
	PopBack(&plist);
	PrintSeqlist(&plist);
	PopBack(&plist);
	PrintSeqlist(&plist);
	PopBack(&plist);
	PrintSeqlist(&plist);
	PopBack(&plist);
	PrintSeqlist(&plist);
	PopBack(&plist);
	PrintSeqlist(&plist);
	Distroy(&plist);
}
void test2()
{
	struct SeqList plist;
	InitSeqlist(&plist);
	PushFront(&plist, 1);
	PushFront(&plist, 2);
	PushFront(&plist, 3);
	PushFront(&plist, 4);
	PrintSeqlist(&plist);
	PopFront(&plist);
	PrintSeqlist(&plist);
	PopFront(&plist);
	PrintSeqlist(&plist);
	PopFront(&plist);
	PrintSeqlist(&plist);
	PopFront(&plist);
	PrintSeqlist(&plist);
	PopFront(&plist);
	PrintSeqlist(&plist);
	Distroy(&plist);
}
void test3()
{
	struct SeqList plist;
	InitSeqlist(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PrintSeqlist(&plist);
	Insert(&plist, 2, 6);
	PrintSeqlist(&plist);
	Distroy(&plist);
}
void test4()
{
	struct SeqList plist;
	InitSeqlist(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PrintSeqlist(&plist);
	int ret = Find(&plist, 3);
	//int ret = Find(&plist, 5);
	printf("%d\n", ret);
	Remove(&plist, 3);
	PrintSeqlist(&plist);
	/*Remove(&plist, 6);
	PrintSeqlist(&plist);*/
	Distroy(&plist);
}
void test5()
{
	struct SeqList plist;
	InitSeqlist(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 2);
	PushBack(&plist, 4);
	PushBack(&plist, 6);
	PushBack(&plist, 2);
	PrintSeqlist(&plist);
	RemoveAll(&plist, 2);
	PrintSeqlist(&plist);
	Distroy(&plist);
}
void test6()
{
	struct SeqList plist;
	InitSeqlist(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PrintSeqlist(&plist);
	ReverseList(&plist);
	PrintSeqlist(&plist);
	Distroy(&plist);
}
void test7()
{
	struct SeqList plist;
	InitSeqlist(&plist);
	PushFront(&plist, 1);
	PushFront(&plist, 2);
	PushFront(&plist, 3);
	PushFront(&plist, 4);
	PrintSeqlist(&plist);
	SortList(&plist);
	PrintSeqlist(&plist);
	Distroy(&plist);
}
void test8()
{
	struct SeqList plist;
	InitSeqlist(&plist);
	PushBack(&plist, 1);
	PushBack(&plist, 2);
	PushBack(&plist, 3);
	PushBack(&plist, 4);
	PushBack(&plist, 5);
	PushBack(&plist, 6);
	PrintSeqlist(&plist);
	int ret = BinarySearch(&plist, 5);
	printf("%d\n", ret);
	Distroy(&plist);
}
int main()
{
	test1();//测试在后边添加和删除
	//test2();//测试在前边添加和删除
	//test3();//测试指定位置添加函数
	//test4();//测试查找函数和指定删除某个数的函数，找到返回下标，没找到返回-1
	//test5();//测试删除所有指定的某个值的函数
	//test6();//测试逆序函数
	//test7();//测试排序函数（从小到大排列）
	//test8();//测试二分查找函数，找到返回下标，没找到返回-1

	return 0;
}


注意：因为是动态开辟的内存，所以用完一定要记得释放这块动态开辟的内存。每一个测试函数都包含了销毁函数（里边包括了释放动态内存的函数），为了避免再一次使用已经释放了的空间导致程序崩溃，所以，测试函数一次只能调用一个，想要测试哪个函数的功能，在主函数里边将对应的那个测试函数放开就可以了。


运行结果：


PS：欢迎大家提出宝贵意见哦 ~



http://www.niftyadmin.cn/n/1014851.html

相关文章

[转]子窗体（被调用者）中实现对其父窗体（调用者）的刷新

[转]子窗体（被调用者）中实现对其父窗体（调用者）的刷新

如何在子窗体&#xff08;被调用者&#xff09;中实现对其父窗体&#xff08;调用者&#xff09;的刷新呢&#xff1f;网络上有几种方法&#xff0c;先总结如下&#xff1a;调用窗体&#xff08;父&#xff09;&#xff1a;Form1,被调用窗体&#xff08;子&#xff09;&#xf…
阅读更多...
C语言注释转化为C++注释（C语言实现）

C语言注释转化为C++注释（C语言实现）

/* int a0;*/是C语言注释风格&#xff0c;而我们都知道C语言这样的注释是有缺陷的&#xff08;不能嵌套注释&#xff09;&#xff0c;为了弥补这一缺陷&#xff0c;可将C语言注释风格改为C注释风格&#xff08;//int a0;&#xff09;.本文就来讲一下怎么运用C语言实现C注释转化…
阅读更多...
希望大雪早日停下来.

希望大雪早日停下来.

昨天看到白二的BLOG,提到了下雪,许多人回不了家,有些地方停水停电.今天看到了好多网络新闻,发现雪大得超过了我的想象,有人在车站呆了一周了.真希望大雪早日停下来.大家开心回家过年. 这里也下雪了, 不过不大,因为住在校园内,所以只感觉有点冷. 我春节不回国,不给春运添乱了. 人…
阅读更多...
单链表的实现和相关面试题及其详解（C语言）

单链表的实现和相关面试题及其详解（C语言）

链表是一种物理存储单元上非连续、非顺序的存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的链接次序实现的 链表由一系列结点&#xff08;链表中每一个元素称为结点&#xff09;组成&#xff0c;结点可以在运行时动态生成。 每个结点包括两个部分&#xff1a;一个是存…
阅读更多...
ADSL常见经典故障大全

ADSL常见经典故障大全

ADSL是运行在原有电话线上的一种高速宽带上网方式&#xff0c;它具有节省投资、上网速度快、安装简单等优点。目前很多局域网尤其是网吧都使用这种方式。当然用这种方式上网的故障也比较多&#xff0c;下面就为大家谈谈ADSL故障的排解方法与实例。造成ADSL故障的因素ADSL常见的…
阅读更多...
求带环链表的入口的多种解法

求带环链表的入口的多种解法

方法1&#xff1a; 公式推导:定义两个指针&#xff0c;一个快指针&#xff0c;一个慢指针。两个指针一起走&#xff0c;快指针每次走两步&#xff0c;慢指针每次走一步&#xff08;相当于速度不一样&#xff09;。如果有环&#xff0c;那么它们就一定会相遇&#xff0c;当他们相…
阅读更多...
Representation of Integers and Reals Section I[翻译]

Representation of Integers and Reals Section I[翻译]

Representation of Integers and Reals Section I 【原文见&#xff1a;http://www.topcoder.com/tc?moduleStatic&d1tutorials&d2integersReals】 …
阅读更多...
DD-WRT调节发射功率

DD-WRT调节发射功率

DD-WRT设备可以帮我们实现任意调节发射功率的目的&#xff0c;这样我们就可以根据无线网卡距离DD-WRT无线路由器的远近来决定发射信号的强弱了。下面我们就用事实说话&#xff0c;一步步的教会各位读者如何在DD-WRT设备中调节发射信号功率&#xff0c;以及对比调节前后的接收效…
阅读更多...
最新文章

Copyright @ 2022~2023