第三个一千行+500行总结-数据结构C复习--知识点总结3--七到九章
第七章 (接知識點總結2) 圖
圖的遍歷:
//深度優先搜索
#define OK 1
#define True ?1
#define Error -1
#define False 0
typedef enum{DG, DN, UDG. UDN}Graph;
int visited[MAX];
//Graph代表圖的一種存儲結構比如鄰接表,鄰接矩陣?
void TranverseGraph(Graph g){
?? ?int vi;
?? ?
?? ?for(vi = 0; vi < g.vernum; vi++)?
?? ??? ?visited[vi] = False;
?? ?for(vi = 0; vi < g.vernum; vi++){//連通圖那么此操作執行一次?
?? ??? ?if(!visited[vi])
?? ??? ??? ?DepthFirstSearch(g, vi);?? ?
?? ?}
}?
void DepthFirstSearch(Graph g, int v0)
{
?? ?visit(v0);
?? ?visited[v0] = True;
?? ?
?? ?w = FirstAdjVertex(g, v0);
?? ?while(w != -1){
?? ??? ?if(visited[w])
?? ??? ??? ?DepthFirstSearch(g, w);
?? ??? ?w = NextAdjVertex(g, v0, w);
?? ?}
}?
深度遍歷總結:總之就是一直找鄰接點,找到一個那么找這個結點的下一個鄰接點,找不到就換...
對于鄰接表:
void DepthFirstSearch(AdjList g, int v0){
?? ?visit(v0);
?? ?visited[v0] = True;//這里的True是宏定義,bool類型的為true
?? ?
?? ?ArcNode *p;
?? ?p = ?g.vertex[v0].firstarc;
?? ?while(p){
?? ??? ?if(!visited[p->adjvex])
?? ??? ??? ?DepthFirstSearch(g, p->adjvex);
?? ??? ?p = p->nextarc;
?? ?}
}?
圖的遍歷--廣度優先搜索?
void BreadFirstSearch(Graph g int v0){
?? ?visit(v0);
?? ?visited[v0] = True;//標志數組,證明該結點已經訪問過?
?? ?
?? ?InitQueue(&Q);
?? ?EnterQueue(&Q, v0);
?? ?
?? ?while(!IsEmpty(Q)){
?? ??? ?DeleteQueue(&Q, &v);
?? ??? ?w = FirstAdjVertex(g, v);
?? ??? ?while(w != -1){
?? ??? ??? ?if(!visited[w]){
?? ??? ??? ??? ?visit(w);
?? ??? ??? ??? ?visited[w] = True;
?? ??? ??? ??? ?EnterQueue(&Q, w);
?? ??? ??? ?}
?? ??? ??? ?w = NextAdjVertex(g, v, w);
?? ??? ?}
?? ?}
}?
廣度遍歷總結:就是一層一層的訪問,訪問完這一個結點衍生出去路徑為1的結點,在走下一層...
圖的應用
//求圖中兩個節點的簡單路徑
int pre[];
void one_path(Graph *G, int u, int v)
{
?? ?//找到一條從u到v結點的簡單路徑
?? ?int i;
?? ?pre = (int *)malloc(G->vexnum * sizeof(int));
?? ?for(i = 0; i < G->vernum; i++)
?? ??? ?pre[i] = -1;//未訪問標志?
?? ?pre[u] = -2;//訪問了,無前驅?
?? ?DSF_path(G, u, v);
?? ?free(pre);?
}
int DSF_path(Graph *G, int u, int v){
?? ?int j;
?? ?for(j = FirstAdj(G, u); j >= 0; j = nextadj(G, u, j)){
?? ??? ?if(pre[j] == -1){
?? ??? ??? ?pre[j] = u;
?? ??? ??? ?if(j == v)
?? ??? ??? ?{
?? ??? ??? ??? ?print_path(pre, v);
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?else if(DFS_path(G, j, v))
?? ??? ??? ??? ?return 1;?
?? ??? ?}?? ?
?? ?}
?? ?return 0;
}?
生成樹:一個連通圖的生成樹是一個極小聯通子圖, 含有全部頂點,只有構成一棵樹的n-1條邊
最小生成樹:各邊代價之和最小的生成樹
Prime算法:
思想:點集分為兩個U,V-U, 分別(U)存樹上的結點和(V-U)去掉U中結點的剩余結點;從V-U種選擇代價最小的邊
?? ?并入邊集,直到U=V.這一算法不會構成回路, 因為并入的邊始終是鄰接點分布在U和V-U中.
?? ??
//鄰接矩陣
#define MAXV ...
typedef struct{
?? ?int no;//頂點編號?
?? ?InfoType info;
}VertexType;
typedef struct{
?? ?int edges[MAXV][MAXV];//鄰接矩陣?
?? ?int n, e;//頂點數量, 邊數?
?? ?VertexType vexs[MAXV];//存放結點信息?
}MatGraph;?
#define M 32767
void Prime(MatGraph g, int v){
?? ?int lowcost[MAXV];
?? ?int min;
?? ?int closet[MAXV];
?? ?int i, j ,k;
?? ?for(i = 0; i < g.n; i++){
?? ??? ?lowcost[i] = g.edges[v][i];
?? ??? ?closet[i] = v;
?? ?}
?? ?for(i = 1; i < g.n; i++){
?? ??? ?min = M;
?? ??? ?for(j = 0; j < g.n; j++){
?? ??? ??? ?if(lowcost[j] != 0 && lowcost[j] < min){
?? ??? ??? ??? ?min = lowcost[j];
?? ??? ??? ??? ?k = j;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?printf("邊(%d, %d)權為: %d", v, k, lowcost[k]);
?? ??? ?lowcost[k] = 0;
?? ??? ?
?? ??? ?for(j = 0; j < g.n; j++){
?? ??? ??? ?if(lowcost[j] != 0 && lowcost[j] > g.edges[k][j])
?? ??? ??? ?{
?? ??? ??? ??? ?lowcost[j] = g.edges[k][j];
?? ??? ??? ??? ?closet[j] = k;
?? ??? ??? ?}
?? ??? ?}
?? ?}
}
Kruskal?
總結:對所有邊的權重值按照升序排列,依次選取權重較小的邊,
?? ? 確保不構成回路(選中的邊的所有結點不能重復出現在新加入的一條邊中) ?? ?
?? ??
#define 32367
typedef struct{
?? ?int u;
?? ?int v;
?? ?int w;
?? ?//邊的始點, 重點, 權重?
}Edge;
void Kruskal(MatGraph h){
?? ?
?? ?int i, j, u1, v1, sn1, sn2, k;
?? ?int vset[MAXV];
?? ?Edge E[MaxSize];
?? ?
?? ?k = 0;//指示數組E的下標
?? ?
?? ?//對于邊(權重)初始化?
?? ?for(i = 0; i < g.n; i++){
?? ??? ?for(j = i + 1; j < g.n; j++)//上三角?
?? ??? ??? ?if(g.edge[i][j] != M)//M = 32367
?? ??? ??? ?{
?? ??? ??? ??? ?E[k].u = i; E[k].v = j;
?? ??? ??? ??? ?E[k].w = g.edge[i][j]; k++;
?? ??? ??? ?}
?? ?}
?? ?//冒泡排序最簡單?
?? ?Sort(E, edge); //升序, 權值遞增?
?? ?
?? ?for(i = 0; i < g.n; i++)//初始化輔助數組?
?? ??? ?vset[i] = i;
?? ??? ?
?? ?k = 1;//k:當前構造生成樹的第幾條邊, 初始值為1
?? ?j = 0;//E中邊的下標
?? ?while(k < g.n){
?? ??? ?
?? ??? ?u1 = E[j].u;
?? ??? ?v1 = E[j].v;
?? ??? ?sn1 = vset[u1];
?? ??? ?sn2 = vset[u2];
?? ??? ?
?? ??? ?if(sn1 != sn2){
?? ??? ??? ?printf("(%d, %d): %d", u1, v1, E[j].w);
?? ??? ??? ?k++;
?? ??? ??? ?for(i = 0; i < g.n; i++){
?? ??? ??? ??? ?if(vset[i] == sn2)
?? ??? ??? ??? ??? ?vset[i] = sn1;//改結點相同, 表示這兩個結點已經形
?? ??? ??? ??? ??? ?//通路, 避免成環?
?? ??? ??? ?}
?? ??? ??? ?j++;?
?? ??? ?}?
?? ?}?
}
拓撲排序
原理: 對于鄰接矩陣
找入度為零的結點i, 即列為零的結點,標記, 將其刪除, 刪除鄰接邊即將序號i的行置零 , 重復...
鄰接表
加一個輔助數組記錄每個結點的入度; 入度為0, 入棧;?
棧非空, 出棧, 刪除鄰接邊;
即輔助數組鄰接點的總數count-1;?
//鄰接表定義如下
typedef struct ANode{
?? ?int adjvex; // 該邊的終點編號?
?? ?struct Anode *nextarc;
}ArcNode;?
typedef struct{
?? ?Vertex data;
?? ?int count;//輔助數組, 存放入度?
?? ?ArcNode *firstarc;
}VNode;
typedef struct{
?? ?VNode adjlist[MAV];
?? ?int n, e;
}AdjGraph;
拓撲排序
//基于鄰接表?
void TopSort(AdjGraph *G){
??? ?int i, j;
??? ?int st[MAXV], ?top = -1;//棧的指針
?? ?ArcNode *p;
?? ?
?? ?for(i = 0; i < G->n;i++){//入度置初值為0?
?? ??? ?G->adjlist[i].count = 0;
?? ?}?
?? ?for(i = 0; i < G->n; i++){//求所有頂點的入度?
?? ??? ?p = G->adjlist[i].firstarc;
?? ??? ?while(p!=NULL){
?? ??? ??? ?G->adjlist[p->adjvex].count++;
?? ??? ??? ?p = p->nextarc;//鄰接表?
?? ??? ?}
?? ?}
?? ?for(i = 0; i < G.n; i++){//入度為零進棧?
?? ??? ?if(G->adjlist[i].count == 0){
?? ??? ??? ?top++;
?? ??? ??? ?st[top] = i;
?? ??? ?}
?? ?}
?? ?
?? ?while(top != -2){
?? ??? ?
?? ??? ?i = st[top]; top--;//出棧一個頂點i?
?? ??? ?printf("%d", i);
?? ??? ?
?? ??? ?p = G->adjlist[i].firstarc;
?? ??? ?while(p != NULL){
?? ??? ??? ?j = p->adjvex;//找出p的鄰接點,入度-1?
?? ??? ??? ?G->adjlist[j].count--;
?? ??? ??? ?if(G->adjlist[j].count == 0){//入度為0入棧?
?? ??? ??? ??? ?top++;
?? ??? ??? ??? ?st[top] = j;
?? ??? ??? ?}
?? ??? ??? ?p = p->nextarc;
?? ??? ?}
?? ??? ?
?? ?}
?}
?
AOE網--邊表示活動的網
唯一入度為0的頂點為源點,唯一出度為0的頂點為匯點
源點到匯點的最長路徑長度為整個工程任務所需時間,稱為關鍵路徑
關鍵路徑上的活動稱為關鍵活動.
//迪杰斯特算法 看PPT,難度較大?
void Dijkstra(MatGraph g, int v){ // v is the original dot.
?? ?int dist[MAXV], path[MAXV]; ? //dist is to memorize the weighted length of the path.
?? ?//path is used to memorize the node of the path
?? ?int s[MAXV]; //to mark the node whether have been used.
?? ?int mindist, i, j;
?? ?
?? ?for(i = 0; i < g.n; i++){
?? ??? ?dist[i] = g.edges[v][i]; //Firstly store the weighted length of the related edge.
?? ??? ?//If it is not relevant to it, put infinite on it. If it is itself, put 0 on it
?? ??? ?s[i] = 0;//s[] is cleared.
?? ??? ?if(g.edge[v][i] < INF)//如果v和i鄰接那么賦值i的鄰接點為v?
?? ??? ??? ?path[i] = v;
?? ??? ?else
?? ??? ??? ?path[i] = -1;//path is used to memorize the node before the latest
?? ??? ?//if it is -1, proven there is no path.
?? ?s[v] =1;?
?? ?for(i = 0; i < g.n; i++){//找出路徑長度最小頂點u?
?? ??? ?mindis = INF;
?? ??? ?for(j = 0; j < g.n; j++)//Find out the shortest length of the node.
?? ??? ??? ?if(s[j] == 0 && dist[j] < mindis){
?? ??? ??? ??? ?u = j;
?? ??? ??? ??? ?mindis = dist[j];
?? ??? ??? ?}
?? ??? ?s[u] = 1;//node u is added into s//u has been used
?? ??? ?for(j = 0; j < g.n; j++)
?? ??? ??? ?if(s[j] == 0)//s[j]is not used
?? ??? ??? ??? ?if(g.edge[u][j]<INF && dist[u]+g.edge[u][j]<dist[j]){
?? ??? ??? ??? ??? ?dist[j] = dist[u]+g.edges[u][j];
?? ??? ??? ??? ??? ?path[j] = u;?
?? ??? ??? ??? ?}
?? ?}?? ?
?? ?}
?? ?Dispath(dist, path, s, g.n, v);//printf
} ?
對于多源點最短路徑問題
//佛洛里得算法 難度大,看ppt?
void Floyd(MatGraph g){
?? ?int A[MAXVEX][MAXVEX];//記錄路徑長度
?? ?int path[MAXVEX][MAXVEX];//記錄路徑?
?? ?int i, j, k;
?? ?for(i = 0; i < g.n; i++)
?? ??? ?for(j = 0; j < g.n; j++){
?? ??? ??? ?A[i][j] = g.edges[i][j];
?? ??? ??? ?if(i!= j && g.edges[i][j] < INF)
?? ??? ??? ??? ?path[i][j] = i;
?? ??? ??? ?else
?? ??? ??? ??? ?path[i][j] = -1;//自環或者不存在鄰接邊?
?? ??? ?}?
?? ?for(k = 0; k < g.n; k++){//O(n^3)
?? ??? ?for(i = 0; i < g.n; i++)
?? ??? ??? ?for(j = 0; j < g.n; j++)
?? ??? ??? ??? ?if(A[i][j] > A[i][k]+A[k][i]){
?? ??? ??? ??? ?//i, j 之間有兩種形式, i直接到j;
?? ??? ??? ??? ?//或者i經過k到達j?
?? ??? ??? ??? ??? ?A[i][j] = A[i][k]+A[k][i];
?? ??? ??? ??? ??? ?path[i][j] = path[k][j];
?? ??? ??? ??? ??? ?//修改最短路徑經過k?
?? ??? ??? ??? ?}
?? ?}
}?
第七章總結:圖是最復雜的線性表.分類很多根據弧的有向與否,連通性,邊數量,權....
儲存分為邊集合(鄰接矩陣), 鏈接的方式(鄰接表,十字鏈表,鄰接多重表)
圖的遍歷分為深度遍歷和廣度優先遍歷,前者遞歸,后者隊列!!!
應用!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1?
第八章 查找
概念:列表(python,就相當于數組),主關鍵詞,次關鍵字
查找:分為動態和靜態查找 前者僅僅是查找, 后者插入找不到的元素或者刪除已經查到的元素
?
基于線性表的查找
// 1.順序查找法
//思想:所給的關鍵字和表中元素的關鍵字逐個比較
定義如下:
#define SIZE 20
typedef struct{
?? ?int key;
?? ?int other_data;
}RecordType;?
typedef struct{
?? ?RecordType r[SIZE];//r[0]為工作單元?
?? ?int length;
}RecordList;
分為:設置監視哨和不設監視哨
監視哨:r[0]防止越界
int SeqSearch(RecordList ?l, ?KeyType ?k)
//在順序表l中順序查找其關鍵字等于k的元素，若找到，則函數值為該元素在表中的位置，否則為0
{
?? ?int i;
?? ?l.r[0].key=k;?
?? ?i=l.length;
?? ?while (l.r[i].key!=k) ?i--;
?? ?return(i);
}
int SeqSearch(RecordList l, ?KeyType k)
//不用"監視哨"法，在順序表中查找關鍵字等于k的元素
{
?? ?int i;
?? ?i=l.length;
?? ?while (i>=1&&l.r[i].key!=k) ?i--;
?? ?if (i>=1)?
?? ??? ?return(i);
?? ?else
?? ??? ?return (0);
}
//2.折半查找法
要求:順序儲存結構(不能鏈表!!!),按照關鍵字大小有序排列(正序和逆序)
思想:利用mid=(high+low)/2(整數). 判斷條件:low<=high;
int BinSrch(RecordList ?l, ?KeyType ?k)
/*在有序表l中折半查找其關鍵字等于k的元素，若找到，則函數值為該元素在表中的
位置*/
{
?? ?int low,high,mid;
?? ?low=1; ?
?? ?high=l.length;/*置區間初值*/
?? ?while( low <= high)
?? ?{
?? ??? ?mid=(low+high) / 2;
?? ??? ?if ?(k==l.r[mid]. key) ?
?? ??? ??? ?return (mid);/*找到待查元素*/
?? ??? ?else ?
?? ??? ??? ?if (k<l.r[mid]. key)?
?? ??? ??? ??? ?high=mid-1;/*未找到，則繼續在前半區間進行查找*/
?? ??? ??? ?else ?
?? ??? ??? ??? ?low=mid+1;/*繼續在后半區間進行查找*/
?? ?}
?? ?return (0);
}
//3.分塊查找法
要求:列表分為子表,最后一個子表長度可以不滿;索引表每個索引對應每個塊(子表)的起始位置,記錄每個塊的最大(最小)
的關鍵字;索引表按照關鍵字有序排列
基于樹的查找法
二叉排序樹定義:元素大小關系:左子樹<根<右子樹,遞歸定義
結構定義:
typedef struct node{
?? ?int key;
?? ?struct node *lchild, *rchild;
}BSTNode, *BSTree;
?
插入:?
遞歸算法?
void InsertBST(BSTree *bst, KeyType key)
/*若在二叉排序樹中不存在關鍵字等于key的元素，插入該元素*/
{?
?? ?BSTree s;
?? ?if (*bst == NULL)/*遞歸結束條件*/
?? ?{
?? ??? ?s=(BSTree)malloc(sizeof(BSTNode));/*申請新的結點s*/
?? ??? ?s-> key=key;
?? ??? ?s->lchild=NULL;?
?? ??? ?s->rchild=NULL;
?? ??? ?*bst=s;
?? ?}
?? ?else?
?? ??? ?if (key < (*bst)->key)
?? ??? ??? ?InsertBST(&((*bst)->lchild), key);/*將s插入左子樹*/
?? ??? ?else?
?? ??? ??? ?if (key > (*bst)->key)
?? ??? ??? ??? ?InsertBST(&((*bst)->rchild), key); /*將s插入右子樹*/
}
非遞歸: !!!!!!!!!!!!!!!
int ?InsertBST(BSTree ?*bst, ?KeyType ?K)
/*若在二叉排序樹中不存在關鍵字等于key的元素，插入該元素*/
{
?? ?BSTree ?f, q, s;
?? ?s=(BSTree)malloc(sizeof(BSTNode));
?? ?s->key = K;
?? ?s->lchild = NULL;
?? ?s->rchild = NULL;
?? ?
?? ?//空樹直接賦值?
?? ?if ( *bst == NULL )?
?? ?{?
?? ??? ?*bst = s;?
?? ??? ?return ?1;?
?? ?}
?? ?//指針跟蹤技術?
?? ?f = NULL;
?? ?q = *bst;
?? ?while( q )
?? ?{?
?? ??? ?if ( q->key == K )?
?? ??? ??? ?return ?0;
?? ??? ?if( K < q->key ) //小于走左邊?
?? ??? ?{?
?? ??? ??? ?f = q;?
?? ??? ??? ?q = q->lchild;?
?? ??? ?}
?? ??? ?else?
?? ??? ?{ ?
?? ??? ??? ?f = q;?
?? ??? ??? ?q = q->rchild;?
?? ??? ?}
?? ?}//走到頭仍然沒找到就插入?
?? ?if ( K < f->key )?
?? ??? ?f->lchild = s;?
?? ?else ?
?? ??? ?f->rchild = s;
?? ?return ?1; ?
}
創建二叉排序樹:
void ?CreateBST(BSTree ?*bst)
/*從鍵盤輸入元素的值，創建相應的二叉排序樹*/
{?
?? ?KeyType key;
?? ?*bst=NULL;
?? ?scanf("%d", &key);
?? ?while (key!=ENDKEY) ? /*ENDKEY為自定義常量*/
?? ?{
?? ??? ?InsertBST(bst, key);
?? ??? ?scanf("%d", &key);
?? ?}
}?
查找:?
遞歸算法?
BSTree ?SearchBST(BSTree bst, KeyType key)
//在根指針bst所指二叉排序樹中，遞歸查找某關鍵字等于key的元素，若查找成功，返回指向該元素結點指針，否則返回空指針
{?
?? ?if (!bst)?
?? ??? ?return NULL;
?? ?else if (bst->key == key)
?? ??? ?return bst;//查找成功
?? ?else if (bst->key > key)
?? ??? ?return SearchBST(bst->lchild, key);//在左子樹繼續查找
?? ?else?
?? ??? ?return SearchBST(bst->rchild, key);//在右子樹繼續查找
}
二叉排序樹的刪除略顯復雜:
1.不存在,不動
2.存在
2.1.葉子節點:直接刪,free掉
2.2只有左右子樹一支:孩子改到刪去位置(孩子變為雙親),free
2.3.左右孩子都有:
2.3.1處理1:
?? ?利用中序遍歷算法找到將要刪除結點p的直接前驅s,p左子樹變為其雙親的左孩子,右子樹變為其前驅s的右孩子?
2.3.2處理2:?
?? ?直接刪除結點p,p的前驅s代替p,free(s),s的左孩子為s的雙親的右孩子,p的右孩子為s的右孩子
!!!
BSTNode ?* DelBST(BSTree t, KeyType ?k) /*在二叉排序樹t中刪去關鍵字為k的結點*/
{
?? ?BSTNode ?*p, *f,*s ,*q;
?? ?p=t;?
?? ?f=NULL;
?? ?while(p) ?/*查找關鍵字為k的待刪結點p*/
?? ?{?
?? ??? ?if(p->key==k ) ?break; ?/*找到則跳出循環*/
?? ??? ?f=p; ? /*f指向p結點的雙親結點*/
?? ??? ?if(p->key>k) ?
?? ??? ??? ?p=p->lchild;
?? ??? ?else?
?? ??? ??? ?p=p->rchild;
?? ?}?
?? ?if(p==NULL) ?return t; ?/*若找不到，返回原來的二叉排序樹*/
?? ?if(p->lchild==NULL) ?/*p無左子樹*/
?? ?{?
?? ??? ?if(f==NULL)?
?? ??? ??? ?t=p->rchild; ?/*p是原二叉排序樹的根*/
?? ??? ?else?
?? ??? ??? ?if(f->lchild==p) ?/*p是f的左孩子*/
?? ??? ??? ??? ?f->lchild=p->rchild ; ?/*將p的右子樹鏈到f的左鏈上*/
?? ??? ??? ?else ?/*p是f的右孩子*/
?? ??? ??? ??? ?f->rchild=p->rchild ; ?/*將p的右子樹鏈到f的右鏈上*/
?? ??? ??? ?free(p); ?/*釋放被刪除的結點p*/
?? ?}
?? ?else ?/*p有左子樹*/
?? ?{?
?? ??? ?q=p;?
?? ??? ?s=p->lchild;
?? ??? ?while(s->rchild) ?/*在p的左子樹中查找最右下結點*/
?? ??? ?{
?? ??? ??? ?q=s;?
?? ??? ??? ?s=s->rchild;
?? ??? ?}
?? ??? ?if(q==p)?
?? ??? ??? ?q->lchild=s->lchild ; ?/*將s的左子樹鏈到q上*/
?? ??? ?else?
?? ??? ??? ?q->rchild=s->lchild;
?? ??? ?p->key=s->key; ?/*將s的值賦給p*/
?? ??? ?free(s);
?? ?}
?? ?return t;
} ?
?? ?
平衡二叉排序樹:左子樹右子樹高度絕對值之差小于等于1
插入算法:LL,RR,LR,RL型
結構定義中含平衡因子代碼如下:
?? ?
void ?ins_AVLtree(AVLTree ?*avlt , ?KeyType ?K)
/*在平衡二叉樹中插入元素k，使之成為一棵新的平衡二叉排序樹*/
{
?? ?AVLTNode *S;
?? ?AVLTNode *A,*FA,*p,*fp,*B,*C;
?? ?S=(AVLTree)malloc(sizeof(AVLTNode));
?? ?S->key=K;?
?? ?S->lchild=S->rchild=NULL;
?? ?S->bf=0;
?? ?if (*avlt==NULL) ?
?? ??? ?*avlt=S;
?? ?else?
?? ?{?
?? ?/* 首先查找S的插入位置fp，同時記錄距S的插入位置最近且
?? ??? ?平衡因子不等于0（等于-1或1）的結點A，A為可能的失衡結點*/
?? ??? ?A=*avlt; ?FA=NULL;
?? ??? ?p=*avlt; ?fp=NULL;
?? ??? ?while ?(p!=NULL)
?? ??? ?{?
?? ??? ??? ?if (p->bf!=0)?
?? ??? ??? ?{
?? ??? ??? ??? ?A=p; FA =fp;
?? ??? ??? ?}
?? ??? ??? ?fp=p;
?? ??? ??? ?if ?(K < p->key) ?
?? ??? ??? ??? ?p=p->lchild;
?? ??? ??? ?else ?
?? ??? ??? ??? ?p=p->rchild;
?? ??? ?}
?? ??? ?/* 插入S*/
?? ??? ?if (K < fp->key)?
?? ??? ??? ?fp->lchild=S;
?? ??? ?else
?? ??? ??? ?fp->rchild=S;
?? ??? ?/* 確定結點B，并修改A的平衡因子 */
?? ??? ?if (K < A->key)
?? ??? ?{
?? ??? ??? ?B=A->lchild;
?? ??? ??? ?A->bf=A->bf+1;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?B=A->rchild;
?? ??? ??? ?A->bf=A->bf-1;
?? ??? ?}
?? ??? ?/* 修改B到S路徑上各結點的平衡因子（原值均為0）*/
?? ??? ?p=B;
?? ??? ?while (p!=S)
?? ??? ?{
?? ??? ??? ?if ?(K < p->key)
?? ??? ??? ?{
?? ??? ??? ??? ?p->bf=1;
?? ??? ??? ??? ?p=p->lchild;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?p->bf=-1;
?? ??? ??? ??? ?p=p->rchild;
?? ??? ??? ?}
?? ??? ??? ?/* 判斷失衡類型并做相應處理 */
?? ??? ??? ?if ?(A->bf==2 && B->bf==1) ? ? ? /* LL型 */
?? ??? ??? ?{
?? ??? ??? ??? ?B=A->lchild;
?? ??? ??? ??? ?A->lchild=B->rchild;
?? ??? ??? ??? ?B->rchild=A;
?? ??? ??? ??? ?A->bf=0;
?? ??? ??? ??? ?B->bf=0;
?? ??? ??? ??? ?if (FA==NULL)?
?? ??? ??? ??? ??? ?*avlt=B;
?? ??? ??? ??? ?else?
?? ??? ??? ??? ??? ?if (A==FA->lchild)?
?? ??? ??? ??? ??? ??? ?FA->lchild=B;
?? ??? ??? ??? ??? ?else?
?? ??? ??? ??? ??? ??? ?FA->rchild=B;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ??? ?if (A->bf==2 && B->bf==-1) ? ? ? /* LR型 */
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?B=A->lchild;
?? ??? ??? ??? ??? ?C=B->rchild;
?? ??? ??? ??? ??? ?B->rchild=C->lchild;
?? ??? ??? ??? ??? ?A->lchild=C->rchild;
?? ??? ??? ??? ??? ?C->lchild=B;
?? ??? ??? ??? ??? ?C->rchild=A;
?? ??? ??? ??? ??? ?if (S->key < C->key)
?? ??? ??? ??? ??? ?{?
?? ??? ??? ??? ??? ??? ?A->bf=-1;
?? ??? ??? ??? ??? ??? ?B->bf=0;
?? ??? ??? ??? ??? ??? ?C->bf=0;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?else?
?? ??? ??? ??? ??? ??? ?if (S->key >C->key)
?? ??? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ??? ?A->bf=0;
?? ??? ??? ??? ??? ??? ??? ?B->bf=1;
?? ??? ??? ??? ??? ??? ??? ?C->bf=0;
?? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ??? ?else
?? ??? ??? ??? ??? ??? ?{?
?? ??? ??? ??? ??? ??? ??? ?A->bf=0;
?? ??? ??? ??? ??? ??? ??? ?B->bf=0;
?? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ??? ?if ?(FA==NULL)?
?? ??? ??? ??? ??? ??? ??? ?*avlt=C;
?? ??? ??? ??? ??? ??? ?else?
?? ??? ??? ??? ??? ??? ??? ?if (A==FA->lchild)?
?? ??? ??? ??? ??? ??? ??? ??? ?FA->lchild=C;
?? ??? ??? ??? ??? ??? ??? ?else?
?? ??? ??? ??? ??? ??? ??? ??? ?FA->rchild=C;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else?
?? ??? ??? ??? ??? ?if ?(A->bf==-2 && B->bf==1) ? ? ? /* RL型 */
?? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ?B=A->rchild;
?? ??? ??? ??? ??? ??? ?C=B->lchild;
?? ??? ??? ??? ??? ??? ?B->lchild=C->rchild;
?? ??? ??? ??? ??? ??? ?A->rchild=C->lchild;
?? ??? ??? ??? ??? ??? ?C->lchild=A;
?? ??? ??? ??? ??? ??? ?C->rchild=B;
?? ??? ??? ??? ??? ??? ?if (S->key <C->key)?
?? ??? ??? ??? ??? ??? ?{?
?? ??? ??? ??? ??? ??? ??? ?A->bf=0;
?? ??? ??? ??? ??? ??? ??? ?B->bf=-1;
?? ??? ??? ??? ??? ??? ??? ?C->bf=0;
?? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ??? ?else?
?? ??? ??? ??? ??? ??? ??? ?if (S->key >C->key)
?? ??? ??? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ??? ??? ?A->bf=1;
?? ??? ??? ??? ??? ??? ??? ??? ?B->bf=0;
?? ??? ??? ??? ??? ??? ??? ??? ?C->bf=0;
?? ??? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ??? ??? ?else?
?? ??? ??? ??? ??? ??? ??? ?{?
?? ??? ??? ??? ??? ??? ??? ??? ?A->bf=0;
?? ??? ??? ??? ??? ??? ??? ??? ?B->bf=0;
?? ??? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ??? ??? ?if (FA==NULL) ?
?? ??? ??? ??? ??? ??? ??? ??? ?*avlt=C;
?? ??? ??? ??? ??? ??? ??? ?else
?? ??? ??? ??? ??? ??? ??? ??? ?if (A==FA->lchild)?
?? ??? ??? ??? ??? ??? ??? ??? ??? ?FA->lchild=C;
?? ??? ??? ??? ??? ??? ??? ??? ?else ?
?? ??? ??? ??? ??? ??? ??? ??? ??? ?FA->rchild=C;
?? ??? ??? ??? ??? ?}
?? ??? ??? ??? ??? ?else?
?? ??? ??? ??? ??? ??? ?if (A->bf==-2 && B->bf==-1) ? ? ? /* RR型 */
?? ??? ??? ??? ??? ??? ?{
?? ??? ??? ??? ??? ??? ??? ?B=A->rchild;
?? ??? ??? ??? ??? ??? ??? ?A->rchild=B->lchild;
?? ??? ??? ??? ??? ??? ??? ?B->lchild=A;
?? ??? ??? ??? ??? ??? ??? ?A->bf=0;
?? ??? ??? ??? ??? ??? ??? ?B->bf=0;
?? ??? ??? ??? ??? ??? ??? ?if (FA==NULL)?
?? ??? ??? ??? ??? ??? ??? ??? ?*avlt=B;
?? ??? ??? ??? ??? ??? ??? ?else
?? ??? ??? ??? ??? ??? ??? ??? ?if (A==FA->lchild)
?? ??? ??? ??? ??? ??? ??? ??? ??? ?FA->lchild=B;
?? ??? ??? ??? ??? ??? ??? ??? ?else?
?? ??? ??? ??? ??? ??? ??? ??? ??? ?FA->rchild=B;
?? ??? ??? ??? ??? ??? ?}
?? ??? ??? ??? ?}
?? ??? ?}
}?
icoding例題:
?? ?
AVL添加
平衡二叉樹，是一種二叉排序樹，其中每個結點的左子樹和右子樹的高度差至多等于1。
它是一種高度平衡的二叉排序樹?，F二叉平衡樹結點定義如下：
typedef struct node
{
? ? int val;
? ? struct node *left;
? ? struct node *right;
? ? struct node *parent;
? ? int height;
} node_t;
//請實現平衡二叉樹的插入算法：
//向根為 root 的平衡二叉樹插入新元素 val，成功后返回新平衡二叉樹根結點
node_t *avl_insert(node_t *root, int val);
#include <stdlib.h>
#include <stdio.h>
#include "avl.h"
int get_height(node_t *p){
?? ?if(!p)
?? ??? ?return 0;
?? ?else
?? ??? ?return p->height;
}
node_t* avl_insert(node_t *root, int val){
//首先清晰字母定義;
//val新插入結點元素值,height高度!!!?
//定義查找過程中出現的距離插入結點最近的平衡因子不為零的結點A
//定義A的孩子結點為B,需要旋轉的結點
//定義插入節點為s,s的值為val
//平衡因子:左子樹減去右子樹深度?
?? ?node_t *s, *A, *B, *C, *p, *fp;
?? ?//依次:插入點, 失衡點(也可能是旋轉點),旋轉點,旋轉點(也可能是插入點=s),動點,跟蹤點
?? ?int i, k;//平衡因子?
?? ?
?? ?s = (node_t *)malloc(sizeof(node_t));
?? ?if(!s) return NULL;
?? ?
?? ?s->val = val;
?? ?s->left = s->parent = s->right = NULL;
?? ?s->height = 1;
?? ?
?? ?//類似于指針跟蹤技術,p為動指針,A為跟蹤指針?
?? ?A = root; A->parent = NULL;
?? ?p = root; p->parent = NULL;
?? ?
?? ?//找出A?
?? ?if(!p)
?? ??? ?root = s;
?? ?else{
?? ??? ?while(p){
?? ??? ??? ?//先找出最近的A->height!=0的結點, 就是最后的失衡點
?? ??? ??? ?i = get_height(p->left) - get_height(p->right);?
?? ??? ??? ?if(i){
?? ??? ??? ??? ?A = p;
?? ??? ??? ??? ?A->parent = p->parent;
?? ??? ??? ?}
?? ??? ??? ?//fp跟蹤p,因為下一步p會往下移動,p最終指向s的那一層?
?? ??? ??? ?fp = p;
?? ??? ??? ?if(val < p->val)
?? ??? ??? ??? ?p = p->left;
?? ??? ??? ?else
?? ??? ??? ??? ?p = p->right;
?? ??? ??? ?}//p最終指向NULL就推出循環?? ??
?? ?}?
?? ?
?? ?//插入, 此時fp是p的前一個結點,p指向空?
?? ?if(val < fp->val)
?? ??? ?fp->left = s;
?? ?else
?? ??? ?fp->right = s;
?? ??? ?
?? ?//確定旋轉結點B,修改A的平衡因子
?? ?if(val < A->val)
?? ??? ?B = A->left;
?? ?else
?? ??? ?B = A->right;
?? ?A->height++;
?? ?
?? ?//修改路徑B到s的高度, B在A的下一層?
?? ?p = B; // p最終指向s, 之前指向的是s這一層,但是是空
?? ?while(p != s){
?? ??? ?p->height++;
?? ??? ?if(val < p->val)
?? ??? ??? ?p = p->left;?
?? ??? ?else
?? ??? ??? ?p = p->right;?? ?
?? ?}
?? ?//最終s的高度沒有++的?
?? ??? ?
?? ?
?? ?//調整完高度就修改結點和指針, 首先需要判斷失衡類型
?? ?//分為LL,LR,RR,RL
?? ?//結點A,B平衡因子在修改指針的過程中會變化,但是路徑上的結點不會
?? ?//指針修改包括s結點指針和原來雙親結點指針?
?? ?i = get_height(A->left) - get_height(A->right);
?? ?k = get_height(B->left) - get_height(B->right);?
?? ?
?? ?if(i == 2 && k == 1){//LL
?? ??? ?//B作為旋轉結點
?? ??? ?//先改結點指針, 此時s插入在B的左子樹下, 原來可以認為B左右子樹,A右子樹均為空
?? ??? ?A->left = B->right;
?? ??? ?B->right = A;
?? ??? ?
?? ??? ?//考慮原來A結點的指針,改成B后相應的指針也要改變,下面同理
?? ??? ?if(A->parent == NULL)
?? ??? ??? ?root = B;
?? ??? ?else if(A->parent->left == A)
?? ??? ??? ?A->parent->left = B;
?? ??? ?else
?? ??? ??? ?A->parent->right = B;?? ??? ?
?? ?}
?? ?else if(i == -2 && k == -1){//RR
?? ??? ?A->right = B->left;
?? ??? ?B->left = A;
?? ??? ?
?? ??? ?if(A->parent == NULL)
?? ??? ??? ?root = B;
?? ??? ?else if(A->parent->left == A)
?? ??? ??? ?A->parent->left = B;
?? ??? ?else
?? ??? ??? ?A->parent->right = B;?? ?
?? ?}
?? ?else if(i == 2 && k == -1){//LR
?? ??? ?//此時認為C的左右子樹空,B逆時針旋轉,A順時針旋轉, s插入C的左子樹或者右子樹?
?? ??? ?//如果C結點也是空,也就是說B右子樹空,那么直接插入C=s為B右子樹,此時A右子樹也是空的?
?? ??? ?C = B->right;
?? ??? ?B->right = C->left;
?? ??? ?A->left = C->right;
?? ??? ?C->left = B;
?? ??? ?C->right = A;
?? ??? ?
?? ??? ?if(A->parent == NULL)
?? ??? ??? ?root = C;
?? ??? ?else if(A->parent->left == A)
?? ??? ??? ?A->parent->left = C;
?? ??? ?else
?? ??? ??? ?A->parent->right = C;
?? ?}
?? ?else if(i == -2 && k == 1){//RL?
?? ??? ?//和LR一樣,畫圖來看就好
?? ??? ?C = B->left;
?? ??? ?A->right = C->left;
?? ??? ?B->left = C->right;
?? ??? ?C->left = A;
?? ??? ?C->right = B;
?? ??? ?
?? ??? ?if(A->parent == NULL)
?? ??? ??? ?root = C;
?? ??? ?else if(A->parent->left == A)
?? ??? ??? ?A->parent->left = C;
?? ??? ?else
?? ??? ??? ?A->parent->right = C;
?? ?}
?? ?return root;
}?
計算式查找法:hash(python的字典就是這么存的)
//hash:
1.數字分析法:選擇合適位數的分布均勻的關鍵字?
2.平方取中法:求關鍵字平方值,取中間,重復概率低?
3.分段疊加法:折疊法,移位法
4.除留余數法:取余除數為小于等于表長的最大素數?
5.偽隨機數法:電腦生成偽隨機數?
?? ?
處理沖突!!!!:
1.開放地址法(再散列法):
1.1.線性探測再散列:di = 1,2,3......
1.2.二次探測再散列:di = 1^2, -1^2, 2^2, -2^2,......?
1.3.偽隨機探測再散列: ...
2.再哈希法
3.鏈地址法:!!!
4.建立公共溢出區:分為基本表和溢出表
icoding:
?? ?
哈希表創建
typedef enum{
? ? HASH_OK,
? ? HASH_ERROR,
? ? HASH_ADDED,
? ? HASH_REPLACED_VALUE,
? ? HASH_ALREADY_ADDED,
? ? HASH_DELETED,
? ? HASH_NOT_FOUND,
} HASH_RESULT;
typedef struct __HashEntry HashEntry;
struct __HashEntry{
? ? union{
? ? ? ? char ?*str_value;
? ? ? ? double dbl_value;
? ? ? ? int ? ? ? int_value;
? ? } key;
? ? union{
? ? ? ? char ?*str_value;
? ? ? ? double dbl_value;
? ? ? ? int ? ? ? int_value;
? ? ? ? long ? long_value;
? ? ? ? void ?*ptr_value;
? ? } value;
? ? HashEntry *next;
};
struct __HashTable{
? ? HashEntry **bucket; ? ? ? ?
? ? int size;
? ? HASH_RESULT last_error;
};
typedef struct __HashTable HashTable;
// 創建大小為hash_size的哈希表，創建成功后返回HashTable類型的指針，否則返回NULL。
HashTable *create_hash(int hash_size);
哈希表相關說明：
HASH_RESULT 類型為相關函數的返回類型
HashEntry 為哈希表所保存元素（即鍵值對 《key, value》）類型
HashTable 為哈希表，其中 bucket 指向大小為size的、元素類型為 HashEntry*的指針數組
哈希表采用鏈地址法處理沖突
請實現 create_hash 函數，創建指定大小的哈希表。
#include <stdio.h>
#include <stdlib.h>
#include "hash.h"
HashTable* create_hash(int size){
?? ?HashTable *r;
?? ?
?? ?r = (HashTable *)malloc(sizeof(HashTable));
?? ?if(r == NULL) return NULL;
?? ?
?? ?r->bucket = (HashEntry **)malloc(size * sizeof(HashEntry *));
?? ?if(r->bucket == NULL){
?? ??? ?free(r);
?? ??? ?return NULL;
?? ?}
?? ?
?? ?r->size = size;
?? ?r->last_error = HASH_OK;
?? ?return r;
}
添加:?
向哈希表中添加元素，其中鍵類型為char*， 元素類型為int。
HASH_RESULT hash_add_int(HashTable * table, const char * key, int value);
哈希表相關說明：
HASH_RESULT 類型為相關函數的返回類型
HashEntry 為哈希表所保存元素（即鍵值對 《key, value》）類型
HashTable 為哈希表，其中 bucket 指向大小為size的、元素類型為 HashEntry*的指針數組
哈希表采用鏈地址法處理沖突
請實現 hash_add_int 函數，向哈希表中添加元素，其中鍵類型為char*， 元素類型為int。
在添加過程中，如果要添加的鍵值key已在哈希表中，且對應的值value也已存在，則函數返回 HASH_ALREADY_ADDED；
如果要添加的鍵值key已在哈希表中，但對應的值value不同，函數將value值更新到哈希表中，之后返回 HASH_REPLACED_VALUE
如果要添加的鍵值key不在哈希表中，則函數創建 HashEntry 類型，并將其加入到哈希表中，且函數返回 HASH_ADDED。
本題所用的哈希函數如下：
long hash_string(const char *str)
{
? ? long hash = 5381;
? ? int c;
? ? while (c = *str++)
? ? ? ? hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
? ? if(hash < 0)
? ? ? ? hash *= -1;
? ? return hash;
}
#include <stdio.h> ? ?
#include "stdlib.h"
#include "hash.h" ? ? ?
#include <string.h>
?
HASH_RESULT hash_add_int(HashTable *table, const char *key, int value ){
?? ?
?? ?HashEntry *p;//指的是每一個鍵值對?
?? ?int h = hash_string(key) % table->size;//保存哈希函數返回值?
?? ?//int類型也可以?
?? ?// !h %= table->size; 編譯器奇怪的不通過.....?
?? ?
?? ?//該關鍵字對應的哈希表中鍵值對不存在, 分配節點存入?
?? ?if(!table->bucket[h]){
?? ??? ?p = (HashEntry *)malloc(sizeof(HashEntry));
?? ??? ?if(!p) return HASH_ERROR;
?? ??? ?p->key.str_value = (char *)malloc(strlen(key));
?? ??? ?if(!p->key.str_value){
?? ??? ??? ?free(p);
?? ??? ??? ?return HASH_ERROR;
?? ??? ?}
?? ??? ?//!!!!字符串拷貝?
?? ??? ?strcpy(p->key.str_value, key);
?? ??? ?p->value.int_value = value;
?? ??? ?//最好還是置空?
?? ??? ?p->next = NULL;
?? ??? ?table->bucket[h] = p;
?? ??? ?
?? ??? ?return HASH_ADDED;
?? ?}
?? ?//關鍵字對應的哈希表中該位置存在鍵值對,判斷重復或者沖突?
?? ?p = table->bucket[h];
?? ?while(p){?? ?
?
?? ??? ?//關鍵字相同?
?? ??? ?if(strcmp(key, p->key.str_value)==0){
?? ??? ??? ?//判斷值?
?? ??? ??? ?if(p->value.int_value == value){
?? ??? ??? ??? ?return HASH_ALREADY_ADDED;
?? ??? ??? ?}
?? ??? ??? ?else{
?? ??? ??? ??? ?p->value.int_value = value;
?? ??? ??? ??? ?return HASH_REPLACED_VALUE;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?//鏈地址法?
?? ??? ?else{
?? ??? ??? ?if(p->next)
?? ??? ??? ??? ?p = p->next;
?? ??? ??? ?else
?? ??? ??? ??? ?break;
?? ??? ?}
?? ?
?? ?}
?? ?//循環完成后?
?? ?//p指向最后一個結點?
?? ?HashEntry *q;//q接到p后面?
?? ?q = (HashEntry *)malloc(sizeof(HashEntry));
?? ?if(!q) return HASH_ERROR;
?? ?
?? ?q->key.str_value = (char *)malloc(strlen(key));
?? ?if(!q->key.str_value){
?? ??? ?free(q);
?? ??? ?return HASH_ERROR;
?? ?}
?? ?
?? ?strcpy(q->key.str_value, key);
?? ?q->value.int_value = value;
?? ?q->next = NULL;
?? ?p->next = q;
?? ?
?? ?return HASH_ADDED;
?? ??? ?
}
?
第八章總結:?
查找機制: 基于線性結構:靜態查找表,基于比較的順序檢索和折半檢索(有點像快排)
?? ??? ? ?基于樹形結構:動態查找?
?? ??? ? ?哈希計算式查找: 根據關鍵字計算存儲地址
二叉排序樹:值域左子樹 < 根 < 右子樹
其構建:每次從根節點開始比較,順次比較插入
對于二叉排序樹中序遍歷得到遞增序列
查找:比較次數不超過樹的深度,平均查找長度O(log2(n)).?
平衡二叉樹...(AVL)?
Hash法...?
第九章 內部排序?
排序:重點在于對于記錄的關鍵字進行排序,得到按關鍵字有序記錄序列
分為:
?? ?A.內部排序: 排序過程在內存中進行?
?? ?B.外部排序: 待排序記錄數據量過大,需要借助外部存儲設備
排序的穩定性:排序后有相同關鍵字的記錄順序不變就是穩定的排序
插入類排序:
1.直接插入排序:將新加入的記錄的關鍵字與之前的記錄關鍵字從后往前比較,
?? ??? ??? ? ? 若較小,則向前比較,同時進行比較的記錄后移一個位置,直到找到小于等于的關鍵字,插入在其后.?
實例代碼如下: (表內操作)
void InsSort(int r[], int length){//r可以設置為結構數組,這里認為是數組?
?? ?int i,j;
?? ?for(i = 2; i < length; i++){ // i=2開始,i=1為第一個元素,認為是子表,i=0設置為監視哨?
?? ??? ?r[0] = r[i];//將待插入記錄存到監視哨中,臨時保存?
?? ??? ?j = i - 1; ?//i為初始待插入記錄位置,i-1為需要比較的記錄位置
?? ??? ?while(r[0] < r[j]){
?? ??? ??? ?r[j+1] = r[j];
?? ??? ??? ?j--;
?? ??? ?}?
?? ??? ?r[j+1] = r[0];
?? ?}
}?
優點:算法簡單,適用于記錄數目較少且基本有序
時間復雜度:O(n^2).
2.折半插入排序:類似于快排
示例代碼如下:
void BinSort(int r[], int length){
?? ?int i, x, j;
?? ?int low, high, mid;
?? ?for(i = 2;i <= length; i++){
?? ??? ?x = r[i];
?? ??? ?low = 1;
?? ??? ?high = i - 1;
?? ??? ?while(low < high){//Attention!不取等,書上是錯的?
?? ??? ??? ?mid = (low + high) / 2;
?? ??? ??? ?if(x < r[mid])
?? ??? ??? ??? ?high = mid - 1;
?? ??? ??? ?else
?? ??? ??? ??? ?low = mid + 1;
?? ??? ?}
?? ??? ?for(j = i - 1; j >= low; j--)
?? ??? ??? ?r[j+1] = r[j];
?? ??? ?r[low] = x;?
?? ?}
}?
時間復雜度:O(n^2).
需要比較的次數最大為其折半判定樹的深度log2(n)
3.希爾排序:排序結果,基本有序;又稱縮小增量排序;將關鍵字序列分為若干個子序列,對子序列插入排序
void f1(int r[], int length, int d){//d為這一輪子序列長度(增量)?
?? ?int i, j;
?? ?
?? ?for(i = 1+d; i <= length; i++){
?? ??? ?if(r[i] < r[i-d]){
?? ??? ??? ?r[0] = r[i];
?? ??? ??? ?for(j = i - d; j > 0 && r[j] > r[0]; j -= d){
?? ??? ??? ??? ?r[j + d] = r[j];
?? ??? ??? ?}//如果子序列后者的記錄關鍵字比前小,就復制前者到后者?
?? ??? ??? ?r[j + d] = r[0];//復制要交換的一個到適合的位置?
?? ??? ?}
?? ?}
}?
?
void f2(int r[], int length, int d[], int n){
?? ?for(i = 0; i < n; i++)//d[]為增量數組,n為該數組長度 d[n-1] == 1;?
?? ??? ?f1(r, length, d[i]);
}
時間復雜度:O(n^1.5).
算法不是穩定的 .
交換類排序:
1.冒泡排序(相鄰比序法):反復掃描記錄序列,依次交換逆序記錄的位置
void BubbleSort(int r[], int n){
?? ?bool change = true;
?? ?int i,j;
?? ?int x = 0;
?? ?for(i = 1; i < n && change; i++){
?? ??? ?change = false;
?? ??? ?for(j = 1; j <= n - i; j++){//一趟排序后最大的定了,在最后?
?? ??? ??? ?if(r[j]>r[j+1])
?? ??? ??? ?{
?? ??? ??? ??? ?x = r[j];
?? ??? ??? ??? ?r[j] = r[j+1];
?? ??? ??? ??? ?r[j+1] = x;
?? ??? ??? ??? ?change = true;
?? ??? ??? ?}
?? ??? ?}
?? ?}
}?
//下面這種簡單些:上升法,不帶標記?
void BubbleSort(int r[], int n){
?? ?int i, j, k;
?? ?
?? ?for(i = 0; i < n; i++){
?? ??? ?for(j = n - 2; j >= i; j--){
?? ??? ??? ?if(r[j] > r[j+1]){
?? ??? ??? ??? ?k = r[j];
?? ??? ??? ??? ?r[j] = r[j+1];
?? ??? ??? ??? ?r[j+1] = k;
?? ??? ??? ?}
?? ??? ?}
?? ?}?
}
時間的復雜度:O(n^2).?
2.快排:原理:一次性可以消除多個逆序來減少耗費時間
找到一個劃分元,關鍵字小的移到前面,大的移到后面,遞歸在子序列中找出劃分元.直到子表長度小于等于1
void QKSort(int r[], int low. int high){
?? ?if(low < high){
?? ??? ?pos = QKPass(r, low, high);//再次快排
?? ??? ?QKSort(r, low, pos -1);
?? ??? ?QKSort(r, pos +1, high);?
?? ?}
}?
一趟快速排序算法:?
int QKPass(int r[], int low, int high){
?? ?int x;
?? ?while(low < high){
?? ??? ?while(low < high && r[high] > x)
?? ??? ??? ?high--;
?? ??? ?if(low < high){
?? ??? ??? ?r[low] = r[high];
?? ??? ??? ?low++;
?? ??? ?}?? ?
?? ??? ?while(low < high && r[low] < x)
?? ??? ??? ?low++;
?? ??? ?if(low < high){
?? ??? ??? ?r[high] = r[low];
?? ??? ??? ?high--;
?? ??? ?}?? ??? ?
?? ?}
?? ?r[low] = x;
?? ?return low;
}
時間復雜度:O(nlog2(n))?
選擇類排序:
1.簡單選擇排序:直接從數組中選擇最小的記錄和第一個記錄交換位置,循環
void SelectSort(int r[], int b){
?? ?int i, j, k;
?? ?int x;
?? ?
?? ?for(i = 1; i < n; i++){
?? ??? ?k = i;
?? ??? ?for(j = i+1; j <= n; j++){
?? ??? ??? ?if(r[j] < r[k])//選擇最小的記錄,得到在數組中的位置?
?? ??? ??? ??? ?k = j;
?? ??? ?}
?? ??? ?if(k != i){
?? ??? ??? ?x = r[i];
?? ??? ??? ?r[i] = r[k];
?? ??? ??? ?r[k] = x;
?? ??? ?}//交換位置?
?? ?}
}?
時間復雜度:O(n^2).
2.樹形選擇排序(錦標賽排序):與簡單選擇排序不同點是,占用空間更多,保留了之前的比較結果
每一個記錄看作葉子節點,兩兩比較,選出最小的為雙親,進一步遞歸向上,找出根,比較成功后,
該記錄對應的葉子節點置為無窮;
進一步兩兩比較重復上述過程,直到記錄全部輸出
時間復雜度:O(nlog2(n)).?
3.堆排序:排序過程中把向量中儲存的數據看作一顆完全二叉樹來進行操作
重建堆:
?? ?大堆,篩選最大的元素出去,然后最后的元素補根節點,調整堆使最大的元素在最上面?
void sift(Type r[], int k, int m){
?? ?//r[k...m]是以r[k]為根的完全二叉樹,調整r[k]使之滿足堆的性質?
?? ?int i, j, t, x;
?? ?
?? ?t = r[k];
?? ?x = r[k].key;?
?? ?i = k;
?? ?j = 2 * k;//j指向t的左孩子
?? ?bool finished = false;
?? ?
?? ?while(j <= m && !finished){
?? ??? ?if(j + 1 <= m && r[j].key < r[j+1].key){
?? ??? ??? ?j++;
?? ??? ?}//得到左右孩子中記錄關鍵字較大的位置坐標?
?? ??? ?if(x >= r[j].key) //如果滿足堆的性質,上面的比孩子大?
?? ??? ??? ?finished = true;
?? ??? ?else{
?? ??? ??? ?r[i] = r[j];
?? ??? ??? ?i = j;
?? ??? ??? ?j = 2 * i;
?? ??? ?}
?? ?}?
?? ?r[i] = t;
}?
建初堆:
void crt_heap(Type r[], int n)
{
?? ?//對r[]建立堆, n為數組長度
?? ?int i;
?? ?for(i = n / 2; i >= 1; i--)//i指向最后一個非葉子節點?
?? ??? ?sift(r, i, n);?
?}?
堆排序算法:
void HeapSort(Type r[], int n)
{
?? ?crt_heap(r, n);
?? ?
?? ?for(i = n; ?i>= 2 ;--i){
?? ??? ?r[0] = r[1];
?? ??? ?r[1] = r[i];
?? ??? ?r[i] = r[0];//最后一個元素和第一個元素交換位置,把最大的換到最后面去,以此達到升序排列x?
?? ??? ?sift(r, 1, i-1);
?? ?}
?}?
時間復雜度:O(nlog2(n)).
算法是不穩定的, 空間復雜度O(1) .
歸并類排序:將兩個或兩個以上的有序表合并成一個表
兩個有序子序列合并算法:?
void Merge(Type r1[], int low, int mid, int high, Type r2[])
{
?? ?//r1[low...mid]和r1[mid+1,..high]分別按照關鍵字有序排列 ,合并存放在r2[]中
?? ?int i, j, k;
?? ?i = low;
?? ?j = mid + 1;
?? ?k = low;
?? ?
?? ?while(i <= mid && j <= high){
?? ??? ?if(r1[i].key <= r1[j].key)
?? ??? ??? ?r2[k++] = r[i++];
?? ??? ?else
?? ??? ??? ?r2[k++] = r[j++];
?? ?}
?? ?while(i <= mid){
?? ??? ?r2[k++] = r1[i++];
?? ?}
?? ?while(j <= high){
?? ??? ?r2[k++] = r1[j++];
?? ?}
?}?
2-路歸并排序的遞歸算法:
void MSort(Type r1[], int low, int high, Type r3[])
{
?? ?//r1[low...high]排序后放在r3[low...high] 中, r2為輔助空間
?? ?Type *r2;
?? ?int mid;
?? ?
?? ?
?? ?r2 = (Type *)malloc(sizeof(Type) * (high - low + 1));
?? ?if(low == high) r3[low] = r1[low];
?? ?//這個是遞歸最終退出條件
?? ?else{//r1前半段放到r2前半段中,同理對于后半段,再將r2合并排序?
?? ??? ?mid = (low + high) / 2;
?? ??? ?MSort(r1, low, mid, r2);
?? ??? ?MSort(r1, mid + 1, high, r2);?
?? ??? ?Merge(r2, low, mid, high, r3);
?? ?}?
?? ?free(r2);
?}?
調用:
void MergeSort(Type r[], int n){
?? ?MSort(r, 1, n, r);
}?
分配類排序:核心是分配和收集,利用關鍵字的優先級進行排序的思想?
高位優先排序:比如橋牌,先比較花色在比較面值;比如學號,比較級,院,班,號;
低位優先排序: 鏈式基數排序
思想:基于"分配"和"收集"的操作, 將單關鍵字轉化為多關鍵字排序
將鏈表作為存儲結構, 待排序記錄以指針相連,構成鏈表;
分配:按照關鍵字取值分配記錄到鏈隊列相應隊列中,每個隊列關鍵字取值相同
收集:按照關鍵字大小,從小到大,將隊列首尾相接連接成一個鏈表;
重復上述步驟..
定義:
//待排序記錄結點
typedef struct node{
?? ?int data;//比如說一個三位數?
?? ?struct node *next;
}TNode;
//隊列首尾指針
typedef struct{
?? ?node *front;
?? ?node *rear;
}TPointer;?
//根據數組R[](已經存在元素),構建帶頭結點待排序記錄鏈表
TNode *create_list(int R[], int n){
?? ?
?? ?TNode *p, *ph;
?? ?//p為每一個存了記錄的結點, ph為頭結點
?? ?ph = (TNode *)malloc(sizeof(TNode));
?? ?if(!ph) return NULL;?
?? ?ph->next = NULL;
?? ?
?? ?int i;
?? ?for(i = 0; i < n; i++){
?? ??? ?p = (TNode *)malloc(sizeof(TNode));
?? ??? ?if(!p) return NULL;
?? ??? ?
?? ??? ?p->data = R[i];
?? ??? ?//頭插法插入?
?? ??? ?p->next = ph->next;
?? ??? ?ph->next = p;
?? ?}
?? ?return ph;//返回頭結點?
}?
#define N 10
//分配算法,對三位數的記錄序列按照關鍵字低位排序分配?
void dispatch(TNode *ph, TPointer *Q, int d){?? ?
?? ?//ph存記錄, Q隊列:存指針,d根據關鍵字到那一趟取值不同?? ?
?? ?TNode *p = NULL;//作為輔助空間拆分ph?
?? ?int i, idx;
?? ?
?? ??
?? ?//初始化Q
?? ?for(i = 0; i < N; i++){
?? ??? ?Q[i].front = NULL;
?? ??? ?Q[i].rear = NULL;?
?? ?}?
?? ?
?? ?p = ph->next;
?? ?if(p){
?? ??? ?ph->next = p->next;
?? ??? ?p->next = NULL;
?? ?}//第一個記錄被單獨拆到p里面
?? ?
?? ?while(p){
?? ??? ?idx = p->data;
?? ??? ?for(i = 0; i < d; i++)
?? ??? ??? ?idx = idx / N;
?? ??? ?//第一趟排序,d = 0
?? ??? ?idx = idx % N;
?? ??? ?
?? ??? ?//根據關鍵字分配到Q中
?? ??? ?if(Q[idx].front = NULL){
?? ??? ??? ?Q[idx].front = p;
?? ??? ??? ?Q[idx].rear = p;
?? ??? ?}?
?? ??? ?else{//尾插法?
?? ??? ??? ?Q[idx].rear->next = p;
?? ??? ??? ?Q[idx].rear = p;
?? ??? ?}
?? ??? ?p = ph->next;
?? ??? ?if(p){//拆,直到拆完?
?? ??? ??? ?ph->next = p->next;
?? ??? ??? ?p->next = NULL;
?? ??? ?}
?? ?}?
}
void collect(TNode *ph, TPointer *Q){
?? ?TNode *p;
?? ?int i;
?? ?//ph為頭結點,最終可以傳出去
?? ?
?? ?for(i = 0; !Q[i].front; i++)
?? ??? ?;//找出第一個隊列中非空結點
?? ?ph->next = Q[i].front;
?? ?p = Q[i].rear;
?? ?i++;
?? ?
?? ?for(; i < N; i++){
?? ??? ?if(Q[i].front){
?? ??? ??? ?p->next = Q[i].front;
?? ??? ??? ?p = Q[i].rear;//注意的是Q[i]內部的結點是連接好的?
?? ??? ?}
?? ?}
?? ?p->next = NULL;
}?
void list_sort(int *R, int n){
?? ?int i;
?? ?TNode *ph, *p;
?? ?TPointer Q[N];
?? ?int m = max(R, n);//最大關鍵字?
?? ?
?? ?ph = create_list(R, n);
?? ?
?? ?for(i = 0; m; i++, m /= N){
?? ??? ?dispatch(ph, Q, i);
?? ??? ?collect(ph, Q);
?? ?}
?? ?for(i = 0, p = ph->next; p; p = p->next){
?? ??? ?R[i] = p->data;//復制到數組最終輸出?
?? ?}
?? ?free(ph);
}
總結
以上是生活随笔為你收集整理的第三个一千行+500行总结-数据结构C复习--知识点总结3--七到九章的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 猪肉怎么做才好吃 猪肉的四种做法介绍
- 下一篇： 单反相机什么牌子好？单反相机哪款好？