数据结构

第一章绪论

1.1什么是数据结构

数据结构是一门研究非数值计算的程序设计问题中的计算机的操作对象以及他们之间的关系和操作等的学科。

1.2基本概念和术语

数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可有若干个数据项组成。数据项是数据的不可分割的最小单位。

数据对象是性质相同的数据元素的集合，是数据的一个子集。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

结构：数据元素相互之间的关系

四种基本结构：

集合：同属于一个集合
线性结构：结构中的数据元素之间存在一个对一个的关系。
树形结构：结构中的数据元素之间尽一个对多个的关系。
图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。

因此数据结构的形式定义：是一个二元组，数据元素的有限集+数据元素关系的有限集。

在计算机中称二进制位串为元素或结点，当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域，因此元素或结点可看成是数据元素在计算机中的映像。

数据元素之间的关系在计算机中有两种不同的表示方法：

顺序映像：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系得到——》顺序存储结构
非顺序映像：借助指示元素存储地址的指针表示元素之间的逻辑关系得到——》链式存储结构

数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。可分为两类：①非结构的原子类型——不可分解，例如C语言中的基本类型。②结构类型——的值是由若干个成分按某种结构组成的，因此可以分解。

某种意义上，数据结构是“一组具有有相同结构的值“，则结构类型是”由一种数据结构和定义在其上的一组操作组成“。

抽象数据类型：ADT是指一个数学模型以及定义在改模型上的一组操作。抽象数据类型的定义进取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。

原子类型

固定聚合类型

可变聚合类型：构成可变聚合类型的值的成分的数目是不确定，

（后两种类型可统称为结构类型）

操作类型三元组定义：

数据对象（定义了关系运算的某个集合），数据关系，基本操作

多形数据类型：是指其值的成分不确定的数据类型。（具有相同的数学抽象特性）

1.3抽象数据类型的表现与实现

对本书语言作简要说明：

预定义常量和类型
1. 函数结果状态代码：true1，false0，OK1，error0，infeasible-1，overflow2；
2. status 是函数的类型，其值是函数结果状态代码：typedef int status
数据结构的表示（存储结构）用类型定义（typedef）描述
基本操作的算法形式：注意形参表中，以&打头的参数即为引用参数
赋值语句有：简单赋值，串联赋值，成组赋值，交换赋值，条件赋值
选择语句有：if，else，Switch（case）
循环语句有：for，while，do-while
结束语句有：函数结束语句（return 表达式； return；）case结束语句：break；，异常结束语句：exit(异常代码);
输入输出语句：scanf，printf
注释
基本函数：max，min，abs()求绝对值，floor()求不足整数值，ceil()求进位整数值，eof()判定文件结束，eoln()判定行结束
逻辑运算约定：&&短路与，||短路或

1.4算法和算法分析

算法：是对特定问题求解步骤的一个描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

五个重要特性：

有穷性：有穷步，每一步有穷时间
确定性：每条指令有确切含义，任何条件下，算法只有唯一执行路径。
可行性：
输入
输出

一个好的算法：

正确性：4个层次
可读性：算法主要是为了阅读交流，其次是机器执行
健壮性：当输入数据非法时，算法也能适当做出反应或进行处理，而不会产生莫名其妙的输出结果。
效率与低存储量需求

效率算法的度量：

事后统计
事前分析估算

一个算法是由控制结构（顺序，分支，循环三种）和源操作（指固有数据类型的操作）构成，则算法时间取决于两者的综合效果。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作：

T(n)=O(f(n))

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。

语句的频度是指该语句重复执行的次数。

时间复杂度：无特别指明，一般是指最坏情况下的时间复杂度。

算法的存储空间需求：

以空间复杂度作为算法所需要的存储空间的量度。

S(n)=O(f(n))

其中n为问题的规模（或大小），一个上机执行的程序除了需要存储空间来寄存本身所用指令、常量、变量和输入数据外，也需要对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。

若额外空间相对于输入数据量来说是常数，则称次算法为原地工作。此时，S(n)=O(1);

