线性表概念和实现

线性表

“线性表(Linear List)”:由同类型数据元素构成有序序列的线性结构

• 表中元素个数称为线性表的长度
• 线性表没有元素时，称为空表
• 表起始位置称表头，表结束位置称表尾

线性表的抽象数据类型描述

类型名称：线性表(List)
数据对象集：线性表是n(>=0)个元素构成的有序序列(a1,a2,…，an)
操作集：线性表L ∈ List，整数i表示位置，元素X ∈ ElementType，线性表基本操作主要有：
List MakeEmpty():初始化一个空线性表L;
ElementType FindKth(int K,List L):根据位序K，返回相应元素;
int Find(ElementType X,List L):在线性表L中查找X的首次出现位置
void Insert(ElementType X,int i,List L):在位序i前插入一个新元素X;
void Delete(int i,List L):删除指定位序i的元素;
int Length(List L):返回线性表L的长度n.

线性表的顺序存储

利用类似于数组的连续存储空间顺序存放线性表的各元素
注意数组存储的数据结构不一定是顺序，也可能是链表式的

下标i	0	1	…	i-1	i	…	n-1	…	MAXSIZE-1
Data	a1	a2	…	ai	ai+1	…	an	…	——

#define MaxSize<储存数据元素的最大个数>
tpedef struct LNode *List;
struct LNode
{
    ElementType Data[MAXSIZE];
    int Last;
};
struct LNode L;
List PtrL;
访问下标为i的元素：L.Data[i]或PtrL—>Data[i];
线性表的长度：L.Last+1或trL—>Last+1

线性表的链式存储实现

不要求逻辑上相邻的两个元素物理上也相邻：通过“链”建立起数据元素之间的逻辑关系

• 插入、删除不需要移动数据元素，只需要修改“链”
• 相应的，链式结构想要获取元素位置和线性表长度比较困难
• 头结点不存储元素，专门用来指向后面的整个链表

tpedef struct LNode *List;
struct LNode
{
    ElementType Data;
    List Next;
};
struct LNode L;
List PtrL;

c/c++提供了指针这一功能，因此可以实现“真正”的链表，但在其他高级语言中同样存在这种数据结构
“抽象的链表”：如java等语言中
一块空间用于存储数据，一块区域用于存储指针(下一个结点的地址)即可

多重链表

多重链表存储结构：链表中结点可能同时隶属于多个链

• 多重链表中结点的指针域会有多个
  • 如前例广义表中存在Next和SubList两个指针域
  • 包含多个指针域的链表并不一定是多重链表
    • 比如双向链表就不是多重链表

多重链表有广泛的用途：
基本上如树、图等相对复杂的数据结构都可以采用多重链表方式实现存储

例：矩阵存储
矩阵可以采用二维数组表示，但二维数组表示有两个缺陷：

• 数组空间要提前分配
• 对于“稀疏矩阵”，将造成大量的存储空间浪费

因此采用一种典型的多重链表——十字链表存储稀疏矩阵

• 只存储矩阵非0元素项
  • 结点的数据域：行坐标Row、列坐标Col、数值Value
• 每个结点通过两个指针域，将同行、同列串联起来(双向、循环链表，头结点指向行/列第一个元素，行/列最后一个元素指回头结点)
  • 行指针(或称为向右指针)Right
  • 列指针(或称为向下指针)Down

• 标识域Tag用来区分头结点和非0元素结点
  • 头结点标识值为"Head"，矩阵非0元素结点标识值为"Term"
  • 头结点没有值，只有一个Next指针；十字链表定义时通过union将两种不同结构联合起来
  • 十字链表首元素记录整个十字链表的行数、列数和非零元素数

线性表顺序存储演示

//以下两部分顺序存储和链式存储代码均来自浙江大学数据结构课程
#include<cstdio>
#include<cstdlib>
#define MAXSIZE 50
typedef int Position;
typedef int ElementType;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last;
};

/* 初始化(建立空的顺序表) */
List MakeEmpty()        
{
    List L;

    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;

    return L;
}

/* 查找 */
#define ERROR -1

Position Find( List L, ElementType X )      //查找成功的平均比较次数为(n+1)/2次，平均时间性能为O(n)
{
    Position i = 0;

    while( i <= L->Last && L->Data[i]!= X )
        i++;
    if ( i > L->Last )  return ERROR; /* 如果没找到，返回错误信息 */
    else  return i;  /* 找到后返回的是存储位置 */
}

