数据结构学习3

9、栈的链式存储结构及实现

定义 栈的链式存储结构称为链栈,是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此,链栈没有必要像单链表那样附加头结点,栈顶指针top就是链表的头指针。

对于链栈来说： 1.不需要头结点 2.不存在栈满的情况 3.top=NULL，为空栈

示意图：

链栈的结构代码

/* 链栈结构*/
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;
​
typedef struct
{
    LinkStackPtr top;
    int count;
}LinkStack;

进栈（push）操作

/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S,SElemType e)
{
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
    s->data=e;
    s->next=S->top;/*把当前的栈顶元素赋值给新结点的直接后继*/
    S->top=s;/*将新的结点s赋值给栈顶指针*/
    S->count++;
    return OK;
}

出栈（pop）操作

/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK:否则返回
ERROR*/
Status Pop(LinkStack *S,SElemType *e)
{
    LinkStackPtr p;
    if(StackEmpty(*S))
        return ERROR;
    *e=S->top->data;
    p=S->top;   /*将栈顶结点赋值给p*/
    S->top-S->top->next; /*使得栈顶指针下移一位，指向后一结点*/
    free(p);    /*释放结点p*/
    S->count--;
    return OK;
}

注意 1、使用过程中元素的个数变化不可预料,有时很小,有时非常大，那么最好用链栈 2.如果它的变化在可控的范围内,建议用顺序栈

栈的应用

应用1—递归 递归的定义: 一个直接调用自己或间接调用自己的函数成为递归函数 注意： 必须有退出条件，让递归退出，是函数不再调用自身。 优点： 是代码简洁，更易理解 缺点; 1.递归由于是函数调用自身,而函数调用是有时间和空间的消耗的:每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址以及临时变量,而往栈中压入数据和弹出数据都需要时间。 2.调用栈可能会溢出，其实每一次函数调用会在内存栈中分配空间，而每 个进程的栈的容量是有限的,当调用的层次太多时,就会超出栈的容量,从而导致 栈溢出。

