AIDROID

Subtitle

0%

408-theory-Data Structure

Posted on Edited on In , Views: Valine:

原文链接：408-theory-Data-Structure

线性表 Linear List

结构

顺序表 Sequential List

链表 Linked List

带头结点和不带头结点两种实现，带头结点保证插入删除的一致性

单链表 Singly Linked List

双向链表 Doubly Linked List

循环链表 Circular Linked List

循环单链表 Circular Singly Linked List
循环双链表 Circular Doubly Linked List

基本函数

  • ListInit(&L);初始化
  • ListLength(L);计算表长
  • ListEmpty(L);判断表空
  • ListPrint(L);输出表
  • LocateElem(L,e);按值查找
  • GetElem(L,i);下标查找
  • ListInsert(&L,i,e);插入
  • ListDelete(&L,i,&e);删除
  • ListDestroy(&L);摧毁

Sequential List

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
// seqlist
# include"stdio.h"
#include <stdlib.h>
// static memory allocation
#define SEQLIST_MAX_SIZE 1024 
#define DATATYPE int
typedef struct SList {
    int size;
    DATATYPE data[SEQLIST_MAX_SIZE];
} StaticSeqList,*PStaticSeqList ;

void StaticSeqListInit_base(PStaticSeqList list){
    list->size=0;
}
StaticSeqList StaticSeqListInit_create(){
    StaticSeqList list;
    list.size=0;
    return list;
}
StaticSeqList StaticSeqListInit_auto(DATATYPE* values,int size){

}

StaticSeqList StaticSeqListDestory(PStaticSeqList list){
    
}

void StaticSeqListPrint_base(PStaticSeqList list,int reverse){
    printf("list:");
    if(reverse==0){
        for(int i=0;i<list->size;i++) printf("%d ",list->data[i]);
        printf("\n");
        return ;
    }
    for(int i=list->size-1;i>=0;i--) printf("%d ",list->data[i]);
        printf("\n");
        return ;
}

int StaticSeqListInsert(PStaticSeqList list,DATATYPE value,int index){
    if(list->size>=SEQLIST_MAX_SIZE) {
        printf("out of max size");
        return -1;
    }
    if (index<-1){
        printf("invalid index");
        return -1;
    }

    if(index==-1 | index >=SEQLIST_MAX_SIZE-1) index=list->size;

    for(int i=list->size;i>index;i--){
        list->data[i]=list->data[i-1];
    }
    list->data[index]=value;
    list->size+=1;
    return 0;
}
int StaticSeqListDelete(PStaticSeqList list,int index){
        if(list->size<=0) {
        printf("out of max size");
        return -1;
    }
    if (index<-1){
        printf("invalid index");
        return -1;
    }
    if(index==-1 | index >=SEQLIST_MAX_SIZE-1) index=list->size;

    for(int i=list->size-1;i>index;i--){
        list->data[i-1]=list->data[i];
    }
    list->size-=1;
    return 0;
}

int StaticSeqListLocateItem(StaticSeqList list,int value){
    int i=list.size;
    while(i-->=0){
        if(list.data[i]==value) break;
    }
    return i;
}
int StaticSeqListGetItem(StaticSeqList list,int index){
    return list.data[index];
}







// dynamic memory allocation

typedef struct DList {
    int size;
    int maxsize;
    DATATYPE* data;
} DynamicSeqList,*PDynamicSeqList ;

void DynamicSeqListInit_base(PDynamicSeqList list){
    list->size=0;
}
PDynamicSeqList DynamicSeqListInit_create(int maxsize){
    PDynamicSeqList list = (PDynamicSeqList)malloc(sizeof(DynamicSeqList));
    list->data=(int*)malloc(sizeof(int)*maxsize);
    list->maxsize=maxsize;
    list->size=0;
    return list;
}
DynamicSeqList DynamicSeqListInit_auto(DATATYPE* values,int size){

}

DynamicSeqList DynamicSeqListDestory(PDynamicSeqList list){
    free(list->data);
    free(list);
}

void DynamicSeqListPrint_base(PDynamicSeqList list,int reverse){
    printf("list:");
    if(reverse==0){
        for(int i=0;i<list->size;i++) printf("%d ",list->data[i]);
        printf("\n");
        return ;
    }
    for(int i=list->size-1;i>=0;i--) printf("%d ",list->data[i]);
        printf("\n");
        return ;
}

int DynamicSeqListInsert(PDynamicSeqList list,DATATYPE value,int index){
    if(list->size>=SEQLIST_MAX_SIZE) {
        printf("out of max size");
        return -1;
    }
    if (index<-1){
        printf("invalid index");
        return -1;
    }

    if(index==-1 | index >=SEQLIST_MAX_SIZE-1) index=list->size;

    for(int i=list->size;i>index;i--){
        list->data[i]=list->data[i-1];
    }
    list->data[index]=value;
    list->size+=1;
    return 0;
}
int DynamicSeqListDelete(PDynamicSeqList list,int index){
        if(list->size<=0) {
        printf("out of max size");
        return -1;
    }
    if (index<-1){
        printf("invalid index");
        return -1;
    }
    if(index==-1 | index >=SEQLIST_MAX_SIZE-1) index=list->size;

    for(int i=list->size-1;i>index;i--){
        list->data[i-1]=list->data[i];
    }
    list->size-=1;
    return 0;
}

int DynamicSeqListLocateItem(DynamicSeqList list,int value){
    int i=list.size;
    while(i-->=0){
        if(list.data[i]==value) break;
    }
    return i;
}
int DynamicSeqListGetItem(DynamicSeqList list,int index){
    return list.data[index];
}













void main(){

    //// StaticSeqList
    // StaticSeqList ssl;    
    // StaticSeqListInit_base(&ssl);
    // printf("%d\n",ssl.size);
    // StaticSeqListInsert(&ssl,1,-1);
    // StaticSeqListInsert(&ssl,2,-1);
    // StaticSeqListPrint_base(&ssl,0);
    // printf("1 locate at:%d\n",StaticSeqListLocateItem(ssl,1));
    // printf("get ssl[1]:%d\n",StaticSeqListGetItem(ssl,1));
    // StaticSeqListDelete(&ssl,-1);
    // StaticSeqListPrint_base(&ssl,0);
    // StaticSeqListDestory(&ssl);



    //// DynamicSeqList
    // DynamicSeqList dsl=*DynamicSeqListInit_create(10);
    // DynamicSeqListInsert(&dsl,1,-1);
    // DynamicSeqListInsert(&dsl,2,-1);
    // DynamicSeqListPrint_base(&dsl,0);
    // printf("1 locate at:%d\n",DynamicSeqListLocateItem(dsl,1));
    // printf("get ssl[1]:%d\n",DynamicSeqListGetItem(dsl,1));
    // StaticSeqListDelete(&dsl,-1);
    // DynamicSeqListDestory(&dsl);



}

LinkedList

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
# include <stdio.h>
# include <stdlib.h>


// link list
typedef struct snode
{
    int data;
    struct snode *next;        
}SNode,*SinglyLinkList;
typedef struct dnode
{
    int data;
    struct dnode *prev;
    struct dnode *next;
}DNode,*DoublyLinkList;
// Singly Linked List 

// 
SinglyLinkList SinglyLinkListInit(){
    SinglyLinkList head=(SinglyLinkList)malloc(sizeof(SNode));
    head->data=0;
    head->next=NULL;
    return head;
}

int SinglyLinkListLength(SinglyLinkList list){
    int i=0;
    while(list->next){
        i++;
        list=list->next;
    }
    return i;
}
int SinglyLinkListEmpty(SinglyLinkList list){
    if(!(list->next)) return 1;
    return 0;
}

void SinglyLinkListPrint(SinglyLinkList list){
    printf("list: ");
    while(list->next){
        printf("%d ",list->next->data);
        list=list->next;
    }
    printf(";\n");
}


int SinglyLinkListInsert(SinglyLinkList list,int i,int elem){

    if(i<-1) {
        printf("index out of range\n");
        return -1;
    } 
    if (i==-1 | i>=SinglyLinkListLength(list)) i=SinglyLinkListLength(list);
    SinglyLinkList p=list;
    SinglyLinkList node=(SinglyLinkList)malloc(sizeof(SNode));
    node->data=elem;
    node->next=NULL;

    int pre=-1;

    while(pre<i-1) {
        p=p->next;
        pre+=1;
    }

    node->next=p->next;
    p->next=node;
    return 0;
}

