数据结构--线性表

1.线性表的定义：

存在唯一的一个被称为“第一个”的数据元素；
存在唯一的一个被称为“最后一个”的数据元素；
除第一个之外，集合中的每一个数据元素都只有一个前驱；
除最后一个之外，集合中的每一个数据元素都只有一个后继；
线性表是最简单最常用的一种线性表。
线性表分为顺序表和链表。
顺序表又分为定长顺序表和不定长顺序表。

2. 线性表的顺序表，顺序表的设计思想

加入length和左端连续。
struct SqLsit
{
int elem[10];
int length;
}SqList;
结构示意图如下:

3.实现顺序表的操作（重点）

//不定长顺序表
#include "sqlist.h"
#include <stdio.h>
#include <assert.h>

//初始化
void InitSqlist(PSQList ps)
{
	assert(ps != NULL);
	if (ps == NULL)
		return;

	ps->length = 0;
}

static bool IsFul(PSQList ps)
{
	return ps->length == 10;
}

//插入数据，在ps顺序表的pos位置插入val;
bool Insert(PSQList ps, int pos, int val)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;

	if (pos<0 || pos>ps->length || IsFul(ps))
	{
		return false;
	}
	//把数据移动到后面
	for (int i = ps->length - 1; i >= pos; i--)
	{
		ps->elem[i + 1] = ps->elem[i];
	}
	//插入数据
	ps->elem[pos] = val;
	//有效数据个数++；
	ps->length++;	
	return true;
}

//判空
bool IsEmpty(PSQList ps)
{
	return ps->length == 0;
}

//在ps中查找第一个key值，找到返回下标，没有找到返回-1；
int Search(PSQList ps, int key)
{
	for (int i = 0; i < ps->length; i++)
	{
		if (key == ps->elem[i])
			return i;
	}
	return -1;
}

//删除pos位置的值
bool DelPos(PSQList ps, int pos)
{
	assert(ps != NULL);
	if (ps == NULL)
		return false;

	if (pos<0 || pos>=ps->length)
	{
		return false;
	}
	//将后面的数据前移
	for (int i = pos; i < ps->length - 1; i++)
	{
		ps->elem[i] = ps->elem[i + 1];
	}
}

总结，数据结构的基本含义，简单来说，数据结构就是研究数据（不仅仅是数值的数据）之间的关系以及操作。顾名思义，就是数据的结构，只有你清楚了这些结构如何表现如何处理问题的，你就会发现，数据结构不仅仅拘泥于某一种语言，它更多的是一种思想理念，这样你在实际的编程中你才能运用它，使你的代码更加高效。因为你心中有它，心中有数据结构，那么只要能熟能生巧，你就会自然而然的想到使用它，从而你的代码就会更加高效。