应用2—四则运算表达式 中缀表达式转后缀表达式： 可以实现所有的计算按运算符出现的顺序,严格从应向有进行(不再考虑运 算符的优先级和括号） 规则： 1.从左到右遍历中缀表达式的每个数字和符号 2.遇到数字，输出，成为后缀表达式的一部分 3.遇到符号,判断其,我顶符号的优先级,不高于栈顶符号,栈顶符号依次出线，示将当前符号进栈 4.遇到右括号依次弹出栈里的元素,直到弹出左括号 5.当钱变为空时,输出的结果即为后缀表达式

10、队列

①队列的定义

定义 队列(queue)是只允许在一端进行插入操作,而在另外一端进行删除操作的线性表。 允许插入的端是队尾,允许删除的一端是队头。 特点： 一种先进先出(First In First Out)的线性表,简称FIFO. 逻辑结构： 与线性表一样，是一对一的关系 存储结构： 顺序队和链队,以循环顺序队列最常见 关键： 掌握入队和出队操作

②队列的抽象数据类型

ADT ADT队列（Queue） Data 同线性表。元素具有相同的类型,相邻元素具有前驱和后继 Operation InitQueue(Q);初始化操作,建立一个空的队列Q DestroyQueue(Q);若队列Q存在,则销毁它 ClearQueue(Q);将队列Q清空 QueueEmpty(Q);若队列Q为空,返回true,否则返回false GetHead(Q,e);若队列Q存在且非空,用e返回对头元素 EnQueue(Q,e);若队列Q存在，插入一个元素到队尾 DeQueue(*Q,e);删除对头元素,并返回值 QueueLength(Q);返回队列Q的元素个数 endADT

③循环队列 队列的顺序存储结构 利用一组连续的存储单元(一维数组)依次存放队头到队尾的各个元素,成为顺序队列。 入队 在队尾追加一个元素,不需要移动任何元素,因此时间复杂度为O(1) 出队 两种方式: 1.队头不动 2.队头移动

队列的顺序存储结构 队头不动的方式和线性表的顺序存储结构完全相同 队头移动方式: 1.结构定义代码

#define MAXSIZE 20 /* 存储空间初始分配量*/
​
typedef struct
{
    QElemType data[MAXSIZE];
    int front,      /* 头指针*/
    int rear;       /*尾指针,若队列不空,指向队列尾元素的下一个位置*/
}SqQueue;

队列的顺序存储结构 队头移动方式：

2.空队列的特征： Q.front = Q.rear; 3.队列极易装满,因为数组通常有长度限制,而其前端空间无法释放和利用 4.会造成假溢出 当尾指针己经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 解决假溢出的途径----采用循环队列

新问题 在循环队列中,空队特征是front=rear,队满时也会有front=rear;判断条件出现二义性 解决方案有3种： 1·使用计数器记录队列中元素的个数(队列长度) 2.加设标志位，删除时置1，插入置0，当front=rear时读取标志位就可以判断是空还是满了 3.浪费一个单元，对满特征是 front=(rear+1)%QueueSize 计算队列长度 (rear-front+QueueSize) % QueueSize

操作

/*初始化一个空队列Q*/
Status InitQueue(SqQueue*Q)
{
    Q->front=0;
    Q->rear=0;
    return OK;
}
​
/*返回Q的元素个数，也就是队列的当前长度*/
int QueueLength(SqQueue Q)
{
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
​
/*若队列未满,则插入元素e为Q新的队尾元素*/
Status EnQueue(SqQueue *Q,QElemType e)
{
    if ((Q->rear+1)%MAXSIZE==Q->front) /队列满的判断*
        return ERROR;
    Q->data[Q->rear]=e;     /*将元素e赋值给队尾*/
    Q->rear=(Q->rear+1)%MAXSIZE;/*rear指针向后移一位置，*/
                                /*若到最后则转到数组头部*/
        return OK;
}
​
/*若队列不空,则删除Q中队头元素,用e返回其值*/
Status DeQueue(SqQueue *Q,QElemType *e)
{
    if (Q->front == Q->rear)        /*队列空的判断*/
        return ERROR;
    *e=Q->data[Q->front];       /*将队头元素赋值给e*/
    Q->front=(Q->front+1)%MAXSIZE;/*front指针向后移一位置*/
    /* 若到最后则转到数组头部*/
    return OK;
}

④队列的链式存储结构及实现

链队列 队列的链式存储,称为链队列。 其实就是线性表的单链表，只不过只能尾进头出 结构定义

typedef struct QNode/*结点结构*/
{
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr,
​
typedef struct
{/*队列的链表结构*/
    QueuePtr front,rear;/*队头、队尾指针*/
}LinkQueue;

1.空链队的特征: front=rear 2.链队会满吗?一般不会，结点是动态申请的，除非内存不够

入队

/*插入元素e为Q的新的队尾元素*/
Status EnQueue(LinkQueue *Q,QElemType e)
{
    QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    if（!s）/*存储分配失败*/
        exit(OVERFLOW);
    s->data=e;
    s->next=NULL;
    Q->rear->next=s;/*把拥有元素e的新结点s赋值给原队尾结点的后继*/
    Q->rear=s;
    return OK;      /*把当前的s设置为队尾结点， rear指向s*/
}

出队

/*队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR*/
Status DeQueue(LinkQueue *Q,QElemType *e)
{
    QueuePtr p;
    if(Q->front==Q->rear)
        return ERROR;
    p=Q->front->next;/*将欲删除的队头结点暂存给p*/
    *e=p->data;     /*将欲删除的队头结点的值赋值给e*/
    Q->front->next=p->next;/*将原队头结点的后继p->next赋值给头结点后继*/
    if(Q->rear==p)  /*若队头就是队尾，则删除后将rear指向头结点*/
        Q->rear=Q->front;
    free(p);
    return OK;
}

11、串

①串的定义

定义 串( string)是由零个或多个字符组成的有限序列,记作s="a,a2..an”,其中s为串的名字,用成对的双引号括起来的字符序列为串的值,但两边的双引号不算串值,不包含在串中。a(1sisn)可以是字母、数字或其它字符。n为串中字符的个数,称为串的长度。 注意： 1.空串:不含任何字符的串称为空串,它的长度n=0 2.空白串:含有一个或多个空格的串 3·子串和主串:若一个串是另一个串中连续的一段,则这个串称为另一个串的子串,而另一个串相对于该串称为主串。例如,串s1=“abcdefg”,s2="fabcdefghxyz”，则s1为s2的子串， s2相对于s1为主串

空串是任意串的子串,任意串是自身的子串

②串的抽象数据类型

ADT ADT串 （string)

Data
串中的元素仅有一个字符组成，相邻元素具有前驱和后继的关系
Operation
    StrAssign(T,*chars);生成一个字符串T,值为chars
    StrCopy(T,S);
    ClearString(S);
    StringEmpty(S);
    StrLength(S);
    StrCompare(S,T);
    Concat(T,S1,S2); ;连接字符串S1,S2,用T返回
    SubString(Sub,S,pos,len);求子串
    Index(S,T,pos); 子串在主串中的位置
    Replace(S,T,V); 替换主串里的子串
    Strinsert(S,pos,T);插入子串
    StrDelete(S,pos,len);删除子串
endADT

③串的存储结构

顺序存储结构 利用一组连续的存储单元(一维数组)来存储串中的字符序列。按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区。一般是用定长的数组来定义。

链式存储结构 采用单链表来存储串

④朴素模式匹配算法 目的 确定主串中所含子串(模式串)第一次出现的位置。模式匹配成功是指在主串S中能够找到子串(模式串)T,否则,称子串(模式串)T在主串S中不存在。 常用的有两种模式匹配方法： BF算法(又称朴素的,经典的、穷举的) KMP算法(避免回溯，匹配速度快)

BF算法思想： 1)从主串S的第一个字符起和模式串T的第一个字符进行比较,若相等,则继续逐个比较后续字符,否则从串S的第二个字符起再重新和串T进行比较。 2)依此类推，直至串T中的每个字符依次和串S的一个连续的字符序列相等,则称模式匹配成功,此时串T的第一个字符在串S中的位置就是T在S中的位置,否则模式匹配不成功。

