首页 > 其他分享 >数据结构·线性表

数据结构·线性表

时间:2024-06-04 16:27:04浏览次数:30  
标签:结点 线性表 复杂度 元素 len next 插入 数据结构

线性表

一、逻辑结构和基本操作

1. 逻辑结构

  • 具有相同数据类型的n个数据元素的有限序列,表长n,n=0为空表
  • 表头:第一个元素
  • 表尾:最后一个元素
  • 除第一个元素外,每个元素有且仅有一个直接前驱
  • 除最后一个元素外,每个元素有且仅有一个直接后继

2. 基本操作

initList(&L);
len(L);
locateElem(L, i);
getElem(L, i);
listInsert(&L, i, e);
listDelete(&L, i, &e);
printList(L);
isEmptyList(L);
destroyList(&L);

二、顺序存储结构

1. 定义:又称顺序表,使用一组地址连续的存储单元,依次存储线性表的数据元素,使逻辑上相邻的两个元素物理位置也相邻

  • 存储空间的起始位置data[ ]
  • 顺序表最大存储容量MaxSize
  • 顺序表当前最大长度len
    特点
  • 随机访存,O(1)时间复杂度访问
  • 存储密度高,每个结点只存储数据元素
  • 无需花费空间建立数据之间的逻辑关系,由物理位置相邻特性决定
  • 逻辑上物理上均相邻,插入删除操作需要移动大量元素

2. 基本操作

(1)插入元素

//插入元素
boolean listInsert(SqList &L, int i, Elemtype e){
	if(i < 1 || i  L.len + 1)
		return -1;
	if(L.len = MaxSize)
		return -1;
	for(int j = L.len; j  i; j--)
		L.data[j] = L.data[j - 1];
	L.data[i - 1] = e;
	L.len++;
}

分析

  • 最好情况:在表尾插入 (i=n+1),不需要移动元素,时间复杂度为O(1)
  • 最坏情况:在表头插入 (i=1),元素后移n次,时间复杂度O(n)
  • 平均情况:假设$P_i$ ($P_i = \frac{1}{n+1}$),是在第i个位置上插入一个结点的概率,则在长度为n的线性表中插入一个结点所需移动的平均次数为$\frac{n}{2}$,其时间复杂度为O(n)
    (2)删除元素
//删除元素
boolean listDelete(SqList &L, int i, Elemtype e){
	if(i < 1 || i  L.len + 1)
		return -1;
	e = L.data[i-1];
	for(int j = i; j < L.len; j++)
		L.data[j-1] = L.data[j];
	L.len--;
	return true;
}

分析

  • 最好情况:在表尾插入 (i=n),不需要移动元素,时间复杂度为O(1)
  • 最坏情况:在表头插入 (i=1),元素后移n次,时间复杂度O(n)
  • 平均情况:假设$P_i$ ($P_i = \frac{1}{n+1}$),是在第i个位置上插入一个结点的概率,则在长度为n的线性表中插入一个结点所需移动的平均次数为$\frac{n-1}{2}$,其时间复杂度为O(n)
    (3)查找元素
	int locateElem(SqList &L, Elemtype e){
		int i;
		for(i = 0; i < L.len; i++)
			if(e == L.data[i])
				return i+1;
	}

分析

  • 最好情况:查找的元素在表头,仅需比较1次,时间复杂度O(1)
  • 最坏情况:查找的元素在表尾或不存在,需要比较n次,时间复杂度O(n)
  • 平均情况:假设$P_i$ ($P_i = \frac{1}{n}$)是在第i个位置上结点的概率,则在长度为n的线性表中插入一个结点所需移动的平均次数为$\frac{n+1}{2}$,其时间复杂度为O(n)

链式存储结构

1.创建单链表

(1)头插法

  • 为新插入的结点分配内存空间
  • 每次都是把插入的新结点放入表头(头结点位置)
  • 链表结点的次序与输入的顺序相反

(2)尾插法

  • 为新插入的结点分配内存空间
  • 每次都是把插入的新结点放入表尾(尾结点位置)
  • 链表中的结点顺序与输入顺序一致

2.按值查找结点

  • 在链表中从第一个结点出发,顺指针next逐个向下搜索,直到找到第i个结点,否则返回最后一个结点的指针域NULL

3.按序号查找结点

  • 从链表第一个结点开始,由前往后按照序号递增定位到相应结点的位置,返回该值,需检查序号是否越界

