02_线性表_顺序表

2 线性表

线性表：（顺序表，单链表，静态链表，栈，队列，串）
有唯一的头，有唯一的尾；其他任意一个节点都有一个直接前驱和一个直接后继

顺序表： 逻辑相邻物理也相邻（类似一维数组）但是和数组有区别
顺序表与数组的区别：

数组只支持2个操作：向数组中放数据，从数组中取数据，一维数组是一个特殊的顺序表

顺序表支持多种操作：插入，删除…



问题： 向顺序表中插入数据需要挪动其位置后的数据，但是如何判断其位置后有没有数据

普通解决方法： C语言中只能判断变量中是否有值，不能判断是否是有效值；
(1) ’ \0’ 是字符串结束的标志，故只能用来判断字符串
(2) arr[i] ! = 0 ;若用此方法，则’ 0 '表示无效值，数组中不能存放有效值 ‘ 0 ’
正确解决方法： 此时需要人为的加入一个标记：定义一个计算器，记录有效数据的个数

2.1 顺序表：适合查询

2.1.1 定长顺序表

//顺序表，固定长度：非常简单，但是不实用
typedef struct SQList//把一种数据类型起一种新的别名为SQList
{
    
	int elem[10];//存放数据，固定长度为10
	int length;//有效数据的个数;此时插入数据时物理位置必须连续，无论插入多少个数据,length始终为一个数字，故空间复杂度为O(1);
               //若插入数据时不连续，则每插入一个数据都要有标记。此时空间复杂度为O（n）;
}SQList,
*PSQList;//结构体指针：
//等价于 typedef struct SQList* PSQList;结构体指针起个别名叫PSQList


//初始化
void InitSqList(PSQList ps)//PSQList==SQList *
{
    
	assert(ps != nullptr);//断言只在Debug模式下有效：Debug是程序员开发版本，有调试信息
	if (ps == nullptr)    //在Release模式下依然有效：Release是发行版本，代码优化过，编译器自动删除了所有调试信息
	{
    
		return;
	}
	ps->length = 0;//有效数据个数为0，故不需要将数组中10个元素初始化为0；
}

//判断被插入数组是否满
static bool IsFul(PSQList ps)
{
    
	return ps->length == 10;
}

//在ps顺序表的pos位置标插入数据val
//插入的数据必须左边连续
void Insert(PSQList ps, int pos, int val)
{
    
	assert(ps != nullptr);//断言只在Debug模式下有效：Debug是程序员开发版本，有调试信息
	if (ps == nullptr)    //在Release模式下依然有效：Release是发行版本，代码优化过，编译器自动删除了所有调试信息
	{
    
		return ;
	}
	if (pos<0 || pos>ps->length|| IsFul(ps))
	{
    
		return ;
	}
	//移动后面的数据
	for (int i = ps->length - 1;i >= pos;i--)
	{
    
		ps->elem[i + 1] = ps->elem[i];
	}
	//插入新的数据
	ps->elem[pos] = val;
	//有效数据个数+1；
	ps->length += 1;

}

//输出顺序表
void Show(PSQList ps)
{
    
	for (int i = 0;i < ps->length;++i)
	{
    
		printf("%d", ps->elem[i]);
		printf(" ");
	}
	printf("\n");
}

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

//在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;
	}
}


//在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; }*/

	/*int pos = -1; int i = 0; while (i < ps->length && key != ps->elem[i]) { i++; } if (i < ps->length) { pos = i; } return pos;*/

	int pos = ps->length - 1;
	while (pos>=0 && key != ps->elem[pos])
	{
    
		--pos;
	}
	return pos;
}


//删除pos位置的值
bool DelPos(PSQList ps, int pos)
{
    
	//判断pos位置是否合法
	if (pos < 0 || pos >= ps -> length)
	{
    
		return false;
	}
	//将后面的数据前移
	//for (int i = pos;i < ps->length;i++)
	for (int i = pos;i < ps->length-1;i++)
	{
    
		ps->elem[i] = ps->elem[i + 1];//遇见i+1需要考虑越界
	}
	ps->length--;
	return true;
}

//删除第一个val值
bool DelVal(PSQList ps, int val)
{
    
	int i = Search(ps, val);
	if (i < 0)
	{
    
		return false;
	}
	return DelPos(ps, i);
}

//返回key的前驱下标，如果不存在返回-1；
int GetPrio(PSQList ps, int key)
{
    
	int i = Search(ps, key);
	if (i <= 0)//注意头没有前驱
	{
    
		return-1;
	}
	return i - 1;
}

//返回key的后继下标，如果不存在返回-1；
int GetNext(PSQList ps, int key)
{
    
	int i = Search(ps, key);
	if (i< 0 || i==ps->length - 1)//注意尾巴也没有后继
	{
    
		return-1;
	}
	return i + 1;
}

//清空数据
void Clear(PSQList ps)
{
    
	ps->length = 0;
}

//销毁整个内存(动态内存)
void Destory(PSQList ps)
{
    
	Clear(ps);//此例子没有开辟动态内存
}

2.1.2 不定长顺序表

类型改变如下：

顺序表冒泡排序

代码优化：若数据本身就有序，直接退出循环