12、树

①树的定义

定义 树是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中： (1)有且仅有一个特定的根(Root)的结点; (2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、...、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

②相关概念

根：根结点(没有前驱) 叶子：终端结点(没有后继) 森林：指m棵不相交的树的集合（例如删除A后的子树个数） 双亲：即上层的那个结点（直接前驱） 孩子：即下层结点的子树的根（直接后继） 兄弟:同一双亲下的同层结点(孩子之间互称兄弟) 堂兄弟:即双亲位于同一层的结点(但并非同一双亲) 祖先:即从根到该结点所经分支的所有结点 子孙:即该结点下层子树中的任一结点 结点：即树的数据元素 结点的度：结点挂接的子树 有几个直接后继就是几度， 结点的层次:从根到该结点的层数 终端结点：即度为0的结点，即叶子 分支结点：即度不为0的结点（也称为内部结点） 树的度:所有结点度中的最大值(Max{各结点的度]) 树的深度(或高) :指所有结点中最大的层数(Max{个结点的层次}）

树的抽象数据类型 ADT 树(tree) Data 树由一个根结点和若干子树构成。树中结点具有相同数据类型。 Operation InitTree(T)：构造空树T。 DestroyTree(T)：销毁树T。 CreateTree( T, definition):按definition中给出树的定义来构造树。 ClearTree(T):若树T存在,则将它清空为空树。 TreeEmpty(T):若T为空树,返回true;若T不为空树,返回false. TreeDepth(T)：返回T的深度。 Root(T)：返回T的根结点。 Value(T,cur_e): cur_e是树T的结点，返回此结点的值。 Assign(T, cur_e, value):给树T的cur_e结点赋值为value. Parent(T, cur_e):若cur_e是T的非根结点,返回它的双亲:否则返回空。 LeftChild(T, cur_e):若cur_e是T的非叶结点,返回它的最左孩子;否则返回空。 RightSibling(T, cur_e):若cur_e有右兄弟,返回它的右兄弟;否则返回空。 InsertChild(*T, p, i, c): p为指向树T的某个结点, i为指向p的结点的度加1, c为与T不相交的非空树,操作结果为c为插入T中P所指向结点的第i+1棵子树。 DeleteChild("T,p, i): p指向T的某个结点, i为p所指结点的度,操作结果为删除T中p指向的结点的第i棵树。 endADT

③逻辑结构

特点： 一对多(1:n),有多个直接后继(如家谱树、目录树等等),但只有一个根结点,且子树之间互不相交。

几种表示方法： 1.图形表示方法：

2.嵌套集合表示法

3.日录树表示法(又称凹入表示法)

4.左孩子-右兄弟表示法

树是非线性的如何存储？ 仍然有顺序存储、链式存储等方式。

树的顺序存储方案： 可规定为:从上到下、从左至右将树的结点依次存入内存。 重大缺陷:复原困难,不能唯一复原没有实用价值

树的链式存储方案： 可用多重链表:有多个后继指针 细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长” ? 缺点:等长结构太浪费(每个结点的度不一定相同) 不等长结构太复杂(要定义好多种结构类型) 解决思路：先研究最简单的、最有规律的树，然后设法把一般的树转化为简单的树。 最简单的树：二叉树

④树的运算

要明确： 1·普通树(即多叉树)转化成二叉树,会给运算带来很大的方便。 2.二叉树的运算