【数据结构】线性表的基本操作

第1讲 线性表

本章主要掌握如下内容：

线性表的定义和基本操作，线性表的实现,线性表的顺序存储结构及链式存储结构，线性表的应用。

知识点分析

（一）线性表的定义和基本操作

1．线性表基本概念

1）定义：是由相同类型的结点组成的有限序列。如：由n个结点组成的线性表

（ a1, a2, …, an）

a1是最前结点，an是最后结点。结点也称为数据元素或者记录。

2）线性表的长度：线性表中结点的个数称为其长度。长度为0的线性表称为空表。

3）结点之间的关系：设线性表记为（a1,a2,„ai-1 , ai, ai+1 ,„an），称ai-1是ai的直接前驱结点．．．．（简称前驱），ai+1是ai的直接后继结点．．．．（简称后继）。

4）线性表的性质：

① 线性表结点间的相对位置是固定．．的，结点间的关系由结点在表中的位置确定。

② 如果两个线性表有相同的数据结点，但它们的结点顺序不一致，该两个线性表也是不相等的。

注意：线性表中结点的类型可以是任何数据（包括简单类型和复杂类型），即结点可以有多个成分，其中能唯一标识表元的成分称为关键字（key），或简称键。以后的讨论都只考虑键，而忽略其它成分，这样有利于把握主要问题，便于理解。

『经典例题解析』

线性表的特点是每个元素都有一个前驱和一个后继。( )

【答案】错误。

【解析】线性表的第一个数据元素没有前驱，最后一个元素没有后继。其余的所有元素都有一个前驱和后继。

2．线性表的抽象数据类型

线性表是一个相当灵活的数据结构，其长度可以根据需要增加或减少。从操作上讲，用户不仅可以对线性表的数据元素进行访问操作，还可以进行插入、删除、定位等操作。

《数据结构》

实

验

报

告

2 前言

计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。

数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。

3 目录

一、 实验目的

二、 实验内容和要求

三、 源代码

1) 顺序表的代码

2) 单链表的代码

四、 测试结果

1) 顺序表的测试结果

2) 单链表的测试结果

五、心得体会

实验一 线性表的基本操作及其应用

一、实验目的

1、帮助读者复习C++语言程序设计中的知识。

2、熟悉线性表的逻辑结构。

3、熟悉线性表的基本运算在两种存储结构上的实现。 4 4、掌握顺序表的存储结构形式及其描述和基本运算的实现。

5、熟练掌握动态链表结构及有关算法的设计

二、实验内容

题目一：顺序表的基本操作

[问题描述]

实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。

[基本要求]

（1）依次从键盘读入数据，建立带头结点的顺序表；

（2）输出顺序表中的数据元素

（3）求顺序表的长度；

（4）根据指定条件能够取元素和修改元素；

（5）实现在指定位置插入和删除元素的功能。

（6）根据算法，将两个有序的顺序表合并成一个有序顺序表。

随堂测验

一、选择题

1. 在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 （ A ）

个前驱结点；最后一个结点没有后继结点，其余每个结点有且只有（A ）个后继结点。

A. 1 , 1 B. 1 , 2 C. 2 , 1 D. 2 , 2

2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_D__。

A. 必须是连续的 B. 部分地址必须是连续的

C. 一定是不连续的 D. 连续或不连续都可以

3. 指针变量p指向单链表中的结点，若该结点是链表的尾结点，下面正确的说法是(A )。

A. p->next = = NULL B. p->next != NULL

C. p = =NULL D. p->next->next = =NULL

4. 设指针p所指结点不是单链表的尾结点，删除p所指结点的后继结点的操作是（ A ）。

A. p->next=p->next->next; delete p; B. q=p->next; p->next=q->next;

delet p->next;

C. p->next=p-next->next; delet p->next; D. q=p->next; p->next=q->next;

delete q;

5. 链表不具备的特点是 __A__ 。

A 可随机访问任何一个元素 B 插入、删除操作不需要移动元素

C 无需事先估计存储空间大小 D 所需存储空间与线性表长度成正比

6. 在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是 C 。

A R=F->next; B R=R->next; C F=F->next; D F=R->next;

7. 数据三种最主要的逻辑结构是线性结构和（ B ）。

【数据结构】线性表最基本的定义操作

/*主函数执行操作*/

//------------------------------第一部分-------------------

/*线性表最基本的定义操作*/

#include

//线性表存储空间的初始化分配量

#define List_init_size 10

//初始化增量

#define Listincrement 1

#define OK 1

#define ERROR 0

#define OVERFLOW -2

//自定义int类型的ElemType元素

typedef int ElemType;

//自定义int类型的Status返回状态

typedef int Status;

typedef struct SqList{

ElemType *elem; //指向线性表的第一个节点

int length; //线性表的实际长度

int listsize; //线性表的最大长度

};

//-----------------结束-------------------

//-----------------第二部分----------------

//初始化操作

Status InitList_Sq(struct SqList *L)

{

L->elem = (ElemType *)malloc(List_init_size*sizeof(ElemType));

if(!L->elem)

{

printf("存储空间分配失败！"); exit(1);

}

L->length = 0;

L->listsize = List_init_size;

return OK;

}

// 插入操作

Status ListInsert_Sq(struct SqList *L,int i,ElemType e)