void SinglyLinkListDelete(SinglyLinkList list,int i){

    if(i<-1) {
        printf("index out of range\n");
    } 
    if (i==-1 | i>=SinglyLinkListLength(list)-1) i=SinglyLinkListLength(list)-1;

    SinglyLinkList p=list;
    int pre=-1;
    while(pre<i-1) {
        p=p->next;
        pre+=1;
    }
    SinglyLinkList n=p->next;
    p->next=n->next;
    
    free(n);
}



int SinglyLinkListLocateItem(SinglyLinkList list,int elem){
    int i=0;
    list=list->next;
    while (list)
    {
        if ((list->data)==elem) return i;
        i++;
        list=list->next;        
    }
    return -1;
}
SinglyLinkList SinglyLinkListGetItem(SinglyLinkList list,int i){
    if(i<-1|i>=SinglyLinkListLength(list)) {
        printf("index out of range\n");
        return NULL;
    } 
    if (i==-1 ) i=SinglyLinkListLength(list)-1;
    int c=-1;
    while (c<i) {
        list=list->next;
        c+=1;
    }
    return list;
}

void SinglyLinkListDestory(SinglyLinkList list){
    while(list->next){
        SinglyLinkListDelete(list,0);
        list=list->next;
    }
    free(list);
}







// Doubly Linked List

















// Circular Linked List
//  Circular Singly Linked List

// Circular Doubly Linked List




void main(){

    SinglyLinkList list=SinglyLinkListInit();
    for(int i=0;i<10;i++){
        SinglyLinkListInsert(list,-1,i);
        SinglyLinkListPrint(list);
    }
    printf("list[2]:%d\n",SinglyLinkListGetItem(list,2)->data);
    printf("list[%d]=4\n",SinglyLinkListLocateItem(list,4));

    for(int i=0;i<10;i++){
        SinglyLinkListDelete(list,0);
        SinglyLinkListPrint(list);
    }    
    SinglyLinkListDestory(list);
}

实例

约瑟夫环

栈 Stack

结构

顺序栈 Sequential Stack

链栈 Linked Stack

共享栈 Shared Stack

基本函数

  • StackInit(&S);初始化
  • StackEmpty(S);判断栈空
  • StackPush(S,e);入栈
  • StackPop(S,&e);出栈
  • StackGetTop(S,&e);获取栈顶元素
  • StackDestroy(&S);摧毁

SequentialStack

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
# include <stdio.h>
# include <stdlib.h>

typedef struct DynamicSequentialStack
{
    int size;
    int top;
    int* data;
} DynamicSequentialStack;


DynamicSequentialStack DynamicSequentialStackInit(int size){
    DynamicSequentialStack s;
    s.data=(int*)malloc(sizeof(int)*(size+1));
    s.top=0;
    s.size=size;
    return s;
} 

int DynamicSequentialStackEmpty(DynamicSequentialStack s){
    if(s.top==0) return 1;
    else return 0;
}

int DynamicSequentialStackPush(DynamicSequentialStack *s,int elem){
    if(s->top==s->size){
        printf("stack max\n");
        return -1;
    } 
    s->data[s->top]=elem;
    s->top++;
    return 0;
}

int DynamicSequentialStackPop(DynamicSequentialStack *s,int *elem){
    if(DynamicSequentialStackEmpty(*s)){
        printf("stack empty\n");
        return -1;
    }
    *elem=s->data[--s->top];
    return 0;
}

int DynamicSequentialStackGetTop(DynamicSequentialStack *s,int *elem){
    if(DynamicSequentialStackEmpty(*s)){
        printf("stack empty\n");
        return -1;
    }
    *elem=s->data[s->top-1];

    return 0;
}

void DynamicSequentialStackDestpry(DynamicSequentialStack *s){
    free(s->data);
}



void main(){

    DynamicSequentialStack s=DynamicSequentialStackInit(3);

    DynamicSequentialStackPush(&s,10);
    DynamicSequentialStackPush(&s,9);
    DynamicSequentialStackPush(&s,8);
    DynamicSequentialStackPush(&s,7);

    int elem;
    DynamicSequentialStackGetTop(&s,&elem);
    printf("s get item:%d\n",elem);


    for(int i=0;i<4;i++){
        if(DynamicSequentialStackPop(&s,&elem)==0)  printf("s pop.%d:%d\n",i,elem);
    }
    if(DynamicSequentialStackGetTop(&s,&elem)==0)  printf("s get top:%d\n",elem);
}






LinkedStack

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
# include <stdio.h>
# include <stdlib.h>


typedef struct StackLNode{
    int data;
    struct StackLNode *next;
}StackLNode,*PStackLNode;

typedef struct LinkStack{
    int size;
    PStackLNode top;
}LinkStack,*PLinkStack;

PLinkStack LinkStackInit(){
    PLinkStack s=(PLinkStack)malloc(sizeof(LinkStack));
    s->top=NULL;
    s->size=0;
    return s;
} 

int LinkStackEmpty(PLinkStack s){
    if(s->top==NULL) return 1;
    else return 0;
}


int LinkStackPush(PLinkStack s,int elem){
    PStackLNode node=(PStackLNode)malloc(sizeof(StackLNode));

    node->data=elem;
    node->next=s->top;
    s->top=node;
    s->size++;
}

int LinkStackPop(PLinkStack s,int *elem){
    if(LinkStackEmpty(s)){
        printf("stack emtpy\n");
        return -1;
    }
    PStackLNode node=s->top;
    *elem=node->data;
    s->top=node->next;
    s->size--;
    free(node);
    return 0;
}

int LinkStackGetItem(PLinkStack s,int *elem){
    if(LinkStackEmpty(s)){
        printf("stack emtpy\n");
        return -1;
    }
    *elem=s->top->data;
    return 0;
}

void LinkStackDestpry(PLinkStack s){
    while (!LinkStackEmpty(s))
    {
        LinkStackPop(s,NULL);
    }
    free(s);
}



void main(){
    PLinkStack s=LinkStackInit();

    printf("%d\n",LinkStackEmpty(s));
    LinkStackPush(s,1);
    // printf("%p\n",s.top);
    // printf("%d\n",s->top->data);
    LinkStackPush(s,2);
    LinkStackPush(s,3);

    int elem;
    for(int i=0;i<4;i++){
        if(!LinkStackEmpty(s)){
            LinkStackPop(s,&elem);
            printf("s pop.%d:%d\n",i,elem);
        }
    }
    LinkStackPop(s,&elem);

}






实例

函数式计算

迷宫问题

DFS深度优先搜索中的应用

队列 Queue

结构

顺序实现 Sequential Queue

由于队列本身只存在首尾的元素操作，因此常用顺序结构实现

假溢出和循环队列

队空和队满判断条件

受限制队列

输入受限制队列

输出受限制队列

基本函数

  • QueueInit(&S);初始化
  • QueueEmpty(S);判断队空
  • QueueFront(S,&e);获取队头元素
  • Queuerear(S,&e);获取队尾元素
  • EnQueue(S,e);入队
  • DeQueue(S,&e);出队
  • QueueDestroy(&S);摧毁

SequentialQueue

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
# include <stdio.h>
# include <stdlib.h>



typedef struct SequentialQueue
{
    int size;
    int front,rear;
    int* data;
} SequentialQueue;


SequentialQueue SequentialQueueInit(int size){
    SequentialQueue q;
    q.size=size;
    q.front=0;q.rear=0;
    q.data=(int*)malloc(sizeof(int)*(size+1));
    return q;
}

int SequentialQueueEmpty(SequentialQueue* q){
    if(q->front==q->rear) return 1;
    return 0;
}
int SequentialQueueFull(SequentialQueue* q){
    if((q->size+q->front)%(q->size+1)==q->rear) return 1;
    return 0;
}

int SequentialQueueFront(SequentialQueue* q,int* elem){
    if(SequentialQueueEmpty(q)){
        printf("get front error:queue empty\n");
        return -1;
    }
    *elem=q->data[q->front];
    return 0;
}

int SequentialQueueRear(SequentialQueue* q,int* elem){
    if(SequentialQueueEmpty(q)){
        printf("get rear error:queue empty\n");
        return -1;
    }
    *elem=q->data[(q->size+q->rear)%(q->size+1)];
    return 0;
}

