自己做网站推广关键词,无极官网下载,网站点击量设计,网站历史频道怎么做文章目录 一.顺序表的存储结构定义1.1定义1.2 图示1.3结构代码*C语言的内存动态分配 二.顺序表基本运算*参数传递2.1建立2.2初始化(InitList(L))2.3销毁(DestroyList(L))2.4判断线性表是否为空表(ListEmpty(L))2.5求线性表的长度(ListLength(L))2.6输出线性表(DispLi… 文章目录 一.顺序表的存储结构定义1.1定义1.2 图示1.3结构代码*C语言的内存动态分配 二.顺序表基本运算*参数传递2.1建立2.2初始化(InitList(L))2.3销毁(DestroyList(L))2.4判断线性表是否为空表(ListEmpty(L))2.5求线性表的长度(ListLength(L))2.6输出线性表(DispList(L))2.7查找元素的操作(GetElem与LocateElem)2.7.1按序号(GetElem(L,i,e))2.7.2按元素(LocateElem(L,e)) 2.8插入数据元素(ListInsert(L,i,e))2.9删除数据元素(ListDelet(L,i,e)) 三.顺序表优缺点 一.顺序表的存储结构定义
1.1定义
线性表的顺序表示又称为顺序存储结构或顺序映像称为顺序表其逻辑结构与存储结构一致用一段地址连续的存储单元依次存储线性表的数据元素。 设顺序表的每个元素占用 c 个存储单元则第 i 个元素的存储地址为 所以只要确定了存储顺序表的起始地址即基地址a1计算任意一个元素的存储地址的时间是相等的。 1.2 图示 如图可见顺序表的特点地址连续依次存放随机存取和类型相同即以物理位置相邻表示逻辑关系任一元素均可随机存取我们通常用一维数组表示顺序表也就是把线性表中相邻元素存储在数组中相邻位置从而导致数据元素的序号和存放它的数组下标之间具有一一对应的关系。 注意 C语言中数组的下标是 从0开始 的而顺序表中元素的序号是 从1开始 的即线性表中第 i 个元素存储在数组中下标为 i-1 的位置。 1.3结构代码
#define LIST INIT SIZE 100 //线性表存储空间的初始分配量
typedef struct{ElemType elem[LIST_INIT_SIZE];//存放顺序表中的元素的一个数组可以替换事先定义int length; //当前长度
}SqList; //SqList是存放ElemType类型元素的顺序表指针指向第一个元素的地址从上面代码我们可以看到这里我们封装了一个结构事实上就是对数组进行封装增加了个当前长度的变量罢了。通过sqlist这个结构对数组进行封装多了一个length的变量 总结一下顺序存储结构封装需要三个属性。 存储空间的起始位置数组data它的存储位置就是线性表存储空间的存储位置。类似队伍的第一个同学找到自己的位置线性表的最大存储容量数组长度maxsize也就是我们总共买了多少张票data三个含义首地址地址常量data[0]线性表的当前长度length也就是总共来了多少人 注意数组的长度与线性表的当前长度需要区分一下数组的长度是存放线性表的存储空间的总长度一般初始化后不变。而线性表的当前长度是线性表中元素的个数是会变化的。由于线性表中可以进行插入操作所以数组长度要大于当前线性表的长度。 *C语言的内存动态分配
由上诉内容可知[MaxSize]是固定的存放地址也固定下面我们介绍动态内存分配可以重建或修改数组
获得这个根数组中基地址第一个元素的地址其他地址用下标来操作。
//先定义指针用内存分配函数动态分配内存定义空间
typedef struct{ElemType *elem;int length;
}SqList;//顺序表类型
L.elem(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);//分配MaxSize个ElemType类型的空间
//返回值类型是void*所以要强转
//要保存这个地址到data中就要把malloc返回值强转为L.data的类型二.顺序表基本运算
*参数传递
在学习顺序表基本运算之前我们先了解一下相关的知识点——C中的参数传递 函数调用时传送给形参表的实参必须与形参三个一致类型个数顺序 参数传递有两种方式传值方式参数为整型实型和字符型等和传地址 传地址有三种参数为指针变量参数为引用类型参数为数组名 注意当指针变量做参数时形参变化不影响实参栈的创建和销毁 #includeiostream.h
void swap(float *m,float *n){float *t;tm;mn;nt;
}
void main(){float a,b,*p1,*p2;cinab;p1a;p2b;//即交换p1和p2的值不会影响a和b的值swap(p1,p2);
}
coutaendlbendl;数组名作参数 数组可以看成const指针特殊的指针定义后不可修改 传递的是数组的首地址 对形参数组所做的任何改变都将反映到实参数组中 //用数组做函数的参数求10个整数的最大数
#includeiostream.h
#define N 10//定义常量N为10
int max(int b[]){//定义计算数组中最大数的函数int i,n;nb[0];for(i1;iN;i)if(nb[i])nb[i];return n;
}
int max(int a[]);
void main(){int a[10];int i,m;for(i0;iN;i)cina[i];mmax(a);coutthe max number is:m;
}引用类型做参数 引用它用来给一个对象提供一个替代的名字 传递引用参数给函数与传递指针的效果是一样的形参变化实参也发生变化。 引用类型做形参在内存中并没有产生实参的副本它直接对实参操作而一般变量做参数形参与实参就占用不同的存储单元所以形参变量的值是实参变量的副本。因此当参数传递的数据量较大时用引用比用一般变量传递参数的时间和空间效率都好。 指针参数虽然也能达到与使用引用的效果但在被调函数中需要重复使用“*指针变量名”的形式进行运算这很容易产生错误且程序的阅读性交差另一方面在主函数的调用点处必须用变量的地址作为实参。 #includeiostream.h
void main(){int i5;int ji;//j是一个引用类型代表i的一个替代名i值改变时j值也跟着改变所以会输出i7,j7i7;coutiijj;
}#includeiostream.h
void swap(float m,float n){float temp;tempm;mn;ntemp;
}
void main(){float a,b;cinab;swap(a,b);coutaendlbendl;
}形参L和L的区别带的是引用型参数它是地址传递其实参会随着形参的改变而改变不带的参数是一般参数是值传递其实参不会随着形参的改变而改变。所以结构改变并且需要传回这种改变的要用引用型参数否则用一般参数。
引用L-length等同于(*L)length
2.1建立
这里介绍整体创建顺序表即由数组元素a[0…n-1]创建顺序表L。其方法是将数组a中的每个元素依次放入顺序表中并将n赋给顺序表的长度域。算法如下
void CreatList(SqList *L,ElemType a[],int n){//由a中的n个元素建立顺序表int i0,k0;//k表示L中元素的个数初始值为0L(SqList*)malloc(sizeof(SqList));//分配存放线性表的空间while(in){//i扫描数组a的元素L-data[k]a[i];//将元素a[i]存放到L中k;i;}L-lengthk;//设置L的长度K
}调用上述算法创建好L所指的顺序表之后需要回传给对应的实参也就是说L是输出型参数所以在形参L的前面需要加上引用符.
2.2初始化(InitList(L))
该运算功能是构造一个空的线性表L实际上只需分配线性表的存储空间并将length域设置为0即可。算法如下
void InitList(SqList *L){L(SqList*)malloc(sizeof(SqList));//分配存放线性表的空间L-length0;;//置空线性表的长度为0
}本算法的时间复杂度为O(1)。
2.3销毁(DestroyList(L))
该运算功能是释放线性表L占用的内存空间。算法如下
void DestroyList(SqList *L){free(L);//释放L所指的顺序表空间
}本节的顺序表是通过malloc函数分配存储空间的当不再需要顺序表时务必调用DestroyList基本运算释放其存储空间否则尽管系统会自动释放顺序表的指针变量L但不会自动释放L指向的存储空间如此可能会造成内存泄漏本算法的时间复杂度为O(1).
2.4判断线性表是否为空表(ListEmpty(L))
该运算返回一个布尔值表示L是否为空表。若L为空表返回true否则返回false。算法如下
bool ListEmpty(SqList *L){return(L-length0);
}2.5求线性表的长度(ListLength(L))
该运算返回顺序表L的长度实际上只需返回length域的值即可。算法如下
bool ListEmpty(SqList *L){return(L-length0)
}2.6输出线性表(DispList(L))
该运算依次输入L中各元素的值。算法如下
void DispList(SqList *L){for(int i0;iL-length;i)printf(%d,L-data[i]);printf(\n);
}本算法中的基本操作为for循环中的printf语句故时间复杂度为O(n)
2.7查找元素的操作(GetElem与LocateElem)
2.7.1按序号(GetElem(L,i,e))
实现GetElem的具体操作即将线性表L中的第i个位置元素值返回。就程序而言我们只需要把数组第i-1下标的值返回即可。
bool GetElem(SqList *L,ElemType e){int i0;while(i1||iL-length)return false;//参数i错误时返回falseeL-data[i-1];//取元素的值return true;//成功找到元素时返回true
}本算法的时间复杂度为O(1)
2.7.2按元素(LocateElem(L,e))
按运算顺序查找第一个值为e的元素的逻辑符号若这样的元素不存在则返回为0.算法如下
int LocateElem(SqList *L,ElemType e){int i0;while(iL-length L-data[i]!e)i;//查找元素eif(iL-length)return 0;//未找到时返回0elsereturn i1;//找到后返回其逻辑符号
}该算法的时间复杂度为O(n)
2.8插入数据元素(ListInsert(L,i,e))
刚才我们提到过排队的问题如果这时候有一个人要回到队列当中我们应该怎么做我们会找到他要插入位置的那个同学让他以及它后面的同学全部往后移动一个位置再将新同学安排在这个位置里面。所以我们插入算法的思路如下
如果插入位置不合理抛出异常如果线性表长度大于等于数组长度则抛出异常或动态增加数组容量从最后一个元素开始向前遍历到第i个位置分别将他们都向后移动一个位置将要插入元素填入位置i处线性表长度1; 算法如下
Status ListInsert(SqList *L,int i,ElemType e){int k;if(L-lengthMAXSIZE){//顺序线性表已经满了return ERROR;}if(i1||iL-length1){//当i不在范围内时return ERROR;}if(iL-length){//若插入数据位置不在表尾//将要插入位置后数据元素向后移动一位for(kL-length-1;ki;k--){L-data[k1]L-data[k];}}L-data[i-1]e;//将新元素插入L-length;return true;
}时间复杂度为O(n)
2.9删除数据元素(ListDelet(L,i,e))
我们完全可以借鉴前面插入数据元素的算法得到删除数据算法的思路 如果删除位置不合理抛出异常 取出删除元素 从删除元素位置开始遍历到最后一个元素位置分别将它们都向前移动一个位置 表长-1 算法如下
Status ListDelet(SqList *L,int i,ElemType *e){int k;if(L-length0){return ERROR;}if(i1||iL-length){return ERROR;}*eL-data[i-1];if(iL-length){for(ki;kL-length;k){L-data[k-1]L-data[k];}}L-length--;return true;
}三.顺序表优缺点
线性表的顺序存储结构在存、读数据时不管是哪个位置时间复杂度都是O(1)。而在插入或删除数据时时间复杂度都是O(n)。这就说明它比较适合元素个数比较稳定不经常插入和删除元素而更多的操作是存取数据的应用。那么我们可以得出它的优缺点
优点
无需为表示表中元素之间的逻辑关系而增加额外的存储空间。可以快速地存取表中任意位置的元素。
缺点
插入和删除操作需要移动大量元素。当线性表长度变化较大时难以确定存储空间的容量。容易造成存储空间的“碎片”因为申请空间的时候是一整块一整块地申请的那么两块地的中间就会有一小块碎片的地方被浪费
