数据结构考研讲义.doc

目录
绪论 3
0、1 基本概念 3
第一章 线性表 4
1、1 线性表得定义 4
1、2 线性表得实现 4
1、2、2 线性表得链式存储结构 6
第二章 栈、队列与数组 11
2、1 栈 11
2、2 队列 15
2、3 特殊矩阵得压缩存储 17
2、3、1 数组 17
2、3、2 特殊矩阵 17
第三章 树与二叉树 20
3、1 树得概念 20
1、树得定义 20
2.相关术语 20
3、2 二叉树 21
3、2、1 定义与性质 21
3、2、2 二叉树得存储 22
3、2、3 二叉树得遍历 23
3、2、4 线索二叉树 25
3、3 树与森林 29
3、3、1 树得存储结构 29
3、3、2 森林与二叉树得转换 30
3、3、3 树与森林得遍历 30
3、4 哈夫曼( Huffman)树与哈夫曼编码 31
第四章 图 32
4、1 图得概念 32
4、2 图得存储及基本操作 33
4、2、1 邻接矩阵 33
4、2、2 邻接表 33
4、3 图得遍历 35
4、3、1 深度优先搜索 35
4、3、2 广度优先搜索 35
4、4 图得基本应用 37
4、4、1 最小生成树 37
4、4、2 最短路径 37
4、4、3 拓扑排序 39
4、4、4 关键路径 40
第五章 查找 42
5、1 查找得基本概念 42
5、2 顺序查找法 43
5、3 折半查找法 44
5、4 动态查找树表 45
5、4、1 二叉排序树 45
5、4、2 平衡二叉树 47
5、4、3 B 树及其基本操作、 B+树得基本概念 49
5、5 散列表 51
5、5、2 常用得散列函数 51
5、5、3 处理冲突得方法 52
5、5、4 散列表得查找 52
5、5、5 散列表得查找分析 53
第六章 排序 54
6、1 插入排序 54
6、1、1 直接插入排序 54
6、1、2 折半插入排序 54
6、2 冒泡排序 55
6、3 简单选择排序 56
6、4 希尔排序 57
6、5 快速排序 58
6、6 堆排序 60
6、7 二路归并排序 62
6、8 基数排序 63
6、9 各种内部排序算法得比较 64
绪论
0、1 基本概念
1、数据结构
数据结构就是指互相之间存在着一种或多种关系得数据元素得集合。
数据结构就是一个二元组 Data_Structure ＝( D, R),其中, D 就是数据元素得有限集, R 就是D 上关系得有限集。
2、逻辑结构:就是指数据之间得相互关系。通常分为四类结构:
( 1)集合:结构中得数据元素除了同属于一种类型外,别无其它关系。
( 2)线性结构:结构中得数据元素之间存在一对一得关系。
( 3)树型结构:结构中得数据元素之间存在一对多得关系。
( 4)图状结构:结构中得数据元素之间存在多对多得关系。
3、存储结构:就是指数据结构在计算机中得表示,又称为数据得物理结构。通常由四种基本得存储方法实现:
( 1)顺序存储方式。数据元素顺序存放,每个存储结点只含一个元素。存储位置反映数据元素间得逻辑关系。存储密度大。但有些操作(如插入、删除)效率较差。
( 2)链式存储方式。每个存储结点除包含数据元素信息外还包含一组(至少一个)指针。指针反映数据元素间得逻辑关系。这种方式不要求存储空间连续,便于动态操作(如插入、删除等),但存储空间开销大(用于指针),另外不能折半查找等。
( 3)索引存储方式。除数据元素存储在一组地址连续得内存空间外,还需建立一个索引表,索引表中索引指示存储结点得存储位置(下标)或存储区间端点(下标)。
( 4)散列存储方式。通过散列函数与解决冲突得方法,将关键字散列在连续得有限得地址空间内,并将散列函数得值解释成关键字所在元素得存储地址。其特点就是存取速度快,只能按关键字随机存取,不能顺序存取,也不能折半存取。
2 算法与算法得衡量
1、算法就是对特定问题求解步骤得一种描述,就是指令得有限序列。其中每一条指令表示一个或多个操作。
算法具有下列特性:⑴有穷性⑵确定性⑶可行性⑷输入⑸输出。
算法与程序十分相似,但又有区别。程序不一定具有有穷性,程序中得指令必须就是机器可执行得,而算法中得指令则无此限制。算法代表了对问题得解,而程序则就是算法在计算机上得特定得实现。一个算法若用程序设计语言来描述,则它就就是一个程序。
2、算法得时间复杂度:以基本运算得原操作重复执行得次数作为算法得时间度量。一般情况下,算法中基本运算次数 T(n)就是问题规模 n(输入量得多少,称之为问题规模)得某个函数f(n),记作:
T(n) ＝ Ο(f(n));也可表示 T(n) ＝m(f(n)),其中 m 为常量。记号“O”读作“大 O”,它表示随问题规模 n 得增大,算法执行时间 T(n)得增长率与 f(n)得增长率相同。
注意:有得情况下,算法中基本操作重复执行得次数还随问题得输入数据集不同而不同。
常见得渐进时间复杂度有:
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n) ＜O(n!) ＜O(nn)。
3、算法得空间复杂度:就是对一个算法在运行过程中临时占用得存储空间大小得量度。只需要
分析除输入与程序之外得辅助变量所占额外空间。
原地工作:若所需额外空间相对于输入数据量来说就是常数,则称此算法为原地工作,空
间复杂度为 O(1)。
第一章 线性表
1、1 线性表得定义
线性表就是一种线性结构,在一个线性表中数据元素得类型就是相同得,或者说线性表就是由同一类型得数据元素构成得线性结构,定义如下:
线性表就是具有相同数据类型得n(n≥0)个数据元素得有限序列,通常记为:
(a1, a2, … ai-1, ai, ai+1, …an)
其中n为表长, n＝0 时称为空表。
需要说明得就是: ai为序号为 i 得数据元素( i=1,2,…,n),通常将它得数据类型抽象为ElemType, ElemType根据具体问题而定。
1、2 线性表得实现
1、2、1 线性表得顺序存储结构
1、顺序表
线性表得顺序存储就是指在内存中用地址连续得一块存储空间顺序存放线性表得各元素,用这种存储形式存储得线性表称其为顺序表。因为内存中得地址空间就是线性得,因此,用物理上得相邻实现数据元素之间得逻辑相邻关系就是既简单又自然得。
设a１得存储地址为Loc(a１),每个数据元素占d个存储地址,则第i个数据元素得地址为:
Loc(ai)=Loc(a１)+(i-1)*d 1≤i≤n
这就就是说只要知道顺序表首地址与每个数据元素所占地址单元得个数就可求出第i个数据元素得地址来,这也就是顺序表具有按数据元素得序号随机存取得特点。
线性表得动态分配顺序存储结构:
#define LIST_INIT_SIZE 100 //存储空间得初始分配量
#define LISTINCREMENT 10 //存储空间得分配增量
typedef struct{
ElemType *elem; //线性表得存储空间基址
int length; //当前长度
int listsize; //当前已分配得存储空间
}SqList;
2、顺序表上基本运算得实现
( 1)顺序表得初始化
顺序表得初始化即构造一个空表, 这对表就是一个加工型得运算, 因此, 将L设为引用参数,
首先动态分配存储空间,然后,将length置为0,表示表中没有数据元素。
int Init_SqList (SqList &L){
L、elem = (ElemType * )malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L、elem) exit (OVERFLOW); //存储分配失败
L、length=0;
L、 listsize = LIST_INIT_SIZE; //初始存储容量
return OK;
}
( 2)插入运算
线性表得插入就是指在表得第i(i得取值范围: 1≤i≤n+1)个位置上插入一个值为 x 得新元素,
插入后使原表长为 n得表:
(a1, a2, 、、、 , ai-1, ai, ai+1, 、、、 , an)
成为表长为 n+1 表:
(a1, a2, 、、、, ai-1, x, ai, ai+1, 、、、, an ) 。
顺序表上完成这一运算则通过以下步骤进行:
① 将ai～an 顺序向下移动,为新元素让出位置;(注意数据得移动方向:从后往前依次后移一个元素)
② 将 x 置入空出得第i个位置;
③ 修改表长。
int Insert_SqList (SqList &L, int i, ElemType x){
if (i < 1 || i > L、length+1) return ERROR; // 插入位置不合法
if (L、length >= L、listsize) return OVERFLOW; // 当前存储空间已满,不能插入
//需注意得就是,若就是采用动态分配得顺序表,当存储空间已满时也可增加分配
q = &(L、elem[i-1]); // q 指示插入位置
for (p = &(L、elem[L、length-1]); p >= q; --p)
*(p+1) = *p; // 插入位置及之后得元素右移
*q = e; // 插入e
++L、length; // 表长增1
return OK;
}
顺序表上得插入运算, 时间主要消耗在了数据得移动上, 在第i个位置上插入 x , 从 ai 到an 都要向下移动一个位置,共需要移动 n－i＋1个元素。
( 3)删除运算
线性表得删除运算就是指将表中第 i ( i 得取值范围为 : 1≤ i≤n)个元素从线性表中去掉,
删除后使原表长为 n 得线性表:
(a1, a2, 、、、 , ai-1, ai, ai+1, 、、、, an)
成为表长为 n－1 得线性表:
(a1, a2, 、、、 , ai-1, ai+1, 、、、 , an)。
顺序表上完成这一运算得步骤如下:
① 将ai+1～an 顺序向上移动;(注意数据得移动方向:从前往后依次前移一个元素)
② 修改表长。
int Delete_SqList (SqList &L;int i) {
if ((i < 1) || (i > L、length)) return ERROR; // 删除位置不合法
p = &(L、elem[i-1]); // p 为被删除元素得位置
e = *p; // 被删除元素得值赋给 e
q = L、elem+L、length-1; // 表尾元素得位置
for (++p; p <= q; ++p)
*(p-1) = *p; // 被删除元素之后得元素左移
--L、length; // 表长减1
return OK;
}
顺序表得删除运算与插入运算相同,其时间主要消耗在了移动表中元素上,删除第i个元素时,其后面得元素 ai+1～an 都要向上移动一个位置,共移动了 n-i 个元素,顺序表得插入、删除需移动大量元素 O(n);但在尾端插入、删除效率高 O(1)。
1、2、2 线性表得链式存储结构
1、2、2、1 单链表
1、链表表示
链表就是通过一组任意得存储单元来存储线性表中得数据元素得。为建立起数据元素之间得线性关系,对每个数据元素ai,除了存放数据元素得自身得信息 ai 之外,还需要与ai一起存放其后继 ai+1 所在得存储单元得地址,这两部分信息组成一个“结点”,结点得结构如图所示。
其中,存放数据元素信息得称为数据域,存放其后继地址得称为指针域。因此n个元素得线性表通过每个结点得指针域拉成了一个“链”,称之为链表。因为每个结点中只有一个指向后继得指针,所以称其为单链表。
线性表得单链表存储结构C语言描述下:
typedef struct LNode{
ElemType data; // 数据域
struct LNode *next; // 指针域
}LNode, *LinkList;
LinkList L; // L 为单链表得头指针
通常用“头指针”来标识一个单链表,如单链表L、单链表H等,就是指某链表得第一个结点得地址放在了指针变量 L、 H 中, 头指针为“NULL”则表示一个空表。
2、单链表上基本运算得实现
(1)建立单链表
单链表结点结构
data next
●头插法——在链表得头部插入结点建立单链表
链表与顺序表不同,它就是一种动态管理得存储结构,链表中得每个结点占用得存储空间不就是预先分配,而就是运行时系统根据需求而生成得,因此建立单链表从空表开始,每读入一个数据元素则申请一个结点,然后插在链表得头部。
LinkList CreateListF ( ){
LinkList L=NULL; //空表
LNode *s;
int x; //设数据元素得类型为int
scanf(＂%d＂,&x);
while (x!=flag) {
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
s->next=L; L=s;
scanf (＂%d＂,&x);
}
return L;
}
●尾插法——在单链表得尾部插入结点建立单链表
头插入建立单链表简单, 但读入得数据元素得顺序与生成得链表中元素得顺序就是相反得,若希望次序一致,则用尾插入得方法。因为每次就是将新结点插入到链表得尾部,所以需加入一个指针 r 用来始终指向链表中得尾结点,以便能够将新结点插入到链表得尾部。
初始状态, 头指针L=NULL, 尾指针 r=NULL; 按线性表中元素得顺序依次读入数据元素,不就是结束标志时,申请结点,将新结点插入到 r 所指结点得后面,然后 r 指向新结点(注意第一个结点有所不同)。
LinkList CreateListR1 ( ){
LinkList L=NULL;
LNode *s,*r=NULL;
int x; //设数据元素得类型为int
scanf(＂%d＂,&x);
while (x!=flag) {
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
if (L==NULL) L=s; //第一个结点得处理
else r->next=s; //其它结点得处理
r=s; //r 指向新得尾结点
scanf(＂%d＂,&x);
}
if ( r!=NULL) r->next=NULL; //对于非空表,最后结点得指针域放空指针
return L;
}
在算法CreateListR1中,第一个结点得处理与其它结点就是不同得,原因就是第一个结点加入时链表为空,它没有直接前驱结点,它得地址就就是整个链表得指针,需要放在链表得头指针变量中;而其它结点有直接前驱结点,其地址放入直接前驱结点得指针域。 “第一个结点”得问题在很多操作中都会遇到,如在链表中插入结点时,将结点插在第一个位置与其它位置就是不同得,在链表中删除结点时,删除第一个结点与其它结点得处理也就是不同得,等等。
为了方便操作,有时在链表得头部加入一个“头结点”,头结点得类型与数据结点一致,标识链表得头指针变量L中存放该结点得地址,这样即使就是空表,头指针变量L也不为空了。
头结点得加入使得“第一个结点”得问题不再存在,也使得“空表”与“非空表”得处理成为一致。
头结点得加入完全就是为了运算得方便,它得数据域无定义,指针域中存放得就是第一个数据结点得地址,空表时为空。
尾插法建立带头结点得单链表,将算法CreateListR1改写成算法CreateListR2形式。
LinkList CreateListR2( ){
LinkList L=(LNode *)malloc(sizeof(LNode));
L->next=NULL; //空表
LNode *s,*r=L;
int x; //设数据元素得类型为int
scanf(＂%d＂,&x);
while (x!=flag) {
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s; //r 指向新得尾结点
scanf(＂%d＂,&x);
}
r->next=NULL;
return L;
}
因此,头结点得加入会带来以下两个优点:
第一个优点:由于开始结点得位置被存放在头结点得指针域中,所以在链表得第一个位置上得操作就与在表得其它位置上得操作一致,无需进行特殊处理;
第二个优点:无论链表就是否为空,其头指针就是指向头结点在得非空指针(空表中头结点得指针域为空),因此空表与非空表得处理也就统一了。在以后得算法中不加说明则认为单链表就是带头结点得。
(2)查找操作
●按序号查找 Get_LinkList(L,i)
从链表得第一个元素结点起,判断当前结点就是否就是第i个,若就是,则返回该结点得指针,否则继续后一个,表结束为止,没有第ｉ个结点时返回空。
LNode * Get_LinkList(LinkList L, int i); {
LNode * p=L;
int j=0;
while (p->next !=NULL && j<i ){
p=p->next; j++;
}
if (j==i) return p;
else return NULL;
}
(3)插入运算
●后插结点:设p指向单链表中某结点, s指向待插入得值为x得新结点,将*s插入到*p得后面,插入示意图如图所示。

