Categories: 算法相关

线性表

线性表定义:

线性表(Linear List)是由n(n≥0)个数据元素(结点)a1,a2,…,an组成的有限序列。
① 数据元素的个数n定义为表的长度(n=0时称为空表)。
② 将非空的线性表(n>0)记作:(a1,a2,…,an
③ 数据元素ai(1≤i≤n)只是个抽象符号,其具体含义在不同情况下可以不同。

         【例1】英文字母表(A,B,…,Z)是线性表,表中每个字母是一个数据元素(结点)

【例2】一副扑克牌的点数(2,3,…,10,J,Q,K,A)也是一个线性表,其中数据元素是每张牌的点数
线性表的特征:

  1. 有且只有一个“首元素”。
  2. 有且只有一个“末元素”。
  3. 除末元素外,其余元素均有唯一的后继元素。
  4. 除首元素外,其余元素均有唯一的前驱元素。

常见线性表的基本操作:

1  InitList(L)

构造一个空的线性表L,即表的初始化。

2 ListLength(L)

求线性表L中的结点个数,即求表长。

3 GetNode(L,i)

取线性表L中的第i个结点,这里要求1≤i≤ListLength(L)

4 LocateNode(L,x)

在L中查找值为x 的结点,并返回该结点在L中的位置。若L中有多个结点的值和x 相同,则 返回首次找到的结点位置;若L中没有结点的值为x ,则返回一个特殊值表示查找失败。

5 InsertList(L,x,i)

在线性表L的第i个位置上插入一个值为x 的新结点,使得原编号为i,i+1,…,n的结点变为编号为i+1,i+2,…,n+1的结点。这里1≤i≤n+1,而n是原表L的长度。插入后,表L的长度加1。

6 DeleteList(L,i)

删除线性表L的第i个结点,使得原编号为i+1,i+2,…,n的结点变成编号为i,i+1,…,n-1的结点。这里1≤i≤n,而n是原表L的长度。删除后表L的长度减1。

转自 http://itjoy.org/?p=137

龚杰洪

Share
Published by
龚杰洪

Recent Posts

GOLANG面试八股文-并发控制

背景 协程A执行过程中需要创建…

1 年 ago

MYSQL面试八股文-常见面试问题和答案整理二

索引B+树的理解和坑 MYSQ…

1 年 ago

MYSQL面试八股文-InnoDB的MVCC实现机制

背景 什么是MVCC? MVC…

1 年 ago

MYSQL面试八股文-索引类型和使用相关总结

什么是索引? 索引是一种用于加…

1 年 ago

MYSQL面试八股文-索引优化之全文索引(解决文本搜索问题)

背景:为什么要有全文索引 在当…

1 年 ago