算法与数据结构课程记录

新学期要学习算法与数据结构的课程,在此开篇,用于记录一些学习内容,以备考试。

内容一般不包括实际代码,算法采用文字或类C进行描述

如何理解数据结构?

数据结构需要分为两个层次去理解:

1
2
逻辑结构——从具体问题抽象出的数学模型
存储结构——数据元素及其关系在计算机中的存储方式

逻辑结构

分为四类基本的逻辑结构,集合、线性、树、图。

存储结构

分为两种:顺序存储结构、链式存储结构。

顺序存储结构例子:数组

链式存储结构例子:链表(每一个元素都会存储自身数据以及其他数据的地址)

抽象数据类型(ADT)

可以由三元组来表示 $ \text{ADT}= (D,R,P) $

$ D $ 表示数据对象

$ R $ 表示D上的关系集合

$ P $ 表示D上的数据操作

定义方式:

1
2
3
4
5
ADT抽象数据类型名{
数据对象:(数据元素集合)
数据关系:(数据关系二元组结合)
基本操作:(操作函数的罗列)
};ADT抽象数据类型名;

算法

算法是一个有穷的指令集,是一个用来完成特定任务规定的一个运算序列。

算法评价

评价维度:正确性,可读性,健壮性,高效性

算法效率

时间复杂度,用该算法执行消耗的时间来进行度量,可采取事后统计或事前分析估计。

事后统计

利用计算机内的计时功能,但由于计算机运行消耗时间由:算法选用策略、问题规模、程序语言、编译器生产的机器代码质量、指令执行速度,五个方面来共同决定

事前分析估计

针对算法中语句执行次数进行估计,而不是真实的运行时间。

算法的规模:求解问题的输入量,用$ n $来表示。而决定算法规模$ n $复杂性的函数用$ f(n) $来表示,一般是算法中最大的语句频度。

时间复杂度:是算法的执行时间,也是$ n $的函数,用$ T(n) $来表示

当问题规模$ n \rightarrow \infty $时,$ T(n) $的数量级的增长率和$ f(n) $的增长率相同,因此可以说:

所以,算法的时间复杂度通常是由最深嵌套层内的语句的频度决定的。

算法的时间复杂度有如下几种类型:

类型 表示
常数阶 $ O(1) $
对数阶 $ O(log_2(n)) $
线性阶 $ O(n) $
线性对数阶 $ O(n log_2(n)) $
平方阶 $ O(n^2) $
立方阶 $ O(n^3) $
—— ——
$ K $次方阶 $ O(n^K) $
指数阶 $ O(2^n) $

分析实例

例子一:

1
2
3
4
5
6
7
8
for( i = 1; i <= n; i++){
for( j = 1; j <= n; j++){
c[i][j] = 0;
for( k = 1; k <= n; k++){
c[i][j] = c[i][j] + a[i][k] * b[l][j];
}
}
}

例子二:

1
2
3
4
5
6
7
for( i = 1; i <= n; i++){
for( j = 1; j <= i; j++){
for( k = 1; k <= j; k++){
x = x + 1;
}
}
}

例子三:

1
2
3
4
i = 1;
while(i<=n){
i = i * 2;
}

取最大值

$T(n)$总结

当时间复杂度大于立方阶 $ O(n^3) $ 之后,一旦进入指数阶,算法所需时间将与方阶非常悬殊。应当在设计算法时避免这类情况。

注:指数阶内算法时间复杂度: $ O(2^n) \lt O(n!) \lt O(n^n) $

算法的空间复杂度(非重点)

算法所需的存储空间的度量,记作:$ S(n) = O(f(n)) $

占据的空间包括:IO,指令,常数,变量等,以及辅助空间。

如果输入数据所占空间与算法无关,则无需考虑。

线性表

首先抛出问题,什么是线性表?

一个线性表是n个具有相同特性的数据元素的有限序列

在一系列数据元素中,如:

则有 $a1$为线性表起点, $a_n$为线性表终点,可把$a{i-1}$称为$ai$ 的直接前趋,把$a{i+1}$称为$a_i$ 的直接后继。$n$为表长,$n =0$ 可称为空表。

