数据结构(C语言版)——单链表顺序存储结构

发表于 | 评论数： | 阅读次数：
本文字数： 3.2k | 阅读时长 ≈ 6 分钟

单链表顺序存储结构的代码实现。

定义与声明

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
#ifndef _LINEAR_LIST_H_
#define _LINEAR_LIST_H_
#include <stdio.h>

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10

typedef int ElemType;

typedef struct {
	ElemType *elem;
	int length;
	int listsize;
}Sqlist;

int InitList(Sqlist*);
void DestroyList(Sqlist*);
void ClearList(Sqlist*);
int ListEmpty(Sqlist);
int ListLength(Sqlist);
int GetElem(Sqlist, int, ElemType*);
int LocateElem(Sqlist, ElemType, int compare(ElemType, ElemType));
int PriorElem(Sqlist, ElemType, ElemType*);
int NextElem(Sqlist, ElemType, ElemType*);
int ListInsert(Sqlist*, int, ElemType);
int ListDelete(Sqlist*, int, ElemType*);
int ListTraverse(Sqlist, int visitor(ElemType));

#endif // !_LINEAR_LIST_H_

函数实现

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>
#include "linear_list.h"

int InitList(Sqlist* L) {
	(*L).elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	(*L).length = 0;
	(*L).listsize = LIST_INIT_SIZE;
	return 1;
}

void DestroyList(Sqlist* L) {
	free(L->elem);
	L->elem = NULL;
	L->length = 0;
	L->listsize = 0;
}

void ClearList(Sqlist* L) {
	L->length = 0;
}

int ListEmpty(Sqlist L) {
	return L.length == 0 ? 1 : 0;
}

int ListLength(Sqlist L) {
	return L.length;
}

int GetElem(Sqlist L, int i, ElemType* e) {
	if (i<0 || i>L.length)
		return 0;
	else
		*e = L.elem[i - 1];
	return 1;
}

int LocateElem(Sqlist L, ElemType e, int compare(ElemType, ElemType)) {
	for (int i = 1; i <= L.length; i++) {
		if (compare(e, L.elem[i - 1]))
			return i;
	}
	return 0;
}

int PriorElem(Sqlist L, ElemType cur_e, ElemType* pri_e) {
	if (L.elem[0] != cur_e) {
		for (int i = 1; i < L.length; i++) {
			if (L.elem[i] == cur_e) {
				*pri_e = L.elem[i - 1];
				return 1;
			}
		}
	}
	return 0;
}

int NextElem(Sqlist L, ElemType cur_e, ElemType* next_e) {

	for (int i = 0; i < L.length - 1; i++) {
		if (L.elem[i] == cur_e) {
			*next_e = L.elem[i + 1];
			return 1;
		}
	}
	return 0;
}

int ListInsert(Sqlist* L, int i, ElemType e) {
	ElemType *tmp, *p, *q;
	if (i < 1 || i>L->length + 1)
		return 0;
	if (L->length >= L->listsize) {
		tmp = (ElemType*)realloc(L->elem, (L->length + LISTINCREMENT) * sizeof(ElemType));
		if (!tmp)
			exit(-2);
		L->elem = tmp;
		L->listsize += LISTINCREMENT;
	}
	q = &(L->elem[i - 1]);
	for (p = &(L->elem[L->length - 1]); p >= q; p--)
		*(p + 1) = *p;
	*q = e;
	L->length++;
	return 1;
}

int ListDelete(Sqlist* L, int i, ElemType* e) {
	ElemType *p, *q;
	if (i<1 || i>L->length)
		return 0;
	q = &(L->elem[i - 1]);
	*e = *q;
	for (p = &(L->elem[L->length - 1]), ++q; q <= p; ++q)
		*(q - 1) = *q;
	L->length--;
	return 1;
}

int ListTraverse(Sqlist L, int visitor(ElemType)) {
	for (int i = 0; i < L.length; i++) {
		if (!visitor(L.elem[i]))
			return 0;
	}
	return 1;
}
相关文章