当前位置：文档之家 › 第二章 线性表-顺序表

第二章 线性表-顺序表

  • 格式：docx
  • 大小：23.10 KB
  • 文档页数：2

第二章 线性表—顺序表

一、 单项选择题

1、线性表是具有n个（ C ）的有限序列。

A、数据表 B、字符 C、数据元素 D、数据项

2、以下（ A ）是一个线性表。

A、由n个实数组成的集合；

B、由n个字符组成的序列；

C、所有整数组成的序列；

D、邻接表

3、线性表的顺序存储结构是一种（ B ）

A、随机存取的存储结构

B、顺序存取的存储结构

C、索引存取的存储结构

D、散列存取的存储结构

4、一个顺序表所占用的存储空间大小与（ B）无关。

A、表的长度 B、元素的存放顺序

C、元素的类型 D、元素中各字段的类型

5、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为了提高效率，应采用（ B ）的存储结构。

A、单链表 B、双向链表

C、单循环链表 D、顺序表

二、 应用题

1、从有序顺序表中删除所有其值重复的元素，使得表中所有元素的值均不同。

void DelListaelem (List L )

{

if ( L.length<=0 )

{

printf( “List is empty!”); exit(1); }

int i = 0, j, k;

elemType temp;

while ( i <= L.length)

{//循环检测

j = i + 1; temp = L.data[i];

while ( j <= L.length )

{ //对于每一个i, 重复检测一遍后续元素

if ( temp == L.data[j] )

{//如果相等, 后续元素前移 for ( k = j+1; k <= L.length; k++ )

L.data[k-1] =L. data[k];

L.length--; //表最后元素位置减1

}

else j++;

}

i++; //检测完L.data[i], 检测下一个

}

}

2、设将n（n>1）个整数存放到一维数组R中。试设计一个算法：将R中保存的序列循环左移p（0

（1）给出算法的基本设计思路；

（2）根据设计思路，采用C语言描述算法，关键之处给出注释；

（3）说明你所设计算法的时间复杂性和空间复杂性

(1)算法基本设计思想：

先将N个数据x0,x1,x2……xp,………xn-1原地逆置，得到Xn-1,…Xp,Xp-1,…,X0,然后再将前n-p个和后P个元素分别原地逆置，得到最终结果：

Xp,Xp+1,…X0,X1,…Xp-1

(2)void Reverse(int r[],int left,int right)

{

Int k=left,i=right,temp;

While(k

Temp=r[k];

r[i]=temp;

k++;i++;

}

}

Void leftshift(int r[],int n,int p)

{ if(p>0 && p

Reverse(r,o,n-1);

Reverse(r,o,n-p-1);

Reverse(r,n-p,n-1);

}

}

(3)时间复杂度为O（n），空间复杂度O（1）.

合集下载

第二章线性表答案

第二章线性表答案

2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

Status OrderListInsert-sq(SqList va, ElemType x) {

//将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法1)

if (va.length==va.listsize){

newbase=(ElemType

*)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType));

if (!newbase) exit(OVERFLOW);

va.elem=newbase;

va.listsize+=LISTINCREMENT;

}//当前存储空间已满，增加分配空间

if (!va.length) {va.elem[0]=x; ++va.length; return OK;}

q=&(va.elem[0]);

while (*q<=x)&&(q<=&(va.elem[va.length-1])) ++q; //查找插入位置

for (p=&(va.elem[va.length-1]); p>=q; --p) *(p+1)=*p;

*q=x;

++va.length;

return OK;

}//OrderListInsert-sq