逻辑特性

对于一个非空线性表来说满足以下逻辑结构特性:

存在唯一一个被称为“第一个”的数据元素

存在唯一一个被称为“最后一个”的数据元素

除第一个之外,结构中的每一个数据元素均只有一个前趋

除最后一个之外,结构中的每一个数据元素均只有一个后继

线性表特性:

同一性:由同类数据元素组成

有穷性:由有限个数据元素组成

有序性:相邻元素之间存在序偶关系

线性表是一种比较常见的数据结构,如矩阵、数组,字符串、堆栈,队列都符合线性表特性。

抽象数据类型定义

数据对象:$ D = { a_i | a\in{ElemSet}, i =1,2,\cdots,n,n \geq 0 } $,

数据关系:$ R = { | a_{i-1},a_i \in D, i = 2, \cdots , n } $

基本操作

初始化线性表,销毁线性表,清空线性表,求线性表的长度,判断是否为空,获取线性表中某个数据元素内容,检索值为e的数据元素,在线性表中插入元素,在线性表中删除元素,获取前趋元素,获取后继元素。

补充:C语言的内存操作函数

stdlib.h中:

malloc(m);开辟m字节长度的地址空间,并返回首地址;

sizeof(x)计算变量x的长度;

free(p)释放指针p所指的变量内存空间(彻底删除);

new 类型名 T (初值列表)申请用于存放T类型对象的内存空间,并根据初值列表赋初值,如失败返回NULL

delete p释放指针p指向的内存,和new一起使用;

线性表的存储

顺序存储

顺序存储,每一个元素在内存中连续相邻,可称为顺序表,如数组。

这种方式可称为随机存取结构,即可以随时读取线性表中的任何一个元素。

C语言描述

1
2
3
4
5
6
#define MAXSIZE 100
typedef struct{
ElemType *elem;
int length
}SqList;
SqList L;

那么在连续内存中,前一部分均为元素,末尾内存区域存储表长。

顺序表基本操作

本节描述,基于以下定义:

1
2
3
4
5
6
#define MAXSIZE 100
typedef struct{
ElemType *elem;
int length
}SqList;
SqList L;
构造
1
2
3
4
5
6
7
8
Status InitList_Sq(SqList &L){
L.elem = new ElemType[MAXSIZE];
if(!L.elem){
exit(OVERFLOW);
}
L.length = 0;
return OK;
}
释放
1
2
3
4
5
void DestoryList(SqList &L){
if(L.elem){
delete(L.elem);
}
}
清空
1
2
3
void ClearList(SqList &L){
L.lenth = 0;
}
顺序表长度
1
2
3
int GetLength(SqList L){
return L.length;
}
是否为空
1
2
3
4
5
6
int IsEmpty(SqList L){
if (L.length == 0)
return 1;
else
return 0;
}
元素查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//获取相应位置的元素内容
int GetElem(SqList L, int i, ElemType &e){
if (i<1 || i>L.length)
return ERROR;
e = L.elem[i-1];
return OK;
}
//根据指定数据进行查找,返回位置。时间复杂度为O(n)
int LocateElem(SqList L, ElemType e){
for (int i = 0; i < L.length; i++){
if (L.elem[i] == e){
return i + 1;
}
}
return 0;
}
元素插入

算法描述如下:

1.将 $ a_i \sim a_n $ 顺序向下移动,为新元素让出位置。

2.将 $x$ 置入空出的第 $i$个位置

3.表长自增

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status ListInsert_Sq(SqList &L, int i, ElemType e){
if(i < 1 || i > L.length + 1){
return ERROR;
}
if(L.length == MAXSIZE){
return ERROR;
}
for(j = L.length; j >= i; j--){
L.elem[j+1] = L.elem[j];
}
L.elem[i-1] = e;
L.length++;
return OK;
}

在这个插入代码中,时间开销主要在移动元素的操作,需要遍历一部分元素,若插入在表尾,执行速度较快,反之几乎需要遍历所有元素。则平均移动次数为

