数据结构笔记

本文最后更新于:2021年10月17日 晚上

摘要
首页显示摘要内容(替换成自己的)

P1 线性表

L1 顺序表示

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
//顺序表
#include <stdio.h>

#define MAXSIZE 10
#define ERROR 0
#define SUCCESS 1

typedef int DataType;

//定义顺序表
typedef struct seqList_l {
DataType data[MAXSIZE]; //数据项
int length;
} seqList; //基本元素

//初始化空表
void initList(seqList *L) {
L->length = 0;
}

//初始化非空表
int creatList(seqList *L, const DataType r[], int n) {
if (n < 0 || n > MAXSIZE) {
printf("存储空间不足");
return ERROR;
}
for (int i = 0; i < n; ++i) {
L->data[i] = r[i];
}
L->length = n;
return SUCCESS;
}

//判空
int isEmpty(seqList *L) {
if (L->length == 0)return ERROR; else return SUCCESS;
}

//求表长
int length(seqList *L) {
return L->length;
}

//遍历表
void printList(seqList *L) {
for (int i = 0; i < L->length; ++i) {
printf("%d ", L->data[i]);
}
puts("");
}

//查找值
DataType get(seqList *L, int i) {
if (i < 0 || i > L->length) return ERROR;
return L->data[i - 1];
}

//查找元素位置
int locate(seqList *L, DataType x) {
for (int i = 0; i < L->length; ++i) {
if (L->data[i] == x) return i + 1;
}
return ERROR;
}

//插入算法
int insert(seqList *L, int i, DataType x) {
if (L->length >= MAXSIZE || i > L->length) {
puts("location error");
return ERROR;
}
for (int j = L->length; j > i - 1; j--) {
L->data[j] = L->data[j - 1];
}
L->data[i - 1] = x;
L->length++;
return SUCCESS;
}

//删除算法
int delete(seqList *L, int i) {
if (i < 1 || i > L->length) {
puts("location error");
return ERROR;
}
for (int j = i - 1; j < L->length - 1; ++j) {
L->data[j] = L->data[j + 1];
}
L->length--;
return SUCCESS;
}

//逆转算法
int reverse(seqList *L) {
DataType t;
for (int i = 0; i < L->length / 2; ++i) {
t = L->data[i];
L->data[i] = L->data[L->length - 1 - i];
L->data[L->length - 1 - i] = t;
}
return SUCCESS;
}

int reverseX(seqList *L, int start, int end) {
if (start < 1 || start > L->length || end < 1 || end > L->length) {
puts("location error");
return ERROR;
}
DataType t;
for (int i = start - 1, j = end - 1; i < j; ++i, --j) {
t = L->data[i];
L->data[i] = L->data[j];
L->data[j] = t;
}
return SUCCESS;
}

//循环
int move(seqList *L, int start, int end, int step) {
if (start >= end || start < 1 || start > L->length || end < 1 || end > L->length) {
puts("区间位置异常");
return ERROR;
}
step = step % (end - start + 1);
reverseX(L, start, start + step - 1);
reverseX(L, start + step, end);
reverseX(L, start, end);
return SUCCESS;
}

//奇偶分类
int divide(seqList *L) {
int i = 0, j = L->length - 1;
while (i < j) {
while (L->data[i] % 2 == 0)i++;
while (L->data[j] % 2 == 1)j--;
if (i < j) {
int t = L->data[i];
L->data[i] = L->data[j];
L->data[j] = t;
}

}
return SUCCESS;
}

int main() {
// seqList L;
// initList(&L);
// int a[MAXSIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// creatList(&L, a, 10);
// if (isEmpty(&L)) puts("not empty");
// else puts("empty");
// printf("%d\n", length(&L));
// printList(&L);
// insert(&L, 5, 99);
// printList(&L);
// delete(&L, 1);
// printList(&L);
// reverse(&L);
// printList(&L);
// reverseX(&L, 3, 5);
// move(&L, 6, 10, 5);
// printList(&L);
// divide(&L);
// printList(&L);
return 0;
}

L2 链式表示

参考文章:
参考链接


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!