数据结构重点

链表

单链表基本运算

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.c

1 #include<stdio.h> 2 #include"link.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 H=list_create(); 12 if(H==NULL) 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 H=list_create(); 43 if(H==NULL) 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(H==NULL) 9 { 10 printf("malloc failed\n"); 11 return H;//此时H为NULL 12 } 13 //赋值初始值 14 H->data=0; 15 H->next=NULL; 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(H==NULL){ 27 return -1; 28 } 29 p=(linklist)malloc(sizeof(linknode)); 30 if(p==NULL) 31 { 32 printf("malloc failed\n"); 33 return -1; 34 } 35 p->data=value; 36 p->next=NULL; 37 38 q=H; 39 while(q->next!=NULL){ 40 q=q->next; 41 } 42 43 q->next=p; 44 45 return 0; 46 }

链表的打印

47 48 int list_show(linklist H){ 49 linklist p; 50 if(H==NULL){ 51 52 printf("H is null\n"); 53 return -1; 54 } 55 p=H; 56 57 while(p->next!=NULL){ 58 printf("%d ",p->next->data); 59 p=p->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(H==NULL){ 70 71 printf("H is null"); 72 return NULL; 73 } 74 75 if(pos==-1){ 76 return H; 77 } 78 79 p=H; 80 i=-1; 81 while(i<pos){ 82 p=p->next; 83 if(p==NULL){ 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 p=list_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->data=value; 104 q->next=NULL; 105 // 插入数据 106 q->next=p->next; 107 p->next=q; 108 109 return 0; 110 } 111

链表元素的删除

int list_delete(linklist H,int pos){ 113 114 linklist p; 115 //存放要删除的节点并且释放 116 linklist q; 117 //判断该链表是否为空表 118 if(H==NULL){ 119 printf("H is null\n"); 120 return -1; 121 } 122 123 124 p=list_get(H,pos-1); 125 126 //判断找到的位置是否为空 127 if(p==NULL) 128 return -1; 129 if(p->next==NULL){ 130 printf("delete pos is invalid\n"); 131 return -1;} 132 133 134 q=p->next; 135 p->next=p->next->next; 136 free(q);//释放 137 return 0; 138 }

链表的释放

int list_free(linklist H){ 140 linklist p; 141 142 if(H==NULL) 143 return NULL; 144 145 p=H; 146 147 printf("free"); 148 while(H!=NULL){ 149 p=H; 150 151 printf("%d ",p->data); 152 H=H->next; 153 154 free(p); 155 } 156 157 puts("");//换行符要放在最后 158 159 return 0; 160 }

有序链表的合并

#include<stdio.h> 2 #include"link.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 H1=list_create(); 12 if(H1==NULL) 13 return; 14 H2=list_create(); 15 if(H2==NULL) 16 return; 17 18 for(i=0;i<sizeof(a)/sizeof(int);i++) 19 { 20 list_tail_insert(H1,a[i]); 21 } 22 for(i=0;i<sizeof(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(H1==NULL||H2==NULL){ 165 printf("H1||H2 is NULL\n"); 166 return -1; 167 } 168 p=H1->next; 169 q=H2->next; 170 r=H1; 171 H1->next=NULL; 172 H2->next=NULL; 173 174 while(p&&q){ 175 176 if(p->data<q->data){ 177 r->next=p; 178 p=p->next; 179 180 r=r->next; 181 r->next=NULL; 182 } 183 else 184 { 185 r->next=q; 186 q=q->next; 187 188 r=r->next; 189 r->next=NULL; 190 } 191 } 192 193 194 return 0; 195 }

链表的反转

int list_reverse(linklist H){ 197 linklist p,q; 198 if(H==NULL){ 199 printf("H is NULL\n"); 200 return -1; 201 } 202 if(H->next==NULL||H->next->next==NULL){ 203 return 0;// 空表或者只有一个元素 就直接返回 204 } 205 206 p=H->next->next; 207 H->next->next=NULL; 208 while(p!=NULL){ 209 q=p; 210 p=p->next; 211 212 q->next=H->next; 213 H->next=q; 214 } 215 return 0; 216 }

链表相邻两个节点最大值

linklist list_adjmax(linklist H){ 219 int sum; 220 linklist q,r,p; 221 if(H==NULL) 222 { 223 printf("H is null\n"); 224 return NULL;//注意 返回类类型是指针 225 } 226 if(H->next==NULL||H->next->next==NULL||H->next->next->next==NULL){ 227 return H; 228 } 229 q=H->next; 230 p=H->next->next; 231 r=q; 232 sum=p->data+q->data; 233 234 while(p->next!=NULL){ 235 p=p->next; 236 q=q->next; 237 if(sum<p->data+q->data){ 238 sum=q->data+p->data; 239 r=q; 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 #include<stdio.h> 2 #include"sqstack.h" 3 #include<string.h> 4 #include<stdlib.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->maxlen=len; 18 s->top=-1; 19 20 return s; 21 } 22 int stack_push(sqstack*s,data_t value){ 23 if(s==NULL){ 24 printf("s is null\n"); 25 return -1; 26 } 27 28 if(s->top==s->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->top+1]); 41 } 42 data_t stack_top(sqstack*s){ 43 return (s->data[s->top]); 44 } 45 int stack_free(sqstack*s){ 46 if(s==NULL){ 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(s==NULL){ 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->top==s->maxlen-1?1:0); 72 }

1 #include<stdio.h> 2 #include"sqstack.h" 3 #include<stdlib.h> 4 int main(int argc,const char* argv[]){ 5 sqstack *s; 6 s=stack_create(100); 7 if(s==NULL) 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 #endif

1 #include<stdio.h> 2 #include<stdlib.h> 3 #include"hash.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(HT==NULL){ 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->key=key; 29 p->value=key%N; 30 p->next=NULL; 31 32 q=&(HT->data[key%N]); 33 34 while(q->next&&q->next->key<p->key){ 35 q=q->next; 36 } 37 p->next=q->next; 38 q->next=p; 39 40 return 0; 41 } 42 43 linklist hash_search(hash *HT,datatype key){ 44 linklist p; 45 if(HT==NULL){ 46 printf("HT is NULL\n"); 47 return -1; 48 } 49 p=&(HT->data[key%N]); 50 51 while(p->next&&p->next->key!=key){ 52 p=p->next; 53 } 54 55 if(p->next==NULL){ 56 return NULL; 57 }else{ 58 printf("found %d\n",key); 59 return p->next; 60 } 61 }

1 #include<stdio.h> 2 #include<stdlib.h> 3 #include"hash.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((HT=hash_create())==NULL){ 12 13 return -1; 14 } 15 for(i=0;i<sizeof(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(r==NULL) 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, t+1, high); return 0; } int compare(const void *p1, const void *p2) { return (*(const int *)p1 - *(const int *)p2); }

快速排序