操作如下:
①s->next=p->next;
②p->next=s;
注意:两个指针得操作顺序不能交换。
(4)删除运算
●删除结点
设p指向单链表中某结点,删除*p。操作过程如图。要实现对结点*p得删除,首先要找到*p得前驱结点*q,然后完成指针得操作即可。

操作如下:①q=L;
while (q->next!=p)
q=q->next; //找*p得直接前驱
②q->next=p->next;
free(p);
因为找*p前驱得时间复杂度为O(n),所以该操作得时间复杂度为O(n)
通过上面得基本操作我们得知:
(1) 单链表上插入、删除一个结点,必须知道其前驱结点。
(2) 单链表不具有按序号随机访问得特点,只能从头指针开始一个个顺序进行。
1、2、2、2 循环链表
对于单链表而言,最后一个结点得指针域就是空指针,如果将该链表头指针置入该指针域,则使得链表头尾结点相连,就构成了单循环链表。
在单循环链表上得操作基本上与非循环链表相同,只就是将原来判断指针就是否为 NULL 变为就是否就是头指针而已,没有其它较大得变化。
对于单链表只能从头结点开始遍历整个链表,而对于单循环链表则可以从表中任意结点开始遍历整个链表,不仅如此,有时对链表常做得操作就是在表尾、表头进行,此时可以改变一下链表得标识方法,不用头指针而用一个指向尾结点得指针 R 来标识,可以使得操作效率得以提高。
1、2、2、3 双向链表
单链表得结点中只有一个指向其后继结点得指针域 next,因此若已知某结点得指针为 p,其后继结点得指针则为 p->next ,而找其前驱则只能从该链表得头指针开始,顺着各结点得next 域进行,也就就是说找后继得时间性能就是 O(1),找前驱得时间性能就是 O(n),如果也希望找前驱得时间性能达到 O(1),则只能付出空间得代价:每个结点再加一个指向前驱得指针域,结点得结构为如图所示,用这种结点组成得链表称为双向链表。