删除元素

如果能理解插入元素,那么删除元素就比较好理解了。

1
2
3
4
5
6
7
8
9
10
11
Status ListDelete_Sq(SqList &L, int i, ElemType e){
if(i < 1 || i > L.length){
return ERROR;
}
e = L.elem[i-1];
for(j = i; j <= L.length; j++){
L.elem[j-1] = L.elem[j];
}
--L.length;
return OK;
}

空间复杂度:

顺序表优缺点

  • 优点
    • 存储密度大
    • 可以随机存取表中的任意元素
  • 缺点
    • 在插入、删除某一元素,需要大量移动元素。
    • 浪费存储空间(申请了内存但不一定全部使用)
    • 属于静态存储形式,数据元素的个数不可以自由扩充。

链式存储

1.用一组任意的存储单元存放线性表的数据元素(这组内存单元可以连续,也可以不连续)

2.为表示数据元素之间的逻辑关系,还需要有存储一个指示后继的信息——指针

3.由数据域和指针域构成的数据元素的存储映像,成为节点(node)。

C语言描述

1
2
3
4
5
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode, *LinkList;
//*LinkList为LNode类型的指针

术语

术语 解释
结点 数据元素的存储映像,由数据域和指针域两部分组成
链表 n个结点由指针链组成一个链表
他是线性表的链式存储映像,成为线性表的链式存储结构。
单链表 结点只有一个指针域的链表,称为单链表或线性链表。
双链表 结点有两个指针域的链表。
循环链表 首尾相接的链表
头指针 指向链表中第一个结点的指针
首元结点 指链表中存储第一个数据元素$a_1$的一个结点,数据域内只放空表标志和表长等信息。

无头结点时,初始指针指向第一个元素地址。可以引入头结点来存储一些信息。如:当头结点的指针域为空时表示空表。以便首元结点处理,以及统一空表非空表的处理。

头结点的数据域可以为空,也可以存放线性表的长度等附加信息,但此结点不能计入链表长度值。

结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻。

但在访问时只能通过头指针进入链表,并通过向后遍历的方式进行寻找。

这种方法也成为顺序存取法

优缺点

  • 优点
    • 元素个数可以随意扩充
    • 插入删除等操作无需移动数据,只需修改指针域即可
  • 缺点
    • 存储密度较小,需要额外存储指针域
    • 存取效率不高,顺序存取,存取时必须从第一个结点开始向后遍历。

基本操作

本节描述,基于以下定义:

1
2
3
4
5
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode, *LinkList;
//*LinkList为LNode类型的指针
构造

1.生成新结点为头结点,用头指针L指向头结点

2.头结点的指针域置空

1
2
3
4
5
Stutus InitList_L(LinkList &L){
L = new LNode;
L->next = NULL;
return OK;
}
释放

基本思想就是从头向后遍历。

