[数据结构与算法]学习笔记：数据结构(C语言版)线性表顺序结构

第二章 线性表

2.1 线性表的基本概念

线性结构是一种最简单且最常用的数据结构。

线性结构的基本特点是节点之间满足线性关系。

1．存在唯一的一个“第一元素”；

2．存在唯一的一个**“最后元素”** ；

3．除最后元素之外，均有唯一的后继；

4．除第一个元素之外，均有唯一的前驱。

动态数组，链表，栈，队列都属于线性结构。其共同之处，是节点中有且只有一个开始节点和终端节点。按照这种关系，可以把它们的所有节点排列成一个线性序列。（他们分别属于几种不同的抽象数据类型实现）。

线性表是零个或者多个数据元素的有限数列，

数据结构之间是有顺序的，数据元素个数是有限的，数据元素的类型必须相同。

线性表的实现

• 1. 顺序存储结构
• 2. 链式存储结构

2.2 线性表顺序存储（动态数组）的设计与实现

基本操作：

1. 线性表的定义

#define LTST_INIT_SIZE 100	//线性表存储空间的初始分配量
#define LISTINCREMENT 10  //线性表存储空间的分配增量

typedef struct 
{
	int *elem;		 // 存储空间的基址(注意:数组是一块连续的内存空间)
	int length;		 //当前长度
	int listsize;	 //当前分配的存储容量
} SqList;

//对typedef的理解: typedef 是C语言关键字，可以使用它来为数据类型取一个新的名字。
typedef unsigned int u32;
typedef struct _PERSON{
	char name[64];
	int age;
}Person;

void test(){
	u32 val; //相当于 unsigned int val;
	Person person; //相当于 struct PERSON person;
}

注意：(来源于菜鸟教程)

#define 是 C 指令，用于为各种数据类型定义别名，与 typedef 类似，但是它们有以下几点不同：

• typedef 仅限于为类型定义符号名称，#define 不仅可以为类型定义别名，也能为数值定义别名，比如您可以定义 1 为 ONE。
• typedef 是由编译器执行解释的，#define 语句是由预编译器进行处理的。

2. 线性表的初始化

//初始化
//C 库函数 void *malloc(size_t size) 分配所需的内存空间，并返回一个指向它的指针
//参数：size -- 内存块的大小，以字节为单位。
//返回值：该函数返回一个指针（void*） ，指向已分配大小的内存。如果请求失败，则返回 NULL
//在 C 语言中，sizeof() 是一个判断数据类型或者表达式长度的运算符,以字节为单位。
Status InitList_Sq(SqList &L)
{
	//构造一个空的线性表 
	L.elem = (int*)malloc(LTST_INIT_SIZE*sizeof(int));
	if (!L.elem) //判断空间是否分配成功 相当于 if(L.elem==NULL)  NULL在C语言宏定义为 0/(void*)0
		exit(OVERFLOW);   
	L.length = 0;
	L.listsize = LTST_INIT_SIZE;  //当前分配的存储容量 = 线性表存储空间的初始分配量
	return OK;
}

结构销毁操作

3. 线性表的销毁

void DestroyList_Sq(SqList &L){
	if (L.elem){  //相当于if(L.elem != NULL)
		delete [] L.elem;
		L.length = 0;
		L.elem = NULL;
	}
}

//拓展知识：
//C++释放堆区数组时：delete [] 数组名
	person* pArray = new person[10];
    delete [] pArray;
//如果不加[]，则只释放第一个。

4. 线性表的清空

void ClearList(SqList &L){
	L.length = 0;
	printf("顺序表清空成功"); 
} 

//拓展知识：
//C++引用：引用变量是一个别名，也就是说，它是某个已存在变量的另一个名字。一旦把引用初始化为某个变量，就可以使用该引用名称或变量名称来指向变量。

5. 判断线性表是否为空

