当前位置:首页 » 《关注互联网》 » 正文

学习笔记:数据结构(C语言版)线性表顺序结构_m0_52344565的博客

19 人参与  2022年01月13日 14:16  分类 : 《关注互联网》  评论

点击全文阅读


第二章 线性表

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

在这里插入图片描述
小张学长呕心沥血之作,若有错误之处请多多指正。若有帮助,可以点赞关注哦!!!


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/33183.html

元素  函数  指针  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1