本章习题

1.在数据结构中，从逻辑上可以把数据结构分成（ C ）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构

C．线性结构和非线性结构 D．内部结构和外部结构

4.以下说法正确的是（ D ）。

A．数据元素是数据的最小单位

B．数据项是数据的基本单位

C．数据结构是带有结构的各数据项的集合

D．一些表面上很不相同的数据可以有相同的逻辑结构

数据元素是数据的基本单位。 数据项是数据的不可分割的最小单位。

6.以下数据结构中，（A）是非线性数据结构

A．树 B．字符串 C．队 D．栈

5.以下与数据的存储结构无关的术语是（ C ）。

A．顺序队列 B. 链表 C. 有序表 D. 链栈

第二章线性表

线性结构的特点：在数据元素的非空有限集中，①存在唯一的一个被称作“第一个”的数据元素。②存在唯一一个别称作“最后一个”的数据元素。③④除第一个之外，集合中的每一个数据元素均只有一个前驱，只有一个后继

线性表的类型定义

线性表是最常用且最简单的一种数据结构。一个线性表是N个数据元素的有限序列。稍微复杂的线性表中，一个数据元素可以由若干个数据项组成，在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称文件。

同一线性表中的元素必定有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。

直接前驱元素，直接后继元素。

线性表中每个数据元素都有一个确定的位置，如a₁是第一个数据元素，a_i是第i个数据元素，因此i称为数据元素a_i在线性表中的位序。

线性表是一个相当灵活的数据结构，对其数据元素可以进行访问，插入，删除等操作。

抽象数据类型线性表的定义：

ADT List{
	数据对象：
	数据关系：
	基本操作：
		构造
		销毁
		置空
		判空
		取元素
		定位元素
		插入
		删除
		遍历
		……
}

例2-1：合并两个线性表

算法思想：遍历LB，将所有在线性表B中，但不在线性表A中的数据元素插入到线性表A中。

例2-2：已知LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素扔按值非递减有序排列

算法：设两个指针i和j分别指向LA和LB中的某个元素，显然指针i，j的初值均为1，假设i指向a,j指向b，插入c，则：c=a>b?b:a;

当LA和LB中有一个线性表已经遍历结束，则对另外一个线性表的剩余元素采取插入到线性表LC中即可。

2.2线性表的顺序表示和实现

线性表的线性表示是指用一组地址连续的存储单元依次存储线性表的数据元素。

LOC(a1)是线性表的第一个数据元素a1的存储地址，通常称为线性表的起始位置或基地址。（每个元素需要占有L个存储单元）

线性表的这种机内表示称作线性表的顺序存储结构或顺序映像。通常称这种存储结构的线性表为顺序表。（以元素在计算机内的“物理位置相邻”来表示线性表中数据元素之间的逻辑关系）故线性表的顺序存储结构是一种随机存取的存储结构。

通常用数组来描述数据结构中的顺序存储结构，线性表长度可变，采用动态内存分配。

typedef struct{
	ElemType *elem;//指示线性表的基地址
	int length;//指示线性表的当前长度。
	int listsize;//指示顺序表当前分配的存储空间大小，一旦插入元素而空间不足时，可进行再分配。
}SqList;

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
L.length=0;//空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储空间。

算法2.3：在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素

算法：在第i(1≤i≤n)个元素之间插入一个元素时，需将第n至第i(共n-i+1)个元素向后移动一个位置。

①要判断插入的位置i是否合理，

