数据结构（C++版）王红梅_数据结构c++版

第一章 绪论

一、数据结构

1、数据的逻辑结构可以分为

（1）线性结构     一对一

有且只有一个开始和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继

例如：线性表、栈、队列、串（字符串 数组 广义表）。

（2）非线性结构  一对多

一个结点可能也有多个直接前驱和直接后继

例如：树形结构、图形结构。

数据结构从逻辑上分为四类：

（1）集合：数据元素之间就是“属于同一个集合”

（2）线性结构：数据元素之间存在着一对一的线性关系

（3）树结构：数据元素之间存在着一对多的层次关系

（4）图结构：数据元素之间存在着多对多的任意关系。

 2、数据的存储结构

（1）顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。

（2）链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示 。

3、数据的运算：检索、排序、插入、删除、修改等

二、算法

1、算法的特性：输入、输出、有穷性、确定性、可行性。

2、算法的描述方法：自然语言、流程图、程序代码、伪代码（类语言）。

3、算法设计的要求：正确性、可读性、健壮性（鲁棒性）、抽象分级、高效性。

4、算法分析：

（1）算法所耗费的时间

算法运行时间 = ∑ 每条语句的执行次数（每条语句频度） × 该语句执行一次所需的时间

时间复杂度：算法所需时间的度量

（2）算法执行过程中所耗费的存储空间

空间复杂度：算法所需存储空间的度量 S（n） = O（f（n））

第二章 线性表

2.1 线性表的逻辑结构

1、线性表简称表，是n（n>=0）个具有相同类型的数据元素的有序列表，线性表中数据元素的个数称为线性表的长度。长度等于零时称为空表，一个非空表通常记为：

L = （a1，a2，a3，...，an）

其中，ai 称为数据元素，下脚标i表示该元素在线性表中的位置或序号，称元素 ai 位于表的第i个位置，或称 ai 是表中的第 i 个元素。a1 称为第一个元素，an 称为最后一个元素，任意一对相邻的元素 ai-1 和 ai 之间存在序偶关系 ai-1,ai>，且 ai-1 称为 ai 的前驱，ai 称为 ai-1 的后继。a1 无前驱，an 无后继，其他每一个元素有且仅有一个前驱和一个后继。

 2、线性表的特性：有限性、相同性、顺序性

2.2 线性表的顺序存储结构及实现

1、线性表的顺序存储结构称为顺序表

2、顺序表的实现

（1）构造函数

①无参构造函数  将顺序表长度length初始化为0

SeqList<DataType>::SeqList()
{  
    length = 0; 
}

 ②有参构造函数

template <class DataType>
SeqList<DataType>::SeqList(DataType a[] , int n)
{
    if (n > MaxSize) 
    {
        throw"参数非法";
    }
    for (i = 0 ; i < n ; i++ )
    {
        data[i] = a[i] ;
    }
    length = 0 ;
}

（2）求线性表的长度

返回成员变量length的值

（3）查找操作

①按位查找 时间复杂度为O（1）

template <class DataType>
DataType SeqList<DataType>::Get(int i)
{
    if ( i < 1 && i > length )
    {
        throw"查找位置非法";
    }
    else
    {
        return data[i-1];    
    }
}

②按值查找 平均时间性能O（n）

template <class DataType>
int SeqList<DataType>::Locate(DataType x)
{
    for ( i = 0 ; i < length ; i++ )
    {
        if (data[i] == x )
        {    
            return i+1;
        }
    }
    return 0;
}

（4）插入操作 平均时间复杂度为O（n）

伪代码

1. 如果表满了，则抛出上溢异常;

2. 如果元素的插入位置不合理，则抛出位置异常;

3. 将最后一个元素至第i个元素分别向后移动一个位置；

4. 将元素x填入位置i处；

5. 表长加1；

template <class DataType>  
void SeqList<DataType>::Insert(int i, DataType x)
{
    if (length >= MaxSize) 
    {
        throw "上溢";
    }
    if (i < 1 || i > length + 1) 
    {
        throw "位置";
    }
    for (j = length ; j >= i ; j--)
    {
        data[j] = data[j-1]; //注意第j个元素存在于数组下标为j-1处
        data[i-1] = x;
        length++;
    }
}

（5）删除操作 平均数间复杂度为O（n）

