数据结构

（笔记）数据结构2.1-线性表及其实现

陈越 何钦铭

Posted by 王晗 on November 4, 2017

第二讲 线性结构

2.1 线性表及其实现

【例】一元多项式及其运算 一元多项式：$f(x)=a_0+a_1x+…+a_{n-1}x^{n-1}+a_ns^x$ 主要运算：多项式相加、相减、相乘等

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

数组各分量对应多项式各项： $a[i]:项x^i的系数a_i$

例如：$f(x)=4x^5-3x^2+1$ 表示成： 问题：表示$x+x^{2000}$浪费很多内存

方法2：顺序结构表示非零项

每个非零项$a_ix^i$涉及两个信息：系数$a_i和指数i$，可以将一个多项式看成一个$（a_i,i）$二元组的集合。 用结构数组表示：数组分量是由系数$a^i$、指数$i$组成的结构，对应一个非零项

例如：$P(x)=9x^{12}+15x^8+3x^2$        $P(x)=26x^{19}-4x^8-13x^6+82$

|下标i | 0 | 1 | 2 | …… |    |下标i | 0 | 1 | 2 | 3 | …… | |——–|—|—|—|—| |——–|—|—|—|—| | 系数$a^i$ | 9 | 15 | 3 | —— | | 系数$a^i$ | 26 | -4 | -13 | 82 | —— | | 指数$i$ | 12 | 8 | 2 | —— | | 指数$i$ | 19 | 8 | 6 | 0 | —— | 注意：按指数大小有序存储 相加过程：从头开始，比较两个多项式当前对应项的指数。

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

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

| coef | expon | link | |——–|——–| | | |

typedef struct PolyNode *Polynomial;
struct PolyNode{
		int coef;
        int expon;
        Polynomial link;
}

例如： $P(x)=9x^12+15x^8+3x^2$

$P(x)=26x^19-4x^8-13x^6+82$ 链表存储形式为：

什么是线性表

线性表：由同类型数据元素构成有序序列的线性结构

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

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

类型名称：线性表（List） 数据对象集：线性表是$n(>=0)个元素构成的有序序列(a_1,a_2,…,a_n)$ 操作集：线性表$L\in List,整数i表示位置，元素X\in ElementType$

  • List MakeEmpty():初始化一个空线性表L；

  • ElementType FindKth(int K,List L):根据位序K，返回相应元素；

  • int Find(ElementType X,List 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.

线性表的顺序存储实现

typedef 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或PtrL->Last+1

主要操作的实现
  • 初始化（建立空的顺序表）
List MakeEmpty(){
	List PtrL;
	PtrL=(List)malloc(sizeof(struct LNode));
    PtrL->Last=-1;
    return PtrL;
}

malloc函数（memory allocation 动态内存分配） 原型：extern void *malloc(unsigned int num_bytes); 头文件：#include 或 #include (注意：alloc.h 与 malloc.h 的内容是完全一致的。) 功能：分配长度为num_bytes字节的内存块 说明：如果分配成功则返回指向被分配内存的指针，否则返回空指针NULL。 当内存不再使用时，应使用free()函数将内存块释放。

  • 查找
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)

  • 插入（第$i(1<=i<=n+1)个位置上插入一个值为X的新元素$)

先移动，后插入 

void Insert(ElementType X,int i,List PtrL){
	int j;
    if(PtrL->Last==MAXSIZE-1){     //表空间已满，不能插入
    	print("表满");
        return;
    }
    if(i<1||i>PtrL->Last+2){       //检查插入位置合法性
    	print("位置不合法");
        return;
    }
    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)

  • 删除（删除表的第$i(1<=i<=n)$个位置上的元素）

后面的元素依次前移 

void Delete(int i,,List PtrL){
	int j;
    if(i<1||i>PtrL->Last+1){        //检查空表及删除位置的合法性
    	return;
    }
    for(j=ij>=PtrL->Last;j++)
    	PtrL->Data[j-1]=PtrL->Data[j];
        PtrL->Last--; 
        return;
}

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

线性表的链式存储实现

typedef struct LNode *List;
struct LNode{
		ElementType Data;
        List Next;
};
struct LNode L;
List PtrL;
主要操作的实现
  • 求表长
int Length(List Ptrl){
	List p=Ptrl;   //p指向表的第一个结点
    int j=0;
    while(p){
    	p=p->Next;
        j++;     //当前p指向的是第i个结点
    }
    return j;
}
  • 查找
  • 按序号查找：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;    //否则返回空
}
  • 按值查找：Find 
    List FindKth(ElementType X,,List PtrL){
 List p=Ptrl;
 int i=1;
 while(p!=NULL&&p->Data!=X)
 	P=P->Next;
 return p;
}
  • 插入（在第$i-1(1<=i<=n+1)个结点后插入一个值为X的新元素$)
  • 先构造一个新节点，用s指向；
  • 再找到链表的第i-1个结点，用p指向；
  • 然后修改指针，插入结点（p之后插入新节点是s）

void Insert(ElementType X,int i,List PtrL){
	List p,s;
    if(i==1){                                       //新节点插入在表头
    	s=(List)malloc(sizeof(struct LNode));       //申请、填装节点
        s->Data=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=X;
        s->Next=p->Next;                            //新节点插入在第i-1个结点的后面
        p->Next=s;
        return PtrL;
    }
}

平均时间复杂度：1/2n

  • 删除（删除表的第$i(1<=i<=n)$个位置上的元素）
  • 先找到链表的第i-1个结点，用p指向
  • 再用指针s指向要被删除的结点（p的下一节点）；
  • 然后修改指针，删除s所指结点；
  • 最后释放s所指结点空间。

void Delete(int i,,List PtrL){
	List p,s;
    if(i==1){
    	s=PtrL;
        if(PtrL!=NULL) PtrL=PtrL->Next;
        else return NULL;
        free(s);
        return PtrL;
    }
    p=FindKth(i-1,PtrL);
    if(p==NULL){
    	printf("第%d个结点不存在"，i-1)； return NULL;
        return NULL;
    }else if(p->Next==NULL){
    	printf("第%d个结点不存在"，i)； return NULL;
    }else{
        s=p->Next;
        p->Next=s->Next;
        free(s);
        return PtrL;
    }
}

平均时间复杂度：1/2n

广义表

【例】二元多项式：$P(x，y)=9x^{12}y^2+4x^12+15x^8y^3-x^8y+3x^2$ 【分析】将二院多项式看成关于x的一元多项式 $P(x，y)=(9y^2+4)x^{12}+(15y^3-y)x^8+3x^2$ ####广义表

  • 广义表是线性表的推广
  • 对于线性表而言，n个元素都是基本的单元素
  • 广义表中，这些元素不仅可以是单元素也可以是另一个广义表。
typedef struct GNode GList;
struct GNode{
		int Tag;            //标志域：0表示结点是单元素，1表示结点是广义表
        union{              //子表指针域SubList与单元素数据域data复用，即公用存储空间
        	ElementType Data;
            GList SubList;
        }URegion;
		Glist Next;         //指向后继结点
};

多重链表

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

  • 多重链表中结点的指针域会有多个
  • 但包含两个指针域的链表并不一定是多重链表，比如双向链表

多重链表的用途：基本如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。 【例】矩阵可以用二维数组表示，但有缺陷：

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

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

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

矩阵A的多重链表图

  • 用一个标志域Tag来区分结点和非0元素结点
  • 头结点的标识值为“Head”,矩阵非0元素结点的标识值为“Term”

FEATURED TAGS
数据结构
FRIENDS