浙大《数据结构》第二章：线性结构

注：本文使用的网课资源为中国大学MOOC

https://www.icourse163.org/course/ZJU-93001

目录



线性表及其实现

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


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

类型名称：线性表(List)

数据对象集：线性表是n(>=0)个元素构成的有序序列((a_1,a_2,...,a_n))

操作集：线性表(L in List)，整数i表示位置，元素(X in ElementType)，基本操作有：

#define MaxSize 100 // 链表元素的最大个数
typedef int ElementType; // ElementType 暂时定义为 int 类型

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前插入一个新的元素
void delete(int i, List L); //删除指定位序i的元素
int Length(List L); //返回线性表L的长度n

线性表的顺序存储实现

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

#define MaxSize 100 // 链表元素的最大个数
typedef int ElementType; // ElementType 暂时定义为 int 类型

typedef struct
{
    ElementType Data[MAXSIZE];
    int Last;
}List;
List L, *PtrL;

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

线性表的长度：L.Last+1或PtrL->Last+1

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

List *MakeEmpty()
{
    List *PtrL;
    PtrL = (List *)malloc(sizeof(List));
    PtrL->Last = -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; //找到后返回的是存储位置
}

3、插入

在第i个位置中插入一个值为X的新元素

思路：先将数组中i+1后的数据移动，再插入新数据

void Insert(ElementType X, int i, List *PtrL)
{
    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;
}

4、删除

删除表中的第i个位置上的元素

思路：i后面的元素依次前移即可

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

线性表的链式存储实现

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

typedef struct
{
    ElementType Data;
    struct Node *Next;
}List;
List L, *PtrL;

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) //找到第K个，返回指针
        return p;
    else //否则返回空
        return NULL;
}

（2）按值查找：Find

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

3、插入

(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(List));
        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(List));  //申请、填装结点
        s->Data = X;
        s-Next = p->Next; //新结点插入在第i-1个结点后面
        p->Next = s;
        return PtrL;
    }
}

4、插入

(1) 先找到链表上的第i个结点，用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 GNode
{
    int Tag;  //标志域：0表示结点是单元素，1表示结点是广义表
    union
    {
        ElementType Data;
        struct GNode *SubList;
    }URegion; //子表指针域SubList与单元素数据域Data复用，即共用存储空间
    struct GNode *Next; //指向后继结点
}GList;

举例1：二元多项式的表示：

[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 ]

所以，上述二元多项式可以用复杂链表表示：

举例二、十字链表存储稀疏矩阵

[ ] 只存储矩阵非0元素项

结点的数据域：行坐标Row、列坐标Col、数值Value
[ ] 每个结点通过两个指针域，把同行、同列串起来

  • 行指针(或称为向右指针)Right
  • 列指针(或称为向下指针)Down

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


堆栈

堆栈：具有一定操作约束的线性表，只在一端(栈顶，top)做插入、删除

堆栈的抽象数据类型描述

类型名称：堆栈(Stack)

数据对象集：一个有0个或多个元素的有穷线性表

操作集：长度为MaxSize的堆栈(S in Stack)，堆栈元素(item in ElementType),基本操作有：

Stack CreateStack( int MaxSize ); //生成空堆栈，其最大长度为MaxSize
int IsFull( Stack S, int MaxSize ); //判断堆栈S是否已满
void Push( Stack S, ElementType item ); //将元素item压入堆栈
int IsEmpty( Stack S ); //判断堆栈s是否为空
ElementType Pop( Stack S ); //删除并返回栈顶元素

栈的顺序存储实现

通常由一个一位数组和一个记录栈顶元素位置的变量

#define MaxSize 100 // 堆栈元素的最大个数
typedef int ElementType; // ElementType 暂时定义为 int 类型

typedef struct
{
    ElementType Data[MAXSIZE];
    int Top;
}Stack;

1、入栈

void Push( Stack *PtrS, ElementType item )
{
    if ( PtrS->Top == MaxSize-1)
    {
        printf("堆栈满");
        return;
    }
    else
    {
        PtrS->Data[++(PtrS->Top)] = item;
    }
    return;
}

2、出栈

ElementType Pop( Stack *PtrS )
{
    if ( PtrS->Top == -1)
    {
        printf("堆栈空");
        return ERROR; //ERROR是ElementType的特殊值，标志错误
    }
    else
        return ( PtrS->Data[(PtrS->Top)--] );
        
}

3、举例：用一个数组实现两个堆栈，要求最大地利用数组空间

分析：使得这两个栈分别从数组的两头开始从中间生长，当两个栈的栈顶指针相遇时，表示两个栈都满了。