//判断顺序表是否为空表 
//在C89 (ANSI C）标准中没有定义与布尔类型相关的内容
//但在C99标准中新定义了一个新的关键字_Bool ，以及新增了一个头文件 <stdbool.h>规范了布尔类型的操作，方便程序员进行调用！
//但有些编译器中不支持C99类型
bool IsEmpty(SqList L){
	if(L.length==0)
		return true;
	else
		return false;
}

6. 返回数据元素的个数

typedef int Status;
//求顺序表的长度
Status GetLength(SqList L){
	return L.length;
} 

7. 给线性表元素赋值

//赋值 
Status AssignList_Sq(SqList &L)
{
	int n,m; //输入个数 
	printf("请输入集合元素个数:");
	scanf("%d",&n); 
	for(int i = 0;i < n;i++){
		printf("请输入第%d个元素:",i+1);
		scanf("%d",&m);
		L.elem[i] = m;
		L.length++;
	}
	printf("赋值成功"); 
}

8. 线性表的打印

//打印
void printf_Sq(SqList L)
{
	if(L.elem == NULL){
		printf("该顺序表已被销毁"); 
	}
	for(int i = 0; i < GetLength(L); i++){
		printf("%d ",L.elem[i]);
	}
	
	printf("\n");
}

9. 用e返回线性表中第i个元素

//用e返回L中第i个元素
Status GetElem(SqList L,int i, int &e) 
{
	if(i < 1||i > GetLength(L))
		return ERROR;
	
	e = L.elem[i-1];
	return OK;
}

10. 在表中查找第一个值与e满足compare()元素的位序

Status equal_e(int a,int b)
{
	if(a==b)
		return OK;
	else
		return ERROR;
}

//在表中查找第一个值与e满足compare()元素的位序 
Status LocateElem(SqList L, int e,int (*compare)(int,int)){
	int i = 1;
	//int *p = L.elem; 
	while(i<=GetLength(L)&&!(*compare)(L.elem[i-1],e)){  //*p++
		++i;
	}
	if(i<=GetLength(L))
		return i;
	else
		return 0;
}

//拓展知识:函数指针
//函数指针做函数参数(回调函数)

拓展知识：函数指针(指向函数的指针)

函数指针定义方式(先定义函数类型，根据类型定义指针变量);

先定义函数指针类型，根据类型定义指针变量;

直接定义函数指针变量;

int my_func(int a,int b){
	printf("ret:%d\n", a + b);
	return 0;
}

//1. 先定义函数类型，通过类型定义指针
void test01(){
	typedef int(FUNC_TYPE)(int, int);
	FUNC_TYPE* f = my_func;
	//如何调用？
	(*f)(10, 20);
	f(10, 20);
}

//2. 定义函数指针类型
void test02(){
	typedef int(*FUNC_POINTER)(int, int);
	FUNC_POINTER f = my_func;
	//如何调用？
	(*f)(10, 20);
	f(10, 20);
}

//3. 直接定义函数指针变量
void test03(){
	int(*f)(int, int) = my_func;
	//如何调用
	(*f)(10, 20);
	f(10, 20);
}

函数指针做函数参数(回调函数)

函数参数除了是普通变量，还可以是函数指针变量。

 //形参为普通变量  
void fun(int x ){}
 //形参为函数指针变量  
void fun(int(*p)(int a)){} 

函数指针变量常见的用途之一是把指针作为参数传递到其他函数，指向函数的指针也可以作为参数，以实现函数地址的传递。

11. 获取顺序表指定元素的后继

//获取顺序表指定元素的后继
Status Next_elem(SqList L,int i,int &e){
	if(i<1||i>L.length){
		return ERROR;
	}
	if(i==GetLength(L)){
		printf("最后一个元素没有后继");
		return ERROR; 
	}
	
	e = L.elem[i];
} 

12. 获取顺序表指定元素的前驱

//获取顺序表指定元素的前驱 
Status Prior_elem(SqList L,int i,int &e){
	if(i<1||i>L.length){
		return ERROR;
	}
	if(i==1){
		printf("第一个元素没有前驱");
		return ERROR; 
	}
	
	e = L.elem[i-2];
} 

