链表之链式存储
链表之链式存储
用户1154259
发布于 2018-01-18 10:14:33
发布于 2018-01-18 10:14:33
优点：
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 }运行结果
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-01-26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。