下载文档原格式
第一章绪论1、数据结构是计算机中存储、组织数据的方式。
精心选择的数据结构可以带来最优效率的算法。
2、程序设计=算法+数据结构3、解决问题方法的效率：●●●4、5、6、7、8、9、数据结构是带结构的数据元素的集合。
10、不同的关系构成不同的结构。
11、次序关系：{<ai,ai+1>|i=1,2,3,4,5,6}12、对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的基本操作；2）数据的存储结构，数据结构基本操作的实现；13、数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。
数据结构的基本操作：14、1516171819、链接存储结构特点：●比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成)。
●逻辑上相邻的节点物理上不必相邻。
●插入、删除灵活(不必移动节点，只要改变节点中的指针)。
20、数据类型是一个值的集合和定义在此集合上的一组操作的总称。
21、ADT有两个重要特征:数据抽象和数据封装。
22、抽象数据类型(AbstractDataType简称ADT)：是指一个数学模型以及定义在此数学模型上的一组操作。
232424252627第二章线性表1、线性结构的特点：在数据元素中的非空有限集中。
（1）存在唯一的一个被称作“第一”的数据元素；（2）存在唯一的一个被称作“最后一个”的数据元素；（3）除第一个外，集合中的每一个数据元素均只有一个前驱；（4）除最后一个外，集合中的每一个数据元素均只有一个后继。
2、线性表(LinearList)：一个线性表是n个数据元素的有限序列。
3、线性表的顺序存储实现：typedefstruct{ElementTypeData[MAXSIZE];4}5while(i<=PtrL->Last&&PtrL->Data[i]!=X)i++;if(i>PtrL->Last)return-1;/*如果没找到，返回-1*/ elsereturni;/*找到后返回的是存储位置*/}6、插入算法voidInsert(ElementTypeX,inti,List*PtrL){intj;if(PtrL->Last==MAXSIZE-1){/*表空间已满，不能插入*/ printf(＂表满＂);}}}7voidDelete(inti,List*PtrL){intj;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}}9（1List*FindKth(intK,List*PtrL){List*p=PtrL;inti=1;while(p!=NULL&&i<K){p=p->Next;i++;}if(i==K)returnp;/*找到第K个，返回指针*/elsereturnNULL;/*}（2{}10if(i==1){/*新结点插入在表头*/s=(List*)malloc(sizeof(List));/*申请、填装结点*/ s->Data=X;s->Next=PtrL;returns;/*返回新表头指针*/}p=FindKth(i-1,PtrL);/*查找第i-1个结点*/ if(p==NULL){/*第i-1个不存在，不能插入*/ printf(＂参数i错＂);returnNULL;}}11PtrL=PtrL->Next;/*从链表中删除*/free(s);/*释放被删除结点*/returnPtrL;}p=FindKth(i-1,PtrL);/*查找第i-1个结点*/if(p==NULL){printf(“第%d个结点不存在”,i-1);returnNULL;}elseif(p->Next==NULL){printf(“第%d个结点不存在”,i);returnNULL;}else{}}121314①单链表②双链表③单循环链表④顺序表第三章Chapter3栈(stacks)和队列（queues）1、栈是限定仅能在表尾一端进行插入、删除操作的线性表。
吉首大学题库一、一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（）。
A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。
A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（）。
A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A. O(n)B. O(1)C. O(log2n)D. O(n2)二、二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。
当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。
第一章绪论之五兆芳芳创作1、数据结构是计较机中存储、组织数据的方法.精心选择的数据结构可以带来最优效率的算法.2、程序设计=算法+数据结构3、解决问题办法的效率：●跟数据的组织方法有关●跟空间的利用效率有关●跟算法的巧妙程度有关4、数据：所有能输入到计较机中,且被计较机处理的符号的荟萃，是计较机操纵对象的总称；是计较机处理的信息的某种特定的符号暗示形式.5、数据元素：数据中的一个“个别”,数据结构中讨论的根本单位.相当于“记实”,在计较机程序中通常作为一个整体考虑和处理.6、数据项: 相当于记实的“域”, 是数据的不成联系的最小单位,如学号.数据元素是数据项的荟萃.7、数据对象：性质相同的数据元素的荟萃.例如: 所有运动员的记实荟萃8、数据结构：是相互间存在某种关系的数据元素荟萃.9、数据结构是带结构的数据元素的荟萃.10、不合的关系组成不合的结构.11、次序关系：{<ai,ai+1>|i=1,2,3,4,5,6}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）按值查找: FindList *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!=NULL14、如果最经常使用的操纵是取第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 50Typedef 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 datastruct stacknode *next}stacknode10、链式栈的特点：链式栈无栈满问题；空间可扩充；拔出与删除仅在栈顶处执行；链式栈的栈顶在链头；适合于多栈操纵.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）abcde23、若已知一个栈的进栈序列是p1，p2，p3，…，pn .其输出序列为1，2，3，…，n ，若p3=1，则p1为 C .（A）可能是2（B）一定是2（C）不成能是2 （D）不成能是324、设有一个空栈，栈顶指针为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 ⑧1003H24、一个队列的入队序列是若1，2，3，4，则队列的输出序列是 B .（A）4，3，2，1 （B）1，2，3，4（C）1，4，3，2 （D）3，2，4，125、若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值辨别为0和3.当从队列中删除一个元素，再参加两个元素后，rear和front的值辨别是 B .（A）1和5 （B）2和4 （C）4和2 （D）5和126、有5个元素，其入栈次序为A、B、C、D、E，在各类可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？C、D、B、A、E C、D、E、B、AC、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(m0)棵互不相交的树的荟萃例题: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 100Typedef 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 Cvoid 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 67、例题：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 K2、若先序遍历此二叉树，按拜访结点的先后次序将结点排列起来，其先序序列为：-+a*b-cd/ef按中序遍历，其中序序列为：a+b*c-d-e/f按后序遍历，其后序序列为：abcd-*+ef/ -8、（1）查询二叉树中某个结点Status Preorder (BiTree T, ElemType x, BiTree &p) {// 若二叉树中存在和x 相同的元素，则p 指向该结点并//前往OK,// 不然前往FALSEif (T) {if (T->data= =x) { p = T; return OK,}else {if (Preorder(T->lchild, x, p)）return OK;else (Preorder(T->rchild, x, p)) return OK;}//else}//ifelse return FALSE;}（2）计较二叉树中叶子结点的个数int CountLeaf (BiTree T){//前往指针T所指二叉树中所有叶子结点个数if (!T ) return 0;if (!T->lchild && !T->rchild) return 1;else{m = CountLeaf( T->lchild);n = CountLeaf( T->rchild);return (m+n);} //else } // CountLeaf（3）求二叉树的深度(后序遍历)int Depth (BiTree T ){ // 前往二叉树的深度if ( !T ) depthval = 0; else {depthLeft = Depth( T->lchild );depthRight= Depth( T->rchild );depthval = 1 + (depthLeft > depthRight ?depthLeft : depthRight);}return depthval;}（4）按先序遍历序列成立二叉树Status CreateBiTree (BiTree &T ){ //按先序次序输入二叉树中结点的值（一个字符），空格字符暗示空树，机关二叉链表暗示的二叉树Tscanf (&ch);if ( ch==‘‘ ) T=NULL; else {if(!T=(BiTNode *)malloc(sizeof(BiTNode)))) exit (OVERFLOW);T->data=ch; //生成根结点CreateBiTree(T->lchild);//机关左子树CreateBiTree(T->rchild);//机关右子树}Return OK; }//CreateBiTree9、遍历二叉树的非递归算法（1）先序遍历二叉树的非递归算法void inorder(JD *r)//先序遍历二叉树非递归算法// { int i=0; JD *p,*s[M]; p=r;do {while(p!=NULL) {printf("%d\t",p->data);if (p->rc!=NULL)s[i++]=p->rc;p=p->lc;}if ( i > 0) p=s[--i];}while( i>0 || p!=NULL); }（2）中序遍历二叉树的非递归算法void inorder(JD *r)//先序遍历二叉树非递归算法// { int i=0; JD *p,*s[M]; p=r;do {while(p!=NULL) {{s[i++]=p; p=p->lc;}if (i>0){p=s[--i];printf("%d\t",p->data);p=p->lc;}if ( i > 0) p=s[--i];}while( i>0 || p!=NULL); }（3）后序遍历二叉树的非递归算法void inorder(JD *r)//先序遍历二叉树非递归算法//{ int s2[M],b,i=0; JD *p,*s1[M]; p=r;do {while(p!=NULL) {{s1[i-1]=p;s2[i++]=0;p=p->lc;}while (i>0 && (s2[i-1]=1)){p=s1[--i]; printf(“%d\t”,p->data ); }if (i>0){p=s[--i];printf("%d\t",p->data);p=p->lc;}if ( i > 0){ s2[i-1]=1; p=s1[i-1]; p=p->rc; }}while( i>0); }11、线索二叉树：以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不克不及在结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态进程中才干得到，为了能保管所需的信息，可增加标记域;Ltag=0 ，lchild 域指示结点的左孩子；Ltag=1，lchild 域指示结点的前驱.Rtag=0，rchild 域指示结点的右孩子；Rtag=1，rchild 域指示结点的后驱.以这种结构组成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索，加上线索的二叉树称之为线索二叉树.（1）先序线索二叉树（2）中序线索二叉树（3）后序线索二叉树12、树的存储结构○1双亲暗示法#define MAX_TREE_SIZE 100typedef struct PTNode {//结点结构ElemType data;int parent; // 双亲位置域} PTNode;typedef struct {//树结构PTNode nodes[MAX_TREE_SIZE];int r, n; // 根结点的位置和结点个数} PTree;○2孩子暗示法○3带双亲的孩子链表○4孩子兄弟暗示法链表中每个结点的两个指针域辨别指向其第一个孩子结点和下一个兄弟结点.typedef struct node{ datatype data;struct node *fch, *nsib;}JD;13、树和森林与二叉树的转换加线：在兄弟之间加一连线.抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系，旋转：以树的根结点为轴心，将整树顺时针转45°.13、将二叉树转换成树●加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来.●抹线：抹掉原二叉树中双亲与右孩子之间的连线●调整：将结点按条理排列，形成树结构14、森林转换二叉树（1）将各棵树辨别转换成二叉树.（2）将每棵树的根结点用线相连.（3）以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，组成二叉树型结构14、二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之酿成孤立的二叉树.复原：将孤立的二叉树复原成15、树和森林的遍历树的遍历两种次序遍历树的办法：一种是先根（次序）遍历树，即先拜访树的根结点，然后依次先根遍历根的每棵子树；一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后拜访根结点.森林的遍历先序遍历：A B C D E F G H I J中序遍历：B C D A F E H J I G16、赫夫曼树及其应用例题：w={5, 29, 7, 8, 14, 23, 3, 11}习题：1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法B .（A）正确（B）错误2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是D .（A）空或只有一个结点（B）完全二叉树（C）二叉排序树（D）高度等于其节点数3、深度为5的二叉树至多有C 个结点.（A）16 （B）32 （C）31 （D）104、按照使用频率为5个字符设计的赫夫曼编码不成能是C .（A）111，110，10，01，00（B）000，001，010，011，1（C）100，11，10，1，0（D）001，000，01，11，105、树和二叉树的主要不同是（1）树的结点个数至少为1，而二叉树的结点个数可以为0（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为2（3）树的结点无左、右之分，而二叉树的结点右左、右之分.6、深度为k的完全二叉树至少有个结点，至多有个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号.7、一棵二叉树的第i(i1)层最多有个结点；一棵有n（n>0）个结点的满二叉树共有个叶子结点和个非叶子结点.8、已知二叉树的先序、中序和后序序列辨别如下，其中有一些看不清的字母用*暗示，请机关出一棵适合条件的二叉树并画出该二叉树.●先序序列是：*BC**FG●中序序列是：CB*EAG*●后序序列是：*EDB*FA9、将右图所示的树转化为二叉树，并写出先序遍历，中序遍历和后序遍历的结果.解：先序：ABEFGCDHI中序：EFGBCHIDA后序：GFEIHDCBA10、设给定权集w={2，3，4，7，8，9}，试机关关于w的一棵赫夫曼树，并求其加权路径长度WPL.WPL=(9+7+8)*2+4*3+(2+3)*4=80第十章内部排序1、内排序大致可分为五类：拔出排序、互换排序、选择排序、归并排序和分派排序.2、直接拔出排序直接拔出的算法实现void sort(NODE array[],int n)//待排序元素用一个数组array[ ] 暗示，数组有n 个元素 { int i, j;NODE x; // x 为中间结点变量for ( i=1; i<n; i++) //i 暗示拔出次数,共进行n-1次拔出{ x=array[i]; //把待排序元素赋给 xj=i-1;while ((j>=0)&& ( x.key<array[j].key)){array[j+1]=array[j]; j--; } // 顺序比较和移动 array[j+1]=x; }}例如，n=6，数组R 的六个排序码辨别为：17，3，25，14，20，9.它的直接拔出排序的执行进程如图7-1所示. 直接拔出排序的时间庞杂度为O （n2）. 直接拔出算法的元素移动是顺序的，该办法是稳定的. 3、希尔排序 希尔排序的时间庞杂性在O （nlog2n ）和O （n2 ）之间，大致为O （n1.3）.由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改动相同排序码元素的原始顺序，因此希尔0 1 2 3 4 5初始状态 (17 ) 3 25 14 20 9 第一次插入 (3 17 ) 25 14 20 9 第二次插入 (3 17 25 ) 14 20 9 第三次插入 (3 14 17 25 ) 20 9 第四次插入 (3 14 17 20 25 ) 9第五次插入 (3 9 14 17 20 25)图10-1直接插入排序示例排序是不稳定的.例如，n=8，数组array[ ]的八个元素辨别为：91，67，35，62，29，72，46，57.下面用图10-2给出希尔排序算法的执行进程.4、互换排序1）冒泡排序冒泡排序的算法实现void Bubblesort( NODE array[],int n){ int i, j, flag; //当flag为0则停止排序NODE temp;for ( i=1; i<n; i++) // i 暗示趟数，最多n-1趟{ flag=0; //开始时元素未互换for ( j=n-1; j>=i; j--)if (array[j].key<array[j-1].key) //产生逆序temp=array[j];array[j]=array[j-1];array[j-1]=temp;flag=1; } //互换，并标识表记标帜产生了互换if(flag==0) break; }}例如，n=6，数组R的六个排序码辨别为：17，3，25，14，20，9.下面用图10-3给出冒泡排序算法的执行进程.冒泡排序算法的时间庞杂度为O（n2）.由于其中的元素移动较多，所以属于内排序中速度较慢的一种.因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法.2）快速排序快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种.快速排序的算法实现void quicksort(NODE array[],int start , int end){ int i , j; NODE mid;if (start>=end) return;i=start;j=end;mid=array[i];while (i<j){ while (i<j && array[j].key>mid.key) j--;if (i<j) {array[i]=array[j]; i++; }while (i<j && array[i].key<=mid.key) i++;if (i<j) {array[j]=array[i]; j--; } } //一次划分得到基准值的正确位置array[i]=mid;quicksort(array,start,i-1); //递归调用左子区间quicksort(array,i+1,end); }//递归调用右子区间例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图10-4所示.快速排序所占用的帮助空间为栈的深度，故最好的空间庞杂度为O（log2n），最坏的空间庞杂度为O(n).快速排序是一种不稳定的排序办法.5、选择排序1）直接选择排序例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序进程如图7-5所示.直接选择排序的时间庞杂度为O(n2)数量级2）树形选择排序例如，给定排序码头50，37，66，98，75，12，26，49，树形选择排序进程见图7-7.3）堆排序例如，给定排序码49，38，65，97，76，13，27，70，成立初始堆的进程如图7-8所示.按条理遍历完全二叉树，得到一个由大到小排列的有序序列：97，76，70，65，49，38，27，13每次筛选运算的时间庞杂度为O(log2n)，故整个堆排序进程的时间庞杂度为O(nlog2n).5、归并排序例如，给定排序码46，55，13，42，94，05，17，70，二路归并排序进程如图7-10所示.二路归并排序的时间庞杂度为O(nlog2n).6、各类内排序办法的比较和选择1）从时间庞杂度比较从平均时间庞杂度来考虑，直接拔出排序、冒泡排序、直接选择排序是三种复杂的排序办法，时间庞杂度都为O(n2)，而快速排序、堆排序、二路归并排序的时间庞杂度都为O(nlog2n)，希尔排序的庞杂度介于这两者之间.若从最好的时间庞杂度考虑，则直接拔出排序和冒泡排序的时间庞杂度最好，为O(n)，其它的最好情形同平均情形相同.若从最坏的时间庞杂度考虑，则快速排序的为O(n2)，直接拔出排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将下降一半，最坏情形对直接选择排序、堆排序和归并排序影响不大.2）从空间庞杂度比较归并排序的空间庞杂度最大，为O(n)，快速排序的空间庞杂度为O(log2n)，其它排序的空间庞杂度为O（1）.3）从稳定性比较直接拔出排序、冒泡排序、归并排序是稳定的排序办法，而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序办法.4）从算法复杂性比较直接拔出排序、冒泡排序、直接选择排序都是复杂的排序办法，算法复杂，易于理解，而希尔排序、快速排序、堆排序、归并排序都是改良型的排序办法，算法比复杂排序要庞杂得多，也难于理解.8、各类内排序办法的选择1）从时间庞杂度选择对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选复杂的排序办法.2）从空间庞杂度选择尽量选空间庞杂度为O（1）的排序办法，其次选空间庞杂度为O(log2n)的快速排序办法，最后才选空间庞杂度为O（n）二路归并排序的排序办法.3）一般选择法则●当待排序元素的个数n较大，排序码散布是随机，而对稳定性不做要求时，则采取快速排序为宜.●当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采取二路归并排序为宜.●当待排序元素的个数n大，排序码散布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采取堆排序或二路归并排序为宜.●当待排序元素的个数n小，元素根本有序或散布较随机，。
第一章绪论1、数据结构是计算机中存储、组织数据的方式。
精心选择的数据结构可以带来最优效率的算法。
2、程序设计= 算法+数据结构3、解决问题方法的效率：●跟数据的组织方式有关●跟空间的利用效率有关●跟算法的巧妙程度有关4、数据：所有能输入到计算机中,且被计算机处理的符号的集合，是计算机操作对象的总称；是计算机处理的信息的某种特定的符号表示形式。
5、数据元素：数据中的一个“个体”,数据结构中讨论的基本单位。
相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。
6、数据项: 相当于记录的“域”, 是数据的不可分割的最小单位,如学号。
数据元素是数据项的集合。
7、数据对象：性质相同的数据元素的集合.例如: 所有运动员的记录集合8、数据结构：是相互间存在某种关系的数据元素集合。
9、数据结构是带结构的数据元素的集合。
10、不同的关系构成不同的结构。
11、次序关系：{<ai,ai+1>|i=1,2,3,4,5,6}12、对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的基本操作；2）数据的存储结构，数据结构基本操作的实现；13、数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。
数据结构的基本操作：指对数据结构的加工处理。
14、数据的存储结构(物理结构)：数据结构在计算机内存中的表示。
数据结构基本操作的实现：基本操作在计算机上的实现（方法)。
15、数据结构的有关概念16、数据元素的4类的基本结构：○1集合；○2线性结构：结构中数据元素之间存在一对一的关系；○3树形结构：结构中数据元素之间存在一对多的关系；○4图状结构或网状结构：结构中数据元素之间存在多对多的关系。
17、C语言的优点：C语言可以直接操作内存。
18、每个节点都由两部分组成：数据域和指针域。
19、链接存储结构特点：●比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成)。
●逻辑上相邻的节点物理上不必相邻。
