C++几种常见的数据结构，顺序表 链表 栈 队列 二叉树 哈希表_c++ 哈希表 二叉树 堆栈 链表

一. 内容简介

C++几种常见的数据结构，顺序表 链表 栈 队列 二叉树 哈希表

二. 软件环境

2.1 Visual studio 2017

三.主要流程

3.1 顺序表

3.2 链表

3.3 栈

3.4 队列

3.5 二叉树

3.6 哈希表

四.具体步骤

4.1 顺序表

头文件

#pragma once
typedef int data_t;// 根据自己需要换数据类型
#define N 100

typedef struct {
	data_t data[N];
	int last;
}sqlist,*sqlink;

sqlink list_create();
int list_free(sqlink l);
int list_clear(sqlink l);
int iist_empty(sqlink l);
int list_length(sqlink l);
int list_locate(sqlink l,data_t value);
int list_insert(sqlink l, data_t value,int pos);
int list_delete(sqlink l,int pos);
int list_merge(sqlink l1,sqlink l2);
int list_purge(sqlink l);
int list_show(sqlink l);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

cpp文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sqlist.h"
/*
 * list_create: 判断表是否为空
 * para:
 * @ret: 返回常见好的顺序表
 */
sqlink list_create() {
	// 申请内存
	sqlink L;
	L = (sqlink)malloc(sizeof(sqlist));
	if (L==NULL) {
		printf("list malloc failed\n");
		return L;
	}
	// 初始化
	memset(L,0, sizeof(sqlist));//清零
	L->last = -1;
	// 返回
	return L;
}
int list_free(sqlink l) {
	if (l == NULL) {
		return -1;
	}
	free(l);
	l = NULL;
	return 0;
}
/*
 * list_clear: 清空数据表
 * para: sqlink l 要清空的表
 * @ret: 0 清空成功 -1 表示失败
 */
int list_clear(sqlink l) {
	if (l==NULL)
	{
		return -1;
	}
	// 初始化
	memset(l, 0, sizeof(sqlist));//清零
	l->last = -1;
	return 0;
}
/*
 * iist_empty: 数据表是否为空
 * para: sqlink l 要清空的表
 * @ret: 1 为空 0 表示不为空
 */
int iist_empty(sqlink l) {
	if (l->last==-1) {
		return 1;
	}
	else
	{
		return 0;
	}
}
int list_length(sqlink l) {
	if (l == NULL)
	{
		return -1;
	}
	return (l->last+1);
}

int list_locate(sqlink l, data_t value) {
	for (int i = 0; i <= l->last ; i++)
	{
		if (l->data[i]==value) {
			return i;
		}
	}
	return -1;
}
int list_insert(sqlink l, data_t value, int pos) {
	// full
	if (l->last == N-1) {
		printf("list is full\n");
		return -1;
	}
	// check para
	if (pos<0 ||pos>l->last+1) {
		printf("pos is invalid\n");
		return -1;
	}
	// move 
	for (int i = l->last; i >=pos; i--)
	{
		l->data[i + 1] = l->data[i];
	}
	// update
	l->data[pos] = value;
	l->last++;

	return 0;
}

int list_show(sqlink l) {
	if (l==NULL) {
		return -1;
	}
	if (l->last==-1)
	{
		printf("list is empty\n");
	}
	for (int i = 0; i <= l->last; i++)
	{
		printf("%d",l->data[i]);
	}
	puts("");
}