线性表得双向链表存储结构C语言描述下:
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
与单链表类似,双向链表通常也就是用头指针标识,也可以带头结点。
( 1)双向链表中结点得插入:设 p 指向双向链表中某结点, s 指向待插入得值为 x 得新结点,将*s 插入到*p 得前面,插入示意图如所示。

操作如下:
① s->prior=p->prior;
② p->prior->next=s;
③ s->next=p;
④ p->prior=s;
指针操作得顺序不就是唯一得,但也不就是任意得,操作①必须要放到操作④得前面完成,否则*p 得前驱结点得指针就丢掉了。
( 2)双向链表中结点得删除:设 p 指向双向链表中某结点,删除*p。操作示意图如图所示。
操作如下:
①p->prior->next=p->next;
②p->next->prior=p->prior;
free(p);

1、2、2、4 顺序表与链表得比较
总之,两种存储结构各有长短,选择那一种由实际问题中得主要因素决定。通常“较稳定”
得线性表选择顺序存储,而频繁做插入删除得即动态性较强得线性表宜选择链式存储。
第二章 栈、队列与数组
2、1 栈
2、1、1 栈得定义
栈就是限制在表得一端进行插入与删除得线性表。允许插入、删除得这一端称为栈顶,另一个固定端称为栈底。当表中没有元素时称为空栈。
2、1、2 栈得存储实现与运算实现
栈就是运算受限得线性表,线性表得存储结构对栈也就是适用得,只就是操作不同而已。
利用顺序存储方式实现得栈称为顺序栈。与线性表类似,栈得动态分配顺序存储结构如下:
#define STACK_INIT_SIZE 100 //存储空间得初始分配量
#define STACKINCREMENT 10 //存储空间得分配增量
typedef struct{
SElemType *base; //在栈构造之前与销毁之后, base 得值为 NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配得存储空间
}SqStack;
需要注意,在栈得动态分配顺序存储结构中, base 始终指向栈底元素,非空栈中得 top始终在栈顶元素得下一个位置。
下面就是顺序栈上常用得基本操作得实现。
( 1)入栈:若栈不满,则将 e 插入栈顶。
int Push (SqStack &S, SElemType e) {
if (S、top-S、base>=S、stacksize)
{……} //栈满,追加存储空间
*S、top++ = e; //top 始终在栈顶元素得下一个位置
return OK;
}
( 2)出栈:若栈不空,则删除 S 得栈顶元素,用 e 返回其值,并返回 OK,否则返回ERROR。
int Pop (SqStack &S, SElemType &e) {
if (S、top==S、base) return ERROR;
e = *--S、top;
return OK;
}
出栈与读栈顶元素操作,先判栈就是否为空,为空时不能操作,否则产生错误。通常栈空常作为一种控制转移得条件。
2、1、3 栈得应用举例
由于栈得“先进先出”特点,在很多实际问题中都利用栈做一个辅助得数据结构来进行求解,下面通过几个例子进行说明。
1.数制转换
十进制数 N 与其她 d 进制数得转换就是计算机实现计算得基本问题,其解决方法很多,其中一个简单算法基于下列原理:

