一、简要

第二章一共四小节，第四节是应用的一节，重点是第二节和第三节。

1、涵盖内容

1、线性表的定义、基本操作及特点。

2、线性表的实现及应用，包括顺序存储结构、链式存储结构(单链表、循环链表和双向链表)的构造原理，在两种存储结构上对线性表实施的主要的操作(三种链表的建立、插入和删除、检索等)的算法设计与实现。

2、学习要求

1、掌握线性表的相关概念；

2、掌握顺序表的相关理论概念，能用C语言编写顺序表的相关操作。

3、掌握链表的相关理论概念，能用C语言编写链表的相关操作。

4、了解线性表和链表的差别，和其优劣。

3、参考书目

《数据结构（C语言版）》严蔚敏、吴伟民编著清华大学出版社

二、线性结构

1、线性结构特点

在数据元素的非空有限集中

1.存在唯一被称为“第一个”的数据元素；

2.存在唯一被称为“最后一个”的数据元素；

3.除第一个之外，集合中每个数据元素都只有一个直接前驱；

4.除最后一个之外，集合中每个数据元素都只有一个直接后继；

三、线性表

1、定义

线性表是几个具有相同数据类型的n个数据元素的有序序列；其中n为表长；n=0时，线性表是一个空表。若用L命名线性表，则其一般表示如下：

其中：

a1是唯一的“第一个”数据元素，称为表头元素，该元素有且只有一个直接后继，

an是唯一一个“最后一个”元素，称为表尾元素，有且仅有一个直接前驱。

其余所有元素，都有唯一直接前驱和唯一直接后继。

ai是是第i个数据元素，称i为数据元素ai在线性表中的位序。

2、特点

1.表中元素个数有限；

2.表中元素具有逻辑上的顺序性，在序列中各元素排列序列有先后次序。

3.表中元素都是单个元素；

4.表中元素数据类型都相同，占用相同大小的存储空间；

5.表中元素具有抽象性，仅讨论元素间的逻辑关系，不考虑元素究竟表示什么内容。

3、注意点

线性表是一种逻辑结构，表示元素之间的一对一相邻关系，不能决定其存储结构，顺序表和链表是两种常用的线性表存储结构。

4、基本操作

1.抽象数据类型

ADT List  {        //数据对象：D ；        //数据关系：S ；        //基本操作：P ；} ADT List

2.基本操作

//1.构造一个空的线性表Status InitList_sq(SqList &L) //2.销毁线性表LStatus DestroyList(SqList &L) //3.将线性表置空LStatus ClearList(SqList &L) //4.判断线性表L是否为空Status ListEmpty(SqList &L) //5.返回线性表中L的数据元素的个数Status ListLength(SqList &L) //6.用e返回线性表L中第i个元素Status GetElem(SqList L, int i, ElemType &e) //7.返回L中第一个与e满足关系compare()的数据元素的位序，若不存在则返回0Status LocateElem(SqList L, ElemType e, Status(*compare)(ElemType, ElemType)) //8.若L中的cur_e不是L的头结点，用pre_e返回cur_e的前驱。否则失败Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e) //9.若L中的cur_e不是L的尾结点，用next_e返回cur_e的后继。否则失败Status NextElem(SqList L, ElemType cur_e, ElemType &next_e) //10.在L中的第i个位置之前插入新的数据元素e，L的长度+1；Status ListInsert(SqList &L, int i, ElemType e) //11.删除L中的第i个元素，并用e返回它的值，L的长度-1；Status ListDelete(SqList &L, int i, ElemType e) //12.依次对L中的每个数据元素调用函数visit()，一旦visit失败，则操作失败。Status ListTraverse(SqList L, Status visit())

你可能感兴趣的文章