首页 > 代码库 > 线性结构

线性结构

线性表及其实现

[引例]:多项式的表示

一元多项式:f(x)=a0+a1X+...+an-1Xn-1+anXn

主要运算:多项式的相加、相减、相乘等。

[分析]如何表示多项式?

多项式的关键数据:

  • 多项式的项数n
  • 各项系数ai及指数i

方法1:顺序存储结构直接表示

数组各分量对应多项式的各项:

a[i]:项Xi的系数ai,i是对应的指数

例如:f(x)=4x5-3x2+1,表示成:

 0  1   2   3  4  5    ......    下标i

1 0 -3 0 0 4 ......

 a[i]

 1     -3x2      4x5  

以这样的形式表示后,两个多项式进行相加时,直接用两个数组对应分量相加即可。

用这个方法有一个问题,比如,如何表示多项式x+3x2000?

  显然,至少要用2001个长度的数组,但其本身只有两项在起作用,不仅造成的空间极大浪费,而且运算过程中要进行循环,含有很多0项,比较繁琐。

 

方法2:顺序存储结构表示非零项

每个非零项aixi涉及两个信息:系数ai和指数i

可以将一个多项式看成是一个系数和指数(ai,i)的二元组的集合

结构数组表示:数组分量是由系数ai、指数i组成的结构,对应一个非零项

例如:P1(x)=9x12+15x8+3x2和P2(x)=26x19-4x8-13x6+82

技术分享

用这种方式来表示,只需要表示非零项即可。为了计算方便,需要按指数大小有序存储

相加过程:从头开始比较两个多项式当前对应项的指数

P1:(9,12),(15,8),(3,2)

P2:(26,19),(-4,8),(-13,6),(82,0)

先看两个多项式的第一项(9,12)和(26,19),由于指数19比12大,那么就将(26,19)输出,

然后将(9,12)与P2的第二项(-4,8)进行比较,由于12比8大,所以将(9,12)输出,

然后将(-4,8)与P1的第二项(15,8)进行比较,此时两者指数相同,则将系数相加得到(11,8)输出,

以此类推,当其中一个多项式结束之后,另一个多项式未完成的项直接输出即可。

===>P3:(26,19),(9,12),(11,8),(-13,6),(3,2),(82,0)

即P3(x)=26x19+9x12+11x8-13x6+3x2+82

 

方法3:链表结构存储非零项

链表中每个结点存储多项式中的一个非零项,包括系数和指数两个数据域以及一个指针域

coef expon link

 

typedef struct PolyNode *Polynomial;
struct PolyNode{
     int coef;//系数
     int expon;//指数
     Polynomial link;//指针域  
}
//定义一个结构体

上述的例子中,两个多项式的链表存储形式可以表示为:

技术分享

它的加法运算过程和方法2的过程是一样的

 


 什么是线性表?

由前面关于多项式的引例可以得到如下启示:

  • 同一个问题可以有不同的表示(存储)方法
  • 有一类共性问题:有序线性序列的组织和管理

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

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

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

  • 类型名称:线性表(List)
  • 数据对象集:线性表是n(≥0)个元素构成的有序序列(a1,a2,...,an)
  • 操作集:线性表L€List,整数i表示位置,元素X€ElementType

线性表基本操作主要有:

  1. List MakeEmpty():初始化一个空线性表L;
  2. ElementType FindKth(int K,List L):根据位序K,返回相应元素;
  3. int Find(ElementType X,List L):在线性表L中查找X的第一次出现的位置
  4. void Insert(ElementType X,int i,List L):在位序前插入一个新元素X;
  5. void Delete(int i,List L):删除指定位序i的元素;
  6. int Length(List L):返回线性表L的长度n。

线性表的顺序存储实现:利用数组连续存储空间顺序存放线性表的各元素

技术分享

typedef struct LNode *List;
struct LNode{
    ElementType Data[MAXSIZE];
    int Last;//代表线性表的最后一个元素
};
struct LNode L;
List PtrL;//PtrL为线性表结构的指针

访问下标为i的元素:L.Data[i]或Ptrl->Data[i]

线性表的长度:L.Last+1或Ptrl->Last+1

主要操作的实现:

1.初始化(建立空的顺序表)

