学习笔记|学习笔记(数据结构(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 ,以及新增了一个头文件 规范了布尔类型的操作,方便程序员进行调用! //但有些编译器中不支持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; }

【学习笔记|学习笔记(数据结构(C语言版)线性表顺序结构)】考虑移动元素的平均情况:
假设在第 i 个元素之前插入的概率为,则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为:
在这里插入代码片学习笔记|学习笔记(数据结构(C语言版)线性表顺序结构)
文章图片

若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的期望值为:
学习笔记|学习笔记(数据结构(C语言版)线性表顺序结构)
文章图片

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 的线性表中删除一个元素所需移动元素次数的期望值为:
学习笔记|学习笔记(数据结构(C语言版)线性表顺序结构)
文章图片

若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的期望值为:
学习笔记|学习笔记(数据结构(C语言版)线性表顺序结构)
文章图片

学习笔记|学习笔记(数据结构(C语言版)线性表顺序结构)
文章图片

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

学习笔记|学习笔记(数据结构(C语言版)线性表顺序结构)
文章图片

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

    推荐阅读