假设现要编制一个满足下列要求得程序:对于输入得任意一个非负十进制整数,打印输出与其等值得八进制数。由于上述计算过程就是从低位到高位顺序产生八进制数得各个数位,而打印输出,一般来说应从高位到低位进行,恰好与计算过程相反。因此,若将计算过程中得到得八进制数得各位顺序进栈,则按出栈序列打印输出得即为与输入对应得八进制数。
算法思想:当 N>0 时重复( 1),( 2)
( 1)若 N≠0,则将 N % r 压入栈 s 中 ,执行( 2) ;若 N=0,将栈 s 得内容依次出栈,算法结束。
( 2)用 N / r 代替 N。
void conversion () {
InitStack(S); // 构造空栈
scanf ("%d",N);
while (N) {
Push(S, N % 8);
N = N/8;
}
while (!StackEmpty(S)) {
Pop(S,e);
printf ( "%d", e );
}}
2、、表达式求值
表达式求值就是程序设计语言编译中一个最基本得问题,它得实现也就是需要栈得加入。下面得算法就是由运算符优先法对表达式求值。在此仅限于讨论只含二目运算符得算术表达式。
( 1)中缀表达式求值:
中缀表达式:每个二目运算符在两个运算量得中间,假设所讨论得算术运算符包括: + 、- 、 *、 /、 %、 ^(乘方)与括号()。
设运算规则为:
.运算符得优先级为:() ——> ^ ——>＊、 /、 %——> +、 - ;
.有括号出现时先算括号内得,后算括号外得,多层括号,由内向外进行;
.乘方连续出现时先算最右面得。
表达式作为一个满足表达式语法规则得串存储,如表达式“3*2^( 4+2*2-１*3) -5”,它得得求值过程为:自左向右扫描表达式,当扫描到 3*2 时不能马上计算,因为后面可能还有更高得运算,正确得处理过程就是:需要两个栈:对象栈 s1 与运算符栈 s2。当自左至右扫描表达式得每一个字符时,若当前字符就是运算对象,入对象栈,就是运算符时,若这个运算符比栈顶运算符高则入栈,继续向后处理,若这个运算符比栈顶运算符低则从对象栈出栈两个运算量,从运算符栈出栈一个运算符进行运算,并将其运算结果入对象栈,继续处理当前字符,直到遇到结束符。
中缀表达式表达式 “3*2^( 4+2*2-１*3) -5”求值过程中两个栈得状态情况见图所示。