List MakeEmpty(){
    List PtrL;
    PtrL = (List)malloc(sizeof(struct LNode));//申请一个结构
    PtrL->Last=-1;//Last表示链表的最后一个元素,当last为0时,表示含有一个元素,没有元素就赋值为-1
    return PtrL;  //返回结构的指针
}

 2.查找

int  Find(ElementType X,List PtrL){
    int i=0;
    while(i<=PtrL->Last && PtrL->Data[i]!=X){
          i++;
    }
     if(i>PtrL->Last)   
          return -1;//如果没有找到,返回-1
     else 
          return i;//找到后返回的是存储位置
}

查找成功的平均次数是(n+1)/2,平均时间性能为O(n)。

3.插入(第i(1≤i≤n+1)个位置上插入一个值为X的新元素)

技术分享

只能先移动最后一个元素

void Insert(ElementTyepe X,int i,List PtrL){
    int j;
    if(PtrL->Last == MAXSIZE-1){
         printf("表空间已满,不能插入");
         return;
    }
    if(i<1 || i>PtrL->Last+2){
         printf("位置不合法");
    }
    for(j=PtrL->Last;j>=i-1;j--)
         PtrL->Data[j+1] = Ptrl->Data[j];//将ai~an倒序向后移动
    PtrL->Data[i-1]=X;//新元素插入
    PtrL->Last++;//Last仍指向最后元素
    return;
}

平均移动次数为n/2,平均时间性能为O(n)

4.删除(删除表的第i(1<= i<= n)个位置上的元素)

技术分享

void Delete(int i,List PtrL){
     int j;
     if(i<1 || i>PtrL->Last+1){//检查空表及删除位置的合法性
          printf("不存在第%d个元素",i);
          return;
     };
     for(j=i;j<=PtrL->Last;j++)
          PtrL->Data[j-1]=PtrL->Data[j];//将ai+1~an顺序向前移动
     PtrL->Last--;//Last仍指向最后元素
     return;
}

平均移动次数是(n-1)/2,平均时间性能为O(n)

 


 线性表的链式存储实现

  • 不要求逻辑上相邻的两个元素物理上也相邻,通过“链”建立起元素之间的逻辑关系。
  • 插入、删除不需要移动数据元素,只需修改“链”

技术分享

typedef struct LNode *List;
//每个结点都是一个结构
struct LNode{ ElementType Data;//结点的数据 List Next;//下一个结点的位置 }; struct LNode L; List PtrL;

主要操作实现:

1.求表长

int Length(List PtrL){
    List p=PtrL;//p指向表的第一个结点
    int j=0;
    while(p){
         p=p->Next;
         j++;//当前p指向的是第j个结点
    }  
    return j;
}

平均时间性能:O(n)

2.查找

(1)按序号查找:FindKth;

List FindKth(int K,List PtrL){
     List p=PtrL;
     int i=1;
     while(p!=NULL && i<K){
          p=p->Next;
          i++;  
    }
     if(i==K)  
          return p;//找到第K个,返回指针
     else 
          return NULL;//否则返回空
}

(2)按值查找:Find

List Find(ElementType X,List PtrL){
     List p=PtrL;
     while(p!=NULL && p->Data!=X){
           p=p->Next;
     }
     return p;
}

平均时间性能:O(n)

3.插入(在第i-1(1≤i≤n+1)个结点后插入一个值为X的新结点)

(1)先构造一个新结点,用s指向;

(2)再找到链表的第i-1个结点,用p指向

(3)然后修改指针,插入节点(p之后插入新结点是s)

技术分享

 技术分享

执行顺序:(1)s->Next=p->Next;(2)p->Next=s;

思考:修改指针的两个步骤如果交换一下,将会发生什么?

如果语句执行顺序为:(1)p->Next=s;(2)s->Next=p->Next,则

技术分享

将会导致s->Next指向其本身。

List Insert(ElementType X,int i,List PtrL){
     List p,s;
     if(i==1){//新结点插入在表头
          s=(List)malloc(sizeof(struct LNode))//申请、填装结点
          s->Data=http://www.mamicode.com/X;
          s->Next=PtrL;
          return s;//返回新表头指针
     }  
     p=FindKth(i-1,PtrL);//查找第i-1个结点
     if(p==NULL){//第i-1个不存在,不能插入
          printf("参数i错误");
          return NULL;
     }else{
          s=(List)malloc(sizeof(struct LNode));//申请、填装结点
          s->Data=http://www.mamicode.com/X;
          s->Next=p->Next;//新结点插入在第i-1个结点的后面
          p->Next=s;
          return PtrL;
     }
}

平均时间性能是:O(n/2)

4.删除(删除链表的第i(1≤i≤n)个位置上的结点)

(1)先找到链表的第i-1个结点,用p指向;

(2)再用指针s指向要被删除的结点(p的下一个结点);s=p->Next;

(3)然后修改指针,删除s所指结点;p->Next=s->Next;

技术分享