②要判断存储空间是否已满，若满则进行增加分配(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

③将插入位置及之后的元素后移。

算法2.4线性表的删除操作

算法：删除第i(1≤i≤n)个元素时需将从第i+1至第n(共n-i)个元素依次向前移动一个位置。

①要判断需删除的位置i是否合法，若合法，则返回其值，p=&(L.elem[i-1])

;e=*p;;q=L.elem+L.length-1其中：p为被删除元素的位置，将被删除元素的值赋给e，用q表示表尾元素的位置。②而后可对被删除元素之后的元素左移。

算法2.5 在顺序存储结构的线性表中插入或删除一个数据元素，平均移动表中一半元素，若表长为n，则4,3算法的时间复杂度均为O(n)

算法2.6 顺序表的合并

算法2.7 元素赋值，时间复杂度为O(La.length+Lb.length)

2.3 线性表的链式表示和实现

链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。

2.3.1线性链表

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

因此对于数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai的存储映像，称为结点。它包括两个域：其中存储数据元素信息的域称为 数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点链接成一个链表，即为线性表的链式存储结构。

头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。

逻辑上相邻的数据元素并不要求其物理位置紧邻，由此，这种存储结构为非顺序映像或链式映像。

//线性表的单链表存储结构
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
//在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可存储线性表的长度类的信息。头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）
//此时，单链表的头指针指向头结点。
//若线性表为空表，则头结点的指针域为空，

在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是：非随机存取的存储结构。

算法2.8在单链表中插入一个数据元素

在a,b之间插入数据元素x。①首先生成一个数据域为x的结点，②然后插入到单链表中。③需要修改a结点中的指针域，使其指向结点x④使得结点x的指针域指向结点b

设s为指向结点x的指针，p为单链表中指向结点a的指针，则：

s->next=p->next; p->next=s;

算法2.9在单链表中删除一个数据元素

a,b,c 要求删除结点b。则需要修改结点a的指针域。

p->next=p->next->next;

在单链表中插入和删除一个数据元素，仅需要修改指针而不需要移动元素。

算法2.10 头插法

首先:L->next=null;
for(i=n;i>0;--i){
	p=(LinkList)malloc(sizeof(LNode));
	scanf(&p->data);
	p->next=L->next;
	L->next=p;
}
//即一直在链表的首部进行插入。

算法2.11 将两个有序链表并为一个有序链表

P31

算法2.12 线性表的静态单链表存储结构

数据的第零分量可看出是头结点，其指针域指示链表的第一个结点。

静态链表

在静态单链表中查找第1个值为e的元素。

若第i个分量表示链表的第k个结点，则S[i].cur指示第k+1个结点的位置。

i=S[i].cur的操作实为指针后移。

2.3.2循环链表

循环链表是另一种形式的链式存储结果。特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

将两个线性表合并成一个表时，仅需要将一个表的表尾和另一个表的表头相接。即：①Ta头结点保存②Tb表接到Ta尾③释放Tb头④Tb尾接到Ta头。

2.3.3 双向链表

双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱。

typedef struct DuLNode{
	ElemType data;
	struct DuLNode *prior;
	struct DuLNode *next;
}DuLNode,*DuLinkList;

双向链表也有循环表。

算法2.18 在双向链表中插入（在带头结点的双链循环链表中第i个位置前插入元素e)

p=GetElemP_DuL(L,i);//p指向第i个元素
s=(DuLinkList)malloc(sizeof(DuLNode));
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;

算法2.19 在双向链表中删除第i个元素

p=GetElemP_DuL(L,i);//p指向第i个元素
p->prior->next=p->next;
p->next->prior=p>prior;
free(p);
return ok;

从实际应用角度出发重新定义线性链表及其基本操作：
一个带头结点的线性链表类型定义如下：

typedef struct LNode{//结点类型
	ElemType data;
	struct LNode *next;
}*Link,*Position;

typedef struct{//链表类型
	Link head,tail;//分别指向线性链表中的头结点和最后一个结点
	int len;//指示线性链表中数据元素的个数。
}LinkList;

P38—-39

2.4一元多项式的表示及相加

一般情况下的一元n次多项式可写成：

$P_n(x)=p_1x^{e_1}+p_2x^{e_2}+……+p_mx^{e_m}$

一元多项式的计算：

两个一元多项式的乘法的运算，可以利用两个一元多项式的加法的算法来实现，因为乘法运算可以分解为一系列的加法运算。

$M(x)=A(x)*B(x)=…… 每一项都是一个一元多项式$

本章习题

11.若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ C）。