int SequentialQueueEnQueue(SequentialQueue* q,int elem){
    if(SequentialQueueFull(q)){
        printf("enqueue error:queue full\n");
        return -1; 
    }
    q->data[q->rear]=elem;
    q->rear=(q->rear+1)%(q->size+1);
    return 0;
}

int SequentialQueueDeQueue(SequentialQueue *q,int *elem){
    if(SequentialQueueEmpty(q)){
        printf("dequeue:queue empty\n");
        return -1;
    }
    *elem=q->data[q->front];
    q->front=(q->front+1)%(q->size+1);
    return 0;
}

void SequentialQueueDestory(SequentialQueue* q){
    free(q->data);
    free(q);
}












void main(){
    SequentialQueue q=SequentialQueueInit(4);
    printf("empty?:%d,full?:%d\n",SequentialQueueEmpty(&q),SequentialQueueFull(&q));
    
    int front=-1,rear=-1;
    for(int i=0;i<5;i++){
        SequentialQueueEnQueue(&q,i);
        SequentialQueueFront(&q,&front),SequentialQueueRear(&q,&rear);
        printf("front:%d,rear:%d,empty?:%d,full?:%d\n",front,rear,SequentialQueueEmpty(&q),SequentialQueueFull(&q));
    }

    int elem=-1;
    for(int i=0;i<5;i++){
        SequentialQueueDeQueue(&q,&elem);
        SequentialQueueFront(&q,&front),SequentialQueueRear(&q,&rear);
        printf("elem:%d,front:%d,rear:%d,empty?:%d,full?:%d\n",elem,front,rear,SequentialQueueEmpty(&q),SequentialQueueFull(&q));
    }  

}







LinkedQueue

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
# include <stdio.h>
# include <stdlib.h>
// 链式队列同循环链表，本身无需指定队列大小以及队空和队满的条件判断。
// 部分教材会出现链队列的判断条件设置，仅作参考，实际不会出现这种应用场景。

typedef struct LinkedQueueNode
{
    int data;
    struct LinkedQueueNode *next;
}LinkedQueueNode;



typedef struct LinkedQueue
{
    LinkedQueueNode *front,*rear;
} LinkedQueue;


LinkedQueue LinkedQueueInit(){
    LinkedQueue *q=(LinkedQueue*)malloc(sizeof(LinkedQueue));
    LinkedQueueNode *first=(LinkedQueueNode*)malloc(sizeof(LinkedQueueNode));
    first->next=NULL;
    q->front=first;
    q->rear=first;
    return *q;
}

int LinkedQueueEmpty(LinkedQueue *q){
    if(q->front==q->rear) return 1;
    return 0;
}

int LinkedQueueFront(LinkedQueue *q,int *elem){
    if(LinkedQueueEmpty(q)){
        printf("\033[31mLinkedQueueFront(LinkedQueue *q,int *elem):queue empty\n\033[0m");
        return -1;
    }
    *elem=q->front->data;
    return 0;
}
int LinkedQueueRear(LinkedQueue *q,int *elem){
    if(LinkedQueueEmpty(q)){
        printf("\033[31mLinkedQueueRear(LinkedQueue *q,int *elem):queue empty\n\033[0m");
        return -1;
    }
    *elem=q->rear->data;
    return 0;
}

int LinkedQueueEnqueue(LinkedQueue *q,int elem){
    LinkedQueueNode *node=(LinkedQueueNode*)malloc(sizeof(LinkedQueueNode));
    q->rear->data=elem;
    node->next=q->rear->next;
    q->rear->next=node;
    q->rear=node;
    return 0;    
}

int LinkedQueueDequeue(LinkedQueue *q,int *elem){
    if(LinkedQueueEmpty(q)){
        printf("\033[31mLinkedQueueDequeue(LinkedQueue *q,int *elem):queue empty\n\033[0m");
        return -1;
    }
    LinkedQueueNode *node=q->front;
    q->front=node->next;
    *elem=node->data;
    free(node);
    return 0;
}

void LinkedQueueDestory(LinkedQueue *q){
    while (!LinkedQueueEmpty(q))
    {
        LinkedQueueDequeue(q,NULL);
    }
}



void main(){

    LinkedQueue q=LinkedQueueInit();
    printf("q empty?:%d\n",LinkedQueueEmpty(&q));

    int front=-1,rear=-1;
    for(int i=0;i<4;i++){
        LinkedQueueEnqueue(&q,i);
        LinkedQueueFront(&q,&front);
        // LinkedQueueRear(&q,&rear); // rear point to the new empty node;
        printf("front:%d\n",front);
    }
    int elem=-1;
    for(int i=0;i<5;i++){
        LinkedQueueDequeue(&q,&elem);
        LinkedQueueFront(&q,&front);
        printf("elem:%d,front:%d\n",elem,front);
    }
    LinkedQueueDestory(&q);
}







实例

函数式计算

BFS广度优先搜索中的应用

数组 Array

结构

矩阵压缩

下标、索引的计算问题

一般问题中经常会出现索引和下标同时出现的情况，在计算机中索引从0开始，
下标访问元素为An，实际索引地址为A[n-1]。解决方法为全部采用下标计算，最后在下标访问地址减1。

对角矩阵

三角矩阵

三对角矩阵

稀疏矩阵

基本函数

实例

Numpy高效矩阵库的实现

串

结构

存储格式

  • 静态存储：静态为使用一个连续数组存储，存在上限。
  • 动态存储：动态为使用malloc和free实现在堆区的存储。
  • 块链存储：在每个块内连续纯粹，块之间使用链存储。

模式匹配算法

暴力匹配 O(mn)

KMP O(m+n)

子串，前后缀，最长匹配前后缀、PM(partical match)数组、Next数组、Nextval数组
实现思路：通过模式串的最长匹配前后缀长度，如果i字符出现失配，可以让i位前的子串的前缀字符直接移到后缀位置，因为是匹配的，也就是跳过中间的无效字符:

$move[i]=(i-1)-PM[i-1]$
$j=j-move[i]=1+PM[j-1]$
为了让第i位直接访问，我们将PM数组右移一位，首位为-1，然后数组+1，最终得到next数组,即第j位出现失配，更新j为$next[j]$的值
$j=next[j]$

基本函数

  • StringAssign(&T,chars);初始化
  • StringDestroy(&S);摧毁
  • StringLength(S);摧毁
  • Stringcopy(&S2,S1);S1赋值到S2
  • StringCompare(S1,S2);比较
  • SubString(&sub,S1,start,len);获取子串
  • StringConcat(&S3,S1,S2);合并
  • Index(S,P) 判断串S中首次出现P的索引

String

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
# include <stdio.h>
# include <stdlib.h>



typedef struct String
{
    char *ch;
}String;


void StringInit(String *s,char *chars,int len){
    s->ch=(char*)malloc(sizeof(char)*(len+1));
    int i;
    for(i=0;i<len;i++){
        s->ch[i]=chars[i];
    }
    s->ch[i]='\0';
}

int StringLength(String s){
    int i=0;
    while(s.ch[i]!='\0') i++;
    return i;
}

void StringCopy(String *s1,String s2){
    int i=StringLength(s2);
    s1->ch=(char*)malloc(sizeof(char)*(i+1));
    s1->ch[i]='\0';
    while(--i>-1){
        s1->ch[i]=s2.ch[i];
    }
}

int StringCompare(String s1,String s2){
    int len=StringLength(s1);
    if(len!=StringLength(s2)) return 0;
    while(len>-1) {
        if (s1.ch[len]!=s2.ch[len]) return 0;
        len--;
    }
    return 1;
}

int SubString(String *sub,String s,int start, int len){
    int slen=StringLength(s);
    if((start<0)||(start>slen-1)||(start+len>slen-1)){
        sub->ch=(char*)malloc(sizeof(char));
        sub->ch[0]='\0';
        return -1;
    }
    sub->ch=(char*)malloc(sizeof(char)*len+1);
    sub->ch[len]='\0';
    for(int i=0;i<len;i++){
        sub->ch[i]=s.ch[start+i];
    }    
    return 0;
}

void StringConcat(String *s,String s1,String s2){
    int ls1=StringLength(s1),ls2=StringLength(s2);
    int ls=ls1+ls2;
    s->ch=(char*)malloc(sizeof(char)*(ls+1));
    s->ch[ls]='\0';
    int i;
    for(i=0;i<ls1;i++){
        s->ch[i]=s1.ch[i];
    }
    for(i=0;i<ls2;i++){
        s->ch[ls1+i]=s2.ch[i];
    }    
}


