线性表Linear List

引子：多项式表示
线性表定义

引子：多项式表示

一元多项式及其运算： $f (x) = a_{0} + a_{1} x + ... + a_{n} x^{n}$

主要运算：多项式相加、相减、相乘等

分析：如何表示多项式？

（1）顺序存储结构直接表示

数组各分量对应多项式各项，a[i]：项 $x_{i}$ 的系数 $a_{i}$

两个多项式相加：两个数组对应分量相加

问题：如何表示多项式 $f (x) = x + 3 x^{2000}$ ？

空间利用率较低

（2）顺序存储结构表示非零项

每个非零项 $a_{i} x^{i}$ 涉及两个信息：系数 $a_{i}$ 和指数i

可以将一个多项式看成是一个 $(a_{i}, i)$ 二元组的集合。

用结构数组表示：数组分量是由系数 $a_{i}$ 、指数i组成的结构，对应一个非零项

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

为了方便相加可以按指数大小存储！

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

（3）链表结构存储非零项

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

coef	expon	link

typedef struct PolyNode *Polynomial;

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

线性表定义

多项式表示问题的启示：

1.同一个问题可以有不同的表示（存储）方法

2.有一类共性问题：有序线性序列的组织和管理

线性表：0个或多个同类型数据元素的有限序列。

班级同学的花名册是线性表，因为这是有限序列。在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

线性表的抽象数据类型定义

线性表的抽象数据类型定义如下：

ADT 线性表(List)
Data
	线性表的数据对象集合为{a1,a2,...,an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
	InitList(*L):初始化操作，建立一个空的线性表L。
	ListEmpty(L):若线性表为空，返回true，否则返回false。
	ClearList(*L)：将线性表清空。
	GetElem(L,i,*e)：将线性表L中的第i个未知元素值返回给e。
	LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
	ListInsert(*L,i,e)：在线性表L中的第i个位置插入新元素e。
	ListDelete(*L,i,*e)：删除线性表L中第i个位置元素，并用e返回其值。
	ListLength(L)：返回线性表L的元素个数。
endADT

线性表的顺序存储实现

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

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

陈越姥姥《数据结构》课程实现版本：

#define MAXSIZE 20 /*存储空间初始分配量*/

typedef struct LNode* List;

struct LNode
{
    ElementType Data[MAXSIZE];
    int Last;//记录最后一位有效位
};
struct LNode L;
List PtrL;

List MakeEmpty()
{
    List PtrL;
    PtrL=(List)malloc(sizeof(struct LNode));
    PtrL->Last=-1;
    return PtrL;
}
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;//找到后返回的是存储位置（下标）
}

/*插入（第i（1<=i<=n+1）个位置上插入一个值为X的新元素*/

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

/*删除：删除表的第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];     /*将a(i+1)~an顺序向前移动*/
    PtrL->Last--;         /*Last仍指向最后一个元素*/
    return;
}

《大话数据结构》给出的顺序存储的链表实例：

#include <bits/stdc++.h>
using namespace std;

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2             //这样就为 `OVERFLOW` 定义了一个值为 `-2` 的常量。

typedef int ElemType;
typedef int Status;

typedef struct
{
    ElemType *elem;
    int length;
}SqList;

//线性表的初始化
Status InitList(SqList &L)
{
    L.elem=new ElemType[MAXSIZE];
    if(!L.elem)
        exit(OVERFLOW);
    L.length=0;
    return OK;
}
//线性表的取值
Status GetElem(SqList L,int i,ElemType &e)
{
    if(i<1||i>L.length)
        return ERROR;
    e=L.elem[i-1];
    return OK;
}
//查找元素
int LocateElem(SqList L,ElemType e)
{
    for(int i=0;i<L.length;i++)
    {
        if(L.elem[i]==e)
            return i+1;
    }
    return 0;
}
//线性表插入元素
Status ListInsert(SqList &L,int i,ElemType e)
{
    if(i<1||i>L.length+1)
        return ERROR;
    if(L.length==MAXSIZE)
        return ERROR;
    for(int j=L.length-1;j>=i-1;j--)
    {
        L.elem[j+1]=L.elem[j];
    }
    L.elem[i-1]=e;
    L.length++;
    return OK;
}
//线性表删除元素
Status ListDelete(SqList &L,int i)
{
    if(i<1||i>L.length)
        return ERROR;
    for(int j=i;j<=L.length-1;j++)
        L.elem[j-1]=L.elem[j];
    L.length--;
    return OK;
}
//打印线性表
Status Display(SqList &L)
{
    for(int i=0;i<L.length;i++)
        printf("%d ",L.elem[i]);
    printf("\n");
    return 0;
}

