1. 首页
  2. 文章中心
  3. C

C语言实现LinkedList链表数据结构

90 阅读 0 评论
我是靠谱客的博主 朴实时光，这篇文章主要介绍C语言实现LinkedList链表数据结构，现在分享给大家，希望可以做个参考。

链表基本的就是一个数据域一个指针域，数据域存储你的数据，指针域就指向你下一个节点的内存地址。

示意图(画的很粗糙,请见谅)
这里写图片描述

  • 链表的特点：
    • 增删快 (修改元素时，只需要改变指针域指向就可以了)
    • 查询慢 (元素之前内存地址不连续，只能挨个挨个遍历查找)

我们现在就来实现一个非循环单链表

  • 首先写出链表的结构体：
复制代码
1
2
3
4
5
6
7
typedef struct Node{ //非循环单链表结构体
    int data; //数据区域

    Node * pNext; // 指针指向下一个节点


} NODE,*PNODE;
  • 然后我们初始化出一个头结点
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 PNODE initLinkedList(){


    PNODE pHead = (PNODE)malloc(sizeof(NODE));//头结点不存放数据

    if( NULL == pHead ){
        printf("%sn","动态分配内存失败，程序退出");
        exit(-1);
    }

    pHead->pNext = NULL;

    return pHead;
}
  • 然后再是添加新节点的方法
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
PNODE addElement(PNODE pTail,int val){

    PNODE pNew = (PNODE)malloc(sizeof(NODE)); //创建新节点
    if(NULL == pNew ){
        printf("%sn","追加节点动态分配内存失败，退出程序");
        exit(-1);
    }


    pNew->data = val; //给新节点赋值
    pNew->pNext = NULL; //新节点的下一个节点为NULL
    pTail->pNext = pNew; // 将pNew节点挂在pTail后面
    length += 1;//节点有效个数加1

    return pNew;//返回最后一个节点
}
  • 遍历链表
复制代码
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

bool isEmpty(PNODE pNode){

    if(NULL == pNode->pNext){
        printf("%sn","pNode is null");
        return true;
    }

    return false;
}

void loopElement(PNODE pNode){
    if(isEmpty(pNode)){
        return;//为空直接返回
    }

    PNODE p = pNode->pNext;
    printf("%sn","start loop");

    while(NULL != p){
        printf("%dn",p->data);
        p = p->pNext;
    }

    printf("%sn","end loop");

}
  • 然后在加一个main方法测试
    • 记得要加入这三个头文件运行
复制代码
1
2
3
#include <stdio.h> /* 基础头文件*/
#include <malloc.h> /*动态分配内存头文件*/
#include <stdbool.h>  /*返回布尔值的头文件*/
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

int main(){
    printf("%sn" ,"start");

    PNODE  pHead = initLinkedList();

    /*addElement start */

    PNODE node = addElement(pHead,1);//追加到pHead节点下
    PNODE node2 = addElement(node,2);//追加到node节点下
    PNODE node3 = addElement(node2,4);//......
    PNODE node4 = addElement(node3,3);//......

    /*addElement end */

    loopElement(pHead);

    printf("length: %dn",length);


    printf("%sn" ,"end");
    //getchar();
  return 0; 
}

此时一个非循环单链表的功能基本上有了，现在附上全部的代码：
LinkedList.c

复制代码
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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
#include <stdio.h> /* 基础头文件*/
#include <malloc.h> /*动态分配内存头文件*/
#include <stdbool.h>  /*返回布尔值的头文件*/


/***
*zhouzhongqing
*链表List
*2017年10月28日14:56:19
*/



typedef struct Node{ //非循环单链表结构体
    int data; //数据区域

    Node * pNext; // 指针指向下一个节点


} NODE,*PNODE;


PNODE last; //声明每次添加节点后的最后一个节点



int length; //节点有效个数

/***
*方法声明
**/

/**
*初始化，动态分配内存
**/
PNODE initLinkedList();

/***
*添加节点
**/
PNODE addElement(PNODE pTail,int val);

/***
*添加节点 使用声明最后一个节点的方式
**/
void addElementLast(PNODE pTail,int val);


/**
*遍历所有节点
**/
void loopElement(PNODE pNode);


/***
*测试添加节点
**/
PNODE addElementTest();


/**
*判断是否为空         空返回true 非空返回 false
*/
bool isEmpty(PNODE pNode);


/**
*排序 ,冒泡排序
**/
void sortList(PNODE pNODE);



/**
*检查输入的下标是否越界 越界返回false 否则为成功true
*/
bool checkElementIndex(int index);



/**
*通过下标获取节点 从0开始
**/
PNODE get(PNODE pNode,int index);





int main(){
    printf("%sn" ,"start");

    PNODE  pHead = initLinkedList();

    /*addElement start */
    /*
    PNODE node = addElement(pHead,1);//追加到pHead节点下
    PNODE node2 = addElement(node,2);//追加到node节点下
    PNODE node3 = addElement(node2,4);//......
    PNODE node4 = addElement(node3,3);//......
    */
    /*addElement end */


    /*addElementLast start */
    addElementLast(pHead,1);
    addElementLast(pHead,5);
    addElementLast(pHead,8);
    addElementLast(pHead,4);

    /*addElementLast end */


    //排序
    sortList(pHead);




    loopElement(pHead);


    //get 
    //PNODE node = get(pHead,4);
    //printf("node->data : %dn",node->data);


    printf("length: %dn",length);



    //loopElement(addElement2());

    printf("%sn" ,"end");
    //getchar();
  return 0; 
}




bool checkElementIndex(int index){
     return index >= 0 && index < length;
}