#define MaxSize 100 // 堆栈元素的最大个数
typedef int ElementType; // ElementType 暂时定义为 int 类型

struct DStack
{
    ElementType Data[MAXSIZE];
    int Top1; //堆栈1的栈顶指针
    int Top2; //堆栈2的栈顶指针
}S; //注意此时S只是一个变量

S.top1 = -1;
S.top2 = MaxSize;

// 入栈操作，设置Tag作为区分两个堆栈的标志，取值1和2
void Push( struct DStack *PtrS, ElementType item, int tag )
{
    if ( PtrS->Top2 - PtrS->Top1 == 1)
    {
        printf("堆栈满");
        return;
    }
    if ( Tag == 1) //对第一个堆栈操作
        PtrS->Data[++(PtrS->Top1)] = item;
    else //对第二个堆栈操作
    {
        PtrS->Data[--(PtrS->Top2)] = item;
    }
}


// 出栈，设置Tag作为区分两个堆栈的标志，取值1和2
ElementType Pop( struct DStack *PtrS, int Tag )
{
    if ( Tag == 1) //对第一个堆栈操作
        if ( PtrS->Top1 == -1) //堆栈1空
        {
            printf("堆栈1空");
            return NULL; 
        }
        else
            return ( PtrS->Data[(PtrS->Top1)--] );
    else
    {
        if ( PtrS->Top2 == MaxSize ) //堆栈2空
        {
            printf("堆栈2空");
            return NULL; 
        }
        else
            return ( PtrS->Data[(PtrS->Top2)++] );
    }
}

栈的链式存储实现

实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。

#define MaxSize 100 // 堆栈元素的最大个数
typedef int ElementType; // ElementType 暂时定义为 int 类型

typedef struct Node *LinkStack;
struct Node
{
    ElementType Data;
    LinkStack Next;
}

/*堆栈初始化*/
LinkStack *CreateStack()
{
    //构建一个堆栈的头结点
    LinkStack *S;
    S = ( LinkStack )malloc( sizeof(struct Node) );
    S->Next = NULL;
    return S;
}
/* 判断堆栈s是否为空 */
int IsEmpty( LinkStack *S )
{
    //判断堆栈是否为空，若为空函数返回整数1，否则返回0
    return ( S->Next == NULL);
}

/* 入栈 */
void Push( ElementType item, LinkStack *S )
{
    //将元素item压入堆栈
    struct Node *TmpCell;
    TmpCell = ( LinkStack )malloc( sizeof(struct Node)); 
    TmpCell->Element = item;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
}

/* 出栈 */
ElementType Pop( LinkStack *S )
{
    // 删除并返回栈顶元素
    struct Node *FirstCell; // 新建一个结点，暂存栈顶结点
    ElementType TopElem;
    if ( IsEmpty (S) )
    {
        printf("堆栈空");
        return NULL;
    }
    else
    {
        FirstCell = S-Next;
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Element;
        free(FirstCell);
        return TopElem;
    }
}

应用：后缀表达式求值

从左到右读入后缀表达式的各项。

  • 运算数：入栈；
  • 运算符：从堆栈中弹出适量数量的运算数，计算并将结果入栈；
  • 最后栈顶上的元素就是表达式的结果值。

扩展：中缀表达式转化为后缀表达式

举例：(a*(b+c)/d o abc+*d/)

思路：从头到尾读取中缀表达式的每一个对象，对不同的对象按不同的情况处理；

  1. 运算数：直接输出
  2. 左括号：压入堆栈
  3. 右括号：将栈顶的运算符弹出并输出，直到遇到左括号(出栈，不输出)；
  4. 运算符：
    • 若优先级大于栈顶运算符，则把它压栈；
    • 若优先级小于等于栈顶运算符，则将栈顶运算符弹出并输出，再比较新的栈顶运算符，知道该运算法大于等于栈顶运算符优先级为止，然后将该运算符压栈；
  5. 若各对象处理完毕，则把堆栈中存留的运算符一并输出。


## 队列

队列(Queue):具有一定操作约束的线性表，只能在一端插入，而在另一端删除。

队列的抽象数据类型描述

类型名称：队列(Queue)

数据对象集：一个有0个或多个元素的有穷线性表

操作集：长度为MaxSize的队列(Q in Queue)，队列元素(item in ElementType),基本操作有：

Queue CreateQueue( int MaxSize); //生成长度为MaxSize的空队列
int IsFullQ( Queue Q, int MaxSize); //判断队列Q是否已满
void AddQ( Queue Q, ElementType item); //将元素item插入队列Q中
int IsEmptyQ( Queue Q ); //判断队列Q是否为空
ElementType Delete( Queue Q ); //将队头元素从队列中删除并返回

