数据结构简明备忘录 线性表

线性表

线性表是线性结构的抽象,线性结构的特点是结构中的数据元素之间存在一对一的线性关系。
数据元素之间的位置关系是一个接一个的排列:
.除第一个位置的数据元素外,其他数据元素位置的前面都只有一个数据元素。
.除最后一个位置的外,其他数据元素位置的后面都只有一个元素。
线性表通常表示为:L=(D,R)
D是数据元素的有限集合
R是数据元素之间关系的有限集合

线性表的基本操作:


代码如下:

public interface IListDS<T> {
int GetLength(); //求长度
void Clear(); //清空
bool IsEmpty(); //判空
void Append(T item); //附加
void Insert(T item, int i); //插入
T Delete(int i); //删除
T GetElement(int i); //取表元素
int Locate(T value); //按值查找
}

顺序表

顺序表是线性表的顺序存储(Sequence Storage),是指在内存中用一块地址连续的空间依次存放线性表的数据元素(Sequence List),具有随机存取的特点。

w: 每个数据元素占w个存储单元
A1:顺序表的基地址(Base Address)
Loc(Ai)=Loc(A1)+(i-1)*w 1<=i<=n

为了理解顺序表,闪电学习了这样一个例题,有兴趣的朋友可以在自己的机器上写一下。
有数据类型为整型的顺序表La和Lb,其数据元素均按从小到大的升序排列,编写一个算法将它们合并成一个表Lc,要求Lc中数据元素也按升序排列。
算法思路:
依次扫描La和Lb的数据元素,比较La和Lb当前数据元素的值,将较小值的数据元素赋给Lc,如此直到一个顺序表被扫描完,然后将未完的那个顺序表中余下的数据元素赋给Lc即可。Lc的容量要能够容纳La和Lb两个表相加的长度。
思路图示:



代码如下:

public class SeqList<T> : IListDS<T> {
private int maxsize; //顺序表的容量
private T[] data; //数组,用于存储顺序表中的数据元素
private int last; //指示顺序表最后一个元素的位置

//构造器
public SeqList(int size)
{
data = new T[size];
maxsize = size;
last = -1; //如果顺序表为空,last=-1
}
//索引器
public T this[int index]
{
get { return data[index]; }
set { data[index] = value; }
}
//最后一个元素的位置属性
public int Last
{
get { return last; }
}
//容量属性
public int Maxsize
{
get { return maxsize; }
set { maxsize = value; }
}
//判断顺序表是否为空
public bool IsEmpty()
{
if (last == -1)
return true;
else
return false;
}
//判断顺序表是否为满
public bool IsFull()
{
if (last == maxsize - 1)
return true;
else
return false;
}
//求顺序表的长度
public int GetLength()
{
return last + 1;
}
//清空顺序表
public void Clear()
{
last = -1;
}
//在顺序表末尾添加新元素
public void Append(T item)
{
if (IsFull())
{
Console.WriteLine("List is full.");
return;
}
data[++last] = item;
}

//在顺序表第i个数据元素位置插入一个数据元素
public void Insert(T item, int i)
{
if (IsFull())
return;
if (i < 1 || i > last + 2)
return;
if (i == last + 2)
data[last + 1] = item;
else
{
for (int j = last; j >= i - 1; --j)
{
data[j + 1] = data[j];
}
data[i - 1] = item;
}
++last;
}
//删除顺序表的第i个数据元素
public T Delete(int i)
{
T tmp = default(T);
if (IsEmpty())
return tmp;
if (i < 1 || i > last + 1)
return tmp;
if (i == last + 1)
tmp = data[last--];
else
{
tmp = data[i - 1];
for (int j = i; j <= last; ++j)
data[j] = data[j + 1];
}
--last;
return tmp;
}
//获得顺序表的第i个数据元素
public T GetElement(int i)
{
if (IsEmpty() || (i < 1) || (i > last + 1))
return default(T);
return data[i-1];
}
//在顺序表中查找值为value的数据元素
public int Locate(T value)
{
if (IsEmpty())
return -1;
int i = 0;
for (i = 0; i <= last; ++i)
{
if (value.Equals(data[i]))
break;
}
if (i > last)
return -1;
return i;
}
}

代码如下:

public class GenericList
{
public GenericList()
{ }
public SeqList<int> Merge(SeqList<int> La, SeqList<int> Lb)
{
SeqList<int> Lc = new SeqList<int>(La.Maxsize+Lb.Maxsize);
int i = 0;
int j = 0;
int k = 0;
//两个表中元素都不为空
while ((i <= (La.GetLength() - 1)) && (j <= (Lb.GetLength() - 1)))
{
if (La[i] < Lb[j])
Lc.Append(La[i++]);
else
Lc.Append(Lb[j++]);
}
//a表中还有数据元素
while (i <= (La.GetLength() - 1))
Lc.Append(La[i++]);
//b表中还有数据元素
while (j <= (Lb.GetLength() - 1))
Lc.Append(Lb[j++]);
return Lc;
}
}