//顺序表，长度不固定（容量满了可以自动增长）
typedef struct DSQList//把一种数据类型起一种新的别名为SQList
{
    
	int* elem;//动态内存的地址，因为用malloc,所以返回就是一个地址，想存一个整型值，数组存放整型值，所以返回一个整型的指针
	//书上定义的是ElemType*elem;目的是为了解决泛型（int，char...)
	//C语言解决泛型用：函数指针；C++解决泛型用：模板
	int length;//有效数据的个数;
	int listsize;//总容量
}DSQList,
* DPSQList;//结构体指针：
//等价于 typedef struct DSQList* DPSQList;结构体指针起个别名叫DPSQList

//初始化,动态创建初始容量
void InitDSqList(DPSQList ps)
{
    
	assert(ps != nullptr);
	if(ps==nullptr)
	{
    
		return;
	}
	ps->elem = (int*)malloc(INIT_SIZE * sizeof(int));//对比STL中容器的初始化为0
	ps->length = 0;//有效数据个数
	ps->listsize = INIT_SIZE;//总容量
}

//判断被插入数组是否满
static bool IsFul(DPSQList ps)//内部使用不对外提供服务故为静态函数
{
    
	return ps->length == INIT_SIZE;
}

//容量增长函数，容量变为原来的2倍（STL中有可能是2倍或1.5倍）
//1.5倍更好。因为当前面的空间释放之后，后面重新申请空间时可以利用到前面释放的空间
// 10 15 23 35 53 ... 当第2次扩容申请23个空间时就可以利用前面释放的10+15=25个空间（如果空间连续的话）

//10 20 40 ... 如果扩容2倍，前面释放的空间无法重新利用
static bool Inc(DPSQList ps)
{
    
	ps->elem = (int*)realloc(ps->elem, ps->listsize * 2 * sizeof(int));
	assert(ps->elem != NULL);
	ps->listsize *= 2;
	//ps->length;不变
	return true;
}
//在ps顺序表的pos位置标插入数据val
bool Insert(DPSQList ps, int pos, int val)
{
    
	if (pos<0 || pos> ps->length)
	{
    
		return false;
	}
	if (IsFul(ps))
	{
    
		Inc(ps);
	}
	//移动后面的数据
	for (int i = ps->length - 1;i >=pos;i--)
	{
    
		ps->elem[i + 1] = ps->elem[i];
	}
	//插入新的有效数据
	ps->elem[pos] = val;
	//有效数据个数+1
	ps->length++;
	return true;
}

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

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

//删除pos位置的值
bool DelPos(DPSQList ps, int pos)
{
    
	//判断pos位置是否合法
	if (pos < 0 || pos >= ps->length)
	{
    
		return false;
	}
	//将后面的数据前移
	//for (int i = pos;i < ps->length;i++)
	for (int i = pos;i < ps->length - 1;i++)
	{
    
		ps->elem[i] = ps->elem[i + 1];//遇见i+1需要考虑越界
	}
	ps->length--;
	return true;
}

//删除第一个val值
bool DelVal(DPSQList ps, int val)
{
    
	int i = Search(ps, val);
	if (i < 0)
	{
    
		return false;
	}
	return DelPos(ps, i);
}

//删除所有val值
bool Del_All_Val(PDSQList ps, int val)
{
    
	int i, j = 0;
	while (j < ps->length)
	{
    
		if (ps->elem[j] != val)
		{
    
			ps->elem[i] = ps->elem[j];
			++i;
		}
		++j;
	}
	ps->length = i;
}

//返回key的前驱下标，如果不存在返回-1；
int GetPrio(DPSQList ps, int key)
{
    
	int i = Search(ps, key);
	if (i <= 0)//注意头没有前驱
	{
    
		return-1;
	}
	return i - 1;
}

//返回key的后继下标，如果不存在返回-1；
int GetNext(DPSQList ps, int key)
{
    
	int i = Search(ps, key);
	if (i < 0 || i == ps->length - 1)//注意尾巴也没有后继
	{
    
		return-1;
	}
	return i + 1;
}

//输出顺序表
void Show(DPSQList ps)
{
    
	for (int i = 0;i < ps->length;++i)
	{
    
		printf("%d", ps->elem[i]);
		printf(" ");
	}
	printf("\n");
}

//清空数据
void Clear(DPSQList ps)
{
    
	ps->length = 0;
}

//销毁整个内存
void Destory(DPSQList ps)
{
    
	free(ps->elem);
	ps->elem = NULL;//ps->elem==(*ps).elem
	ps->length = 0;
	ps->listsize = 0;
	ps = NULL;//无效代码
}

ps = NULL;为何为无效代码
因为将 ps 置空，仅仅改变了ps指向，并没有解引用（* ps）,所以指针 elem 指向的顺序表并没有销毁

顺序表的特点：
1.插入数据的时间复杂度是O（n);如果是尾插时间复杂度是O（1）

	for (int i = ps->length - 1;i >=pos;i--)
	{
    
		ps->elem[i + 1] = ps->elem[i];
	}

2.删除数据的时间复杂度是O（n);如果是尾删时间复杂度为O（1）
3.通过下标访问数据，时间复杂度为O（1）
4.简单