绪论 数据结构概念 概念：
数据元素：一个数据体，考虑为一个人，一份订单… 数据项：数据体内的各项，人的信息项，订单的信息项… 数据对象：具有相同性质，数据元素的集合 数据类型：是指一个值得集合，和定义在此集合上一组操作的总称原子类型：基本数据类型 结构类型：结构体(可以再分为若干分量) 抽象数据类型：抽象数据组织及与之相关操作(描述了数据的逻辑结构和抽象运算)，可以用其定义一个完整的数据结构 数据结构：相互间存在一种或多种特定关系的数据元素的集合 数据结构三要素：
逻辑结构存储结构数据的运算：比如，栈的抽象运算是先进后出
课后习题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1.数据的逻辑结构独立于其存储结构，逻辑结构是抽象表达方式，例如图的逻辑结构，采用顶点与边 而图的存储结构采用二维数组(顺序存储)或链表结点(链式存储) 2.存储数据时，不仅要存储数据的值，还要存储数据元素之间的关系(例如顺序表存储元素有下标，表示与其他数据元素的位置关系) 3.对于两种不同的数据结构，他们的逻辑结构完全有可能相同， 4.举例说明，对相同的逻辑结构，同一种运算在不同的存储方式下实现时，其运算效率不同？ 线性表，可以顺序存储，可以链式存储，顺序存储方式，插入删除操作要平均移动一半元素，O(n) 链式存储方式，插入删除时间复杂度O(1) 5.以下与数据存储结构无关的术语是：D A 循环队列 B 链表 C 哈希表 D 栈 解析：栈是一种抽象数据类型，可采用顺序存储，链式存储，只表示逻辑结构 6.以下属于逻辑结构的是（c）。 A.顺序表 B.哈希表 C.有序表 ·D.单链表 顺序表体现数组存储方式，哈希表体现散列存储方式，单链表体现链式存方式，有序表体现有序的逻辑结构
算法 算法：求解问题的步骤
算法特性 ：
有穷性，有限步骤内完成，有穷时间内完成 确定性，意义明确，无歧义；给定相同的输入，输出结果确定唯一 可行性，可以通过基本运算执行有限次来实现 输入，0个或多个输入 输出，1个或多个输出 好的算法具备特质 ：
正确性，能正确实现目的 可读性，容易理解阅读 健壮性，可以灵活处理数据中的非法数据，给出反应进行处理 高效率地存储需求，花费时间少(时间复杂度低)，不费内存(空间复杂度低) 时间复杂度 ：
空间复杂度 ：普通程序 结论 1 只需关注存储空间大小与问题规模相关的变量 2 分析所占空间x与问题规模n的关系 x=f(n) 3 x的数量级O(x)就是算法空间复杂度S(n)
递归程序 结论 1 找到递归深度x与问题规模n的关系 2 x的数量级O(x)就是算法空间复杂度S(n)
线性表 序号 总结 定义 数据类型同类型、有限、有序(先后顺序) 位序 线性表数据元素的位序从1开始(数组下标以0开始) 基本操作 创销、增删改查；判空、判长、打印输出 注意 函数名要有可读性、见名知意 包括 链表(链式存储)、顺序表(顺序存储)
1 2 3 4 5 6 7 8 9 10 构造方法框架： InitL1st(&L）:初始化表。构造一个空的线性表。 Length(L):求表长。返回线性表L的长度，即L中数据元素的个数。 LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。 GetE1em(L,i):按位查找操作。获取表L中第1个位置的元素的值。 ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e. ListDelete(&L,i,&e):别除操作，别除表L中第1个位置的元素，并用e返回别除元素的值。 Pr1 ntList(L):输出操作。按前后顺序输出线性表L的所有元素值。 Empty(L):判空操作。若L为空表，则返回true,否则返回false. DestroyList(&L):销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
线性表顺序存储 顺序表 顺序表定义 顺序表实现方式：静态分配：ElemType data[MaxSize]（存储空间不可调控）
1 2 3 4 5 #define Maxsize 10 typedef struct {ElemType data [MaxSize]; int Length;}SqList;
动态分配：ElemType * data （存储空间可调控）
1 2 3 4 5 6 #define Initsize10 typedef struct {ElemType *data ; int Maxsize;int Length;}SqList;
1 2 3 4 5 6 7 void InitList (SeqList &L) { L.data=(int *)malloc (Initsize*sizeof (int )); L.length=0 ; L.MaxSize=Initsize; }
1 2 3 4 5 6 7 8 9 10 void Increasesize (SeqList &L,int len) { int *p=L.data; L.data=(int *)malloc ((L.MaxSize+len)*sizeof (int )); for (int i=0 ;i<L.length;i++){ L.data[i]=p[i]; } L.MaxSize=L.MaxSize+len; free (p); }
顺序表特点
随机访问：可以在O(1)时间内找到第i给元素 存储密度高，只能存储数据本身，不能存储指针信息 拓展容量不方便：每次拓展容量都需要开拓一个新的内存空间，并复制过去 插入删除元素不方便，需要移动大量的元素 顺序表插入操作 健壮性，异常处理 ：
返回布尔型变量用于判断操作是否成功 方法要进行，判满，判断插入位置是否有效 1 2 3 4 5 6 7 8 9 10 11 12 bool ListInsert (SqList&L int i，int e) { if （i<1ll i>L.length+1 ） return false ； if （L.length>=MaxSize） return false ； return false ； for （intj=L.length;j>=i；j--） L.data[j]=L.data[j-1 ]； L.data[i-1 ]=e； L.length++； return true ；
顺序表的删除操作 健壮性异常处理
返回布尔型变量用于判断操作是否成功 判空、判断删除位置i是否有效 要加一个变量e(注意要&e)，将被删除元素的值带回来 1 2 3 4 5 6 7 8 9 bool ListDelete (SqList &L,int i,int &e) {if (i<1 i>L.length) return false ; e=L.data[i-1 ]; for (int j=i;j<L.length;j++) L.data[j-1 ]=L.data[j]; L.length--; return true ;}
顺序表的查找 按位查找 1 2 3 ElemType GetElem (SeqList L,int i) { return L.data[i-1 ]; }
时间复杂度：O(1)
按值查找 1 2 3 4 5 int LocateElem (SeqList L,ElemType e) { for (int i=0 ;i<L.length;1 ++) if (L.data[i]==e) return i+1 ; return 0 ;
时间复杂度：
最好：O(1) 查找元素在表头 最坏：O(n) 查找元素在表尾 平均：O(n) 循环n+1/2次 对称矩阵的压缩存储
课后习题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 bool delet_min (SqList T,int &e) { if (T.length==0 ){ return false ; } int min=0 ; for (int i=1 ;i<T.length;i++){ if (T.data[i]<T.data[min]){ min=i; } } e=T.data[min]; T.data[min]=T.data[length-1 ]; T.length--; }
1 2 3 4 5 6 7 8 9 10 11 12 13 void inverse (SqList T) { int temp; for (int i=0 ;i<T.length/2 ;i++){ temp=T.data[i]; T.data[i]=T.data[T.length-i]; T.data[T.length-i]=temp; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 void del_x (Sqlist &T,int x) { int k=0 ; for (int i=0 ;i<T.length;i++){ if (T.data[i]!=x){ T.data[k]=T.data[i]; k++; } } T.length=k; } void del_x (Sqlist &L,int x) { int k=0 ; for (int i=0 ;i<L.length;i++){ if (T.data[i]==x){ k++; }else { L.data[i-k]=L.data[i]; } } L.len=L.len-k; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 bool delet_st (Sqlist &T,int s,int t) { if (s>=t||T.length==0 ){ return false ; } int k=0 ; for (int i=0 ;i<T.length;i++){ if (!(T.data[i]>s&&T.data[i]<t)){ T.data[k]=T.data[i]; k++; } } T.length=k; return true ; } bool delet_st (Sqlist &L,int s,int t) { if (s>=t||T.length==0 ){ return false ; } int k=0 ; for (int i=0 ;i<L.length;i++){ if (L.data[i]>s&&L.data[i]<t){ k++; }else { L.data[i-k]=L.data[i]; } } L.length-=k; return true ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 typedef struct SqTable { int * data; int length; }Sqlist; bool delet (Sqlist &T,int pos) { if (T.length==0 ){ return false ; } for (int i=pos+1 ;i<T.length;i++){ T.data[i-1 ]=T.data[i]; } T.length--; return true ;} void delet_repeat (Sqlist &T) { if (T.length==0 ){ return ; } int i=0 ; while (i<T.length-1 ){ for (int j=i+1 ;j<T.length;j++){ if (j==T.length){ break ; } if (T.data[i]==T.data[j]){ delet(T,j); j--; } } i++; } } void delet_repeat (Sqlist &T) { qsort(T.data, T.length, sizeof (int ), cmp); int i = 0 ; for (int j = 1 ; j < T.length; j++) { if (T.data[i] != T.data[j]) { i++; T.data[i] = T.data[j]; } } T.length = i + 1 ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 Sqlist merge (Sqlist T1,Sqlist T2) { Sqlist T3; T3.data=(int *)malloc (sizeof (int )*(T1.length+T2.length)); int k=0 ; int i=0 ; int j=0 ; while (i<T1.length&&j<T2.length){ if (T1.data[i]<=T2.data[j]){ T3.data[k]=T1.data[i]; i++; k++; }else { T3.data[k]=T2.data[j]; j++; k++; } } while (i<T1.length){ T3.data[k]=T1.data[i]; k++; i++; } while (j<T2.length){ T3.data[k]=T2.data[j]; k++; j++; } T3.length=k; return T3; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 void reserve_singel (Sqlist &T,int bengin,int end) { if (T.length<=1 ){ return ； } for (begin,end;begin<end;begin++,end--){ int temp; temp=T.data[begin]; T.data[begin]=T.data[end]; T.data[end]=temp; } } void reserve_all (Sqlist &T,int p) { reserve_singel(T,0 ,p-1 ); reserve_singel(T,p,n-1 ); reserve_singel(T,0 ,n-1 ); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 void Swap (SSTable &S,int i) { if (i>=S.len){ return ; } int temp; temp=S.data[i]; S.data[i]=S.data[i+1 ]; S.data[i+1 ]=temp; } bool Insert (SSTable &S,int x,int pos) { for (int i=S.len-1 ;i>=pos;i--){ S.data[i+1 ]=S.data[i]; } S.len++; } void Binary_Search_insert (SSTable S,int x) { int low=0 ,high=S.len,mid; while (low<=high){ mid=(low+high)/2 ; if (S.data[mid]==x){ Swap(S,mid); return ; }else if (S.data[mid]<x){ low=mid+1 ; }else { high=mid-1 ; } } Insert(S,x,low); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int findMissMin (int A[],int n) { int *B; B=(int *)malloc (sizeof (int )*n); memset (B,0 ,sizeof (int )*n); for (int i=0 ;i<n;i++){ if (A[i]>0 &&A[i]<=n){ B[A[i]-1 ]=1 ; } } for (int i=0 ;i<n;i++){ if (B[i]==0 ){ break ; } } return i+1 ; }
线性表链式存储 单链表 单链表的定义 1 2 3 4 5 typedef struct LNode { ElemType data; struct LNode *next ; }LNode *LinkList;
1 2 3 4 5 bool InitList (LinkList &L) { L=NULL ; return true ; }
1 2 3 4 5 6 7 8 bool Empty (LinkList L) { if (L =NULL ) return true else { return false } }
1 2 3 4 5 6 void test () { LinkList L; InitList(L); .... }
1 2 3 4 5 typedef struct LNode { ElemType data; struct LNode *next ; }LNode *LinkList;
1 2 3 4 5 6 7 8 9 bool InitList (LinkList &L) { L=(LinkList) malloc (sizeof (LNode)); if (L==NULL ){ return false ; } L->next=NULL ; return true ; }
1 2 3 4 5 6 7 bool Empty (LinkList L) { if (L->next==NULL ){ return true ; }else { return false ; }
1 2 3 4 5 6 void test () { LinkList L; InitList(L); .... }
单链表的插入 按位插入不带头结点 按位插入带头结点 指定结点的前插操作O(n) 指定结点的前插操作O(1) 1 2 指定结点，这种方式，先找到指定节点的前驱结点-->遍历 平均复杂度O(n)
1 2 这种方式，无需找到指定结点前驱结点，先插入到后面，然后交换data,等效为前插 O(1)
单链表的删除 1 2 按位置删除，只能通过遍历找到第i-1个结点 最坏，平均都是O(n)
1 2 这种指定节点删除方式，时间复杂度`O(1)`,但是极限情况，当p最后结点的时候 就无法通过转移数据的方式完成删除
单链表查找 按位查找 时间复杂度O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 LinkList GetEle_by_pos (LinkList L,int pos) { if (pos<1 ){ return NULL ; } if (pos==0 ){ return L; } Linklist p; p=L; int i=0 ; while (p!=NULL &&i<pos){ p=p->next; i++; } return p; }
无需再定义一个p指针用来遍历，直接用头结点L进行遍历，然后返回L，由于L没有用引用,最终并不会改变L1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 LinkList GetEle_by_pos (LinkList L,int pos) { if (pos<1 ){ return NULL ; } if (pos==0 ){ return L; } int i=0 ; while (L&&i<pos){ L=L->next; i++; } return L; }
按值查找 时间复杂度O(n)
1 2 3 4 5 6 7 Linklist LocateElem (LinkList L,ElemType e) { L=L->next; while (L !=NULL &&L->data!=e) L = L->next; return L;
统计表长 时间复杂度O(n)
单链表建立 头插法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 void list_head_insert (LNode* &L) { L= (LinkList)malloc (sizeof (LNode)); L->next=NULL ; ElemType x; LinkList s; scanf ("%d" ,&x); while (x!=9999 ){ s=(LinkList) malloc (sizeof (LNode)); s->data=x; s->next=L->next; L->next=s; scanf ("%d" ,&x); } }
重要性质：头插法实现的链表数据是逆置的，用于链表的逆置
链表逆置：循环依次读取老链表数据，然后用头插法依次建立新链表/再次用头插法插入到之后，这样就是实现了链表逆置
尾插法 时间复杂度O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 void list_tail_insert (LinkList &L) { L=(LinkList) malloc (sizeof (LNode)); L->next=NULL ; ElemType x; LNode *s,*r=L; scanf ("%d" ,&x); while (x!=9999 ){ s=(LinkList) malloc (sizeof (LNode)); s->data=x; r->next=s; r=s; scanf ("%d" ,&x); } r->next=NULL ; }
双链表 1 2 3 为了克服单链表无法直接通过一个结点访问其前驱 提出了双链表 双链表结点结构体，有两个指针，一个指向前驱，另一个指向后继
1 2 3 4 5 typedef struct DNode ( ElemType data; struct DNode *prior,*next; }DNode,*DLinklist;
循环单链表 1 2 3 4 5 6 在循环单链表中，表尾结点*r的next域指向L，故表中没有指针域为NULL的结点，因此， 循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。 循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作是在表尾进行，则执 行的操作不同，以让单链表继续保持循环的性质。当然，正是因为循环单链表是一个“环”，因 此在任何一个位置上的插入和删除操作都是等价的，无须判断是否是表尾。
静态链表 1 2 3 4 静态链表借助数组，表示链式存储结构 需要大片的连续的空间，删除或增加结点不需要移动其他元素 结点有指针域(下一个结点的数组下标)，数据域(存储的数据)； 静态链表以next=-1表示结束
1 2 3 4 5 #define Maxsize 50 typedef struct { ElemType data; int next; }SLinkList [Maxsize];
课后习题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 LinkList search_k (LinkList L,int k) { int count=0 ; LinkList p=L->next; LinkList q=L->next; while (p!=NULL ){ if (count<k){ p=p->next; count++; }else { p=p->next; q=q->next; } } if (count<k){ return NULL ; } return q; } int Get_length (LinkList L) { int count=0 ; while (L){ L=L->next; count++; } return count; } void find_same_str (LinkList str1,LinkList str2) { m=Get_length(str1); n=Get_length(str2); for (str1;m>n;m--){ str1=str1->next; } for (str2;n>m;n--){ str2=str2->next; } while (str1->next!=NULL &&str1->next!=str2->next){ str1=str1->next; str2=str2->next; } return p->next; } void resort (LinkNode *L) { LinkNode *k,kk=L; LinkNode *r,s; while (kk->next){ k=k->next; kk=kk->next; if (kk->next!=NULL ){ kk=kk->next; } } kk=k->next; while (kk){ r=kk->next; kk->next=k->next; k->next=kk; kk=r; } s=L->next; kk=k->next; while (kk){ r=kk->next; kk->next=s->next; s->next=q; s=q->next; kk=r; } }
栈 栈的实现 定义：一种只允许在一端进行插入或删除的线性表
栈实现–顺序存储
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #define MaxSize 10 typeof struct { int data[MaxSize]; int top; }SqStack void init (SqStack &S) { S.top=-1 ; } bool isEmpty (SqStack &S) { if (S.top==-1 ){ return true ; } else { return false ; } } bool push (SqStack &S,ElemType x) { if (S.top==MaxSize-1 ){ return false ; } S.data[++S.top]=x; return true ; } bool pop (SqStack &S,ElemType &x) { if (S.top==-1 ){ return false ; } x=S.data[S.top--]; return true ; }
栈实现–链式存储
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 typedef struct SNode { int data; struct SNode *next ; }SNode, *LiStack; bool InitStack (LiStack &S) { S = (SNode *) malloc (sizeof (SNode)); S->next = NULL ; return true ; } bool StackEmpty (LiStack S) { if (S->next==NULL ) return true ; else return false ; } bool Push (LiStack &S, int x) { SNode * p = (SNode *) malloc (sizeof (SNode)); p->data = x; p->next = S->next; S->next = p; return true ; } bool Pop (LiStack &S, int &x) { if (StackEmpty(S)) return false ; SNode * p = S->next; x = p->data; S->next = p->next; free (p); return true ; }
栈在括号匹配中应用 括号匹配问题
1 2 遇到左括号-->入栈 遇到右括号-->出栈，并且匹配检查
算法实现
栈在表达式求值应用
前缀、中缀、后缀表达式是什么？
中缀转后缀表达式手算方式？
1 2 虽然两种后序表达式都是正确的，但是由于计算机运算遵循左优先原则，尽可能的先算左边运算符 这样就保证运算顺序唯一
用栈实现后缀表达式的计算？
1 2 3 1.从左往右依次扫描 2.扫描到数字，则压入栈 3.扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，继续1
用栈实现中缀表达式转后缀表达式？
用栈实现中缀表达式求值？
1 2 3 4 5 6 7 8 中缀转后缀+后缀计算 1.扫描中缀表达式，从左往右 2.扫描到数，入数栈；扫描到符号，入符号栈 3.扫描到符号如果前面有优先级更高的，则要先弹出高优先级，再入栈当前符号，并弹出两个操作数 与弹出的符号运算，并将结果入回数栈顶部 4.如果扫描到的符号前面没有优先级更高的，则无需操作，继续扫描 5.遇到 ( 则 直接入栈，遇到 ) 依次弹出栈内运算符，并弹出相应数进行运算，直到弹出 ( 为止
栈在递归中的应用 递归工作栈
课后习题
1 基本操作是指能直接实现的操作，ACD都属于基本操作，但是B栈不能直接删除栈底元素，需要一个一个移开上面元素，再删除，再放回之前的元素
1 2 3 4 5 6 7 3个不同元依次进栈，能得到（B)种不同的出栈序列。 A.4 B.5 C.6 D.7 解析：卡特兰数，(6x5x4)/(3x2x1)/4=5
1 2 3 4 5 6 7 8 9 共享栈，可以节省存储空间，降低发生上溢的可能 共享栈是一种两个栈共享同一片存储空间的数据结构。它的特点是两个栈的栈底在这片存储空间的两 端，当元素入栈时，两个栈的栈顶指针相向而行。这样可以更有效地利用存储空间，只有在整个空间 满时才会发生上溢 共享栈栈满条件判断有两种： 栈顶指针初始指向-1: 栈顶指针初始指向0：
队列 队列实现 是只允许在一端进行插入，在另一端删除的线性表
队列(顺序存储) 队列(链式存储-带头结点) 队列(链式存储-不带头结点) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 #define MaxSize 10 typedef struct { int data[MaxSize]; int rear,front; }SqSueue; void InitQueue (SqQueue &Q) { Q.rear=Q.front=0 ; } bool IsEmpty (SqQueue Q) { if (Q.rear==Q.front){ return true ; }else { return false ; } } bool IsFull (SqQueue Q) { if ((Q.rear+1 )%MaxSize==q.front){ return true ; }else { return false ; } } bool EnQueue (SqQueue &Q,int x) { if (IsFull(Q)){ return false ; }else { Q.data[Q.rear]=x; Q.rear=(Q.rear+1 )%MaxSize; } } bool OutQueue (SqQueue &Q,int x) { if (IsEmpty){ return false ; }else { Q.front=(Q.front+1 )%MaxSize; return true ; } }
1 2 3 - 队列中元素个数=(rear+MaxSize-front)%MaxSize - 队列中最多存储MaxSize-1个元素，留一个空位给rear用来(rear+1)%MaxSize判定 否则，全装满，rear=front,那么判空，判满无法区分
1 另一种判断队列空满的方法，增加辅助变量，可以充分利用存储单元，可以装满
回顾
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 typedef struct LinkNode { int data; struct LinkNode *next ; }LinkNode;*LinkList; typedef struct { LinkNode *front,*rear; }LinkQueue; void InitQueue (LinkQueue &Q) { L=(LinkList)malloc (sizeof (LinkNode)); Q.front=Q.rear=L; Q.front->next=NULL ; } bool IsEmpty (LinkQueue Q) { if (Q.front==Q.rear){ return true ; } return false ; } void EnQueue (LinkQueue &Q,int x) { LinkList s; s=(Linklist)malloc (sizeof (LinkNode)); s->data=x; s->next=NULL ; Q.rear->next=s; Q.rear=s; } bool OutQueue (LinkQueue &Q,int x) { if (IsEmpty){ return false ; }else { LinkList p=Q.front->next; x=p->data; Q.front->next=p->next; if (Q.rear==p){ Q.rear=Q.front; } free (p); return true ; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 void InitQueue (LinkQueue &Q) { Q.front=NULL ; Q.rear=NULL ; } bool IsEmpty (LinkQueue Q) { if (Q.front==Q.rear==NULL ){ return true ; } return false ; } void EnQueue (LinkQueue &Q,int x) { linkList s; s=(Linklist)malloc (sizeof (LinkNode)); s->data=x; s->next=NULL ; if (Q.front==NULL ){ Q.front->next=s; Q.rear=s; }else { Q.rear->next=s; Q.rear=s; } } bool OutQueue (LinkQueue &Q,int x) { if (Q.front==NULL ){ return false ; }else { Linklist p=Q.front; x=p->data; Q.front=p->next; if (p==Q.rear){ Q.rear=NULL : Q.front=NULL ; } free (p); return true ; } }
注意：顺序存储，rear指向的是尾部元素的后一位；链式存储，rear指向的就是尾部元素
双端队列
课后习题
1 2 3 迷宫求解，本质是岔路选择，遇到选择则入栈 缓冲区，本质是一个队列，将信息，按原本顺序输出(先入先出)，作用是缓存信息(延长信息存在时间)，以防止计算机反应慢接收不到
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 1.一个问题的递归算法求解和其相对应的非递归算法求解，（B）。 A.递归算法通常效率高一些 B.非递归算法通常效率高一些 C.两者相同 D.无法比较 解析：递归算法-->代码简洁，容易理解，但是效率低，因为递归存在大量重复运算；非递归算法-->代码繁琐，但是效率较高，没有多余运算 ------ 2.执行（B）操作时，需要使用队列作为辅助存储空间。 A.查找散列（哈希）表 B 广度优先搜索图 C．前序（根）遍历二叉树 D.深度优先搜索图 解析： B：图的广度优先遍历：以广度为优先考虑，使用队列 C：前中后序遍历二叉树，在递归方法中都隐含 递归栈。 那么非递归方法中必然是使用栈来进行这些 相关操作的。 3.下列说法中正确的是（A）。 A.消除递归不一定需要使用栈 B。对同一输入序列进行两组不同的合法入栈和出栈组合操作，所得的输出序列也一定相同 C.通常使用队列来处理函数或过程调用 D.队列和栈都是运算受限的线性表，只允许在表的两端进行运算 解析：A本来没必要使用递归的算法，使用递归，那么消除递归就不一定需要使用栈替代 4.为解决计算包主机省打印机之间速度不匹配问题，通常设置一个打印数缓冲区，庄机将要输出的数据依次写入该缓冲，而打机则依次从该缓冲区中取出数据。该缓冲区的逻辑结应该是(A) A.栈 B.队列 C.树 D.图 5.某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类，上渡船有如下规定：同类车先到先上船；客车先于货车上渡船，且每上4辆客车，才允许放上一辆货车；若等待客车不足4辆，则以货车代替；若无货车等待，允许客车都上船。试设计一个算法模拟渡口管理。 “同类车先到先上船’一一队列。一个队列负责一种车。 接下来是按照条件进行按顺序上车。 每次上限是10，也就是4客车+1货车，4客车+1货车。 最后两个条件，其实就是“没客车的话货车可以替代客车”和“没货车的话客车可以替代货车”。 写两个函数，用于上客车和上货车，每一个内部再进行判断是否够用。 经过上面的过程，整个算法的思路就明确下来了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #define MaxSize 100 typedef struct node { int n; double val; }Stack[MaxSize]; void comculate (int n,int x) { Stack a; int top=-1 ,i; for (i=n;i>=2 ;i--){ top++; a[top].n=i; } double fv1=1 ,fv2=2 *x; while (top>=0 ){ a.[top].val=2 *x*fv2-2 *(a.[top].n)*fv1; fv1=fv2; fv2=a.[top].val; top--; } if (n==0 ){ return fv1; }else { return fv2; } }
串 KMP匹配算法 动画演示
树与二叉树 基本术语 分支结点：有左孩子或右孩子或都有的结点叶子结点：没有左右孩子的结点结点之间的路径：结点与结点之间的边的数量，只能单方向从上往下结点的层次(深度)：从上往下数，默认从1开始结点的高度：从下往上数树的高度(深度)结点的度：结点有多少个分支树的度：各结点的度的最大值森林：m个(m>=0)互不相交的树组成前驱：遍历后的顺序，当前节点的前一个节点为该节点的前驱节点后继：遍历后的顺序，当前节点的后一个节点为该节点的前驱节点树的常考性质 完全二叉树与满二叉树 二叉树的常考性质 1.具有n个结点的完全二叉树的高度向上取整
向下取整
2.完全二叉树，度为0、1、2的结点个数
1 2 3 4 5 6 7 假设度为0、1、2的结点个数分别为n0、n1、n2 yw 是完全二叉树 sy n0=0或1 yw n0=n2+1 sy n0+n2-->奇数 sy n0+n2+n0的奇偶性看n1 sy 当n1=1时，结点数是偶数；当n1=0时，结点数为奇数
二叉树的定义 定义顺序存储的二叉树–下标从1开始 二叉树顺序存储的数据结构定义，需要注意以下两点：
1 2 3 4 5 6 7 8 9 10 若顺序二叉树从数组下标1开始存储结点，则： ● 结点 i 的父结点编号为 i/2 ● 结点 i 的左孩子编号为 i*2 ● 结点 i 的右孩子编号为 i*2+1 若顺序二叉树从数组下标0开始存储结点，则： ● 结点 i 的父结点编号为 [(i+1)/2] - 1 ● 结点 i 的左孩子编号为 [(i+1)*2] - 1 = 2*i + 1 ● 结点 i 的右孩子编号为 [(i+1)*2+1] - 1 = 2*i + 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 typedef struct TreeNode { int data; bool isEmpty; } TreeNode; void InitSqBiTree (TreeNode t[], int length) { for (int i=0 ; i<length; i++){ t[i].isEmpty=true ; } } int main () { TreeNode t[100 ]; InitSqBiTree(t, 100 ); }
实现函数，找到结点 i 的父结点、左孩子、右孩子 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 bool isEmpty (TreeNode t[], int length, int index) { if (index >= length || index < 1 ) return true ; return t[index].isEmpty; } int getLchild (TreeNode t[], int length, int index) { int lChild = index * 2 ; if (isEmpty(t, length, lChild)) return -1 ; return lChild; } int getRchild (TreeNode t[], int length, int index) { int rChild = index * 2 + 1 ; if (isEmpty(t, length, rChild)) return -1 ; return rChild; } int getFather (TreeNode t[], int length, int index) { if (index == 1 ) return -1 ; int father = index / 2 ; if (isEmpty(t, length, father)) return -1 ; return father; }
利用上述三个函数，实现先/中/后序遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 void PreOrderSqTree (TreeNode *t, int length, int index) { if (isEmpty(t, length, index)) return ; visitNode(t[index]); PreOrderSqTree(t, length, getLchild(t, length, index)); PreOrderSqTree(t, length, getRchild(t, length, index)); } void InOrderSqTree (TreeNode *t, int length, int index) { if (isEmpty(t, length, index)) return ; InOrderSqTree(t, length, getLchild(t, length, index)); visitNode(t[index]); InOrderSqTree(t, length, getRchild(t, length, index)); } void PostOrderSqTree (TreeNode *t, int length, int index) { if (isEmpty(t, length, index)) return ; PostOrderSqTree(t, length, getLchild(t, length, index)); PostOrderSqTree(t, length, getRchild(t, length, index)); visitNode(t[index]); } int main () { TreeNode t[100 ]; InitSqBiTree(t, 100 ); InOrderSqTree (t, 100 , 1 ); }
定义顺序存储的二叉树（从数组下标0开始存储） 1 2 3 4 5 与 上面思路相同，只不过结点编号的计算有些区别而已 若顺序二叉树从数组下标0开始存储结点，则： ● 结点 i 的父结点编号为 [(i+1)/2] - 1 ● 结点 i 的左孩子编号为 [(i+1)*2] - 1 = 2*i + 1 ● 结点 i 的右孩子编号为 [(i+1)*2+1] - 1 = 2*i + 2
定义链式存储的二叉树 1 2 3 4 5 typedef struct TNode { ElenType c; struct TNode *lift ,*right ; }BiTNode,*BiTree;
课后习题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 1.树的路径长度是指树根到每个结点的路径长的总和，根到每个结点的路径长度的最大值应是树的高度-1 2.[2010统考真题]在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结 点，1个度为2的结，点，10个度为1的结点，则树T的叶结点个数是（82） 解析：结点总数=20x4+10x3+1x2+10x1+1=123;又因为结点总数=有度结点（20+10+1+10）+无度结点所以 123-41=82; 3.度为2的有序树不一定是二叉树，因为，二叉树的每个结点都有左右次序，若一个树有两个结点但是没有左右次序，那么就不算是二叉树 4.重要-->n个结点的完全二叉树的高度为(log2n) + 1 或log2(n+1) 5.设二叉树有2n个结点，且m<n,则不可能存在（）的结点。 A.n个度为0 B.2m个度为0 C.2m个度为1 D.2m个度为2 解析：因为2n=n0 + n1 + 2n2，所以n1=2(n-n2)-1是奇数 5.重要总结：高度为h的满二叉树的结点个数=2^h-1-->类比，二进制位计算 6.[2009统考真题]已知一棵完全二叉树的第6层(设根为第1层)有8个叶结，点，则该 完全二叉树的结点个数最多是（） A.39 B.52 C.111 D.119 解析：第六层有8个叶子结点，说明树有可能6层有可能7层，最多就是7层的时候，计算得到111 7.[2011统考真题]若一棵完全二叉树有768个结，点，则该二叉树中叶结点的个数是（）。 A.257 B.258 C.384 D.385 解析：完全二叉树最后一个分支结点的序号是n/2，有小数舍去小数部分 8.2018统考真题]设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结 点都有2个子结点。若T有k个叶结点，则T的结点总数是（）。 A.2k-1 B.2k C.2^k D.2^k-1 解析：A 9.[2020统考真题]对于任意一棵高度为5且有10个结点的二叉树，若采用顺序存储结构 保存，每个结点占1个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存 储单元数量至少是（）。 A.31 B.16 C.15 D.10 解析：顺序存储，数组存放，又因为逻辑结构的二叉树高5层，却只有10个结点，说明没有放满想象成一颗5层的满二叉树 A，为什么不能是完全二叉树？如果只是完全二叉树，如果第五层的最后一个结点放了一个结点，那么数组如果按照完全二叉树给空间，明显放不下，所以考虑最坏情况，想象满二叉树，保证所有情况都满足
二叉树的遍历 先序/深度优先遍历
递归遍历求树的深度
层序/广度优先遍历(BFS)
中序遍历
确定一颗二叉树 如果只是给定一个二叉树的前\中\后\层序\遍历序列中的一种，那么是无法确定唯一的一颗二叉树的至少要知道两种不同遍历的序列：前+中、后+中、层序+中 基本思路都是通过前\后\层序遍历确定根节点，再通过中序遍历确定左右子树 前+中第一个是根节点左子树，右边就是右子树
线索二叉树 线索二叉树定义 1 2 3 尾部结点的左右指针，由指向NULL转变为指向前驱和后继 这样有利于二叉树寻找前驱和后继 疑问？那如果左右指针不是空的结点该如何指向自己的前驱后继呢？
注意：这里讲的前驱，后继是指的是遍历后序列顺序的前后结点，不是二叉树结构上的前后关系1 2 3 4 5 6 7 8 typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild ,rchild int ltag ,rtag ; }ThreadNode,*ThreadTree;
线索二叉树的实现 1 2 3 4 5 6 7 8 9 10 11 12 本质就是二叉树的中序遍历 只是在参数里多传递了一个前驱指针pre 主要结构 左、根、右 -->就是一个中序遍历结构 pre指向的是p的前驱 当遍历到最底层时，开始执行访问结点操作，也就是中间黄色代码操作 如果p左节点为空，那么可以转为线索指向前驱pre,标记变为1 接着如果pre的右结点有空位，也可以指向前驱p 接着，pre后移为后继p p后移为后继
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 void InThread (ThreadTree &p,ThreadTree spre) ( if (p!=NULL ){ InThread(p->1 child,pre); if (p->lchild==NULL )( p->lchild=pre; p->1 tag=1 : } if (pre!=NULL &6 pre->rchild==NULL ){ pre->rchild=p; pre->rtag=1 ; } pre=p; InThread(p->rchild,pre); } } void CreateInThread(ThreadTree T){ ThreadTree pre=NULL ; if (T!=NULL ){ InThread(T,pre); pre->rchild=NULL ; pre->rtag=1 ; }
线索二叉树的遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ThreadNode *Firstnode (ThreadNode *p) { while (p->ltag==0 ){ p=p->lchi1d; } return p;} TreadNode *Nextnode (TreadNode *p) { if (p->rtag==0 ){ return Firstnode(p); } else { return p->right; } } void Inorder (TreadNode *T) { TreadNode *p; for (p=Firstnode(T);p!=NULL ;p=Nextnode(p)){ visit(p); } }
课后习题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 1.引入线索二叉树的目的是（） A,加快查找结点的前驱或后继的速度 B.为了能在二叉树中方便插入和删除 C.为了能方便找到双亲 D.使二叉树的遍历结果唯一 解析：线索是结点的前驱和后继结点的指针，可以加快遍历 2.线索二叉树是一种(C)结构。 A.逻辑B.逻辑和存储C.物理D.线性 解析：二叉树是一种逻辑结构。 而线索二义树明确指明了在存储过程中的数据存放方式(指明了线索是标记为1的时候)，就是物理结构了。 (物理结构=存储结构) 3.n个结点的线索二叉树上含有的线索数为(B) A.2n B.n-1 C.n+l D.n. 解析：每个结点有两条链域指针，总共2n条，每个结点被一条指针指向，剩余的构成线索，2n-(n-1) 4.二叉树在线索化后，仍不能有效求解的问题是（D）。 A.先序线索二叉树中求先序后继 B.中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D.后序线索二叉树中求后序后继 4.注意，前序、中序线索树的遍历不需要通过弹栈的方式来遍历后继结点，因为后继都可以通过线索来指向 但是，后序线索二叉树的遍历必须通过弹栈的方式，返回上一层及的后继结点，如下图所示，结点3既没有左右孩子指针指向4结点，又没有后继线索指向4结点(左右子树占用了线索) 所以，中序，前序线索二叉树不需要栈支持了，但是后序线索二叉树任然需要
1 2 3 4 5 6 7 8 9 10 11 12 5.[2011统考真题]一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1, 该二叉树的中序遍历序列不会是（C）。 A.1,2,3,4 B.2,3,4,1 C.3,2,4,1 D.4,3,2,1 解析：前后序遍历序列相反，说明每个结点只能有左孩子或只能有右孩子,不会同时存在两个子树 6.编写后序遍历二叉树的非递归算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 while (p||!isEmpty(S)){ if (p){ push(S,p); p=p->lift; } else { Getop(S,p); if (p->right&&p->right!=r){ p=p->right; } else { pop(S,p); visit(p->data); r=p; p=NULL ; } } }
1 2 3 4 7.试给出二叉树的自下而上、从右到左的层次遍历算法。 解析：思路，按照层序遍历遍历，新增一个栈，用于存放出队列的结点，这样就能将原有序列取反，并在最后通过弹栈进行后续操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 void InvertLevel (BiTree T) { Stack S; Queue Q; Init(Q); BiTree q; Q.EnQueue(T); while (!iSEmpty(Q)){ q=OutQueue(Q); Push(S,q); if (T->left){ EnQueue(Q,T->left); } if (T->right){ EnQueue(Q,T->right); } } while (!isEmpty(S)){ Pop(S,p); Visit(p); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 typedef struct { BiNode data[MaxSize]; int front,rear; }Queue; int level_order (BiTree T) { int level=0 ,last=0 ; Queue Q; InitQueue(Q); if (!T){ return 0 ; } EnQueue(T); while (!IsEmpty(Q)){ BiTree p=OutQueue(Q); if (p->left){ EnQueue(p->left); } if (p->right){ EnQueue(Q->right); } if (Q.front=last){ level++; last=Q.rear; } } return level; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 typedef struct { BiTree data[MaxSize]; int level[MaxSize]; int front,rear; }Qu; int BiWide (Bitree T) { BiTree q; int k=0 ; int max i; Qu Q; Q.front=Q.rear=-1 ; Q.rear++; Q.data[rear]=T Q.level[rear]=1 ; while (Q.front<Q.rear){ Q.front++; q=Q.data[front]; k=Q.level[front]; if (q->left!=NULL ){ Q.rear++; Q.data[Q.rear]=q->left; Q.level[Q.rear]=k+1 ; } if (q->right!=NULL ){ Q.rear++; Q.data[Q.rear]=q->right; Q.level[Q.rear]=k+1 ; } } max=0 ;i=0 ; k=1 ; while (i<=Q.rear){ int n=0 ; while (i<=Q.rear&&k==Q.level[i]){ i++; n++; } k=Q.level[i]; if (n>max){ max=n; } } return max; }
1 2 3 4 5 6 7 8 9 10 void ProToPost (Element pre[],int l1,int h1,Element post[],int l2,int h2) ){ int half; if (l1<=h1){ post[h2]=pro[l1]; half=(l1+h1)/2 ; ProToPost(pre,l1+1 ,l1+half,post,l2,l2+half-1 ); ProToPost(pre,l1+half+1 ,h1,post,l2+half,h2-1 ); } }
1 11.设一颗二叉树中各个结点的值不相同，其先序遍历和中序遍历的序列分别存放在数组A[1..n]和数组B[1..n]中，试编写一个算法建立该二叉树的二叉链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 BiTree BuildTree (ElemType A[],int l1,int h1,ElemType B[],int l2,int h2) { BiTree root=(BiTree)malloc (sizeof (BiNode)) root->data=A[l1]; int i=l2; while (A[l1]!=B[i]){ i++; } llen=i-l2; rlen=h2-i; if (llen){ root->left=BuildTree(A,l1+1 ,l1+llen,B,l2,l2+llen-1 ); }else { root->left=NULL ; } if (rlen){ root->right=BuildTree(A,h1-rlen+1 ,h1,B,h2-rlen+1 ,h2); }else { root->right=NULL ; } return root; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 bool IsCompelet (BiTree T) { Queue Q; init(Q); EnQueue(Q,T); BiTree q; while (!isEmpty(Q)){ q=OutQueue(Q); if (q){ EnQueue(q->left); EnQueue(q->right); }else { while (!isEmpty(Q)){ q=OutQueue(Q); if (q){ return fasle; } } } } return true ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 int InOrder (BiTree T) { static int count=0 ; if (T!=NULL ){ InOrder(T->left); if (T->left!=NULL &&T->right!=NULL ){ count++; } InOrder(T->right); } return count; }
森林 什么是森林？
树、森林转化为二叉树 1 2 3 4 5 首先将树转化为二叉树 将树转化为二叉树 1.给兄弟加线 2.将除长子外的与父节点的线去掉 3.最后层次调整
1 2 3 将森林转化为二叉树 1.先将所有树先转化为二叉树 2.将第一课树的根节点，将自己的子树森林转化为左子树，右子树指向下一棵树的根节点
课后习题 1 2 假设树原始分支只有一条 想象树每多一条分支，就会出现一个叶子结点，且多一组兄弟结点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1.若森林F有15条边、25个结点，则F包含树的个数是 A.8 B.9 C.10 D.11 解析：对于一棵树而言，除了根节点，其他每个结点都由一条边指向，也就是说，其他每个结点都对应一条边，所以，一棵树的结点数=边数+1 所以，结点数-边数=25-15=10，所以有10棵树 2.编程求以孩子兄弟表示法存储的森林的叶子结点数。 解析：题目意思是，求在森林转化的二叉树中，找到原森林中叶子结点的个数 找规律发现，森林中的叶子结点，在二叉树中都没有左子树，所以可以通过遍历二叉树，每次碰到结点判断一下该节点是否有左孩子，没有就num++ 3.在二叉树中有两个结点m和n,如果m是n的祖先，使用（C）可以找到从m到n的路径。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 解析：后序遍历是从后往前，在找到n之后，层层往上层父节点寻找，这个过程一定能找到m，并且父节点入栈顺序是按照从后往前的顺序。 但是先序遍历，在找到n之后，因为在这之间先访问了父节点，所以这个父节点入栈顺序是从前往后，从一开始就要入栈的话，就无法保证找到n 中序遍历一样抽象
哈夫曼树 带权路径长度 1 2 3 结点的带权路径长度：从树的根节点到该结点的路径长度(经过的边数)与该结点上值得乘积 树的带权路径长度：树种所有叶子结点的带权路径之和(WPL,Weight Path Length) 带权路径长度最小的二叉树被称为哈夫曼树，也称最优二叉树
哈夫曼树定义 编码问题
S=AAABBACCCDEEA
S中出现次数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 为了使得编码变短，尽量将出现次数较多的编码缩短 于是建立如下哈夫曼树 1.将字符按出现次数从多到少排列 2.从最少的两个次数相加组成 次数结点 3.同样的过程完全建立一颗抽象的树状结构 4.在树上左分支0,右分支1 5.向右寻找一位,编码1，向左寻找一位编码0 6.例如 B --> 110 7.A次数最多5-->编码最短0 ；D次数最少1-->编码最长1110 8.达到了编码串缩短的目的 如何解码呢？ 从左到右逐个扫描编码串字符，0向左走，1向右走，如果走到叶子结点（字符位置），就读取 然后再次回到根节点，没有就继续扫描
1 2 3 1.权值越大的字符，离根节点越近(权值看做字符的次数) 2.哈夫曼树中，没有度为1的结点，这类树叫做"正则二叉树"(严格二叉树) 3.哈夫曼树的带权路径长度最短(也称最优二叉树)
哈夫曼树带权路径长度的计算 概念
路径：在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径 路径长度：在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。 结点的带权路径长度：树的根结点到该结点的路径长度和该结点权重的乘积 树的带权路径长度：在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。 计算方法
问题描述：给定树T，有n个叶结点，并且其权重值为{A1,A2,A3…An};如何计算树T的WPL
例如2021年408这道题
1 若某二叉树有5个叶子结点，其权值分别为10，12，16，21，30。则其最小的带权路径长度(WPL)是()
方法
按照算法步骤画出哈夫曼树 具体算法如下：
1 2 3 4 1. 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点) 2. 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； 3. 从森林中删除选取的两棵树，并将新树加入森林 4. 重复2、3步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树
举例说明
首先对集合进行排序得到{10，12，16，21，30} 我们找到权值最小的两个结点10和12合并；得到新的森林根结点为22。现在结点集合为{16,21,22,30}
接着我们找到当前最小的结点16和21合并：得到新的森林根结点为37。现在结点集合为{22,30,37}
接着我们找到当前最小的结点22和30合并：得到新的森林根结点为53。现在结点集合为{37,53}
接着我们找到当前最小的结点37和53合并：得到新的森林根结点为90。现在结点集合为{90}；由于结点个数只剩一个，所以算法结束、构造哈夫曼树完毕
可以看到哈夫曼树的构造堆左右子树的顺序是没有要求的，当然我们画哈夫曼树的可以按照一定规律来这样更明确思路更清晰，比如我这里是按照左节点<右结点的原则来画的
依次累加计算所有叶结点的带权路径长度 从上面构造的哈夫曼树可知所有结点的路径长度，例如结点”16“的路径长度为2。所以WPL=(16+21+30)*2+(10+12)*3=200
二叉树的估计 1 2 3 右侧的分别是表示遍历后的顺序 黑色表示要删除的 注意：前后结果相反，有两种情况，没有左(L)或没有右(R)都满足
二叉存储表达式 1 2 3 4 5 根据二叉存储表达式建立二叉树：3+4*5*(2+3) 手工方法：1.加括号明确运算次序(3+((4*5)*(2+3))) 2.列出数字元素 3 4 5 2 3 作为叶子结点 3.按运算次序 用运算符作为分支节点 建立二叉树 栈方法：不介绍
课后习题 1 2 1.前缀码是一种编码系统，通常是可变长度码，在其中的每个码字，都具备「前缀性质」(prefix property)，也就说，在编码中的每个码字，都不能被其他码字当成前置部位。例如，编码字{9,55}具备了前缀性质，但编码字{9,5,59,55}就不具备，因为其中的"5”，是59"及"55"的前缀
1 题目已对两个字符编码1和01，因为哈夫曼树只对叶子结点进行编码，所以1和01两个结点就是叶子结点，不能继续延伸。故只能往左下继续寻找，最终如图，注意要数的是叶子结点的个数
1 2 哈夫曼树如果有n个叶子结点，那么总共有2n-1个结点 因为n个叶子结点，经过n-1次整合，构建出n-1个非叶子结点，总共2n-1个结点
1 第一次整合需要m个，之后整合只需m-1个叶子结点，每次整合有一个非叶子结点，所以n-1/m-1
1 2 3 4 5 6 7 8 9 10 11 1对于哈夫曼树的说法错误的是（D） A.对应一组权值构造出来的哈夫曼树一能不是唯一的 B.哈夫曼树具有最小的带权路径长度 C.哈夫曼树中没有度为1的结点 D.哈夫曼树中除了度为1的结点外，还有度为2的结点和叶结点 解析： A:确实不唯一。仅思考两个结点的情况：1和2，就有两种：1在左子树2在右子树和反过来。 B:正确。正是我们使用哈夫曼树进行编码的意义所在。 C:正确。任意非叶子结点都是由两个树（数据元素）构成的，因此不存在度为1的结点。 D:解析同C,因此错误。
1 所谓定长编码集，就是所有字符编码位数都一样，0001 1100 1010 ..
图 课后习题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1.图中有关路径的定义是(A). A.由顶点和相邻顶点序偶构成的边所形成的序列 B.由不同顶，点所形成的序列 C.由不同边所形成的序列 D.上述定义都不是 解析：A路径是由顶点与相邻顶点序偶构成的边的序列 例如顶点A到顶点D的路劲 <A B> <B C> <C D> ; B路劲不是由顶点构成 ；C没有讲明是由相邻的边形成的序列 2.[2017统考真题]已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶 点个数为4，其他顶点的度均小于3。图G所含的顶点个数至少是（11） 解析：无向图边数的2倍等于各顶点度数的总和。为求至少的顶点数，应使每个顶点的度取最大，由 于其他顶点的度均小于3，可以设它们的度都为2，设它们的数量是x,列出方程4×3+3×4+2x=16×2, 解得x=4。因此至少包含4+4+3=11个顶点。 3.图G是一个非连通无向图，共有28条边，该图至少有多少个项点？ 解析：由于图G是一个非连通无向图，在边数固定时，顶点数最少的情况是该图由两个连通子图构 成，且其中之一只含一个顶点，另一个为完全图。其中只含一个顶点的子图没有边，另一个完全 图的边数为n(n-1)2=28,得n=8。所以该图至少有1+8=9个顶点。
图的逻辑结构(王道) 1 2 3 4 5 6 7 8 9 10 顶点与顶点的关系 - 路径一一顶点v到顶点v之间的一条路径是指顶点序列 - 回路一一第一个顶点和最后一个顶点相同的路径称为回路或环 - 简单路径一一在路径序列中，顶点不重复出现的路径称为简单路径。 - 简单回路一一除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。 - 路径长度一一路径上边的数目 - 点到点的距离一一从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到的距离 若从u到v根本不存在路径，则记该距离为无穷(∞)。 - 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的 - 有向图中，若从项点到项w和从项点w到项点之间都有路径，则称这两个项点是强连通的
1 2 3 局部图的研究--子图 - 子图：部分顶点，与部分边构成的较小的局部图 - 生产子图：包含原图所有顶点的子图，不一定要所有边
1 2 3 连通分量--描述无向图 - 包含尽可能多的顶点和边 - 下面三个部分都是极大连通子图，属于单独的一个分量
图逻辑结构(天勤) 图由顶点和边构成
无向图：边没有指向方向 (A1,A3) 没有指向
有向图：边有箭头方向 <A1,A3> 表示A1–>A3 ,不能反过来
顶点的度：多少条边与该顶点相连
无向图：A1的度为3 有向图：A1入度为1，出度为2，度为3 简单图：不存在重复的边，并且没有指向自身的边
无向完全图：任意两个顶点之间，都存在边，总共n(n-1)/2条边
有向完全图：任意两个顶点之间，都存在两条方向相反的边，总共n(n-1)条边
若边含有权值则称为网
路径：一个顶点到相邻顶点序偶构成的边的序列,例如：（A1 A2）（A2 A3）（ A3 A6）
简单路径：序列中顶点不重复出现的路径 例如：A1 A2 A3 A2 A4就不是简单路径，其中A2重复了
回路(环)：第一个顶点和最后一个顶点相同，例如：A1 A4 A3 A1
简单回路：除了第一个顶点和最后顶点，中间没有重复出现顶点
连通图：针对无向图不一定要闭合，只要任意顶点间有路径即可
非连通图：
强连通图：针对有向图。如果有向图中的任意两个节点都可以互相到达，则该有向图是强连通的弱连通图：针对有向图。如果将有向图中的所有有向边都看作无向边，得到的无向图是连通的，则该有向图是弱连通的。极大强连通子图（强连通分量）：针对有向图极小强连通子图：针对有向图极小连通子图与最小生成树 1 2 3 - 极小连通子图是指一个无向图的子图，如果它是连通的，并且在保持子图连通的前提下，不能从子图中删除任何边，那么它就是极小连通子图。 - 最小生成树是指一个连通无向图的生成树，它包含图中所有的顶点，并且边的权值之和最小。生成树是一种特殊的极小连通子图，它没有环，并且边数等于顶点数减1。如果一个极小连通子图是一个树，那么它也是原图的生成树。但是，并不是所有的极小连通子图都是树，也不是所有的极小连通子图都是最小生成树。
有向-无向图的连通问题 无向图
有向图 1 这里只讨论有向图强连通，弱连通就是无向图的情况，不再讨论
图的存储结构 顺序存储结构 1 2 3 4 5 6 7 8 用一个二维数组，形成的一个矩阵表示顶点之间的关系 这里演示的是带权的路径 用行标、列标组合表示两个顶点之间路径 按行列找到的数值就是路径权值，例如(1,0)=2,表示1-->0的路径权值为2 这里规定对角线上的值为无穷，也就是顶点到自身的路径为无穷(有的地方也规定为0) 注意：当二位数组对称，说明是无向图，互相指向；当二维数组不对称，说明是有向图
1 2 3 0行 X 3列 只有0行与3列对应相乘都不为0时才有值 结果=3，说明有3个点，与0和3都存在路径
邻接矩阵 1 2 3 4 5 6 #define MaxVertexNum 100 typedef struct { char Vex[MaxVertexNum]; int Edge[MaxVertexNum][MaxVertexNum]; int vexnum,arcnum; }MGraph;
链式存储结构 邻接表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #define N 8 typedef struct ArcNode { int adjvex; struct ArcNode *next ; }ArcNode; typedef struct VNode { char data; ArcNode *first; } VNode typedef struct { VNode vex[N] int vexnum,arcnum; }ALGraph;
十字链表 1 2 3 4 5 针对有向图 只能用于存储有向图 由于邻接表无法表示入边，与出边，所以改进为十字链表 左结构体-->顶点 右结构体-->边 in表示入边，out表示出边，由first引出第一条，由next引出下一条，01、14、20...表示边(有方向)
邻接多重表 1 2 3 4 针对无向图 左结构体-->顶点 右结构体-->边 由于边是双向 接下来有点抽象自己看^o^
课后习题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 1.邻接表可以用于存储无向图，，只是把每条边都视为两条方向相反的有向边，因此需要存储两次 2.在有向图的邻接表存储结构中，顶，点v在边表中出现的次数是（C）。 A顶点v的度 B.顶点v的出度 C:顶点v的入度 D.依附于顶，点v的边数 3.n个顶点的无向图的邻接表最多有(B)个边表结点。 A.n2 B.n(n-1) C.n(n+1)· D.n(n-1)/2 解析：n个顶点的无向图最多有(n-1)/2条边，每条边在邻接表中存储两次，所以边表结点最多为 n(n-l)个。 5.带权有向图G用邻接矩阵存储，则的入度等于邻接矩阵中(D). A.第i行非∞的元素个数 B.第i列非∞的元素个数： C.第i行非∞且非0的元素个数 D.第i列非∞且非0的元素个数
1 2 3 4 5 6 7 8 9 10 11 12 void Convert (AlGraph *G,int [M][N]) { for (int i =0 ;i<n;i++){ ArcNode *p = G->v[i].first; while (p){ int [i][p->adjv]=1 ; p=p->next; } } }
1 2 n个顶点的连通图，最多有n(n-1)/2条边-->每个顶点与其他n-1个顶点相连，最后每条边重复考虑了一次。 所以28条边的连通图最少有8个顶点，要是非连通图则+1顶点 与其他顶点隔离 -->8+1=9
1 2 n个顶点，组成连通无向图，边最少n-1，因为 形成单链 组成强连通有向图，边最少n ，因为形成有向环
1 无向图将所有顶点的度相加=边数x2 ，因为每条边会多重复算一次，利用这个特性，求出度为2的点
1 有向图,求每个顶点最大的度-->每个顶点最多与n-1个顶点相连-->出边+入边-->(n-1)*2
1 环任意去除一条边都是一颗生成树-->共有n条边-->有n条生成树
1 在树中，每个顶点都有一条边指向，除了根节点，所以n-e=根结点数目
1 2 这道题比较难 保证形成连通图的最少变数，7个顶点，前6个保证连通边数达到最大无法再增多，再多加1条连接剩下的顶点，7个就保证连通了
1 2 无向图双向的，所以邻接矩阵沿对角线一定对称；由于这个矩阵不对成所以一定是有向图 第i个顶点的度=矩阵中i行i列的1之和
1 2 Edge --> E 边 Vertex --> V 顶点
1 28条边用最少顶点充分利用n(n-1)=26-->8个顶点-->再额外+1孤立顶点-->实现非连通-->最少9顶点
1 2 3 4 5 6 所有1集中在对角线往上 - i<j - i到j有边 运用拓扑排序方式，对顶点号依次编号
图的遍历 深度优先遍历(DFS) 1 2 3 4 5 6 7 8 9 10 讨论的是邻接表的遍历犯法 为了防止出现图遍历的时候的死循环问题需要，将遍历过得结点进行标记，防止再次遍历 于是 1.设置一个与顶点数组相对应的标记数组(设为全局变量)，数组初始=0； 2.遍历过后标记为1，visit[v]=1; 3.然后ArcNode*q=G->adjList [v].first 找到第一条与该顶点相连的边 4.找到第二条与该顶点相连的边，访问下一个顶点(往深处找)，先判断是否访问过 5.如果没有访问过进行递归 6.如果访问过就找与之相连的下一条边，直到与该顶点相连的边遍历完
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 typedef struct ArcNode { int adjV; struct ArcNode *next ; }ArcNode; typedef struct VNode { VertexType data; ArcNode *first; } VNode,AdjList[MaxSize] typedef struct { AdjList vertice; int n,e }ALGraph
广度优先遍历(BFS) 1 2 3 4 5 6 7 8 讨论的是邻接表的遍历 要点： 1.找到与一个顶点相邻的所有顶点 2.标记哪些顶点被访问过 3.需要一个辅助队列，这里采用循环队列 采用循环的队列作为辅助队列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 typedeof int maxSize void BFS (AGraph *G,int v,int visited[maxSize]) { ArcNode *p; int que[maxSize],front=0 ,rear=0 ; int j; visit(v); vistted[v]=1 ; rear = (rear+1 )%maxSize; que[rear]=v; while (front!=rear){ front = (front+1 )%maxSize; j=que[front]; p=G->AdjList[j].first; while (p!=NULL ){ if (visited[p->adjV]==0 ){ visit(p->adjV); visited[p->adjV]==1 ; rear=(rear+1 )%maxSize; que[rear]=p->adjV } p = p->next; } } }
最小生成树(Prim算法) 1 2 3 4 5 6 7 8 9 生成树：由一个图按照某一种规则，导出里面包含的一颗树(就是由图所有顶点，与部分边，构成的一颗树，就是极小连通子图) 最小生成树：构成的这颗生成树的所有分支的权值和最小(所以讨论的是带权图) 实现思路： 1.先确定一个根节点A0 2.找到与根节点相邻的所有的边，选择权值最小的并入树中(如果产生环，则选择第二小的)，此时A0 A1两个结点 3.继续，找到与A0 A1相邻的所有的边，3,2,7,8 -->将权值为2的边并入树，此时结点A0 A1 A2 4.重复...
最小生成树(Kruskal算法) 1 2 3 4 5 大致思想是 1.将每条边都列举出来，按照权值从小到大排列 2.从最小的边开始，如果边两边的顶点并未"连通"，则连通这条边 3.如果两边顶点处于同一个"并查集"，即连通，则遍历下一条边 4.直到所有顶点处于同一个"并查集"中，即生成了最小生产树
最短路径(DIjkstra) 1 2 3 4 5 6 求某一个顶点(确定某一点)到其余各顶点之间的最短路径 设置3个数组 dist[] -->树中，min[从起点经过新增顶点与上述顶点间的距离,原本直接距离] ，初始=无穷 path[] --> 表示，上述顶点的起始顶点 ,初始=-1 set[] --> 0表示未并入树中，1表示已在树中 ，初始=0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Dijkstra算法 前提：列出所有顶点与a的直接距离，没有直接相连设为∞； 1轮：a直接到达的是b、c。与原距离对比 一样，不更新距离，入路径更短的 b 2轮：b直接到达的是c、d。与原距离对比 {abc}<{ac} {abd}<{ad};更新距离，入路径更短的 c 3轮：c直接到达的是d、e、f。与原距离对比 {acd}>{abd}不更新 ，{ace}<{ae}更新，{acf}<{af}更新 入路径更短的 f 4轮：f直接到达的是 没有 只剩下 d、e 入路径更短的 d 5轮：d直接到达的是f、e。与原距离对比，{acde}={ace}不更新，{acdf}>{acf}不更新 入最后的 e 每一轮，根据新增顶点作为试探，列出所有与其直接相连的顶点，并将新开辟出的路径与原路径对比 如果更短就更新路径。并且最后将与之相连的最近的顶点，入到路径之中
最短路径(Floyd) 1 2 3 4 5 6 7 8 求带权图中各顶点之间的最短路劲 A矩阵：记录顶点到顶点的距离(一开始无中转点，无路径则为∞) path矩阵：记录顶点到顶点之间中转点(一开始无设为-1) 接下来依次将中转点由V0~Vn遍历 确定每一个中转点后，又在A距离矩阵遍历，比较加入中转点后与原距离的大小 比如A(-1)[2][1] > A(-1)[2][0] + A(-1)[0][1] 表示将0作为中转点，V2到V1的距离缩短了
1 三层循环，时间复杂度O(V^3)；空间复杂度O(V^2)
最短路劲总结
有向无环图(DAG)
1 DAG表达式，将重复部分，只保留一个(可以节省空间)，由两个指针指向同一个
1 2 3 4 DAG表达式的构建 1.将出现的元素罗列出来 2.按照运算次序，按顺序加入运算符结点，并且将运算符号分层 3.最后从最底层检查是否有重复部分，并合并
拓扑排序 1 拓扑序列是有向无环图（DAG）中所有顶点的一种线性排序，使得对于每一条有向边 <u, v>，顶点 u 在拓扑序列中都排在顶点 v 的前面。换句话说，拓扑序列可以看作是一个 DAG 中所有顶点的一种合法排序方式。
AOV网：用顶点表示活动的网
1 2 3 4 5 6 7 8 拓扑排序，实现的是，将AOV网中依次的输出具有传递性的活动(顶点),找到做事的先后顺序 AOV网允许有多个入度为0的顶点活动 实现思路： 1.找到入度为0的顶点，先输出 2.删除顶点，与顶点有关的边（出边，也就是将由该顶点指向的所有顶点入度-1） 3.重复1 2 直到为空
1 2 3 4 5 代码实现需要定义两个数组，一个栈 indegree[] 记录当前所有顶点的入度 print[] 记录拓扑排好的的顶点序列 Stack S 保存度为0的顶点(也可以用队列代替)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 bool TopoSort (Graph G) { InitStack(S); for (int i=0 ;i<G.n;i++){ if (indegree[i]==0 ){ push(S,i); } } int count=0 ; while (!IsEmpty(S)){ Pop(S); print[count]=i; count++; for (p=G.vertices[i].first;p!=NULL ;p=p->next){ int v=p->adjV; if (!(--indegree[v])){ push(S,v); } } } if (count<G.n){ return false ; }else { return true ; } }
1 该算法。每一个顶点要被处理一次，每一条边也要遍历一次，所以时间复杂度O(|V|+|E|)
DFS实现逆拓扑排序 1 2 3 4 这里和深度优先遍历几乎一样 只是将Visit(v)放到最后 实现了，只有递归结束之后访问本节点(在这之前已经先访问了递归里面的结点，也就是深处结点) 这样就实现了逆拓扑排序
DFS算法实现拓扑排序 1 2 3 4 5 6 7 8 9 10 1)假设结点u是结点v的祖先，则在调用DFS访问u的过程中，必然会在这个过程结束之 前递归地对y调用DFS访问，即v的DFS函数结束时间先于u的DFS结束时间。从而 可以考虑在DFS调用过程中设定一个时间标记，在DFS调用结束时，对各结点计时。因 此，祖先的结束时间必然大于子孙的结束时间。 2)若u是结点v的子孙，则v为u的祖先，按上述思路，v的结束时间大于u的结束时间。 3)若u和v没有关系，则u和v在拓扑序列的关系任意。 从而按结束时间从大到小，可以得到一个拓扑序列。 实际上和深度优先遍历算法完全相同，只不过加入了变量time
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void DFS (int v,ALGraph *G,int time,int Time[]) { vistit[v]=1 ; ArcNOde *p=G->AdjList[v].first; while (p){ if (visit[q->AdjV]==0 ){ DFS(q->AdjV,G); } p=p->next; } time++; Time[v]=time; }
关键路径 图中所有路径长度=总工期的路径 ，都是关键路径。：在AOE网络中, 有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径 的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此， 完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路 径就叫做关键路径(Critical Path)。
AOE网，边表示活动，顶点表示事件
只有顶点事件发生后，各条边活动才能开始 顶点的所有入边活动都结束时，顶点事件才能发生 有些活动是能并行进行的
1 2 3 4 5 6 AOE网只有1个入度为0的顶点，开始顶点(源点)，他表示整个工程的开始 也只有1个出度为0的顶点，结束顶点(汇点)，他表示整个工程的结束 从源点到汇点的所有路径中，具有最大路径长度(总权值)的路径称为关键路径，关键路径上的活动称为，关键活动 在这里关键路径的总长度就是整个工程完成所需最短时间
1 2 3 4 5 6 7 8 9 10 11 12 vk-->顶点(事件) ai-->活动(边) 1.事件vk的最早完成时间ve(k) 2.事件vk的最晚完成时间vl(k) 3.边ai的最早完成时间e(i) 4.边ai的最晚完成时间l(i) 规定将发生时间最长的路线定为汇点的 最晚发生时间=最早发生时间(如果不规定一下最晚发生时间，那么没有意义，因为，前面的事件可以一直拖下去永远不执行) 可以通过逆拓扑排序先从后往前的倒推每个事件的最迟发生时间(由汇点来反推) 关键活动是，活动最迟发生时间=活动最早发生时间 的活动
课后习题1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1.以下叙述中，正确的是（A）。 A.只要无向连通图中没有权值相同的边，则其最小生成树唯一 B.只要无向图中有权值相同的边，则其最小生成树一定不唯一 C.从n个顶，点的连通图中选取n-1条权值最小的边，即可构成最小生成树 D.设连通图G含有n个顶点，则含有n个顶点、n-1条边的子图一定是G的生成树 解析：选项A最小生成树的算法是基于贪心策略的，每次从事选取权值最小的，且满足条件的边，如果各边权值不同，则每次选择的新的顶点也是唯一的，因此最小生成树是唯一的 选项B,若无向图本身就是一棵树，则最小生成树就是它本身，这时就是唯一的。选项C,选取的一1条边可 能构成回路。选项D,含有n个顶点、n-1条边的子图可能构成回路，也可能不连通。 2.最短路径一定是简单路劲 3.下面的（A）方法可以判断出一个有向图是否有环（回路）。 I.深度优先遍历Ⅱ.拓扑排序Ⅱ.求最短路径V.求关键路径 A.I、Ⅱ、IV B.I、II、V, C.:I、IⅡ、IⅢ D.全部可以 解析：深度优先遍历，深度优先遍历是逐层遍历的,通过栈等数据结构可以记录已经访问过的顶点。一旦发现重复顶点,立即结束遍历,返回最终结果。
1 2 最小生成树不唯一的话，得到的最小生成树就可能相同也可能不同 但是如果最小生成树唯一，那不同算法得到的就一定相同
1 拓扑排序结束条件时找到直至为空，如果有环，则无法找到拓扑序列
1 2 不能排成拓扑序列，说明有环，那么D正确 强连通分量-->就是顶点之间可以相互抵达，那么就是存在闭环
1 2 3 4 5 邻接矩阵 顶点指向方向 i->j 行->列 如果上三角矩阵：那么必定 编号小指向编号大 如果下三角矩阵：那么必定 编号大指向编号小的 而拓扑排序，必定是小编号指向大编号，那么体现在邻接矩阵就是上三角矩阵
1 2 3 4 5 6 7 8 关键路径手算 1.画出图 2.画表格，最早开始时间 ；最晚开始时间 3.从前往后依次计算各个顶点最早开始时间(就是等顶点之前所有顶点完成的时间) 4.之后再从后往前，求各个顶点的最晚开始时间(应该满足不影响工期，就是最后一个顶点的最早开始时间 21) 5.找出最早、最晚开始时间相等的点组成关键路径 关键路径的长度必然=整个工程完成的时间
1 2 3 I ：加入只有一个路径，那么关键路径就是自己，怎么变都是一条关键路径 II ：关键路径就是整个工程时间，没问题 III：如果有多条关键路径，降低某一条不影响其他条
1 2 3 DFS深度优先遍历 这样想，比如1这个结点最先入栈，在它后面的结点没有弹栈之前不会弹栈 递归的思考，对于每个结点都是这样，于是就神奇的发现，实现了逆拓扑排序，只需要在弹栈之后再输出元素就可以了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Dijkstra算法 前提：列出所有顶点与a的直接距离，没有直接相连设为∞； 1轮：a直接到达的是b、c。与原距离对比 一样，不更新距离，入路径更短的 b 2轮：b直接到达的是c、d。与原距离对比 {abc}<{ac} {abd}<{ad};更新距离，入路径更短的 c 3轮：c直接到达的是d、e、f。与原距离对比 {acd}>{abd}不更新 {ace}<{ae}更新，{acf}<{af}更新 入路径更短的 f 4轮：f直接到达的是 没有 只剩下 d、e 入路径更短的 d 5轮：d直接到达的是f、e。与原距离对比，{acde}={ace}不更新 {acdf}>{acf}不更新 入最后的 e 每一轮，根据新增顶点作为试探，列出所有与其直接相连的顶点，并将新开辟出的路径与原路径对比 如果更短就更新路径。并且最后将与之相连的最近的顶点，入到路径之中
1 2 3 4 5 拓扑排序 1.寻找入度为0的顶点 2.删除该顶点与其发出的边(由这个顶点指向的其他顶点的入度-1) 3.接着寻找入度为0的顶点 4...
1 2 3 4 顶点的最早开始时间与最晚开始时间容易求 需要注意的是，边的最早开始时间就是顶点的最早开始时间(顶点刚开始，就开启活动) 但是，边的最晚开始时间却不是起始顶点的最晚开始时间(活动可能有剩余时间等待)，所以 应该从 下一个顶点的最晚开始时间减去活动所需时间
1 2 3 4 5 6 7 拓扑排序 1.寻找入度为0的顶点 2.删除该顶点与其发出的边(由这个顶点指向的其他顶点的入度-1) 3.接着寻找入度为0的顶点 ... 注意：如果存在多个入度=0的顶点，那么拓扑序列可能有多个
1 2 时间余量：就是不拖延工期前提，活动最多能拖延多久 活动时间余量=结束顶点的最迟开始时间-开始顶点的最早开始时间-该活动的时间
1 2 (2)该图有多少个强连通分量？ 只有入度没有出度，或者只有出度没有入度的顶点，必然不可能和其他顶点连通，所以这种顶点自身就是一个强连通分量。通过不断去除已经找到的强连通分量进而更加清晰的寻找另外的强连通分量
1 2 3 4 说明如何用DFS 实现拓扑排序? - 深度优先遍历，会将先经过的结点入栈，先入后出，一般用于实现逆拓扑排序 - 如果反过来要实现逆拓扑排序，则需要定义一个全局变量time,标记当前结点的结束时间 - 然后将顶点按时间从大到小排序，得到的的就是拓扑序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Dijkstra最短路径算法能否给出一颗生产树？该树是否一定是最小生成树？ - 能，但不一定是最下生成树。 解答：Dijkstra最短路径算法能够给出一棵生成树，但该树不一定为最小生成树。虽然Dijkstra算法和Prim算法的思路与步骤较为相似，但两者的更新算法不一致，而其余部分完全一致。 Dijkstra算法对应的Min更新算法为 if(Min[j]>Min[k]+G[k][j]); Min[j]=Min[k]+G[k][j]; 而Pim算法Q对应的Min更新算法为 if(Min[j]>G[k][j]); Min[j]=G[k][j] 为此，可考虑以下的反例 对于以下的带权连通无向图
1 2 （2）.本质就是图结构体=顶点结构体+边结构体 （3）.本质就是找出R1到各个路由器的最短路劲，然后按照从小到大的顺序排序，Dijkstra算发就是按照，先入较短路径的顶点，然后根据新入顶点找下一个较短路劲顶点，这样得到的顶点路劲必然是后面加入的顶点路劲更长
1 2 3 （1）.按照prim算法过程依次选出边即可 （2）.题目只问一个问题——是否唯一？；答，唯一即可，无需多做解释 （3）.题目只问满足什么条件时？；答一个充分条件即可。
1 2 3 （1）."所有可能"，说明要列出所有，的最小生成树的情况 （2）.写prim算法名称-->奇怪怎么会有怎么简单的问题？ （3）.TTL就是信息保留时间，当路径长度大于TTL时，信息销毁
1 2 3 4 邻接表存储的图 DFS遍历使用了栈-->栈内存的顶点最多不超过顶点数n BFS使用了队列-->队列内的顶点数，最多也不超过n 那么DFS BFS空间复杂度都与n都有关,空间复杂度'不可避免'的O(n)
1 2 无论是DFS还是BFS 邻接矩阵都有nxn个空间需要依次遍历，所以时间复杂度是O(n^2)
1 2 3 4 5 6 7 8 9 DFS遍历 分析D选项 从a作为开始结点a-->e-->d-->f-->c 到c往下DFS发现边为NULL，执行到底不再递归弹栈,返回到c 返回c，发现c的next为空，执行到底，退出栈 返回f,发现.. 返回d,发现... 返回e,发现e的next边与b相连，于是对b递归，访问b -->最终顺序是a e d f c b
1 2 3 4 5 A.关键路径有争议，因为求关键路径，需要先求各个事件的最早开始时间和最晚开始时间，但是如果有环的话，那么就导致事件无限循环无法结束，最终报错-->至于通过报错判断是否有环是否可以利用还存在争议 B.Dijikstra算法是求最短路劲，通过依次加入顶点，更新距离的操作与有没有环没有关系 C.深度优先遍历算法.这里可以微调一下深度优先算法.将弹栈后的结点，清除器访问标记--> 这样做虽然会导致访问重复结点，但是我们的目的是判断是否有环，而不是遍历。所以有环的话，必然会在某一条深度递归中，压入已经存在栈内的顶点(重复顶点)，那么就可以判断有环存在。至于清除访问标记是因为该深度已经遍历，那么将节点释放相当于弹栈，以便判断下一条单条深度递归中的重复顶点。 D.广度优先遍历,无法实现有向图是否有环的判断，因为，广度优先遍历无法判断图是否有环，因为广度优先遍历是按照图的层次结构，从起始顶点开始，依次访问与它相邻的所有顶点，然后再访问这些顶点的邻接点，直到所有顶点都被访问为止¹。在这个过程中，如果一个顶点有一条边指向已经访问过的顶点，并不能说明这两个顶点在同一个环中，因为它们可能是不同层次的顶点。
1 2 3 这道题目需要注意的点： 1.对于写出深度优先生成树，不能根据给出的表，画出完整的图G后再进行深搜。因为给定的表隐含着遍历顺序，而你完整图中进行的遍历没有符合题目要求的顺序,因此，应该直接根据邻接表来深度搜索--> 1-->2-->3-->4-->5 2.对于写出广度优先生成树，同样的道理不能按照画出的完整图来遍历，原因依然是要按照题目中邻接表中隐含的顺序来进行推进-->1 2 3 4 5 如下
1 2 3 算法设计 1.切入点：树的顶点=数的边+1 2.步骤：初始化两个变量i j,分别存储顶点数目，边的数目；遍历顶点，没访问一个顶点i++,在访问与该点所有相连的边,每条边j++;最终边的数量统计了两次，因为一条边连接了两个顶点，所以最终统计i=j/2 + 1是否成立
1 2 3 4 5 6 DFS如果不用递归，那么必须需要栈的数据结构来替代递归栈. 邻接表采用深度优先遍历，从i开始-->i入栈-->遍历j-->j入栈-->跳转到j开头那一行-->遍历k-->k入栈-->跳转到k的那一行-->...-->遍历到最深层-->一次往回弹栈 从过程中，入栈需要存入两种信息： 1.该入栈结点的编号 2.该入栈顶点位于哪行的地几个位置(为了使得弹栈之后回到相对应的位置继续遍历) 3.另外还需要，用一种数据结构存储已经遍历过的顶点，防止重复遍历
1 2 3 4 用遍历算法判断邻接表方式存储的有向图中，是否存在顶点i到j的路径 1.将i作为遍历的开始顶点 2.采用任意遍历算法，遍历只要寻找到顶点j就说明存在从i到j的路径,返回true，否则返回false
课后习题2
1 2 3 邻接矩阵:nxn 无向图:矩阵中2e个1 0个数=n^2-2e
1 2 3 图的邻接表的存储结构-->左边一列，顶点结构体；右边的是由顶点引出的与顶点相连的所有边结构体。 这题顶点v在边表中的出现次数，是指边表中存储的是边指向的下一个顶点(有向图)
1 邻接表存储无向图，由于无向图边是双向的，所以n(n-1)条边
1 2 3 4 5 6 删除有向图某个顶点v相关的所有边 1.删除该顶点引出的所有一连串的边表结点，最多引出n-1条边 O(n) 2.删除所有指向该顶点的所有边，由于无法判断起始点是哪一个，所以只能从头到尾遍历O(e) 最终时间复杂度O(n+e)
1 2 3 4 十字链表是存储有向图 邻接多重表是存储无向图 推出十字链表和邻接多重表的目的是为了将某一条边的两个顶点都表示出来，以至于可以直接通过一条边找到两端的两个顶点，而不是只能从一个顶点出发
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 typedef struct { int numVertice,numEdge; char Vertice[maxV]; int Edge[maxv][maxv]; }Graph; int IsExistEL (Mgraph G) { int degree,count; for (int i=0 ;i<G.numV;i++){ degree =0 ; for (int j;j<G.numV;j++){ if (G.Edge[i][j]==1 ){ degree++; } } } if (degree%2 ==1 ){ count++; } if (count==2 ||count==0 ){ return 1 ; }else { return 0 ; } }
查找 基本概念查找长度：查找运算中，需要对比关键字的次数平均查找长度：（ASL Average Search Length），所有查找过程中进行关键字比较次数的平均值
顺序查找 时间复杂度 无论如何优化，始终为O(n)
折半查找 针对有序的顺序表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 typedef struct { ElemType *data; int len; }SSTable; int Binary_Search (SSTable T,ElemType key) { int low=0 ,high=T.len,mid; while (low<=high){ mid=(low+high)/2 ; if (T.data[mid]==key){ return mid; }else if (T.data[mid]<key){ high=mid-1 ; }else { low=mid+1 ; } } return -1 ; }
折半查找判定树折半查找判定树的性质
1 2 3 4 5 6 7 8 9 - mid=(low+high)/2 采用的是向下取整方式 - 结点数n为奇数，右子树结点数-左子树结点数=1 - 结点数n为偶数，右子树结点数=左子树结点速 - 折半查找判定树一定是平衡二叉树 - 折半查找判定树，只有最下面一层不是满的，因此求树高h于完全二叉树公式一致 - 失败结点：n+1个也就是查找成功结点的空链域数量 - 每个元素所在层数表示查找次数，所以查找成功，失败的时间复杂度不会超过树高(树高不包括失败 结点)log2(n+1),时间复杂度O(log2n)
1 树高不包含失败的结点(紫色的空节点)，因为查找失败的查找次数也就是查找到其父节点的查找次数(也就是失败结点的父节点的树高)，因为，当查找到树梢结点发现没找到就查找失败，那么查找是吧的次数也就是树梢结点的高度了
分块查找 1 特点：块内无序，块间有序,块内存放数据个数不同，索引中保存每个块的最大关键字和起始到末尾的地址
1 2 3 4 5 6 7 8 9 10 11 12 - 考察选择，不要求代码 索引表中保存的是每个区块中最大的关键字 分块查找 - 对分块的索引表采用顺序查找 - 对分块的索引表采用折半查找 分两种情况： 1.查找元素正好是索引表的元素,例如30 2.查找元素不是索引表的元素此时，折半查找，最终low>high，low指向的就是目标元素 所在区块
1 2 顺序查找方式 ASL=查索引表的平均查找长度+查分块的平均查找长度
二叉查找(排序)树(BST) 查找-插入-构造树二叉查找(非递归) 二叉查找(递归) 二叉排序树插入(递归) 二叉排序树插入(非递归) 二叉排序树的建立 1 2 3 4 5 6 7 8 9 10 BSTNode *BST_Search (BSTree T,int key) { while (T!=NULL &&key!=T->key){ if (key<T->key){ T=T->left; }else { T=t->right; } } return T; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 BSTNode *BST_Search (BSTree T,int key) { if (T==NULL ){ return NULL ; } if (key==T->key){ return T; } else if (key<T->key){ return BST_Search(T->left,key); } else if (key>T->key,key){ return BST_Search(T->right,key); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 bool BST_Insert (BSTree &T,int k) { if (T==NULL ){ T=(BSTree)malloc (sizeof (BSTNode)); T->key=key; T->left=NULL ; T->right=NULL ; return true ; } else if (k==T->key){ return false ; } else if (k<T->key){ return BST_Insert(T->left,k); } else { return BST_Insert(T->right,k); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 bool BST_Search (BSTree &T,int k) { while (T!=NULL ){ if (k=T->key){ return false ; } else if (k<T->key){ T=T->left; } else { T=T->right; } } T=(BSTree)malloc (sizeof (BSTNode)); T->key=k; T->left=NULL ; T->right=NULL ; return true ; }
1 2 3 4 5 6 7 8 void Creat_BST (BSTree &T,int str[],int n) { int i=0 ; T=NULL ; while (i<n){ BST_Insert(T,str[i]); i++; } }
查找ASL分析
二叉排序树删除情况1-删叶节点 情况2-只有左或·右结点- 同时有左右结点 有两种方式
回顾
平衡二叉树 平衡二叉树概念 1 2 3 4 5 平衡二叉树(Balanced Binary Tree)，在二叉排序树基础上，树上任意结点的左子树与右子树高度只差不超过1 平衡因子=左子树高度-右子树高度 如果二叉树平衡，各个结点的平衡因子只能是0,-1,1
平衡二叉树插入调整 1 2 3 平衡二叉树插入新结点如何保持平衡？ 只需调整引起不平衡的最小的那个子树，画圈的部分
1 2 3 4 5 6 7 8 9 10 如何调整？ 插入导致不平衡分为四种情况：(A是最小不平衡子树) LL 在A的左孩子的左子树中插入导致不平衡 RR 在A的右孩子的右子树中插入导致不平衡 LR 在A的左孩子的右子树中插入导致不平衡 RL 在A的右孩子的左子树中插入导致不平衡 通过旋转来调整二叉树的失衡 要找到最小的那颗失衡的二叉树调整
LL LL右旋调整
RR RR左旋调整
LL&RR代码思路
LR LR
RL RL
总结
平衡二叉树ASL分析
平衡二叉树删除调整 1 2 3 4 5 ①删除结点(方法同“二叉排序树”) ②一路向北找到最小不平衡子树，找不到就完结撒花 ③找最小不平衡子树下，“个头”最高的儿子、孙子 ④根据孙子的位置，调整平衡(LL/RR/LR/RL) ⑤如果不平衡向上传导，继续②，对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡（不平衡向上传递）
红黑树 红黑树定义性质 1 虽然平衡二叉树与红黑树，search、Insert、Delete操作时间复杂度都是O(log2(n)),但是平衡二叉树需要频繁调整数的形态；如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大），再进行LL/RR/LR/RL调整
1 2 3 4 5 6 7 8 9 红黑树特性： 1.每个结点或是红或是黑色 2.根节点一定是黑 3.叶子结点均是黑(指的是失败结点，查找失败结点，也叫NULL结点) 4.不存在两个相邻红结点(即红结点的父、孩子结点一定是黑) 5.对于每个结点，从该结点到任一叶子结点的简单路劲，所含黑结点数量一致 =>1.红黑树从根节点到叶结点(NULL结点)的最长路径长度不大于最短路径的两倍 2.n个结点的红黑树高度h<=2log2(n+1) --> search时间复杂度O(log2(n))
红黑树结点结构体
1 2 3 4 5 6 7 struct RBnode { int key; RBnode* parent; RBnode* lChild; RBnode* rChild; int color; }
红黑树插入 插入根为黑 为了维持，每条路径黑色结点数量相同，默认插入红色结点。冲突的情况只可能是父节点同样为红色，情况分两种，看叔叔结点颜色。 叔叔结点为红色，三角颜色取反,影响向上传递，情况另外讨论
叔叔结点为黑色，向上的3个结点，选取中值作为根，且满足”黑根+叶子红+左给左+右给右”
B树 m阶B树——结点关键字个数⌈m/2⌉-1≤n≤m-1.例5阶B树，关键字2≤n≤4(根节点除外，可以是1)；叶结点在终端结点之下，没有存储关键字，看做查找失败的结点。
B数插入的规则：
单个结点，满了后，中间结点作根，两端分别做左右子树分裂。 只能从最低层的终端插入。 子树结点也满了后，按照1的原则，将中间结点提到父节点，在分类出左右两个子树。 父节点满了后，需要按照同样的规则网上分裂。 依次将关键字5,6,9,13,8,2,12,15插入初始为空的4阶B树
B+树 只考察基本概念
散列查找 散列表的基本概念
什么是散列表、散列函数？
同义词和冲突 冲突（碰撞） ：在散列表中插⼊⼀个数据元素时，需要根据关键字的值确定其存储地址，若该地址已经存储了其他元素，则称这种情况为“冲突（碰撞）”。同义词 ：若不同的关键字通过散列函数映射到同⼀个存储地址，则称它们为“同义词”。
如何减少冲突？ 拉链法
开放地址法
散列函数的构造
设计散列函数应该注意什么？
除留余数法 除留余数法 —— H(key) = key % p适⽤场景：较为通⽤，只要关键字是整数即可
为什么要取质数
原因：对质数取余，可以分布更均匀，从⽽减少冲突
直接定址法 直接定址法 —— H(key) = key 或 H(key) = a × key + b适⽤场景：关键字分布基本连续
数字分析法 数字分析法 —— 选取数码分布较为均匀的若⼲位作为散列地址；适⽤场景：关键字集合已知，且关键字的某⼏个数码位分布均匀
平方取中法 平⽅取中法——取关键字的平⽅值的中间⼏位作为散列地址。适⽤场景：关键字的每位取值都不够均匀
平方取中间两位，由于中间的两位的值受到了原来每一个数码位的影响，所以，相对具有代表性 处理冲突的方法–拉链法
拉链法散列表的插入 散列表数组中，存的是链表的头指针，这里采用的是头插法，也可以尾插法
拉链法散列表的查找
拉链法散列表的删除
处理冲突的方法–开放地址法
开放定址法：如果发⽣“冲突”，就给新元素找另⼀个空闲位置。
开发地址法的基本原理
线性探测法
平方探测法
双散列法
伪随机序列法
特别注意：关于删除操作 注意：采⽤“开放定址法”时，删除元素不能简单地将被删元素的空间置为空，否则将截断在它之后的探测路径，可以做⼀个“已删除”标记，进⾏逻辑删除。【注：⽆论线性探测法、平⽅探测法、双散列法、伪随机序列法原理都⼀样。删除元素时，只能逻辑删除】
课后习题 顺序查找、折半查找、分块查找习题 1 顺序查找概念，从一端到另一端，适合链式存储结构和顺序存储结构
1 因为查找的目标元素是任意的，对有序表而言，需要一次从头查找直到遇到mubiao,而对无序表而言依然需要从头查找直到遇到目标，所以，无论有序还是无序表，只要查找目标四任意的，那么查找平均时间都是一样的
1 2 B.字符型不能比较，所以没法做到有序，也就无法二分查找 D.二分查找只能以顺序方式存贮
1 折半查找树一定是一颗平衡二叉树，因为查找的元素一定是中间的元素，那么就有左半部分与右半部分，也就是左右结点，最极端的情况也就是两端没有左或没有右，也就是说，左右子树的高度只差不会大于1
1 2 折半查找对应着一颗平衡二叉树，任意结点的左右子树高度只差不超过1，所以对应查找时间（=树高=查找次数=log2(n)）,但是二叉排序树，没有限制高度相差，所以二叉排序树可以单个高度很高，加入要查的目标元素就在这个很高的分支里面，那么查找次数就多。 所以，折半查找和二叉排序树的查找时间性能上，时而相同时而不同，但是大部分是折半查找效率高，
1 2 3 折半查找树是平衡二叉树 但是不是所有平衡二叉树都满足折半查找树要求，折半查找树，左右子树都平均，最多相差一两个结点，但是平衡二叉树比如下图，右下有一大部分空缺。 所以如果找折半查找树的高度，可以把其当成一颗完全二叉树来求
1 空节点的个数就是查找失败的个数，但是查找失败所需次数(查找长度)不是失败结点的高度，而是查找到的最后一个结点的查找次数，也就是失败结点没有高度
1 分块查找，将数据分为若干块，块间有序是指按每块的最大值排序，块内无序，块内数据个数无需相同
1 2 最好情况：最理想分块 √n ;块内有序;块内快外都进行二分查找； 在上述最好情况下，最多比较16次
1 对于A 500,200说明500向左走,左边的应该都比500小符合；200,450,说明200向右走，说明200右边应该比比200大且比500小,不符合；
1 该题的算法本质就是顺序查找，而顺序查找如果要比折半查找比较次数更少，那只有x接近数组开头处
1 2 3 B.折半查找当结点个数为偶数时，要么统一选取左边结点为中间结点，要么统一选取右边结点为中间结点，看图B 末梢处，剩余两个结点，一边的选取了靠右的为中间结点，另一边选取了考左的为中间结点，不符合算法 C.与B类似 D.左子树4结点，右子树5结点，说明偶数结点数，统一选取考左的为中间结点，那么又因为，更小的子树的左子树为2，右子树为1，选取的又是靠右的，互相矛盾，所以不符合算法
1 2 k分查找成功时间复杂度-->查找树的高度logk n + 1-->查找成功次数最多logk n + 1时间复杂度O(logk n) 查找不成功查找次数最多也为logk n + 1-->时间复杂度也为O(logk n)
1 2 3 4 5 顺序查找查找成功7,15，23...8N-1 --->共n个-->查找长度1+2+3+..+n 二分查找查找成功 第一层结点查找长度分别为2,3,4,5,..n+1 第二层结点查找长度分别为2x3,2x4,2x5...2x(n+2) 第三层.. 4x4,4x5,4x6...4x(n+3)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 int BSearch (SSTable ST,x,int begin,int end) { if (begin<=end){ int mid = (begin+end)/2 ; if (ST.data[mid]=x){ return mid; }else if (ST.data[mid]<x){ end = mid-1 ; Bsearch(ST,x,begin,end); }else { begin = mid+1 ; Bsearch(ST,x,begin,end); } }else { return -1 ； } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 int Search_swap (SSTable &ST,int x) { int i=0 ; while (ST.data[i]!=x&&i<ST.length){ i++; if (i>=ST.length){ return -1 ; } } Swap(ST.data[i],ST.data[i-1 ]); return i-1 ; } LinkList Search_swap (Linklist &L,int x) { LinkList p,q; if (L->next.data=x){ return L->next; } for (p=L;p->next->next.data!=x;p=p->next){ if (p->next->next==NULL ){ return NULL ; } } q=p->next; p->next=q->next; q->next=q->next->next; p->next->next=q; return p->next; }
平衡二叉树习题 1 2 A.查找失败则插入所查找的结点，查找失败说明找到结点的右边或左边已经无节点才导致失败 那么，直接在空的位置上插入结点，并不会导致树的分裂和组合
1 2 3 4 完全二叉树才是二叉排序树的最理想情况 完全二叉树求深度以满二叉树为模板 ，根据等比数列求和 --> n=2^h -1 -->这是n完全沾满第h层的时候 但是第h层没有完全沾满时，数的高度同样是h,这样就需要对log2(n+1)向上取整
1 根据平衡二叉树，高度为h所需最少结点数的关系，解决此题
1 2 3 4 5 6 平衡二叉树任意结点的左右子树高度只差不超过1 H=1, n=1 H=2, h左=1，h右=0 ; 1+1+0=2 H=3, h左=2，h右=1 ; 1+2+1=4 -->h左 根据前面H=2求得的n，h右 根据前面H=1求得的n ... 递推
1 2 平衡因子均为1-->用最少的结点构成高度最高的平衡二叉树 与之前那题一模一样
1 2 3 1.平衡二叉树的调整，需要调整的是插入后导致的最小的不平衡子树 2.这题是RL型，RL是指，新插入的导致二叉树不平衡的结点是相对于最小不平衡子树的头号结点的位置，是先往右，再往左 3.相对应的树的调整相当于打方向盘，从后往前考虑，先是往左偏了，就要右旋。接着考虑上层往右偏了，就要左旋
1 直到一个二叉排序树的先序遍历序列。-->数字从小到大就是中序遍历序列-->结合中序遍历序列和先序遍历序列，就能完整的画出一颗二叉排序树-->在根据树来进行分析
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 bool IsOrderTree (BiTree T) { Stack S; Push(S,T); BiTree Q; while (!IsEmpty(S)){ Q=Pop(S); if (Q->lift!=NULL ){ if (Q->lift->data<Q->data){ Push(S,Q->lift); }else { return false ; } } if (Q->right!=NULL ){ if (Q->right->data>Q->data){ Push(S,Q->right); }else { return false ; } } } return true ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int BS_Search_high (BSTree T,int x) { BSTree Q = T; int count=1 ; while (Q){ if (Q->data=x){ return count; }else if (Q->data<x){ Q=Q->left; count++; }else { Q=Q->right; count++; } } return false ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 void Jude_AVL (BiTree T,int &balance,int &h) { int bl=0 ,br=0 ,hl=0 ,hr=0 ; if (bt==NULL ){ h=0 ; balance=1 ; } else if (bt->lichild==NULL &&bt->rchild==NULL ){ h=1 ; balance=1 ; } else { Judge_AVL(bt->lchild,bl,hl); Judge_AVL(bt->rchild,br,hr); h=(h1>h2?h1:h2)+1 ; if (abs (h1-h2)<2 ){ balance=bl&&br; }else { balance=0 ; } } }
1 2 3 1.从大到小输出-->中序遍历稍作修改 2.输出的值不小于k，对中间结点输出的时候，做一个判断 代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 void print_dechute (BSTree T) { if (T==NULL ){ return ; } if (T->right!=NULL ){ print_dechute(T->right); } if (T->data>=k){ printf ("%d" ,T->data); } if (T->left!=NULL ){ print_dechute(T->left); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 这题思路是 在每个结点里面保存，以当前结点为根的子树中总共有多少个结点 假设这棵树的根节点是T 一下几种情况： 1.T->lchild==NULL - 若T->rchild非空且k=1,则T就是滴k小节点 - 若T->rchild非空且k!=1,则第k小元素在T的右子树上 2.T->lchild!==NULL - T->lchild->count=k-1,则T就是第k小元素 - T->lchild->count>k-1,则第k小元素必在左子树，继续到左子树中去找 - T->lchild->count<k-1,则第k小元素必在右子树，继续搜索右子树，寻 找第k-(T->lchild->count+1)小的元素 代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 BSTree Search_Small (BSTree T,int k) { if (k<1 ||k>T->count){ return NULL ; } if (T->lchild==NULL ){ if (k==1 ){ return T; }else { return Search_Small(T->rchild,k-1 ) } }else { if (T->lchild->count==k-1 ){ return T; } if (T->lchild->count>k-1 ){ return Search_Small(T->lchild,k-1 ); } if (T->lchild->count<k-1 ){ return Search_Small(T->rchild,k-(T->lchild->count+1 )); } } }
红黑树习题
1 2 3 4 5 6 7 8 9 10 11 12 13 D选项：根据两个性质解答 1.红黑树对于每个结点，到叶子结点的任意一条路径上的黑结点的个数相同 2.红结点不能与红结点相邻 所以红黑树的单条从根结点到叶子结点的路径上的黑色结点个数是确定的设为x 假设出发结点是black: - 高度最小的子树，全部位黑色结点，高度为 x-1 - 高度最高的子树，黑色结点与红色结点相间出现 - 子树原结点是black--> x-1 + (x-2)=2x-3 - 子树原结点是red --> (x-1)+(x-1)=2x-2 假设出发结点是red: - 高度最小子树，x - 高度最大子树，2x-1 左右子树高度之比都小于2
1 2 3 4 A.红黑树是自平衡的树，但不是平衡二叉树 B.红黑树所有结点都是黑色，那么它一定是满二叉树因为从根节点出发，到叶子结点，黑色结点数是一样的 C.红色结点孩子结点可以全为黑 D.一看就是错的
1 2 3 4 5 红黑树的插入操作 1.插入的结点始终一致染成红色 2.如果违反了不红红，则看叔叔的颜色 3.黑叔，影响不向上传递，只需先按照平衡二叉树旋转，然后将旋转后的爷爷结点染黑 4.红叔，影响向上传递，只需向先将爷爷结点染红，儿子染黑，然后爷爷结点作为新插入结点继续向上判断
B、B+树习题 B树与B+树区别
m阶B 树，对于根节点的子树，子树2m；除了根节点的非叶子结点，子树**⌈m/2⌉m**
排序 注1：通常来说，408算法题不会限制你具体使用哪种算法 快速排序最实用，代码简，时间复杂度低；相比堆排序代码更简洁，、相比2路归并，空间复杂度小
课后习题 1 2 3 4 1.拓扑排序是将有向图中所有结点排成一个线性序列，虽然也是在内存中进行的，但它不属于我们这里所提到的内部排序范畴，也不满足前面排序的定义。 2.排序算法的稳定性是指? 经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变
插入排序 直接插入排序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 加入需要排序的数组是arr=[1,0,6,3,2,7,5] 需要两个下标指针i、j 初始时，只有第一个元素有序，那i从 1开始，j=i-1 arr=[ 1, 0, 6, 3, 2, 7, 5] j i 先将arr[i]=temp存着 如果arr[j] > arr[i],arr[j]往后移一位，arr[j+1]=arr[j],j--; arr[ 1, 1, 6, 3, 2, 7, 5] j i j+1 arr[j+1]=temp arr[ 0, 1, 6, 3, 2, 7, 5] j i j+1 ...
1 2 3 4 5 6 7 8 9 10 11 12 void insert_sort (ElemType *str,int n) { int i,j,temp; for (i=1 ;i<n;i++){ temp=str[i]; for (j=i-1 ;j>=0 &&str[j]>temp){ str[j+1 ]=str[j]; j--; } str[j+1 ]=temp; } }
1 2 3 4 5 6 7 8 9 10 11 时间复杂度： 在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一次而不用 移动元素， 因而时间复杂度为O（n）. 在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反（逆序），总的比较次数达 到最大，总的移动次数也达到最大，总的时间复杂度为O（n^2）. 平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为 平均情况下的时间复杂度，总的比较次数与总的移动次数均约为n^2/4。 稳定性： 由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置 发生变化的情况，即直接插入排序是一个稳定的排序方法
希尔排序
课后习题 1 2 3 4 5 1.在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。 A.直接插入排序B.简单选择排序C.快速排序 D.归并排序 解析:待排序序列基本有序，只需比较n-1次时间复杂度O(n),达到效率最高
交换类排序 冒泡排序 1 2 3 4 5 6 7 8 从后往前(或从前往后)两两比较相邻元素的值，如果逆序，就交换，直到将最小元素，交换到最上层 第1轮，比较n个元素，比较n-1次，找到最小的，放到第一位 第2轮，比较n-1个元素，比较n-2次，找到剩余中最小，放到第二位 ... 比较n-1轮 n-1 + n-2 + ...+ 3 + 2 + 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 void bubble_sort (ElemType arr[],int n) { int i,j; bool flag; for (i=0 ;i<n-1 ;i++){ flag=false ; for (j=n-1 ;j>i;j--){ if (arr[j]<arr[j-1 ]){ swap(arr[j],arr[j-1 ]); flag=true ; } } if (flag==false ){ return ; } } }
1 2 3 4 5 6 时间复杂度： 最好情况：数组本身有序，那么比较第一轮比较了n-1次后，标记返回false，退出排序，O(n) 最坏情况：O(n^2) 平均：O(n^2) 空间复杂度：O(1) 稳定性：由于i>j且A[i]=A[j]时，不会发生交换，因此冒泡排序是一种稳定的排序方法。
快速排序 1 2 3 4 5 6 7 8 一个顺序表 以第一个数为基数，赋值给mid存起来，此时，基数的位置看做为空 定义两个指针i j i从左往右找比3大的数，i停止 j从右往左找比3小的数，j停止 然后i j 对应的数完成一次交换，i j 继续前进 循环..直到ij相遇i==j arr[i]=mid
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int partition (ElemTypeA[],intlow，inthigh）{ ElemType mid=A[1 ow]： while （low<high）{ while （low<high&sA[high]>=mid) --high； A[low]=A[high]； while (low<high&sA[low]<=mid) ++1 ow； A[high]=A[low] } A[low]=mid return low； void quick_sort(ElemType *str,int low,int high){ if (low<high) { int postion = partition(str, low, high); quick_sort(str, low, postion - 1 ); quick_sort(str, postion + 1 , high); } return ; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 时间复杂度 最好情况：每次分割都能平均分成两份则2^x=n; x=log2 n;每轮分割，所有子数组 的比较总次数n-1次 所以是(n-1)log2 n,O(n)=nlog2 n 平均状态：接近最好情况O(n)=nlog2 n 最差情况：如果数组本来就有序，那么每次都无法一次切一半，变成从1到n-1都要 分割一次,每轮分割依旧比较n-1次，那么O(n)=n^2 空间复杂度 容量与递归的最大深度一致，最好情况log2 n ;最坏n-1 稳定性： 在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换 到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方 法。例如，表L={3,2,2},经过一趟排序后L={2,2,3},最终排序序列也是L= {2,2,3},显然，2与2的相对次序已发生了变化。 快速排序时内部排序算法中平均性能最优的一种算法
选择排序 简单选择排序 1 2 3 4 5 6 7 8 9 数组设置两个指针 min j 第一轮： min指向第1个数据，j指向min后一个,j移动寻找比min小的，然后min=j，j遍历到最后，最终交换arr[i]和arr[min] 第二轮： min指向第2个数据，重复上述步骤 ...重复n-1趟
1 2 3 4 5 6 7 8 9 10 11 void SelectSort (ElemType A[],int n) ( for (int i=0 ;i<n-1 ;i++){ int min=i; for (int j=i+l;j<n;j++){ if (A[j]<A(min]){ min=j; } } swap(A(i],A[min]); } }
1 2 3 4 5 6 7 空间复杂度：第一轮比较n-1次 第二轮比较n-2次 ...最后一次比较1次 n-1 + n-2 + n-3 +...+3 + 2 + 1=(n-1)n/2 所以是O(n^2) 最好最坏都是O(n^2) 稳定性：在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同 关键字元素的相对位置发生改变。例如，表L={2,2,1},经过一趟排序后L={1,2,2},最终排 序序列也是L={1,2,2},显然，2与2的相对次序已发生变化。因此，简单选择排序是一种不稳 定的排序方法
堆排序 1 2 3 4 5 6 7 8 9 10 11 引入大根堆的概念： 对于一颗二叉树，任意结点的数值要比左右子树的所有结点的值都大 这样一来，根节点成为了最大的结点 既然大根堆的根节点最大，就不断调整为大根堆： 对非叶子结点进行检测，判断这些非根节点是否大于左右 非叶子结点也就是-->叶子结点的父节点-->i/2向下取整 例如下面这个例子： 想要调整为大根堆，从8/2=4号结点(非终端结点)开始调整, 然后3号结点78,接着2号结点17,最后1号结点53 这样从后往前调整-->若元素互换破坏了下一级的堆-->则采用相同的方法继续往下调整
1.实现逻辑1.建立大根堆 :
把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整 检查当前结点是否满足根≥左、右若不满足，将当前结点与更大的一个孩子互换 若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整(小元素不断下坠) 一般从最底层的分支结点开始调整1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 void BuildMaxHeap (int A[],int len) { for (i=len/2 ,i>0 ,i--){ HeadAdjust(A,i,len); } } void HeadAdjust (int A[],int k,int len) { A[0 ]=A[k]; for (son;son<=len;son*=2 ){ if (son<length&&A[son]<A[son+1 ]){ son++; } if (A[k]<A[son]){ A[k]=A[son]; k=son; }else { break ; } } A[k]=A[0 ]; }
2.交换堆顶元素与最后一个元素.并将小元素下坠,恢复成大根堆
根节点最多才下坠h-1次，且没下坠一次最多比较2次，根结点最多比较2(h-1)次 时间复杂度 O(h) 时间复杂度,其他结点<根节点 , 假设每个都是 O(h),公有n个结点 O(nh) h高度=log2n ，总时间复杂度O(nh)=O(nlog2n) 2.算法稳定性
堆排序不稳定 假设只有1、a1、a2当左右子节点相同时a1=a2，会优先考虑左结点和根结点交换 排序时，交换根结点与最后结点，使得位序在前的a1跑到a2后面，–>1、a2、a1 因此是不稳定的 堆的插入和删除 1 2 3 4 堆的插入： 1.插入的新元素放到表尾，最末尾的结点 2.与父节点对比，对于小根堆而言，如果新元素比父结点更小，二者互换 3.新元素一路上升,直至无法继续上升为止
1 2 3 堆的删除： 1.被删除的元素空出来的位置，用堆底部的元素替代 2.最后让该元素不断下坠，直至无法下坠
归并排序 什么是归并？ 1 2 3 归并两个有序数组 定义指针i指向有序数组1，指针j指向有序数组2,指针k指向要放入的数组 对比i,j所指向的元素，选择更小的一个放入k中
多路归并 1 2 4路归并，就是归并4个数组 根据规律发现，m路归并，每次选出一个元素，最少需要比较关键字m-1次
单个归并代码实现 1 2 3 4 5 6 7 merge的时候，需要三个指针,i指向A的有序的前半段，j指向A有序的后半段，k指向放入的数组的当前位置 1、将A[] 元素全部复制放到B[] ，i ,j分别对应low\mid+1起始位置，k=i. 2、i j 先比较，小的放入A[k],i++,j不动，k++ 3、直到有剩余，i到头了，j还没到头;或者j到头了，i还没到头。while循环将剩余的全部放入,k随着++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 int *B=(int *)malloc (n*sizeof (int ));void Merge (int A[],int low,int high,int mid) { int i,j,k; for (k=low;k<high;k++){ B[k]=A[k]; } for (i=low,j=mid+1 ,k=i;i<=mid&&j<=high;k++){ if (B[i]<=B[j]){ A[k]=B[i]; i++; }else { A[k]=B[j]; j++; } } while (i<=mid){ A[k++]=B[i++]; } while (j<=high){ A[k++]=B[j++]; } }
归并排序完整代码 1 2 3 4 5 6 7 8 void MergeSort (int A[],int low,int high) { if (low<=high){ int mid=(low+high)/2 ; MergeSort(A,low,mid); MergeSort(A,mid+1 ,high); Merge(A,low,mid,high); } }
归并排序效率分析 1 2 3 4 5 空间复杂度： 递归调用栈的所占的空间不会超过log2 n 数量级；运用了额外的数组B空间O(n) 相加O(log2 n)+O(n);舍去小的--> O(n) 时间复杂度： 每一层归并时间复杂度O(n),共h=log2 n 层，时间复杂度O(nlog2 n)
基数排序 基数排序算法 1 2 3 4 5 6 7 8 9 10 11 12 基数排序： 递增排序： 1.分别对一组数据根据他的的个位、十位、百位、分别先后进行排序 2.其中个位为最次位关键字(对整体的值影响最小)，百为为最主要关键字(对 值影响最大) 3.先根据对权重最低的个位对数进行分配收集，然后在第一次排好的序列之 上，再根据十位进行分配收集，最后是百位-->最红会得到一个有序序列 递减排序： 步骤与递增相同，不过是先对高位进行分配收集，后对低位进行分配和收集 注意： 基数排序不是基于“比较”的排序算法，而是根据相同位数字的不同进行分类规整然 后收集的过程，只是这个分类收集的顺序导致了最后的有序
基数排序算法效率分析 1 2 3 4 5 6 7 8 9 空间复杂度： 初始序列为一串链表，定义了一个链式队列的数组用来分配各个数字，由于数组里 只是存放队头指针+队尾指针，实际所需的空间只有数组的10个空间，里面的队列是 在原有链表序列的基础上修改指针指向得到，并没有消耗多余的空间。所以空间复 杂度O(r)-->r是数字可能出现的种类0~9 时间复杂度： 一趟分配n个O(n);一次收集扫描r个队列O(r) -->因为只需将队列整个拆下来拼接 总共分配收集3趟,设趟数为d 时间复杂度 O(d(n+r))
基数排序应用
外部排序 1 2 3 什么是外部排序？ 对磁盘(外存)中的数据进行排序，由于外存容量很大，但内存容量很小，要对外存中所有 数据进行啊排序的话，内存放不下
新增 卡特兰数
1 2 题目转化-->4个结点的二叉树有多少种形状，然后可以将a b c d按照先序遍历填进二叉树里(填法唯一) (每种形状必定能按照一定顺序填 a b c d 使得先序遍历出来次序符合要求)
1 因为1入栈马上出栈，接着2入栈马上出栈，所以只看后面三个数的出栈序列
并查集(2022新增考点)
Find查操作：如何查到一个元素到底属于哪个集合？
从指定元素出发，一路向北，找到根节点，判断根节点是否相同 Union并操作：如何把两个集合合并为一个集合？
让一棵树成为另一棵树的子树即可 双亲表示法：便于找到父节点(查)，便于合并两棵树(并)
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #define MaxSize 100 typedef struct { char data; int parent; }PTNode; typedef struct { PTNode node[MaxSize]; int n } #define Size 20 int UFSets[Size]; void Init (int S[]) { for (int i=0 ;i<Size;i++){ S[i]=-1 ; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 int Find (int S[],int x) { while (S[x]>=0 ){ x=S[x]; } return x; } void Union (int S[],int root1,int root2) { if (root2==root1){ return ; } if (S[root1]>S[root2]){ S[root1] += S[root2]; S[root2]=root1; }else { S[root2] += S[root1]; S[root1] = root2; } }
总结
find优化+Union优化
课后习题