13. 插入算法实现

//在顺序表中插入指定的元素
Status ListInsert_Sq(SqList &L,int i,int e){
	if(i<1||i>GetLength(L)+1)
		return ERROR;
	if(GetLength(L)>=L.listsize){
		int *newspace = (int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int)); //重新分配内存空间 
		if(!newspace){
			exit(OVERFLOW);
		} 
		L.elem = newspace;
		L.listsize+=LISTINCREMENT;            
	}
	
//书上的 
//	int *q,*p;
//	q = &(L.elem[i-1]);
//	for(p=&(L.elem[L.length-1]);p>=q;p--)
//		*(p+1)=*p;
//	*q=e;
//	++L.length;
//	return OK;
	int k,j;
	for(k = 0,j=L.length-1;j>=k;k++,j--){
		L.elem[j+1] = L.elem[j];
	} 
	L.elem[k] = e;
	++L.length;
	return OK;
	
} 

考虑移动元素的平均情况:

假设在第 i 个元素之前插入的概率为,则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为：
在这里插入代码片
若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：

14. 删除算法实现

//删除顺序表指定位置元素
Status DeleteList_Sq(SqList &L,int i,int &e)
{
    int j=0;
    if(i<1||i>L.length)
    {
        return ERROR;;
    }
    else
    {
    	e = L.elem[i-1];
        for(j=i; j<=L.length-1; j++)
        {
            L.elem[j-1]=L.elem[j];
        }
        --L.length;
    }

}

考虑移动元素的平均情况:

假设删除第 i 个元素的概率为， 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为：

若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：

15. 并集

//并集A+B 
Status union_set(SqList La,SqList Lb,SqList &Lc){
	int La_Len = GetLength(La);
	int Lb_Len = GetLength(Lb);
	int e;
	for(int i=1;i<=Lb_Len;i++){
		GetElem(Lb,i,e);
		if(!LocateElem(La,e,equal_e))
			ListInsert_Sq(La,++La_Len,e);
	}
	
	for(int i =0;i<=La_Len;i++){
		GetElem(La,i,e);
		ListInsert_Sq(Lc,i,e);
	}
}

16. 交集

//交集AB 
Status mixture_set(SqList La,SqList Lb,SqList &Lc){
	int La_Len = GetLength(La);
	int Lb_Len = GetLength(Lb);
	int e;
	int index = 0;
	SqList p,q;
	if(La_Len >= Lb_Len){
		p = Lb;
		q = La;
	}
	else{
		p = La;
		q = Lb;
	}
	//p = La_len <= Lb_len ? La:Lb;
	//q = La_len > Lb_len ? La:Lb; 
	
	for(int i=1;i<=GetLength(p);i++){
		GetElem(p,i,e);
		if(LocateElem(q,e,equal_e))
			ListInsert_Sq(Lc,++index,e);
	}
	
	if(GetLength(Lc))
		return OK;
	else
		return ERROR;
}

17. 差集

//差集A-B
Status different(SqList La,SqList Lb,SqList &Lc)
{
    int La_len=GetLength(La);
    int e;
    int index=0;
    for(int i=1; i<=La_len; i++)
    {
        GetElem(La,i,e);
        if(!LocateElem(Lb,e,equal_e))
            ListInsert_Sq(Lc,++index,e);
    }
    if(GetLength(Lc))
        return OK;
    else
        return ERROR;
} 

18. 逆转

//逆转
Status ReverseList_Sq(SqList &L){
    int mid = (L.length-1)/2;
    for(int i=0; i<=mid; i++){
        int tmp = L.elem[i];
        L.elem[i] = L.elem[L.length-1-i];
        L.elem[L.length-1-i] = tmp;
    }
}

小张学长呕心沥血之作，若有错误之处请多多指正。若有帮助，可以点赞关注哦！！！