A．O(1) B．O(n) C．O(n2) D．O(nlog2n)

第三章栈和队列

从数据结构角度看，栈和队列也是线性表，是操作受限的线性表。

3.1栈

3.1.1 抽象数据类型栈的定义

栈是限定仅在表尾进行插入或删除操作的线性表。对栈来说，表尾端有特殊含义，称为栈顶（top），表头端称为栈底（bottom），不含元素的空表称为空栈。

栈又称 后进先出的线性表（LIFO）

基本操作：

InitStack

DestoryStack

ClearStack

StackEmpty

StackLength

GetTop

Push(&S,e);//插入元素e为新的栈顶元素

Pop(&S,e);//删除S的栈顶元素，并用e返回其值

StackTraverse

3.1.2 栈的表示和实现（栈也有两种存储表示方法）

顺序栈：栈的顺序存储结构是利用一组地址连续的存储单位一次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。

顺序栈：

typedef struct{
	SElemType *base;//栈底指针，若base值为null，则表明栈结构不存在
	SElemTpye *top;//栈顶指针，其初始值指向栈底，top=base可作为栈空的标志。
	int stacksize;//指示栈的当前可使用的最大容量。
}SqStack;
在非空栈中，其栈顶指针始终在栈顶元素的下一个位置上。

//构造一个空栈S
S.base=(SElemType *)malloc(STACK_INIIT_SIZE*sizeof(SElemType));
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
//栈满，追加存储空间。
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACK_INIIT_SIZE)*sizeof(SElemType));
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INIT_SIZE;
//插入元素e作为新的栈顶元素
*S.top++=e;
//删除S的栈顶元素，用e返回其值
e=*--S.top;

3.2 栈的应用举例

3.2.1数制转换

基本原理：

$N=(N div d)*d+N mod d$

其中div是整除运算，mod为求余运算。

//将十进制转为八进制
while(N){
	Push(S,N%8);
	N=N/8;
}//进栈

while(!StackEmpty(S)){
	Pop(S,e);
    printf("%d",e);
}//出栈
利用后进先出的特性。

3.2.2 括号匹配的检验

建议括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。

3.2.3 行编辑程序

接受用户从终端输入的程序或数据，并存入用户的数据区。

若发现键入一个错误的字符，则补进一个退格符“#”。若果差错较多，这进入一个退行符“@”。

为此，可设这个输入缓冲区为一个栈结构，当终端接受了一个字符后，对其进行判断，如果既不是退格符也不是退行符，则将该字符压入栈顶。若为退格符，则从栈顶删去一个字符，如果为退行符，则将字符栈清为空栈。

while(ch!=EOF){//EOF是全文结束符。
 while(ch!+EOF&&ch!='\n'){
	switch(ch){
	case '#':Pop(S,c);	break;
	case '@':ClearStack(S);	break;
	default:Push(S,ch);	break;
	}
	}
}

3.2.4 迷宫求解(待理解)

P51

3.2.5 表达式求值

任何一个表达式都是由操作数，运算符和界限符组成的，称他们为单词。

为实现算符优先算法，可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做 OPND，用以寄存操作数或运算结果。算法的基本思想如下：

①首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素。②以此读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后做相应操作，直至每个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）

3.3 栈和递归的实现

void hanoi(int n,char x,char y,char z){//将塔座x上安直径由小到大且自上而下编号为1到n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。搬动操作move(x,n,z)可定义为（c是初值为0的全局变量，对搬动计数）
//printf("%i.move disk %i from %c to %c\n",++c,n,x,z);
    if(n==1)
        move(x,1,z);//将编号为1的圆盘从x移动到z
    else{
        hanoi(n-1,x,z,y);//将x上编号为1至n-1的圆盘移动到y,z作辅助
        move(x,n,z);//将编号为n的圆盘从x移动到z
        hanoi(n-1,y,x,z);//将y上编号为1至n-1的圆盘移动到z,x作辅助
    }
}

3.4 队列