4.插入

  • 插入操作是将值为x的新结点插入到单链表的第i个位置
  • 先检查插入位置是否合法
  • 找到待插入位置的前驱结点
  • 在其后将结点插入
	p = getElem(L, i-1)
	s-next = p-next;
	p-next = s;

5.删除

  • 将单链表的第i个结点删除
  • 先检查插入位置是否合法
  • 找到待删除位置的前驱结点
  • 删除其后结点
	p = getElem(L, i-1)
	q = p-next;
	q-next = p-next;
	free(q);

双链表

  • 双链表有两个指针prior和next,分别指向前驱和后继结点
  • 插入操作
	s-next = p-next;
	p-next-prior = s;
	s-prior = p;
	p-next = s;
  • 删除操作
	p-next = q-next;
	q-next-prior = p;
	free(q);

循环链表

  • 循环双链表和循环单链表
  • 静态链表使用数组来描述线性表的链式存储结构

标签:结点,线性表,复杂度,元素,len,next,插入,数据结构
From: https://www.cnblogs.com/blueflylabor/p/18231131

相关文章

  • 数据结构·简述
    数据结构绪论一、数据结构:相互存在一种或多种特定关系的集合结构:任何问题,数据元素不孤立存在,之间存在关系逻辑结构存储结构(物理结构)数据的运算逻辑结构和存储结构密不可分算法设计取决于逻辑结构,实现依赖存储结构二、逻辑结构:数据元素之间的逻辑关系与存储无关,独立于......
  • 数据结构·基本概念
    DataStructureNotesAuthor:"blueflylabor"Version:1.0RefreshDate2020.11.26Description:JustrecordandreviewsomepointsaboutDataStructure.Havemistakesthatpleasecorrectityourself.数据结构的基本概念1.数据2.数据元素:数据的基本单位,一个......
  • 数据结构·查找算法
    查找1.顺序查找一般表(1)代码typedefstruct{ElemType*elem;inttableLen;}SSTable;intsearchSeq(SSTableST,ElemTypekey){ST.elem[e]=key;//设置哨兵for(inti=0;i<ST.tableLen;i++)returni;//存在返回,不存在返回1}(2)设......
  • 数据结构·查找算法
    查找1.顺序查找一般表(1)代码typedefstruct{ElemType*elem;inttableLen;}SSTable;intsearchSeq(SSTableST,ElemTypekey){ST.elem[e]=key;//设置哨兵for(inti=0;i<ST.tableLen;i++)returni;//存在返回,不存在返回1}(2)设......
  • 数据结构第四篇【再谈泛型】
    数据结构第四篇【再谈泛型】泛型泛型类的使用泛型的上界泛型方法通配符通配符上界通配符下界......
  • 【第二节】C/C++数据结构之线性表
    目录一、线性表基本说明1.1基本概念1.2抽象数据类型1.3存储结构1.4插入与删除的区别1.5顺序存储和链式存储的优缺点二、链表2.1基本概念2.2抽象数据类型2.3单链表的定义2.4单链表的基本操作2.5单链表模板形式的类定义与实现三、单向循环链表四、双链表......
  • Java数据结构-delayQueue-优先队列--信号量
    原编辑链接:https://www.yuque.com/zhaozhaozhaozhao-khkij/lp7g2t/blwysxg3ygb00dw6?singleDoc#《3delayqueue》Queue问题单端队列和双端队列,分别对应的实现类是哪个?○Java中的单项队列queue是用链表实现的,Queue本身是一个接口,继承了Collection集合;○双端队列(De......
  • 数据结构单链表的前插法实现
    单链表的前插法实现可以通过以下步骤进行:创建一个新的节点,并将要插入的元素存储在新节点的数据域中。将新节点的指针域指向原链表的头节点。将原链表的头节点指向新节点。具体代码实现如下所示:classNode:def__init__(self,data):self.data=data......
  • 数据结构学习笔记-希尔排序
    希尔排序的算法设计与分析问题描述:设计并分析希尔排序算法【算法设计思想】选择一个初始的增量序列,通常选择数组长度的一半(n/2)作为初始增量。对于每个增量,将数组分割成若干个子序列,每个子序列的长度等于当前增量。例如,如果增量为5,那么数组将被分割成长度为5的子序列。对......
  • 【Java数据结构】详解Stack与Queue(一)
    ......