队列的顺序存储实现

队列的顺序存储结构通常由一个一维数组和一个记录队列猎头元素的变量front以及一个记录队列对位元素位置的变量rear组成。

#define MaxSize <储存数据元素的最大个数>

typedef struct
{
    ElementType Data[MaxSize];
    int rear
    int front;
}Queue;

/* 入队列 */
void AddQ( Queue *PtrQ, ElementType item )
{
    //使用加一取余法体现队列顺序存储的循环使用。
    if ( (PtrQ->rear+1) % MaxSize == PtrQ->front )
    {
        printf("队列满");
        return;
    }
    PtrQ->rear = (PtrQ->rear+1) % MaxSize;
    PtrQ->Data[PtrQ->rear] = item;
}

/* 删除队列元素 */
ElementType Delete( Queue *PtrQ )
{
    if ( PtrQ->rear == PtrQ->front )
    {
        printf("队列空");
        return ERROR;
    }
    else
    {
        PtrQ->front == (PtrQ->front+1) % MaxSize;
        return PtrQ->Data[PtrQ->front];
    }
}

队列的链式存储实现

队列的链式存储结构可以由单链表实现，插入和删除操作分别在链表两头进行。

//单链表定义
typedef struct Node
{
    ElementType Data;
    struct Node *Next;
}QNode;

//链队列结构
typedef struct
{
    QNode *rear; //指向队尾结点
    QNode *front; //指向队头结点
}LinkQueue
LinkQueue *PtrQ;

/* 删除队列元素 */
ElementType Delete( Queue *PtrQ )
{
    QNode *FrontCell;
    ElementType FrontElem;
    
    if ( PtrQ->front == NULL )
    {
        printf("队列空");
        return ERROR;
    }
    FrontCell = PtrQ->front;
    if (PtrQ->front == PtrQ->rear) //如果队列只有一个元素
        PtrQ->front = PtrQ->rear = NULL; //删除队列后置为空
    else
        PtrQ->front = PtrQ->front->Next;
    
    FrontElem = FrontCell->Data;
    free(FrontCell); //释放被删除结点空间
    return FrontCell;
}


应用实例：一元多项式的加法和乘法运算

设计函数分别求两个一元多项式的乘积与和


题意理解

已知两个多项式分别为：

[egin{aligned} &3x ^4-5x^2+6x-2\ &5x^{20}-7x^4+3x end{aligned} ]

对应的程序输入为：

  • 4 3 4 -5 2 6 1 -2 0
  • 3 5 20 -7 4 3 1

加法输出为：

  • 5 20 -4 4 -5 2 9 1 -2 0

代表：

[5x^{20}-4x^4-5x^2+9x-2 ]

乘法输出为：

  • 15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1

代表：

[15x^{24}-25x^{22}+30x^{21}-10x^{20}-21x^8+35x^6-33x^5+14x^4-15x^3+18x^2-6x ]


搭建程序框架

int main()
{
    //1、构造多项式的链式表达
    Polynomial P1,P2,PP,PS;
    //2、读入多项式1
    P1 = ReadPoly();
    //3、读入多项式2
    P2 = ReadPoly();
    //4、乘法运算并输出
    PP = Mult( P1,P2 );
    //5、加法运算并输出
    PS = Add( P1,P2 );
    //6、打印结果
    PrintPoly( PP );
    PrintPoly( PS );
}

函数实现

#include <stdio.h>
#include <stdlib.h>  //调用malloc()和free()
#include <malloc.h>  //调用malloc()和free()
#include <windows.h> //windows.h里定义了关于创建窗口，消息循环等函数

typedef struct PolyNode *Polynomial;
struct PolyNode
{
    int coef; //系数
    int expon; //指数
    Polynomial link;
};

/* 比较函数 */
int Compare(int a, int b)
{
    if ( a>b )
        return 1;
    else if ( a<b )
        return -1;
    else
        return 0;   
}

/* 多项式的系数与指数的合并 */
void Attach(int c, int e, Polynomial *pRear)
{
    Polynomial P;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->coef = c; //对新结点赋值
    P->expon = e;
    P->link = NULL;
    (*pRear)->link = P; //注意pRear是指针的指针
    *pRear = P;         //修改pRear的值
}

