数据结构清华大学出版社严蔚敏吴伟民编著
第一章绪论
1、数据结构是计算机中存储、组织数据的方式。精心选择的数据
结构可以带来最优效率的算法。
2、程序设计= 算法+数据结构
3、解决问题方法的效率：
●跟数据的组织方式有关
●跟空间的利用效率有关
●跟算法的巧妙程度有关
4、数据：所有能输入到计算机中,且被计算机处理的符号的集合，
是计算机操作对象的总称；
是计算机处理的信息的某种特定的符号表示形式。
5、数据元素：数据中的一个“个体”,数据结构中讨论的基本单
位。相当于“记录”,在计算机程序中通常作为一个整体考
虑和处理。
6、数据项: 相当于记录的“域”, 是数据的不可分割的最小单位,
如学号。数据元素是数据项的集合。
7、数据对象：性质相同的数据元素的集合.
例如: 所有运动员的记录集合
8、数据结构：是相互间存在某种关系的数据元素集合。
9、数据结构是带结构的数据元素的集合。
10、不同的关系构成不同的结构。
11、次序关系：
{
12、对每种数据结构，主要讨论如下两方面的问题：
1）数据的逻辑结构，数据结构的基本操作；
2）数据的存储结构，数据结构基本操作的实现；
13、数据的逻辑结构：
数据之间的结构关系，是具体关系的抽象。
数据结构的基本操作：
指对数据结构的加工处理。
14、数据的存储结构(物理结构)：
数据结构在计算机内存中的表示。
数据结构基本操作的实现：
基本操作在计算机上的实现（方法)。
15、数据结构的有关概念
16、数据元素的4类的基本结构：
○1集合；
○2线性结构：结构中数据元素之间存在一对一的关系；
○3树形结构：结构中数据元素之间存在一对多的关系；
○4图状结构或网状结构：结构中数据元素之间存在多对多的关系。
17、C语言的优点：C语言可以直接操作内存。
18、每个节点都由两部分组成：数据域和指针域。
19、链接存储结构特点：
●比顺序存储结构的存储密度小
(每个节点都由数据域和指针域组成)。
●逻辑上相邻的节点物理上不必相邻。
●插入、删除灵活
(不必移动节点，只要改变节点中的指针)。
20、数据类型是一个值的集合和定义在此集合上的一组操作的
总称。
21、ADT 有两个重要特征:数据抽象和数据封装。
22、抽象数据类型(Abstract Data Type 简称ADT)：是指一个数
学模型以及定义在此数学模型上的一组操作。
23、抽象数据类型有：数据对象〈数据对象的定义〉、数据关
系〈数据关系的定义〉、基本操作〈基本操作的定义〉。24、数据类型的定义和含义。
定义：数据类型是一个值的集合和定义在这个值集上的一组
操作的总称。
含义：将数据按一定次序与形式存放的结构。
24、算法空间复杂度S(n)
算法的存储量包括：
①输入数据所占的空间；
②程序本身所占的空间；
③辅助变量所占的空间。
25、算法具有有穷性、确定性、可行性、输入和输出五大特性。
26、抽象数据类型具有数据抽象、数据封装的特点。
27、数据的储存结构分为：顺序存储结构和链式存储结构。
第二章线性表
1、线性结构的特点：在数据元素中的非空有限集中。
（1）存在唯一的一个被称作“第一”的数据元素；
（2）存在唯一的一个被称作“最后一个”的数据元素；
（3）除第一个外，集合中的每一个数据元素均只有一个前驱；
（4）除最后一个外，集合中的每一个数据元素均只有一个后继。
2、线性表(Linear List) ：一个线性表是n个数据元素的有限序列。
3、线性表的顺序存储实现：
typedef struct {
ElementType Data[MAXSIZE];
int Last;
} List;
List L, *PtrL;
4、初始化（建立空的顺序表）
List *MakeEmpty( )
{ List *PtrL;
PtrL = (List *)malloc( sizeof(List) );
PtrL->Last = -1;
return PtrL;
}
5、查找
int Find( ElementType X, List *PtrL )
{ int i = 0;
while( i <= PtrL->Last && PtrL->Data[i]!= X )
i++;
if (i > PtrL->Last) return -1; /* 如果没找到，返回-1 */
else return i; /* 找到后返回的是存储位置*/
}
6、插入算法
void Insert( ElementType X, int i, List *PtrL )
{ int j;
if ( PtrL->Last == MAXSIZE-1 ){ /* 表空间已满，不能插入*/
printf(＂表满＂);
return;
}
if ( i < 1 || i > PtrL->Last+2) { /*检查插入位置的合法性*/
printf(＂位置不合法＂);
return;
}
for ( j = PtrL->Last; j >= i-1; j-- )
PtrL->Data[j+1] = PtrL->Data[j]; /*将ai～an倒序向后移动*/
PtrL->Data[i-1] = X; /*新元素插入*/
PtrL->Last++; /*Last仍指向最后元素*/
return;
}
7、删除算法
void Delete( int i, List *PtrL )
{ int j;
if( i < 1 || i > PtrL->Last+1 ) { /*检查空表及删除位置的合法性*/
printf (“不存在第%d个元素”, i );
return ;
}
for ( j = i; j <= PtrL->Last; j++ )
PtrL->Data[j-1] = PtrL->Data[j]; /*将ai+1～an顺序向前移动*/
PtrL->Last--; /*Last仍指向最后元素*/
return;
}
8、求表长
int Length ( List *PtrL )
{ List *p = PtrL; /* p指向表的第一个结点*/
int j = 0;
while ( p ) {
p = p->Next;
j++; /* 当前p指向的是第j 个结点*/
}
return j;
}
9、查找
（1）按序号查找: FindKth;
List *FindKth( int K, List *PtrL )
{ List *p = PtrL;
int i = 1;
while (p !=NULL && i < K ) {
p = p->Next;
i++;
}
if ( i == K ) return p;
/* 找到第K个，返回指针*/
else return NULL;
/* 否则返回空*/
}
（2）按值查找: Find
List *Find( ElementType X, List *PtrL )
{
List *p = PtrL;
while ( p!=NULL && p->Data != X )
p = p->Next;
return p;
}
10、插入（在链表的第i-1(1≤i≤n+1)个结点后插入一个值为X的新结点)
List *Insert( ElementType X, int i, List *PtrL )
{ List *p, *s;
if ( i == 1 ) { /* 新结点插入在表头*/
s = (List *)malloc(sizeof(List)); /*申请、填装结点*/
s->Data = X;
s->Next = PtrL;
return s; /*返回新表头指针*/
}
p = FindKth( i-1, PtrL ); /* 查找第i-1个结点*/
if ( p == NULL ) { /* 第i-1个不存在，不能插入*/
printf(＂参数i错＂);
return NULL;
}else {
s = (List *)malloc(sizeof(List)); /*申请、填装结点*/
s->Data = X;
s->Next = p->Next; /*新结点插入在第i-1个结点的后面*/
p->Next = s;
return PtrL;
}
}
11、删除（删除链表的第i (1≤i≤n)个位置上的结点)
List *Delete( int i, List *PtrL )
{ List *p, *s;
if ( i == 1 ) { /* 若要删除的是表的第一个结点*/
s = PtrL; /*s指向第1个结点*/
PtrL = PtrL->Next; /*从链表中删除*/
free(s); /*释放被删除结点*/
return PtrL;
}
p = FindKth( i-1, PtrL ); /*查找第i-1个结点*/
if ( p == NULL ) {
printf(“第%d个结点不存在”, i-1); return NULL;
} else if ( p->Next == NULL ){
printf(“第%d个结点不存在”, i); return NULL;
} else {
s = p->Next; /*s指向第i个结点*/
p->Next = s->Next; /*从链表中删除*/
free(s); /*释放被删除结点*/
return PtrL;
}
}
12、链表不具备的特点是 1 。
①可随机访问任一节点②插入删除不须要移动元素
③不必事先估计存储空间④所需空间与其长度成正比
13、带头结点的单链表head为空的判定条件是 2 。
①head==NULL ②head->next==NULL
③head->next==head ④head!=NULL
14、如果最常用的操作是取第i个结点及其前驱，则采用 4 存
储方式最节省时间。
①单链表②双链表③单循环链表④顺序表
第三章Chapter 3 栈(stacks)和队列（queues）
1、栈是限定仅能在表尾一端进行插入、删除操作的线性表。
2、栈的特点是“后进栈的元素先出栈”（last in, first out），故栈又
称为后进先出表（LIFO）。
3、一个栈是一些元素的线形列表，其中元素的插入和删除均在表
的同一端进行。插入和删除发生的一端称为栈顶（the top of the stack）。
4、第一个进栈的元素在栈底，
5、最后一个进栈的元素在栈顶，
第一个出栈的元素为栈顶元素，
最后一个出栈的元素为栈底元素。
6、连续栈(Contiguous Stack)的类型定义
#define MaxStack 50
Typedef struct
{datatype stack[MaxStack];
int top;
}Seqstack;
Seqstack *s;
7、判断栈是否已满
viod Push(Seqstack *s, datatype x )
{
if (s->top>=MaxStack-1) printf(“overflow”);
else {
s-> top++;
s->stack[s->top]=x;}
}
8、判断栈是否为空
datatype pop(Seqstack *s )
{ if (s->top<0)
{printf(“underflow”); return(NULL);}
return(s->stack[s->top]);
s->top--;
}
9、返回栈顶元素的值，栈不发生变化。
datatype top(Seqstack *s )
{ if (s->top<0)
{printf(“underflow”); return(NULL);}
return(s->stack[s->top]);
}
10、链栈（Linked Stack)的类型定义
栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链
表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：
typedef struct stacknode {
datatype data
struct stacknode *next
}stacknode
11、链式栈的特点：
链式栈无栈满问题；空间可扩充；插入与删除仅在栈顶处执行；链式栈的栈顶在链头；适合于多栈操作。
11、栈是限定仅能在表的一端进行插入、删除操作的线性表。
12、栈的元素具有后进先出的特点。
13、栈顶元素的位置由栈顶指针的指示, 进栈、出栈操作要修改栈顶指针。
14、抽象数据类型队列的定义：
队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。
15、队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。
16、双端队列：就是限定插入和删除操作在表的两端进行的线性表。
17、链队列结点定义：
typedef struct Qnode
{ QElemType data;
struct QNode *next;
} QNode,*QueuPtr;
18、队列的顺序存储结构称为顺序队列，在队列的顺序存储结构中，
除了用一组地址连续的储存单元依次存放从队头到队尾的元素
之外，尚需要附设两个指针front和rear分别指示队列头元素
和队列尾元素的位置。
19、在非空队列中，头指针始终指向队头元素，而尾指针始终指向
队尾元素的下一位置。
20、栈的特点是先进后出，队列的特点是先进后出。
21、栈和队列的共同特点是只允许在端点处插入和删除元素。
22、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 C 。
（A）edcba （B）decba （C）dceab （D）abcde
23、若已知一个栈的进栈序列是p1，p2，p3，…，pn 。其输出序列为1，2，3，…，n ，若p3=1，则p1为 C 。
（A）可能是2（B）一定是2（C）不可能是2 （D）不可能是3 24、设有一个空栈，栈顶指针为1000H（十六进制，下同），现有输入序列为1、2、3、4、5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是 3 ，栈顶指针是
8 。
①5、4、3、2、1 ②2、1 ③2、3
④3、4 ⑤1002H ⑥1004H
⑦1005H ⑧1003H
24、一个队列的入队序列是若1，2，3，4，则队列的输出序列是
B 。
（A）4，3，2，1 （B）1，2，3，4
（C）1，4，3，2 （D）3，2，4，1
25、若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 B 。
（A）1和5 （B）2和4 （C）4和2 （D）5和1 26、有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有哪几个
C、D、B、A、E C、D、E、B、A
C、D、B、E、A
第六章树和二叉树
1、树型结构是一类重要的非线性结构。
2、树的定义：树是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：
（1）有且仅有一个特定的称为根的结点；
（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，T3…Tm，其中每个子集又是一棵树，并称其为根的子树。
3、基本术语
结点——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数
叶子(leaf)——度为0的结点
孩子(child)——结点子树的根称为该结点的孩子
双亲(parents)——孩子结点的上层结点叫该结点的~
兄弟(sibling)——同一双亲的孩子
树的度——一棵树中最大的结点度数
结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……
深度(depth)——树中结点的最大层次数
森林(forest)——m(m?0)棵互不相交的树的集合
例题:
4、二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。
二叉树可以是空集合，根可以有空的左子树或空的右子树。
性质1: 在二叉树的第i层上至多有2i-1个结点(i>=1)。
性质2：深度为k的二叉树至多有2k－1个结点（k>=1)。
性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。
性质4：具有n个结点的完全二叉树的深度为?log2n?＋1。
性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从
第1层到第?log2n ?+1层，每层从左到右)，则对任一结点i（1<=i<=n)，有：
（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，
则其双亲是结点?i/2?。
（2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左
孩子是结点2i。
（3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结
点2i＋1。
一棵深度为k且有2k-1个结点的二叉树称为满二叉树。如：
5、二叉树的存储结构
●顺序存储结构
define MAX-TREE-SIZE 100
Typedef TelemType SqBiTree[ MAX-TREE-SIZE];
SqBitree bt;
缺点是有可能对存储空间造成极大的浪费。
●链式存储结构
二叉链式存储结构
typedef struct BiTNode
{ TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
三叉链表
typedef struct node
{ datatype data;
struct node *lchild, *rchild, *parent;
}JD;
6、遍历二叉树
二叉树是由三个基本单元组成：根结点、左子树和右子树。
若限定先左后右，则只有前三种情况，分别称之为先（根）序遍历，中（根）序遍历和后（根）序遍历。
（1）先序遍历算法
若二叉树为空树，则空操作；否则，
●访问根结点；
●先序遍历左子树；
●先序遍历右子树。
void PreOrder（BiTree bt）{/*先序遍历二叉树bt*/
if (bt==NULL) return; /*递归调用的结束条件*/
Visite（bt->data）; /*(1)访问结点的数据域*/
PreOrder（bt->lchild）; /*(2)先序递归遍历bt的左子树*/
PreOrder（bt->rchild）;/*(3)先序递归遍历bt的右子树*/}
例题：
先序遍历序列：A B D C
void preorder(JD *bt)
{ if(bt!=NULL)
{ printf("%d\t",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
（2）中序遍历算法
若二叉树为空树，则空操作；否则，
●先序遍历左子树；
●访问根结点；
●先序遍历右子树。
void InOrder（BiTree bt）{/*先序遍历二叉树bt*/
if (bt==NULL) return; /*递归调用的结束条件*/
InOrder（bt->lchild）; /*(2)先序递归遍历bt的左子树*/ Visite（bt->data）; /*(1)访问结点的数据域*/
InOrder（bt->rchild）;/*(3)先序递归遍历bt的右子树*/} 例题：
中序遍历序列：B D A C
（3）后序遍历算法
若二叉树为空树，则空操作；否则，
●先序遍历左子树；
●先序遍历右子树；
●访问根结点。
void PostOrder（BiTree bt）{/*后序遍历二叉树bt*/
if (bt==NULL) return; /*递归调用的结束条件*/
PostOrder（bt->lchild）;/*(1)后序递归遍历bt的左子树*/
PostOrder（bt->rchild）; /*(2)后序递归遍历bt的右子树
Visite（bt->data）; /*(3)访问结点的数据域*/}
例题：
后序遍历序列：D B C A
（4）层次遍历
所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。层次遍历序列:1 2 3 4 5 6
7、例题：1、
先序序列：A B C D E F G H K
中序序列：B D C A E H G K F
后序序列：D C B H K G F E K
层次序列：A B E C F D G H K
2、
若先序遍历此二叉树，按访问结点的先后次序将结点排列起来，其先序序列为：-+a*b-cd/ef
按中序遍历，其中序序列为：a+b*c-d-e/f
按后序遍历，其后序序列为：abcd-*+ef/ -
8、（1）查询二叉树中某个结点