int list_delete(sqlink l, int pos) {
	if (l->last == -1) {
		printf("list is empty\n");
		return -1;
	}
	if (pos<0||pos>l->last) {
		printf("delete pos is invalid\n");
		return -1;
	}
	for (int i = pos+1; i <=l->last; i++)
	{
		l->data[i - 1] = l->data[i];
	}
	l->last--;
	return 0;
}
int list_merge(sqlink l1, sqlink l2) {
	int i = 0;
	int ret;
	while (i<=l2->last)
	{
		ret = list_locate(l1,l2->data[i]);
		if (ret == -1) {
			if (list_insert(l1, l2->data[i], l1->last + 1) == -1) {
				return -1;
			}
		}
	}
	return 0;
}
int list_purge(sqlink l) {
	if (l->last == 0) {
		return 0;
	}
	int i = 1;
	int j;
	while (i<= l->last)
	{
		j = i - 1;
		while (j>= 0)
		{
			if (l->data[i] == l->data[j]) {
				list_delete(l,i);
			}
			else
			{
				j--;
			}
		}
		if (j<0) {
			i++;
		}
	}
	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

4.2 链表

实现了链表一些基本的功能，还加了几个简单的算法， 链表反转，求链表种相邻两节点data值之和最大的，第一节点的指针，链表拼接，以及排序
链表头文件

#pragma once
typedef int data_t;
typedef struct node {
	data_t data;
	struct node * next;
}listnode, *linklist;
linklist list_create();
linklist list_free();
int list_tail_insert(linklist h, data_t value);
linklist list_get(linklist h,int pos);
int list_insert(linklist h,data_t value,int pos);
int list_delete(linklist h,int pos);
int list_show(linklist h);
int list_reverse(linklist h);
linklist list_adjmax(linklist h);
int list_merge(linklist l1,linklist l2);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

链表cpp文件

#include "linklist.h"
#include <stdlib.h>
#include <stdio.h>

linklist list_create() {
	linklist h = (linklist)malloc(sizeof(listnode));
	if (h == NULL) {
		printf("malloc failed\n");
		return h;
	}
	h->data = 0;
	h->next = NULL;
	return h;
}
linklist list_free(linklist h) {
	linklist p = h;
	if ( h == NULL) {
		return NULL;
	}
	while (h != NULL)
	{
		p = h;
		h = h->next;
		free(p);
	}
	return NULL;
}

int list_tail_insert(linklist h,data_t value) {
	if (h==NULL) {
		printf("H is NULL\n");
		return -1;
	}
	linklist p = (linklist)malloc(sizeof(listnode));
	linklist q = h;
	if (p == NULL) {
		printf("malloc failed\n");
		return -1;
	}
	p->data = value;
	p->next = NULL;
	while (q->next != NULL)
	{
		q=q->next;
	}
	q->next = p;
	return 0;
}

linklist list_get(linklist h, int pos) {
	linklist p;
	int i = -1;
	if (h == NULL) {
		printf("h is null\n");
		return NULL;
	}
	if (pos == -1) {
		return h;
	}
	if (pos < -1) {
		printf("pos is null\n");
		return NULL;
	}
	p = h;
	while (i<pos)
	{
		p = p->next;
		if (p==NULL)
		{
			break;
			printf("pos is invalid\n");
		}
		i++;
	}
	return p;
}

int list_insert(linklist h, data_t value, int pos) {
	linklist p;
	linklist q;
	if (h == NULL) {
		printf("h is null\n");
		return -1;
	}
	p = list_get(h,pos-1);
	if (p == NULL) {
		return -1; 
	}
	if ((q = (linklist)malloc(sizeof(listnode)))==NULL) {
		printf("malloc failed\n");
		return -1;
	}
	q->data = value;
	q->next = p->next;
	p->next = q;
	return 0;
}

int list_delete(linklist h, int pos) {
	linklist p;
	linklist q;
	if (h == NULL) {
		printf("h is NULL\n");
	}
	p = list_get(h,pos - 1);
	if (p == NULL) {
		return -1;
	}
	if (p->next == NULL) {  
		printf("delete pos is invalid\n");
	}
	q = p->next;
	p->next = q->next;
	free(q);
	q = NULL;
}

int list_show(linklist h) {
	if (h == NULL) {
		printf("H is NULL\n");
		return -1;
	}
	linklist p = h;
	while (p->next != NULL)
	{
		printf("%d\n",p->next->data);
		p = p->next;
	}
	// puts("");
	return 0;
}

链表相关算法
// 链表反转
int list_reverse(linklist h) {
	linklist p;
	linklist q;
	if (h==NULL) {
		printf("h is null\n");
		return -1;
	}
	if (h->next==NULL||h->next->next==NULL)
	{
		return 0;
	}
	p = h->next->next;
	h->next->next = NULL;
	while (p!=NULL)
	{
		q = p;
		p = p->next;

		q->next = h->next;
		h->next = q;
	}
	return 0;
}
// 求链表种相邻两节点data值之和最大的，第一节点的指针
linklist list_adjmax(linklist h) {
	linklist p, q, r;
	data_t sum;
	if (h==NULL) {
		printf("h is Null\n");
		return NULL;
	}
	if (h->next == NULL || h->next->next == NULL || h->next->next->next == NULL) {
		return h;
	}
	q = h->next;
	p = h->next->next;
	r = q;
	sum = q->data + p->data;
	while (p->next != NULL)
	{
		p = p->next;
		q = q->next;
		if (sum < q->data + p->data)
		{
			sum = q->data + p->data;
			r = q;
		}
	}
	return r;
}
// 链表拼接，以及排序
int list_merge(linklist l1, linklist l2) {
	linklist p, q, r;

	if (l1 == NULL||l2==NULL) {
		printf("l1,l2 is null");
	}
	p = l1->next;
	q = l2->next;
	r = l1;
	l1->data = NULL;
	l2->data = NULL;
	while (p&&p)
	{
		if (p->data<=q->data) {
			r->next = p;
			p = p->next;
			r = r->next;
			r->next = NULL;
		}
		else
		{
			r->next = q;
			q = q->next;
			r = r->next;
			r->next = NULL;
		}
	}
	if (p==NULL)
	{
		r->next = q;
	}
	else
	{
		r->next = p;
	}
	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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

4.3 栈

栈是先用数组实现的栈
头文件

#pragma once
typedef int data_t;
typedef struct {
	data_t *data;
	int maxlen;
	int top;
}sqstack;
sqstack * stack_create(int len);
int stack_push(sqstack *s,data_t value);
int stack_empty(sqstack *s);
int stack_full(sqstack *s);
data_t stack_pop(sqstack *s);
data_t stack_top(sqstack *s);
int stack_clear(sqstack *s);
int stack_free(sqstack *s);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

cpp文件

#include "sqstack.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
sqstack * stack_create(int len) {
	sqstack * s;
	if ((s=(sqstack *)malloc(sizeof(sqstack)))==NULL) {
		printf("malloc sqstack failed\n");
		return NULL;
	}
	if ((s->data = (data_t *)malloc(len*sizeof(data_t))) == NULL) {
		printf("malloc data failed\n");
		return NULL;
	}
	memset(s->data,0,len*sizeof(data_t));
	s->maxlen = len;
	s->top = -1;
	return s;
}
int stack_push(sqstack *s, data_t value) {
	if (s==NULL) {
		printf("s is null\n");
		return -1;
	}
	if (s->top == s->maxlen-1) {
		printf("stack is full\n");
		return -1;
	}
	s->top++;
	s->data[s->top] = value;
	return 0;
}
int stack_empty(sqstack *s) {
	if (s == NULL) {
		printf("s is null\n");
		return -1;
	}
	return (s->top == -1 ? 1 : 0);
}
int stack_full(sqstack *s) {
	if (s == NULL) {
		printf("s is null\n");
		return -1;
	}
	return (s->top == s->maxlen-1 ? 1 : 0);
}
data_t stack_pop(sqstack *s) {
	s->top--;
	return (s->data[s->top+1]);
}  
data_t stack_top(sqstack *s) {
	return (s->data[s->top]);
}
int stack_clear(sqstack *s) {
	if (s == NULL) {
		printf("s is null\n");
		return -1;
	}
	s->top = -1;
	return 0;
}
int stack_free(sqstack *s) {
	if (s == NULL) {
		printf("s is null\n");
		return -1;
	}
	if (s->data!=NULL) {
		free(s->data);
	}
	free(s);
}
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

然后接下来是链表栈，都是一些很简单的功能
头文件

#pragma once
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);
1
2
3
4
5
6
7
8
9
10
11
12

cpp文件

#include "linkstack.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.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) {
	if (s == NULL) {
		printf("s is NULL\n");
		return -1;
	}
	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;
		free(p);
	}
}
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

