C语言动态顺序表的实现

悠悠 2022-05-20 23:42 202阅读 0赞

上一次我们实现了静态顺序表，静态顺序表的大小固定，不方便我们去存取数据。

而动态顺序表就可以很方便的存取数据。

同样，我们有以下接口要实现：

#ifndef __SEQLIST_H__
    #define __SEQLIST_H__
    #include<stdio.h>
    #include<assert.h>
    #include<string.h>
    #include<stdlib.h>
    #define MAX 3
    typedef int DataType;
    typedef struct SeqList
    {
    	DataType *data;//存储顺序表元素
    	int sz;//顺序表数组的大小
    	int capicity;//容量
    }SeqList, *pSeqList;
    
    //初始化 
    void InitSeqList(pSeqList pSeq);
    //销毁初始化的空间
    void DestoryList(pSeqList pSeq); 
    //增容函数
    void DeleteCapicityList(pSeqList pSeq);  
    //尾部插入 
    void PushBack(pSeqList pSeq, DataType d);
    //尾部删除 
    void PopBack(pSeqList pSeq);
    //头部插入 
    void PushFront(pSeqList pSeq, DataType d);
    //头部删除 
    void PopFront(pSeqList pSeq);
    //查找指定元素 
    int Find(pSeqList pSeq, DataType d);
    //指定位置插入 
    void Insert(pSeqList pSeq, int pos, DataType d);
    //删除指定位置元素 
    void Erase(pSeqList pSeq, int pos);
    //删除指定元素 
    void Remove(pSeqList pSeq, DataType d);
    //删除所有的指定元素 
    void RemoveAll(pSeqList pSeq, DataType d);
    //返回顺序表的大小 
    int Size(pSeqList pSeq);
    //判断顺序表是否为空 
    int Empty(pSeqList pSeq);
    //冒泡排序 
    void BubbleSort(pSeqList pSeq);
    //选择排序 
    void SelectSort(pSeqList pSeq);
    //选择排序的优化 
    void SelectSortOP(pSeqList pSeq);
    //二分查找 
    int BinarySearch(pSeqList pSeq, DataType d);
    //二分查找递归写法 
    int BinarySearch_R(pSeqList pSeq, int left, int right, DataType d);
    //打印 
    void PrintSeqList(pSeqList pSeq);
    #endif //__SEQLIST_H__