/* 插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/
bool Insert( List L, ElementType X, Position P )        //在下标为P-1(第P个)元素插入，0<P<n
{ /* 在L的指定位置P前插入一个新元素X */                      //平均移动次数为n/2，平均时间性能为O(n)
    Position i;

    if ( L->Last == MAXSIZE-1) {
        /* 表空间已满，不能插入 */
        printf("表满"); 
        return false; 
    }  
    if ( P<0 || P>L->Last+1 ) { /* 检查插入位置的合法性 */  //PtrL->Last+1对应第n+1个元素
        printf("位置不合法");
        return false; 
    } 
    for( i=L->Last; i>=P; i-- )
        L->Data[i+1] = L->Data[i]; /* 将位置P及以后的元素顺序向后移动 */
    L->Data[P] = X;  /* 新元素插入 */
    L->Last++;       /* Last仍指向最后元素 */
    return true; 
} 

/* 删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/
bool Delete( List L, Position P )                       //平均移动次数为n/2，平均时间性能为O(n)
{ /* 从L中删除指定位置P的元素 */
    Position i;

    if( P<0 || P>L->Last ) { /* 检查空表及删除位置的合法性 */
        printf("位置%d不存在元素", P ); 
        return false; 
    }
    for( i=P+1; i<=L->Last; i++ )
        L->Data[i-1] = L->Data[i]; /* 将位置P+1及以后的元素顺序向前移动 */
    L->Last--; /* Last仍指向最后元素 */
    return true;   
}

线性表链式存储演示

#include<cstdio>
#include<cstdlib>
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

#define ERROR NULL
/* 求表长 */
    int Length(List PtrL)                                    //平均时间性能：O(n)
    {
        List p=PtrL;
        int j=0;
        while(p)
        {
            p=p->Next;
            j++;
        }
        return j;
    }

/* 查找：按值查找(Find)和按序号查找(FindKth) */
Position Find( List L, ElementType X )                      //平均查找次数为n/2，平均时间性能为O(n)
{
    Position p = L; /* p指向L的第1个结点 */

    while ( p && p->Data!=X )
        p = p->Next;

    /* 下列语句可以用 return p; 替换 */
    if ( p )
        return p;
    else
        return ERROR;
}
ElementType FindKth(int K,List PtrL)                        //平均时间性能：O(n)
{
    List p=PtrL;
    int i=1;
    while(p!=NULL&&i<K)
    {
        p=p->Next;
        i++;
    }
    if(i==K)return p->Data;
    else return -1;
}

/*
    插入(在第i-1(1<i<n+1)个结点后面插入一个值为X的新结点)                 
        *先构造一个新结点，用s指向                                        
        *找到链表的第i-1个结点，用p指向
        *修改p、s的指针，插入结点(s->next=p->next;p->next=s;)
*/
/* 带头结点的插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是链表结点指针，在P之前插入新结点 */
bool Insert( List L, ElementType X, Position P )                //平均移动次数为n/2，平均时间性能为O(n)
{ /* 这里默认L有头结点 */
    Position tmp, pre;

    /* 查找P的前一个结点 */    
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;        
    if ( pre==NULL ) { /* P所指的结点不在L中 */
        printf("插入位置参数错误\n");
        return false;
    }
    else { /* 找到了P的前一个结点pre */
        /* 在P前插入新结点 */
        tmp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */
        tmp->Data = X; 
        tmp->Next = P;
        pre->Next = tmp;
        return true;
    }
}
/*
    删除(删除链表的第i(1<i<n+1)个位置上的结点)
            *先找到链表的第i-1个结点，用p指向
            *用指针s指向要被删除的结点(p的下一个结点)
            *修改指针，删除s所指向的结点
            *释放s所指向的结点的空间
*/
/* 带头结点的删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是拟删除结点指针 */
bool Delete( List L, Position P )                       //平均移动次数为n/2，平均时间性能为O(n)
{ /* 这里默认L有头结点 */
    Position pre;

    /* 查找P的前一个结点 */    
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;        
    if ( pre==NULL || P==NULL) { /* P所指的结点不在L中 */
        printf("删除位置参数错误\n");
        return false;
    }
    else { /* 找到了P的前一个结点pre */
        /* 将P位置的结点删除 */
        pre->Next = P->Next;
        free(P);
        return true;
    }
}