数据结构

您所在的位置：网站首页 › 线性表的特点是每个元素都有一个前驱和后驱 › 数据结构

数据结构

2024-02-21 00:37| 来源: 网络整理| 查看: 265

数据结构-线性表 2.1线性表的定义和基本操作 2.1.1线性表的定义

具有**相同数据类型的n（n>0)个数据元素的有限**序列，其中n为表长，当n=0时表示线性表是一个空表

线性表的基本特征表中元素个数有限表中元素具有逻辑上的连续性，有其先后顺序表中元素都是数据元素，且都是相同的数据结构，这表示每个元素占有相同大小的存储空间除表头元素外，每个元素都有且仅有一个直接前驱除表尾元素外，每个元素都有且仅有一个直接后继 2.1.2线性表的基本操作 InitList (&L)初始化表，构建一个空的线性表Length(L)求表长。LocateElem(L,e)按值查找操作。GetElem(L,i)按位查找操作ListInsert（&L,i,e)插入操作。ListDelete（&L,i,&e)删除操作。PrintList(L)输出线性表Empty（L）判空操作DestroyList（&L）摧毁操作 2.2线性表的顺序表示（顺序表） 2.2.1顺序表的定义定义

线性表的顺序存储又称顺序表,

顺序存储，把逻辑上相邻的袁术存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

sizeof(ElemType)是每个数据元素所占用的存储空间的大小

存储结构实现方式静态分配 #include #define MaxSize 10 //静态分配容易造成资源浪费，数据超过容量时，处理又很麻烦，所以一般采用动态分配的方式 typedef struct { int data[MaxSize]; //用静态的数组存放数据元素 int Length; //表示顺序表的当前长度 }SqList; //顺序表的类型定义 //初始化顺序表 void InitList(SqList &L) { L.Length=0; } int main(){ SqList L; //声明一个顺序表 InitList(L); //初始化 //尝试打印data for(int i=0;i //使用malloc函数申请一片连续的存储空间 L.data = (int *)malloc(InitSize*sizeof(int)); L.length=0; L.MaxSize=InitSize; } //增加动态数组的长度 void IncreaseSize(SeqList &L,int len){ int *p = L.data; L.data= (int *)malloc((L.MaxSize+len)*sizeof(int)); //malloc函数开辟一片新的区域 for(int i = 0; i SeqList L; //声明一个顺序表 InitList(L); //初始化 //往顺序表中加入几个元素; IncreaseSize(L,5); printf("%d",L.MaxSize); return 0; } 特点随机访问，在时间O(1)时间内找到第i个元素存储密度高拓展容量不方便插入，删除数据元素不方便 2.2.2顺序表的基本操作插入操作 //插入操作，在顺序表的第i个位置插入一个元素 bool ListInsert(SqList &L,int i,int e){ if(L.length>=MaxSize) //判断插入位置是否合法 return false; if(iL.length+1) return false; for(int j=L.length;j>=i;j--) //将要插入位置的之后的元素后移 L.data[j]=L.data[j-1]; L.data[i-1]=e; //将e放入到i位置 L.length++; //顺序表长度加一 return true; }

插入操作时间复杂度：最好为O(1),最坏为O(n),平均O(n)

删除操作 //删除操作，删除第i个位置的元素，并返回这个元素 bool ListInsert(SqList &L,int i,int &e){ if(iL.length) //判断删除位置是否合法 return false; e = L.data[i-1]; //取出要删除位置的数 for(int j=i;j //扫描每个元素的值，判断值是否和e相等 for (int i=0;i return i+1; } } return 0; } //若数据元素是结构类型时，要改变相等条件不能用“==”来判断结构体是否相等

【本文地址】

数据结构

数据结构

今日新闻

推荐新闻