政务网的门户网站建设,wordpress主题 uifun,线上推广销售渠道,修改网站版权二、线性表
2.1线性表的定义和基本操作
2.1.1 线性表的基本概念
线性表#xff1a;是具有相同数据类型的 n 个数据元素的有限序列。(Eg:所有的整数按递增次序排列#xff0c;不是顺序表#xff0c;因为所有的整数是无限的)其中n为表长#xff0c;当n0时线性表是一个空表…二、线性表
2.1线性表的定义和基本操作
2.1.1 线性表的基本概念
线性表是具有相同数据类型的 n 个数据元素的有限序列。(Eg:所有的整数按递增次序排列不是顺序表因为所有的整数是无限的)其中n为表长当n0时线性表是一个空表。若用L表示一个线性表则是线性表中的第i个元素称为线性表中的位序是表头元素;是表尾元素。 除第一个元素外每个元素有且仅有一个直接前驱; 除最后一个元素外每个元素有且仅有一个直接后继
2.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 的长度即表中元素的个数。PrintList(L)输出操作。按前后顺序输出线性表 L 的所有元素值。Empty(L)判空操作。若表L 为空表则返回 true否则返回 false。
对数据操作的思路创销、增删改查 什么时候要传入引用“”—―对参数的修改结果需要“带回来”时
#includestdio.hvoid test ( int x) {x1024;printf ( test函数内部x%d\n,x) ;
}int main() {int x 1;printf( 调用test前xd\n,x) ;test (x);printf ( 调用test后x%din,x);
} 2.2线性表的顺序表示 2.2.1 顺序表的定义
顺序表用顺序存储的方式实现线性表 顺序存储把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
C语言中通过sizeof(ElementType)可以知道一个数据元素的大小
2.2.2 顺序表的实现
静态分配
#define MaxSize 10 // 定义最大长度 typedef struct {int data[MaxSize]; // 使用静态的数组存放数据元素 int length; // 顺序表的当前长度
}SqList; //顺序表的类型定义//基本操作 —— 初始化一个顺序表
void InitList(SqList L) {for(int i0;iMaxSize;i)L.data[i]0; //将所有数据元素设置为默认初始值L.length 0; // 顺序表初始长度为0
}int main() {SqList L; // 声明一个顺序表 InitList(L); // 初始化顺序表 return 0;
}如果不设置数据元素的默认值静态数组的表长确定后就无法更改存储空间是静态的最好使用动态分配
动态分配
#include stdlib.h //malloc函数要使用的头文件
#define InitSize 10 // 顺序表的初始长度typedef struct {int *data; // 声明动态分配数组的指针 int MaxSize; // 顺序表的最大容量int length; // 顺序表的当前长度
}SeqList;// 初始化顺序表
void InitList(SqList L) {// 用malloc函数申请一片连续的存储空间 L.data (int *)malloc(InitSize * sizeof(int)); //(int*)把malloc返回的指针转换成定义的同类型的指针L.length 0; //把数据表的长度设为0L.MaxSize InitSize; //把数据表的最大长度设为初始值
}// 增加动态数组的长度
void IncreaseSize(SqList L, int len) {int *p L.data; //把顺序表的data指针的值赋给指针pL.data (int *)malloc((L.MaxSizelen) * sizeof(int));for (int i 0; i L.length; i)L.data[i] p[i]; // 将数据复制到新区域 L.MaxSize L.MaxSize len; // 顺序表最大长度增加len free(p); // 释放原来的内存空间
}int main() {SeqList L; // 声明一个顺序表 InitList(L); // 初始化顺序表 ...//往数据表中随便插入几个元素IncreaseSize(L, 5); //再多申请5个空间return 0;
}顺序表的特点
随机访问即可以在 O(1) 时间内找到第 i 个元素存储密度高每个节点只存储数据元素拓展容量不方便即使使用动态分配的方式实现拓展长度的时间复杂度也比较高要把数据复制到新的区域插入删除操作不方便需移动大量元素 2.2.3 顺序表的插入删除
Listlnsert(L,i,e):插入操作。在表L中的第i个位置上插入指定元素e
#define MaxSize 10 // 定义最大长度 10个元素typedef struct {int data[MaxSize]; // 用静态的数组存放数据元素 int length; // 顺序表的当前长度
}SqList; //定义数据表SqlList// 在顺序表i位置插入e
bool ListInsert(SqList L, int i, int e) { //注意位序、数组下标的关系 if (i 1 || i L.length1) // 判断i的范围是否有效 return false;if (L.length MaxSize) // 判断存储空间是否已满 return false;for (int j L.length; j i; j--) // 将第i个元素之后的元素后移 L.data[j] L.data[j-1];L.data[i-1] e; // 在位置i处放入e i-1 下标L.length; // 长度1 return true;
} int main() {SqList L; //声明一个顺序表InitList(L); //初始化顺序表...//此次省略一些代码插入几个元素ListInsert(L, 3, 3); //调用函数 在顺序表L的第三个位置插入数据3return 0;
} 插入操作的时间复杂度 问题规模nL.length(表长)
最好情况新元素插入到表尾不需要移动元素 i n1循环0次 最好时间复杂度 O(1)
最坏情况新元素插入到表头需要将原有的 n 个元素全都向后移动 i 1循环 n 次 最坏时间复杂度 O(n)
平均情况假设新元素插入到任何一个位置的概率相同即 i 1,2,3, … , length1 的概率都是 p 循环 n 次i2 时循环 n-1 次i3循环 n-2 次 …… i n1时循环0次 平均循环次数 np (n-1)p (n-2)p ... 1⋅p 平均时间复杂度 O(n)
ListDelete(L,i,e):删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。
#define MaxSize 10typedef struct {int data[MaxSize];int length;
} SqList;// 删除顺序表i位置的数据并存入e
bool ListDelete(SqList L, int i, int e) { //注意e加了引用这里处理的e跟main函数中的e在内存中对应的是同一份数据if (i 1 || i L.length) // 判断i的范围是否有效return false;e L.data[i-1]; // 将被删除的元素赋值给e for (int j i; j L.length; j) //将第i个位置后的元素前移 L.data[j-1] L.data[j];L.length--; //线性表长度-1return true;
}int main() {SqList L; //声明一个顺序表InitList(L); //初始后顺序表...//此次省略一些代码插入几个元素int e -1; //用变量e把删除的元素“带回来”if (ListDelete(L, 3, e)) //调用删除操作删除第三个位置的元素用e返回printf(已删除第3个元素删除元素值为%d\n, e);elseprintf(位序i不合法删除失败\n); return 0;
} 插入操作的时间复杂度 问题规模nL.length(表长)
最好情况删除表尾元素不需要移动其他元素 i n循环 0 次 最好时间复杂度 O(1)
最坏情况删除表头元素需要将后续的 n-1 个元素全都向前移动 i 1循环 n-1 次 最坏时间复杂度 O(n)
平均情况假设删除任何一个元素的概率相同即 i 1,2,3, … , length 的概率都是 p i1时循环 n-1 次i2 时循环 n-2 次i3循环 n-3 次 …… i n时循环0次 平均循环次数 (n-1)p (n-2)p ... 1⋅p 平均时间复杂度 O(n) 2.2.4 顺序表的查找
GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。
// 静态分配的按位查找
#define MaxSize 10 //定义最大长度typedef struct {ElemType data[MaxSize]; //用静态的数组存放元素int length; //顺序表的当前长度
}SqList; //顺序表的类型定义ElemType GetElem(SqList L, int i) { //位序从1开始return L.data[i-1]; //数组下标从0开始所以要-1
}// 动态分配的按位查找
#define InitSize 10 //顺序表的初始长度typedef struct {ElemType *data; //指示动态分配数组的指针 *data变量是一个指针 int MaxSize; //顺序表的最大容量int length; //顺序表的当前长度
}SeqList; //顺序表的类型定义ElemType GetElem(SeqList L, int i) {return L.data[i-1];
}//*data指向了malloc分配的一整片连续空间的起始地址 即data[i-1]按位查找的时间复杂度 O(1) 由于顺序表的各个数据元素在内存中连续存放 因此可以根据起始地址和数据元素大小立即找到 第 i 个元素——“随机存取”特性
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。
#define InitSize 10typedef struct {ElemType *data; //指示动态分配数组的指针int MaxSize; //顺序表的最大容量 int length; //顺序表的当前长度
}SqList;// 查找第一个元素值为e的元素并返回其位序
int LocateElem(SqList L, int e) {for (int i 0; i L.length; i)if (L.data[i] e) //依次判断数据表中的数据元素跟传入的数据e是否相等return i1; // 数组下标为i的元素值等于e返回其位序i1 return 0; // 没有查找到
}基本数据类型int、char、double、 float 等可以直接用运算符“”比较,结构类型的数据元素不能
按值查找的时间复杂度
2.3线性表的链式表示