客户端代码:


代码如下:

static void Main(string[] args)
{
SeqList<int> sl1 = new SeqList<int>(4);
sl1.Append(1);
sl1.Append(3);
sl1.Append(4);
sl1.Append(7);
SeqList<int> sl2 = new SeqList<int>(6);
sl2.Append(2);
sl2.Append(5);
sl2.Append(6);
sl2.Append(8);
sl2.Append(11);
sl2.Append(14);
GenericList gl = new GenericList();
SeqList<int> sl3 = gl.Merge(sl1, sl2);
Console.WriteLine("length:" + sl3.GetLength());
for (int i = 0; i < sl3.GetLength(); i++)
{
Console.WriteLine(i + ":" + sl3[i]);
}
}

好了,下一次学习链表。
作者:LevinLee

时间: 2010-03-29

Python常见数据结构详解

本文详细罗列归纳了Python常见数据结构,并附以实例加以说明,相信对读者有一定的参考借鉴价值. 总体而言Python中常见的数据结构可以统称为容器(container).而序列(如列表和元组).映射(如字典)以及集合(set)是三类主要的容器. 一.序列(列表.元组和字符串) 序列中的每个元素都有自己的编号.Python中有6种内建的序列.其中列表和元组是最常见的类型.其他包括字符串.Unicode字符串.buffer对象和xrange对象.下面重点介绍下列表.元组和字符串. 1.列表 列表是

python数据结构之二叉树的建立实例

先建立二叉树节点,有一个data数据域,left,right 两个指针域 复制代码 代码如下: # -*- coding: utf - 8 - *- class TreeNode(object): def __init__(self, left=0, right=0, data=0):        self.left = left        self.right = right        self.data = data 复制代码 代码如下: class BTree(object):

python实现bitmap数据结构详解

bitmap是很常用的数据结构,比如用于Bloom Filter中:用于无重复整数的排序等等.bitmap通常基于数组来实现,数组中每个元素可以看成是一系列二进制数,所有元素组成更大的二进制集合.对于Python来说,整数类型默认是有符号类型,所以一个整数的可用位数为31位. bitmap实现思路 bitmap是用于对每一位进行操作.举例来说,一个Python数组包含4个32位有符号整型,则总共可用位为4 * 31 = 124位.如果要在第90个二进制位上操作,则要先获取到操作数组的第几个元素,

Python实现基本线性数据结构

数组 数组的设计 数组设计之初是在形式上依赖内存分配而成的,所以必须在使用前预先请求空间.这使得数组有以下特性: 1.请求空间以后大小固定,不能再改变(数据溢出问题): 2.在内存中有空间连续性的表现,中间不会存在其他程序需要调用的数据,为此数组的专用内存空间: 3.在旧式编程语言中(如有中阶语言之称的C),程序不会对数组的操作做下界判断,也就有潜在的越界操作的风险(比如会把数据写在运行中程序需要调用的核心部分的内存上). 因为简单数组强烈倚赖电脑硬件之内存,所以不适用于现代的程序设计.欲使用可

python数据结构树和二叉树简介

一.树的定义 树形结构是一类重要的非线性结构.树形结构是结点之间有分支,并具有层次关系的结构.它非常类似于自然界中的树.树的递归定义:树(Tree)是n(n≥0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:(1)有且仅有一个特定的称为根(Root)的结点:(2)其余的结点可分为m(m≥0)个互不相交的子集Tl,T2,-,Tm,其中每个子集本身又是一棵树,并称其为根的子树(Subree). 二.二叉树的定义 二叉树是由n(n≥0)个结点组成的有限集合.每个结点最多有两个子树的有序树

Python中列表、字典、元组、集合数据结构整理

本文详细归纳整理了Python中列表.字典.元组.集合数据结构.分享给大家供大家参考.具体分析如下: 列表: 复制代码 代码如下: shoplist = ['apple', 'mango', 'carrot', 'banana'] 字典: 复制代码 代码如下: di = {'a':123,'b':'something'} 集合: 复制代码 代码如下: jihe = {'apple','pear','apple'} 元组: 复制代码 代码如下: t = 123,456,'hello' 1.列表 空

python数据结构之二叉树的遍历实例

遍历方案   从二叉树的递归定义可知,一棵非空的二叉树由根结点及左.右子树这三个基本部分组成.因此,在任一给定结点上,可以按某种次序执行三个操作:   1).访问结点本身(N)   2).遍历该结点的左子树(L)   3).遍历该结点的右子树(R) 有次序:   NLR.LNR.LRN 遍历的命名 根据访问结点操作发生位置命名:NLR:前序遍历(PreorderTraversal亦称(先序遍历))  --访问结点的操作发生在遍历其左右子树之前.LNR:中序遍历(InorderTraversal)

C#数据结构与算法揭秘二 线性结构

