2.1 线性表

2.1.1 基本知识

例1：一元多项式及其运算
$f(x)=a_0 + a_1 x ....+a_{n-1}x^{n-1} + a_nx^n$
表示方法：
1. 顺序存储结构直接表示；
2. 顺序存储 结构；
（用结构数组表示：数组分量是由系数$a_i$ 、指数$i$组成的结构，对应一个非零项）
3. 链表结构存储非零项。
（链表中每个结点存储多项式中的一个 非零项，包括：系数和指数 两个数据域以及一个。）

启示：

1. 同一个问题可以有不同的表示（存储）方法；
2. 有一类共性问题：有序线性序列的组织和管理。

。

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

1. 表中元素个数称为线性表的 长度；
2. 线性表没有元素时，称为 空表；
3. 表起始位置称 表头，表结束位置称 表尾。

解析：

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

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;$
这样子是不是好看一些呢？只可惜编译器不这么想。
来源于.

$color{red}{struct 和 typedef struct}$
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;
　$color{red}{在C中，这个申明后申请结构变量的方法有两种：}$
　　　　（1） struct tagMyStruct 变量名；
　　　　(tagMyStruct称为”tag”,即”标签”,实际上是一个临时名字，不论是否有typedefstruct 关键字和tagMyStruct一起，构成了这个结构类型，这个结构都存在。)
　　　　（2） MyStruct 变量名
　　　　$color{red}{在c++中可以有}$
　　　　（1） struct tagMyStruct 变量名
　　　　（2） MyStruct 变量名
　　　　（3） tagMyStruct 变量名
来源于。

$color{red}{用数组建立空链表的程序分析}$
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. 定义：利用数组的 连续存储空间顺序存放 线性表的各元素。
   

各种操作的时间性能:
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$;
• 后缀表达式：$a b c*+de/-$.
  如果用后缀表达式来进行计算，实质就是堆栈的应用！

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

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

2.2.2 顺序存储

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

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

2.2.3 堆栈的链式存储及应用

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

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

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

步骤：

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

2.3 队列

2.3.1 定义及顺序存储

1.定义：$color{red}{先进先出FIFO}$

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

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

2.3.2队列的链式存储

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

答：
$color{red}{front }$在单链表表头，$color{red}{rear}$在单链表表尾。

例1：如何用两个栈模拟实现一个队列? 如果这两个堆栈的容量分别是m和n（m>n)，你的方法能保证队列的最大容量是多少？（这里讨论的是顺序栈，如果是链式栈的话完全没有必要考虑空间）
答：
$color{red}{方法 }$：用一个栈作为存储空间，另一个栈作为输出缓冲区，入队时把元素按顺序压入两栈模拟的队列，出队时按入队的顺序出栈即可。
$color{red}{结果 }$：两个栈所模拟的队列的最大容量为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 0n");
        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;/*两者相等*/
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!