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

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了陈越《数据结构》第二章 线性结构，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

2.1 线性表

2.1.1 基本知识

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

启示：

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

。

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

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

解析：

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

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中，@H_301_728@这个申明后申请结构变量的方法有两种：
　　　　（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. 定义：利用数组的 连续存储空间顺序存放 线性表的各元素。

各种操作的时间性能:
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 广义表和多重链表

@H_301_1274@2.1.4.1 广义表

2.1.4.2 多重链表

例子：表示稀疏矩阵

2.2 堆栈

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

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

  • 前缀表达式： −+a∗bc−d/e ;
  • 后缀表达式： abc∗@H_938_1404@+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)，你的方法能保证队列的最大容量是多少？（这里讨论的是顺序栈，如果是链式栈的话完全没有必要考虑空间）
答：
@H_809_2301@方法 ：用一个栈作为存储空间，另一个栈作为输出缓冲区，入队时把元素按顺序压入两栈模拟的队列，出队时按入队的顺序出栈即可。
结果 ：两个栈所模拟的队列的最大容量为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;/*两者相等*/
}
原文链接：https://www.f2er.com/datastructure/382309.html

猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test