网站程序0day,优秀高端网站建设企业,亚马逊建站服务,有没有做游戏评测的网站线性表 前言——线性结构线性表线性表的定义线性表的特点线性表的存储结构顺序存储链式存储单链表双向链表循环链表静态链表 前言——线性结构
线性结构是一种基本的数据结构#xff0c;主要用于对客观世界中具有单一前驱和后继的数据关系进行描述。线性结构的特点是数据元素… 线性表 前言——线性结构线性表线性表的定义线性表的特点线性表的存储结构顺序存储链式存储单链表双向链表循环链表静态链表 前言——线性结构
线性结构是一种基本的数据结构主要用于对客观世界中具有单一前驱和后继的数据关系进行描述。线性结构的特点是数据元素之间呈现一种线性关系即元素“一个接一个排列”。 线性表
线性表的定义 线性结构 线性表是最简单、最基本也是最常用的一种线性结构 存储结构 顺序存储、链式存储 基本操作 插入、删除和查找
线性表的特点
线性表可为空。非空线性表的特点如下
存在唯一一个称为“第一个”的元素存在唯一一个称为“最后一个”的元素除第一个元素外每个元素都有且只有一个直接前驱除最后一个元素外每个元素都有且只有一个直接后继
线性表的存储结构
线性表的存储结构分为顺序存储和链式存储。 顺序存储
基础概念
精辟 用一组地址连续的存储单元依次存储线性表中的数据元素从而使得逻辑上相邻的两个元素在物理位置上也相邻。公式 以 L O C ( a 1 ) LOC(a_1) LOC(a1) 表示线性表中第一个元素的存储位置在顺序存储结构中第 i i i 个元素 a i a_i ai 的存储位置为 L O C ( a i ) L O C ( a 1 ) ( i − 1 ) ∗ L LOC(a_i) LOC(a_1) (i-1) * L LOC(ai)LOC(a1)(i−1)∗L 其中 L L L 表示每个数据元素所占空间的字节数。优点 可以随机存取表中的元素根据上述的公式我们可以根据计算关系得知表中任一个元素的位置。缺点 插入和删除操作需要移动元素在插入前要移动元素以挪出空的存储单元然后再插入元素删除时同样需要移动元素以填充被删除元素空出来的存储单元。
基本操作
插入 在表长为 n n n 的线性表中插入新元素时共有 n 1 n1 n1 个插入位置。在位置 1 1 1 插入新元素表中原有 n n n 个元素都需要移动在位置 n 1 n1 n1 插入新元素时不需要移动任何元素。因此等概率下插入一个新元素需要移动的元素个数期望 E i n s e r t E_{insert} Einsert 为 E i n s e r t ∑ i 1 n 1 P i ∗ n − i 1 1 n 1 ∑ i 1 n 1 ( n − i 1 ) n 2 E_{insert} \sum ^{n1} _{i1} P_i *n-i1 \frac 1 {n1} \sum ^{n1} _{i1} (n-i1) \frac n 2 Einserti1∑n1Pi∗n−i1n11i1∑n1(n−i1)2n 其中 P i P_i Pi 表示在表中的位置 i i i 插入新元素的概率。删除 在表长为 n n n 的线性表中删除元素时共有 n n n 个可删除的元素。删除元素 a 1 a_1 a1 时需要移动 n − 1 n-1 n−1 个元素删除元素 a n a_n an 时不需要移动元素。因此等概率下删除一个元素需要移动的元素个数期望 E d e l e t e E_{delete} Edelete 为 E d e l e t e ∑ i 1 n q i ∗ ( n − i ) 1 n ∑ i − 1 n ( n − i ) n − 1 2 E_{delete} \sum ^{n} _{i1} q_i*(n-i)\frac 1 n \sum ^{n} _{i-1} (n-i) \frac {n-1} 2 Edeletei1∑nqi∗(n−i)n1i−1∑n(n−i)2n−1 其中 q i q_i qi 表示删除第 i i i 个元素即 a i a_i ai的概率。 链式存储 线性表的链式存储是通过指针链接起来的结点来存储数据元素基本结点结构为 其中数据域用于存储数据元素的值指针域用于存储当前元素的直接前驱或直接后继的位置信息。指针域中的信息称为指针或链。
单链表
因为链式存储存储各元素的结点的地址并不要求是连续的因此存储数据元素的同时必须存储元素之间的逻辑关系。结点与结点之间通过指针域构成一个链表若节点中只有一个指针域则称为单链表或称线性链表。 假设单链表中的元素是整型则单链表结构类型的定义为
typedef struct node{int data; /*结点的数据域假设为整型*/struct node *next; /*结点的指针域*/
}NODE, *LinkList在链式存储结构中只需要一个指针称为头指针上图中 head指向第一个结点就可以顺序地访问到表中的任意一个元素。
在链式存储结构下进行插入和删除元素其实实质上都是对相关指针的修改。 插入
在单链表中若在 p p p 所指结点后插入新结点 s s s基本步骤如下
s-next p-next;
p-next s;我们先将 p p p 所指结点的后继结点指针赋给 s s s 所指结点的指针域然后将 p p p 所指结点的指针域修改为 s s s 所指结点。
删除
在单链表中删除 p p p 所指结点的后继结点时步骤如下
q p-next;
p-next p-next-next;
free(q)我们先令临时指针 q q q 指向待删除的结点然后修改 p p p 所指结点的指针域为指向 p p p 所指向结点的后继的后继结点从而将元素所在结点从链表中删除最后释放 q q q 所指结点的空间。
头结点
在实际应用中为了简化对链表状态的判定和处理特别引入一个不存储数据元素的结点称为头结点将其作为链表的第一个结点并令头指针指向该结点。
单链表的操作查找、插入、删除 单链表的查找操作
LinkList Find_List(LinkList L, int k) /*L为带头结点单链表的头指针*/
/*在表中查找第k个元素若找到返回该元素结点的指针否则返回空指针NULL*/
{LinkList p; int i;i 1; p L-next; /*初始时令p指向第一个元素结点i为计数器*/while(p ik) { /*顺指针链向后查找直到p指向第k个元素结点或p为空指针*/p p-next; i;}if(p ik) return p; /*存在第k个元素且指针p指向该元素结点*/return NULL
} /*Find_List*/单链表的插入操作
int Insert_List(LinkList L, int k, int newElem) /*L为带头结点单链表的头指针*/
/*将元素newElem插入表中的第k个元素之前若成功则返回0否则返回-1*/
/*该插入操作等同于将元素newElem插入在第k-1个元素之后*/
{LinkList p,s; /*p,s为临时指针*/if(k 1) p L; /*元素newElem要插入到第1个元素之前*/else p Find_List(L, k-1) /*查找表中的第k-1个元素并令p指向该元素结点*/if(!p) return -1; /*表中不存在第k-1个元素不满足运算要求*/s (NODE *)malloc(sizeof(NODE)); /*创建新元素的结点空间*/if(!s) return -1;s-data newElem;s-next p-next; p-next s; /*将元素newElem插入到第k-1个元素之后*/return 0;
} /*Insert_List*/单链表的删除操作
int Delete_List(LinkList L, int k) /*L为带头结点的单链表的头指针*/
/*删除表中的第k个元素结点若成功则返回0否则返回-1*/
/*删除第k个元素相当于令第k-1个元素结点的指针域指向第k1个元素所在结点*/
{LinkList p,q; /*p,q为临时指针*/if(k 1) p L; /*删除的是第一个元素结点*/else p Find_List(L, k-1); /*查找表中的第k-1个元素并令p指向该元素结点*/if(!p||!p-next) return -1; /*表中不存在第k个元素*/q p-next; /*令q指向第k个元素结点*/p-next q-next; free(q); /*删除结点*/return 0;
} /*Delete_List*/所以综上当线性表采用链表作为存储结构时我们不能对数据元素进行随机访问但是具有插入和删除操作不需要移动元素的优点。
双向链表
每个结点包含两个指针分别指向当前元素的直接前驱和直接后继。其特点是可以从表中任意的结点出发从两个方向上遍历链表。
若双向链表中结点的 front 和 next 指针域分别指示当前结点的直接前驱和直接后继则在双向链表中插入结点的操作过程表示为
s-front p-front;
p-front-next s;
s-next p;
p-front s;在双向链表中删除结点的操作过程表示为
p-front-next p-next;
p-next-front p-front;
free(p);循环链表
在单向链表或双向链表的基础上令表尾结点的指针指向链表的第一个结点构成循环链表。其特点是可以从表中任意结点开始遍历整个链表。
静态链表
借助数组来描述线性表的链式存储结构用数组元素的下标表示元素所在结点的指针。
