二 : 线性结构 - (1)线性表

怎么用程序设计语言来表示多项式?

例 : 一元多项式

方法1 : 数组(表示非零项)

数组各分量对应多项式各项 : a[i] 表示项 x的系数 a
比如 : 多项式
表示为 :

两个多项式相加 : 两个数组对应分量相加
缺点 : 如何表示 ? (需要2001个分量 , 但只有两个有数据 , 其他都是无效的0)

方法2 : 数组(不表示非零项)

顺序存储结构表示非零项 (只需要表示非零项)
每个非零项涉及两个信息 : 系数 和指数 , 可以将一个多项式看成是一个 二元组的集合
用结构数组表示 :

每一项按指数大小有序存储
相加时从指数高的开始依次比较多项式当前项的指数

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

包括系数和指数两个数据域和一个指针域

什么是线性表? List

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

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

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

  操作集

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

顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素
需要一个指针存放最后一个元素存放的位置
操作集 :

1. 初始化 : malloc()开辟内存
2. 查找 : while(...)i++ (查找成功的平均比较次数是 , 平均时间性能是**)**
3. 插入 (在第 i 个位置上插入一个值为X的新元素) : 把元素放到 i-1 的位置
   需要先把 i-1 后面的元素依次往后移动一位之后再插入
   从后面开始挪 !!! if()
   倒序向后移动并插入新元素 : for(...) PtrL->Data[j+1] = PtrL->Data[j]; PtrL->Data[i-1]=X;
4. 删除 : 把 i 之后的元素全部往前挪 , 从 i 处开始循环 (平均移动次数是 , 平均时间性能是**)**

   对于数组 , 想找到位置为 i 的元素和数组的长度很容易 , 对于链表却不是这样

链式存储实现

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

1. 求表长 : 把链表遍历一遍
   设临时指针 p , 指向链表的头 -> 设一个计数器 j -> 每遍历一个就+1 (循环条件是链表还没有结束) ->return j
   while(p){p=p->Next;j++}每个p都指向当前的第 j 个节点
2. 查找
   (1)按序号查找 : 循环条件为表不空和 i< K
   (2)按值查找 : 循环条件为表不空和 **i< K
   

**

1. 插入 : 把新元素插在第 i-1 个结点的后面
   (1) 先构造一个新结点 malloc(), 用s指向;
   (2) 再找到链表的第 i-1 个节点 , 用p指向;
   (3) 然后修改指针 , 插入结点 (p之后插入新结点是s)
   
   这两个语句顺序不能对调 , 对调之后会 : s->Next指向 s
   
2. 删除 : 第 i 个位置上的结点
   (1) 先找到链表的第i-1个结点 , 用p指向
   (2) 再用指针s指向要被删除的结点 (p的下一个结点)
   (3) 然后修改指针 , 删除s所指结点
   (4) 把malloc()函数申请的空间用free()函数释放回去 (放置内存泄漏)
   
   平均时间复杂度为

广义表

一元多项式的表示如上。二元多项式该如何表示 ?
例 :

分析

将上述二元多项式看成关于x的一元多项式 , 用(复杂)链表表示出来

定义

广义表 (Generalized List)

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

  问题

  在构造广义表时遇到的问题 : 域有可能是不能分解的单元素 (比如指针) 怎么处理 ?
  C语言提供了 union{} , 可以把不同类型的数据组合在一起 , 设一个标记
  

多重链表

定义

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

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

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

怎么表示矩阵?(稀疏矩阵)

A矩阵中第一个Term表示 : 这是一个4行5列的矩阵 , 非零项有7项

在矩阵的多重链表表示中 , 第i行的head和第i列的head实际上使用一个结点

• 用一个标识域Tag来区分头结点和非零元素结点 , 头结点标识为Head , 矩阵非零元素结点的标识值为Term
• 用 union{}把两个Tag结合到一起

小测验

2.1 线性表及其实现.pdf

C语言实现 - 顺序表的定义及查找插入删除

typedef int Position;
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 )
{
    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 ) 
{ /* 在L的指定位置P前插入一个新元素X */
    Position i;
    if ( L->Last == MAXSIZE-1) {
        /* 表空间已满，不能插入 */
        printf("表满"); 
        return false; 
    }  
    if ( P<0 || P>L->Last+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 )
{ /* 从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;   
}

C语言实现 - 链式表的定义及查找插入删除

typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

/* 查找 */
#define ERROR NULL

Position Find( List L, ElementType X )
{
    Position p = L; /* p指向L的第1个结点 */

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

    /* 下列语句可以用 return p; 替换 */
    if ( p )
        return p;
    else
        return ERROR;
}

/* 带头结点的插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是链表结点指针，在P之前插入新结点 */
bool Insert( List L, ElementType X, Position P )
{ /* 这里默认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;
    }
}

/* 带头结点的删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是拟删除结点指针 */
bool Delete( List L, Position P )
{ /* 这里默认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;
    }
}