伪代码

1. 如果表空了，则抛出下溢异常;

2. 如果元素的删除位置不合理，则抛出位置异常;

3. 取出被删除元素；

4. 将下标为i,i+1,…,n-1处的元素分别移到下标为i-1, i,…,n-2处；

5. 表长减1，返回被删元素值；

template <class DataType> 
DataType SeqList<DataType>::Delete (int i)
{     
    if ( length ==0 ) 
    {
        throw “下溢";
    }
    if (i < 1 || i > length ) 
    {
        throw "位置";
    }
    x=data[i-1];     //取出位置i的元素
    for (j=i ; j < length ; j++)
    {
        data[j-1] = data[j]; //注意此处j已经是元素所在的数组下标
    }
    length--;
    return x;
}

（6）遍历操作 

按下标依次输出各元素

template <class DataType>  
void SeqList<DataType> ::PrintList()
{
    for (i = 0; i < length; i++)     
    {
        cout<<data[i];
    }    
}

顺序表的优点

⑴ 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；

⑵ 随机存取：可以快速地存取表中任一位置的元素

顺序表的缺点

⑴ 插入和删除操作需要移动大量元素；

⑵ 表的容量难以确定，表的容量难以扩充；

⑶ 造成存储空间的碎片。

2.3 线性表的链式存储结构及实现

顺序表  → 静态存储分配 → 事先确定容量

链表     → 动态存储分配 → 运行时分配空间

一、单链表

1、单链表：线性表的链式存储结构。

单链表是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续、不连续、零散分布。

单链表是由若干结点构成的； 单链表的结点只有一个指针域。

单链表的结点结构：

 data（数据域）：存储数据元素    next（指针域、链域）：存储该结点的后继结点的地址

存储特点：

①逻辑次序和物理次序不一定相同。

②元素之间的逻辑关系用指针表示。

头指针：指向第一个结点（开始结点）的地址。

尾标志：终端结点的指针域为空，即NULL。

空表：first == NULL

非空表：

2、单链表的实现

template <class DataType>
class LinkList
{   
public:
     LinkList( )；                   //无参构造函数，建立只有头结点的空链表
     LinkList(DataType a[ ], int n); //有参构造函数，建立有 n 个元素的单链表
     ~LinkList( );                   //析构函数
     int Length( );                  //求单链表的长度
     DataType Get(int i);            //按位查找。在单链表中查找第 i 个结点的元素值
     int Locate(DataType x);         //按值查找。在单链表中查找值为 x 的元素符号
     void Insert(int i, DataType x); //插入操作，在 i 个位置插入元素值为 x 的结点
     DataType Delete(int i);         //删除操作，在单链表中删除第 i 个结点
     void PrintList( );              //遍历操作，按序号依次输出各元素
private:
     Node<DataType> *first;          //单链表的头指针
};

 （1）遍历操作

template <class DataType>
void LinkList<DataType> :: PrintList( )
{
     p = first->next;     //工作指针 p 初始化
     while (p != NULL)
     {
         cout << p->data;
         p = p->next;     //工作指针 p 后裔，注意不能写成 p++ 
     }
}

（2）求线性表的长度

伪代码：

1. 工作指针p初始化; 累加器count初始化;

2. 重复执行下述操作，直到p为空：

        2.1 工作指针p后移;    

        2.2 count++;

3. 返回累加器count的值；

template <class DataType>
int LinkList<DataType> :: Length( )
{
    p = first->next;    //工作指针 p 初始化; 
    count = 0;          //累加器 count 初始化;
    while (p != NULL)
    {
        p = p->next;
        count++;
    }
    return count;       //注意 count 的初始化和返回值之间的关系
}

（3）查找操作

①按位查找  平均时间性能为O（n）   单链表是顺序存取结构。

template <class DataType>
int LinkList<DataType> :: Get( int i)
{
     p = first->next;        //初始化
     count = 1;              //初始化    
     while (p != NULL && count < i)
     {
         p = p->next;        //工作指针后移
         count++;
     }
     if (p == NULL) 
     { 
         throw “位置”;
     }
     else 
     {
        return p-> data;
     }
}

②按值查找    平均时间性能为O（n）

