第3章 简单数据结构顺序表

第3章线性表的顺序存储c#实现---《⼤话数据结构》读书笔记

线性表的定义

线性表(List)：零个或多个数据元素的有限序对。

强调:

1. 线性表是有限的。

2. 元素之间是有顺序的。

3. 若存在多个元素，则第⼀个元素⽆前驱，最后⼀个元素⽆后继。

4. 其他每个元素都有且只有⼀个前驱和后继。

数学语⾔定义

若线性表记为(a1,…ai-1,ai,ai+1,…,an)，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当

i=1,2,…，n-1时，ai有且仅有⼀个直接后继，当i=2,3,…n时，ai有且仅有⼀个直接前驱。

线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。

线性表的顺序存储结构

顺序存储的定义

线性表的顺序存储结构，指的是⽤⼀段地址连续的存储单元依次存储线性表的数据元素。

a1a2……ai-1ai……an

顺序表⾄少需要3个属性

1. 存储空间：⼀个⼀维数组，它的存储位置就是存储空间的存储位置。

2. 线性表的最⼤存储容量：数组长度MaxSize。

3. 线性表的当前长度:length。

注意

这⾥有2个概念：“数组的长度”和“线性表的长度“需要区分下

数组的长度是存放线性表的存储空间的长度，存储分配以后这个量是不变的。

线性表的长度是线性表中数据元素的个数，随着线性表的插⼊和删除等操作的进⾏，这个量是变化的。

地址的计算⽅法

存储器中每个存储单元都有⾃⼰的编号，这个编号称为地址。

假设线性表的每个元素占⽤c个存储单元，那么线性表中第i+1个数据元素的存储位置和i个数据元素的存储位置满⾜下列关系(LOC表⽰获得

存储位置的函数)。

LOC(ai+1)=LOC(ai)+c;

LOC(ai)=LOC(a1)+(i-1)*c;

--------------------------代码------------------------------

class Program

一、选择

1、 设输入序列为1，2，3，4。借助一个栈可以得到的输出序列是（ ）。

A. 1，3，4，2 B. 3，1，4，2 C. 4，3，1，2 D. 4，1，2，3

2、 一个队列的入队序列是1，2，3，4，则队列的出队序列是（ ）。

A. 1，3，4，2 B. 3，1，4，2 C. 4，3，1，2 D. 1，2，3，4

3、 栈和队列都是（ ）。

A. 顺序存储的线性表 B. 链式存储的线性表

C. 限制存储点的线性表 D. 限制存储点的非线性结构

4、 队列通常采用两种存储结构是( )

A.顺序存储结构和链表存储结构 B.和索引方式

C.链表存储结构和散列方式 D.线性存储结构和非线性存储结构

5、 设循环队列用数组A[n]存储，头尾指针分别为front和rear。求解当前队列中元素个数的公式是 ( )

A .rear-front B. front-rear

C.n-(front-rear) D. (n+rear-front)%n

二、填空

1、 设有一个链栈，其中各结点中有data和next两字段 ，栈顶指针为Ls（≠NULL）， 则执行退栈的基本操作是____________________。则S指针所指向的结点入栈操作的语句为：S->next=Ｌs；Ｌs=______________。

2、 设数组Ｂ[5][6]的元素占４个单元。从首地址1000开始将其按行优先方式存储，则元素Ｂ[3][2]的地址为______________。

3、 在具有n个单元的循环队列中，队满时共有______________个元素。

4、 循环队列判满的条件是______________________。

第3章 数据结构

一、选择题

1. 图形结构是数据元素之间存在一种____B_____。

A 一对多关系 B 多对多关系 C 多对一关系 D 一对一关系

2.算法分析的目的是___C_____。

A 找出数据结构的合理性 B 研究算法中的输入和输出的关系

C 分析算法的效率以求改进 D 分析算法的易懂性和文档性

3.算法的时间复杂度与___A____ 有关。

