1.总结
说到数据结构，第一个想到的就是链表，因为后面所以的数据结构都是可以通过链表的形式实现。
2.时间复杂度
说到算法，第一个想到的就是效率问题，让我们简单看下时间复杂度：如果一个算法用常数时间（O（1））将问题的大小消减为其一部分（通常是二分之一），那木该算法就是O(logN)，如果使用常数时间只是把问题减少一个常数（如将问题减少1），那木这种算法就是O（N）。
3.单链表（为了方便分析，链表都是带有头结点数据域不存放值）
代码实现如下（每个函数传入指针默认不是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
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
|
node.h
#ifndef _LIST_
#define _LIST_
typedef
struct
node{
int
Data;
struct
node *Next;
}*Pnode,Node;
int
IsEmpty(Pnode L);
int
IsLast(Pnode L);
Pnode Find(
int
X,Pnode L);
void
Delete(
int
X,Pnode L);
Pnode FindPrevious(
int
X,Pnode L);
void
HeadInsert(
int
X,Pnode L,Pnode P);
void
TialInsert(
int
X,Pnode L,Pnode P);
void
DisplayList(Pnode L);
Pnode MallocNode();
#endif
node.c
#include<stdio.h>
#include<stdlib.h>
#include"node.h"
/*申请节点*/
Pnode MallocNode()
{
Pnode P = (Pnode)
malloc
(
sizeof
(Node));
if
(NULL != P)
{
return
P;
}
else
{
return
NULL;
}
}
/*判断是否为空*/
int
IsEmpty(Pnode L)
{
if
(L->Next == NULL)
{
return
0;
}
return
-1;
}
/*判断是否是最后一个节点*/
int
IsLast(Pnode L)
{
if
(L->Next == NULL)
{
return
0;
}
return
-1;
}
/*查找数据域为X的节点*/
Pnode Find(
int
X,Pnode L)
{
Pnode P = L->Next;
if
(0 == IsEmpty(L))
{
printf
(
"list is empty!\n"
);
return
NULL;
}
while
(P != NULL && P->Data != X)
P = P->Next;
return
P;
}
/*查找数据域为X的前驱节点*/
Pnode FindPrevious(
int
X,Pnode L)
{
Pnode P = L;
if
(0 == IsEmpty(L))
{
printf
(
"list is empty!\n"
);
return
NULL;
}
while
(P->Next != NULL && P->Next->Data != X )
P = P->Next;
return
P;
}
/*删除数据为X的节点*/
void
Delete(
int
X,Pnode L)
{
Pnode P,Temp;
if
(0 == IsEmpty(L))
{
printf
(
"list is empty!\n"
);
return
;
}
P = FindPrevious(X,L);
if
(0 != IsLast(P))
{
Temp = P->Next;
P->Next = Temp->Next;
free
(Temp);
}
else
{
printf
(
"no find data!\n"
);
return
;
}
}
/*头插*/
void
HeadInsert(
int
X,Pnode L,Pnode P)
{
P->Data = X;
if
(NULL == L->Next)
{
L->Next = P;
P->Next = NULL;
}
else
{
P->Next = L->Next;
L->Next = P;
}
}
/*尾插*/
void
TialInsert(
int
X,Pnode L,Pnode P)
{
P->Data = X;
P->Next = NULL;
Pnode T = L;
while
(NULL != T->Next)
T = T->Next;
T->Next = P;
}
/*显示链表*/
void
DisplayList(Pnode L)
{
Pnode P = L->Next;
while
(NULL != P)
{
printf
(
" %d"
,P->Data);
P = P->Next;
}
}
|
4.双向链表
5.双向循环链表
双向链表和双向循环链表以后用到再实现，上面的结构不对，应该有前驱指针。
|
1
2
3
4
5
|
struct
Node{
Ele Data;
struct
Node *Tail;
struct
Node *Next;
}
|
本文转自 8yi少女的夢 51CTO博客，原文链接：http://blog.51cto.com/zhaoxiaohu/1963104，如需转载请自行联系原作者