图 中缀表达式 3*2^( 4+2*2-1*3) -5 得求值过程
为了处理方便,编译程序常把中缀表达式首先转换成等价得后缀表达式,后缀表达式得运算符在运算对象之后。在后缀表达式中,不在引入括号,所有得计算按运算符出现得顺序,严格从左向右进行,而不用再考虑运算规则与级别。
中缀表达式“3*2^( 4+2*2-1*3) -5 ”得后缀表达式为: “32422*+13*-^*5-”。
( 2)后缀表达式求值
计算一个后缀表达式,算法上比计算一个中缀表达式简单得多。这就是因为表达式中即无括号又无优先级得约束。具体做法:只使用一个对象栈,当从左向右扫描表达式时,每遇到一个操作数就送入栈中保存,每遇到一个运算符就从栈中取出两个操作数进行当前得计算,然后把结果再入栈,直到整个表达式结束,这时送入栈顶得值就就是结果。
( 3) 中缀表达式转换成后缀表达式:
将中缀表达式转化为后缀表达示与前述对中缀表达式求值得方法完全类似,但只需要运算符栈,遇到运算对象时直接放后缀表达式得存储区,假设中缀表达式本身合法且在字符数组 A 中,转换后得后缀表达式存储在字符数组 B 中。具体做法:遇到运算对象顺序向存储后缀表达式得 B 数组中存放,遇到运算符时类似于中缀表达式求值时对运算符得处理过程,但运算符出栈后不就是进行相应得运算,而就是将其送入 B 中存放。具体算法在此不再赘述。
3.栈与递归
在高级语言编制得程序中,调用函数与被调用函数之间得链接与信息交换必须通过栈进行。当在一个函数得运行期间调用另一个函数时,在运行该被调用函数之前,需先完成三件事:
( 1)将所有得实在参数、返回地址等信息传递给被调用函数保存;
( 2)为被调用函数得局部变量分配存储区;
( 3)将控制转移到被调用函数得入口。
从被调用函数返回调用函数之前,应该完成:
( 1)保存被调函数得计算结果;
( 2)释放被调函数得数据区;
( 3)依照被调函数保存得返回地址将控制转移到调用函数。
多个函数嵌套调用得规则就是:后调用先返回,此时得内存管理实行“栈式管理”。
递归函数得调用类似于多层函数得嵌套调用,只就是调用单位与被调用单位就是同一个函数而已。在每次调用时系统将属于各个递归层次得信息组成一个活动记录( ActivaTion Record),这个记录中包含着本层调用得实参、返回地址、局部变量等信息,并将这个活动记录保存在系统得“递归工作栈”中,每当递归调用一次,就要在栈顶为过程建立一个新得活动记录,一旦本次调用结束,则将栈顶活动记录出栈,根据获得得返回地址信息返回到本次得调用处。
将递归程序转化为非递归程序时常使用栈来实现。
2、2 队列
2、2、1 队列得定义及基本运算
栈就是一种后进先出得数据结构,在实际问题中还经常使用一种“先进先出”得数据结构:即插入在表一端进行,而删除在表得另一端进行,将这种数据结构称为队或队列,
把允许插入得一端叫队尾(rear) ;把允许删除得一端叫队头(front)。
2、2、2 队列得存储实现及运算实现
与线性表、栈类似,队列也有顺序存储与链式存储两种存储方法。
1.顺序队列
循环队列得类型定义如下:
#define MAXQSIZE 100 //最大队列长度
typedef struct {
QElemType *base; //动态分配存储空间
int front; //头指针,若队列不空,指向队列头元素
int rear; //尾指针,若队列不空,指向队列尾元素得下一个位置
} SqQueue;
下面就是循环队列上基本操作得实现。

