链表单链表基本运算link.h文件1 typedef int data_t; 2 3 typedef struct node{ 4 data_t data; 5 struct node* next; 6 }linknode,*linklist; 7 8 linklist list_create(); 9 int list_tail_insert(linklist H,data_t value); 10 int list_show(linklist H); 11 linklist list_get(linklist H,int pos);int list_insert(linklist H,data_t value,int pos); 12 int list_delete(linklist H,int pos); 13 int list_free(linklist H); 14主函数 main.c1 #includestdio.h 2 #includelink.h 3 void test_get(); 4 5 int main(int argc,const char* argv[]) 6 { 7 linklist p; 8 linklist H; 9 int value; 10 11 Hlist_create(); 12 if(HNULL) 13 return -1; 14 15 printf(input:); 16 while(1) 17 { 18 scanf(%d,value); 19 if(value-1)//注意这里是判断等于别写成赋值 20 break; 21 list_tail_insert(H,value); 22 printf(input:); 23 } 24 25 list_show(H); 26 27 list_insert(H,8,4); 28 list_show(H); 29 30 list_delete(H,5); 31 list_show(H); 32 33 list_free(H); 34 return 0; 35 } 36 void test_get(){ 37 38 linklist p; 39 linklist H; 40 int value; 41 42 Hlist_create(); 43 if(HNULL) 44 return -1; 45 46 printf(input:); 47 while(1) 48 { 49 scanf(%d,value); 50 if(value-1)//注意这里是判断等于别写成赋值 51 break; 52 list_tail_insert(H,value); 53 printf(input:); 54 } 55 56 list_show(H); 57 58 list_insert(H,100,4); 59 if(p!NULL)//判断 避免段错误 60 printf(value%d\n,p-data); 61 return 0; 62 } ~ ~链表的创建linklist list_create(){ 5 6 linklist H; 7 H(linklist)malloc(sizeof(linknode)); 8 if(HNULL) 9 { 10 printf(malloc failed\n); 11 return H;//此时H为NULL 12 } 13 //赋值初始值 14 H-data0; 15 H-nextNULL; 16 17 return H; 18 }链表的插入尾插20 int list_tail_insert(linklist H,data_t value){ 21 22 linklist p; 23 linklist q; 24 25 //检查链表是否创建成功 26 if(HNULL){ 27 return -1; 28 } 29 p(linklist)malloc(sizeof(linknode)); 30 if(pNULL) 31 { 32 printf(malloc failed\n); 33 return -1; 34 } 35 p-datavalue; 36 p-nextNULL; 37 38 qH; 39 while(q-next!NULL){ 40 qq-next; 41 } 42 43 q-nextp; 44 45 return 0; 46 }链表的打印47 48 int list_show(linklist H){ 49 linklist p; 50 if(HNULL){ 51 52 printf(H is null\n); 53 return -1; 54 } 55 pH; 56 57 while(p-next!NULL){ 58 printf(%d ,p-next-data); 59 pp-next; 60 } 61 62 puts(); 63 return 0; 64 }链表的位置上数值的获取linklist list_get(linklist H,int pos) 66 { 67 int i; 68 linklist p; 69 if(HNULL){ 70 71 printf(H is null); 72 return NULL; 73 } 74 75 if(pos-1){ 76 return H; 77 } 78 79 pH; 80 i-1; 81 while(ipos){ 82 pp-next; 83 if(pNULL){ 84 printf(pos is invalid\n); 85 return NULL; 86 } 87 i; 88 } 89 return p; 90 }任意位置上数值的插入int list_insert(linklist H,data_t value,int pos ){ 93 linklist p; 94 linklist q; 95 // locate node pos-1 96 plist_get(H,pos-1); 97 98 //new node q 99 if((q(linklist)malloc(sizeof(linknode)))NULL){ 100 printf(malloc failed\n); 101 return -1; 102 } 103 q-datavalue; 104 q-nextNULL; 105 // 插入数据 106 q-nextp-next; 107 p-nextq; 108 109 return 0; 110 } 111链表元素的删除int list_delete(linklist H,int pos){ 113 114 linklist p; 115 //存放要删除的节点并且释放 116 linklist q; 117 //判断该链表是否为空表 118 if(HNULL){ 119 printf(H is null\n); 120 return -1; 121 } 122 123 124 plist_get(H,pos-1); 125 126 //判断找到的位置是否为空 127 if(pNULL) 128 return -1; 129 if(p-nextNULL){ 130 printf(delete pos is invalid\n); 131 return -1;} 132 133 134 qp-next; 135 p-nextp-next-next; 136 free(q);//释放 137 return 0; 138 }链表的释放int list_free(linklist H){ 140 linklist p; 141 142 if(HNULL) 143 return NULL; 144 145 pH; 146 147 printf(free); 148 while(H!NULL){ 149 pH; 150 151 printf(%d ,p-data); 152 HH-next; 153 154 free(p); 155 } 156 157 puts();//换行符要放在最后 158 159 return 0; 160 }有序链表的合并#includestdio.h 2 #includelink.h 4 5 int main(int argc,const char* argv[]) 6 { 7 linklist H1, H2; 8 int a[]{1,4,6,8,10}; 9 int b[]{2,4,16,18,30}; 10 int i; 11 H1list_create(); 12 if(H1NULL) 13 return; 14 H2list_create(); 15 if(H2NULL) 16 return; 17 18 for(i0;isizeof(a)/sizeof(int);i) 19 { 20 list_tail_insert(H1,a[i]); 21 } 22 for(i0;isizeof(b)/sizeof(int);i) 23 { 24 list_tail_insert(H2,b[i]); 25 } 26 list_show(H1); 27 list_show(H2); 28 29 list_merge(H1,H2); 30 list_show(H1); 31 list_show(H2); 32 return 0; 33 }函数2 int list_merge(linklist H1,linklist H2){ 163 linklist p,q,r; 164 if(H1NULL||H2NULL){ 165 printf(H1||H2 is NULL\n); 166 return -1; 167 } 168 pH1-next; 169 qH2-next; 170 rH1; 171 H1-nextNULL; 172 H2-nextNULL; 173 174 while(pq){ 175 176 if(p-dataq-data){ 177 r-nextp; 178 pp-next; 179 180 rr-next; 181 r-nextNULL; 182 } 183 else 184 { 185 r-nextq; 186 qq-next; 187 188 rr-next; 189 r-nextNULL; 190 } 191 } 192 193 194 return 0; 195 }链表的反转int list_reverse(linklist H){ 197 linklist p,q; 198 if(HNULL){ 199 printf(H is NULL\n); 200 return -1; 201 } 202 if(H-nextNULL||H-next-nextNULL){ 203 return 0;// 空表或者只有一个元素 就直接返回 204 } 205 206 pH-next-next; 207 H-next-nextNULL; 208 while(p!NULL){ 209 qp; 210 pp-next; 211 212 q-nextH-next; 213 H-nextq; 214 } 215 return 0; 216 }链表相邻两个节点最大值linklist list_adjmax(linklist H){ 219 int sum; 220 linklist q,r,p; 221 if(HNULL) 222 { 223 printf(H is null\n); 224 return NULL;//注意 返回类类型是指针 225 } 226 if(H-nextNULL||H-next-nextNULL||H-next-next-nextNULL){ 227 return H; 228 } 229 qH-next; 230 pH-next-next; 231 rq; 232 sump-dataq-data; 233 234 while(p-next!NULL){ 235 pp-next; 236 qq-next; 237 if(sump-dataq-data){ 238 sumq-datap-data; 239 rq; 240 } 241 } 242 return r; 243 }栈顺序栈1 typedef int data_t; 2 3 typedef struct { 4 data_t *data; 5 int maxlen; 6 int top; 7 }sqstack; 8 sqstack* stack_create(int len); 9 int stack_push(sqstack*s,data_t value); 10 data_t stack_pop(sqstack*s); 11 data_t stack_top(sqstack*s); 12 int stack_free(sqstack*s); 13 int stack_clear(sqstack*s); 14 int stack_empty(sqstack*s); 15 int stack_full(sqstack*s);1 #includestdio.h 2 #includesqstack.h 3 #includestring.h 4 #includestdlib.h 5 sqstack* stack_create(int len){ 6 sqstack* s; 7 if((s(sqstack*)malloc(sizeof(sqstack)))NULL){ 8 printf(malloc sqstack failed\n); 9 return NULL; 10 } 11 12 if((s-data(data_t*)malloc(len*sizeof(data_t)))NULL){ 13 printf(malloc data dailed\n); 14 return NULL; 15 } 16 memset(s-data,0,len*sizeof(data_t)); 17 s-maxlenlen; 18 s-top-1; 19 20 return s; 21 } 22 int stack_push(sqstack*s,data_t value){ 23 if(sNULL){ 24 printf(s is null\n); 25 return -1; 26 } 27 28 if(s-tops-maxlen-1){ 29 printf(stack is full\n); 30 return -1; 31 } 32 s-top; 33 s-data[s-top]value; 34 35 return 0; 36 } 37 38 data_t stack_pop(sqstack*s){ 39 s-top--; 40 return (s-data[s-top1]); 41 } 42 data_t stack_top(sqstack*s){ 43 return (s-data[s-top]); 44 } 45 int stack_free(sqstack*s){ 46 if(sNULL){ 47 printf(s is NULL\n); 48 return -1; 49 } 50 if(s-data!NULL){ 51 free(s-data); 52 free(s); 53 return 0; 54 } 55 } 56 int stack_clear(sqstack*s){ 57 printf(s is null\n); 58 return -1; 59 } 60 int stack_empty(sqstack*s){ 61 if(sNULL){ 62 printf(s is NULL \n); 63 return -1; 64 } 65 return (s-top-1?1:0); 66 } 67 int stack_full(sqstack*s){ 68 printf(s is NULL\n); 69 return -1; 70 71 return (s-tops-maxlen-1?1:0); 72 }1 #includestdio.h 2 #includesqstack.h 3 #includestdlib.h 4 int main(int argc,const char* argv[]){ 5 sqstack *s; 6 sstack_create(100); 7 if(sNULL) 8 return -1; 9 10 stack_push(s,10); 11 stack_push(s,20); 12 stack_push(s,30); 13 stack_push(s,40); 14 while(!stack_empty(s)){ 15 printf(pop %d\n,stack_pop(s)); 16 } 17 free(s); 18 return 0; 19 }链式栈入栈typedef int data_t; typedef struct node { data_t data; struct node *next; }listnode, *linkstack; linkstack stack_create(); int stack_push(linkstack s, data_t value); data_t stack_pop(linkstack s); int stack_empty(linkstack s); data_t stack_top(linkstack s); linkstack stack_free(linkstack s);#include stdio.h #include stdlib.h #include linkstack.h linkstack stack_create() { linkstack s; s (linkstack)malloc(sizeof(listnode)); if (s NULL) { printf(malloc failed\n); return NULL; } s-data 0; s-next NULL; return s; } int stack_push(linkstack s, data_t value) { linkstack p; if (s NULL) { printf(s is NULL\n); return -1; } p (linkstack)malloc(sizeof(listnode)); if (p NULL) { printf(malloc failed\n); return -1; } p-data value; //p-next NULL; p-next s-next; s-next p; return 0; } data_t stack_pop(linkstack s) { linkstack p; data_t t; p s-next; s-next p-next; t p-data; free(p); p NULL; return t; } int stack_empty(linkstack s) { if (s NULL) { printf(s is NULL\n); return -1; } return (s-next NULL ? 1 : 0); } data_t stack_top(linkstack s) { return (s-next-data); } linkstack stack_free(linkstack s) { linkstack p; if (s NULL) { printf(s is NULL\n); return NULL; } while (s ! NULL) { p s; s s-next; printf(free:%d\n, p-data); free(p); } return NULL; }#include stdio.h #include stdlib.h #include linkstack.h int main(int argc, const char *argv[]) { linkstack s; s stack_create(); if (s NULL) return -1; stack_push(s, 10); stack_push(s, 20); stack_push(s, 30); stack_push(s, 40); #if 0 while (!stack_empty(s)) { printf(pop:%d\n, stack_pop(s)); } #endif s stack_free(s); return 0; }队列typedef int datatype; #define N 128 typedef struct { datatype data[N]; int front; int rear; }sequeue; sequeue * queue_create(); int enqueue(sequeue *sq, datatype x); datatype dequeue(sequeue *sq); int queue_empty(sequeue *sq); int queue_full(sequeue *sq); int queue_clear(sequeue *sq); sequeue * queue_free(sequeue *sq);#include stdio.h #include stdlib.h #include string.h #include sequeue.h sequeue * queue_create() { sequeue *sq; if ((sq (sequeue *)malloc(sizeof(sequeue))) NULL) { printf(malloc failed\n); return NULL; } memset(sq-data, 0, sizeof(sq-data)); sq-front sq-rear 0; return sq; } int enqueue(sequeue *sq, datatype x) { if (sq NULL) { printf(sq is NULL\n); return -1; } if ((sq-rear 1) % N sq-front) { printf(sequeue is full\n); return -1; } sq-data[sq-rear] x; sq-rear (sq-rear 1) % N; return 0; } datatype dequeue(sequeue *sq) { datatype ret; ret sq-data[sq-front]; sq-front (sq-front 1) % N; return ret; } int queue_empty(sequeue *sq) { if (sq NULL) { printf(sq is NULL\n); return -1; } return (sq-front sq-rear ? 1 : 0); } int queue_full(sequeue *sq) { if (sq NULL) { printf(sq is NULL\n); return -1; } if ((sq-rear 1) % N sq-front) { return 1; } else { return 0; } } int queue_clear(sequeue *sq) { if (sq NULL) { printf(sq is NULL\n); return -1; } sq-front sq-rear 0; return 0; } sequeue * queue_free(sequeue *sq) { if (sq NULL) { printf(sq is NULL\n); return NULL; } free(sq); sq NULL; return NULL; }#include stdio.h #include sequeue.h int main(int argc, const char *argv[]) { sequeue *sq; if ((sq queue_create()) NULL) { return -1; } enqueue(sq, 10); enqueue(sq, 100); enqueue(sq, 1000); while (!queue_empty(sq)) { printf(dequeue:%d\n, dequeue(sq)); } queue_free(sq); return 0; }链式队列#include stdio.h #include stdlib.h #include linkqueue.h linkqueue * queue_create() { linkqueue *lq; if ((lq (linkqueue *)malloc(sizeof(linkqueue))) NULL) { printf(malloc linkqueue failed\n); return NULL; } lq-front lq-rear (linklist)malloc(sizeof(listnode)); if (lq-front NULL) { printf(malloc node failed\n); return NULL; } lq-front-data 0; lq-front-next NULL; return lq; } int enqueue(linkqueue *lq, datatype x) { linklist p; if (lq NULL) { printf(lq is NULL\n); return -1; } if ((p (linklist)malloc(sizeof(listnode))) NULL) { printf(malloc node failed\n); return -1; } p-data x; p-next NULL; lq-rear-next p; lq-rear p; return 0; } datatype dequeue(linkqueue *lq) { linklist p; if (lq NULL) { printf(lq is NULL\n); return -1; } p lq-front; lq-front p-next; free(p); p NULL; return (lq-front-data); } int queue_empty(linkqueue *lq) { if (lq NULL) { printf(lq is NULL\n); return -1; } return (lq-front lq-rear ? 1 : 0); } int queue_clear(linkqueue *lq) { linklist p; if (lq NULL) { printf(lq is NULL\n); return -1; } while (lq-front-next) { p lq-front; lq-front p-next; printf(clear free:%d\n, p-data); free(p); p NULL; } return 0; } linkqueue * queue_free(linkqueue *lq) { linklist p; if (lq NULL) { printf(lq is NULL\n); return NULL; } while (lq-front) { p lq-front; lq-front p-next; printf(free:%d\n, p-data); free(p); } free(lq); lq NULL; return NULL; }typedef int datatype; typedef struct node { datatype data; struct node *next; }listnode , *linklist; typedef struct { linklist front; linklist rear; }linkqueue; linkqueue * queue_create(); int enqueue(linkqueue *lq, datatype x); datatype dequeue(linkqueue *lq); int queue_empty(linkqueue *lq); int queue_clear(linkqueue *lq); linkqueue * queue_free(linkqueue *lq);#include stdio.h #include linkqueue.h int main(int argc, const char *argv[]) { linkqueue *lq; lq queue_create(); if (lq NULL) return -1; enqueue(lq, 10); enqueue(lq, 20); enqueue(lq, 30); enqueue(lq, 40); //while (!queue_empty(lq)) { //printf(dequeue:%d\n, dequeue(lq)); //} queue_clear(lq); lq queue_free(lq); enqueue(lq, 50); return 0; }查找哈希查找法1 #ifndef _HASH_ 2 #define _HASH_ 3 4 typedef int datatype; 5 #define N 20 6 typedef struct node{ 7 datatype key; 8 datatype value; 9 struct node* next; 10 }listnode,*linklist; 11 12 typedef struct{ 13 listnode data[N]; 14 }hash; 15 16 hash* hash_create(); 17 int hash_insert(hash*HT,datatype key); 18 linklist hash_search(hash*HT,datatype key); 19 #endif1 #includestdio.h 2 #includestdlib.h 3 #includehash.h 4 5 hash* hash_create(){ 6 hash*HT; 7 if((HT(hash*)malloc(sizeof(hash)))NULL){ 8 printf(malloc failed\n); 9 return NULL; 10 } 11 memset(HT,0,sizeof(hash)); 12 13 return HT; 14 } 15 16 int hash_insert(hash*HT,datatype key){ 17 linklist q,p; 18 if(HTNULL){ 19 printf(Ht is NULL\n); 20 return -1; 21 } 22 23 if((p(linklist)malloc(sizeof(listnode)))NULL){ 24 printf(malloc failed\n); 25 return -1; 26 } 27 28 p-keykey; 29 p-valuekey%N; 30 p-nextNULL; 31 32 q(HT-data[key%N]); 33 34 while(q-nextq-next-keyp-key){ 35 qq-next; 36 } 37 p-nextq-next; 38 q-nextp; 39 40 return 0; 41 } 42 43 linklist hash_search(hash *HT,datatype key){ 44 linklist p; 45 if(HTNULL){ 46 printf(HT is NULL\n); 47 return -1; 48 } 49 p(HT-data[key%N]); 50 51 while(p-nextp-next-key!key){ 52 pp-next; 53 } 54 55 if(p-nextNULL){ 56 return NULL; 57 }else{ 58 printf(found %d\n,key); 59 return p-next; 60 } 61 }1 #includestdio.h 2 #includestdlib.h 3 #includehash.h 4 int main(int argc,const char* argv[]) 5 { 6 hash* HT; 7 linklist r; 8 int key; 9 int data[]{23,45,67,12,41,8,3,10}; 10 int i; 11 if((HThash_create())NULL){ 12 13 return -1; 14 } 15 for(i0;isizeof(data)/sizeof(int);i){ 16 hash_insert(HT,data[i]); 17 } 18 printf(input:); 19 scanf(%d,key); 20 r hash_search(HT,key); 21 if(rNULL) 22 printf(not found\n); 23 else 24 printf(found: %d %d\n,key%N,r-key); 25 return 0; 26 } 27排序快速排序#include stdio.h #include stdlib.h #define N 15 int partion(int *data, int low, int high); int quick_sort(int *data, int low, int high); int compare(const void *p1, const void *p2); int main(int argc, const char *argv[]) { int data[N] {0}; int i; srandom(10); for (i 0; i N; i) { data[i] random() % 100; } for (i 0; i N; i) { printf(%d , data[i]); } puts(); //quick_sort(data, 0, N-1); qsort(data, N, sizeof(int), compare); for (i 0; i N; i) { printf(%d , data[i]); } puts(); return 0; } int partion(int *data, int low, int high) { int temp data[low]; while (low high) { while (low high temp data[high]) { high--; } data[low] data[high]; while (low high temp data[low]){ low; } data[high] data[low]; } data[low] temp; return low; } int quick_sort(int *data, int low, int high) { int t; if (data NULL) { return -1; } if (low high) return 0; t partion(data, low, high); quick_sort(data, low, t-1); quick_sort(data, t1, high); return 0; } int compare(const void *p1, const void *p2) { return (*(const int *)p1 - *(const int *)p2); }快速排序
数据结构重点
链表单链表基本运算link.h文件1 typedef int data_t; 2 3 typedef struct node{ 4 data_t data; 5 struct node* next; 6 }linknode,*linklist; 7 8 linklist list_create(); 9 int list_tail_insert(linklist H,data_t value); 10 int list_show(linklist H); 11 linklist list_get(linklist H,int pos);int list_insert(linklist H,data_t value,int pos); 12 int list_delete(linklist H,int pos); 13 int list_free(linklist H); 14主函数 main.c1 #includestdio.h 2 #includelink.h 3 void test_get(); 4 5 int main(int argc,const char* argv[]) 6 { 7 linklist p; 8 linklist H; 9 int value; 10 11 Hlist_create(); 12 if(HNULL) 13 return -1; 14 15 printf(input:); 16 while(1) 17 { 18 scanf(%d,value); 19 if(value-1)//注意这里是判断等于别写成赋值 20 break; 21 list_tail_insert(H,value); 22 printf(input:); 23 } 24 25 list_show(H); 26 27 list_insert(H,8,4); 28 list_show(H); 29 30 list_delete(H,5); 31 list_show(H); 32 33 list_free(H); 34 return 0; 35 } 36 void test_get(){ 37 38 linklist p; 39 linklist H; 40 int value; 41 42 Hlist_create(); 43 if(HNULL) 44 return -1; 45 46 printf(input:); 47 while(1) 48 { 49 scanf(%d,value); 50 if(value-1)//注意这里是判断等于别写成赋值 51 break; 52 list_tail_insert(H,value); 53 printf(input:); 54 } 55 56 list_show(H); 57 58 list_insert(H,100,4); 59 if(p!NULL)//判断 避免段错误 60 printf(value%d\n,p-data); 61 return 0; 62 } ~ ~链表的创建linklist list_create(){ 5 6 linklist H; 7 H(linklist)malloc(sizeof(linknode)); 8 if(HNULL) 9 { 10 printf(malloc failed\n); 11 return H;//此时H为NULL 12 } 13 //赋值初始值 14 H-data0; 15 H-nextNULL; 16 17 return H; 18 }链表的插入尾插20 int list_tail_insert(linklist H,data_t value){ 21 22 linklist p; 23 linklist q; 24 25 //检查链表是否创建成功 26 if(HNULL){ 27 return -1; 28 } 29 p(linklist)malloc(sizeof(linknode)); 30 if(pNULL) 31 { 32 printf(malloc failed\n); 33 return -1; 34 } 35 p-datavalue; 36 p-nextNULL; 37 38 qH; 39 while(q-next!NULL){ 40 qq-next; 41 } 42 43 q-nextp; 44 45 return 0; 46 }链表的打印47 48 int list_show(linklist H){ 49 linklist p; 50 if(HNULL){ 51 52 printf(H is null\n); 53 return -1; 54 } 55 pH; 56 57 while(p-next!NULL){ 58 printf(%d ,p-next-data); 59 pp-next; 60 } 61 62 puts(); 63 return 0; 64 }链表的位置上数值的获取linklist list_get(linklist H,int pos) 66 { 67 int i; 68 linklist p; 69 if(HNULL){ 70 71 printf(H is null); 72 return NULL; 73 } 74 75 if(pos-1){ 76 return H; 77 } 78 79 pH; 80 i-1; 81 while(ipos){ 82 pp-next; 83 if(pNULL){ 84 printf(pos is invalid\n); 85 return NULL; 86 } 87 i; 88 } 89 return p; 90 }任意位置上数值的插入int list_insert(linklist H,data_t value,int pos ){ 93 linklist p; 94 linklist q; 95 // locate node pos-1 96 plist_get(H,pos-1); 97 98 //new node q 99 if((q(linklist)malloc(sizeof(linknode)))NULL){ 100 printf(malloc failed\n); 101 return -1; 102 } 103 q-datavalue; 104 q-nextNULL; 105 // 插入数据 106 q-nextp-next; 107 p-nextq; 108 109 return 0; 110 } 111链表元素的删除int list_delete(linklist H,int pos){ 113 114 linklist p; 115 //存放要删除的节点并且释放 116 linklist q; 117 //判断该链表是否为空表 118 if(HNULL){ 119 printf(H is null\n); 120 return -1; 121 } 122 123 124 plist_get(H,pos-1); 125 126 //判断找到的位置是否为空 127 if(pNULL) 128 return -1; 129 if(p-nextNULL){ 130 printf(delete pos is invalid\n); 131 return -1;} 132 133 134 qp-next; 135 p-nextp-next-next; 136 free(q);//释放 137 return 0; 138 }链表的释放int list_free(linklist H){ 140 linklist p; 141 142 if(HNULL) 143 return NULL; 144 145 pH; 146 147 printf(free); 148 while(H!NULL){ 149 pH; 150 151 printf(%d ,p-data); 152 HH-next; 153 154 free(p); 155 } 156 157 puts();//换行符要放在最后 158 159 return 0; 160 }有序链表的合并#includestdio.h 2 #includelink.h 4 5 int main(int argc,const char* argv[]) 6 { 7 linklist H1, H2; 8 int a[]{1,4,6,8,10}; 9 int b[]{2,4,16,18,30}; 10 int i; 11 H1list_create(); 12 if(H1NULL) 13 return; 14 H2list_create(); 15 if(H2NULL) 16 return; 17 18 for(i0;isizeof(a)/sizeof(int);i) 19 { 20 list_tail_insert(H1,a[i]); 21 } 22 for(i0;isizeof(b)/sizeof(int);i) 23 { 24 list_tail_insert(H2,b[i]); 25 } 26 list_show(H1); 27 list_show(H2); 28 29 list_merge(H1,H2); 30 list_show(H1); 31 list_show(H2); 32 return 0; 33 }函数2 int list_merge(linklist H1,linklist H2){ 163 linklist p,q,r; 164 if(H1NULL||H2NULL){ 165 printf(H1||H2 is NULL\n); 166 return -1; 167 } 168 pH1-next; 169 qH2-next; 170 rH1; 171 H1-nextNULL; 172 H2-nextNULL; 173 174 while(pq){ 175 176 if(p-dataq-data){ 177 r-nextp; 178 pp-next; 179 180 rr-next; 181 r-nextNULL; 182 } 183 else 184 { 185 r-nextq; 186 qq-next; 187 188 rr-next; 189 r-nextNULL; 190 } 191 } 192 193 194 return 0; 195 }链表的反转int list_reverse(linklist H){ 197 linklist p,q; 198 if(HNULL){ 199 printf(H is NULL\n); 200 return -1; 201 } 202 if(H-nextNULL||H-next-nextNULL){ 203 return 0;// 空表或者只有一个元素 就直接返回 204 } 205 206 pH-next-next; 207 H-next-nextNULL; 208 while(p!NULL){ 209 qp; 210 pp-next; 211 212 q-nextH-next; 213 H-nextq; 214 } 215 return 0; 216 }链表相邻两个节点最大值linklist list_adjmax(linklist H){ 219 int sum; 220 linklist q,r,p; 221 if(HNULL) 222 { 223 printf(H is null\n); 224 return NULL;//注意 返回类类型是指针 225 } 226 if(H-nextNULL||H-next-nextNULL||H-next-next-nextNULL){ 227 return H; 228 } 229 qH-next; 230 pH-next-next; 231 rq; 232 sump-dataq-data; 233 234 while(p-next!NULL){ 235 pp-next; 236 qq-next; 237 if(sump-dataq-data){ 238 sumq-datap-data; 239 rq; 240 } 241 } 242 return r; 243 }栈顺序栈1 typedef int data_t; 2 3 typedef struct { 4 data_t *data; 5 int maxlen; 6 int top; 7 }sqstack; 8 sqstack* stack_create(int len); 9 int stack_push(sqstack*s,data_t value); 10 data_t stack_pop(sqstack*s); 11 data_t stack_top(sqstack*s); 12 int stack_free(sqstack*s); 13 int stack_clear(sqstack*s); 14 int stack_empty(sqstack*s); 15 int stack_full(sqstack*s);1 #includestdio.h 2 #includesqstack.h 3 #includestring.h 4 #includestdlib.h 5 sqstack* stack_create(int len){ 6 sqstack* s; 7 if((s(sqstack*)malloc(sizeof(sqstack)))NULL){ 8 printf(malloc sqstack failed\n); 9 return NULL; 10 } 11 12 if((s-data(data_t*)malloc(len*sizeof(data_t)))NULL){ 13 printf(malloc data dailed\n); 14 return NULL; 15 } 16 memset(s-data,0,len*sizeof(data_t)); 17 s-maxlenlen; 18 s-top-1; 19 20 return s; 21 } 22 int stack_push(sqstack*s,data_t value){ 23 if(sNULL){ 24 printf(s is null\n); 25 return -1; 26 } 27 28 if(s-tops-maxlen-1){ 29 printf(stack is full\n); 30 return -1; 31 } 32 s-top; 33 s-data[s-top]value; 34 35 return 0; 36 } 37 38 data_t stack_pop(sqstack*s){ 39 s-top--; 40 return (s-data[s-top1]); 41 } 42 data_t stack_top(sqstack*s){ 43 return (s-data[s-top]); 44 } 45 int stack_free(sqstack*s){ 46 if(sNULL){ 47 printf(s is NULL\n); 48 return -1; 49 } 50 if(s-data!NULL){ 51 free(s-data); 52 free(s); 53 return 0; 54 } 55 } 56 int stack_clear(sqstack*s){ 57 printf(s is null\n); 58 return -1; 59 } 60 int stack_empty(sqstack*s){ 61 if(sNULL){ 62 printf(s is NULL \n); 63 return -1; 64 } 65 return (s-top-1?1:0); 66 } 67 int stack_full(sqstack*s){ 68 printf(s is NULL\n); 69 return -1; 70 71 return (s-tops-maxlen-1?1:0); 72 }1 #includestdio.h 2 #includesqstack.h 3 #includestdlib.h 4 int main(int argc,const char* argv[]){ 5 sqstack *s; 6 sstack_create(100); 7 if(sNULL) 8 return -1; 9 10 stack_push(s,10); 11 stack_push(s,20); 12 stack_push(s,30); 13 stack_push(s,40); 14 while(!stack_empty(s)){ 15 printf(pop %d\n,stack_pop(s)); 16 } 17 free(s); 18 return 0; 19 }链式栈入栈typedef int data_t; typedef struct node { data_t data; struct node *next; }listnode, *linkstack; linkstack stack_create(); int stack_push(linkstack s, data_t value); data_t stack_pop(linkstack s); int stack_empty(linkstack s); data_t stack_top(linkstack s); linkstack stack_free(linkstack s);#include stdio.h #include stdlib.h #include linkstack.h linkstack stack_create() { linkstack s; s (linkstack)malloc(sizeof(listnode)); if (s NULL) { printf(malloc failed\n); return NULL; } s-data 0; s-next NULL; return s; } int stack_push(linkstack s, data_t value) { linkstack p; if (s NULL) { printf(s is NULL\n); return -1; } p (linkstack)malloc(sizeof(listnode)); if (p NULL) { printf(malloc failed\n); return -1; } p-data value; //p-next NULL; p-next s-next; s-next p; return 0; } data_t stack_pop(linkstack s) { linkstack p; data_t t; p s-next; s-next p-next; t p-data; free(p); p NULL; return t; } int stack_empty(linkstack s) { if (s NULL) { printf(s is NULL\n); return -1; } return (s-next NULL ? 1 : 0); } data_t stack_top(linkstack s) { return (s-next-data); } linkstack stack_free(linkstack s) { linkstack p; if (s NULL) { printf(s is NULL\n); return NULL; } while (s ! NULL) { p s; s s-next; printf(free:%d\n, p-data); free(p); } return NULL; }#include stdio.h #include stdlib.h #include linkstack.h int main(int argc, const char *argv[]) { linkstack s; s stack_create(); if (s NULL) return -1; stack_push(s, 10); stack_push(s, 20); stack_push(s, 30); stack_push(s, 40); #if 0 while (!stack_empty(s)) { printf(pop:%d\n, stack_pop(s)); } #endif s stack_free(s); return 0; }队列typedef int datatype; #define N 128 typedef struct { datatype data[N]; int front; int rear; }sequeue; sequeue * queue_create(); int enqueue(sequeue *sq, datatype x); datatype dequeue(sequeue *sq); int queue_empty(sequeue *sq); int queue_full(sequeue *sq); int queue_clear(sequeue *sq); sequeue * queue_free(sequeue *sq);#include stdio.h #include stdlib.h #include string.h #include sequeue.h sequeue * queue_create() { sequeue *sq; if ((sq (sequeue *)malloc(sizeof(sequeue))) NULL) { printf(malloc failed\n); return NULL; } memset(sq-data, 0, sizeof(sq-data)); sq-front sq-rear 0; return sq; } int enqueue(sequeue *sq, datatype x) { if (sq NULL) { printf(sq is NULL\n); return -1; } if ((sq-rear 1) % N sq-front) { printf(sequeue is full\n); return -1; } sq-data[sq-rear] x; sq-rear (sq-rear 1) % N; return 0; } datatype dequeue(sequeue *sq) { datatype ret; ret sq-data[sq-front]; sq-front (sq-front 1) % N; return ret; } int queue_empty(sequeue *sq) { if (sq NULL) { printf(sq is NULL\n); return -1; } return (sq-front sq-rear ? 1 : 0); } int queue_full(sequeue *sq) { if (sq NULL) { printf(sq is NULL\n); return -1; } if ((sq-rear 1) % N sq-front) { return 1; } else { return 0; } } int queue_clear(sequeue *sq) { if (sq NULL) { printf(sq is NULL\n); return -1; } sq-front sq-rear 0; return 0; } sequeue * queue_free(sequeue *sq) { if (sq NULL) { printf(sq is NULL\n); return NULL; } free(sq); sq NULL; return NULL; }#include stdio.h #include sequeue.h int main(int argc, const char *argv[]) { sequeue *sq; if ((sq queue_create()) NULL) { return -1; } enqueue(sq, 10); enqueue(sq, 100); enqueue(sq, 1000); while (!queue_empty(sq)) { printf(dequeue:%d\n, dequeue(sq)); } queue_free(sq); return 0; }链式队列#include stdio.h #include stdlib.h #include linkqueue.h linkqueue * queue_create() { linkqueue *lq; if ((lq (linkqueue *)malloc(sizeof(linkqueue))) NULL) { printf(malloc linkqueue failed\n); return NULL; } lq-front lq-rear (linklist)malloc(sizeof(listnode)); if (lq-front NULL) { printf(malloc node failed\n); return NULL; } lq-front-data 0; lq-front-next NULL; return lq; } int enqueue(linkqueue *lq, datatype x) { linklist p; if (lq NULL) { printf(lq is NULL\n); return -1; } if ((p (linklist)malloc(sizeof(listnode))) NULL) { printf(malloc node failed\n); return -1; } p-data x; p-next NULL; lq-rear-next p; lq-rear p; return 0; } datatype dequeue(linkqueue *lq) { linklist p; if (lq NULL) { printf(lq is NULL\n); return -1; } p lq-front; lq-front p-next; free(p); p NULL; return (lq-front-data); } int queue_empty(linkqueue *lq) { if (lq NULL) { printf(lq is NULL\n); return -1; } return (lq-front lq-rear ? 1 : 0); } int queue_clear(linkqueue *lq) { linklist p; if (lq NULL) { printf(lq is NULL\n); return -1; } while (lq-front-next) { p lq-front; lq-front p-next; printf(clear free:%d\n, p-data); free(p); p NULL; } return 0; } linkqueue * queue_free(linkqueue *lq) { linklist p; if (lq NULL) { printf(lq is NULL\n); return NULL; } while (lq-front) { p lq-front; lq-front p-next; printf(free:%d\n, p-data); free(p); } free(lq); lq NULL; return NULL; }typedef int datatype; typedef struct node { datatype data; struct node *next; }listnode , *linklist; typedef struct { linklist front; linklist rear; }linkqueue; linkqueue * queue_create(); int enqueue(linkqueue *lq, datatype x); datatype dequeue(linkqueue *lq); int queue_empty(linkqueue *lq); int queue_clear(linkqueue *lq); linkqueue * queue_free(linkqueue *lq);#include stdio.h #include linkqueue.h int main(int argc, const char *argv[]) { linkqueue *lq; lq queue_create(); if (lq NULL) return -1; enqueue(lq, 10); enqueue(lq, 20); enqueue(lq, 30); enqueue(lq, 40); //while (!queue_empty(lq)) { //printf(dequeue:%d\n, dequeue(lq)); //} queue_clear(lq); lq queue_free(lq); enqueue(lq, 50); return 0; }查找哈希查找法1 #ifndef _HASH_ 2 #define _HASH_ 3 4 typedef int datatype; 5 #define N 20 6 typedef struct node{ 7 datatype key; 8 datatype value; 9 struct node* next; 10 }listnode,*linklist; 11 12 typedef struct{ 13 listnode data[N]; 14 }hash; 15 16 hash* hash_create(); 17 int hash_insert(hash*HT,datatype key); 18 linklist hash_search(hash*HT,datatype key); 19 #endif1 #includestdio.h 2 #includestdlib.h 3 #includehash.h 4 5 hash* hash_create(){ 6 hash*HT; 7 if((HT(hash*)malloc(sizeof(hash)))NULL){ 8 printf(malloc failed\n); 9 return NULL; 10 } 11 memset(HT,0,sizeof(hash)); 12 13 return HT; 14 } 15 16 int hash_insert(hash*HT,datatype key){ 17 linklist q,p; 18 if(HTNULL){ 19 printf(Ht is NULL\n); 20 return -1; 21 } 22 23 if((p(linklist)malloc(sizeof(listnode)))NULL){ 24 printf(malloc failed\n); 25 return -1; 26 } 27 28 p-keykey; 29 p-valuekey%N; 30 p-nextNULL; 31 32 q(HT-data[key%N]); 33 34 while(q-nextq-next-keyp-key){ 35 qq-next; 36 } 37 p-nextq-next; 38 q-nextp; 39 40 return 0; 41 } 42 43 linklist hash_search(hash *HT,datatype key){ 44 linklist p; 45 if(HTNULL){ 46 printf(HT is NULL\n); 47 return -1; 48 } 49 p(HT-data[key%N]); 50 51 while(p-nextp-next-key!key){ 52 pp-next; 53 } 54 55 if(p-nextNULL){ 56 return NULL; 57 }else{ 58 printf(found %d\n,key); 59 return p-next; 60 } 61 }1 #includestdio.h 2 #includestdlib.h 3 #includehash.h 4 int main(int argc,const char* argv[]) 5 { 6 hash* HT; 7 linklist r; 8 int key; 9 int data[]{23,45,67,12,41,8,3,10}; 10 int i; 11 if((HThash_create())NULL){ 12 13 return -1; 14 } 15 for(i0;isizeof(data)/sizeof(int);i){ 16 hash_insert(HT,data[i]); 17 } 18 printf(input:); 19 scanf(%d,key); 20 r hash_search(HT,key); 21 if(rNULL) 22 printf(not found\n); 23 else 24 printf(found: %d %d\n,key%N,r-key); 25 return 0; 26 } 27排序快速排序#include stdio.h #include stdlib.h #define N 15 int partion(int *data, int low, int high); int quick_sort(int *data, int low, int high); int compare(const void *p1, const void *p2); int main(int argc, const char *argv[]) { int data[N] {0}; int i; srandom(10); for (i 0; i N; i) { data[i] random() % 100; } for (i 0; i N; i) { printf(%d , data[i]); } puts(); //quick_sort(data, 0, N-1); qsort(data, N, sizeof(int), compare); for (i 0; i N; i) { printf(%d , data[i]); } puts(); return 0; } int partion(int *data, int low, int high) { int temp data[low]; while (low high) { while (low high temp data[high]) { high--; } data[low] data[high]; while (low high temp data[low]){ low; } data[high] data[low]; } data[low] temp; return low; } int quick_sort(int *data, int low, int high) { int t; if (data NULL) { return -1; } if (low high) return 0; t partion(data, low, high); quick_sort(data, low, t-1); quick_sort(data, t1, high); return 0; } int compare(const void *p1, const void *p2) { return (*(const int *)p1 - *(const int *)p2); }快速排序
算法精解与面试技巧)