void sortList(PNODE pNODE){
    if(isEmpty(pNODE)){
        return ;
    }

    int i,j,t;

    PNODE p,q;

     for(i=0,p=pNODE->pNext;i<length-1;++i,p=p->pNext){
        printf("p->data-1 : %d,%dn",p->data,p->data);
        for(j=i+1,q=p->pNext;j<length;++j,q=q->pNext) {
            printf("q->data-2 :%d,%dn",q->data,q->data);
             if(p->data>q->data) {//类似于数组中的：a[i]>a[j]
                    //数据位置相互转换，大的p->data放在后面的位置 小的q->data放在前面的位置
                     t=p->data;//类似于数组中的：     t=a[i];
                     p->data=q->data;//类似于数组中的： a[i]=a[j];
                     q->data=t;//类似于数组中的：     a[j]=t;
            }
         }
     }

     //loopElement(pNODE);

}


PNODE get(PNODE pNode, int index){

     if(isEmpty(pNode)){
        return NULL;
     }

     if(!checkElementIndex(index)){
        printf("%s index = %dn","index outOf bounds exception :" ,index);
        return NULL;
     }

     int i = 0;
     PNODE p = pNode;

     while(NULL!=p->pNext&&i<index)
     {
           p=p->pNext;
           ++i;
     }


     PNODE q = p->pNext;

    return q;
}






bool isEmpty(PNODE pNode){

    if(NULL == pNode->pNext){
        printf("%sn","pNode is null");
        return true;
    }

    return false;
}




void addElementLast(PNODE pTail,int val){
    if(NULL != last){
        pTail = last;
    //  printf("%sn", "如果不是添加第一个数据节点pTail改为最后一个节点");
    }

    PNODE pNew = (PNODE)malloc(sizeof(NODE));//创建新节点
    if(NULL == pNew ){
        printf("%sn","addElementJDK方法追加节点动态分配内存失败，退出程序");
        exit(-1);
    }

    pNew->data = val; //给新节点赋值
    pNew->pNext = NULL; //新节点的下一个节点为NULL
    pTail->pNext = pNew; // 将pNew节点挂在pTail后面
    length += 1;//节点有效个数加1

    last = pNew;//将节点置为最后一个节点，这个写法我参考的jdk7的LinkedList源码的基本思路
}



PNODE addElement(PNODE pTail,int val){

    PNODE pNew = (PNODE)malloc(sizeof(NODE)); //创建新节点
    if(NULL == pNew ){
        printf("%sn","追加节点动态分配内存失败，退出程序");
        exit(-1);
    }


    pNew->data = val; //给新节点赋值
    pNew->pNext = NULL; //新节点的下一个节点为NULL
    pTail->pNext = pNew; // 将pNew节点挂在pTail后面
    length += 1;//节点有效个数加1

    return pNew;//返回最后一个节点
}




void loopElement(PNODE pNode){
    if(isEmpty(pNode)){
        return;//为空直接返回
    }

    PNODE p = pNode->pNext;
    printf("%sn","start loop");

    while(NULL != p){
        printf("%dn",p->data);
        p = p->pNext;
    }

    printf("%sn","end loop");

}




 PNODE initLinkedList(){


    PNODE pHead = (PNODE)malloc(sizeof(NODE));//头结点不存放数据

    if( NULL == pHead ){
        printf("%sn","动态分配内存失败，程序退出");
        exit(-1);
    }

    pHead->pNext = NULL;

    return pHead;
}



/**
*zhouzhongqing
*测试方法
*2017年10月31日14:01:32
**/

  PNODE addElementTest(){



       int len;//用来存放有效节点的个数

       int val = 1;//用来临时存放用户输入的节点的值
       int val2 = 2;//用来临时存放用户输入的节点的值
      //分配了一个不存放有效数据的头节点
       PNODE  pHead = initLinkedList();
       if(NULL==pHead)
       {
                printf("分配失败，程序终止！n");
                exit(-1);
       }
       PNODE pTail=pHead;
       pTail->pNext=NULL;

        PNODE pNew=(PNODE)malloc(sizeof(NODE));
        if(NULL==pNew)
        {
                 printf("分配失败，程序终止！n");
                 exit(-1);
        }
        pNew->data=val;//挂
        pNew->pNext=NULL;
        pTail->pNext=pNew;
        pTail=pNew;
        len++;


         PNODE pNew2=(PNODE)malloc(sizeof(NODE));
        if(NULL==pNew2)
        {
                 printf("分配失败，程序终止！n");
                 exit(-1);
        }
        pNew2->data=val2;//挂
        pNew2->pNext=NULL;
        pTail->pNext=pNew2;
        pTail=pNew;

        len++;

     return pHead;
 }

最后

以上就是朴实时光最近收集整理的关于C语言实现LinkedList链表数据结构的全部内容，更多相关C语言实现LinkedList链表数据结构内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(60)

相关文章

C#学习单向链表和接口 IList<T>
C#学习单向链表和接口 IList
手写LinKedList双向链表 终于搞清了什么是链表结构
手写LinKedList双向链表 终于搞清了什么是链表结构
Java数据结构-2 链表，模拟LinkedList实现
Java数据结构-2 链表，模拟LinkedList实现
链表的简单应用学生管理系统
链表的简单应用学生管理系统
C语言实现LinkedList链表数据结构
C语言实现LinkedList链表数据结构
链表 相关操作思路
链表 相关操作思路
关于MySQL数据库对敏感数据的加密的实现一、单向加密二、双向加密
关于MySQL数据库对敏感数据的加密的实现一、单向加密二、双向加密
链表题主要思路
链表题主要思路

评论列表共有 0 条评论

立即
投稿
返回
顶部