Status OrderListInsert-sq(SqList va, ElemType x) {

//将x插入到递增有序的顺序表va中，插入后va仍然递增有序(算法2)

if (va.length==va.listsize){

newbase=(ElemType

*)realloc(va.elem,(va.listsize+LISTINCREMENT)*sizeof(ElemType));

数据结构习题及答案与实验指导(线性表)2

数据结构习题及答案与实验指导(线性表)2

1 第2章 线性表

线性表是一种最基本、最常用的数据结构，它有两种存储结构——顺序表和链表。本章主要介绍线性表的定义、表示和基本运算的实现。重点讨论了线性表的存储结构，以及在顺序、链式两种存储结构上基本运算的实现。

重点提示：

 线性表的逻辑结构特征

 线性表的顺序存储和链式存储两种存储结构的特点

 在两种存储结构下基本操作的实现

2-1 重点难点指导

2-1-1 相关术语

1．线性表

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为：(a1,a2,…,an)，其中n为表长，n=0时称为空表。

要点：一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关系。

2．顺序表

顺序存储的线性表。

要点：按线性表中的元素的逻辑顺序依次存放在地址连续的存储单元里，其存储特点：用物理上的相邻实现逻辑上的相邻。

3．链表

用链表存储的线性表。

要点：链表是通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，对每个结点的地址是否连续没有要求。

4．单链表

每个结点除了数据域外还有一个指向其后继的指针域。

要点：通常将每个元素的值和其直接后继的地址作为一个结点，通过每个结点中指向后继结点的指针表示线性表的逻辑结构。

5．头指针

要点：头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在指针变量H、L中。通常用头指针来惟一标识一个链表。

6．头结点

要点：附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点；为空表时，该指针域为空。

2 7．头结点的作用

要点：其作用有两个，一是使对空表和非空表的处理得到统一；二是在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。

2-1-2 线性表的顺序存储

1．顺序表

数据结构考研笔记整理(全)

数据结构考研笔记整理(全)

数据结构考研笔记整理（全）

一、 第二章 线性表

● 考纲内容

● 一、线性表的基本概念

● 线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑

结构，实现线性表的存储结构为顺序表或者链表

● 二、线性表的实现

● 1、顺序表

● 定义(静态分配)

● #define MaxSize 50 \\ typedef struct{ \\ ElemType data[MaxSize];\\ int

length;\\ }SqList;

● 定义(动态分配)

● #define MaxSize 50\\ typedef strcut{\\ EleType *data; //指示动态非配

数组的指针\\ int MaxSize,length;\\ }SqList;

● c的动态分配语句为

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

● c++动态分配语句为L.data=new ElemType[InitSize];

● 插入操作

● 删除操作

● 按值寻找

● 2、链表

● 单链表

● 单链表的定义

●

● 头插法建立单链表

●

● 尾插法建立单链表

●

● 按序号查找getElem(LinkList L,int i)和按值查找locateElem(LinkList

L,ElemType e)

● 插入结点（后插）

● p=getElem(L,i-1); //查找插入位置的前驱结点\\ s.next=p.next;\\

p.next=s;

● 将前插操作转化为后插操作,即先将s插入的p的后面然后调换s

和p的数据域

● s.next=p.next;\\ p.next=s.next;\\ temp=p.data;\\ p.data=s.data;\\

s.data=temp;

● 删除结点

● p.getElem(L,i-1);\\ q=p.next;\\ p.next=q.next;\\ free(q);

线性表的顺序存储——顺序表

线性表的顺序存储——顺序表

线性表的顺序存储——顺序表

之前我们讲了线性表, 本篇来阐述下线性表的顺序存储——顺序表

定义

线性表的顺序存储⼜称为顺序表, 它是⽤⼀组地址连续的存储单元依次存储线性表中的数据元素. 逻辑上相邻的两个数据元素在物理位置上同样相邻.

规律

顺序表中逻辑顺序与物理顺序相同L = ($a_{1}$, $a_{2}$, ..., $a_{i}$, $a_{i + 1}$, ..., $a_{n}$)

其中在逻辑上相邻的两个数据元素，在顺序表中也存放在相同的存储单元当中，每⼀个⼩格⼦就代表⼀个存储单元。

注 线性表中的元素的位序是从1开始, ⽽数组中元素下标是从0开始的

若线性表存储的起始位置为Loc(A), sizeof(ElemType)为每个数据元素所占⽤的存储空间⼤⼩, 那么根据这⼀特点，我们可以计算出每⼀个数据元素存储的地址。

第⼀个元素的地址是 LOC(A)，计算第⼆个元素的地址就可以⽤第⼀个元素的地址加上第⼀个数据元素 $a_{1}$ 所消耗的存储空间，⽤ sizeof 可求得该数据元素所消耗的存储空间⼤

⼩。这⾥需要注意的⼀点是，n 与 MaxSize 是有含义上的不同的，其中 $a_{n}$ 代表的是顺序表中最后⼀个数据元素，⽽ MaxSize 代表的是数组的最后⼀个存储单元。

顺序表的两种实现⽅法

顺序表可以⽤数组来实现。根据数组的两种分配⽅式，也就有两种描述顺序表的⽅法。分别是静态描述分配顺序表的⽅法和动态描述分配顺序表的⽅法。⾸先来看数组静态分配时时如

何描述⼀个顺序表的。

静态描述分配顺序表

#define MaxSize 50

typedef struct{

ElemType data[MaxSize];

int length;

}SqList;

这就是描述顺序表的语句。第⼀句是定义了⼀个宏，也就是定义线性表的最⼤长度为 50，同时这也是数组的最⼤容量。接着定义了⼀个结构体。结构体就是把多个基本数据类型组合

到⼀起构成⼀个新的数据类型。它的定义语句是⽤ typedef struct ，然后⽤⼤括号圈起来所要包含的基本数据类型。最后 SqList 代表着该结构体的名字。