内容概括:
一、链表简介及创建列表
二、添加节点
三、链表排序
代码编译平台:
CentOS 6.4 64b
一、链表简介及创建列表:
传统数组缺点:
传统数组长度需要事先设定,不能改变,内存由系统自动分配,函数调用结束后系统自动回收,不能跨函数调用。
链表:
内存空间不要求连续,增删操作灵活。
链表由头指针、头结点、首节点、普通节点和尾节点组成。
每个节点有两个部分,一个是数据,一个是存放下一个节点的节点指针。
头指针:指向头结点的指针,通过头指针便可对链表进行所有操作。
头结点:链表的第一个节点,其不存放有效数据,其指针指向首节点。
首节点:第一个存放有效数据的节点。
尾节点:存放有效数据,但其指针是空(NULL)。
注:除头结点之外,其他都是有效节点,如果只有头结点,即头结点的指针为空,则表示此链表为空链表。
节点的结构体
struct NODE { int data; struct NODE * pNext; };
通过CreateList函数实现链表的创建。
首先创建出头指针和头节点,并创建操作指针pOperate方便后续操作,代码如下:
struct NODE * pMntHead = (struct NODE *) malloc(sizeof(struct NODE *)) ; struct NODE * pOperate = pMntHead; pOperate->pNext = NULL;
创建节点:
创建数据节点和临时节点指针pMnt,实用此指针完成数据节点的数据存储
int value; //通过用户输入取值 struct NODE * pMnt = (struct NODE *) malloc(sizeof(struct NODE *)); pMnt->data = value;
节点连接:
将数据节点的指针置空(将每个新节点当做尾节点看待),并将链表的尾节点指向此节点(节点连接)
pMnt->pNext = NULL; pOperate->pNext = pMnt;
最后移动pOperate指针,准备添加下一个节点
pOperate = pMnt;
至此,一个只有一个数据节点的链表就添加完成了,其他数据节点类似操作, 完整代码如下:
#include <stdio.h> #include <malloc.h> struct NODE { int data; struct NODE * pNext; }; //定义节点 struct NODE * CreateList(void); //创建链表,并返回链表地址 void ShowList(const struct NODE *); //显示链表数据 int main(void) { struct NODE * pHead; pHead = CreateList(); ShowList(pHead); printf("\n"); ; } struct NODE * CreateList(void) { int list_len; int i; int value; struct NODE * pMntHead = (struct NODE *) malloc(sizeof(struct NODE *)) ; //创建头指针和头结点 struct NODE * pOperate = pMntHead; pOperate->pNext = NULL; printf("Input the list length: "); scanf("%d", &list_len); ; i<list_len; i++) { printf("Input the value of %d : ", i); scanf("%d", &value); struct NODE * pMnt = (struct NODE *) malloc(sizeof(struct NODE *)); //创建一个新的数据节点 pMnt->data = value; pMnt->pNext = NULL; pOperate->pNext = pMnt; //连接节点 pOperate = pMnt; } return pMntHead; //返回所创建链表的头结点地址 } // 显示一个链表的所有内容 void ShowList(const struct NODE * pMntHead) { while(pMntHead->pNext != NULL) { pMntHead = pMntHead->pNext; printf("%d ", pMntHead->data); } }
演示:
[root@ly ~]# [root@ly ~]# ls x.c [root@ly ~]# gcc x.c [root@ly ~]# ls a.out x.c [root@ly ~]# ./a.out Input the list length: Input the value of : Input the value of : Input the value of : Input the value of : Input the value of : [root@ly ~]# [root@ly ~]#
二、添加节点:
思路:
创建新节点,然后遍历整个链表找到尾节点并连接到新节点。
代码:
void AddValue(struct NODE * pMntHead, int new_value) { struct NODE * pMnt = (struct NODE *) malloc(sizeof(struct NODE *)); pMnt->data = new_value; pMnt->pNext = NULL; while(pMntHead->pNext != NULL) pMntHead = pMntHead->pNext; pMntHead->pNext = pMnt; }
main函数代码如下:
#include <stdio.h> #include <malloc.h> struct NODE { int data; struct NODE * pNext; }; struct NODE * CreateList(void); //参考链表创建文 void ShowList(const struct NODE *); //参考链表创建文 void AddValue(struct NODE *, int); int main(void) { struct NODE * pHead; pHead = CreateList(); ShowList(pHead); printf("\n"); AddValue(pHead, ); ShowList(pHead); printf("\n"); ; }
演示:
[root@ly ~]# [root@ly ~]# ./a.out Input the list length: Input the value of : Input the value of : Input the value of : Input the value of : [root@ly ~]# [root@ly ~]#
三、链表排序:
思路:
将链表的所有节点通过数组保存,通过数组进行升序排列,最后重新组合链表。
函数代码如下:
void SortList(struct NODE * pHead) { ; struct NODE * tmp, * pMntHead; pMntHead = pHead; // 获取链表有效节点的长度(个数) while(pMntHead->pNext != NULL) { pMntHead = pMntHead->pNext; arry_len++; } pMntHead = pHead; //操作指针复位 // 动态创建相应长度的节点指针数组 struct NODE ** node_addrs = (struct NODE **) malloc(arry_len * sizeof(struct NODE *)); //将节点地址保存到指针数组中 ; i<arry_len; i++) { node_addrs[i] = pMntHead->pNext; pMntHead = pMntHead->pNext; } //对数组进行重新排序 ; i<arry_len; i++) ; j<arry_len--i; j++) ]->data) { tmp = node_addrs[j]; node_addrs[j] = node_addrs[j+]; node_addrs[j+] = tmp; } pMntHead = pHead; // 重新连接各节点 ; i<arry_len; i++) { pMntHead->pNext = node_addrs[i]; pMntHead = node_addrs[i]; } pMntHead->pNext = NULL; free(node_addrs); }
全部代码:
#include <stdio.h> #include <malloc.h> struct NODE { int data; struct NODE * pNext; }; struct NODE * CreateList(void); void ShowList(const struct NODE *); void SortList(struct NODE *); int main(void) { struct NODE * pHead; pHead = CreateList(); ShowList(pHead); printf("\n"); SortList(pHead); ShowList(pHead); printf("\n"); ; } void SortList(struct NODE * pHead) { ; struct NODE * tmp, * pMntHead; pMntHead = pHead; while(pMntHead->pNext != NULL) { pMntHead = pMntHead->pNext; arry_len++; } pMntHead = pHead; struct NODE ** node_addrs = (struct NODE **) malloc(arry_len * sizeof(struct NODE *)); ; i<arry_len; i++) { node_addrs[i] = pMntHead->pNext; pMntHead = pMntHead->pNext; } ; i<arry_len; i++) ; j<arry_len--i; j++) ]->data) { tmp = node_addrs[j]; node_addrs[j] = node_addrs[j+]; node_addrs[j+] = tmp; } pMntHead = pHead; ; i<arry_len; i++) { pMntHead->pNext = node_addrs[i]; pMntHead = node_addrs[i]; } pMntHead->pNext = NULL; free(node_addrs); } struct NODE * CreateList(void) { int list_len; int i; int value; // create head point and the first node struct NODE * pMntHead = (struct NODE *) malloc(sizeof(struct NODE *)) ; struct NODE * pOperate = pMntHead; pOperate->pNext = NULL; printf("Input the list length: "); scanf("%d", &list_len); ; i<list_len; i++) { printf("Input the value of %d : ", i); scanf("%d", &value); struct NODE * pMnt = (struct NODE *) malloc(sizeof(struct NODE *)); pOperate->pNext = pMnt; pOperate = pMnt; pOperate->data = value; pOperate->pNext = NULL; } return pMntHead; } void ShowList(const struct NODE * pMntHead) { while(pMntHead->pNext != NULL) { pMntHead = pMntHead->pNext; printf("%d ", pMntHead->data); } }
演示:
[root@ly ~]# [root@ly ~]# [root@ly ~]# gcc a.c [root@ly ~]# ./a.out Input the list length: Input the value of : Input the value of : Input the value of : Input the value of : Input the value of : Input the value of : Input the value of : Input the value of : Input the value of : Input the value of : [root@ly ~]# [root@ly ~]# [root@ly ~]#