A 问题规模

B 计算机硬件性能

C 程序设计语言的类型或版本

D 算法设计者的水平

4.有下面的算法段：

for (i=0; i

k++;

其时间复杂度为 B 。

A．O(1) B．O(n) C．O(log2n) D．O(n2)

5.计算机算法必须具备输入、输出和___C____。

A、计算方法 B、排序方法

C、解决问题的有限运算步骤 D、程序设计法

6.____B___是数据的基本单位。

A、数据结构 B、数据元素 C、数据项 D、数据类型

7.下面，对非空线性表特点的论述， ___C____ 是正确的。

A．所有结点有且只有一个直接前驱

B．所有结点有且只有一个直接后继

C．每个结点至多只有一个直接前驱，至多只有一个直接后继

D．结点间是按照1对多的邻接关系来维系其逻辑关系的

8.在顺序表中，只要知道____D____，就可以在相同的时间内求出任一结点的存储地址。

A、开始结点 B、终端结点 C、向量大小 D、基地址和结点大小

9.在非空线性表中，有且只有一个直接前驱和一个直接后继的结点是__C____。

A、开始结点 B、终端结点 C、内部结点 D、所有结点

10.顺序表中逻辑上相邻的结点的物理位置为_____A___。

《数据结构》第2章线性表第2 章线性表

第2页第2章线性表要求对数据的线性存储结构有较深刻的理解。理解线性表、向量的逻辑特性，熟悉掌握施加于它们的基本操作的算法和应用。重点1.线性表的逻辑特性及存储表示。2.顺序表上元素的操作。第2 章线性表

第3页基本内容1、线性表的逻辑结构定义和存储结构的描述方法。2、在线性表的顺序存储结构上如何实现基本操作。第2章线性表第2 章线性表

第4页学习要点1、了解线性表的逻辑结构特性2、掌握线性表顺序存储结构的描述方法3、掌握在顺序存储结构上实现线性表基本操作（查找、插入、删除等）的方法4、知道从时间和空间复杂度的角度分析线性表顺序存储结构的特点及使用场合第2章线性表第2 章线性表第5页线性结构的特点在数据元素的非空有限集中，1、线性表的逻辑结构第2章线性表(1) 存在唯一的一个被称做“第一个”的数据元素；(2) 存在唯一的一个被称做“最后一个”的数据元素；(3) 除第一个数据元素之外，集合中的每个数据元素均只有一个前驱；(4) 除最后一个数据元素之外，集合中的每个数据元素均只有一个后继。第2 章线性表第6页线性表的定义1、线性表的逻辑结构线性表(Linear List)是由元素组成的一种有限序列，是一种具有线性结构特点的数据结构。其中元素的个数为线性表的长度。长度为零的线性表为空表。第2 章线性表第7页线性表的形式定义1、线性表的逻辑结构含有n个数据元素的线性表是一个数据结构Linear_list = (D, R)其中D={ai|ai∈D0,i=1,2,···,n, n≥0}R={N}N={|ai-1,ai∈D0,i=2,3,···,n }D0为某个数据对象N为一个序偶的集合若n>0，则通常将线性表记作L=(a1，a2，···, ai，···, an) (i=1, 2, ···, n)第2 章线性表

第8页1、线性表的逻辑结构上述线性表表明了1）同一线性表中的数据元素具有共同特性，属于同一数据对象。此乃线性表的均匀性；2）线性表中各数据元素之间是有位置顺序的，即a1是第一个元素；an是最后一个元素；除a1外，ai （i=2,3,···,n ）均有且仅有一个直接前趋ai -1；除an外，ai （i=1, 2, ···,n-1）均有且仅有一个直接后继ai +1；3）数据元素ai 在该线性表中第i（i=1, 2, ···,n）个位置上；4）线性表中元素的值与元素的位置之间可以有联系，也可以没有联系。第2 章线性表