void String_kmp_get_nextval(int* nextval,String p,int lp){
    nextval[0]=0,nextval[1]=0,nextval[2]=1;
    int i=2,j=1;
    while (i<lp)
    {
        // printf("%d:%c,",i,p.ch[i]);
        // printf("%d:%c,",j,p.ch[j]);
        // printf("%d\n",p.ch[i]==p.ch[j]);
        if(j==0 || p.ch[i-1]==p.ch[j-1]){
            i++;j++;
            nextval[i]=j;
        }
        else{
            j=nextval[j];
        }
    }
}

int StringPatternMach(String s,String p){
    int ls=StringLength(s),lp=StringLength(p);
    int* nextval=(int*)malloc(sizeof(int)*(lp+1));
    String_kmp_get_nextval(nextval,p,lp);
    for(int i=1;i<StringLength(p)+1;i++) printf("%d,",nextval[i]);

    int i=1,j=1;
    printf("%c\n",p.ch[j-1]);
    while(i<=ls && j<=lp){
        printf("s.%d,p.%d\n",i,j);
        printf("%c==%c\n",s.ch[i-1],p.ch[j-1]);
        if(j==0){
            i++;
            j=1;
            continue;
        }
        if(s.ch[i-1]==p.ch[j-1]) {
            i++;j++;
        }
        else{
            j=nextval[j];
        }
    }

    if(j>lp) return i-1-lp;
    else return -1;
}



void StringDestory(String *s){
    free(s->ch);
}



void main(){
    String s1;
    String subs1;
    String s2;
    String s3;
    String s4;
    String p;


    StringInit(&s1,"hello world!",sizeof("hello world!"));
    StringCopy(&s2,s1);
    StringInit(&s3,"hello",sizeof("hello"));

    printf("S1:%s\n",s1);
    printf("S1.size:%d\n",StringLength(s1));
    
    SubString(&subs1,s1,2,3);
    printf("S1[2:5]:%s  ",subs1); // s1[2,5)
    printf("S1[2:5].size:%d\n",StringLength(subs1));


    printf("s2:%s\n",s2);
    printf("s3:%s\n",s3);

    printf("s1==s2:%d\n",StringCompare(s1,s2));
    printf("s2==s3:%d\n",StringCompare(s2,s3));

    StringConcat(&s4,s1,s3);
    printf("s4=s1+s3:%s\n",s4);

    SubString(&p,s1,3,5);
    printf("p:%s\n",p);

    printf("search %s in %s, idx:%d\n",p,s1,StringPatternMach(s1,p));

    StringDestory(&s1);
    StringDestory(&subs1);
    StringDestory(&s2);
    StringDestory(&s3);
    StringDestory(&s4);
    StringDestory(&p);


    printf("process terminated successfully\n");


    // String s;
    // StringInit(&s,"ababaaababaa",sizeof("ababaaababaa"));
    // int* nextval=(int*)malloc(sizeof(int)*(StringLength(s)+1));
    // String_kmp_get_nextval(nextval,s,StringLength(s));
    // for(int i=0;i<StringLength(s)+1;i++) printf("%d,",nextval[i]);
}











实例

树

概念

树
二叉树
满二叉树
完全二叉树
二叉排序树
平衡二叉树

根结点 叶结点 非终端结点 度 双亲 左右孩子 兄弟 叔侄 子孙 祖先
二叉树与度为2的有序树不同，二叉树允许为空，但树为空时度不为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
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
#include<queue>
#include<deque>
#include"iostream"
using namespace std;
// #include"Python.h"
typedef struct LinkedBinaryTreeNode
{
    int data;
    LinkedBinaryTreeNode *left;
    LinkedBinaryTreeNode *right;   
}LinkedBinaryTree;

LinkedBinaryTree* LinkedBinaryTreeNewNode(int data){
    LinkedBinaryTree* node=(LinkedBinaryTree*)malloc(sizeof(LinkedBinaryTree));
    node->data=data;
    node->left=nullptr;
    node->right=nullptr;
    return node;
}
int LinkedBinaryTreeAddNode(LinkedBinaryTree* root,int data){
    LinkedBinaryTree* newnode=LinkedBinaryTreeNewNode(data);
    if(!root){
        *root=*newnode;
        return 0;
    }
    queue<LinkedBinaryTree*> q;
    q.push(root);
    while (!q.empty())
    {
        LinkedBinaryTreeNode* node=q.front();
        q.pop();
        if(node->left){
            q.push(node->left);
        }else{
            node->left=newnode;
            return 0;
        }
        if(node->right){
            q.push(node->right);
        }else{
            node->right=newnode;
            return 0;
        }
    }
    return 0;
}

int LinkedBinaryTreePreorder(LinkedBinaryTree* root){
    if(!root) return 0;
    cout<<root->data<<endl;
    LinkedBinaryTreePreorder(root->left);
    LinkedBinaryTreePreorder(root->right);
    return 0;
}

int LinkedBinaryTreePreorder_Stack(LinkedBinaryTree* root){
    deque<LinkedBinaryTree*> q;
    q.push_front(root);
    cout<<"preorder:";
    if(!root){
        return -1;
    }
    while (!q.empty())
    {
        LinkedBinaryTree* node=q.front();
        cout<<node->data<<" ";
        q.pop_front();
        if(node->right){
            q.push_front(node->right);
        }
        if(node->left){
            q.push_front(node->left);
        }
    }
    cout<<""<<endl;
    return 0;
}
int LinkedBinaryTreeInorder_Stack(LinkedBinaryTree* root){
    deque<LinkedBinaryTree*> q;
    LinkedBinaryTree* node=root;
    cout<<"inorder:";
    if(!root){
        return -1;
    }

    while (node||!q.empty())
    {
        while(node){
            q.push_front(node);
            node=node->left;
        }
        if(!q.empty()){
            node=q.front();
            cout<<node->data<<" ";
            q.pop_front();
            node=node->right;            
        }
    }
    cout<<""<<endl;
    return -1;
}
int LinkedBinaryTreePostorder_Stack(LinkedBinaryTree* root){
    deque<LinkedBinaryTree*> q;
    deque<int> res;
    LinkedBinaryTree* node=root;

    cout<<"postorder:";
    if(!root){
        return -1;
    }
    while (node||!q.empty())
    {
        while (node)
        {
            q.push_front(node);
            res.push_front(node->data);
            node=node->right;
        }
        node=q.front()->left;
        q.pop_front();
    }
    while (!res.empty())
    {
        cout<<res.front()<<" ";
        res.pop_front();
    }
    cout<<""<<endl;
    return -1;
}

int LinkedBinaryTreeSearchNode(LinkedBinaryTree* root,int data, LinkedBinaryTree** get_node){
    deque<LinkedBinaryTree*> q;
    q.push_front(root);
    while (!q.empty())
    {
        LinkedBinaryTree* node=q.front();
        if(node->data==data){
            *get_node=node;
            return 0;            
        }
        q.pop_front();
        if(node->right){
            q.push_front(node->right);
        }
        if(node->left){
            q.push_front(node->left);
        }
    }

    return -1;

}
int LinkedBinaryTreeInsertNode(LinkedBinaryTree* root,int parent_data,int data,int lflag){
    LinkedBinaryTree* node;
    if(LinkedBinaryTreeSearchNode(root,parent_data,&node)==-1){
        cout<<"LinkedBinaryTreeInsertNode(LinkedBinaryTree* root,int parent_data,int data,int lflag):node."<<parent_data<<" not exit"<<endl;
        return -1;
    }

    if(lflag){
        if(node->left){
            cout<<"LinkedBinaryTreeInsertNode(LinkedBinaryTree* root,int parent_data,int data,int lflag):node."<<parent_data<<"->left exit"<<endl;
            return -1;
        }
        node->left=LinkedBinaryTreeNewNode(data);
    }else{
        if(node->right){
            cout<<"LinkedBinaryTreeInsertNode(LinkedBinaryTree* root,int parent_data,int data,int lflag):node."<<parent_data<<"->right exit"<<endl;
            return -1;
        }
        node->left=LinkedBinaryTreeNewNode(data);        
    }
    return 0;
}