上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构--线性结构. 什么是线性结构,线性结构是最简单.最基本.最常用的数据结构.线性表是线性结构的抽象(Abstract), 线性结构的特点是结构中的数据元素之间存在一对一的线性关系. 这 种一对一的关系指的是数据元素之间的位置关系,即: (1)除第一个位置的数据元素外,其它数据元素位置的前面都只有一个数据元素: (2)除最后一个位置的数据元素外,其它数据元素位置的后面都只有一个元素.也就是说,数据元素是一个接一个的排

C#数据结构与算法揭秘二

上文对数据结构与算法,有了一个简单的概述与介绍,这篇文章,我们介绍一中典型数据结构--线性结构. 什么是线性结构,线性结构是最简单.最基本.最常用的数据结构.线性表是线性结构的抽象(Abstract), 线性结构的特点是结构中的数据元素之间存在一对一的线性关系. 这 种一对一的关系指的是数据元素之间的位置关系,即: (1)除第一个位置的数据元素外,其它数据元素位置的前面都只有一个数据元素: (2)除最后一个位置的数据元素外,其它数据元素位置的后面都只有一个元素.也就是说,数据元素是一个接一个的排

C#数据结构与算法揭秘一

这里,我们 来说一说C#的数据结构了. ①什么是数据结构.数据结构,字面意思就是研究数据的方法,就是研究数据如何在程序中组织的一种方法.数据结构就是相互之间存在一种或多种特定关系的数据元素的集合. 程序界有一点很经典的话,程序设计=数据结构+算法.用源代码来体现,数据结构,就是编程.他有哪些具体的关系了, (1) 集合(Set):如图 1.1(a)所示,该结构中的数据元素除了存在"同属于一个集合"的关系外,不存在任何其它关系. 集合与数学的集合类似,有无序性,唯一性,确定性. (2)

C#数据结构与算法揭秘三 链表

上文我们讨论了一种最简单的线性结构--顺序表,这节我们要讨论另一种线性结构--链表. 什么是链表了,不要求逻辑上相邻的数据元素在物理存储位置上也相邻存储的线性结构称之为链表.举个现实中的例子吧,假如一个公司召开了视频会议的吧,能在北京总公司人看到上海分公司的人,他们就好比是逻辑上相邻的数据元素,而物理上不相连.这样就好比是个链表. 链表分为①单链表,②单向循环链表,③双向链表,④双向循环链表. 介绍各种各样链表之前,我们要明白这样一个概念.什么是结点.在存储数据元素时,除了存储数据元素本身的信息

C#数据结构与算法揭秘五 栈和队列

这节我们讨论了两种好玩的数据结构,栈和队列. 老样子,什么是栈, 所谓的栈是栈(Stack)是操作限定在表的尾端进行的线性表.表尾由于要进行插入.删除等操作,所以,它具有特殊的含义,把表尾称为栈顶(Top) ,另一端是固定的,叫栈底(Bottom) .当栈中没有数据元素时叫空栈(Empty Stack).这个类似于送饭的饭盒子,上层放的是红烧肉,中层放的水煮鱼,下层放的鸡腿.你要把这些菜取出来,这就引出来了栈的特点先进后出(First in last out).   具体叙述,加下图. 栈通常记

C#数据结构与算法揭秘四 双向链表

首先,明白什么是双向链表.所谓双向链表是如果希望找直接前驱结点和直接后继结点的时间复杂度都是 O(1),那么,需要在结点中设两个引用域,一个保存直接前驱结点的地址,叫 prev,一个直接后继结点的地址,叫 next,这样的链表就是双向链表(Doubly Linked List).双向链表的结点结构示意图如图所示. 双向链表结点的定义与单链表的结点的定义很相似, ,只是双向链表多了一个字段 prev.其实,双向链表更像是一根链条一样,你连我,我连你,不清楚,请看图. 双向链表结点类的实现如下所示

Python数据结构与算法之图结构(Graph)实例分析

本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简

Python数据结构与算法之二叉树结构定义与遍历方法详解

本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历  采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde

详解常用查找数据结构及算法(Python实现)

一.基本概念 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录). 查找表(Search Table):由同一类型的数据元素(或记录)构成的集合 关键字(Key):数据元素中某个数据项的值,又称为键值. 主键(Primary Key):可唯一地标识某个数据元素或记录的关键字. 查找表按照操作方式可分为: 静态查找表(Static Search Table):只做查找操作的查找表.它的主要操作是: 查询某个"特定的"数据元素是否在表中

JS中数据结构与算法---排序算法(Sort Algorithm)实例详解

排序算法的介绍 排序也称排序算法 (Sort Algorithm),排序是将 一组数据 , 依指定的顺序 进行 排列的过程 . 排序的分类 1)  内部排序 : 指将需要处理的所有数据都加载 到 内部存储器(内存) 中进行排序. 2) 外部排序法: 数据量过大,无法全部加载到内 存中,需要借助 外部存储(文件等) 进行 排序. 常见的排序算法分类 算法的时间复杂度 度量一个程序(算法)执行时间的两种方法 1.事后统计的方法 这种方法可行, 但是有两个问题:一是要想对设计的算法的运行性能进行评测,