int main()
{
    SqList L;
    int v,k,opt;
    InitList(L);
    printf("1：在线性表中存入5个值\n");
    printf("2：查找线性表中的元素\n");
    printf("3：向线性表中插入一个元素\n");
    printf("4：从线性表中删除一个元素\n");
    printf("5：退出\n");
    while(1)
    {
        printf("输入你的选择：");
        cin>>opt;
        if(opt==1)
        {
            printf("请输入要插入的5个值：");
            for(int i=1;i<=5;i++)
            {
                cin>>v;
                ListInsert(L,i,v);
            }
            printf("当前线性表为：");
            Display(L);
        }
        else if(opt==2)
        {
            printf("请输入要查找的元素：");
            cin>>v;
            k=LocateElem(L,v);
            printf("要查找的元素的所在的位置为：%d\n",k);
        }
        else if(opt==3)
        {
            printf("请输入要插入的元素及插入的位置：");
            cin>>v>>k;
            ListInsert(L,k,v);
            printf("插入元素后的线性表为：");
            Display(L);
        }
        else if(opt==4)
        {
            printf("输入要删除的元素的序数：");
            cin>>v;
            ListDelete(L,v);
            printf("删除后的线性表为：");
            Display(L);
        }
        else if(opt==5)
        {
            printf("退出成功！");
            break;
        }
    }
    return 0;

}

1：在线性表中存入5个值
2：查找线性表中的元素
3：向线性表中插入一个元素
4：从线性表中删除一个元素
5：退出
输入你的选择：1
请输入要插入的5个值：9 4 2 1 0
当前线性表为：9 4 2 1 0
输入你的选择：2
请输入要查找的元素：4
要查找的元素的所在的位置为：2
输入你的选择：3
请输入要插入的元素及插入的位置：5 3
插入元素后的线性表为：9 4 5 2 1 0
输入你的选择：4
输入要删除的元素的序数：6
删除后的线性表为：9 4 5 2 1
输入你的选择：5
退出成功！

线性表的链式存储实现

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

插入、删除元素不需要移动数据元素，只需要修改”链“。

如果只知道链表头，该怎么访问序号为i的元素？以及怎么求线性表的长度？

建立结构体和结构体指针：

typedef struct LNode *List;

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

展示链表结构：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct  list_node
{
	int data ;
	struct list_node *next ;
};

typedef struct list_node list_single ;
list_single *create_list_node(int data)
{
	list_single *node = NULL ;
	node = (list_single *)malloc(sizeof(list_single));
	if(node == NULL){
		printf("malloc fair!\n");
	}
	memset(node,0,sizeof(list_single));
	node->data = data;
	node->next = NULL ;
	return node ;
}
int main(void)
{
	int data = 100 ;
	list_single *node_ptr = create_list_node(data); //创建一个节点
	printf("node_ptr->data=%d\n",node_ptr->data);   //打印节点里的数据
	printf("node_ptr->next=%d\n",node_ptr->next);
	free(node_ptr);
	return 0 ;
}

node_ptr->data=100
node_ptr->next=0

1.求链表的长度

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

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）按值查找

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

3.插入（在 $i - 1 （ 1 \leq i \leq n + 1 ）$ 个结点后插入一个值为X的新结点

这个结点是第i个结点。

步骤（1）先构造一个新结点，用s指向；（2）再找到链表的第i-1个结点，用p指向；（3）然后修改指针，插入结点（p之后插入的新结点是s）。

链表要先断再接，顺序不能更改！！

List 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;
    }
}

4.删除（删除链表的 $第 i 个（ 1 \leq i \leq n ）$ 个位置上的的结点

步骤：（1）先找到链表的第i-1个结点，用p指向；（2）再用指针s指向要被删除的结点（p的下一个结点）；（3）然后修改指针，删除s所指结点；（4）最后释放s所指结点的空间。