void LinkedBinaryTreeDestory(LinkedBinaryTree** root){
    deque<LinkedBinaryTree*> q;
    deque<LinkedBinaryTree*> nodes;
    LinkedBinaryTree* node=*root;

    while (node||!q.empty())
    {
        while (node)
        {
            q.push_front(node);
            nodes.push_front(node);
            node=node->right;
        }
        node=q.front()->left;
        q.pop_front();
    }
    while (!nodes.empty())
    {
        node=nodes.front();
        free(node);
        nodes.pop_front();
    }
    *root=nullptr;
    cout<<"Tree Destory"<<endl;
}








int main(){

    LinkedBinaryTree* root=LinkedBinaryTreeNewNode(0);
    cout<<"123"<<endl;
    LinkedBinaryTreeAddNode(root,1);
    LinkedBinaryTreeAddNode(root,2);
    LinkedBinaryTreeAddNode(root,3);
    LinkedBinaryTreeAddNode(root,4);
    LinkedBinaryTreeAddNode(root,5);
    LinkedBinaryTreeAddNode(root,6);
    LinkedBinaryTreeAddNode(root,7);

    LinkedBinaryTreePreorder_Stack(root);
    LinkedBinaryTreeInorder_Stack(root);
    LinkedBinaryTreePostorder_Stack(root);

    // LinkedBinaryTree* node;
    // if(LinkedBinaryTreeSearchNode(root,1,&node)==0){
    //     cout<<node->data<<endl;
    // }

    LinkedBinaryTreeInsertNode(root,7,10,1);
    LinkedBinaryTreePreorder_Stack(root);
    LinkedBinaryTreeDestory(&root);
    LinkedBinaryTreePreorder_Stack(root);

    return 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
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#include"iostream"
#include<deque>
#include<stack>
#include<queue>

using namespace std;

typedef struct ThreadTree{
    int data;
    int lflag,rflag;
    ThreadTree* left;
    ThreadTree* right;
}ThreadTree;

ThreadTree* ThreadTreeNewNode(int data){
    ThreadTree* node=(ThreadTree*)malloc(sizeof(ThreadTree));
    node->data=data;
    node->lflag=node->rflag=0;
    node->left=node->right=0;
    return node;
}

int ThreadTreeAddNode(ThreadTree* root,int data){
    queue<ThreadTree*> q;
    q.push(root);
    while (!q.empty())
    {
        ThreadTree* node=q.front();
        q.pop();
        if(node->left==nullptr){
            node->left=ThreadTreeNewNode(data);
            return 0;
        }else{
            q.push(node->left);
        }
        if(node->right==nullptr){
            node->right=ThreadTreeNewNode(data);
            return 0;
        }else{
            q.push(node->right);
        }
    }
    return -1;
}

int ThreadTreeInsertNode(ThreadTree* root,int parent_data,int data,int lflag){
    queue<ThreadTree*> q;
    q.push(root);
    ThreadTree* parent;
    while (!q.empty())
    {
        ThreadTree* node=q.front();
        q.pop();
        if(node->data==parent_data){
            parent=node;

            break;
        }
        if(node->left!=nullptr){
            q.push(node->left);
        }
        if(node->right!=nullptr){
            q.push(node->right);
        }
    }
    if(lflag){
        if(parent->left){
            cout<<"ThreadTreeInsertNode(ThreadTree* root,int parent_data,int data,int lflag): node."<<parent_data<<"->left exists"<<endl;
            return -1;
        }else{
            parent->left=ThreadTreeNewNode(data);
        }
    }else{
        if(parent->right){
            cout<<"ThreadTreeInsertNode(ThreadTree* root,int parent_data,int data,int lflag): node."<<parent_data<<"->right exists"<<endl;
            return -1;
        }else{
            parent->right=ThreadTreeNewNode(data);
        }
    }

    return 0;
}




int ThreadTreePreThreading(ThreadTree* root,ThreadTree*& prev){
    if(root==nullptr){
        return -1;
    }
    
    if(root->left==nullptr){
        root->left=prev;
        root->lflag=1;
    }
    if(prev!=nullptr && prev->right==nullptr){
        prev->right=root;
        prev->rflag=1;
    }
    prev=root;
    
    if(!root->lflag){
        ThreadTreePreThreading(root->left,prev);
    }
    if(!root->rflag){
        ThreadTreePreThreading(root->right,prev);
    }



    return 0;
}
int ThreadTreeBuildPreThread(ThreadTree* root){
    ThreadTree* node=nullptr;
    int res=ThreadTreePreThreading(root,node);
    return res;    
}
int ThreadTreePreOrderbyPreThread(ThreadTree* root){
    ThreadTree* node=root;
    cout<<"PreOrder by PreThread:"<<" ";
    while (node)
    {
        cout<<node->data<<" ";
        if(node->rflag||node->lflag){
            node=node->right;
        }else{
            node=node->left;
        }
    }
    cout<<""<<flush;
    return 0;
}

int ThreadTreeInThreading(ThreadTree* root,ThreadTree*& prev){
    if(root==nullptr){
        return -1;
    }
    ThreadTreeInThreading(root->left,prev);
    
    if(root->left==nullptr){
        root->left=prev;
        root->lflag=1;
    }
    if(prev!=nullptr && prev->right==nullptr){
        prev->right=root;
        prev->rflag=1;
    }
    prev=root;
    
    ThreadTreeInThreading(root->right,prev);
    return 0;
}
int ThreadTreeBuildInThread(ThreadTree* root){
    ThreadTree* node=nullptr;
    int res=ThreadTreeInThreading(root,node);
    return res;   
}
int ThreadTreeInOrderbyInThread(ThreadTree* root){
    ThreadTree* node=root;
    cout<<"InOrder by InThread:";

    while (node!=nullptr && node->lflag==0)
    {
        node=node->left;
    }
    
    while(node){
        cout<<node->data<<" ";
        if(node->rflag){
            node=node->right;
        }else{
            node=node->right;
            while (node!=nullptr && node->lflag==0){
                node=node->left;
            }
        }
    }
    cout<<""<<flush;;
    
    return 0;
}


int main(){
    ThreadTree* root=ThreadTreeNewNode(0);
    ThreadTreeAddNode(root,1);
    ThreadTreeAddNode(root,2);
    ThreadTreeAddNode(root,3);
    ThreadTreeAddNode(root,4);
    ThreadTreeAddNode(root,5);
    ThreadTreeAddNode(root,6);
    ThreadTreeInsertNode(root,6,7,0);
    
    ThreadTreeBuildPreThread(root);
    ThreadTreePreOrderbyPreThread(root);
    ThreadTreeBuildInThread(root);
    ThreadTreeInOrderbyInThread(root);
    return 0;
}






非递归形式实现上述遍历

森林

双亲、孩子、孩子兄弟表示法
树、森林转二叉树
树、森林的遍历

树 森林 二叉树
先根 先序 先序
后根 中序 中序

实例

哈夫曼编码
并查集

图

概念

有向图 无向图 完全图
简单图 多重图
子图
连通 连通图 连通子图 连通分量：极大连通子图
强连通图 强连通分量
生成树 生成森林
入度 出度 边权 网
路径 路径长度 回路
简单路径 简单回路
距离

结构

邻接矩阵存储（有向无向）
邻接表存储（有向无向）
十字链表存储（有向）
邻接多重表存储（无向）

遍历

可以通过图的遍历判断图的联通性

广度优先搜索BFS

队列实现
BFS可实现求权长度相同网络的单源最短路径问题

方法 时间 空间
邻接表 O(v+e) O(v)
邻接矩阵 O(v2) O(v)

深度优先搜索DFS

栈实现

方法 时间 空间
邻接表 O(v+e) O(v)
邻接矩阵 O(v2) O(v)

实例

最小生成树Minimum-Spanning Tree

prim算法：选择一个结点，每次添加一个可加入的最短距离结点直到所有结点都添加

kruskal算法：每次选取最短路边加入其结点，如果这两个结点已经在同一集合中跳过该边

最短路径

dijkstra算法
先从选定结点开始构造一个距离数组和路径数组，距离初始化为该结点到其它结点的直接距离。每次选择当前集合与其它点之间最短距离结点，并通过该新结点更新与其它结点的最短距离，如果$dis[i]>dis[j]+e(j,i)$就更新

floyd算法
通过最短距离矩阵直接计算所有结点之间的最短距离。

有向无环图实现公共子表达式

拓扑排序

AOV网 结点网

AOE网 边网

六参数法 求解关键路径和最早最晚开始完成时间

查找

概念

查找表 静态查找 动态查找 关键字 平均查找长度ASL 平均查找成功长度 平均查找失败长度

顺序查找

顺序查找

折半查找

分块查找

ASL=(b+1)/2+(s+1)/2 b为块数 s为块中元素个数
当b=sqrt(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
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
#include"iostream"
#include"random"

using namespace std;

typedef struct SequentialSearchTable{
    int *elem;
    int size;
}SSTable;

int SequentialSearch(SSTable l,int item){
    
    l.elem[0]=item; // sentinel 
    int i;
    for(i=l.size;l.elem[i]!=item;i--);
    return i;
}
int OrderedSequentialSearch(SSTable l,int item){
    int i=l.size;
    while(i<=l.size&&l.elem[i]>item)    i--;
    if(l.elem[i]==item) return i;
    else return 0;
}
int BinarySearch(SSTable l,int item){
    int left=1,right=l.size;
    int mid;
    while (left<=right)
    {
        mid=(left+right)/2;
        if(l.elem[mid]==item)
            break;
        else if(l.elem[mid]>item){
            right=mid-1;
        }else{
            left=mid+1;
        }
    }
    if(l.elem[mid]==item) return mid;
    else return 0;
}

int SequentialSearchTablePrint(SSTable sst){
    for(int i=1;i<sst.size;i++){cout<<sst.elem[i]<<" ";};
    cout<<endl;
    return 0;
}

int main(){

    // random_device rd={42};
    mt19937 gen(42);
    uniform_int_distribution<int> dis(1, 100);






    SSTable sst;
    sst.size=10;
    sst.elem=(int*)malloc(sizeof(int)*(sst.size+1));
    for(int i=1;i<sst.size;i++){sst.elem[i]=dis(gen);};
    SequentialSearchTablePrint(sst);
    cout<<"SequentialSearch 74 in sst."<<SequentialSearch(sst,74)<<endl;

    for(int i=1;i<sst.size;i++){sst.elem[i]=i;};
    SequentialSearchTablePrint(sst);
    cout<<"OrderedSequentialSearch 3 in sst."<<OrderedSequentialSearch(sst,3)<<endl;
    cout<<"BinarySearch 3 in sst."<<BinarySearch(sst,3)<<endl;



    return 0;
}

树形查找

二叉排序树

建树 插入 删除
删除时两种情况

  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
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
#include"iostream"
using namespace std;    


// BST:named BinarySearchTree or BinarySortedTree 

typedef struct BinarySearchTree{
    int data;
    struct BinarySearchTree *left;
    struct BinarySearchTree *right;
} BST;

BST* BSTNewNode(int data){
    BST* node=(BST*)malloc(sizeof(BST));
    node->data=data;
    node->left=node->right=nullptr;
    return node;
}

int BSTInorder(BST *root){
    if(root==nullptr) return 0;
    BSTInorder(root->left);
    cout<<root->data<<endl;
    BSTInorder(root->right);
}

BST* BSTGetNext(BST* root){
    while (root->left!=nullptr)
    {
        root=root->left;
    }
    return root;
}
int BSTSearch(BST *root,int data,BST* item){
    BST* node=root;
    while (node)
    {
        if(node->data==data){
            *item=*node;
            return 0;
        }
        if(node->data>data){
            node=node->left;
        }else{
            node=node->right;
        }
    }
    return -1;
}
BST* BSTInsert(BST *root,int data){
    if(root==nullptr) return BSTNewNode(data);

    if(root->data>data){
        root->left=BSTInsert(root->left,data);
    }
    else if(root->data<data){
        root->right=BSTInsert(root->right,data);
    }else{
        cout<<"BST* BSTInsert(BST *root,int data):node."<<data<<" already exists"<<endl;
    }
    return root;
}

BST* BSTDelete(BST *root,int data){
    if(root==nullptr){
        return nullptr;
    }
    
    if(root->data>data){
        root->left=BSTDelete(root->left,data);
    }
    else if(root->data<data){
        root->right=BSTDelete(root->right,data);
    }
    else{
        if(root->left==nullptr&&root->right==nullptr){
            free(root);
            root=nullptr;
        }
        else if (root->left==nullptr)
        {
            BST* freenode=root;
            root=root->right;
            free(freenode);
        }
        else if (root->right==nullptr)
        {
            BST* freenode=root;
            root=root->left;
            free(freenode);
        }
        else{
            BST* nextnode=BSTGetNext(root->right);
            root->data=nextnode->data;
            root->right=BSTDelete(root->right,nextnode->data);
        }
    }
    return root;
}

int main(){

    BST* root=BSTNewNode(0);
    BSTInsert(root,3);
    BSTInsert(root,1);
    BSTInsert(root,4);
    BSTInsert(root,2);
    BSTInsert(root,5);
    BSTInorder(root);
    BST* item;
    if(BSTSearch(root,3,item)==0){
        cout<<item->data<<endl;
    }
    
    BSTDelete(root,4);
    BSTInorder(root);

    return 0;
}











平衡二叉树AVL

左右子树高度差绝对值为平衡因子，任意结点平衡因子不大于1的树为平衡二叉树。

特点：高效查询、低效插入和删除，查找稳定

插入

从插入处自底向上访问父结点，计算平衡因子直到平衡因子大于1，包括以下4种情况：

  1. 最高处为LL结点-右旋
  2. 最高处为RR结点-左旋
  3. 最高处为RL结点-先右旋后左旋
  4. 最高处为LR结点-先左旋后右旋
删除
  1. 删除叶结点时先直接删除
  2. 删除非叶结点找到前驱或后继替代然后直接删除
  3. 在删除的结点的父结点处向上判断，若结点树高-1则需回溯到祖父结点判断调整
查找

平均查找长度O(logn)

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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include"iostream"
using namespace std;

typedef struct AVLTree //Balanced Binary Tree,named as avl to commemorated researchers
{
    int data;
    int height;
    struct AVLTree *left;
    struct AVLTree *right;
}AVLT;


AVLT* AVLTNewNode(int data){
    AVLT* node=(AVLT*)malloc(sizeof(AVLT));
    node->data=data;
    node->height=1;
    node->left=node->right=nullptr;
    return node;
}
int AVLTGetHeight(AVLT* root){
    if(root==nullptr) return 0;
    return root->height;
}
int AVLTUpdateHeight(AVLT* root){
    if(root==nullptr) return 0;
    root->height=1+max(AVLTGetHeight(root->left),AVLTGetHeight(root->right));
    return 0;
}
int AVLTGetBalanceFactor(AVLT *root){
    if(root==nullptr) return 0;
    return AVLTGetHeight(root->left)-AVLTGetHeight(root->right);
}

int AVLTInorder(AVLT *root){
    if(root==nullptr) return 0;
    AVLTInorder(root->left);
    cout<<root->data<<endl;
    AVLTInorder(root->right);
}

AVLT* AVLTRotateRight(AVLT *root){
    AVLT* newnode=root->left;
    root->left=newnode->right;
    newnode->right=root;
    AVLTUpdateHeight(root);
    AVLTUpdateHeight(newnode);
    return newnode;
}
AVLT* AVLTRotateLeft(AVLT *root){
    AVLT* newnode=root->right;
    root->right=newnode->left;
    newnode->left=root;
    AVLTUpdateHeight(root);
    AVLTUpdateHeight(newnode);
    return newnode;
}

AVLT* AVLTInsert(AVLT* root,int data){

    if(root==nullptr) return AVLTNewNode(data);
    if(root->data>data){
        root->left=AVLTInsert(root->left,data);
    }
    else if (root->data<data)
    {
        root->right=AVLTInsert(root->right,data);
    }else{
        return root;
    }
    AVLTUpdateHeight(root);
    int bf=AVLTGetBalanceFactor(root);
    if(bf>1&&root->left->data>data){
        return AVLTRotateRight(root);
    }else if (bf>1&&root->left->data<data){
        root->left=AVLTRotateLeft(root->left);
        return AVLTRotateRight(root);
    }else if (bf<-1&&root->right->data<data)
    {
        return AVLTRotateLeft(root);
    }else if (bf<-1&&root->right->data>data)
    {
        root->right=AVLTRotateRight(root->right);
        return AVLTRotateLeft(root);
    }else;

    return root;
}

AVLT* AVLTGetNext(AVLT* root){
    while (root->left!=nullptr)
    {
        root=root->left;
    }
    return root;
}
AVLT* AVLTDelete(AVLT* root,int data){
    if(root==nullptr) return nullptr;
    if(root->data>data){
        root->left=AVLTDelete(root->left,data);
    }else if (root->data<data)
    {
        root->right=AVLTDelete(root->right,data);
    }
    else{
        if(root->left==nullptr&&root->right==nullptr){
            free(root);
            root=nullptr;
        }
        else if (root->left==nullptr)
        {
            AVLT* freenode=root;
            root=root->right;
            free(freenode);
        }else if (root->right==nullptr)
        {
            AVLT* freenode=root;
            root=root->left;
            free(freenode);
        }else{
            AVLT* next=AVLTGetNext(root->right);
            root->data=next->data;
            root->right=AVLTDelete(root->right,next->data);
        }
    }
    
    AVLTUpdateHeight(root);
    int bf=AVLTGetBalanceFactor(root);
    if(bf>1&&AVLTGetBalanceFactor(root->left)>=0){
        return AVLTRotateRight(root);
    }else if (bf>1&&AVLTGetBalanceFactor(root->left)<0){
        root->left=AVLTRotateLeft(root->left);
        return AVLTRotateRight(root);
    }else if (bf<-1&&AVLTGetBalanceFactor(root->right)<=0)
    {
        return AVLTRotateLeft(root);
    }else if (bf<-1&&AVLTGetBalanceFactor(root->right)>0)
    {
        root->right=AVLTRotateRight(root->right);
        return AVLTRotateLeft(root);
    }else 
        return root;
}

int main(){

    AVLT *root=AVLTNewNode(0);
    root=AVLTInsert(root,1);
    root=AVLTInsert(root,2);
    root=AVLTInsert(root,3);
    root=AVLTInsert(root,4);
    root=AVLTDelete(root,2);
    AVLTInorder(root);
    root=AVLTDelete(root,0);
    root=AVLTDelete(root,1);
    root=AVLTDelete(root,3);
    AVLTInorder(root);
    root=AVLTDelete(root,4);

    return 0;
}

红黑树

红黑树减弱了插入删除的调整条件
主要满足5个性质：

  1. 结点红或黑
  2. 根结点黑
  3. 叶结点黑（叶结点为NULL结点）
  4. 红结点不相邻（红结点父结点和子结点都是黑）
  5. 结点到任意叶结点的简单路径包含黑结点数相同 （黑高，结点最大的黑高作为树的黑高）

特点：

  1. 根结点到叶结点最长路径不大于最短路径2倍
  2. 红黑树高 $h\leq2log_2^{n+1}$ 由于树的结点比黑结点多得到
  3. 插入的都为红结点
插入
  1. 空树插入- 染黑
  2. 父结点为黑- 直接插入
  3. 父结点为红，叔红- 父、叔结点变黑，爷结点变红，继续向上修改直到根结点
  4. 父结点为红，叔黑（4种情况）：（1）父子LL：父结点与爷结点颜色交换，再右旋；（2）父子RR：父结点与爷结点颜色交换，再左旋；（3）父子LR：父子左旋后，新父结点与爷结点颜色交换，再右旋；（4）父子RL：父子右旋后，新父结点与爷结点颜色交换，再左旋；
删除

按照AVL树的删除方式转为其前驱后继删除，找到次底层结点
（删除结点无子树）

  1. 删除结点为红-直接删除
  2. 删除结点为黑，兄弟结点无子树（兄弟无子树表示两个都是叶结点为子树，那由红黑树定义兄弟也为黑）- 删除结点，兄弟变红，父变黑
  3. 删除结点为黑，兄弟结点有一个子树且为LL RR形式- 删除结点，兄弟结点子树、父结点变黑，LL右旋，RR左旋
  4. 删除结点为黑，兄弟结点有一个子树且为LR RL形式- 删除结点，兄弟结点和子树颜色交换，LR左旋，RL右旋，同3情况，继续按照3.中操作（兄弟结点子树、父结点变黑，LL右旋，RR左旋）
  5. 删除结点为黑，兄弟结点有两个子树，兄弟结点黑- 删除结点，兄弟结点和父结点颜色交换
  6. 删除结点为黑，兄弟结点有两个子树，兄弟结点红- 兄弟结点和父结点颜色交换，被删为L左旋，被删为R右旋，删除结点，当前被删结点的兄弟结点和父结点颜色交换

（删除结点一个子树）

  1. 删除结点为黑，将子树涂黑放到删除结点处

（删除结点两个子树）

  1. 找到前驱或后继替换，转为无子树和1子树情况
查找

与二叉排序树相同

B树

m阶B树为所有结点平衡因子为0的m路平衡查找，满足：

  1. 每个结点最多m棵子树，最少⌈m/2⌉棵子树，即关键字范围[⌈m/2⌉-1,m-1]
  2. 根结点若存在子树，则至少2个子树
  3. 非叶结点关键字升序
  4. 叶结点都在同一层，且不包含信息

特点：

  1. 叶结点数（查找失败）为关键字总数n+1
  2. n个关键字的m阶B树高度范围:$[\log_m^{n+1},\log_{⌈m/2⌉}^{(n+1)/2}+1]$
    关键字个数应该小于等于所有结点都有m-1个关键字总数
    $n\leq(m-1)(\sum_{i=0}^{h-1}{m^i})$ => $h\geq\log_m^{n+1}$
    由于B树根结点最少2个子树，可用：关键字数+1大于等于最少叶结点数（查找失败）
    $n+1\geq2(⌈m/2⌉)^{h-1}$ => $h\leq\log_{⌈m/2⌉}^{(n+1)/2}+1$
  3. B树结点数不包括叶子结点
查找

查找关键字，如果相等则返回，不相等找到对应区间子树继续查找，直到为叶结点表示查找失败

插入

插入位置会搜索到非叶结点底层

  1. 插入前关键字数小于m-1-直接插入
  2. 插入前关键字数等于m-1-从⌈m/2⌉处分裂出左右树，将⌈m/2⌉插入到父结点关键字，若父结点溢出继续向上分裂。直到到根结点，根结点分裂后会导致树高+1
删除

B树的删除操作不唯一，当删除的不是最底层结点时，将其替换为前驱或后继，一直替换到非叶结点最底层，转换为非叶结点底层关键字删除操作

  1. 当结点关键字数≥⌈m/2⌉，直接删除
  2. 当结点关键字数==⌈m/2⌉-1，兄弟关键字数≥⌈m/2⌉，借一个实现平衡
  3. 当结点关键字数==⌈m/2⌉-1，兄弟关键字数==⌈m/2⌉-1，将这两个兄弟结点和对应的父结点关键字合并，并并删除该父关键字，同时修正索引结点，直到根结点

B+树

m阶B+树满足：

  1. 关键字范围[⌈m/2⌉,m]
  2. 根结点若存在子树，则至少2个子树，其它结点至少⌈m/2⌉+1棵子树
  3. 非叶结点关键字是其子树中最大(或最小)的关键字，一般选右子树最小（下面默认）
  4. 叶结点包含全部关键字和数据指针，所有叶结点关键字顺序排序且相邻叶结点是链接的
查找

查找关键字，一直查找到叶结点，叶结点没有查找失败

插入

插入位置为叶结点

  1. 插入前关键字数< m- 直接插入
  2. 插入前关键字数=m，索引父结点< m- 从⌈m/2⌉+1处分裂出左右树（⌈m/2⌉+1在左表示关键字最大，在右表示关键字最小），同时将⌈m/2⌉+1插入到父结点关键字
  3. 插入前关键字数=m，索引父结点= m- 从⌈m/2⌉+1处分裂出左右树，同时将⌈m/2⌉+1插入到父结点关键字,由于父结点溢出继续向上分裂。直到到根结点，根结点分裂后会导致树高+1
  4. 旋转：B+树为了减少结构操作，当插入前关键字数=m，但兄弟结点有空，将索引的关键字放到兄弟结点，腾出一个位置插入。
删除
  1. 叶结点关键字数> ⌈m/2⌉，直接删除
  2. 叶结点关键字数= ⌈m/2⌉，兄弟关键字数> ⌈m/2⌉，借一个关键字过来，同时索引的关键字要更新
  3. 叶结点关键字数= ⌈m/2⌉，兄弟关键字数= ⌈m/2⌉，将这两个兄弟结点和对应的父结点关键字合并，并并删除该父关键字，同时修正索引结点，直到根结点

数列查找

散列表查找

散列表是通过关键字直接获取元素地址进行查找
散列函数 散列表 冲突 二次堆积 查找成功 查找失败

散列函数方法
  1. 直接定址 addr=a*key+1 唯一不冲突
  2. 平方取中
  3. 数值分析
  4. 除留余数
  5. 随机数
  6. 折叠法
冲突处理

  1. 开放地址法
    当冲突时使用定义的冲突处理计算出下一个地址，直到不冲突

    $Hi=(H(key)+di)%m$
    其中di为增量序列，可以选择1.线性探测法 2.平方探测法 3.双散列法

  2. 链表法
    散列表不直接存储数据，使用链表，同义词会形成一个链表

性能分析

查找成功ASL
查找失败ASL
装填因子α=表中数据数/散列表长度，α越小越不容易冲突

排序

内部排序：数据在内存中

插入排序

直接插入排序

折半插入排序

希尔排序

交换排序

冒泡排序

快速排序

选择排序

简单选择

堆排序

归并排序

基数排序

外部排序

归并排序

二路归并(增加输入缓冲区数量即多路归并)

  1. 将数据划分r块(保证至少内存能存放3块)
  2. 进行r/2次二路归并排序,剩余r/2块: 每次读取两块(并对每块内部排序),依次选择两块中最小值放入缓冲区,缓冲区满则写入数据.当存在内存块读取完,则直接写入剩下块数据.此时完成一次归并
  3. 第二次归并块数减半,但块长加倍,单块无法全部读入.进行r/4次二路归并排序: 每次先读取两块的部分数据,缓冲区满了则写入,内存块读取完
    了从硬盘块继续读入,知道全部读取完,完成排序.
  4. 一直归并直到硬盘中只剩一块,完成外部排序.

多路归并败者树

针对多路归并算法,提出的败者树:每个内存块排序后的第一个数据作为树的叶子结点,比较两个子树结点大小,大的失败,记录到父结点,小的继续向上比较.一直到根结点,平均比较logk次(k路归并)

选择置换排序

  1. 从硬盘中读取数据,找到最小值输出,标记MIN.
  2. 继续读入数据,找到最小值.若最小值>MIN:输出,并更新MIN为当前最小值.如果最小值< MIN,标记当前最小值不可输出.选择次小值比较输出.
  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
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include"iostream"
#include"random"
using namespace std;


template<typename T>
struct SortData
{
    int size;
    T* data;
};

typedef SortData<int> SD;

SD* RandomData(int size,int rd=42){
    default_random_engine e;
    uniform_int_distribution<int> u(1,100);
    e.seed(rd);

    SD* d=(SD*)malloc(sizeof(SD));
    d->data=(int*)malloc(sizeof(int)*size);
    d->size=size;
    for(int i=0;i<d->size;i++) d->data[i]=u(e);
    return d;
}
int DataPrint(SD* d){
    for(int i=0;i<d->size;i++) cout<<d->data[i]<<" ";
    cout<<endl;
    return 0;
}

// insertion

int InsertionSort(SD* d){
    int i,j,sentinel;
    for(int i=2;i<d->size;i++){
        sentinel=d->data[i];
        for(j=i-1;d->data[j]>sentinel;j--) d->data[j+1]=d->data[j];
        d->data[j+1]=sentinel;
    }
    return 0;
}

int BinaryInsertionSort(SD* d){
    int i,j,sentinel;
    for(int i=2;i<d->size;i++){
        sentinel=d->data[i];
        int low=0,high=i-1,mid;
        while (low<=high)
        {
            mid=(low+high)/2;
            if(d->data[mid]>sentinel) high=mid-1;
            else low=mid+1; 
        }

        for(j=i-1;j>=high+1;j--) d->data[j+1]=d->data[j];
        d->data[high+1]=sentinel;
    }
    return 0;
}

int ShellSort(SD *d){
    int sentinel,i,j;
    for(int gap=d->size/2;gap>=1;gap/=2){
        for(i=gap+1;i<d->size;i++){
            if(d->data[i]<d->data[i-gap]){
                sentinel=d->data[i];
                for(j=i-gap;j>0&&d->data[j]>sentinel;j-=gap){
                    d->data[j+gap]=d->data[j];
                }
                d->data[j+gap]=sentinel;
            }
        }
    }
}

// swap sort

int BubbleSort(SD *d){
    for(int i=0;i<d->size;i++){
        int ordered=1;
        for(int j=d->size-1;j>i;j--){
            if(d->data[j]<d->data[j-1]){
                d->data[j]=d->data[j]^d->data[j-1];
                d->data[j-1]=d->data[j]^d->data[j-1];
                d->data[j]=d->data[j]^d->data[j-1];
                ordered=0;
            }
        }
        if(ordered) return 0;
    }
}

int QuickSort_partsort(SD *d,int low,int high){
    int pivot=d->data[low];
    while (low<high)
    {
        while(low<high&&d->data[high]>=pivot) high--;
        d->data[low]=d->data[high];
        while (low<high&&d->data[low]<=pivot) low++;
        d->data[high]=d->data[low];
    }
    d->data[low]=pivot;
    return low;    


    return pivot;
}
int QuickSort_recursion(SD *d,int low=-1,int high=-1){
    if(low==-1&&high==-1){
        low=0;high=d->size-1;
    }
    if(low<high){
        int pivot=low;
        pivot=QuickSort_partsort(d,low,high);
        QuickSort_recursion(d,low,pivot-1);
        QuickSort_recursion(d,pivot+1,high);
    }
}

// selection
int SelectionSort(SD *d){
    int min,i,j;
    for(i=0;i<d->size;i++){
        min=i;
        for(j=i+1;j<d->size;j++){
            if(d->data[j]<d->data[min]) min=j;
        }
        if(min!=i){
            d->data[min]=d->data[min]^d->data[i];
            d->data[i]=d->data[min]^d->data[i];
            d->data[min]=d->data[min]^d->data[i];
        }
    }
    return 0;
}

int HeapSortAdjust(SD *d,int k,int size){
    // k in [1,size],drop 0 default becauseof the special 0;
    int sentinel=d->data[k-1],i;
    for(i=2*k;i<=size;i*=2){
        if(i<size&&d->data[i-1]<d->data[i]) i++;
        if(d->data[i-1]<=sentinel) break;
        else{
            d->data[k-1]=d->data[i-1];
            k=i;
        }
    }
    d->data[k-1]=sentinel;
}
int HeapSortBuild(SD *d,int size){
    for(int i=d->size/2;i>0;i--){
        HeapSortAdjust(d,i,d->size);
        // if(i==4){
        //     cout<<123<<endl;
        //     break;
        // }
    }
    return 0;
}
int HeapSort(SD *d){
    HeapSortBuild(d,d->size);
    for(int i=d->size;i>1;i--){
        d->data[i-1]=d->data[i-1]^d->data[0];
        d->data[0]=d->data[i-1]^d->data[0];
        d->data[i-1]=d->data[i-1]^d->data[0];
        HeapSortAdjust(d,1,i-1);
    }
    return 0;
}

// merge
int Mergemerge(SD* d,int* arr,int low,int mid,int high){
    int i,j,k;
    for(k=low;k<=high;k++) arr[k]=d->data[k];
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(arr[i]<=arr[j]) d->data[k]=arr[i++];
        else d->data[k]=arr[j++];
    }
    while (i<=mid){
        d->data[k++]=arr[i++];
    }
    while (j<=high)
    {
        d->data[k++]=arr[j++];
    }
    return 0;
}

int MergeSort(SD *d,int* arr,int low=-1,int high=-1){
    if(low==-1&&high==-1){
        low=0;high=d->size-1;
    }
    if(low<high){
        int mid=(low+high)/2;
        MergeSort(d,arr,low,mid);
        MergeSort(d,arr,mid+1,high);
        Mergemerge(d,arr,low,mid,high);
    }
    return 0;
}


// 



int main(){
    SD* d=RandomData(10);
    DataPrint(d);
    
    // InsertionSort
    // InsertionSort(d);
    // BinaryInsertionSort(d);
    // ShellSort(d);
    // BubbleSort(d);
    // QuickSort_recursion(d);
    // SelectionSort(d);
    // HeapSort(d);
    
    int* arr=(int*)malloc(sizeof(int)*10);
    MergeSort(d,arr);
    DataPrint(d);


    return 0;
}