template <class DataType>  
int LinkList<DataType> :: Locate(DataType x) 
{
    p = first->next;        //初始化
    count = 1;              //初始化
    while (p != NULL)    
    {
        if (p->data == x)
        {
            return count;    //查找成功，返回序号
        }  
        p = p->next;                   
        count++;
    }
    return 0;                //退出循环表明查找失败
}

（4）插入操作  时间复杂度O（n）

                      表头插入                     表中插入                                表尾插入

伪代码：

 1. 工作指针 p 初始化；            

 2. 查找第 i-1 个结点并使工作指针 p 指向该结点；  

3. 若查找不成功，则插入位置不合理，抛出插入位置异常；否则，      

        3.1 生成一个元素值为 x 的新结点 s ；      

        3.2 将新结点 s 插入到结点 p 之后；

 template <class DataType>  
 void LinkList<DataType> :: Insert(int i, DataType x)
 {
     p = first ;
     count = 0;                             //工作指针 p 应指向头结点
     while (p != NULL && count < i - 1)     //查找第 i – 1 个结点
     {
          p = p->next;                       //工作指针 p 后移
          count++;
     }
     if (p == NULL) 
     {     
          throw "位置";                       //没有找到第 i – 1 个结点
     }
     else 
     { 
          s = new Node;  
          s->data = x;                        //申请一个结点 s ，其数据域为 x
          s->next = p->next;               
          p->next = s;                        //结点 s 插入结点 p 之后
     }
 }

 （5）构造函数 

无参构造函数

template <class DataType>  
LinkList<DataType> :: LinkList()
{
    first = new Node;        //生成头结点
    first -> next = NULL;    //头结点的指针域置空
}

有参构造函数（头插法和尾插法）

①头插法   每次将新申请的结点插在头结点的后面。

template <class DataType>  
LinkList<DataType> :: LinkList(DataType a[ ], int n)
{
    first = new Node;
    first->next = NULL;             //初始化一个空链表
    for (i = 0; i < n; i++)
    { 
         s = new Node;
         s->data = a[i];           //为每个数组元素建立一个新结点    
         s->next = first->next; 
         first->next = s;          //将结点 s 插入到头结点之后
    }
}

 ②尾插法   每次将新申请的结点插入在终端结点的后面

 

 

template <class DataType>  
LinkList<DataType> :: LinkList(DataType a[ ], int n)
{
    first = new Node<DataType>;  //生成头结点
    r = first;                   //尾指针初始化
    for (i = 0; i < n; i++)
    { 
        s = new Node<DataType>;
        s->data = a[i];          //为每一个数组元素建立一个结点
        r->next = s; 
        r = s;                   //将结点 s 插入到终端结点之后
    }
    r->next = NULL;              //单链表建立完毕，将终端结点的指针域置空
}

 （6）删除操作

 

   在表头删除                                    在表中删除                        被删结点不存在但其前驱结点存在  

 伪代码：

 1.工作指针 p 初始化；  

2. 查找第 i-1 个结点并使工作指针 p 指向该结点；  

3. 若 p 不存在或 p 不存在后继结点，则抛出位置异常；否则，          

        3.1 暂存被删结点和被删元素值；          

        3.2 摘链，将结点 p 的后继结点从链表上摘下；          

        3.3 释放被删结点；          

        3.4 返回被删元素值；

template <class DataType>  
DataType LinkList<DataType> :: Delete(int i)
{
     p = first ; 
     count = 0;                          //注意工作指针 p 要指向头结点
     while (p != NULL && count < i - 1)  //查找第 i-1 个结点
     {
         p = p->next;
         count++;
     }
     if (p == NULL || p->next == NULL)   //结点 p 不存在或 p 的后继结点不存在
     {
         throw "位置"; 
     }
     else
     {
         q = p->next; 
         x = q->data;                    //暂存被删结点
         p->next = q->next;              //摘链
         delete q; 
         return x;
     }
}

 （7）析构函数    将单链表中的结点（包括头结点）的存储空间释放

template <class DataType>
LinkList<DataType> :: ~LinkList( )
{
     while (first != NULL)     //释放单链表的每一个结点的存储空间
     {
         q = first;            //暂存被释放结点    
         first = first->next;  // first 指向被释放结点的下一个结点       
         delete q;    
     }
}

二、循环链表

1、循环链表：将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成单循环链表，简称循环链表。

空循环链表

非空循环链表