1
2
3
4
5
6
7
8
9
Status DestoryList_L(LinkList &L){
LinkList p;
while(L){
p = L;
L = L->next;
delete p;
}
return OK;
}
清空
1
2
3
4
5
6
7
8
9
10
11
Status Clearist(LinkList &L){
LinkList p,q;
p = L->next;
while(){
q = p;
p = p->next;
delete q;
}
L->next = NULL;
return OK;
}
求表长
1
2
3
4
5
6
7
8
9
10
int ListLength_L(LinkList L){
LinkList p;
p = L->next;
i = 0;
while(p){
i++;
p = p->next;
}
return i;
}
判断空
1
2
3
4
5
6
7
int ListEmpty(LinkList L){
if(L->next){
return 0;
}else{
return 1;
}
}
元素查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//按位置查找
Stutus GetElem_L(LinkList L,int i, ElemType &e){
p = L->next;
j = 1;
while(p && j < i){
p = p->next;
++j;
}
if(!p || j>i){
return ERROR;
}
e = p->data;
return OK;
}
//按值查找
LNode *LocateElem_L(LinkList L, ElemType e){
p = L->next;
while(p && p->data!=e){
p = p->next;
}
return p;
}
元素插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//指定位置
Status ListInsert_L(LinkList &L, int i, ElemType e){
p = L; j = 0;
while( p && i < i-1 ){ //达到目标位置即退出循环
p = p->next;
++j;
}
if(!p || j >i-1){
return ERROR;
}
s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
//前插法
void CreatList_F(LinkList &L, int n){
L = new LNode;
L->next = NULL; //初始化
for(i=n;i>0;--i){
cin >> p->data;
p->next = L->next; //插入到表头
L->next = p;
}
}
//尾插法
void CreatList_F(LinkList &L, int n){
L = new LNode;
L->next = NULL; //初始化
r = L;
for(i=n;i>0;--i){
cin >> p->data;
p->next = NULL; //插入到表尾
r->next = p;
r = p;
}
}
元素删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Status ListDelete_L(LinkList &L, int i, ElemType &e){
p = L;
j = 0;
while(p->next && j <i-1){ //找到目标位置
p = p->next;
j++;
}
if(!(p->next) || j>i-1){ //判断目标位置状态
return ERROR;
}
q = p->next; //存取待删对象地址
p->next = q->next;
e = q->data;
delete q; //释放目标结点
return OK;
}

循环链表

表中的最后一个结点的指针域指向头结点,整个链表形成一个环。为了使操作实现方便,可以在循环单链表中设置头结点,这样空循环链表仅由一个自成循环的头结点表示。

合并

1
2
3
B->next = A->next;
p = B->next->next;
A->next = p;

双向链表

1
2
3
4
5
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode, *DuLinkList;

插入

1
2
3
4
5
6
7
8
9
10
11
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){
if(!(p=GetElemP_DuL(L,i))){
return ERROR;
}
s = new DuLNode;
s->data = e;
s->prior = p->prior;
s->next = p;
p->prior = s;
return OK;
}

删除

1
2
3
4
5
6
7
8
9
10
Status ListDelete_DuL(DuLinkList &L, int i, ElemType e){
if(!(p=GetElemP_DuL(L,i))){
return ERROR;
}
e = p->data;
e->prior->next = p->next;
p->next->prior = p->prior;
delete p;
return OK;
}

线性表应用(合并)

