【数据结构基础笔记】第二章线性表之基本概念与类型定义

- 日理万妓 2021-06-11 15:12 335阅读 0赞

**目录**

一、线性结构

1、线性结构特点

二、线性表

1、定义

2、特点

**目录**

一、简要

1、涵盖内容

2、学习要求

3、参考书目

二、线性结构

1、线性结构特点

三、线性表

1、定义

2、特点

3、注意点

4、基本操作

--------------------

# 一、简要 #

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

## 1、涵盖内容 ##

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

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

## 2、学习要求 ##

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

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

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

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

## 3、参考书目 ##

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

# 二、线性结构 #

## 1、线性结构特点 ##

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

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

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

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

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

# 三、线性表 #

## 1、定义 ##

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

![70][]

其中：

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.销毁线性表L
    Status DestroyList(SqList &L) 
    
    //3.将线性表置空L
    Status 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()的数据元素的位序，若不存在则返回0
    Status 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())

[70]: /images/20210516/67318fd08a0544438c95d223821175ee.png