//语句1
for（j=0;j<=（2*n）;j++）
x++;
语句2
//
}
解：
语句
1频度为
（n-1）；语句2频度为
，因此时间复杂度
。
（n-1）*（2n+1）=2n2-n-1
T（n）=2n2-2=O（n2）
例2：
i=1;
while（i<=n）
i=i*2;
//语句
1
//语句2
1；设语句
解：
语句
1频度为
2频度为
f（n），则有2f（n）<=n
。
，即
，去极大值，f（n）=log2n，
f（n）<=log2n
因此时间复杂度
T（n）=1+log2n=O（log2n）
2/62
精品资料
精品学习资料
第2页，共62页
第二章
线性表
2.1线性表的概念和运算
1.线性表的概念
线性表是
n（n≥0）
个类型相同的数据元素组成的
有限序列。
其中数据元素的个数
n为线性表的长度，
当n=0时称为空表。
2.线性表的特点
对于非空的线性表，有且仅有一个
开始结点和一个终端结点；开始结点没有直接前趋，有且仅有一个
直接后继；终端结点
直接后继。
没有直接后继，有且仅有一个直接前趋；其余任何结点有且仅有一个
直接前趋和一个
3.线性表的计算
（1）置空表
（2）求长度
（3）取结点
NULL。
SETNULL（L）：
将线性表
L置为空表。
LENGTH（L）：
返回是线性表
L中结点的个数。
：
当1≤
i≤LENGTH（L）时，返回线性表
L中的第
i个结点，否则返回
GET（L,i）
（4）定位
存在多个值为
LOCATE（L,x）：
当线性表
L中存在一个值为
x的结点时，结果是该结点的位置；若表
L中
x的结点，则返回首次找到的结点位置；若表
L中不存在值为
x的结点，则返回一个特殊值
表示值为x的结点不存在。
（5）插入INSERT（L,n是原表L的长度。
x,i）：
在线性表L的第i个位置插入一个值为
x的新结点。
这里1≤i≤n+1，
（6）删除DELETE（L,i）
：
删除线性表
L的第i个结点。
这里
1≤i≤n，n是原表L的长度。
2.2线性表的存储结构
1.顺序存储：
（1）定义：
把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
简言之，逻
辑上
相邻，物理上也相邻
。
（2）顺序存储方法：
用一组地址连续的存储单元依次存储线性表的元素，可通过
数组来实现。
（3）地址计算：
设首元素
a1的存放地址为
LOC（a1）（称为首地址），设每个元素占用存储空间（地址
长度）为
L字节，则地址计算公式：
。
LOC（ai）=LOC（a1）+（i-1）*L
（4）结构定义：
#defineMAXSIZE1024typedefintdatatype;typedefstruct
{
//线性表的最大长度
//线性表数据元素类型
datatype
intlast;
}sequenlist;
data[MAXSIZE];
指示线性表的终端结点在表中的下标值
//
2.链式存储：
3/62
精品资料
精品学习资料
第3页，共62页
（1）特点：
用一组
任意的存储单元存储线性表的数据元素，利用
指针实现了用不相邻的存储单元存
放逻辑上相邻的元素，每个数据元素
（2）头指针、头节点、开始节点
ai，除存储本身信息外，还需存储其直接后继的信息。
头指针是指向链表中第一个结点（或为头结点或开始结点）
的指针，单链表可由一个头指针唯一确定。
头结点是在链表的开始结点之前附设的一个结点
；数据域内只放空表标志和表长等信息
a1的结点。
；
开始结点是指链表中存储线性表
（3）空表的表示
无头结点时，当头指针的值为空
第一个数据元素
时表示空表；
有头结点时，当头结点的指针域为空
（4）结构定义
时表示空表。
//线性表数据元素类型
typedefintdatatype;
typedefstructnode{
//数据域
//指针域
datatype
data;
structnode
}linklist;
*next;
3.存储结构比较
（1）优缺点
顺序存储的优点是存储密度大查找这样的静态操作。
（＝1），存储空间利用率高。
缺点是插入或删除元素时不方便。
适合做
链式存储的优点是插入或删除元素时很方便，
适合做做插入、删除这样的动态操作。
使用灵活。
缺点是存储密度小（<1），存储空间利用率低。
（2）线性表的顺序存储与链式存储对线性表的运算比较
顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）必须是连续的。
；要求内存中可用存储单元的地址
链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存
放表示结点间关系的指针。
（3）时间复杂度和存储密度比较
顺序存储存储密度
删除时时间复杂度为
=1，链式存储<1。
顺序表中访问任意一结点的时间复杂度均为
O
（1），但是在插入和
O（n）。
链表时间复杂度为
O（n）。
4.单链表操作
（1）查找
voidfindValue（Linklist*head,intx）{Linklist*t;
t=head->next;while（t!
=NULL&&t->data!
=x）
t=t->next;if（t->data==x）
printf（"成功找到\n"）;
else
printf（"没有找到\n"）;
}
（2）插入
voidinsert（Linklist*head,intx）{
4/62
精品资料
精品学习资料
第4页，共62页
Linklist*t,*p;
p=（Linklist*）malloc（sizeof（Linklist））;p->data=x;
t=head;
while（t->next!
=NULL&&t->next->datanext;
if（t==head）{
p->next=head->next;head->next=p;
}elseif（t->next==NULL）{
t->next=p;
p->next=NULL;
}else{
p->next=t->next;t->next=p;
}
}
（3）删除
voiddele（Linklist*head）{Linklistp,q;p=head;
while（p->next!
=NULL）{
if（p->data!
=p->next->data）p=p->next;else
{q=p->next;p->next=q->next;free（q）;}
}
}
（4）逆置
voidreverse（Linklist*head）{Linklist*s,*t,*p;
p=head;
s=p->next;
while（s->next!
=NULL）{t=s->next;
s->next=p;
p=s;s=t;
}
s->next=p;
head->next->next=NULL;head->next=s;
}
5/62
精品资料
精品学习资料
第5页，共62页
2.3例题
例1：
一个一维数组
M，下标的范围是
0到9，每个数组元素用相邻的
5个字节存储。
存储器按字节编址，
设存储数组元素
M[O]的第一个字节的地址是
98，则M[3]的第一个字节的地址是
。
113
例2：
在一个长度为
个元素（或删除第
n的顺序表中向第
i个元素（1≤i≤n+1）之前插入一个新元素时，
需要向后移动
n-i+1
i个元素，需要向前移动
个元素）。
n-i
例3：
在单链表中，若
*p结点不是末尾结点，在其前或后插入
*s结点或删除结点的操作是？
解：
在其前插入
t;
在其后插入
*s结点：
s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=
*s结点：
s->next=p->next;p->next=s;
删除其前结点：
删除其后结点：
需要利用遍历
q=p->next;p->next=q->next;free（q）;
删除自身接结点：
q=p->next;p->data=q->data;p->next=q->next;free（q）;
例4：
在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是
顺序结构
。
第三章
栈和队列
3.1栈和队列的基本概念
1.栈的概念
栈是只允许在
端叫栈底（bottum）
同一端进行插入和删除操作的线性表。
允许进行插入和删除的一端叫
栈顶（top）
，另一
，栈中无数据元素时，称为
空栈。
具有先进后出（FILO）或后进先出（LIFO）的特点。
2.栈的定义
（1）顺序栈
typedefintdatatype;
#defineMAXSIZE100typedefstruct{
（2）链栈
typedefintdatatype;typedefstructnode{
datatypedata;structnode*next;
}linkstack;
linkstack*top;
top是栈顶指针，它唯一地确定一个链栈。
top=NULL时，该链栈为空栈。
链栈中的结点是动态
datatype
data[MAXSIZE];
inttop;
}seqstack;seqstack*s;
产生的，无需考虑上溢问题
。
3.顺序栈操作
（1）判断栈空
intEMPTY（seqstack*s）{
–>top>=0）;
return（!
s
6/62
精品资料
精品学习资料
第6页，共62页
}
（2）置空栈
voidSETNULL（seqstack*s）{
–>top=-1;
s
}
（3）判断栈满
intFULL（seqstack*s）{
return（s–>top==MAXSIZE-1）;
}
（4）进栈
seqstack*PUSH（seqstack*sif（FULL（s））
，datatypex）{
“stackoverflow
”）;returnNULL;}
{printf（
s–>top++;s
–>data[s–>top]=x;
returns;
}
（5）出栈
datatypePOP（seqstack*s）{if（EMPTY（s））{
printf（“stackunderflow
returnNULL;
}
s–>top--;
return（s–>data[s–>top+1]）;
}
（6）取栈顶
datatypeTOP（seqstack*s）{if（EMPTY（s））{
printf（“stackisempty
returnNULL;
}
return（s–>data[s–>top]）;
}
”）;
”）;
4.链栈操作
（1）进栈
linkstack*PUSHLSTACK（linkstack*top,datatypex）{linkstack*p;
p＝（linkstack*）malloc（sizeof（linkstack））;
p->data＝x;
p->next＝top;
返回新栈顶指针
returnp;/*
*/
}
（2）出栈
linkstack*POPLSTACK（linkstack*top,datatype*datap）{
7/62
精品资料
精品学习资料
第7页，共62页
linkstack*p;
if（top==NULL）
{printf（
“underflow
”）;returnNULL;}
datap＝top->data;/*
p=top;
top＝top->next;free（p）;
栈顶结点数据存入
*datap*/
返回新栈顶指针
returntop;/*
*/
}
5.队列的概念
队列（Queue）也是一种运算受限的线性表。
只允许在表的一端进行
插入，而在另一端进行
删除。
允许
删除的一端称为队头（front）
，允许插入的一端称为
队尾
（rear）。
具有先进先出（FIFO）的特点。
6.队列的定义
（1）顺序队列
#defineMAXSIZE100typedefstruct{
datatypedata[MAXSIZE];
intfront;intrear;
}sequeue;
sequeue*sq;
（2）链式队列
typedefstructqueuenode{datatypedata;
structqueuenode*next;
}QueueNode;typedefstruct{
QueueNode*front;
QueueNode*rear;
}LinkQueue;
7.循环队列
（1）假上溢
在入队和出队的操作中，头尾指针只增加不减小，
致使被删除元素的空间永远无法重新利用
。
尽管队
列中实际的元素个数远远小于向量空间的规模，
但也可能由于尾指针巳超出向量空间的上界而不能做入队
操作，该现象称为
（2）循环队列
假上溢。
为了解决假上溢问题，引入了循环队列的概念。
在循环队列中进行
出队、入队操作时，头尾指针仍要
加1，朝前移动。
只不过当头尾指针指向
0。
（3）队空队满问题
入队时：
尾指针向前追赶头指针，
向量上界（MaxSize-1）时，其加1操作的结果是指向
向量的下界
出队时：
头指针向前追赶尾指针，
故队空和队满时头尾指针均相等，
无法通过
来判断队列“空”还是“满”
。
sq->front==sq->rear
解决此问题的方法至少有两种：
1、另设一个布尔变量以区别队列的空和满；
2、少用一个元素空间为代价，入队前，测试尾指针
（4）常用操作
，若相等则认为队满
。
sq->
rear+1==sq->front
队空判断
队满判断入队：
：
：
sq->front==sq->rear
sq->front==（sq->rear+1）%maxSize
sq->rear=（sq->rear+1）%maxSize
8/62
精品资料
精品学习资料
第8页，共62页
出队：
求队长：
sq->front=（sq->front+1）%maxSize
（sq->rear-sq->front+maxSize）%maxSize
8.循环队列操作
（1）入队
①检查队列是否已满，若队满，则进行溢出错误处理。
②将队尾指针后移一个位置（即加
③将新元素赋给队尾指针所指单元。
1），指向下一单元。
StatusEnQueue（SqQueue*Q,ElemTypee）{
if（（Q->rear+1）%MAXQSIZE==Q->front）
//队满上溢
return（ERROR）;
Q->rear=（Q->rear+1）%MAXQSIZE;
Q->data[Q->rear]=e;return（True）;
}
（2）出队
①检查队列是否为空，若队空，则进行下溢错误处理。
②将队首指针后移一个位置（即加
③取队首元素的值。
StatusDeQueue（SqQueue*Q）{if（Q->rear==Q->front）
1）。
//队空下溢
return（NULL）;
Q->front=（Q->front+1）%MAXQSIZE;
return（Q->data[Q->front]）;
}
（3）置空队
Q->front=Q->rear=MAXQSIZE-1;
（4）取队头
datatypeGetHead（SqQueue*Q）{if（Q->front==Q->rear）
//队空
return（NULL）;
return（Q->data[（Q->front+1）%MAXQSIZE]）;
}
（5）判断队空
intQueueEmpty（SqQueue*Q）{if（Q->front==Q->rear）
return（True）;
else
return（False）;
}
9.链式队列操作
（1）置空
voidInitQueue（LinkQueue*Q）{
Q.front=Q.rear=（queuenode*）malloc（sizeof（queuenode））;
9/62
精品资料
精品学习资料
第9页，共62页
Q.front->next=Q.rear->next=NULL;
}
（2）判断队空
intQueueEmpty（LinkQueue*Q）{
return（Q.front->next==NULL&&Q.rear->next==NULL）;
}
（3）入队
voidEnQueue（LinkQueue*Q,datatypex）{QueueNode*p;
p=（QueueNode*）malloc（sizeof（QueueNode））;
p–>data=x;
p–>next=NULL;
Q->rear–>next=p;Q->rear=p;
}
（4）出队
DeQueue（linkqueue*Q）{linkqueue*p;datatypex;
if（EMPTY（Q））
returnNULL;p=Q->front->next;
–>next;
Q->front->next=p
if（p->next==NULL）
Q->rear=Q->front;
x=p->data;
free（p）;returnx;
}
3.2栈和队列的应用
1.递归函数
递归函数又称为自调用函数，
n!
=1,FACT（n）=1,
n>1
C语言描述如下：
intFACT（intn）{
if（n==1）
return
（1）;
else
它的特点：
在函数内部可以直接或间接地调用函数自己。
例如阶乘函数：
可以被描述为
！
n>1，
n=1&n*n-1
n=1&n*FACTn-1！
return（n*FACT（n-1））;
}
10/62
精品资料
精品学习资料
第10页，共62页
2.算法表达式求值
计算机系统在处理表达式前，先设置两个栈：
操作数栈
（OPRD）：
存放处理表达式过程中的操作数；运
算符栈（OPTR）：
存放处理表达式过程中的运算符。
开始时，在运算符栈中先在栈底压入一个表达式的结束
符“#”。
（1）中缀表示法计算机系统在处
升级会员 