数据结构,清华大学出版社,严蔚敏吴伟民编著
第一章绪论
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、连续栈(Contiguous Stack)得类型定义
#define MaxStack 50
Typedef struct
{datatype stack[MaxStack];
int top;
}Seqstack;
Seqstack *s;
6、判断栈就是否已满？
viod Push(Seqstack *s, datatype x )
{
if (s->top>=MaxStack-1) printf(“overflow”);
else {
s-> top++;
s->stack[s->top]=x;}
}
7、判断栈就是否为空？
datatype pop(Seqstack *s )
{ if (s->top<0)
{printf(“underflow”); return(NULL);}
return(s->stack[s->top]);
s->top--;
}
8、返回栈顶元素得值，栈不发生变化。
datatype top(Seqstack *s )
{ if (s->top<0)
{printf(“underflow”); return(NULL);}
return(s->stack[s->top]);
}
9、链栈（Linked Stack)得类型定义
栈得链式存储结构称为链栈，它就是运算受限得单链表，插入与删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就就是链表得头指针。
链栈得类型说明如下：
typedef struct stacknode {
datatype data
struct stacknode *next
}stacknode
10、链式栈得特点：
链式栈无栈满问题；空间可扩充；插入与删除仅在栈顶处执行；链式栈得栈顶在链头；适合于多栈操作。
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得左子树*/
严蔚敏版数据结构课后习题答案-完整版
第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据
类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={
严蔚敏数据结构题集(C语言版)完整
严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={
严蔚敏版数据结构复习题
数据结构复习题集 一、判断题 1.线性表的长度是线性表所占用的存储空间的大小。( F ) 2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。( F ) 3.在对链队列做出队操作时，不会改变front指针的值。( F ) 4.如果两个串含有相同的字符，则说它们相等。( F ) 5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。(T ) 6.已知一棵树的先序序列和后序序列，一定能构造出该树。( F ) 7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。(T ) 8.图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。( F ) 9.对一个堆按层次遍历，不一定能得到一个有序序列。(T ) 10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。(T ) 11. 线性表的逻辑顺序与物理顺序总是一致的。( F ) 12. 线性表的顺序存储表示优于链式存储表示。( F ) 13.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。(T ) 14. 二维数组是其数组元素为线性表的线性表。( F )
15. 每种数据结构都应具备三种基本运算：插入、删除和搜 索。(T ) 16.（101，88，46，70，34，39，45，58，66，10）是堆；(T ) 17.将一棵树转换成二叉树后，根结点没有左子树；( F ) 18.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；(F) 19.哈夫曼树是带权外部路径长度最短的树，路径上权值较大的结点离根较近( T ) 20.用一组地址连续的存储单元存放的元素一定构成线性表。(F) 21.堆栈、队列和数组的逻辑结构都是线性表结构。( T ) 22.给定一组权值，可以唯一构造出一棵哈夫曼树。( F) 23.相对于索引文件的基本数据，索引表包含的信息量相对少得多，因此。索引表可以常驻内存。( T) 24.在平均情况下，快速排序法最快，堆积排序法最节省空间。( T) 25.快速排序法是一种稳定性排序法。( F ) 二.选择题: 1.一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（A）。 A.23415 B.54132 C.31245 D.1425 3 2．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（D）。 A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n 3．二叉树在线索化后，仍不能有效求解的问题是（D）。
数据结构老师给的复习要点(严蔚敏版)
第一章 1. 怎样理解“算法+数据结构=程序”这个公式？举例说明。 算法是语句序列解决特定问题的固有程序片段。数据结构是确定数据间的关系。从具体问题抽象出一个合适的数学模型、然后设计一个解决此数学模型的算法，最后编写出程序。寻求数学模型的是指就是数据结构要完成的工作。参看书p1前两段的描述。 2. 数据结构的概念，它包含哪三方面的内容？ 数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间饿关系和操作的学科。参看书p3 包含三方面的内容:1、数据之间的逻辑关系2、数据在计算机中的存储方式3、在数据上定义的运算的集合。 3. 数据、数据元素、数据项的基本概念。举例说明数据元素和数据项的联系与区别。 数据：描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑或处理。 数据项：数据项是具有独立含义的最小标识单位，是数据元的一个具体值，是数据记录中最基本的、不可分的有名数据单位。 例1：class A { int c[123]; int i; }; class B { A a; } B b; b.a是数据项，B是数据元素 例2：一本书的数目信息为一个数据元素，而数目信息中每一项（如书名、作者名等）为一个数据项 4. 从逻辑结构来看，数据结构有哪四种基本结构，各自的特点是什么？ 1、集合（数据元素之间同属于一个集合，再无其他关系） 2、线性结构（数据元素之间存在一对一的关系） 3、树形结构（数据元素之间一对多的关系） 4、图状结构或网状结构（数据元素之间多对多的关系） 5. 从物理结构来看，数据结构有哪两种基本结构，各自的特点是什么？ 1、顺序存储结构 特点：借助元素在存储器中的相应位置来表示数据元素之间的逻辑关系。 2、链式存储结构 特定：借助元素在存储地址的指针表示数据元素之间的逻辑关系。 6. 算法的5个特征，4个评价标准是什么？ 特征:有穷性、确定性、可行性、输入、输出。 评价标准：正确性、可读性、健壮性、效率与低存储量需求。 7. 描述时间复杂度。
数据结构讲义严蔚敏版第4章
? 4.2 基本体的表面取点 ? 4.3 平面与立体表面的交线 结束放映 ? 4.1 基本体的三视图 ? 4.4 立体与立体表面的交线 ? 4.5 基本体三维造型
4.1 基本体的三视图 常见的基本几何体 平面基本体曲面基本体
一、画基本体三视图的方法步骤 1 .确定三个视图的位置。选择立体上的一个点或立体的对 称中心线、主要棱线、平面等作为画图参考基准；先画 出它们的三个视图（布图），注意要做到横平竖直。 2.画出反映立体主要形状特征（实形）的视图。 3 .再根据立体的长、宽、高尺寸（相对坐标），依照“长 对正、高平齐、宽相等”的规律，完成另外两个视图。 4 .视图完成后，应擦去作图辅助线。 ?立体是具有三维坐标的实心体，研究的立体投影是研究立体表面的投影。 ?立体是有具体形状和尺寸大小的形体。画三视图时，主要用长、宽、高方向的相对坐标，与投影轴无关，从这里开始不再画出投影轴。
开始画三视图！ 在图示位置时,五棱柱的上 下两底面为水平面,在俯视图中反映实形（五边形）.后侧棱面是正平面,其余四个侧棱面是铅垂面,它们的水平投影都积聚成直线,与五边形的边重合。 ⑵ 五棱柱的三视图 ⑴ 棱柱的组成 由上下两个底面和若干侧棱面组成。侧棱面与侧棱面的交线叫侧棱线，侧棱线相互平行。 1.棱柱 二、平面基本体 ● a 0 ● a 0" ● a 0' ● (１)布图:选点ＡＯ画图参考基准，画出其三个投影图。 ２) 画出反映立体主要形状特征的俯视图。 (３) 由“长对正”和立体的高度画出主视图。 ４利用“宽相等”和"高平齐”画出左（二求三）。 三视图概念
严蔚敏版数据结构建立学生信息单链表C语言版适合VC++
#include
void ClearList_L(Linklist L)/*将L重置为空表*/ { Linklist p; if(!L) printf("ERROR\n"); else { while(L->next) { p=L->next; L->next=p->next; free(p); } printf("OK\n"); } } void ListEmpty_L(Linklist L)/*L为空表返回TRUE，否则返回FALSE*/ { if(!L) printf("ERROR\n"); else { if(!L->next) printf("TRUE\n"); else printf("FLASE\n"); } } int ListLength_L(Linklist L)/*返回L中数据元素个数*/ { int i=0; Linklist p=L; if(!L) return 0; else { while(p) { i++; p=p->next; } return i; } }
严蔚敏数据结构复习整理完整版
1.复杂性分析 对各种操作的时间复杂性的分析。 主要是链表，树，排序等简单一些的分析。 分析的时候，从简单的入手，学会方法。 后续的各种豆可能让你分析时间复杂度。 线性链表（顺序表和单链表） 链表循环链表 双向链表 2.线性结构队列（循环队列） 栈 链表主要操作：找某一个元素，插入一个（在哪个位置增加），删除一个（在哪个位置删除）。栈：查找，插入（位置固定），删除（位置固定） 队列：查找，插入（位置固定），删除（位置固定） 顺序表（可以视为一个数组） 单链表： （删除）
（插入）
倒置： （查找）
循环链表 双向链表 栈： （插入删除查找）
队列 （插入删除查找） 循环队列的实现，并不是像上面的图那样，实现了一个循环的样子。 3.二叉树 基本概念 二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。 二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。 二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别： 1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 2. 树的结点无左、右之分，而二叉树的结点有左、右之分。
二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态： (1)空二叉树——如图(a)； (2)只有一个根结点的二叉树——如图(b)； (3)只有左子树——如图(c)； (4)只有右子树——如图(d)； (5)完全二叉树——如图(e) 注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形 性质 (1) 在非空二叉树中，第i层的结点总数不超过, i>=1； (2) 深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点； (3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1； (4) 具有n个结点的完全二叉树的深度为 (5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系： 若I为结点编号则如果I>1，则其父结点的编号为I/2； 如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子； 如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。 (6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。 （7）设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i 存储结构
严蔚敏数据结构讲义(第03章 栈和队列)
第03章栈和队列 3.1栈的基本概念 （一）栈顶top位置的说明： 1.在空栈中，top和base都指向整个栈的起始地址（也就是即将分配的第一个元素的地址）； 2.在非空栈中，top始终是指向栈顶元素的下一个元素的地址。 （二）入栈操作（先压后加）：Stack[top++]=e （三）出栈操作（先减后弹）：e = Stack[--top] （四）栈不存在的判断条件：base==NULL （五）栈空的判断条件：base==top （六）栈满的判断条件：top – base = MaxSize 三、顺序栈的C语言实现 typedef struct{ SElemType *base; //栈底指针 SElemType *top; //栈顶指针 int StackSize; //顺序栈的初始容量（初始分配的能够容纳的元素个数） }SqStack; 四、顺序栈的操作 1.初始化栈——构造一个空栈 Status InitStack(SqStack &S) { S.base = (SElemType*)malloc(Stack_Init_Size*sizeof(SElemType)); if(S.base==NULL) exit(OverFlow); //存储空间分配失败 S.top = S.base; S.StackSize = Stack_Init_Size; } 2.获取栈顶元素——若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR Status GetTop(SqStack S,SElemType &e) { if(S.top==S.base) return ERROR; //栈空 e = *(top – 1); return OK; } 3.入栈——插入元素e作为新的栈顶元素 Status Push(SqStack &S,SElemType e) { if(S.top – S.base >= S.StackSize) //栈已满，需要追加存储空间 { S.base = (SElemType*)realloc(S.base,(S.StackSize+StackIncrement)*sizeof(SElemType)); if(!S.base) exit(OverFlow); //存储空间分配失败 S.top = S.base + S.StackSize; S.StackSize += StackIncrement; } *S.top++ = e; //*指针运算符和++自加运算符优先级相同，但是其结合方向是自右向左 Return OK; }
- 严蔚敏数据结构题集(C语言版)完整
- 数据结构习题集答案_C语言版(严蔚敏 吴伟民)
- 清华大学严蔚敏版数据结构讲义PPT
- 数据结构C语言版(严蔚敏) 教材讲义242页PPT
- 严蔚敏版数据结构复习题
- 严蔚敏版数据结构课后习题答案-完整版
- 严蔚敏《数据结构》(C语言版)笔记和习题(含考研真题)详解
- 严蔚敏版数据结构课后习题答案-完整版
- 清华大学严蔚敏数据结构习题集(C版)答案
- 严蔚敏《数据结构(c语言版)习题集》全答案
- 严蔚敏数据结构题集C语言版完整与答案
- 数据结构讲义严蔚敏版第4章
- 2021年北京林业大学839数据结构考研精品资料之严蔚敏《数据结构(C语言版)》考研核心题库之算法设计题精编
- (完整版)严蔚敏数据结构
- 数据结构老师给的复习要点(严蔚敏版)
- 严蔚敏版数据结构建立学生信息单链表C语言版适合VC++
- 数据结构(C语言版)(严蔚敏)
- 【精品】严蔚敏《数据结构》(C语言版)【教材精讲+考研真题解析】讲义
- 严蔚敏数据结构复习整理完整版
- 严蔚敏版数据结构课后习题答案-完整版