优点:
1 空间存储方便,现用现申请
2 插入删除,只针对单一数据,不需要移动大量数据
缺点:
1 读取,插入,删除慢,需要从头查找,时间复杂度均为O(n)
typedef struct Node{
int data;
struct Node * next;
}Node;
int main(){
...
Node *p = (Node *)malloc(sizeof(Node));
p->data = 1;
...
}
void getNode(Node *L,int n,Node *tar){
int i=1;
Node *p;
p=L->next;
while(p && i<n){
p=p->next;
i++;
}
if(!p || i>n)
printf("error!");
tar->data=p->data;
}
链表不能直接删除头结点,此时元素节点仍在使用中。
void clearList(Node *L){
Node *p,*q;
p=L->next;
while(p){
q=p->next;
free(p);
p=q;
}
L->next=NULL;
}
int insertNode(Node *L,int n,int num){
int i=1;
Node *p = L->next;
while( p && i<n-1){
p=p->next;
i++;
}
if(!p || i>n-1)
return 0;
Node *q = (Node *)malloc(sizeof(Node));
q->data = num;
q->next = p->next;
p->next = q;
return 1;
}
int deleteNode(Node *L,int n){
int i=1;
Node *p = L->next;
Node *q;
while( p->next && i<n-1){
p=p->next;
i++;
}
if( !(p->next) || i>n-1)
return 0;
q=p->next;
p->next = q->next;
free(q);
return 1;
}
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 typedef struct Node{
5 int data;
6 struct Node * next;
7 }Node;
8
9 void createList(Node * L,int len);
10 void showList(Node *L);
11 void clearList(Node *L);
12 void getNode(Node *L,int n,Node *tar);
13 int insertNode(Node *L,int n,int num);
14 int deleteNode(Node *L,int n);
15
16 int main()
17 {
18 Node *L= (Node *)malloc(sizeof(Node));
19
20 createList(L,5);
21 showList(L);
22
23 Node *tar= (Node *)malloc(sizeof(Node));
24 getNode(L,3,tar);
25 printf("the third is:%d\n",tar->data);
26
27 if(insertNode(L,3,0))
28 showList(L);
29
30 if(deleteNode(L,3))
31 showList(L);
32
33 clearList(L);
34 showList(L);
35
36 return 0;
37 }
38
39 void createList(Node * L,int len){
40 int i;
41 Node * p;
42 L->next = NULL;
43 for(i=0;i<len;i++){
44 p = (Node *)malloc(sizeof(Node));
45 p->data = 2*i+1;
46 p->next = L->next;
47 L->next = p;
48 }
49 }
50
51 void showList(Node *L){
52 Node *p = (Node *)malloc(sizeof(Node));
53 p=L->next;
54 while(p){
55 printf("%d->",p->data);
56 p=p->next;
57 }
58 printf("null\n");
59 free(p);
60 }
61
62 void clearList(Node *L){
63 Node *p,*q;
64 p=L->next;
65 while(p){
66 q=p->next;
67 free(p);
68 p=q;
69 }
70 L->next=NULL;
71 }
72
73 void getNode(Node *L,int n,Node *tar){
74 int i=1;
75 Node *p;
76 p=L->next;
77 while(p && i<n){
78 p=p->next;
79 i++;
80 }
81 if(!p || i>n)
82 printf("error!");
83 tar->data=p->data;
84 }
85
86 int insertNode(Node *L,int n,int num){
87 int i=1;
88 Node *p = L->next;
89 while( p && i<n-1){
90 p=p->next;
91 i++;
92 }
93 if(!p || i>n-1)
94 return 0;
95 Node *q = (Node *)malloc(sizeof(Node));
96 q->data = num;
97 q->next = p->next;
98 p->next = q;
99 return 1;
100 }
101
102 int deleteNode(Node *L,int n){
103 int i=1;
104 Node *p = L->next;
105 Node *q;
106 while( p->next && i<n-1){
107 p=p->next;
108 i++;
109 }
110 if( !(p->next) || i>n-1)
111 return 0;
112 q=p->next;
113 p->next = q->next;
114 free(q);
115 return 1;
116 }