1
2
3
4
5
6
7
8
9
10
void union(List &La, List Lb){ //无序顺序表合并,相同元素合并。
La_len = ListLength(La);
Lb_len = ListLength(Lb);
for(i=1;i<=Lb_len;i++){
GetElem(Lb,i,e);
if(!LocateElem(La,e)){
ListInsert(&La,++La_len,e);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void MergeList_Sq( SqList La, SqList Lb, SqList &Lc ) {// 有序顺序表合并
pa = La.elem;
pb = Lb.elem;
Lc.length = La.length + Lb.length;
Lc.elem = new ElemType[Lc.length];
pc = Lc.elem;
pa_last = La.elem + La.length -1;
pb_last = Lb.elem + Lb.length -1;
while(pa<=pa_last && pb<=pb_last){
if(*pa<=*pb){
*pc++ = *pa++;
}else{
*pc++ = *pb++;
}
while(pa<=pa_last){
*pc++ = *pa;
}
while(pb<=pb_last){
*pc++ =*pb++;
}

}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){// 有序链表合并
pa = La->next;
pb = Lb->next;
pc = Lc = La; //用La头结点作为Lc新表的头结点
while(pa && pb){
if(pa->data<=pb->data){
pc->next = pa;
pc = pa;
pa = pa->next; //pa后移
}else{
pc->next = pb;
pc = pb;
pb = pb->next; //pb后移
}
}
pc->next = pa ? pa : pb; //任意一条表遍历完成后 剩余表直接加入Lc末尾
delete Lb; //释放结点(重要)
}

栈和队列

栈和队列,可以视作一种限定性的线性表结构。

对于栈,他只可以在一端进行插入和删除操作。

对于队列,他只可以在一端进行插入,另一端进行删除。

栈只能在表的一端(栈顶-最后元素)进行插入和删除运算的线性表

相关概念有:栈顶,栈底,栈空,进栈,出栈。

进行运算时,符合后进先出准则

逻辑结构

  • 与线性表相同,为一对一关系
  • 受限的线性表,遵循先进后出(FILO)原则
  • 基本操作:入栈、出栈,读栈顶元素,建栈,判断栈满、栈空。

存储结构

顺序栈、链栈均可,常见使用顺序栈。

抽象数据类型定义

数据对象:$ D={ a_i | a\in{ElemSet}, i =1,2,\cdots,n,n \geq 0 } $, (类似线性表)

数据关系:$R={ | a_{i-1},a_i \in D, i = 2, \cdots , n, 约定 a_n为栈顶, a_1为栈底}$

基本操作

1
2
3
4
5
6
7
8
9
InitStack(&S); //构造空栈
DestoryStack(&S);
ClearStack(&S);
StackEmpty(&S);
StackLength(&S);
GetTop(S, &S); //得到栈顶
Push(&S, e);
Pop(&S, e); //出栈
StackTraverse(S); //遍历

顺序栈

利用一组地址连续的存储单元一次存放自栈顶的数据元素

我们首先要确定,数据哪一端作为栈底,一般使用第一个元素作为栈底。同时也要一个top指针来指示栈顶元素在数组中的位置。

栈空时出栈,则下溢。栈满时入栈,则上溢。

结构定义
1
2
3
4
5
6
7
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
构造-InitStack
1
2
3
4
5
6
7
8
9
Status InitStack(SqStack &S){//构造一个空栈S
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base){
exit(OVERFLOW); //存储分配失败
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
} //InitStack
得栈顶-GetTop
1
2
3
4
5
6
7
8
Status GetTop(SqStack S, SElemType &e){ 
//若栈不空,则用e返回S的栈顶元素,并返回OK
if (S.top == S.base){ // 空栈
return ERROR;
}
e = *(S.top-1); //返回非空栈中栈顶元素
return OK;
} //GetTop
Push 入栈
1
2
3
4
5
6
7
Status Push(SqStack &S, SElemType e) {//插入元素e为新的栈顶元素
if(S.top-S.base>=S.stacksize){//栈满
return ERROR;
}
*(S.top++) = e;
return OK;
} //Push
Pop 出栈
1
2
3
4
5
6
7
8
9
Status Pop(Stack &S, ElemType &e){ 
//栈不空,删除S的栈顶元素,用e返回其值,并返回OK;
//否则返回ERROR
if (S.top == S.base){ //空栈
return ERROR;
}
e= *(--S.top); //返回非空栈中栈顶元素
return OK;
} //Pop

链栈

为便于操作,采用带头结点的单链表实现栈。因为栈的插入和删除操作仅限制在表头位置进行,所以链表的表头指针就作为栈顶指针。

结构定义
1
2
3
4
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode, *LinkStack;
初始化
1
2
3
4
Status InitStack(LinkStack &s){
s=NULL;
return ok;
}
入栈
1
2
3
4
5
6
7
8
9
Status Push(LinkStack &S, SElemType e)
{
LinkStackNode *p;
p=(LinkStack *)malloc(sizeof(StackNode));
p->data=e;
p->next= S;
S=p;
return OK;
}
出栈
1
2
3
4
5
6
7
8
9
10
Status Pop(LinkStack &S, SElemType &e)
{
LinkStack *p;
if(S==NULL) return ERROR;
e=S->data;
p=S;
S=S->next;
delete P;
return OK;
}

顺序栈和链栈的对比

  • 时间性能
    • 相同,都是常数时间0(1)。
  • 空间性能
    • 顺序栈:有元素个数的限制和空间浪费的问题
    • 链栈:没有栈满的问题,只有当内存没有可用空间时才会出现栈满,但是每个元素都需要一个指针域,从而产生了结构性开销。

应用/习题

数制转换

在数学中我们通常使用短除法,即:除$d$取余,在最后余数收集过程,符合先进后出的规则。则可有流程:首先将除得的余数进栈,然后余数再依次出栈。

1
2
3
4
5
6
7
8
9
10
11
12
void conversion (){
InitStack(S); //构造空栈
scanf("%d",N); //输入一个十进制数
while(N){
Push(S,N%8); //“余数”入栈
N= N/8; //非零“商”继续运算
}
while (!StackEmpty(s)){//和“求余”所得相逆的顺序输出八进制的各位数
Pop(S,e);
prinft("%d",e);
}
} // conversion

表达式求值

  1. 设置两个工作栈

    1. 运算符栈OPTR,运算符栈的栈底为表达式的起始符#。
    2. 操作数栈OPND,操作数栈为空栈。
  2. 依次读入表达式中的每个字符

    1. 是操作数则进OPND栈;
    2. 是运算符,则和OPTR中的栈顶元素做比较再操作。
      1. 运算符优先级高于OPTR的栈顶元素,则运算符入栈;
      2. 运算符优先级低于OPTR中栈顶元素,则从OPND栈顶弹出两.操作数,与OPTR中的栈顶元素做运算,并将运算结果入OPND
      3. 运算符优先级等于OPTR中栈顶元素,则OPTR的栈顶元素出栏
  3. 直至表达式求置完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
OperandType EvaluateExpression() {
//设OPTR和OPND分别为运算符栈和运算数栈,OP为运算符集合。
InitStack(OPTR);
Push(OPTR, '#');
InitStack(OPND);
c = getchar();
while (c != '#'|| GetTop(OPTR) != '#' ) {
if(!In(c,OP)) {
Push(OPND,c);
c = getchar();
} else {
switch (Precede(GetTop(OPTR),c)) {
case ' < ': Push(OPTR,c);
c=getchar();
break;
case ' = ':
Pop(OPTR,x);
c=getchar();
break;
case '>': Pop(OPTR, theta);
Pop(OPND, b);
Pop(OPND, a);
Push(OPND, Operate(a, theta, b));
break;
}
}
//switch
}
return GetTop(OPND);
}

判断括号匹配

设计一个算法,判断一个表达式中括号是否匹配。若匹配,则返回1;否则返回0。

算法思路:扫描表达式,当遇到左括号时,将其进栈,遇到右括号时,判断栈顶是否为相匹配的左括号。若不是,则退出扫描过程,返回0;否则栈顶元素出栈,直到扫描完整个表达式时,若栈为空,则返回1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int match(char * exps) {
flag = 0;
st.top = -1;
while (exps[i] != ’\0’ && flag == 0) {
switch (exps[i]) {
case‘ (‘:
case‘ [‘:
case‘ {‘:
st.data[++st.top] = exps[i];
break;
/* 各种左括号均进栈 */
case‘)’:
if (st.data[st.top] == ’ (‘) st.top--;
else flag = 1;
break;
case‘]’:
if (st.data[st.top] == ’ [‘) st.top--;
else flag = 1;
break;
case
}’:
if (st.data[st.top] == ’ {‘) st.top--;
else flag = 1;
break;
}
i++;
}
If(flag == 0 && st.top == -1) return (1);
/* 栈空且符号匹配,则返回1 */
else return (0);
/* 否则返回0 */
}
/* match */

进制转换例题

编写一个算法,将非负的十进制整数转换为其他进制的数输出,10及其以上的数字从‘A’开始的字母表示。并给出完整的程序。

解题思路:先定义顺序栈的类型,并根据题意将ElemType设为char型;然后设计一个算法trans来完成数制的转换;最后在主函数中调用实现转换算法的函数。

算法trans的思路:先用“除基取余”法求得从低位到高位的值,同时采用顺序栈暂时存放每次得到的数,当商为0时,再从栈顶到栈底输出从高位到低位的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include "stdio.h"
#define StackSize 100
typedef char ElemType;
typedef struct {
ElemType data[StackSize];
int top;
}
SqStack;
int trans(int d,int b,char string[]) //string用于存放转换后的字符串 {
SqStack st;
char ch;
int r,i=0;
st.top=-1;
// 栈初始化
if (b<=1||b>36 || b==10) // 2≤b≤36且不为10 {
printf(" b is Error\n");
return 0;
}
while(d!=0) {
r=d%b;
//求余数
ch=r+(r<10?'0':'A'-10);
// 将余数转换为相应的字符
st.top++;
st.data[st.top]=ch;
// 进栈
d/=b;
}
while (st.top!=-1) {
string [i++]=st.data[st.top];
//将出栈的字符放入字符数组string
st.top--;
}
string [i]='\0';
//加入字符串结束标志
return 1;
}
void main() {
char str[10];
int d,b,t;
printf("input d (d≥0)please:");
// 输入待转换的整数
scanf("%d",&d);
printf ("input b (2≤b≤36) please:");
// 输入待转换的进制
scanf("%d",&b);
t=trans(d,b,str);
// 调用转换函数
if (t==0) printf("Error!"); else printf("%s\n",str);
// 输出转换结果字符串
}

递归和栈

调用前,系统完成:
(1)将实参,返回地址等传递给被调用函数
(2)为被调用函数的局部变量分配存储区
(3)将控制转移到被调用函数的入口
调用后,系统完成:
(1)保存被调用函数的计算结果
(2)释放被调用函数的数据区
(3)依照被调用函数保存的返回地址将控制转移到调用函数

队列

只允许在一端进行插入而在另一端进行删除的线性表

先进先出,队尾入,队头出

队头:允许插入的一端,队尾:允许删除的一端

抽象数据类型定义

数据对象:$ D={ a_i | a\in{ElemSet}, i =1,2,\cdots,n,n \geq 0 } $, (类似线性表)

数据关系:$R={ | a_{i-1},a_i \in D, i = 2, \cdots , n}$

基本操作

1
2
3
4
5
6
7
8
InitQueue(&Q);
DestoryQueue(&Q); //销毁
ClearQueue(&Q); //清空
QueueEmpty(Q); //判断空
QueueLength(Q);
GetHead(Q,&e); //读队头元素
EnQueue(&Q,e); //插入队列
DeQueue(&Q,&e); //处理队列

结构定义

1
2
3
4
5
6
#define M 100
Typedef struct{
QElemType *base;
int front; //头指针(偏移)
int rear; //尾指针(偏移)
}SqQueue;

循环队列

头指针向后移动时,会出现头部部分空间不被有效利用,出现假溢出的情况,此时可以使用循环队列。循环队列的本质就是当指针(偏移)达到尾部的时复位。

1
2
3
4
5
6
//入队
base[rear] = x;
rear = (rear + 1) % M;
//出队
base[front] = x;
front = (front + 1) % M;

循环队列判断队满

  1. 用另外一个标志来区别队空、队满
  2. 少用一个元素空间,则队空的时候 front == rear,队满时(rear + 1) % M == front

循环队列的初始化

1
2
3
4
5
6
7
8
Status InitQueue (SqQueue &Q){//操作结果:构造一个空队列Q
Q.base =new QElemType[MAXQSIZE]
if(!Q.base){
exit(OVERFLOW);
}
Q.front=Q.rear=0;
return OK;
}

求循环队列的长度

1
2
3
4
5
//初始条件:队列Q已存在。
//操作结果:返回Q的元素个数,即队列的长度。
int QueueLength (SqQueue Q){
return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}//多加一个MAXSIZE是为了保证正值

循环队列入队

1
2
3
4
5
6
7
8
9
10
//初始条件:队列Q已存在。
//操作结果:插入元素e为Q的新的队尾元素。
Status EnQueue(SqQueue &Q,QElemType e){
if((Q.rear+1)% MAXQSIZE== Q.front){ //队列满
return ERROR;
}
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;
}

循环队列出队

1
2
3
4
5
6
7
8
9
10
//初始条件: Q为非空队列。
//操作结果:删除Q的队头元素,并用e返回其值。
Status DeQueue (LinkQueue &Q,QElemType &e){
if(Q.front==Q.rear){ //队列空
return ERROR;
}
e = Q,base[Q.front];
Q.front = (Q.front+ 1) % MAXQSIZE;
return OK;
}

链队

存储结构

1
2
3
4
5
6
7
8
9
10
11
//结点表示:
typedef struct QNode{
QelemType data;
struct QNode *next;
}QNode, *QueuePtr;

//链队列表示:
typedef struct{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;

链队的初始化

1
2
3
4
5
6
7
8
9
//操作结果:构造一一个空队列Q
Status InitQueue (LinkQueue &Q){ //构造一一个空队列Q
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front){ //存储分配失败
exit(OVERFOLW);
}
Q.front->next = NULL;
return OK;
}

销毁链队列

1
2
3
4
5
6
7
8
9
10
//初始条件:队列Q已存在。
//操作结果:队列Q被销毁,不再存在
Status DestroyQueue (LinkQueue &Q){
while(Q.front){
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}

判断链队列是否为空

1
2
3
4
5
//初始条件:队列Q已存在。
//操作结果:若Q为空队列,则返回true,否则返回false;
Status QueueEmpty (LinkQueue Q){
return (Q.front == Q.rear);
}

求链队列的队头元素

1
2
3
4
5
6
7
8
9
//初始条件: Q为非空队列
//操作结果:用e返回Q的对头元素;
Status GetHead (LinkQueue Q, QElemType &e){
if(Q.front==Q.rear){
return ERROR;
}
e = Q.front->next->data;
return OK;
}

链队的入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//初始条件:队列Q已存在。
//操作结果:插入元素e为Q的新的队尾元素。
Status EnQueue(LinkQueue &Q, QElemType e){
//在当前队列的尾元素之后,插入元素e为新的队列尾元素
p = (QueuePtr)malloc(sizeof(QNode));
if (!p){ //存储分配失败
exit(OVERFLOW);
}
p->data=e;
p->next= NULL;
Q.rear->next=p;//修改尾结点的指针
Q.rear = p; //移动队尾指针

}

链队的出队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//初始条件: Q为非空队列。
//操作结果:删除Q的队头元素,并用e返回其值。
Status DeQueue(LinkQueue &Q, QElemType &e){
if(Q.front==Q.rear){//链队列空
return ERROR;
}
p = Q.front->next;
e = p->data; //返回被删元素的值
Q.front->next=p->next; //修改队头结点指针
if(Q.rear==p){
Q.rear=Q.front;
}
free(p);
return OK;
} // DeQueue

应用

杨辉三角(重点理解)

(1) i=2时, 从q中取出队头t=1,计算s+t,得到i=3时的第1个数据1,放在q的队尾;
(2)让s=t,从q中取出队头t=2,计算s+t,得到i=3时的第2个数据3,放在q的队尾;
(3)让s=t,从q中取出队头t=1,计算s+t,得到i=3时的第3个数据3,放在q的队尾;
(4)如此重复,直到第i行的数据处理完毕,全部出队,第i+1行的数据也全部计算出来并入队。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void yanghui (int N){
InitQueue(&Q);
EnterQueue(&Q, 1);
EnterQueue(&Q, 1);//第一行元素入队
s = 0;
for(i= 1;i<= N; i++){
printf("\n");
EnterQueue(&Q, 0); //入队
for(j=1;j<=i+ 2;j++)
{
DelQueue(&Q, &temp); //出队的数赋给temp
EnterQueue(&Q,s+temp);
s=temp;
if(j!=i+2){
printf("%d ",s);
}
}
}
}

性能对比

  • 时间性能
    • 循环队列和链队列的基本操作都需要常数时间0 (1)。
  • 空间性能
    • 循环队列:必须预先确定一个固定的长度,所以有存储元素个数的限制和空间浪费的问题。
    • 链队列:没有队列满的问题,只有当内存没有可用空间时才会出现队列满,但是每个元素都需要一个指针域,从而产生了结构性开销。