 (4)最后释放s所指结点的空间;free(s),这样内存空间才不会泄露。

技术分享

思考:操作指针的几个步骤如果随意改变,将会发生什么?

s->Next将会指向其本身。

List Delete(int i,List PtrL){
    List p,s;
    if(i==1){//若要删除的是第一个结点
        s=PtrL;//s指向第一个结点
        if(PtrL!=NULL)
            PtrL=PtrL-Next;//从链表中删除
        else 
            return NULL;
        free(s);//释放被删除结点
        return PtrL;
   }
    p=FindKth(i-1,PtrL);//查找第i-1个结点
    if(p==NULL){
        printf("第%d个结点不存在",i-1);
        return NULL;
    }else if(p->Next==NULL){
        printf("第%d个结点不存在",i);
        return NULL;
    }else{
        s=p->Next;//s指向第i个结点
        p->Next=s->Next;//从链表中删除
        free(s);//释放被删除结点
        return PtrL;
    }
}

平均时间复杂性:O(n/2)

 


 广义表

[例]我们知道了一元多项式的表示,那么二元多项式又该如何表示?

比如,给定二元多项式:P(x,y)=9x12y2+4x12+15x8y3-x8y+3x2

[分析]可以将上述二元多项式看成关于x的一元多项式:P(x,y)=(9y2+4)x12+(15y3-y)x8+3x2它的系数不再是常量,而是一个关于y的多项式。

所以,上述二元多项式可以用“复杂”链表表示为:

技术分享

广义表(Generalized List)定义:

  • 广义表是线性表的推广
  • 对于线性表而言,n个元素都是基本的单元素
  • 广义表中,这些元素不仅可以是单元素也可以是另一个广义表

在广义表构造时,我们会遇到这样一个问题:一个域有可能是一个不能分解的单元素,有可能是一个指针,为了解决这个问题,C语言提供了Union

typedef struct GNode *GList;
struct GNode{
     int tag;//标识域:0表示结点是单元素,1表示结点是广义表
     union{//子表指针域Sublist与单元素数据域Data复用,即共用存储空间
          ElementType Data;
          GList Sublist;
     }URegion;
     GList Next;//指向后继结点  
}

技术分享

通过Tag来区分到底是Data还是SubList

 


 

多重链表

多重链表:链表中的节点可能同时隶属于多个链

  • 多重链表中结点的指针域会有多个,如前面例子中包含了Next和SubList两个指针域;
  • 但包含两个指针域的链表并不一定是多重链表,比如双向链表不是多重链表

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

【例】矩阵可以用二维数组表示,但二维数组表示有两个缺陷

  • 一是数组的大小需要事先确定
  • 对于“稀疏矩阵”,将造成大量的存储空间浪费

技术分享

【分析】采用一种典型的多重链表——十字链表来存储稀疏矩阵

  • 只存储矩阵非0元素项
    • 结点的数据域:行坐标Row、列坐标Col、数值Value
  • 每个结点通过两个指针域,把同行、同列串起来
    • 行指针(或称为向右指针)Right
    • 列指针(或称为向下指针)Down

矩阵A的多重链表图:存在两种结构类型

第一种:Term类型:它包含两个指针,一个指向同一行,一个指向同一列。同一行和同一列都设计成一个循环链表。

技术分享

第二种:Head类型:作为行(列)链表的头结点

技术分享

左上角的Term作为整个稀疏矩阵的入口,

  • 4——表示稀疏矩阵的行数
  • 5——表示稀疏矩阵的列数
  • 7——表示稀疏矩阵含有的非零项数

用一个标志域Tag来区分头结点和非0元素结点:

头结点的标识值为“Head”,矩阵非0元素结点的标识值为“Term”。

技术分享      技术分享     技术分享

 

线性结构