队列是先进先出(FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除元素。在队列中，允许插入的一端叫做队尾，允许删除的一端则称做队头。

队列的基本操作：

GetHead(Q,&e);//用e返回Q的队头元素。

EnQueue(&Q,e);//插入元素e为Q的新的队尾元素

DeQueue(&Q,&e);//删除Q的队头元素，并用e返回其值。

限定性数据结构：双端队列deque：双端队列是限定插入和删除操作在表的两端进行的线性表。

3.4.2 链队列——队列的链式表示和实现

用链表表示的队列简称为链队列。

为了方便起见，我们给链队列添加一个头结点，并令头指针指向头结点，由此，空的链队列的判决条件为：头指针和尾指针均指向头结点。

//单链队列——队列的链式存储结构：
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

队列的基本操作：

//构造一个空队列：
status InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    Q.front->next=null;
}
//销毁队列Q
while(Q.front){
    Q.rear=Q.front->next;
    free(Q.front);
    Q.front=Q.rear;
}
//插入元素e为Q的新的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=null;
Q.rear->next=p;
Q.rear=p;
//删除Q的队头元素，用e返回其值，
p=Q.front->next;
e=p->data;
Q.front->next=p->next;//头指针往后
if(Q.rear==p)Q.rear=Q.front;
free(p);

3.4.3 循环队列——队列的顺序表示和实现

有待理解

初始化建空队列时，令front=rear=0;每当插入新的队列尾元素时，尾指针增1，每当删除队列头元素时，头指针增1。

在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。

将顺序队列臆造为一个环状的空间，称之为循环队列：约定 ”队列头指针在队列尾指针的下一位置（指环状的下一位置）上“作为队列呈”满“状态的标志

//循环队列——队列的顺序存储结构
#define MAXSIZE 100
typedef struct{
    QElemType *base;//初始化的动态分配存储空间
    int front;//头指针，指向队列头元素
    int rear;//尾指针，指向队列尾元素的下一个位置。
}SqQueue;
//构造一个空队列
Q.base=(QElemType*)malloc(MAXSIZE*sizeof(QElemType));
Q.front=Q.rear=0;
//返回队列的长度
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
//插入元素e为Q的新的队尾元素。
if((Q.rear+1)%MAXSIZE==Q.front)return error;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
//删除队列的头元素，用e返回其值。
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;

栈和队列习题

（2）设有一个递归算法如下

int fact(int n) { //n大于等于0

if(n<=0) return 1;

else return n*fact(n-1); }

则计算fact(n)需要调用该函数的次数为（ C× ）。 fact(n)本身计一次，

A． n+1 B． n-1 C． n D． n+2

（6）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（　B）。

A. (rear+1)%n==front B. rear==front

C．rear+1==front D. (rear-l)%n==front

（10）设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。

A． 6 B. 4 C. 3 D. 2

第四章串

4.1串类型的定义

串（或字符串）是由零个或多个字符组成的有限序列，一般即为:

$s='a_1a_2a_3…a_n'(n≥0)$

常见概念：

串的长度：串中字符的数目空串：零个字符

子串；主串；字符在串中的位置；

两个串相等：两个串长度相等，并且各个对应位置的字符都相等。

空格串（blank string）：由一个或多个空格组成的串。它的长度是串中空格的个数，（和空串不一样）

///串定位-子串的位置
int Index(Stirng S,String T,int pos){
    if(pos>0){
        n=StrLength(S);
        m=StrLength(T);
        i=pos;
        while(i<=n-m+1){
			SubString(sub,S,i,m);
            if(StrCompare(sub,T)!=0)	++i;
            else return i;//返回子串在主串中的位置。
        }
    }
    return 0;
}

4.2串的表示和实现

串有三种机内表示方法。

4.2.1定长顺序存储表示

1 2	#define MAXSTRLEN 255//用户可在255内定义最大串长 typedef unsigned char SString[MAXSTRLEN+1];//0号单元存放串的长度

串联接

三种情况：

S1[0]+S2[0]≤MAXSTRLEN;

