建设工程竣工规划局网站,欧盟理事会,学习建站的网站,茂名 网站建设定义和基本操作
定义#xff1a;相同数据类型的 n ( n ≥ 0 ) n(n \ge 0) n(n≥0)个数据元素的有限序列#xff0c;其中n为表长#xff0c;当n0时线性表是一个空表一般表示#xff1a; L ( a 1 , a 2 , … … , a i , a i 1 , a n ) L(a_1,a_2,……,a_i,a_{i1},a_n) L(a…定义和基本操作
定义相同数据类型的 n ( n ≥ 0 ) n(n \ge 0) n(n≥0)个数据元素的有限序列其中n为表长当n0时线性表是一个空表一般表示 L ( a 1 , a 2 , … … , a i , a i 1 , a n ) L(a_1,a_2,……,a_i,a_{i1},a_n) L(a1,a2,……,ai,ai1,an) a 1 a_1 a1是表头元素 a n a_n an是表尾元素 除第一个元素外每个元素有且只有一个直接前驱除最后一个元素外每个元素有且只有一个直接后继
基本操作
InitList(L)初始化表。构造一个空的线性表L分配内存空间DestroyList(L)销毁操作。销毁线性表并释放线性表L所占用的内存空间ListInsert(L,i,e)插入操作。在表L中的第i个位置插入指定元素eListDelete(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
顺序表
定义
顺序表用顺序存储的方式实现线性表的顺序存储。把逻辑上相邻的元素存储在物理位置也相邻的存储单元中顺序表的实现-静态分配
#define MaxSize 50 //线性表的最大长度typedef struct {ElemType data[MaxSize]; //顺序表的元素int length; //顺序表的当前长度
}SqList; //顺序表的类型定义顺序表的实现-动态分配 时间开销大
#define InitSize 50 //顺序表的初始长度
//动态分配
typedef struct {ElemType* data; //指针动态分配数组的指针int maxsize; //顺序表的最大容量int length; //顺序表的当前长度
}SeqList;动态申请和释放内存空间 Cmalloc、free函数
L.data (ElemType*)malloc(sizeof(ElemType) * InitSize); //C语言初始动态分配 2. Cnew、delete关键字C
L.data new int[InitSize];顺序表的特点 随机访问可以在O(1)时间内找到第i个元素存储密度高拓展容量不方便插入、删除操作不方便需要移动大量元素
插入和删除
插入
ListInsert(L,i,e)插入操作。在表L中第i个位置上插入指定元素
bool ListInsert(SqList L, int i, int e){if (i1 || iL.length 1) { //判断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处放eL.length; //长度加1return true;
}时间复杂度 最好情况在表尾插入即in1不需要移动元素时间复杂度为O(1)最坏情况在表头插入即i1元素后移语句执行n次时间复杂度为O(n)平均情况移动结点的平均次数 n 2 \frac{n}{2} 2n时间复杂度O(n)
删除
bool ListDelete(SqList L, int i, int e){if (i1 || iL.length 1) { //判断i的范围是否有效return false;}e L.data[i - 1]; //将被删除的元素赋值给efor (int j i; j L.length; j) { //将第i个位置后的元素前移L.data[j - 1] L.data[j];}L.length--; 线性表长度减1return true;
}时间复杂度 最好情况删除表尾元素即in,时间复杂度为O(1)最坏情况删除表头元素即i1时间复杂度为O(n)平均情况移动结点的平均次数 n − 1 2 \frac{n-1}{2} 2n−1时间复杂度O(n)
查找
按位查找
GetElem(L,i)按位查找操作。获取表L中第i个位置的元素的值
int GetElem(SqList L, int i){return L.data[i - 1];
}int GetElem(SeqList L, int i){return L.data[i - 1];
}时间复杂度O(1) 随机存取特性
按值查找
LocateElem(L,e)按值查找操作。在表L中查找具有给定关键字值的元素
int LoacteElem(SqList L, int e){int i;for (i 0; i L.length; i) {if (L.data[i] e) { //不可以用于比较两个结构体return i 1; //下标为i的元素值等于e返回其位序i1}}return 0; //退出循环说明查找失败
}时间复杂度 最好情况查找的元素在表头时间复杂度为O(1)最坏情况查找的元素在表尾或不存在时间复杂度为O(n)平均情况平均比较次数 n 1 2 \frac{n1}{2} 2n1时间复杂度为O(n)
单链表
定义
typedef struct LNode { //定义单链表结点类型int data; //每个结点存放一个指针元素struct LNode* next; //指针指向下一个结点
}LNode, * LinkList;不带头结点的单链表
bool InitList(LinkList L){L NULL; //空表暂时没有任何结点return true;
}带头结点的单链表
bool InitList(LinkList L) {L (LNode*)malloc(sizeof(LNode)); //分配一个头结点if (L NULL) {return false;}L - next NULL; //头结点之后暂时还没有结点return true;
}插入和删除
按位序插入带头结点
ListInsert(L,i,e)插入操作。在表L中的第i个位置上插入指定元素e
bool ListInsert(LinkList L, int i, ElemType e){if(i1){return false;}LNode *p; //指针p指向当前扫描的结点int j0; //当前p指向的是第几个结点pL; //L指向头结点头结点是第0个结点不存储数据while(p!NULL ji-1){ //循环找到第i-1个结点pp-next;j;}if(pNULL){ //i值不合法return false;}LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts; //将结点s连到p之后return true; //插入成功
}按位序插入不带头结点
ListInsert(L,i,e)插入操作。在表L中的第i个位置上插入指定元素e
bool ListInsert(LinkList L, int i, ElemType e){if(i1){return false;}if(i1){ //插入第i个结点的操作与其他结点不同LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextL;Ls; //头指针指向新结点return true; //插入成功}LNode *p; //指针p指向当前扫描的结点int j1; //当前p指向的是第几个结点pL; //p指向第1个结点不是头结点while(p!NULL ji-1){ //循环找到第i-1个结点pp-next;j;}if(pNULL){ //i值不合法return false;}LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts; //将结点s连到p之后return true; //插入成功
}指定结点的后插操作
//在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e){if(pNULL){return false;}LNode *s(LNode *)malloc(sizeof(LNode));if(sNULL){ //内存分配失败return false;}s-datae; //用结点s保存数据元素es-nextp-next;p-nexts; //将结点s连接到p之后return true;
}指定元素的前插操作
//在p结点之前插入元素e
bool InsertPriorNode(LNode *p, ElemType e){if(pNULL){return false;}LNode *s(LNode *)malloc(sizeof(LNode));if(sNULL){ //内存分配失败return false;}s-nextp-next;p-nexts; //将结点s连接到p之后s-datap-data; //将p中的元素复制到s中p-datae; //p中元素覆盖为ereturn true;
}按位序删除带头结点
ListDelete(L,i,e)删除操作删除表L中第i个位置的元素并用e返回元素的值
bool ListDelete(LinkList Lint i,ElemType e){if(i1){return false;}LNode *p; //指针p指向当前扫描到的结点int j0; //当前p指向的是第几个结点pL; //L指向头结点头结点是第0个结点 (不存数据)while (p!NULL ji-1){ //循环找至第 i-1个结点pp-next;j;}if(pNULL){ //i值不合法return false;}if(p-next NULL){ //第i-1个结点之后已无其他结点return false;}LNode *qp-next; //令q指向被删除结点e q-data; //用e返回元素的值p-nextq-next; //将*q结点从链中“断开”free(q); //释放结点的存储空间return true; //删除成功
}指定结点的删除
//删除指定结点p
bool DeleteNode (LNode *p){if (pNULL){return false;}LNode *qp-next; //令q指向*p的后继结点p-datap-next-data; //和后继结点交换数据域p-nextq-next; //将*q结点从链中“断开”free(q); //释放后继结点的存储空间return true;
}如果p是最后一个结点只能从表头开始寻找p的前驱时间复杂度O(n) 查找
按位查找
GetElem(L,i)按位查找操作。获取表L中第i个位置的元素的值
//按位查找返回第i个元素带头结点
LNode *GetElem(LinkList, int i){if(i0){return NULL;}LNode *p; //指针p指向当前扫描到的结点int j0; //当前p指向的是第几个结点pL; //L指向头结点头结点是第0个结点不存储数据while (p!NULL ji){ //循环找到第 i 个结点pp-next;j;}return p;
}平均时间复杂度O(n)
按值查找
LocateElem(L,i)按值查找操作。在表L中查找具有给定关键字值的元素
//按值查找找到数据域e 的结点
LNode * LocateElem(LinkList L,ElemType e){LNode *p L-next;//从第1个结点开始查找数据域为e的结点while (p ! NULL p-data ! e)p p-next;return p; //找到后返回该结点指针否则返回NULL
}时间复杂度O(n)
求表的长度
//求表的长度
int Length(LinkList L){int len 0; //统计表长LNode *p L;while (p-next ! NULL){p p-next;len;}return len;时间复杂度O(n)
建立
尾插法头插法
双链表
初始化插入删除遍历
循环链表
循环单链表表尾结点的next指针指向头结点 从一个结点出发可以找到其他任何一个结点 循环双链表
静态链表
概念分配一整连续的内存空间各个结点集中安置
顺序表和链表的比较
逻辑结构 都属于线性表都是线性结构 物理结构/存储结构 顺序表 优点支持随机存取、存取密度高缺点大片连续空间分配不方便改变容量不方便 链表 优点离散的小空间分配方便、改变容量方便缺点不可随机存取、存取密度低 数据的运算/基本操作 初始化 顺序表需要预分配大片连续空间若分配空间过小则之后不方便拓展容量;若分配空间过大则浪费内存资源 静态分配静态数组容量不可改变动态分配动态数组malloc、free容量可改变但需要移动大量元素时间代价高 链表只需分配一个头结点 (也可以不要头结点只声明一个头指针) 之后方便拓展 销毁 顺序表修改Length0 静态分配系统自动回收空间动态分配需要手动free 链表依次删除各个结点(free) 插入和删除 顺序表需要把后续元素后移/前移若数据元素很大则移动的时间代价很大链表修改指针 查找 顺序表 按位查找O(1)按值查找O(n) 若表内元素有序可在 O ( l o g 2 n ) O(log_2n) O(log2n)时间内找到 链表 按位查找O(n)按值查找O(n)
开放式问题回答思路
问题 请描述顺序表和链表的 bla bla bla… 实现线性表时用顺序表还是链表好?
顺序表和链表的逻辑结构都是线性结构都属于线性表但是二者的存储结构不同顺序表采用顺序存储…(特点带来的优点缺点): 链表采用链式存储…(特点、导致的优缺点)。由于采用不同的存储方式实现因此基本操作的实现效率也不同。当初始化时…;当插入一个数据元素时…;当删除一个数据元素时…; 当查找一个数据元素时…