步骤不能更改！！！

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;
    }
}

陈越姥姥《数据结构》课程给出的完整代码如下：

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指向的是第j个结点
    }
    return j;
}

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;  //否则返回空
}

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

List 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;
    }
}

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;
    }
}

《大话数据结构》中链式存储的链表实例：

#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1
typedef int Status;
typedef int ElementType;

typedef struct LNode *List;

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

//表的创建（头插法）

void CreateListHead(List *L,int m[],int n)
{
    List p;
    int i;
    *L=(List)malloc(sizeof(struct LNode));
    (*L)->Next=NULL;
    for(i=0;i<n;i++)
    {
        p=(List)malloc(sizeof(struct LNode));
        p->Data=m[i];
        p->Next=(*L)->Next;
        (*L)->Next=p;
    }
}

//表的创建（尾插法）
void CreateListTail(List *L,int m[],int n)
{
    List p,r;
    int i;
    *L=(List)malloc(sizeof(struct LNode));
    r=*L;
    for(i=0;i<n;i++)
    {
        p=(List)malloc(sizeof(struct LNode));
        p->Data=m[i];
        r->Next=p;
        r=p;
    }
    r->Next=NULL;
}

Status GetElem(List L,int i,ElementType *e)
{
    int j;
    List p;
    p=L->Next;
    j=1;
    while(p&&j<i)
    {
        p=p->Next;
        j++;
    }
    if(!p||j>i)
        return ERROR;
    *e=p->Data;
    return OK;
}
Status ListInsert(List *L,int i,ElementType e)
{
    int j;
    List p,s;
    p=*L;
    j=1;
    while(p&&j<i)
    {
        p=p->Next;
        j++;
    }
    if(!p||j>i)
        return ERROR;
    s=(List)malloc(sizeof(struct LNode));
    s->Data=e;
    s->Next=p->Next;
    p->Next=s;
    return OK;
}

Status ListDelete(List *L,int i)
{
    int j;
    List p,q;
    p=*L;
    j=1;
    while(p->Next&&j<i)
    {
        p=p->Next;
        j++;
    }
    if(!(p->Next)||j>i)
        return ERROR;

    q=p->Next;
    p->Next=q->Next;
    free(q);
    return OK;
}
Status Output(List L)
{
    List p;
    p=L->Next;
    while(p)
    {
        printf("%d",p->Data);
        p=p->Next;
    }
    printf("\n");
}

int main()
{
    List L;
    int i,j,k,n,e,m[100];
    printf("请输入要存储元素的总个数：");
    scanf("%d",&n);
    printf("请输入各个元素的值：");
    for(i=0;i<n;i++)
        scanf("%d",&m[i]);

    CreateListHead(&L,m,n);
    printf("此时链表的元素如下所示：\n");
    Output(L);
    printf("请输入要获取的第j个元素并返回到e值中（输入j的值）：");
    scanf("%d",&j);
    GetElem(L,j,&e);
    printf("此时e的值为第j个元素值：%d\n",e);
    printf("请输入在第k个元素前插入一个元素e1：");
    int e1;
    scanf("%d%d",&k,&e1);
    ListInsert(&L,k,e1);
    printf("此时链表的个元素如下：\n");
    Output(L);
    printf("请输入要删除元素的序号：");
    int l;
    scanf("%d",&l);
    ListDelete(&L,l);
    printf("此时链表的各元素如下：\n");
    Output(L);
    return 0;

}

请输入要存储元素的总个数：5
请输入各个元素的值：1 2 3 4 5
此时链表的元素如下所示：
54321
请输入要获取的第j个元素并返回到e值中（输入j的值）：2
此时e的值为第j个元素值：4
请输入在第k个元素前插入一个元素e1：1 2
此时链表的个元素如下：
254321
请输入要删除元素的序号：2
此时链表的各元素如下：
24321

广义表和多重链表

我们知道了一元多项式的表示，那么二元多项式又该如何表示呢？比如给定二元多项式： $P (x, y) = 9 x^{12} y^{2} + 4 x^{12} + 15 x^{8} y^{3} - x^{8} y + 3 x^{2}$

广义表（Generalized List）

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

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

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

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

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

资料结构与演算法