( 3)求循环队列元素个数:
int QueueLength( SqQueue Q) {
return (Q、rear-Q、front+MAXQSIZE) %MAXQSIZE;
}
2.链队列
链式存储得队称为链队列。与链栈类似,用单链表来实现链队列,根据队得先进先出原
则,为了操作上得方便,分别需要一个头指针与尾指针。

定义一个指向链队列得指针: LinkQueue Q;
下面就是链队列得基本运算得实现。
( 1)入队
int EnQueue (LinkQueue &Q, QElemType e) {
QNode *p;
p = ( QNode *) malloc( sizeof( QNode)) ;
p->data = e;
p->next = NULL;
Q、rear->next = p;
Q、rear = p;
return OK;
}
( 2)出队
int DeQueue (LinkQueue &Q, QElemType &e) {
if (Q、front == Q、rear) return ERROR; //队空,出队失败
p = Q、front->next;
e = p->data; //队头元素放 e 中
Q、front->next = p->next;
if(Q、rear==p) Q、rear= Q、front; //只有一个元素时,此时还要修改队尾指针
free (p);
return OK;
}
3.除了栈与队列之外,还有一种限定性数据结构就是双端队列。
( 1)双端队列:可以在双端进行插入与删除操作得线性表。
( 2)输入受限得双端队列:线性表得两端都可以输出数据元素,但就是只能在一端输入数据元素。
( 3)输出受限得双端队列:线性表得两端都可以输入数据元素,但就是只能在一端输出数据元素。
2、3 特殊矩阵得压缩存储
2、3、1 数组
数组可以瞧作线性表得推广。数组作为一种数据结构其特点就是结构中得元素本身可以就是具有某种结构得数据,但属于同一数据类型,数组就是一个具有固定格式与数量得数据有序集,每一个数据元素有唯一得一组下标来标识,因此,在数组上不能做插入、删除数据元素得操作。通常在各种高级语言中数组一旦被定义,每一维得大小及上下界都不能改变。
现在来讨论数组在计算机中得存储表示。通常,数组在内存被映象为向量,即用向量作为数组得一种存储结构,这就是因为内存得地址空间就是一维得,数组得行列固定后,通过一个映象函数,则可根据数组元素得下标得到它得存储地址。
对于一维数组按下标顺序分配即可。对多维数组分配时,要把它得元素映象存储在一维存储器中,一般有两种存储方式:一就是以行为主序(或先行后列)得顺序存放,即一行分配完了接着分配下一行。另一种就是以列为主序(先列后行)得顺序存放,即一列一列地分配。
以行为主序得分配规律就是:最右边得下标先变化,即最右下标从小到大,循环一遍后,右边第二个下标再变, …,从右向左,最后就是左下标。以列为主序分配得规律恰好相反:最左边得下标先变化,即最左下标从小到大,循环一遍后,左边第二个下标再变, …,从左向右,最后就是右下标。
设有 m×n 二维数组 Amn,下面我们瞧按元素得下标求其地址得计算:
以“以行为主序”得分配为例:设数组得基址为 LOC(a11),每个数组元素占据 d 个地址单元,那么 aij 得物理地址可用一线性寻址函数计算:
LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * d
这就是因为数组元素 aij 得前面有 i-1 行,每一行得元素个数为 n,在第 i 行中它得前面还有j-1 个数组元素。
在 C 语言中,数组中每一维得下界定义为 0,则:
LOC(aij) = LOC(a00) + ( i*n + j ) * d
推广到一般得二维数组: A[c1、、d1] [c2、、d2],则 aij 得物理地址计算函数为:
LOC(aij)=LOC(a c1 c2)+( (i- c1) *( d2 - c2 + 1)+ (j- c2) )d
2、3、2 特殊矩阵
对于一个矩阵结构显然用一个二维数组来表示就是非常恰当得, 矩阵在这种存储表示之下,可以对其元素进行随机存取,各种矩阵运算也非常简单,并且存储得密度为 1。但就是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量得零元素得情况下,比如常见得一些特殊矩阵,如三角矩阵、对称矩阵、对角矩阵、稀疏矩阵等,从节约存储空间得角度考虑,这种存储就是不太合适得,瞧起来存储密度仍为 1,但实际上占用了许多单元去存储重复得非零元素或零元素,这对高阶矩阵会造成极大得浪费,为了节省存储空间,我们可以对这类矩阵进行压缩存储:即为多个相同得非零元素只分配一个存储空间;对零元素不分配空间。
1、对称矩阵
对称矩阵得特点就是:在一个 n 阶方