-
第一章
绪论
逻辑结构：
线性结构
（
2
线性表；
3
栈和队列；
4
数组和广义表；
5
串）和非线性（
6
树；
7
图）
8
查找
；
9
排序
存储结构：顺序存储、链式存储、索引存储、散列存储
判断算法好坏的标准：时间复杂度和空间复杂度
第二章
线性表
线性表：由
< br>n
（
n>=0
）个相同数据类型
的元素组成的有限序列。
逻辑结构的定义方式：
（元素
1
，元素
2
，
。
。
。
）
存储结构：
?
顺序存储
(
用数组体现
)
：
预先分配一段
连续的
区域，
静态<
/p>
分配
int
a[10];
a
表示
a[0]
的地址
顺序表：两层含义：逻辑结构上线性结构
物理上顺序存储
?
链式存储
（用指针）
：
占用的区域
不一定
连续，
动态
分配；
m
alloc
free
链表：两层含义：逻辑结构上线性结构
物理上链式存储
顺序表的插入：
maxsize
表示最多存放的元素的个数，
size
表示
有效元素的个数
1
、
判断满不满：满的条件：
size= =maxsize
2
、
插入的
位置是不是合法（
i>=1&&i<=size+1
）
3
、
后移（先移动后面的）
4
、
插入
size++
；
顺序表的删除：
1
、
判断空间是否是空
（
size=
=0
）
2
、
判断位置是不是合法
（
1<=i<=size
）
3
、
前移（先移动前面的）
4
、
Size- -
链表的插入：
p
结点的后面
1
、
生成空间：
s=(S
*)malloc(sizeof(S));
2
、
赋值：
s->data=X;
3
、
s->
next=p->next;(
修改新结点的指针
)
4
、
P->next=s;
链表的删除
：
p
结点的后面的结点
1
、
q=p->next;
2
、
p->next=q->next;
//p->next=p->next->next;
3
、
free(q);
删除
p
结点本身：
A
、
寻找<
/p>
p
结点的前驱结点
,
转化为删除
p
结点的前驱结点的后
继
q=head;
while(q->next!=p)
q=q->next;
q->next=p->next;
free(p);
B
、
删除<
/p>
p
的后继（
p
结
点不是终端结点，
p
一定要有后继）
q=p->next;
p->data=q->data;
p->next=q->next;
free(q);
第三章
栈和队列
栈和队列是特殊的线性表。
栈
Stack
：操作受限（插入和删除）的线性表。
在线性表的末尾做插入和删除，
叫做栈顶
top
线性表的开始部
分叫做栈底
bottom
特点：
FILO
典型应用：函数的调用
存储方式：
?
顺序存储（用数组体现，静态分配存储空间）
?
链式存储（涉及到指针，动态分配存储空间）
顺序栈的插入：
top
表示栈顶元素的下标，
定义是
int
类型的，
格
式是
int to
p
；
maxsize
表示空间的大小，
最多存放多少个元素
(
在顺序表的基
础上修改的，红颜色粗体部分去掉
)
1
、
判断满不满：满的条件是
top= = maxsize-1
2
、
插入的
位置是不是合法（
i>=1&&i<=size+1
）
：去掉
原因是
位置固定
size+1
3
、
后移（先移动后面的）
：去掉
4
、
top
++
；插入（
data[top]=X
）
顺序
栈的删除：
(
在顺序表的基础上修改的，红颜色粗体部分去
掉
)
1
、
判断空间是否是空
（
top= =-1
top<0
）
2
、
判断位置是不是合法
（
1<=i<=size
）
3
、
前移（先移动前面的）
4
、
top
- -
链栈的插入操作：
top<
/p>
表示栈顶的指针，类似于
head
，
top
是指
针变量
格式：数据类型
*top
；
1
、
生成空
间：
s=malloc
（。
。
。
。
）
；
2
、
赋值：
s->data=X;
3
、
修改指
针：
s->next=top;(
先修改的是新结点的指针
)
4
、
修改
top
指针：
t
op=s
；
链栈的删除：
1
、
p=top;
2
、
top=top->next;
3
、
free(p);
进栈的顺序是
123
，
则可
能的出栈的顺序是
123
、
132
、
213
、
231
、
312
、
3
21
进栈的顺序是
1234
，则可能
的出栈的顺序是
1234
、
1243<
/p>
、
1324
、
1
342
、
1432
、
< br>2134
、
2143
、
2314
、
2341
、
2431
、
3214
< br>、
3241
、
3421
、
4321
队列：
1
、
定义：
操作受限的线性表（在表的一端进行插入、在另一
端进行删除）
2
、
在线性表的末尾进行插入操作，叫做队尾
rear
在线性表的开始做删除操作，叫做队头
front
3
、
特点：
FIFO
4
、
存储结构：
?
顺序存储（用数组体现，静态分配存储空间）
?
链式存储（用指针体现，动态分配存储空间）
入队列的顺序是
1234
，则出队的顺序是
1234
。
循环队列：队列的顺序存储结构
循环
队列长度是
maxsize
，则最多存放
maxsize-1
个元素
?
Front
表示：队头元素的前一个位置
?
Rear
：队尾元素的下标
循环队列空的条件是：
front= = rear
循环队列满的条件是：
front==(rear+1)%maxsiz
e
循环队列的元素的个数是：
(rear-
front+maxsize)%maxsize
循环队列的队头元素的下标：
（
front+1
）
%maxsize
备注：凡涉及到
+1
，都要
%maxsize
顺序队列的插入：
(
在顺序表的基础上修改的，红颜色粗体部分
去掉
)
1
、
判断满不满：满的条件：
front= =
（
rear+1
）
%maxsiz
e
2
、
插入：
rear=(rear+1)%maxsize
data[rear]=X;
顺序队列的删除：
(
在顺序表的基础上修改的，红颜色粗体部分
去掉
)
1
、
判断空间是否是空：空的条件是
front= =rear
2
、
删除：
front=(front+1)%maxsize
链队列：队列的链式存储结构
Front
表示的队头元素的指针
Rear
表示队尾的指针
链队列的插入操作：
1
、
p=malloc(
…
);
2
、
p->data=X;
3
、
p->
next=NULL;
（先修改新产生结点的指针）
4
、
rear->next=p;
5
、
rear=p;
链队列的删除
:
（带头结点的队列）
一、
删除真正的队头元素
1
、
判断队
列是否为空
:
空的条件是
front=
= rear
2
、
s=front->next;
3
、
front->next=s->next;
4
、
free(s);
二、
通过删除头结点
转化为删除队头元素
1
、
判断队
列是否为空
:
空的条件是
front=
= rear
2
、
s=front;
3
、
front=front->next;
4
、
free(s);
(10,20,30)
1
、
线性表，画出带头结点的单链表
2
、
栈，分别画出顺序存储结构
链式存储结构
3
、
队列，分别画出顺序存储结构
链式存储结构
第四章
数组和广义表
表头一定是原子。
（×）
表头一定是广义表。
（×）
表尾一定是原子。
（×）
表尾一定是广义表。
（√）
第五章
串
Int a[]=
”
123
”
;
(
√
)
Int a[10]; a=
”
123
”
;
(
×
)
Char name[10]=
”<
/p>
gmm
”
;
-
-
-
-
-
-
-
-
-
上一篇：宝马奔驰中英文对照表
下一篇：(完整)比较级和最高级