4.4 队列

队列也是分成两块，一块顺序队列
头文件

#pragma once
#define N 128
typedef int datatype;
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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

cpp文件，

#include "sequeue.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.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->rear + 1 )% N == sq->front) {
		printf("sequenue 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) {
	return (sq->rear % N == sq->front ? 1 : 0);
}
int queue_full(sequeue *sq) {
	if ((sq->rear + 1) % N == sq->front) {
		printf("sequenue is full\n");
		return 1;
	}
	else
	{
		return -1;
	}
}
int queue_clear(sequeue *sq) {
	sq->front = sq->rear = 0;
	return 0; 
}
sequeue * queue_free(sequeue *sq) {
	free(sq);
	sq = NULL;
	return NULL;
}
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

然后接着是链表队列
头文件

#pragma once
#define N 128
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);
linklist queue_free(linkqueue *lq);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

cpp文件

#include "linkqueue.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.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 failed\n");
		return NULL;
	}
	lq->front->data = 0;
	lq->front->next = NULL;

	return lq;
}
int enqueue(linkqueue *lq, datatype x) {
	if (lq == NULL) {
		printf("lq is null\n");
		return -1;
	}
	linklist p;
	if ((p=(linklist)malloc(sizeof(listnode)))==NULL) {
		printf("malloc 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;
	p = lq->front;
	lq->front = p->next;
	free(p);
	p = NULL;
	return (lq->front->data);
}
int queue_empty(linkqueue *lq) {
	return (lq->front == lq->rear ? 1:0);
}
int queue_clear(linkqueue *lq) {
	linklist p;
	if (lq == NULL) {
		printf("lq is null\n");
		return NULL;
	}
	while (lq->front->next)
	{
		p = lq->front;
		lq->front = p->next;
		free(p);
		p = NULL;
	}
}
linklist 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;
		free(p);
	}
	free(lq);
	lq = NULL;//应该没啥用
	return NULL;
}
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

