章贡区综合网站建设商家,中国知名网站排名,制作一个网站代码,上海高端网站建设定制1.线性表的定义和基本操作
1.1线性表以及基本逻辑
1.1.1线性表
#xff08;1#xff09;n(0)个数据元素的有限序列#xff0c;记作#xff08;a1,a2,...an#xff09;#xff0c;其中ai是线性表中的数据元素#xff0c;n是表的长度。
#xff08;2#xff09;…1.线性表的定义和基本操作
1.1线性表以及基本逻辑
1.1.1线性表
1n(0)个数据元素的有限序列记作a1,a2,...an其中ai是线性表中的数据元素n是表的长度。
2ai是线性表中“第i个”元素在线性表中的位序。 注意数组下标从0a[0]开始位序从1开始. 1.1.2逻辑特征n0
存在唯一的一个被称为“第一个”的数据元素。
存在唯一的一个被称为“最后一个”的数据元素。
除了第一个元素以外其他元素均只有一个直接前驱。
除了最后一个元素外其他元素均只有一个直接后继。
1.2线性表的基本操作 InitList(L) //创建一个新的线性表L ListEmpty(L) //判断L是否为空 ListLength(L) //求L的长度 GetElem(L,i,e) //取i位置数据元素的值 ClearList(L) //将L置为空表 ListInsert(L,i,e) //在i位置插入值为e的数据元素 ListDelete(L,i,e) //删除i位置的元素e 1.ListInsert(L,i,e) 传值 2.ListDelete(L,i,e)传引用 3.ListDelete(L,i,*e)传指针 1.形参改变-不会影响实参 2.3.形参改变-会影响实参传引用传指针 下面用一张图来介绍形参和实参的区别by 通义千问 传引用适用场景 1.需要函数修改原始数据。 2.对于大型数组或对象为了节省内存开销和提升运算效率使用引用传递。 一句话对参数的修改结果要“带回来”。 2.线性表的顺序表示
2.1线性表和顺序表的定义
1线性表线性表是具有相同数据类型的n(n0)个数据元素的有限序列。
2顺序表用顺序的方式实现线性表的顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中元素之间的关系由存储单元的邻接关系来体现。
2.2静态分配和动态分配
2.2.1静态分配
#define MAX 10
int arr[MAX];
int n; //数据元素个数小于n个
结构体进行封装
#define MAX 100
typedef struct
{ElemType elem[MAX];int n;
}Sqlist;
2.2.2动态存储
1动态申请和释放内存空间
2C语言--malloc,free函数
L.data(ElemType *)malloc(sizeof(ElemType)*InitSize)
//malloc函数返回一个指针需要用“(ElemType *)”强制类型转化为自己定义的数据元素类型指针
2.2.3顺序表基本操作实现
1.初始化顺序表InitList_Sq(L)
操作结果构造一个空的顺序表L.
Status InitList_Sq(SqListL) // 定义一个函数名为 InitList_Sq 的函数参数是对 SqList 类型的引用 L返回类型为 Status这里 Status 可能是一个自定义的表示状态的类型
{L.elem(ElemType*)malloc(initial_size*sizeof(ElemType)); // 为 L 的 elem 属性分配一块内存空间大小为 initial_size 个 ElemType 类型元素所需的空间并将其地址转换为 ElemType*类型赋给 L.elemif(!L.elem) // 如果分配内存失败L.elem 为假即内存分配不成功得到的是 null 指针等情况exit(OVERFLOW); // 退出程序并表示存储空间分配失败OVERFLOW 可能是一个表示溢出或错误的常量L.length0; // 将顺序表 L 的当前长度设置为 0L.listsizeinitial_size; // 将顺序表 L 的初始容量设置为 initial_sizereturn 0; // 返回一个状态值这里可能表示成功初始化
}
下面是对顺序表中长度和容量的解释 在顺序表Sequential List中 一、长度length 指的是顺序表中当前实际存储的元素个数。 例如如果有一个顺序表存储了 5 个整数那么这个顺序表的长度就是 5。随着向顺序表中添加或删除元素长度会相应地发生变化。 二、容量listsize 指的是顺序表预先分配的能够存储元素的最大空间大小。 例如一开始创建顺序表时可能分配了一块可以存储 10 个整数的连续内存空间那么此时这个顺序表的容量就是 10。当顺序表中的元素个数达到容量时如果要继续添加元素通常需要进行扩容操作重新分配更大的连续内存空间。而如果顺序表中的元素个数远小于容量那么就存在一部分未被使用的内存空间。 2.销毁顺序表DestroyList_Sq(L):
释放L所占用的内存空间
void DestroyList_Sq(SqList L)
{free(L.elem); // 释放顺序表 L 的存储数据的内存空间。free 函数用于释放由 malloc、calloc 或 realloc 等函数分配的动态内存。L.elem NULL; // 将 L 的 elem 指针设置为 NULL避免出现悬空指针。L.length 0; // 将顺序表的长度设置为 0表示表中没有元素。L.listsize 0; // 将顺序表的容量设置为 0。
}
3.判定是否为空表 ListEmpty_Sq(L):
若L为空表返回1否则返回0
int ListEmpty_Sq(SqList L)
{if (L.length0)return 1;else return 0;
4.输出顺序表 DispList_Sq(L):
操作结果当L不为空时顺序显示L中各个元素的值。
Status DispList_Sq(SqList L)
{if (ListEmpty_Sq(L))return ERROR;// 如果顺序表为空通过调用 ListEmpty_Sq 函数判断则返回 ERROR可能是一个表示错误的状态码。for(i0;iL-1;i){print(L.elem[i]);}// 如果顺序表不为空遍历顺序表从第一个元素下标为 0开始直到最后一个元素下标为 L-1逐个打印顺序表中的元素。return OK;// 遍历完成后返回 OK可能是一个表示成功的状态码。
}
5.插入数据元素 ListInsert_Sq(L,i,e):
操作结果在顺序表L的第i个位置前插入新元素e.
ListInsert_Sq(SqList L, int i, ElemType e)
{if (i 1 || i L.length 1) {return ERROR;}// 判断插入位置 i 是否合法i 应该在 1 到当前顺序表长度 1之间否则返回错误状态码 ERROR。if (L.length L.listsize) {newbase (ElemType*)malloc(L.elem,(L.listsize ElemNumber)*sizeof(ElemType));L.elem newbase;L.listsize ElemNumber;}// 如果当前顺序表中已存储的元素个数L.length等于或超过了顺序表的容量L.listsize则进行扩容操作。// 分配一块新的内存空间大小为原来的容量加上 ElemNumber 个 ElemType 类型元素所需的空间然后将新分配的内存地址赋给 L.elem并更新顺序表的容量 L.listsize。for (j L.length; j i; j--) {L.elem[j] L.elem[j - 1];}// 将插入位置 i 及之后的元素向后移动一位。L.elem[i - 1] e;// 在插入位置 i 处放入新元素 e。L.length;// 顺序表长度加一。return 1;// 返回一个表示成功的状态码这里是 1。
} 时间复杂度 -最好情况新元素插到表尾不需要移动元素in1,循环0次T(n)O(1); -最坏情况新元素插到表头需要将原有的n个元素全部向后移动i1,循环n次T(n)O(n); -平均情况,新元素插入到任意一个位置概率相同需要的时间是n/2考虑到时间复杂度量级T(n)O(n). 6.删除数据元素 ListDelete_Sq(L,i,e):
操作结果删除顺序表L中的第i个元素用引用变量e返回删除的元素。 ListInsert_Sq(SqList L, int i, ElemType e)
{if (i 1 || i L.length) {return ERROR;}// 判断插入位置 i 是否合法。i 应该在 1 到顺序表的当前长度之间如果不合法则返回错误状态码 ERROR。e L.elem[i - 1];// 将顺序表中位置 i 处的元素赋值给参数 e。for (j i; j L.length; j) {L.elem[j - 1] L.elem[j];}// 从位置 i 开始将后面的元素依次向前移动一位。--L.length;// 顺序表的长度减一表示删除了一个元素。return 1;// 返回一个表示成功的状态码这里是 1。
} 时间复杂度 -最好情况T(n)O(1); -最坏情况T(n)O(n); -平均情况T(n)O(n). 7.按位查找操作 GetElem(L,i):
操作结果获取表L中的第i个位置元素的值。
ElemType GetElem(SeqList L,int i)
{return L.data[i-1];
} 时间复杂度O1 8.按值查找操作 LocateElem(L,e):
操作结果在表L中查找具有给定关键字值的元素第一个。
//在顺序表L中查找第一个元素值等于e的元素并返回其位序
int LocateElem(SeqList L,ElemType e)
{for(int i0;iL.length-1;i){if(L.data[i]e){return i1;}}return 0;
} 时间复杂度 -最好情况目标元素子啊表头循环1次T(n)O(1); -最坏情况目标元素在表尾循环n次T(n)O(n); -平均情况目标元素出现在任何一个位置的概率相同T(n)O(n). 下面是链表敬请期待...