实现主函数：

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include "SeqList.h"
    
    void TestPushBack()
    {
    	SeqList seq;
    	InitSeqList(&seq);
    	PushBack(&seq, 1);
    	PushBack(&seq, 2);
    	PushBack(&seq, 3);
    	PushBack(&seq, 4);
    	PushBack(&seq, 5);
    	PrintSeqList(&seq);
    	PopBack(&seq);
    	PrintSeqList(&seq);
    	PopBack(&seq);
    	PrintSeqList(&seq);
    	PopBack(&seq);
    	PrintSeqList(&seq);
    }
    
    void TestPushFront()
    {
    	SeqList seq;
    	InitSeqList(&seq);
    	PushFront(&seq, 1);
    	PushFront(&seq, 2);
    	PushFront(&seq, 3);
    	PushFront(&seq, 4);
    	PushFront(&seq, 5);
    	PrintSeqList(&seq);
    	PopFront(&seq);
    	PrintSeqList(&seq);
    	PopFront(&seq);
    	PrintSeqList(&seq);
    	PopFront(&seq);
    	PrintSeqList(&seq);
    }
    
    void TestFind()
    {
    	SeqList seq;
    	int tmp = 0;
    	InitSeqList(&seq);
    	PushFront(&seq, 1);
    	PushFront(&seq, 2);
    	PushFront(&seq, 3);
    	PushFront(&seq, 4);
    	PushFront(&seq, 5);
    	PrintSeqList(&seq);
    	tmp = Find(&seq, 1);
    	if (tmp == -1)
    		printf("没找到！\n");
    	else if (tmp > -1)
    		printf("找到了，下标为：%d\n", tmp);
    
    }
    
    void TestInsert_Erase()
    {
    	SeqList seq;
    	InitSeqList(&seq);
    	PushFront(&seq, 1);
    	PushFront(&seq, 2);
    	PushFront(&seq, 3);
    	PushFront(&seq, 4);
    	PushFront(&seq, 5);
    	PrintSeqList(&seq);
    	Insert(&seq, 3, 3);
    	PrintSeqList(&seq);
    	Erase(&seq, 3);
    	PrintSeqList(&seq);
    	Remove(&seq, 3);
    	PrintSeqList(&seq);
    	Insert(&seq, 3, 1);
    	PrintSeqList(&seq);
    	RemoveAll(&seq, 1);
    	PrintSeqList(&seq);
    }
    
    void TestSize_Empty()
    {
    	SeqList seq;
    	int tmp = 0;
    	int empty = 0;
    	InitSeqList(&seq);
    	PushFront(&seq, 1);
    	PushFront(&seq, 2);
    	PushFront(&seq, 3);
    	PushFront(&seq, 4);
    	PushFront(&seq, 5);
    	PrintSeqList(&seq);
    	tmp = Size(&seq);
    	if (tmp == -1)
    		printf("没找到！\n");
    	else if (tmp >= 0)
    		printf("找到了，大小为：%d\n", tmp);
    	empty = Empty(&seq);
    	if (empty == -1)
    		printf("顺序表为空！\n");
    	else if (tmp == 1)
    		printf("顺序表不为空！\n");
    }
    
    void TestSort()
    {
    	SeqList seq;
    	int pos = 0;
    	InitSeqList(&seq);
    	PushFront(&seq, 1);
    	PushFront(&seq, 2);
    	PushFront(&seq, 3);
    	PushFront(&seq, 4);
    	PushFront(&seq, 5);
    	PrintSeqList(&seq);
    	BubbleSort(&seq);
    	PrintSeqList(&seq);
    	SelectSort(&seq);
    	PrintSeqList(&seq);
    	SelectSortOP(&seq);
    	PrintSeqList(&seq);
    	pos = BinarySearch(&seq, 3);
    	if (pos == -1)
    		printf("没找到！\n");
    	else if (pos >= 0)
    		printf("找到了，下标为：%d\n", pos);
    	pos = BinarySearch_R(&seq, 0, seq.sz - 1, 2);
    	if (pos == -1)
    		printf("没找到！\n");
    	else if (pos >= 0)
    		printf("找到了，下标为：%d\n", pos);
    }
    
    int main()
    {
    	//TestPushBack();
    	//TestPushFront();
    	//TestFind();
    	//TestInsert_Erase();
    	//TestSize_Empty();
    	TestSort();
    	system("pause");
    	return 0;
    }

实现子函数：

