一文带你搞懂顺序表

文章目录

• 前言
• 一、顺序表是什么？
• 二、顺序表的实现
• • 1、头文件设计
  • 2、具体函数实现
  • 3、具体测试
• 总结

---

前言

学习数据结构是一个快速提高代码量的捷径，与此同时还可以把前面学到的知识充分的运用起来。
本篇涉及到的知识为结构体、简单数组、malloc函数、realloc函数、memmove函数、qsort函数、枚举等。
malloc函数&&realloc函数详解

memmove函数详解

一、顺序表是什么？

顺序表是为了存储一定的数据进行设计的一种数据结构，与结构体结合起来可以存储自定义的数据类型，克服了原本基本数组的不足之处，另一方面，它可以实现动态的扩容，克服了数组的缺陷，可以有效地避免空间的浪费。

二、顺序表的实现

注：具体函数设计风格和STL类似，方便以后对C++STL模板库的认识。

1、头文件设计

#pragma once
#include 
#include 
#include 
#include 
#include 

typedef int DataType;

typedef struct SeqList
{
	DataType* list;
	int size;
	int capacity;
}SL;

void Init_SeqList(SL* ps);

void SL_Print(SL* ps);

void Check_Capacity(SL* ps);

void SL_push_Back(SL* ps, DataType x);

void SL_pop_Back(SL* ps);

void SL_push_Front(SL* ps, DataType x);

void SL_pop_Front(SL* ps);

void SL_Insert(SL* ps, int pos, DataType x);

void SL_Erase(SL* ps, int pos);

int  SL_Find(SL* ps, DataType x);

void SL_Sort(SL* ps);

void SL_Destroy(SL* ps);

2、具体函数实现

#include "SeqList.h"

void Init_SeqList(SL* ps)
{
	assert(ps);
	ps->list = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void Check_Capacity(SL* ps)
{
	
	if (ps->capacity == ps->size)
	{
		int newCapacity = ps->capacity == 0 ? 10 : ps->capacity * 2;

		DataType* temp = (DataType*)realloc(ps->list, newCapacity, sizeof(DataType));
		if (temp == NULL)
		{
			perror("realloc:");
		}
		ps->list = temp;
	}
}

void SL_push_Back(SL* ps, DataType x)
{
	assert(ps);
	Check_Capacity(ps);
	ps->list[ps->size] = x;
	ps->size++;
}

void SL_Print(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->list[i]);
	}
	printf("\n");
}

void SL_pop_Back(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);

	ps->list[ps->size] = 0;
	ps->size--;
	
}

void SL_push_Front(SL* ps, DataType x)
{
	assert(ps);
	Check_Capacity(ps);
	memmove(&ps->list[1], &ps->list[0], ps->size * sizeof(DataType));
	//memmove(ps->list[1], ps->list[0], ps->size * sizeof(DataType));
	//这样写的话ps->list[1]是数据 不是地址！！！
	ps->list[0] = x;
	ps->size++;
	
	//int end = ps->size;
	//while (end--)
	//{
	//	ps->list[end] = ps->list[end - 1];
	//}
	//ps->list[0] = x;
	//ps->size++;
}

void SL_pop_Front(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);

	memmove(&ps->list[0], &ps->list[1], ps->size * sizeof(DataType));
	ps->size--;
	
}

void SL_Insert(SL* ps, int pos,DataType x)
{
	assert(ps);
	Check_Capacity(ps);
	assert(ps > 0 && ps <= ps->size+1);
	memmove(&ps->list[pos], &ps->list[pos-1], sizeof(DataType) * (ps->size - pos + 1));
	ps->list[pos - 1] = x;
	ps->size++;
}

void SL_Erase(SL* ps, int pos)
{
	assert(ps);
	assert(pos > 0 && pos <= ps->size);
	memmove(&ps->list[pos-1], &ps->list[pos], sizeof(DataType) * (ps->size - pos + 1));
	ps->size--;
	
}

int SL_Find(SL* ps, DataType x)
{
	assert(ps);
	assert(ps->size > 0);
	
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->list[i] == x)
		{
			return i + 1;
		}
	}
	return 0;
}

int CMP(const void* a, const void* b)
{
	return *(DataType*)a - *(DataType*)b;
}

void SL_Sort(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);

	qsort(&ps->list[0], ps->size, sizeof(DataType), CMP);
}

void SL_Destroy(SL* ps)
{
	assert(ps);
	ps->list = NULL;
	ps->size = ps->capacity = 0;
	printf("销毁表！\n");
}

3、具体测试

#include "SeqList.h"

void menu()
{
	printf("----------------------------------------------\n");
	printf("----1.头插                         2.尾插-----\n");
	printf("----3.头删                         4.尾删-----\n");
	printf("----5.插入                         6.删除-----\n");
	printf("----7.获取元素位置                       -----\n");
	printf("----8.排序                         9.打印-----\n");
	printf("----0.退出                               -----\n");
	printf("----------------------------------------------\n");
	printf("\n");
}

enum
{
	Exit,
	push_front,
	push_back,
	pop_front,
	pop_back,
	insert,
	erase,
	get_pos,
	sort,
	print,
	
};

void test1()
{
	SL s;
	Init_SeqList(&s);
	int choice = 1;
	int x;
	int pos;
	
	do {
		menu();
		printf("请选择>");
		scanf("%d", &choice);
		switch (choice)
		{
		case push_front:
			printf("输入要插入的值>");
			scanf("%d", &x);
			SL_push_Front(&s, x);
			break;

		case push_back:
			printf("输入要插入的值>");
			scanf("%d", &x);
			SL_push_Back(&s, x);
			break;

		case pop_front:
			SL_pop_Front(&s);
			break;

		case pop_back:
			SL_pop_Back(&s);
			break;

		case insert:
			printf("输入插入的位置和值>");
			scanf("%d %d", &pos, &x);
			SL_Insert(&s, pos, x);
			break;

		case erase:
			printf("输入要删除元素的位置>");
			scanf("%d", &pos);
			SL_Erase(&s, pos);
			break;
		
		case get_pos:
			printf("输入要查找的元素>");
			scanf("%d", &x);
			printf("%d\n",SL_Find(&s, x));
			break;

		case sort:
			SL_Sort(&s);
			break;

		case print:
			SL_Print(&s);
			break;
		case Exit:
			SL_Destroy(&s);
			printf("退出系统！");
			break;
		default:
			printf("输入错误，请重新输入！");
		}
	} while (choice);

	

}


int main()
{
	
	test1();
	return 0;
}

---

总结

这已经是我第五次写顺序表了，但是在memmove函数传值的时出现了错误，说明对双指针的理解不够深入，在链表的时候涉及到的双指针问题可能会更多。Come on ! ! !
注：作者水平有限，如有错误，敬请指正！！！