链表的开发实现

链表的开发实现

普通实现

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct _LINKNODE {
struct _LINKNODE *next;

} LinkNode;

typedef struct _LINKLIST {
LinkNode linkHeader;
int linkNodeSize;
} LinkLists;


typedef void *LinkList;

LinkList LINKLIST_INIT() {

LinkLists *list = malloc(sizeof(LinkLists));

if (list == NULL) {
return NULL;
}

list->linkHeader.next = NULL;
list->linkNodeSize = 0;

return list;
}


void LINKLIST_INSERT(LinkList list, int pos, void *data) {

if (list == NULL || data == NULL) {

printf("Failed");
return;
}

LinkLists *lists = list;
if (pos < 0 || pos > lists->linkNodeSize) {
pos = lists->linkNodeSize;
}

// 数据的前四个字节存放的指针,将其强转为LinkNode指针。
LinkNode *node = data;

LinkNode *p = &lists->linkHeader;

for (int i = 0; i < pos; i++) {
p = p->next;
}


node->next = p->next;
p->next = node;

lists->linkNodeSize++;

}


void PRINTF_LINKNODE(LinkList list, void(*print)(void *)) {

if (list == NULL) {
return;
}

LinkLists *lists = list;
LinkNode *node = lists->linkHeader.next;


for (int i = 0; i < lists->linkNodeSize; i++) {
print(node);
node = node->next;

}

}

void LINKLIST_DELETEBYPOS(LinkList list, int pos) {

LinkLists *lists = list;

if (list == NULL || pos < 0 || pos > lists->linkNodeSize) {
return;
}

LinkNode *qNode = &lists->linkHeader;

for (int i = 0; i < pos; i++) {
qNode = qNode->next;
}

LinkNode *delNode = qNode->next;

qNode->next = delNode->next;
lists--;

}


typedef struct _PERSON {
void *node;
char name[64];
int age;
} Person;


void myPrintPerson(void *data) {
Person *p = data;
printf("姓名: %s 年龄: %d \n", p->name, p->age);
}

void test01() {

//初始化链表
LinkList mylist = LINKLIST_INIT();

//创建数据
Person p1 = {NULL, "aaa", 10};
Person p2 = {NULL, "bbb", 20};
Person p3 = {NULL, "ccc", 30};
Person p4 = {NULL, "ddd", 40};
Person p5 = {NULL, "eee", 50};

//插入节点
LINKLIST_INSERT(mylist, 0, &p1);
LINKLIST_INSERT(mylist, 2, &p2);
LINKLIST_INSERT(mylist, 1, &p3);
LINKLIST_INSERT(mylist, -1, &p4);
LINKLIST_INSERT(mylist, 0, &p5);

//遍历
PRINTF_LINKNODE(mylist, myPrintPerson);
printf("=-=-=-=-=-=-=-=-=-=-=-=\n");

LINKLIST_DELETEBYPOS(mylist, 1);
PRINTF_LINKNODE(mylist, myPrintPerson);

}

void LINKNODE_RESET(LinkList list) {

LinkLists *lists = list;
lists->linkHeader = NULL;

}

void LINKNODE_DESTORY(LinkList list) {

if (list == NULL) {
return;
}

free(list);

list = NULL;

}


int main(int argc, char *argv[]) {

test01();

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct stackNode {
struct stackNode *next;
} StackNode;

struct LStack {
StackNode nodeHead;
int nodesize;
};


typedef void *LinkStack;


LinkStack init_LinkStack() {
struct LStack *stack = malloc(sizeof(struct LStack));

if (stack == NULL) {
return NULL;
}

stack->nodeHead.next = NULL;
stack->nodesize = 0;

return stack;
}


// 对于链表而言,入栈本质为头插
void push_LinkStack(LinkStack s, void *data) {
if (s == NULL || data == NULL) {
return;
}

struct LStack *stack = s;

// 将用户数据取出钱四个字节用于地址。

StackNode *node = data;


// 更改指针指向
node->next = stack->nodeHead.next;
stack->nodeHead.next = node;

stack->nodesize++;


}

void pop_LinkStack(LinkStack s) {
if (s == NULL) {
return;
}

struct LStack *stack = s;


if (stack->nodesize == 0) {
return;
}


StackNode *firstNode = stack->nodeHead.next;

stack->nodeHead.next = firstNode->next;

stack->nodesize--;

}

void *top_LinkStack(LinkStack s) {
if (s == NULL) {
return NULL;
}

struct LStack *stack = s;


if (stack->nodesize == 0) {
return NULL;
}

return stack->nodeHead.next;

}

int size_LinkStack(LinkStack s) {
if (s == NULL) {
return 0;

}

struct LStack *stack = s;

return stack->nodesize;


}

int isEmpty_Linstack(LinkStack s) {
if (s == NULL) {
return 0;
}

struct LStack *stack = s;


if (stack->nodesize == 0) {
return 1;
}

return 0;

}

void destoryLinkStack(LinkStack s) {

if (s == NULL) {
return;

}

free(s);

}


//测试
struct Person {
void *node;
char name[64];
int age;
};

void test01() {
//初始化栈
LinkStack myStack = init_LinkStack();

//创建数据
struct Person p1 = {NULL, "aaa", 10};
struct Person p2 = {NULL, "bbb", 20};
struct Person p3 = {NULL, "ccc", 30};
struct Person p4 = {NULL, "ddd", 40};
struct Person p5 = {NULL, "eee", 50};

//入栈
push_LinkStack(myStack, &p1);
push_LinkStack(myStack, &p2);
push_LinkStack(myStack, &p3);
push_LinkStack(myStack, &p4);
push_LinkStack(myStack, &p5);

printf("链式存储 -- 栈的元素个数为:%d\n", size_LinkStack(myStack));

//栈不为空,查看栈顶元素,出栈
while (isEmpty_Linstack(myStack) == 0) {
struct Person *p = top_LinkStack(myStack);
printf("姓名:%s 年龄:%d\n", p->name, p->age);

//出栈
pop_LinkStack(myStack);
}

printf("链式存储 -- 栈的元素个数为:%d\n", size_LinkStack(myStack));

//销毁栈
destoryLinkStack(myStack);
}


int main(int argc, char *argv[]) {

test01();
return 0;
}