#define _CRT_SECURE_NO_WARNINGS 1
    
    #include"SeqList.h"
    
    void InitSeqList(pSeqList pSeq)//初始化 
    {
    	assert(pSeq != NULL);
    	pSeq->capicity = MAX;
    	pSeq->sz = 0;
    	pSeq->data=(DataType *)malloc((pSeq->capicity)*sizeof(DataType));
    	if (pSeq->data == NULL)
    	{
    		perror("molloc capicity");
    		exit(EXIT_FAILURE);
    	}
    	memset(pSeq->data, 0, (pSeq->capicity)*sizeof(DataType));
    } 
    
    void DestoryList(pSeqList pSeq)//销毁初始化的空间
    {
    	assert(pSeq!= NULL);
    	free(pSeq->data);
    	pSeq->data = NULL;
    	pSeq->sz = 0;
    	pSeq->capicity = 0;
    }
    
    void CheckCapicityList(pSeqList pSeq)//增容函数
    {
    	assert(pSeq!= NULL);
    	if (pSeq->sz == pSeq->capicity)//如果等于容量就满了就增容  
    	{
    		DataType *ptr = realloc(pSeq->data, (pSeq->capicity + MAX)*sizeof(DataType));
    		if (ptr != NULL)
    		{
    			pSeq->data = ptr;
    			pSeq->capicity += MAX;
    		}
    		else
    		{
    			perror("realloc");
    			exit(EXIT_FAILURE);
    		}
    	}
    }
    
    void PushBack(pSeqList pSeq, DataType d)//尾部插入 
    {
    	assert(pSeq != NULL);
    	CheckCapicityList(pSeq);
    	pSeq->data[pSeq->sz] = d;
    	pSeq->sz++;
    }
    
    void PopBack(pSeqList pSeq)//尾部删除 
    {
    	assert(pSeq != NULL);
    	if (pSeq->sz == 0)
    	{
    		printf("顺序表为空，无法删除！\n");
    		return;
    	}
    	pSeq->sz--;
    }
    
    void PushFront(pSeqList pSeq, DataType d)//头部插入 
    {
    	assert(pSeq != NULL);
    	CheckCapicityList(pSeq);
    	int i = 0;
    	for (i = pSeq->sz - 1; i >= 0; i--)
    	{
    		pSeq->data[i + 1] = pSeq->data[i];
    	}
    	pSeq->data[0] = d;
    	pSeq->sz++;
    }
    
    void PopFront(pSeqList pSeq)//头部删除 
    {
    	assert(pSeq != NULL);
    	if (pSeq->sz == 0)
    	{
    		printf("顺序表为空，无法删除！\n");
    		return;
    	}
    	int i = 0;
    	for (i = 0; i < pSeq->sz - 1; i++)
    	{
    		pSeq->data[i] = pSeq->data[i + 1];
    	}
    	pSeq->sz--;
    }
    
    int Find(pSeqList pSeq, DataType d)//查找指定元素 
    {
    	assert(pSeq != NULL);
    	if (pSeq->sz == 0)
    	{
    		printf("顺序表为空，无法查找！");
    		return -1;
    	}
    	int i = 0;
    	for (i = 0; i < pSeq->sz; i++)
    	{
    		if (pSeq->data[i] == d)
    			return i;
    	}
    	return -1;
    }
    
    void Insert(pSeqList pSeq, int pos, DataType d)//指定位置插入 
    {
    	assert(pSeq != NULL);
    	CheckCapicityList(pSeq);
    	int i = 0;
    	for (i = pSeq->sz - 1; i >= pos; i--)
    	{
    		pSeq->data[i + 1] = pSeq->data[i];
    	}
    	pSeq->data[pos] = d;
    	pSeq->sz++;
    }
    
    void Erase(pSeqList pSeq, int pos)//删除指定位置元素 
    {
    	assert(pSeq != NULL);
    	if (pSeq->sz == 0)
    	{
    		printf("顺序表已空，无法删除！\n");
    		return;
    	}
    	int i = 0;
    	for (i = pos; i < pSeq->sz - 1; i++)
    	{
    		pSeq->data[i] = pSeq->data[i + 1];
    	}
    	pSeq->sz--;
    }
    
    void Remove(pSeqList pSeq, DataType d)//删除指定元素 
    {
    	assert(pSeq != NULL);
    	if (pSeq->sz == 0)
    	{
    		printf("顺序表已空，无法删除！\n");
    		return;
    	}
    	int i = 0;
    	for (i = 0; i < pSeq->sz; i++)
    	{
    		if (pSeq->data[i] == d)
    		{
    			int j = 0;
    			for (j = i; j<pSeq->sz; j++)
    			{
    				pSeq->data[j] = pSeq->data[j + 1];
    			}
    			pSeq->sz--;
    			return;
    		}
    	}
    }
    
    void RemoveAll(pSeqList pSeq, DataType d)//删除所有的指定元素 
    {
    	assert(pSeq != NULL);
    	if (pSeq->sz == 0)
    	{
    		printf("顺序表已空，无法删除！\n");
    		return;
    	}
    	int i = 0;
    	int count = 0;
    	for (i = 0; i < pSeq->sz; i++)
    	{
    		if (pSeq->data[i] != d)
    		{
    			pSeq->data[count++] = pSeq->data[i];
    		}
    	}
    	pSeq->sz = count;
    }
    
    int Size(pSeqList pSeq)//返回顺序表的大小 
    {
    	assert(pSeq != NULL);
    	return pSeq->sz;
    }
    
    int Empty(pSeqList pSeq)//判断顺序表是否为空 
    {
    	assert(pSeq != NULL);
    	if (pSeq->sz == 0)
    	{
    		printf("顺序表已空，无法删除！\n");
    		return -1;
    	}
    	else if (pSeq->sz > 0)
    		return 1;
    }
    
    void BubbleSort(pSeqList pSeq) //冒泡排序
    {
    	assert(pSeq != NULL);
    	int i = 0;
    	int j = 0;
    	int tmp = 0;
    	int flag = 0;
    	for (i = 0; i < pSeq->sz; i++)
    	{
    		flag = 0;
    		for (j = 0; j < pSeq->sz - i - 1; j++)
    		{
    
    			if (pSeq->data[j] > pSeq->data[j + 1])
    			{
    				tmp = pSeq->data[j];
    				pSeq->data[j] = pSeq->data[j + 1];
    				pSeq->data[j + 1] = tmp;
    				flag = 1;
    			}
    		}
    		if (flag == 0)
    		{
    			break;
    		}
    	}
    }
    void SelectSort(pSeqList pSeq)//选择排序 
    {
    	assert(pSeq != NULL);
    	int i = 0;
    	int j = 0;
    	int tmp = 0;
    	for (i = 0; i < pSeq->sz; i++)
    	{
    		int max = 0;
    		for (j = 0; j < pSeq->sz - i; j++)
    		{
    			if (pSeq->data[j]>pSeq->data[max])
    				max = j;
    		}
    		if (max != pSeq->sz - 1 - i)
    		{
    			tmp = pSeq->data[max];
    			pSeq->data[max] = pSeq->data[pSeq->sz - 1 - i];
    			pSeq->data[pSeq->sz - 1 - i] = tmp;
    		}
    	}
    }
    
    void SelectSortOP(pSeqList pSeq)//选择排序的优化 
    {
    	assert(pSeq != NULL);
    	int i = 0;
    	int start = 0;
    	int end = pSeq->sz - 1;
    	int tmp = 0;
    	while (start<end)
    	{
    		int max = start;
    		int min = start;
    		for (i = start; i <= end; i++)
    		{
    			if (pSeq->data[i]>pSeq->data[max])
    				max = i;
    			if (pSeq->data[i]<pSeq->data[min])
    				min = i;
    		}
    		if (max != end)
    		{
    			tmp = pSeq->data[max];
    			pSeq->data[max] = pSeq->data[end];
    			pSeq->data[end] = tmp;
    		}
    		end--;
    		if (max == min)
    			min = max;
    		if (min != start)
    		{
    			tmp = pSeq->data[min];
    			pSeq->data[min] = pSeq->data[start];
    			pSeq->data[start] = tmp;
    		}
    		start++;
    	}
    }
    
    int BinarySearch(pSeqList pSeq, DataType d)//二分查找 
    {
    	assert(pSeq != NULL);
    	int left = 0;
    	int right = pSeq->sz - 1;
    
    	while (left <= right)
    	{
    		int mid = left - ((left - right) >> 1);
    		if (pSeq->data[mid] > d)
    		{
    			right = mid - 1;
    		}
    		else if (pSeq->data[mid] < d)
    		{
    			left = mid + 1;
    		}
    		else
    			return mid;
    	}
    	return -1;
    }
    
    int BinarySearch_R(pSeqList pSeq, int left, int right, DataType d)//二分查找递归写法 
    {
    	assert(pSeq != NULL);
    	if (left > right)
    		return -1;
    	int mid = left + (right - left) / 2;
    	if (pSeq->data[mid] == d)
    		return mid;
    	else if (pSeq->data[mid] > d)
    		return BinarySearch_R(pSeq, left, mid - 1, d);
    	else
    		return BinarySearch_R(pSeq, mid + 1, right, d);
    }
    
    void PrintSeqList(pSeqList pSeq)//打印
    {
    	assert(pSeq != NULL);
    	int i = 0;
    	for (i = 0; i < pSeq->sz; i++)
    	{
    		printf("%d ", pSeq->data[i]);
    	}
    	printf("\n");
    }

这样，动态的就实现了！