S1[0]MAXSTRLEN;

S1[0]=MAXSTRLEN;

求子串（即为复制字符序列的过程）

Status SubString(SString &Sub,SString S,int pos,int len){
    if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)return error;
    Sub[1..len]=S[pos..pos+len-1];
    Sub[0]=len;
    return ok;
}

在顺序存储结构中，实现串操作基于：字符序列的复制，时间复杂度基于复制的字符序列的长度。截尾法常用于处理长度超过上限。

4.2.2堆分配存储表示

typedef struct{
    char *ch;//若是非空串，则按串长分配存储区，否则ch为null。
    int length;
}HString;

StrCopy(&T,S)实现算法：先释放串T所占的空间，为T开辟和S长度相等的存储空间，后将串S的值复制到串T中。

//
Status StrInsert(HString &S,int pos,HString T){
    
}
S.ch=(char *)realloc(S.ch,(S.length+T.length)*sizeof(char)));//重新分配空间
for(i=S.length-1,i>pos-1;--i)	S.ch[i+T.length]=S.ch[i];//腾出位置
S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];//插入T

P76-77有串的堆分配存储表示及其基本操作

4.2.3串的块链存储表示

#define CHUNKSIZE 80
typedef struct Chunk{
	char ch[CHUNKSIZE];
    struct Chunk *next;
}Chunk;
typedef struct{
    Chunk *head,*tail;//串的头和尾指针
    int curlen;//串的当前长度
}

链式存储方法

$存储密度=\frac{串值所占的存储位}{实际分配的存储位}$

4.3串的模式匹配算法（不在期中考范围，待学）

算法种类：

BF算法：古典的，经典的，朴素的，穷举的
KMP算法：速度快

4.4串操作应用

文本编辑

第五章数组和广义表

5.1数组的定义

5.2数组的顺序存储表示

#include<stdarg.h>
#define MAX_ARRAY_DIM 8
typedef struct{
    ElemType *base;//数组元素基址，由initArray分配
    int dim;//数组维数
    int *bounds;//数组维界基址
    int *constants;//数组映像函数常量基址
}Array;

5.4广义表的定义

广义表是线性表的推广。

广义表一般记作：

$LS=(a_1,a_2,…,a_n)$

其中，LS是广义表的名称，n是其长度，在广义表中a_i可以是单个元素，亦可以是广义表，分别称为广义表的原子和子表。当广义表LS非空时，称第一个元素a1为LS的表头head，称其余元素组成的表(a2,a3,…an)为LS的表尾tail。

结论：

列表的元素可以是子表，子表的元素还可以是子表
列表可为其他列表所共享
列表可以是一个递归的表，即列表也可以是其本身的一个子表。
任何一个非空列表的表头可能是原子，也可能是列表，而其表尾必定是列表。

5.5广义表的存储结构

通常采用链式存储结构，每个数据元素可用一个结点表示。

第六章树和二叉树

树形结构是一类重要的非线性数据结构。

6.1数的定义和基本术语

树是n个结点的有限集。在任意一棵非空树种，有且仅有一个特定的称为根的结点。

树的表示方法：①嵌套集合②以广义表的形式表示③凹入表示法

基本术语；

结点的度（结点拥有的子树的数目）

叶子、终端结点

非终端结点、分支结点

树的度（各结点度的最大值）

孩子，双亲，兄弟，祖先，子孙

结点的层次：（根为第一层，根的孩子为第二层）

堂兄弟：其双亲在同一层的结点

树的深度：树中结点的最大层次

有序树：树中结点的各子树看成从左至右是有次序的（即不能互换）

森林：是m棵互不相交的树的集合。

6.2二叉树

特点：每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）。二叉树的子树有左右之分，其次序不能任意颠倒。

3个结点的二叉树有5种；3个结点的树有2种。

二叉树的性质

性质1：在二叉树的第i层上最多有2^(i-1)个结点（i≥1）

性质2：深度为K的二叉树最多有2^k-1个结点（k≥1)

性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

完全二叉树和满二叉树

