数据结构和算法02-线性结构

1. 线性表及其实现

---

引子：

---

1.1 线性表的概念

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

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

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

类型名称：线性表（List）

数据对象集：线性表是n(≥0)个元素构成的有序序列

操作集：线性表L∈List，整数i表示位置，元素X∈ElementType，线性表基本操作主要有：

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

1.3 线性表的顺序存储实现

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

typedef struct LNode *List;
struct Lnode{
    ElementType Data[MAXSIZE];
    int Last;			//包含一个数组和表示最后一个元素的Last
};
struct LNode L;
List Ptrl;

• 访问下标为i的元素：L.Data[i] 或 Ptrl->Data[i]
• 线性表长度：L.Last+1 或 PtrL->Last+1

接下来是主要操作的实现：

1.3.1 初始化

建立空的顺序表

List MakeEmpty() 
{
    List PtrL;
    PtrL = (List) malloc(sizeof(struct LNode));		//申请结构空间
    PtrL->Last = -1;	//最后一个元素声明为-1，代表没有元素了
    return PtrL;
}

1.3.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;  /* 找到后返回的是存储位置 */
}

1.3.3 插入

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

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--) {  /* 将a_i~a_n倒序向后移动 */
        PtrL->Data[j + 1] = PtrL->Data[j];
    }
    PtrL->Data[i - 1] = X;  /* 新元素插入 */
    PtrL->Last++;  /* Last仍指向最后元素 */
    return;
}

1.3.4 删除

删除表上的第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++) {  /* 将a_i+1 ~ a_n顺序向前移动 */
        PtrL->Data[j - 1] = PtrL->Data[j];
    }
    PtrL->Last--;  /* Last仍指向最后元素 */
    return;
}

​

1.4 线性表的链式存储实现

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

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

typedef struct LNode *List;
struct LNode{		//链表的每一个节点都是结构
    ElementType Data;	//数据域
    List Next;			//指针域
};
struct LNode L;
List PtrL;

​

1.4.2 求表长

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

1.4.3 查找

• 按序号查找

List FindKth( int K, List PtrL){
    List p = PtrL;	//将临时指针p定位到表头
    while( p!=NULL && i<K ){	
        p = p->Next;	//将p位移到下一个结点
        i++;
    }
    if( i==K ) return p;
    else return NULL;	//没找到
}

• 按值查找

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

1.4.4 插入

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){
        printf("参数i错");
        return NULL;
    }
    else{
        s = (List)malloc(sizeof(struct LNode));		//申请，填装结点
        s->Data = X;
        s->Next = p->Next;		//注意这一条和下面那条顺序不能相反
        p->Next = s;
        return PtrL;
    }
}

1.4.5 删除

List Delete(int i, List PtrL) 
{
    List p, s;
    if (i == 1) {  		/* 若要删除的是表的第一个结点 */
        s = PtrL;  		/* s指向第1个结点 */
        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;
    }
}

​

1.5 广义表和多重链表

---

引子：

二元多项式的表示方法可如下，将另外一个元作为主元的系数，在这个节点中的数据域为另一个结点的指针，由此构成复杂链表

---

1.5.1 广义表

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

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

1.5.2 多重链表

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

• 多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域

• 但包含两个指针域的链表不一定是多重链表，比如在双向链表不是多重链表

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

  ​

2.堆栈及其实现

2.1 堆栈的概念

---

后缀表达式：

运算符号位于两个运算数之后，其求值策略是从左向右“扫描”，逐个处理运算数和运算符号

• 遇到运算数：记住
• 遇到运算符号：将最近记住的两个运算符合做相应的运算

启示：需要有种存储方法，能顺序存储运算数，并在需要时倒序输出

---

堆栈（Stack）是一种常见的数据结构，它具有后进先出（Last In, First Out，LIFO）的特性。意思是，最后存入堆栈的数据最先被取出。

• 只在一端（栈顶，Top）做插入、删除
• 插入数据：入栈/压栈（Push）
• 删除数据：出栈/弹栈（Pop）

2.2 堆栈的抽象数据类型描述

类型名称：堆栈（Stack）

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

操作集： 长度为MaxSize的堆栈S ∈ Stack，堆栈元素item ∈ 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 )：删除并返回栈顶元素;

  ​

2.3 栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。

#define MaxSize <储存数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode{
    ElementType Data[MaxSize];
    int Top;
};

2.3.1 入栈

void Push( Stack PtrS, ElementType item ){
    if ( PtrS->Top == MaxSize-1 ){		//检查是否满
        printf("堆栈已满");
    }else{
        PtrS->Data[++(PtrS->Top)] = item; //这句话有两个作用，赋值item，将top上移1
        return;
    }
}

