陈越《数据结构》第二章线性结构

2019-11-08 原文

2.1 线性表

2.1.1 基本知识

例1：一元多项式及其运算
f(x)=a0+a1x....+an−1xn−1+anxn
表示方法：
1. 顺序存储结构直接表示；
2. 顺序存储结构；
（用结构数组表示：数组分量是由系数 ai 、指数 i 组成的结构，对应一个非零项）
3. 链表结构存储非零项。
（链表中每个结点存储多项式中的一个非零项，包括：系数和指数两个数据域以及一个。）

启示：

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

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

。

线性表（定义时：1.数据对象集和操作集）
定义：由同类型数据元素构成的有序序列的线性结构。

表中元素个数称为线性表的长度；

线性表没有元素时，称为空表；

表起始位置称表头，表结束位置称表尾。

解析：

指针函数的运用
看看上面三个表达式分别是什么意思？

A) char *(*fun1)(char *p1,char *p2);
B) char **fun2(char *p1,char *p2);
C) char *fun3(char *p1,char *p2);

答：
C）这很容易，fun3是函数名，p1，p2是参数，其类型为char 型，函数的返回值为char 类型。

B) 也很简单，与C）表达式相比，唯一不同的就是函数的返回值类型为char**，是个二级指针。

A) fun1是函数名吗？回忆一下前面讲解数组指针时的情形。我们说数组指针这么定义或许更清晰：
int(∗)[10]p;
再看看A）表达式与这里何其相似！明白了吧。这里fun1不是什么函数名，而是一个指针变量，它指向一个函数。这个函数有两个指针类型的参数，函数的返回值也是一个指针。同样，我们把这个表达式改写一下：
char∗(∗)(char∗p1,char∗p2)fun1;
这样子是不是好看一些呢？只可惜编译器不这么想。
来源于.

struct和typedefstruct
1 首先：//注意在C和C++里不同
　　　　在C中定义一个结构体类型要用typedef:
　　　　typedef struct Student{
　　　　int a;
　　　　}Stu;
　于是在声明变量的时候就可：Stu stu1;(如果没有typedef就必须用struct Student stu1;来声明)
　　这里的Stu实际上就是struct Student的别名。Stu==struct Student
　　另外这里也可以不写Student（于是也不能struct Student stu1;了，必须是Stu stu1;）
　　　　typedef struct{
　　　　int a;
　　　　}Stu;
　　　　但在c++里很简单，直接
　　　　struct Student{
　　　　int a;
　　　　};　　　　
　于是就定义了结构体类型Student，声明变量时直接Student stu2；
　
2.其次：在c++中如果用typedef的话，又会造成区别：
　　　　struct Student {
　　　　int a;
　　　　}stu1;//stu1是一个变量
　　　　typedef struct Student2 {
　　　　int a;
　　　　}stu2;//stu2是一个结构体类型=struct Student
　　使用时可以直接访问stu1.a
　　但是stu2则必须先 stu2 s2;
　　然后 s2.a=10;

3. 给出一个实例
typedef struct tagMyStruct{
　　　　　int iNum;
　　　　　long lLength;
　　　　} MyStruct;
　在C中，这个申明后申请结构变量的方法有两种：
　　　　（1） struct tagMyStruct 变量名；
　　　　(tagMyStruct称为”tag”,即”标签”,实际上是一个临时名字，不论是否有typedefstruct 关键字和tagMyStruct一起，构成了这个结构类型，这个结构都存在。)
　　　　（2） MyStruct 变量名
　　　　在c++中可以有
　　　　（1） struct tagMyStruct 变量名
　　　　（2） MyStruct 变量名
　　　　（3） tagMyStruct 变量名
来源于。

用数组建立空链表的程序分析
Qus:
typedef struct{ ElementType Data[MAXSIZE]; int Last; } List; List L,*PtrL; 然后是初始化的 1. 初始化（建立空的顺序表） List *MakeEmpty( ) { List *PtrL; PtrL = (List *)malloc( sizeof(List) ); PtrL->Last = -1; returnPtrL; }
初始化空的列表直接给他List L,*PtrL;把指针赋过去不就好了吗，为什么还要搞出MakeEmpty( )啊?

Ans:
MakeEmpty( )完成的工作：
1、动态申请了顺序表的空间；
2、设置表指针为-1；
3、返回了表的指针；
你的操作 List L,*PtrL;
PtrL = &L;
L.Last = -1;
来源于。