/* 读入多项式 */
Polynomial ReadPoly()
{
    Polynomial rear, temp, p; //rear代表当前结果表达式尾项指针
    int c, e, N;

    scanf("%d", &N);
    // 一开始构造一个空结点，然后让rear指向这个空结点
    p = (Polynomial)malloc(sizeof(struct PolyNode)); //链表头空结点
    p->link = NULL;
    rear = p;

    while (N--)
    {
        scanf("%d %d", &c, &e);
        Attach(c, e, &rear); //将当前项插入多项式尾部
    }
    temp = p;
    p = p->link; //因为一开始生成的P指向NULL
    free(temp); //所以删除临时生成的头结点
    return p;
}

/* 多项式的加法 */
Polynomial Add(Polynomial P1, Polynomial P2)
{
    Polynomial front, rear, temp;  // front和rear分别指向结果多项式的头和尾
    int sum;
    rear = (Polynomial)malloc(sizeof(struct PolyNode)); 
    rear->link = NULL;
    front = rear;  //由front记录结果多项式的链表头结点
    while (P1 && P2) //当两个多项式都有非零项待处理时
    {
        switch (Compare(P1->expon, P2->expon))
        {
        case 1: // P1中的数据项指数较大
            Attach(P1->coef, P1->expon, &rear);
            P1 = P1->link;
            break;
        case -1: // P2中数据项指数较大
            Attach(P2->coef, P2->expon, &rear);
            P2 = P2->link;
            break;
        case 0:
            sum = P1->coef + P2->coef;
            if (sum)
                Attach(sum, P1->expon, &rear);
            P1 = P1 ->link;
            P2 = P2 ->link;
            break;
        }
    }
    //将未处理完的另一个多项式的所有节点依次复制到结果多项式中去
    for (; P1; P1 = P1->link)
        Attach(P1->coef, P1->expon, &rear);
    for (; P2; P2 = P2->link)
        Attach(P2->coef, P2->expon, &rear);
    rear->link = NULL;
    temp = front;
    front = front->link; //令front指向结果多项式的第一个非零项
    free(temp);          //释放临时空表节点
    return front;
}

/* 多项式的乘法 */
Polynomial Mult(Polynomial P1, Polynomial P2)
{
    Polynomial P, rear, t1, t2, temp;
    int c, e;

    if (!P1 || !P2)
        return NULL;
    t1 = P1;
    t2 = P2;
    //申请一个空结点，让rear指向它
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P ->link = NULL;
    rear = P;
    //1、先用P1的第1项乘以P2，得到初始结果P
    while (t2)
    {
        Attach(t1->coef * t2->coef, t1->expon + t2->expon, &rear);
        t2 = t2->link;
    }
    t1 = t1->link;
    //2、将P1与新生成的P进行比较，按照幂次逐项插入

    while (t1)
    {
        t2 = P2;
        rear = P; //将P的值存放在临时变量rear中
        while (t2)
        {
            e = t1->expon + t2->expon;
            c = t1->coef * t2->coef;
            while(rear->link && rear->link->expon > e)
                //rear的下一项的指数如果比带插入的单项式指数大
                //则rear一直往后指
                rear = rear->link;           
            if (rear->link && rear->link->expon == e) //系数相等则合并
            {
                // 系数相加不为0
                if (rear->link->coef + c)
                    rear->link->coef += c;
                else // 如果系数相加为0则需要删除该节点
                {
                    temp = rear->link;
                    rear->link = temp->link;
                    free(temp);
                }
            }
            else //系数不等，代表插入项的系数较小
            {            
                //此时需要申请一个新的结点，并赋值
                temp = (Polynomial)malloc(sizeof(struct PolyNode));
                temp->coef = c;
                temp->expon = e;
                //然后将新结点插入rear中
                temp->link = rear->link;
                rear->link = temp;
                rear = rear->link;
            }
            t2 = t2->link;
        }
        t1 = t1->link;
    }
    t2 = P;
    P = P->link;
    free(t2);
    return P;
}

/* 打印多项式 */
void PrintPoly(Polynomial P)
{
    // 输出多项式
    int flag = 0; //辅助调整输出格式
    if (!P)
    {
        printf("0 0
");
        return;
    }
    while (P)
    {
        if (!flag)
            flag = 1;
        else
            printf(" ");
        printf("%d %d", P->coef, P->expon);
        P = P->link;
    }
    printf("
");
}


//主函数
int main(void)
{
    //1、构造多项式的链式表达
    Polynomial P1, P2, PP, PS;
    //2、读入多项式1
    P1 = ReadPoly();
    //3、读入多项式2
    P2 = ReadPoly();
    //4、乘法运算并输出
    PP = Mult(P1, P2);
    //5、加法运算并输出
    PS = Add(P1, P2);
    //6、打印结果
    PrintPoly(PP);
    PrintPoly(PS);

    //system("pause"); //程序暂停，显示按下任意键继续
    return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Superorange/p/12448821.html