性质4：具有n个结点的完全二叉树的深度为[log_2n]+1

$k=[log_2n]+1$

性质5：n个结点的完全二叉树，深度为 $[log_2n]+1$ 的结点按层次编号，从上到下，从左到右。则：①i=1时，其为二叉树的根，无双亲②i的左孩子是2i，右孩子是2i+1；其中i是双亲。

6.2.3二叉树的存储结构

顺序存储结构

仅适用于完全二叉树，否者严重造成存储空间的浪费。

链式存储结构

在含n个结点的二叉链表中有n+1个空链域。 $2n-(n-1)=n+1$ 其中n个结点有2n个链域，除根结点外，其它结点都有一个双亲（即都占有着双亲的一个链域）。

typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

6.3遍历二叉树和线索二叉树

二叉树是一种非线性结构

三种遍历方法：

先序遍历：根结点——左子树——右子树
中序遍历：左子树——根结点——右子树
后序遍历：左子树——右子树——根结点

递归算法：

P131

6.3.2线索二叉树

增加了两个标志域，

这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。

其中指向结点前驱和后继的指针，叫做线索。

加上线索的二叉树又称为线索二叉树。

实线为指针（指向左右子树），虚线为线索（指向前驱和后继）

对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

数据结构

第一章 绪论

1.1什么是数据结构

1.2基本概念和术语

1.3抽象数据类型的表现与实现

1.4算法和算法分析

本章习题

第二章 线性表

线性表的类型定义

例2-1：合并两个线性表

例2-2： 已知LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素扔按值非递减有序排列

2.2线性表的顺序表示和实现

算法2.3：在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素

算法2.4线性表的删除操作

算法2.5 在顺序存储结构的线性表中插入或删除一个数据元素，平均移动表中一半元素，若表长为n，则4,3算法的时间复杂度均为O(n)

算法2.6 顺序表的合并

算法2.7 元素赋值，时间复杂度为O(La.length+Lb.length)

2.3 线性表的链式表示和实现

2.3.1线性链表

算法2.8在单链表中插入一个数据元素

算法2.9在单链表中删除一个数据元素

算法2.10 头插法

算法2.11 将两个有序链表并为一个有序链表

算法2.12 线性表的静态单链表存储结构

2.3.2循环链表

2.3.3 双向链表

算法2.18 在双向链表中插入（在带头结点的双链循环链表中第i个位置前插入元素e)

算法2.19 在双向链表中删除第i个元素

2.4一元多项式的表示及相加

本章习题

第三章 栈和队列

3.1栈

3.1.1 抽象数据类型栈的定义

3.1.2 栈的表示和实现（栈也有两种存储表示方法）

3.2 栈的应用举例

3.2.1数制转换

3.2.2 括号匹配的检验

3.2.3 行编辑程序

3.2.4 迷宫求解(待 理解)

3.2.5 表达式求值

3.3 栈和递归的实现

3.4 队列

3.4.2 链队列——队列的链式表示和实现

3.4.3 循环队列——队列的顺序表示和实现

有待理解

栈和队列习题

第四章 串

4.1串类型的定义

4.2串的表示和实现

4.2.1定长顺序存储表示

串联接

求子串（即为复制字符序列的过程）

4.2.2堆分配存储表示

4.2.3串的块链存储表示

4.3串的模式匹配算法（不在期中考范围，待学）

4.4串操作应用

文本编辑

第五章 数组和广义表

5.1数组的定义

5.2数组的顺序存储表示

5.4广义表的定义

5.5广义表的存储结构

第六章 树和二叉树

6.1数的定义和基本术语

6.2二叉树

二叉树的性质

6.2.3二叉树的存储结构

顺序存储结构

链式存储结构

6.3遍历二叉树和线索二叉树

6.3.2线索二叉树

第一章绪论

第二章线性表

例2-2：已知LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素扔按值非递减有序排列

第三章栈和队列

3.2.4 迷宫求解(待理解)

第四章串

第五章数组和广义表

第六章树和二叉树