浙江大学数据结构学习笔记

浙江大学数据结构学习笔记

数据结构浙江大学学习笔记

求最大子列和问题

int MaxSum1(int a[], int N)
{int i, j, k, ThisSum, MaxSum = 0;for(i = 0; i < N; i++){for(j = i; j < N; j++){ThisSum = 0;for(k = i; k <= j; k++)ThisSum += a[k];if(ThisSum > MaxSum)MaxSum = ThisSum;}}return MaxSum;
}int MaxSum2(int a[], int N)
{int i, j, ThisSum, MaxSum = 0;for(i = 0; i < N; i++){ThisSum = 0;for(j = i; j < N; j++){ThisSum += a[j];if(ThisSum > MaxSum)MaxSum = ThisSum;}}return MaxSum;
}int MaxSum4( int A[], int N )  
{   int ThisSum, MaxSum;int i;ThisSum = MaxSum = 0;for( i = 0; i < N; i++ ) {ThisSum += A[i]; /* 向右累加 */if( ThisSum > MaxSum )MaxSum = ThisSum; /* 发现更大和则更新当前结果 */else if( ThisSum < 0 ) /* 如果当前子列和为负 */ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之 */}return MaxSum;  
}

栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成

#define MaxSize
typedef struct SNode *Stack;
struct SNode{ElemenType Data[MaxSize];int Top;
};void Push(Stack PtrS, ElemenType item);
{if(PtrS -> Top == MaxSize-1)printf("栈满");else{PtrS -> Data[++(PtrS -> Top)] = item;}
}ElementType Pop(Stack PtrS)
{if(PtrS -> Top == -1){printf("栈空");return ERROR;   /*ERROR 是 ElementType 的特殊值，标志错误*/}elsereturn (PtrS -> Data[ (PtrS -> Top)-- ];
}/*用一个数组实现两个堆栈，要求最大利用数组空间，使数组只要有空间入栈操作就可以成功*/
#define MaxSize
struct DStack
{ElementType Data[MaxSize];int Top1;   /*堆栈 1 的栈顶指针*/int Top2;   /*堆栈 2 的栈顶指针*/
}S;
S.Top1 = -1;
S.Top2 = MaxSize;void Push(struct DStack *PtrS, ElementType item, int Tag)
{   /*Tag作为区分两个堆栈的标志，取值为 1 和 2*/if(PtrS -> Top2 - PtrS -> Top1 == 1)printf("堆栈满");if(Tag == 1)    /*对第一个堆栈操作*/PtrS -> Data[++(PtrS -> Top1)] = item;else    /*对第二个堆栈操作*/Ptrs -> Data[--(PtrS -> Top2)] = item;
}ElementType Pop(struct DStack *PtrS, int Tag)
{if(Tag == 1){if(PtrS -> Top == -1){printf("堆栈1空");return NULL;}elsereturn PtrS -> Data[(PtrS -> Top1)--];}else{if(PtrS -> Top == MaxSize){printf("堆栈2空");return NULL;}elsereturn PtrS -> Data[(PtrS -> Top2)--];}
}

堆栈的链式存储实现

typedef struct SNode *Stack;
struct SNode{ElementType Data;struct SNode *Next;
};Stack CreateStack()
{   /*构建一个堆栈的头结点，返回指针*/Stack s;S = (Stack)malloc(sizeof(struct SNode));S -> Next = NULL;return S;
}int IsEmpty(Stack S)
{   /*判断栈顶 S 是否为空，若为空，函数返回 1，否则返回 0*/reuturn (S -> Next == NULL);
}void Push(ElementType item, Stack S)
{   /*将元素 item 压入堆栈 S*/struct SNode *TmpCell;TmpCell = (Struct SNode *)malloc(sizeof(struct SNode));TmpCell -> Data = item;TmpCell -> Next = S -> Next;S -> Next = TmpCell;
}ElementType Pop(Stack S)
{/*删除并返回堆栈 S 的栈顶元素*/struct SNode *FirstCell;ElemenType TopElem;if( IsEmpty(s) ){printf("堆栈空");return NULL;}else{FirstCell = S -> Next;S -> Next = FirstCell -> Next;TopElem = FirstCell -> Data;free(FirstCell);return TopElem;}
}

队列的顺序存储实现

#define MaxSize
struct QNode{ElemenType Data[MaxSize];int rear;int front;
};
typedef struct QNode *Queue;void AddQ(Queue PtrQ, ElemenType item)
{if((PtrQ -> rear + 1) % MaxSize == PtrQ -> front){printf("队列满");return；}PtrQ -> rear == (PtrQ -> rear + 1) % MaxSize;PtrQ -> Data[PtrQ -> rear] = item;
}ElemenType DeleteQ(Queue Q)
{if(PtrQ -> front == PtrQ -> rear){printf("队列空");return ERROR;}else{PtrQ -> front = (PtrQ -> front + 1) % MaxSize;return PtrQ -> Data[PtrQ -> front];}
}##队列的链式存储实现
struct Node{ElemenType Data;struct Node *Next;
};
struct QNode{   /*链队列结构*/struct Node *rear;struct Node *front;
};
typedef struct QNode *Queue;
Queue PtrQ;ElemenType DeleteQ(Queue PtrQ)
{struct Node *FrontCell;ElemenType FrontElem;if(PtrQ -> front == NULL){printf("队列空");return ERROR;}FrontCell = PtrQ -> front;if(PtrQ -> front == PtrQ -> rear)PtrQ -> front == PtrQ -> rear = NULL;elsePtrQ -> front == PtrQ -> front -> Next;FrontElem = FrontCell -> Data;free(FrontCell);return FrontElem;
}

图片：

应用实例：多项式加法

struct PolyNode{int coef;   // 系数int expon;  // 指数 struct PolyNode *link;  // 指向下一个结点的指针
};
typedef struct PolyNode *Polynomial;
Polynomial P1, P2;Polynomial PolyAdd(Polynomial P1, P2)
{Polynomial front, rear, temp;int  sum;rear = (Polynomial) malloc (sizeof(struct PolyNode));front = rear;   /*由 front 记录结果多项链表头结点*/while(P1 && P2) /*当两个多项式都有非零项待处理时*/{switch( Compare(P1 -> expon, P2 -> expon) ) // 系数比较{case 1:Attach(P1 -> coef, P1 -> expon, &rear);P1 = P1 -> link;break;case -1:Attach(P2 -> coef, P2 -> expon, &rear);P2 = P2 -> link;break;case 0:sum = P1 -> coef + P2 -> coef;if(sum)Attach(sum, P1 -> expon, &rear);P1 = P1 -> link;P2 = P2 -> link;break;}/*将未处理完的另一个多项式的所有结点依次复制到结果多项式中去*/for(;P1;P1 = P1 -> link)Attach(P1 -> coef, P1 -> expon, &rear);for(;P2;P2 = P2 -> link)Attcah(P2 -> coef, P2 -> expon, &rear);rear -> link = NULL;temp = front;front = front -> link;  /*令 front 指向结果多项式第一个非零项*/free(temp); /*释放临时空表头结点*/return front;}
}void Attach(int  c, int e, Polynomial *pRear)
{Polynomial P;P = (Polynomial)malloc(sizeof(struct PolyNode));P -> coef = c;P -> expon = e;P -> link = NULL;(*pRear) -> link = P;*pRear = P;
}###小白专场:设计函数求两个一元多项式的乘积与和
*3x^4 - 5x^2 + 6x - 2 与 5x^20 - 4x^4 - 5x^2 + 9x -2*typedef struct PolyNode *Polynomial;struct PolyNode{int coef;int expon;Polynomial link;};int main(){Polynomial P1,P2,PP,PS;P1 = ReadPoly();P2 = ReadPoly();PP = Mult(P1,P2);PrintPoly(PP);PS = Add(P1,P2);PrintPoly(PS);return 0;}Polynomial ReadPoly(){Polynomial P,Rear,t;int c,e,N;scanf("%d",&N);P = (Polynomial)malloc(sizeof(struct PolyNode));/*链表头空结点*/P -> link = NULL;Rear = P;while(N--){scanf("%d %d",&c, %e);Attach(c, e, &Rear);    /*将当前项插入多项式尾部*/}t = P;P = P -> link;free(t);    /*删除临时生成的头结点*/return P;}Polynomial Mult(Polynomial P1, Polynomial P2){Polynomial P,Rear,t1,t2,t;int c, e;if(!P1 || !P2)return NULL;t1 = P1;    /*P1、P2 为两个多项式*/t2 = P2;P = (Polynomial)malloc(sizeof(struct PolyNode));P -> link = NULL;Rear = P;while(t2){   /*先用 P1 的第一项乘 P2，得到 P*/Attach( t1->coef * t2->coef, t1->expon + t2->expon, &Rear);t2 = t2 -> link;}t1 = t1 -> link;while(t1){t2 = P2;Rear = P;while(t2){e = t1 -> expon + t2 -> expon;c = t1 -> coef * t2 -> coef;while(Rear->link && Rear->link->expon > e)Rear = Rear -> link;if(Rear->link && Rear->link->expon == e){if(Rear->link->coef + c)Rear->link->coef += c;else{t = Rear -> link;Rear -> link = t -> link;free(t);}}else{t = (Polynomial)malloc(sizeof(struct PolyNode));t -> coef = c;t -> expon = e;t -> link = Rear -> link;Rear -> link = t;Rear = Rear -> link;}}t1 = t1 -> link;}t2 = P;P = P -> link;free(t2);return P;}void PrintPoly(Polynomial P){int flag = 0;if(!P)printf("0 0n");while(P){if(!flag)flag = 1;elseprintf(" ");printf("%d %d", P->coef, P->expon);P = P -> link;}printf("n");}

树

静态查找

方法一：顺序查找

typedef struct LNode *List;
struct LNode{ElemenType Element[MAXSIZE];int Length;
};int SequentialSearch(List Tbl, ElemenType K)
{/*在 Element[1]~Element[n] 中查找关键字为 K 的数据元素 */int i;Tb1 -> Element[0] = K;  /*建立哨兵*/for(i = Tbl -> Length; Tbl -> Element[i] != K; i--);return i;   /*查找成功返回所在单元下标，不成功返回 0*/
}

方法二：二分查找

int BinarySearch(List Tbl, ElemenType K)
{   /*在表 Tbl 中查找关键字为 K 的数据元素*/int left, right, mid,NotFound = -1;left = 1;right = Tbl -> Length;while(left <= right){mid = (left + right)/2;if(K < Tbl -> Element[mid])right = mid - 1;else if(K > Tbl -> Element[mid])left = mid + 1;elsereturn mid;}return NotFound;
}

二叉树

完全二叉树：

typedef struct Tree *BinTree;
struct Tree
{ElenmenType Data;Tree Left;Tree Right;
};void PreOrderTraversal(BinTree BT)  /*先序遍历*/
{if(BT){printf("%d", BT -> Data);PreOrderTraversal(BT -> Left);PreOrderTraversal(BT -> Right);}
}void InOrderTraversal(BinTree BT)   /*中序遍历*/
{InOrderTraversal(BT -> Left);printf("%d", BT -> Data);InOrderTraversal(BT -> Right);
}void PostOrderTraversal(BinTree BT) /*后序遍历*/
{PostOrderTraversal(BT -> Left);PostOrderTraversal(BT -> Right);printf("%d", BT -> Data);
}

中序遍历非递归遍历算法

void InOrdertraversal(BinTree BT)
{BinTree T = BT;Stack S = CreatStack(MaxSize);  /*创建并初始化堆栈*/while(T || !IsEmpty(S)){while(T)    /*一直向左并将沿途结点压入堆栈*/{Push(S,T);T = T -> Left;}}if(!IsEmpty(S)){T = Pop(S); /*结点弹出堆栈*/printf("%d", T -> Data);T = T -> Right; /*转向右子对*/}
}

先序遍历非递归遍历算法

void InOrdertraversal(BinTree BT)
{BinTree T = BT;Stack S = CreatStack(MaxSize);  /*创建并初始化堆栈*/while(T || !IsEmpty(S)){while(T){printf("%d", T -> Data);Push(S,T);T = T -> Left;}}if(!IsEmpty(S)){T = Pop(S); /*结点弹出堆栈*/T = T -> Right; /*转向右子对*/}
}

后序遍历非递归算法

void PostOrderTraversal(BinTree BT) /*后序遍历*/
{BinTree T = BT;BinTree *current;BinTree *previous = NULL;Stack S = CreatStack(MaxSize);while(T || !IsEmpty(S)){current = Pop(S);if(current->Left==NULL && current->Right==NULL || (previous!=NULL && (prevoius==current->Left || previous->Right) )){printf("%d", current->Data);previous = currnet;}else{Push(S, current);if(current -> Left)Push(S, current->Right);if(currnet -> Right)Push(S, current->Left);}}
}

层序遍历

void LevelOrderTraversal(BinTree BT)
{Queue Q;BinTree T;Q = CreatQueue(MaxSize);AddQ(Q,BT);while(!IsEmpty(Q)){T = DeleteQ(Q;printf("%dn",T -> Data);   /*访问取出队列的结点*/if(T -> Left)AddQ(Q, T -> Left);if(T -> Right)AddQ(Q, T -> Right);}
}

遍历二叉树的应用

输出二叉树的叶子结点

void PreOrderPrintLeaves(BinTree BT)
{if(BT){if(!BT->Left && !BT->Right)printf("%d", BT -> Data);PreOrderPrintLeaves(BT -> Left);PreOrderPrintLeaves(BT -> Right);}
}

求二叉树的高度

int PostOrderGetHeight(BinTree BT)
{int HL, HR, MaxH;if(BT){HL = PostOrderGetHeight(BT -> Left);HR = PostOrderGetHeight(BT -> Right);MaxH = (HL > HR) ? HL:HR;return (MaxH + 1);}elsereturn 0;
}

二叉搜索树的查找操作 Find

Position Find(ElementType X, BinTree BST)
{if(!BST)return NULL;if(X > BST -> Data)return Find(X, BST -> Right);   /*在左子数中继续查找*/else if(X < BST -> Data)return Find(X, BST -> Left);    /*在左子数中继续查找*/elsereturn BST;
}Position IterFind(ElementType X, BinTree BST)
{while(BST){if(X > BST -> Data)BST = BST -> Right;   /*在左子数中继续查找*/else if(X < BST -> Data)BST = BST -> Left;    /*在左子数中继续查找*/elsereturn BST;}return NULL;
}

查找最大最小值

Position FindMin(BinTree BST)
{if(!BST)return NULL;else(!BST -> Left)return BST;elsereturn FindMin(BST -> Left);
}Position FindMax(BinTree BST)
{if(BST)while(BST -> Right)BST = BST -> Right;return BST;
}

插入

 BinTree Insert(ElementType X, BinTree BST){if(!BST){   /*若原树为空，生成并返回一个结点的二叉搜索树*/BST = malloc(sizeof(struct TreeNode));BST -> Data = X;BST -> Left = BST -> Right = NULL;}else{if(X < BST -> Data)BST -> Left = Insert(X, BST -> Left);else if(X > BST -> Right)BST -> Right = Insert(X, BST -> Right);}return BST;}

删除

BinTree Delete(ElementType X, BinTree BST)
{Position Tmp;if(!BST)printf("树空");else if(X < BSt -> Data)BST -> Left = Delete(X, BST -> Left);else if(X > BSt -> Data)BST -> Right = Delete(X, BST -> Right);else{if(BST -> Left && BSt -> Right) /*被删除结点有 2 个左右子结点*/{Tmp = FindMin(BST -> Right);/*在右子树中找最小的元素填充删除节点*/BST -> Data = Tmp -> Data;BST -> Right = Delete(BST -> Data, BST -> Right);/*在删除节点的右子树中删除最小元素*/}else    /*被删除结点有一个或无子节点*/{Tmp = BST;if(!BST -> Left)BST = BST -> Right;else if(!BST -> Right)BST = BST -> Left;free(Tmp);}}return BST;
}

小白专场：是否是同一个搜索树

搜索树的表示

typedef struct TreeNode *Tree;
struct TreeNode
{int v;  /*表示树的基本信息*/Tree Left, Right; int flag;   /*某个结点么被访问过 flag 置为 1，反之置为 0*/
}int main()
{int N, L, i;Tree T;scanf("%d", &N);while(N){scanf("%d",&L);T = MakeTree(N);for(i = 0; i < L; i++){if(Judge(T, N))printf("Yesn");elseprintf("Non");}FreeTree(T;scanf("%d", &N);}return 0;
}Tree NewNode(int V)
{Tree T = (Tree)malloc(sizeof(struct TreeNode));T -> v = V;T -> Left = T -> Right = NULL;T -> flag = 0;  /*为 0 表示该结点未曾被访问*/return T;
}Tree Insert(Tree T, int V)
{if(!T)T = NewNode(V;else{if(V > T -> v)T -> Right = Insert(T->Right, V);elseT -> Left = Insert(T->Left, V);}return T;
}Tree MakeTree(int N)
{Tree T;int i, V;scanf("%d", &V);T = NewNode(V);for(i = 1; i < N; i++){scanf("%d", &V);T = Insert(T, V);}return T;
}int check(Tree T, int V)    /*在树 T 中找数 V*/
{if(T -> flag)   /*如果该结点未被访问过*/{if(V < T->v)return check(T->Left, V);else if(V > T->v)return check(T->Right, V);elsereturn 0;}else{if(V == T->v){T->flag = 1;return 1;}elsereturn 0;}
}int Judge(Tree T, int N)
{int i, V, Flag = 0; /*这里的 Flag 是整个程序的标记*//*Flag 为 0 代表目前还一致，1 代表已经不一致*/scanf("%d", &V);if(V != T->v)Flag = 1;elseT -> flag = 1;for(i = 0; i < N; i++){scanf("%d", &V);if( (!Flag) && (!check(T, V)) ) /*刚刚发现不一致的结点*/Flag = 1;}if(Flag)return 0;elsereturn 1;
}void Reset(Tree T)  /*清除 T 中各结点的 flag 标记*/
{if(T -> Left)Reset(T -> Left);if(T -> Right)Reset(T -> Right);T -> flag = 0;
}void FreeTree(Tree T)   /*释放 T 的空间*/
{if(T -> Left)FreeTree(T -> Left);if(T -> Right)FreeTree(T -> Right);free(T);
}

堆

最大堆的创建

typedef struct HeapStruct *MaxHeap;
struct HeapStruct
{ElementType *Elements;  /*存储堆元素的数组*/int Size;   /*堆的当前元素个数*/int Capacity;   /*堆的最大容量*/
}；MaxHeap Create(int MaxSize)
{MaxHeap H = malloc(sizeof(struct HeapStruct));H -> Elements = malloc( (MaxSize+1) * sizeof(ElementType) );H -> Size = 0;H -> Capacity = MaxSize;H -> Elements[0] = MaxData;/*定义哨兵为大于堆中所有可能元素的值，便于以后操作*/return H;
}

将新增结点插入到从其父结点到根结点的有序序列中

void Insert(MaxHeap H, ElementType item)
{/*将元素 item 插入最大堆 H,其中 H -> Elements[0] 已经定义为哨兵*/int i;if( IsFull(H) ){printf("FULL");return;}i = ++H->Size;  /* i 指向插入后堆中的最后一个元素的位置*/for(; H->Elements[i/2] < item; i /= 2)  /*不断比较子结点与父结点的大小*/H->Elements[i] = H->Elements[i/2];H->Elements[i] = item;
}

删除最大堆的根结点

ElementType DeleteMax(MaxHeap H)
{/*从最大堆 H 中取出值最大的元素，并删除该结点*/int Parent, Child;ElementType MaxItem, temp;if( IsEmpty(H) ){printf("FULL);return;}MaxItem = H->Elements[1];   /*取出根结点最大值*/temp = H->Elements[H->Size--];  /*堆中的最后一个元素*/for(Parent=1; Parent*2 <= H->Size; Parent = Child){Child = Parent*2;  /*左儿子*/if( (Child != H->Size) && (H->Elements[Child] < H->Elements[Child+1]) )Child++;    /*右儿子*/if(temp >= H->Elements[Child])break;elseH->Elements[Parent] = H->Elements[Child];}H->Elements[Parent] = temp;    /*移动 temp 元素到下一层*/return MaxItem;
}

哈夫曼树与哈夫曼序列

typedef struct TreeNode *HuffmanTree;
struct TreeNode
{int Weight;HuffmanTree Left, Right;
}
HuffmanTree Huffman(MinHeap H)
{int i;HuffmanTree T;BuildMinHeap(H);    /*将 H->Elements[] 按权值调整为最小堆*/for(i = 1; i < H->Size; i++)    /*做 H->size-1 次合并*/{T = malloc(sizeof(struct TreeNode));T -> Left = DeleteMin(H);   /*从最小堆中删除一个结点，作为新 T 的左子结点*/T -> Right = DeleteMin(H);T->Weight = T->Left + T->Right;Insert(H,T);    /*将新 T 插入最小堆*/}T = DeleteMin(H;reutnr T;
}

采用数组存储集合

typedef struct
{ElementType Data;int Parent;
}SetType;

查找某个元素所在的集合（用根结点表示）

int Find(SetType S[], ElementType X)
{/*在数组 S 中查找值为 X 的元素所属的集合*//* MaxSize 是全局变量，为数组 S 的最大长度*/int i;/*先找到 X 在数组中的位置*/for(i = 0; i < MaxSize && S[i].Data != X; i++);if(i >= MaxSize)    /*未找到*/return -1;for( ; S[i].Parent >= 0; i = S[i].Parent);return i;   /*找到 X 所属集合，返回树根结点在数组 S 中的下标*/
}

集合的并运算

void Union(SetType S[], ElementType X1, ElementType X2)
{int root1, root2;root1 = Find(S, X1);root2 = Find(S, X2);if(root1 != root2)S[root2].Parent = root1;
}

图

用邻接矩阵表示图

typedef strcut GNode *PtrToGNode;
struct GNode
{int Nv; /* 顶点数 */int Ne; /* 边数 */WeightType G[MaxVertexNum][MaxVertexNum];DataType Data[MaxVertexNum];    /*存顶点的数据*/
};
typedef PtrToGNode MGraph;  /*以邻接矩阵存储的图类型*/

初始化一个有 VertexNum 个顶点但没有边的图

typedef int Vertex; /*用顶点下标表示顶点，为整型*/
MGraph CreateGraph(int VertexNum)
{Vertex V, W;MGraph Graph;Graph = (MGraph)malloc(sizeof(struct GNode));Graph -> Nv = VertexNum;Graph -> Ne = 0;/*这里默认顶点编号从 0 开始，到 Graph->Nv-1*/for(V = 0; V < Graph->Nv; V++)for(W = 0; W < Graph->Nv; W++)Graph->G[V][M] = 0;return Graph;
}

向 Graph 插入边

typedef struct ENode *PtrENode;
struct ENode
{Vertex V1, V2;  /*有向边 <V1, V2>*/WeightType Weight;  /*权重*/
};
typedef PtrENode Edge;void InsertEdge(MGraph Graph, Edge E)
{Graph->G[E->V1][E->V2] = E->Weight; /*插入边*/Graph->G[E->V2][E->V1] = E->Weight;
}

完整地建立一个 Graph

MGraph BulidGraph()
{MGraph Graph;Edge E;Vertex V;int Nv, i;scanf("%d", &Nv);Graph = CreateGraph(Nv);scanf("%d", &(Graph->Ne));if(Graph->Ne != 0){E = (Edge)malloc(sizeof(struct ENode));for(i = 0; i < Graph->Ne; i++){scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);InsertEdge(Graph, E);}}/*如果顶点有数据的话，读入数据*/for(V = 0; V < Graph->Nv; V++)scanf("%c", &(Graph->Data[V]));return Graph;
}