做论坛app网站有哪些,开发购物网站,网站建设格式合同,上海知名网站建顺序结构的基本理解
定义#xff1a; 把逻辑上相邻的数据元素存储在物理上相邻#xff08;占用一片连续的存储单元#xff0c;中间不能空出来#xff09;的存储单元的存储结构 存储位置计算#xff1a; LOC(a(i1))LOC(a(i))lLOC(a(i1))LOC(a(i))l LOC(a(i1))LOC(a(i))l L…顺序结构的基本理解
定义 把逻辑上相邻的数据元素存储在物理上相邻占用一片连续的存储单元中间不能空出来的存储单元的存储结构 存储位置计算 LOC(a(i1))LOC(a(i))lLOC(a(i1))LOC(a(i))l LOC(a(i1))LOC(a(i))l
LOC(a(i))LOC(a(j))(i−j)lLOC(a(i))LOC(a(j))(i-j)l LOC(a(i))LOC(a(j))(i−j)l
其中lll为每个元素所需要占用的存储单元
顺序表的优点 以物理位置相邻表示逻辑关系任意元素均可随机存取
顺序表的顺序存储表示
【地址连续、依次存放、随机存取、类型相同】数组元素
所以我们可以用一维数组来表示顺序表。但是顺序表长是可以变化的而数组长度是不可变的所以我们会额外使用一个变量来表示当前位置在顺序表中的长度
# define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
typedef struct{ ElemType elem[LIST_INIT_SIZE]; int lenth; //当前长度
}SqList 注意逻辑位序和物理位序相差1因为数组第一项是a[0]
例子多项式的顺序存储结构类型定义 P(x)AxaBxbCxc⋅⋅⋅Z(i)xzP(x)Ax^aBx^bCx^c···Z(i)x^z P(x)AxaBxbCxc⋅⋅⋅Z(i)xz 其线性表为 P((A,a),(B,b),(C,c),...,(Z,z))P ( ( A , a ) , ( B , b ) , ( C , c ) , . . . , ( Z , z ) ) P((A,a),(B,b),(C,c),...,(Z,z))
# define MAXSIZE 1000
typedef struct{ //多项式非零项的意义 float p; //系数 int e; //指数
}Polynomial
typedef struct{ Polynomial *elem; //存储空间的基地址 int length; //多项式中当前项的系数
}SqList //多项式的顺序存储结构类型为SqList 补充
补充1数组静态与动态的区别
数组静态分配数组动态分配typedef struct{typedef struct{ElemType data[maxsize];**ElemType *data **int length;int length;}SqList//顺序表类型}SqList//顺序表类型
在数组的静态分配中data[maxsize]本质上存储的是data[0]的地址而*data这个指针存储的也是地址本质上相同。而数组动态分配是由申请储存空间完成的
SqList L;
L.data (ElemType*)malloc(sizeof(ElemType)×Maxsize) 补充2常用函数
需要加载头文件stdlib.h
malloc(m)函数开辟m字节长度的地址空间并返回这段空间的首地址
sizeof(x)运算计算变量x的长度
free§函数释放指针p所指变量的存储空间即彻底删除一个变量
(ElemType*)malloc···强制转换类型方法
补充3a与b的交换问题
引用类型做参数(C)
int i5;
int ji;
j是一个引用类型i的值改变的时候j的值也会随之发生变化
比如交换ab的函数可以有如下两种方式
| 利用指针类型 | 利用引用类型 |
| ----------------------------- | --------------------------- |
| #include iostream.h | #include iostream.h |
| void swap(float *m,float *n){ | void swap(floatm,floatn){ |
| float temp; | float temp; |
| temp *m; | tempm; |
| *m *n; | mn; |
| *n temp; | ntemp; |
| } | } |
| void main(){ | void main(){ |
| float a,b, *p1, *p2; | float a,b; |
| cinab; | cinab; |
| p1a; p2b; | swap(a,b); |
| swap(p1,p2); | countaendlbendl; |
| countaendlbendl; | } |
| } | |补充4宏定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
补充5内存相关
软件CC获取内存mallocnew释放内存freedelete基本操作的实现
线性表初始化InitList(L)
操作结果构造一个空的线性表L
C:
C: 线性表销毁DestoryList(L)
初始条件线性表L已经存在
操作结果销毁线性表L
C: C: C(1): 线性表清空ClearList(L)
初始条件线性表L已经存在
操作结果将线性表L重置为空表
C: C: 线性表清空判断ListEmpty(L)
初始条件线性表L已经存在
操作结果若线性表L为空表则返回TRUE;否则返回FALSE
C: C: 线性表长度ListLength(L)
初始条件线性表L已经存在
操作结果返回线性表L中的数据元素个数
C:
C: 线性表查找GetElem(L,i,e)
初始条件线性表L已经存在1≤i≤ListLength(L)
操作结果用e返回线性表L中第i个数据元素的值
C:
C: 线性表定位LocateElem(L,e,compare())
**初始条件**线性表L已经存在compare()是数据元素的判定函数
**操作结果**返回L中第1个与e满足compare()的数据元素的位序。这样的元素不存在则返回值为0
C C: 算法分析
频度平均查找长度为期望值为 (123456⋅⋅⋅n−1n)/n(n1)/2(123456···n-1n)/n(n1)/2 (123456⋅⋅⋅n−1n)/n(n1)/2 拓展一下 上图的情况就是当查找概率都相等时的结果。 线性表元素插入ListInsert(L,i,e)
初始条件线性表L已经存在1≤i≤ListLength(L)1
操作结果在L的第i个位置插入新的数据元素eL的长度加一
算法思想
1判断插入位置i是否合法。
2判断顺序表的存储空间是否已满若已经满了返回ERROR
C:
算法分析 插入的位置有如下三种情况
① 插在位置最后则根本不需要移动速度较快
② 插在位置中间则需要移动一定数量的元素速度适中
③ 插在位置最前则需要将表中所有元素后移速度很慢
那么平均的情况如何
我们知道总共有n1个插入位置第i个插入位置需要移动n-i1次则 (123456⋅⋅⋅n−1n)/(n1)n/2(123456···n-1n)/(n1)n/2 (123456⋅⋅⋅n−1n)/(n1)n/2 线性表元素删除ListDelete(L,i,e)
初始条件线性表L已经存在1≤i≤ListLength(L)
操作结果删除L的第i个数据元素并用e返回其值L的长度减一
算法思想
① 判断删除位置i是否合法合法值1≤i≤n
② 将欲删除的元素保留在e中
③ 将第i1至第n位的元素依次向前移动一个位置
④ 表长减1删除成功返回OK
C: C:
算法分析此处的分析与线性表元素的插入十分类似 (123456⋅⋅⋅n−1)/n(n−1)/2(123456···n-1)/n(n-1)/2 (123456⋅⋅⋅n−1)/n(n−1)/2 顺序表总结
优点
· 存储密度大结点本身所占储存量/结点结构所占存储量
· 可以随机存取表中任意元素
缺点
· 插入删除某元素时需要移动大量元素
· 浪费存储空间
· 属于静态存储形式数据元素不能自由扩充
附录顺序表完整C源码
