[数据结构与算法]数据结构学习笔记-线性表

线性表

Ptrl == Pointer

顺序存储结构定义

#define MaxSize 100
struct LNode {
	int data[MaxSize];//容量为100的顺序线性表
	int Last;//最后一个元素的下标
};
typedef struct LNode* List;//结构体类型的指针，指向结构体
List PtrL;//线性表结构的指针

初始化

C

List MakeEmpty() {
	List PtrL;
	PtrL = (List)malloc(sizeof(struct LNode));
	PtrL-> Last = - 1; //0表示有一个元素,-1表示没有元素
	return PtrL;
}

C++

List MakeEmpty(){
    List Ptrl;
    Ptrl = (List)new SqList;
    Ptrl->Last = -1;
    return Ptrl;
}

最简单的一个函数

插入（增）

void Insert(int X,int i, List PtrL) {
	int j;
	if (PtrL->Last == MaxSize - 1) // 是否表满
	//长度为5,下标自然等于(MaxSize)5-1,也就是4
	{
		cout << "表满了";
		return;
	}
	if ( i < 1 || i > PtrL->Last + 2 ) //插入位置是否合法
	{
		//长度为5的话，Last范围0-4，
		//表空Last=-1，插入第一个元素i=1,1>1(-1+2),满足条件，可以插入
		//表差一个元素满Last=3，i=5，5>5(3+2)，满足条件，可以插入
		cout << "位置不合法!";
		return;
	}
	for (j = PtrL->Last; j >= i-1;j--)
	{
		PtrL->data[j + 1] = PtrL->data[j];//所有元素向后移动一位
		//如果长度为,下标为0 1 2 3,插入元素到第二个位置(下标为1)
		//向2插入元素,Last==3,i = 2
		//data[3] = data[2],data[2] = data[1]
		//理所当然地把X放到下标为i-1的第二个位置中
	}
	PtrL->data[i - 1] = X;//向2插入元素,Last==3,i = 2
	PtrL->Last++;
	//Last是最后一个元素的下标
	//因为插入了一个元素,Last仍要指向最后一个元素,所以Last++
	return;
}

个人认为容易卡住而写不出来的一些地方

位序i与下标之间的对应关系

位序=下标+1

越界的判断条件，i的合法范围从1~Last+2

长度为5的话，Last范围0-4，
表空：Last=-1，插入第一个元素，i=1,1>1(-1+2),满足条件，可以插入
表差一个元素满：Last=3，i=5，5>5(3+2)，满足条件，可以插入

移动元素的下标

如果长度为4,下标为0 1 2 3

插入元素到第二个位置(下标为1)

向i=2插入元素,Last==2,j=2

dataj+1 = data[2],j–(2)

data[2] = data[1]

理所当然地把X放到下标为i-1的第二个位置中

void Insert(int X,int i, List PtrL) {
	int j;
	if (PtrL->Last == MaxSize - 1) // 是否表满
	//长度为5,下标自然等于(MaxSize)5-1,也就是4
	{
		cout << "表满了";
		return;
	}
	if ( i < 1 || i > PtrL->Last + 2 ) //插入位置是否合法
	{
		//长度为5的话，Last范围0-4，
		//表空Last=-1，插入第一个元素i=1,1>1(-1+2),满足条件，可以插入
		//表差一个元素满Last=3，i=5，5>5(3+2)，满足条件，可以插入
		cout << "位置不合法!";
		return;
	}
	for (j = PtrL->Last; j >= i-1;j--)
	{
		PtrL->data[j + 1] = PtrL->data[j];//所有元素向后移动一位
		//如果长度为4,下标为0 1 2 3,插入元素到第二个位置(下标为1)
		//向i=2插入元素,Last==2,j=2
		//data[j+1](3) = data[2],j--(2)
		// data[2] = data[1]
		//理所当然地把X放到下标为i-1的第二个位置中
	}
	PtrL->data[i - 1] = X;//向2插入元素,Last==3,i = 2
	PtrL->Last++;
	//Last是最后一个元素的下标
	//因为插入了一个元素,Last仍要指向最后一个元素,所以Last++
	return;
}

删除（删）

个人认为容易卡住而写不出来的一些地方

越界条件与插入不同，因为插入肯定有一个元素是空的，再加上下标与位序相差1，所以i>L->Last+2

而删除，只存在位序差1，所以i>L->Last+1

void Delete(int i,List PtrL) {
	int j;
	if ( i < 1  || i > PtrL->Last+1 )
	//长度为4 下标 0 1 2 3,Last==3
	//删除第4个元素,i==4,下标为3
	//如果i(4)>Last+1(3+1),则位置合法
	{
		cout << "不存在第%d个元素" << i;
		return;
	}
	for ( j=i ;j < PtrL->Last;j++)
	{
		PtrL->data[j - 1] = PtrL->data[j];
		//长度为4,下标0 1 2 3 ,Last = 3
		//删除第i=2个元素,下标为1,所以j=i(2)
		//之后把data[j]第三个元素数据直接赋值给第二个元素data[j-1],j++
		//第四个元素data[j]的数据直接给第三个元素data[j-1]
	}
	PtrL->Last--;
	//指向最后一个元素
	return;
}

查询（查）

int Find(List PtrL,int X) {
	int i = 0;
	while ( i <= PtrL->Last && PtrL -> data[i]!= X)
	{
		i++;
		if (i > PtrL->Last)
			return -1; //没找到,返回-1
		else 
			return i;//找到了返回下标(位置)
	}
}