4.5 二叉树

二叉树实现
头文件

#pragma once
#include "tree.h"
#define N 128
typedef bitree 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);
linklist queue_free(linkqueue *lq);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

cpp文件

#include <stdlib.h>
#include <stdio.h>
#include <string.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 failed\n");
		return NULL;
	}
	lq->front->data = 0;
	lq->front->next = NULL;
	return lq;
}

int enqueue(linkqueue *lq, datatype x) {
	if (lq == NULL) {
		printf("lq is null\n");
		return -1;
	}
	linklist p;
	if ((p = (linklist)malloc(sizeof(listnode))) == NULL) {
		printf("malloc 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;
	p = lq->front;
	lq->front = p->next;
	free(p);
	p = NULL;
	return (lq->front->data);
}
int queue_empty(linkqueue *lq) {
	return (lq->front == lq->rear ? 1 : 0);
}
int queue_clear(linkqueue *lq) {
	linklist p;
	if (lq == NULL) {
		printf("lq is null\n");
		return NULL;
	}
	while (lq->front->next)
	{
		p = lq->front;
		lq->front = p->next;
		free(p);
		p = NULL;
	}
}
linklist 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;
		free(p);
	}
	free(lq);
	lq = NULL;//应该没啥用
	return NULL;
}
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

4.6 哈希表

哈希表头文件

#pragma once
#define N 15
typedef int datatype;
typedef struct node
{
	datatype key;
	datatype value;
	struct  node * next;
}listnode,*linklist;
typedef struct {
	listnode data[N];
}hash;
hash * hash_create();
int hash_insert(hash *HT,datatype key);
linklist  hash_search(hash *HT,datatype key);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

cpp文件

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "hash.h"

hash * hash_create() {
	hash * HT;
	if ((HT = (hash*)malloc(sizeof(hash)))==NULL) {
		printf("malloc failed");
		return NULL;
	}
	memset(HT,0,sizeof(hash));
	return HT;
}
int hash_insert(hash *HT, datatype key) {
	linklist p,q;
	if (HT == NULL) {
		printf("HT is NULL\n");
		return -1;
	}

	if ((p=(linklist)malloc(sizeof(listnode)))=NULL) {
		printf("malloc failed\n");
		return -1;
	}
	p->key = key;
	p->value = key % N;
	p->next = NULL;
	
	q = &(HT->data[key % N]);
	while (q->next && (q->next->key<p->key))
	{
		q = q->next;
	}
	p->next = q->next;
	q->next = p;
	return 0;
}
linklist hash_search(hash *HT, datatype key) {
	linklist p;
	if (HT == NULL) {
		printf("HT is NULL\n");
		return NULL;
	}
	p = &(HT->data[key%N]);
	while (p->next && (p->next->key!=key))
	{
		p = p->next;
	}
	if (p->next == NULL) {
		return NULL;
	}
	else
	{
		return p->next;
	} 
}
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

五. 参考

华清远见嵌入式课程