第25讲：顺序表专题

1.什么是数据结构

2.顺序表概念及结构

3.顺序表分类

4.实现动态顺序表

1.什么是数据结构

数据结构是计算机存储、组织数据的方式。可以用来完成通讯录项目。

2.顺序表概念及结构

2.1线性表

线性表是n个具有相同特性的数据元素的有限序列

常见的线性表：顺序表，链表，栈队列，字符串

线性表在逻辑上是线性的，但在物理结构上却不一定，也就是在内存上的存储不一定是连续的

3.顺序表分类

静态顺序表：空间是固定的，给多了浪费空间，给少了空间不够

缺点多，不建议使用

动态顺序表：空间可以扩大，但扩大空间会浪费时间

相较于静态顺序表优点多，建议使用

4.实现动态顺序表

文件名：SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include "Seqlist.h"
void initSeqList(SL* pSL)//初始化顺序表
{
	pSL->pa = NULL;
	pSL->size = 0;
	pSL->capacity = 0;
}

void cheak(SL* psl1)//检查空间是否足够
{
	if (psl1->size == psl1->capacity)
		expandSL(psl1);
}

void expandSL(SL* pSL)//扩容
{
	int newcapacity = pSL->capacity == 0 ? 4 : 2 * pSL->capacity;
	SLdatatype* pSLm = realloc(pSL->pa, (size_t)newcapacity * sizeof * (pSL->pa));
	if (pSLm == NULL)
	{
		perror("relloc");
		exit(1);
	}
	else
		pSL->pa = pSLm;
	pSL->capacity = newcapacity;
}

void printSL(SL* pSL)//打印顺序表
{
	assert(pSL);
	int i;
	for (i = 0; i < pSL->size; i++)
		printf("%d ", pSL->pa[i]);
}

void backaddSL(SL* pSL, SLdatatype n)//后增
{
	assert(pSL);
	cheak(pSL);
	pSL->pa[pSL->size++] = n;
}

void frontaddSL(SL* pSL, SLdatatype n)//前增
{
	assert(pSL);
	cheak(pSL);
	int i;
	for (i = 0; i < pSL->size; i++)
	{
		pSL->pa[pSL->size - i] = pSL->pa[pSL->size - i - 1];
	}
	pSL->pa[0] = n;
	pSL->size++;
}

void backdel(SL* pSL)//后删
{
	assert(pSL != NULL);
	assert(pSL->size > 0);
	pSL->size--;
}

void frontdel(SL* pSL)//前删
{
	assert(pSL != NULL);
	assert(pSL->size > 0);
	int i;
	for (i = 0; i < pSL->size - 1; i++)
	{
		pSL->pa[i] = pSL->pa[i + 1];
	}
	pSL->size--;
}

void posaddSL(SL* pSL, SLdatatype n, int pos)//指定位置插入
{
	assert(pSL);
	int i = 0;
	for (i = 0; i < pSL->size - pos + 1; i++)
	{
		pSL->pa[pSL->size - i] = pSL->pa[pSL->size - i - 1];
	}
	pSL->pa[pos - 1] = n;
	pSL->size++;
}

void posdelSL(SL* pSL, int pos)//指定位置删除
{
	assert(pSL);
	int i = 0;
	for (i = 0; i < pSL->size - pos + 1; i++)
	{
		pSL->pa[pos - 1 + i] = pSL->pa[pos + i];
	}
	pSL->size--;
}

void SLfind(SL* pSL, int n)//元素查找
{
	int i = 0, flag = 1;
	for (i = 0; i < pSL->size; i++)
	{
		if (pSL->pa[i] == n)
		{
			printf("元素下标为%d\n", i);
			flag = 0;
		}
	}
	if (flag)
		puts("没有该元素");
}

void SLalter(SL* pSL, int n, int pos)//元素修改
{
	pSL->pa[pos - 1] = n;
}

void SLdesdroy(SL* pSL)//销毁
{
	assert(pSL);
	if (pSL->pa != NULL)
	{
		free(pSL->pa);
		pSL->pa = NULL;
	}
	pSL->size = 0;
	pSL->capacity = 0;
}

文件名：SeqList.h

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLdatatype;
typedef struct SeqList
{
	SLdatatype* pa;//数组首元素地址
	int size;//元素个数
	int capacity;//数组容量
}SL;

//初始化顺序表
void initSeqList(SL* pSL);

//判断空间是否足够
void cheak(SL* psl1);

//扩容
void expandSL(SL* pSL);

//打印顺序表
void printSL(SL* pSL);

//后增
void backaddSL(SL* pSL, SLdatatype n);

//前增
void frontaddSL(SL* pSL, SLdatatype n);

//后删
void backdel(SL* pSL);

//前删
void frontdel(SL* pSL);

//指定位置插入
void posaddSL(SL* pSL, SLdatatype n, int pos);

//指定位置删除
void posdelSL(SL* pSL, int pos);

//元素查找
void SLfind(SL* pSL, int n);

//元素修改
void SLalter(SL* pSL, int n, int pos);

//销毁
void SLdesdroy(SL* pSL);

文件名：test.c

#define _CRT_SECURE_NO_WARNINGS
#include "Seqlist.h"
void test1(SL* psl1)//测试后增
{

	backaddSL(psl1, 5);
	backaddSL(psl1, 6);
	backaddSL(psl1, 7);
	printSL(psl1);
}
void test2(SL* psl1)//测试前增
{
	frontaddSL(psl1, 5);
	frontaddSL(psl1, 6);
	frontaddSL(psl1, 7);
	frontaddSL(psl1, 8);
	frontaddSL(psl1, 9);
	frontaddSL(psl1, 5);
	frontaddSL(psl1, 6);
	printSL(psl1);
	putchar('\n');
}
void test3(SL* psl1)//测试后删
{
	backdel(psl1);
	printSL(psl1);
}
void test4(SL* psl1)//测试前删
{
	frontdel(psl1);
	printSL(psl1);
}
void test5(SL* psl1)//测试指定位置插入
{
	posaddSL(psl1, 80, 3);
	printSL(psl1);
}
void test6(SL* psl1)//测试指定位置删除
{
	posdelSL(psl1, 3);
	printSL(psl1);
}
void test7(SL* psl1)//测试元素查找
{
	SLfind(psl1, 100);
}
void test8(SL* psl1)//测试元素修改
{
	SLalter(psl1, 100, 3);
	printSL(psl1);
}
void test9(SL* psl1)//测试销毁
{
	SLdesdroy(psl1);
	printSL(psl1);
}
int main()
{
	SL sl1;
	initSeqList(&sl1);
//	test1(&sl1);
	test2(&sl1);
//	test3(&sl1);
//	test4(&sl1);
//	test5(&sl1);
//	test6(&sl1);
//	test7(&sl1);
//	test8(&sl1);
	test9(&sl1);
	return 0;
}