2.1.2 顺序存储

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

各种操作的时间性能:
1. 查找 O(k) ;
2. 插入 O(n) ;

3. 删除 O(n) ;

2.1.3 链式存储

定义：

结构的定义：

。

基本操作：
1. 求表长，时间性能为 O(n)。
2. 查找，按序号查找: FindKth 和按值查找: Find，时间性能为 O(n)。
3. 插入，时间性能为 O(n)。

4. 删除，时间性能为 O(n)。

2.1.4 广义表和多重链表

2.1.4.1 广义表

2.1.4.2 多重链表

例子：表示稀疏矩阵

2.2 堆栈

2.2.1堆栈定义和堆栈的抽象数据类型

例1：中缀表达式 a+b∗c−d/e ,请问前缀表达式和后缀表达式是什么？

前缀表达式： −+a∗bc−d/e ;
后缀表达式： abc∗+de/− .
如果用后缀表达式来进行计算，实质就是堆栈的应用！

堆栈定义：
具有一定操作约束的线性表只在一端（栈顶，Top ）做插入、删除。

例2：如果三个字符按 ABC 顺序压入堆栈:
• ABC 的所有排列都可能是出栈的序列吗？
• 可以产生 CAB 这样的序列吗？

2.2.2 顺序存储

例3：请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。

解析：
一种比较聪明的方法是使这两个栈分别从数组的 两头开始向中间生长；当两个栈的 栈顶指针相遇 时，表示两个栈都满了。

2.2.3 堆栈的链式存储及应用

链式存储定义：
栈的链式存储结构实际上就是一个 单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行。栈顶指针Top应该在链表的哪一头？

答：栈顶放在链表的表头，放在尾部不行！

应用： 表达式求值：中缀表达式求值。
基本策略：将中缀表达式转换为后缀表达式，然后求值，如何将中缀表达式转换为后缀？

步骤：

堆栈的其他应用：
1. 函数调用及递归实现
2. 深度优先搜索
3. 回溯算法
….

2.3 队列

2.3.1 定义及顺序存储

1.定义： 先进先出FIFO

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

为了抑制假溢出现象，我们用循环队列进行模拟，但是会出现“空”和“满”无法判断的情况，我们运用：
1. 另设变量；Size（计算队列内元素个数）和tag（标记队列中是否有元素）；
2. 少用一个空间元素。
注 :通常用求余方法进行求解（%）。

2.3.2队列的链式存储

定义：
队列的链式存储结构也可以用一个 单链表 实现。插入和删除操作分别在链表的两头进行；队列指针 front 和 rear 应该分别指向链表的哪一头？

答：
front 在单链表表头， rear 在单链表表尾。

例1：如何用两个栈模拟实现一个队列? 如果这两个堆栈的容量分别是m和n（m>n)，你的方法能保证队列的最大容量是多少？（这里讨论的是顺序栈，如果是链式栈的话完全没有必要考虑空间）
答：
方法：用一个栈作为存储空间，另一个栈作为输出缓冲区，入队时把元素按顺序压入两栈模拟的队列，出队时按入队的顺序出栈即可。
结果：两个栈所模拟的队列的最大容量为2n+1。

2.4 应用实例及小白专场

多项式的加法和乘法：

//author: Paul_Huang
//Data: 15/6/2017

//#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1
#include<stdio.h>
#include<stdlib.h>
#include<process.h>//引入头文件
#include<string.h>


typedef struct Node{
    int coeff;
    int expo;
    struct Node *next;
}polyNode,*polynomial;

polynomial Readpoly();
polynomial Addpoly(polynomial P1,polynomial P2);
polynomial Multpoly(polynomial P1,polynomial P2);
void Printpoly(polynomial P);
void Attach(int coeff,int expo,polynomial *PtrRear);
int compare(int e1,int e2);

int main()
{
    polynomial P1,P2,polyAdd,polyMult;
    P1 = Readpoly();
    P2 = Readpoly();
    polyAdd = Addpoly(P1,P2);
    polyMult = Multpoly(P1,P2);
    Printpoly(polyMult);
    Printpoly(polyAdd);
    system("pause");//暂停往下执行 按下任意键继续
    return 1;
}