2.3.2 出栈

ElementType Pop( Stack PtrS ){
    if ( PtrS->Top == -1){
        printf("堆栈空");
        return ERROR;
    }else{
        return ( PtrS->Data[(PtrS->Top)--]);
    }
}

---

一个数组实现两个堆栈：

让两个堆栈从数组的两头开始向中间生长，当两个栈的栈顶指针相遇时，表示两个栈都满了，这种方法可以让空间利用最大化

#define MaxSize <存储数据元素的最大个数>
struct DStack{
    ElementType Data{MaxSize};
    int Top1;	//堆栈1的顶指针
    int Top2;	//堆栈2的顶指针
}S;
S.Top1 = -1;
S.Top2 = MaxSize;

//入栈操作
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;
    }
}

//出栈操作
ElementType Pop( struct DStack *PtrS, int Tag )
{
    /* Tag作为区分两个堆栈的标志，取值为1和2 */
    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)++];
    }
}

​

2.4 栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。（Top在链表头）

typedef struct SNode *Stack;
struct SNode{
    ElementType Data;
    struct SNode *Next;
};

2.4.1 堆栈初始化（建立空栈）

Stack CreateStack()
{
    /* 构建一个堆栈的头结点，返回指针 */
    Stack S;
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

//判断是否为空
int IsEmpty(Stack S)
{
    /* 判断堆栈是否为空，若为空函数返回整数1，否则返回0 */
    return (S->Next == NULL);
}

2.4.2 入栈

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

2.4.3 出栈

ElementType Pop(Stack S)
{
    /* 删除并返回堆栈S的栈顶元素 */
    struct SNode *FirstCell;
    ElementType TopElem;
    if (IsEmpty(S)) {
        printf("堆栈空");
        return NULL;
    } else {
        FirstCell = S->Next;
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Element;
        free(FirstCell);
        return TopElem;
    }
}

---

堆栈应用1：表达式求值

–中缀表达式如何转换为后缀表达式：

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

① 运算数：直接输出；

② 左括号：压入堆栈；

③ 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）；

④ 运算符：

• 若优先级大于栈顶运算符时，则把它压栈；
• 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；

⑤ 若各对象处理完毕，则把堆栈中存留的运算符一并输出。

堆栈其他应用：函数调用以及递归实现，深度优先搜索，回溯算法……

---

​

3.队列及其实现

3.1 队列的概念

队列是具有一定操作约束的线性表

• 插入和删除操作：只能在一端插入，而在另一端删除
• 数据插入：入队列 （AddQ）
• 数据删除：出队列（DeleteQ）
• 先来先服务，先进先出（FIFO）

3.2 队列的抽象数据类型描述

类型名称：队列（Queue）

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

操作集：长度为 MaxSize 的队列 Q ∈ Queue，队列元素 item ∈ ElementType。

1. Queue CreatQueue( int MaxSize )：生成长度为 MaxSize 的空队列；
2. int IsFullQ( Queue Q, int MaxSize )：判断队列 Q 是否已满；
3. void AddQ( Queue Q, ElementType item )：将数据元素 item 插入队列 Q 中；
4. int IsEmptyQ( Queue Q )：判断队列 Q 是否为空；
5. ElementType DeleteQ( Queue Q )：将队头数据元素从队列中删除并返回。

3.3 队列的顺序存储实现

队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front（指向头元素的前一个位置）以及一个记录队列尾元素位置的变量rear（指向队列最后一个元素）组成。

删除一个元素front+1，加入一个元素rear+1

#define MaxSize <储存数据元素的最大个数>
struct QNode{
    ElementType Data[ MaxSize ];
    int rear;
    int front;
};
typedef struct QNode *Queue;

通常顺环队列的方法能高效利用空间：

3.3.1 入队列

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

3.3.2 出队列

ElementType DeleteQ( Queue PtrQ ){
    if ( PtrQ->front == PtrQ->rear){
        printf("队列空");
        return ERROR;
    }else{
        PtrQ->front = (PtrQ->front+1)%MaxSize;
        return PtrQ->Data[PtrQ->front];
    }
}

3.4 队列的链式存储实现

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

struct Node{
    ElementType Data;
    struct Node *Next;
};
struct QNode{		//链队列结构
    struct Node *rear;		//指向队尾结点
    struct Node *front;		//指向队头结点
};
typedef struct QNode *Queue;
Queue PtrQ;

……

​

4. 经典练习题

4.1 多项式乘法与加法运算