数据结构简明备忘录 线性表
发布时间:2024-01-25 01:59:28
标签:数据结构,线性表
线性表
线性表是线性结构的抽象,线性结构的特点是结构中的数据元素之间存在一对一的线性关系。
数据元素之间的位置关系是一个接一个的排列:
.除第一个位置的数据元素外,其他数据元素位置的前面都只有一个数据元素。
.除最后一个位置的外,其他数据元素位置的后面都只有一个元素。
线性表通常表示为: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


猜你喜欢
- 之前一直遇到js插件生成的元素,click事件无效的问题,重新绑定也不行,终于找到解决方法,在此记下来。同时加深对js事件处理机制的理解。1
- 基本属性cv2.imread(文件名,属性) 读入图像属性:指定图像用哪种方式读取文件 cv2.IMREAD_COLOR:读入彩色图像,默认
- 首先创建一个csv文件,创建方式为新建一个文本文档,然后将这个文本文档重命名为test.csv再用Excel打开,添加内容内容如下:先来添加
- 利用oracle的dbms_random包结合rownum来实现,示例如下,随机取499户:select * from ( select *
- --取得所有数据库名 包括系统数据库 --SELECT name FROM master.dbo.sysdatabases --取得所有非系
- 在网络中传输数据时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送,令牌桶算法就实现了这个功能, 可控制发送到网络上
- 字符串在 Python 中创建字符串对象非常容易。只要将所需的文本放入一对引号中,就完成了一个新字符串的创建(参见清单 1)。如果稍加思考的
- Mysql的left join无效及使用今天写sql发现使用left join 没有把左边表的数据全部查询出来,让我郁闷了一会,后来仔细研究
- 实例的背景说明假定一个个人信息系统,需要记录系统中各个人的故乡、居住地、以及到过的城市。数据库设计如下:Models.py 内容如下:&nb
- 本文实例为大家分享了Python端口扫描的实现代码,供大家参考,具体内容如下获取本机的IP和端口号:import socket def ge
- 实现代码如下:# -*- coding: utf-8 -*-import math, random,timeimport threading
- 1. 对于数组array乘就是对应位置的元素相乘:X1 = np.array([[1,2], [3, 4]])X2 = X1print X2
- 说起 Python 强大的地方,你可能想到是它的优雅、简洁、开发速度快,社区活跃度高。但真正使得这门语言经久不衰的一个重要原因是它的无所不能
- 一、介绍在做YOLOv3项目时,会需要将文本文件中的某部分内容进行批量替换和修改,所以编写了python程序批量替换所有文本文件 * 定部分的
- 哈喽兄弟们,今天来分享一下,Python初学者必须要学会的技能,Python进行debug操作。本文用的测试代码:from torchvis
- 视频读取视频读取,主要利用VideoCapture类下的方法打开视频并获取视频中的帧,具体示例如下:#include<iostream
- 一、背景最近学校校园网不知道是什么情况,总出现掉线的情况。每次掉线都需要我手动打开web浏览器重新进行账号密码输入,重新进行登录。系统的问题
- 登录百度,首先当然是先抓百度的登录包 ,由于是网页登录,最方便的自然是httpwatch了,我使用的测试账号是itiandatest1,密码
- 一、VS2008工程设置工作 首先,建立一个windows应用程序的工程,将C/C++->预处理器->预处理器定义下的_WIND
- 本文实例为大家分享了js实现固定区域内的不重叠随机圆,供大家参考,具体内容如下关键词:js、固定区域、不重叠、随机圆,半径固定、半径随机最近