polynomial Readpoly()
{
    polynomial P,temp,rear;
    int N,coeff,expo;
    /*输入要的项数*/
    scanf("%d",&N);
    P = (polynomial)malloc(sizeof(polyNode));/*链表头空节点*/
    P->next = NULL;
    rear = P;
    while (N--){
        scanf("%d %d",&coeff,&expo);
        Attach(coeff,expo,&rear);/*将当前项插入多项式尾端*/
    }
    /*删除临时节点*/
    temp = P;
    P = P->next;
    free(temp);
    return P;
}

polynomial Addpoly(polynomial P1,polynomial P2)
{
    polynomial P,Rear,temp;
    int sum;
    P = (polynomial)malloc(sizeof(polyNode));/*链表头空节点*/
    P->next = NULL;
    Rear = P;
    while (P1&&P2){
        switch (compare(P1->expo,P2->expo)){
            case 1: /*P1的系数更大*/
                Attach(P1->coeff,P1->expo,&Rear);
                P1 = P1->next;
                break;
            case -1:/*P2的系数更大*/ 
                Attach(P2->coeff,P2->expo,&Rear);
                P2 = P2->next;
                break;
            case 0:/*P1和P2的系数一样大*/ 
                sum = P1->coeff + P2->coeff;
                Attach(sum,&Rear);
                P1 = P1->next;
                P2 = P2->next;
        }
        /*将未完成的多项式补在后面*/
        for (; P1; P1 = P1->next)Attach(P1->coeff,&Rear);
        for (; P2; P2 = P2->next)Attach(P2->coeff,&Rear);
        /*删除临时节点*/
        Rear->next = NULL;
        temp = P;
        P = P->next;
        free(temp);

        return P;
    }
}

polynomial Multpoly(polynomial P1,t1,t2,Temp;
    int coeff,expo;
    /*判断是否为空*/
    if (!P1 || !P2)
        return NULL;

    t1 = P1; t2 = P2;
    P = (polynomial)malloc(sizeof(polyNode));/*链表头空节点*/
    P->next = NULL;
    Rear = P;
    while (t2){

            Attach(t1->coeff*t2->coeff,t1->expo + t2->expo,&Rear);
            t2 = t2->next;

    }
    t1 = t1->next;
    while (t1){
        t2 = P2; Rear = P;/*重置t2与Rear*/
        while (t2){
            coeff = t1->coeff*t2->coeff;
            expo = (t1->expo + t2->expo);
            while (Rear->next && Rear->next->expo > expo)
                Rear = Rear->next; /*循环找到对应的节点*/
            if (Rear->next && Rear->next->expo==expo){
                if (Rear->next->expo + expo)
                    Rear->next->expo += expo;
                else{
                    Temp = Rear->next;
                    Rear->next = Rear->next->next;
                    free(Temp);
                }
            }
            else{
                Temp = (polynomial)malloc(sizeof(polyNode));
                Temp->coeff = coeff;
                Temp->expo = expo;
                Temp->next = Rear->next;
                Rear->next = Temp;/*在Rear后面加上TemP*/
                Rear = Temp;
            }
            t2 = t2->next;
        }
        t1 = t1->next;
    }
    Temp = P;
    P = P->next;
    free(Temp);

    return P;

}

void Printpoly(polynomial P)
{
    int flag = 0; /* 辅助调整输出格式用 */
    if (!P){
        printf("0 0\n");
        return;
    }
    while (P){
        if (!flag)
            flag = 1;
        else
            printf(" ");
        printf("%d %d",P->coeff,P->expo);
        P = P->next;
    }
    printf("\n");
}

void Attach(int coeff,polynomial *PtrRear)
{   /*函数传递进来的是节点指针的地址，*PtrRear*/
    polynomial P;

    P = (polyNode*)malloc(sizeof(polyNode));//申请新节点的两种表示方法
    P->coeff = coeff;
    P->expo = expo;
    /*将P指向的新节点插入到当前结果表达式尾项的后面*/
    (*PtrRear)->next = P;
    *PtrRear = P;
    P->next = NULL;
}

int compare(int e1,int e2)
{
    /*比较两个多项式中的指数项e1和e2,返回1、0、-1*/
    if (e1 > e2) return 1;/*e1大，返回1*/
    else if (e1 < e2) return -1;/*e2大，返回-1*/
    else return 0;/*两者相等*/
}