| 数据结构 | 您所在的位置：网站首页 › 线性表的例子 › 数据结构 |
数据结构
|
👉数据结构-线性表（二）单链表 👉数据结构-线性表（三）双链表 👉数据结构-线性表（四）循环链表 本文介绍了线性表的定义及基本操作以及顺序表示的实现代码！ Let’s go🏃♂️ 数据结构 线性表（一）基本概念及基本操作 思维导图
线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表。若用L命名线性表，则其一般表示为 L = ( a 1 , a 2 , … , a i , a i + 1 , … , a n ) L = (a_1, a_2, … , a_i, a_i+1, … , a_n) L=(a1,a2,…,ai,ai+1,…,an) 几个概念： a i a_i ai 是线性表中的“第i个”元素线性表中的位序 a 1 a_1 a1 是表头元素； a n a_n an 是表尾元素。 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继 。 1.2 基本操作InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。 DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。 ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。 ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。 LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。 GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。 其他常用操作： Length(L) 求表长。返回线性表L的长度，即L中数据元素的个数。 PrintList(L) 输出操作。按前后顺序输出线性表L的所有元素值。 Empty(L) 判空操作。若L为空表，则返回true，否则返回false。 2 线性表的顺序表示 2.1 定义定义： 顺序表–用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。 1、静态分配给各个数据元素分配连续的存储空间，大小为MaxSize * sizeof(ElemType) #include #define MaxSize 10 //定义最大长度 typedef struct SqList { /* data */ int data[MaxSize]; //用静态的“数组”存放数据元素 int length; //顺序表的当前长度 }; void InitList(SqList &L) { L.length = 0; //顺序表初始长度为0； } int main() { SqList L; //声明一个顺序表 InitList(L); //初始化 for (int i = 0; i /* data */ int *data; //用静态的“数组”存放数据元素 int MaxSize; //定义最大长度 int length; //顺序表的当前长度 }; void InitList(SqList &L) { //用malloc函数申请一片连续的存储空间 L.data = (int *)malloc(InitSize*sizeof(int)); L.length = 0; L.MaxSize = InitSize; } void IncreaseSize(SqList &L, int len) { int *p = L.data; L.data = (int *)malloc((L.MaxSize + len)*sizeof(int)); for (int i = 0; i SqList L; //声明一个顺序表 InitList(L); //初始化 //插入元素 IncreaseSize(L, 5); return 0; } 3、顺序表特点1、随机访问，即可以在 O(1) 时间内找到第 i 个元素。（代码实现：data[i-1];静态分配、动态分配都一样 ） 2、存储密度高，每个节点只存储数据元素 3、拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高） 4、插入、删除操作不方便，需要移动大量元素 2.2 基本操作的实现 1、插入ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。 代码实现： #include #include #define MaxSize 10 using namespace std; typedef struct { /* data */ int data[MaxSize]; int length; }SqList; /** * 初始化 */ void InitList(SqList &L) { L.length = 0; //顺序表初始长度为0； } /** * 插入顺序表 */ bool ListInsert(SqList &L, int i, int e) { //判断i的范围是否有效 if (i L.length + 1) { return false; /* code */ } //判断当前存储空间是否已满，不能插入 if (L.length >= MaxSize) { /* code */ return false; } //将第i个元素及以后的元素后移 for (int j = L.length; j >= i; j--) { /* code */ L.data[j] = L.data[j - 1]; } //在位置i处放入e L.data[i - 1] = e; L.length++; //长度++ return true; } /** * 打印输出 */ void printList(SqList L) { cout SqList L; InitList(L); //赋值 for (int i = 0; i /* data */ int data[MaxSize]; int length; }SqList; /** * 初始化 */ void InitList(SqList &L) { L.length = 0; //顺序表初始长度为0； } /** * 删除顺序表 */ bool ListDelete(SqList &L, int i, int &e) { //判断i的范围是否有效 if (i L.length + 1) { return false; /* code */ } e = L.data[i - 1]; //将第i个元素及以后的元素前移 for (int j = i; j cout SqList L; InitList(L); //赋值 for (int i = 0; i /* data */ int *data; //动态分配 int length; int MaxSize; } SqList; /** * 初始化 */ void InitList(SqList &L) { L.data = (int *)malloc(InitSize*sizeof(int)); L.MaxSize = InitSize; L.length = 0; //顺序表初始长度为0； } /** * 按位查找顺序表 */ int ListSearchBySite(SqList L, int i) { cout /* code */ cout /* code */ L.data[i] = i; L.length++; } printList(L); cout L.data = (int *)malloc(InitSize * sizeof(int)); L.MaxSize = InitSize; L.length = 0; //顺序表初始长度为0； } /** * 按值查找顺序表 */ int ListSearchByValue(SqList L, int e) { cout /* code */ cout /* code */ L.data[i] = i; L.length++; } printList(L); cout |
【本文地址】