C语言单向链表
胡安民 人气:0链表
链表实现了，内存零碎数据的有效组织。比如，当我们用 malloc 来进行内存申请的时候，当内存足够，但是由于碎片太多，没有连续内存时，只能以申请失败而告终，而用链表这种数据结构来组织数据，就可以解决上类问题。
静态链表
#include <stdio.h>
// 1.定义链表节点
typedef struct node{
int data;
struct node *next;
}Node;
int main(int argc, char *argv[]) {
// 2.创建链表节点
Node a;
Node b;
Node c;
// 3.初始化节点数据
a.data = 1;
b.data = 3;
c.data = 5;
// 4.链接节点
a.next = &b;
b.next = &c;
c.next = NULL;
// 5.创建链表头
Node *head = &a;
// 6.使用链表
while(head != NULL){
int currentData = head->data;
printf("currentData = %i\n", currentData);
head = head->next;//指向下一个节点
}
return 0;
}动态链表
静态链表的意义不是很大，主要原因，数据存储在栈上，栈的存储空间有限，不能动态分配。所以链表要实现存储的自由，要动态的申请堆里的空间。
有头链表
无头链表
单向链表有有头节点和无头节点两种列表, 有头节点在列表的删除,反转,插入等操作会比无头节点简单,但是不好之处就是多占用些空间,而且在多个链表结合处理的时候有头链表每次都需要过滤头节点,而无头链表直接完美融合 ,而且很多高级语言都是无头链表的便于日后的扩展 ,下面都是依据无头节点进行演示
定义链表节点
// 1.定义链表节点
typedef struct node {
void *data;
struct node *next;
} Node;创建链表
/**
* 创建链表
*/
Node *createList() {
// 1.创建头节点
Node *root = (Node *) malloc(sizeof(Node));
root->data = NULL;
root->next = NULL;
//返回头节点
return root;
}
创建一个空节点
/**
* 创建一个空节点
*/
Node *createNode() {
Node *node = (Node *) malloc(sizeof(Node));
node->data = NULL;
node->next = NULL;
return node;
}尾插法
/**
* @brief insertEndNode 尾插法插入节点
* @param head 需要插入的头指针
* @param data 需要插入的数据
*/
void insertEndNode(Node *node, void *data) {
Node *head = node;
//找到数据为空的节点,没有节点那么就扩展
while (head->data != NULL) {
//扩容
if(head->next == NULL) {
Node *pNode = createNode();
head->next = pNode;
head = pNode;
break;
}
head = head->next;
}
//插入数据
head->data = data;
}头插法
/**
* @brief insertHeadNode 头插法插入节点
* @param head 需要插入的头指针
* @param data 需要插入的数据
*/
void insertHeadNode(Node **node, void *data) {
Node *pNode = createNode();
pNode->data = data;
pNode->next = *node;
*node = pNode;
}
指定位置插入一个结点
简单来说就是先找到需要插入的位置,然后将当前位置节点和他前一个节点连接到需要插入的节点就行了
/**
* @brief insertNOde 将数据节点插入到指定数据位置节点,指定数据节点向后移动, 如果没有找到插入的位置,那么就插入到最后
* @param insertionPoint 指定的数据节点
* @param data 需要插入的数据
*/
void insertNode(Node *node ,void *insertionPoint,void *data){
Node *pNode = node;
Node *pre = pNode;//父节点
while (pNode!=NULL){
if(pNode->data == insertionPoint){
break;
}
pre=pNode; //保留当前节点
pNode=pNode->next;
}
//如果没有找到那么就插入到最后
if(pNode==NULL){
insertEndNode(node,data);
return;
}
Node *dataNode = createNode();
dataNode->data= data;
pre->next = dataNode;
dataNode->next = pNode;
}遍历链表
因为我们值存储是使用无类型的指针,所以需要转换为插入时候的类型才行
/**
* @brief printNodeListDouble 遍历链表
* @param node 链表指针头
*/
void printNodeListDouble(Node *node) {
Node *head = node;
while (head!=NULL&&head->data!=NULL){
double *currentData = head->data;
printf("currentData = %f\n", *currentData);
head = head->next;
}
}
获取链表长度
/**
* @brief listLength 计算链表长度
* @param head 链表头指针
* @return 链表长度
*/
int listLength(Node *head){
int count = 0;
head = head;
while(head){
count++;
head = head->next;
}
return count;
}
链表搜索
/**
* @brief searchList 查找指定节点
* @param head 链表头指针
* @param key 需要查找的值
* @return
*/
Node *searchList(Node *head, void *key){
head = head;
while(head){
if(head->data == key){
break;
}else{
head = head->next;
}
}
return head;
}链表数据排序
因为我们存储数据类型是使用无类型的指针,那么在排序的时候需要转换为指定类型才行
/**
* @brief bubbleSort 对链表值进行排序 小到大
* @param head 链表头指针
*/
void sortDouble(Node *head){
// 1.计算链表长度
int len = listLength(head);
// 2.定义变量记录前后节点
Node *cur = head;
while (cur!=NULL){
Node *cur1=cur->next;
while (cur1!=NULL){
//比较大小 ,然后交换数据
if(*((double *)cur->data) > *((double *)cur1->data)){
double *temp = (double *)cur->data;
cur->data = cur1->data;
cur1->data = temp;
}
cur1 = cur1->next;
}
cur= cur->next;
}
}反转链表
断开链表头，然后以头插法的方式将原链表的数据添加链表。
/**
* @brief reverseList 反转链表
* @param head 链表头指针
*/
void reverseList(Node **root){
Node *head = *root;
Node *pre=head, *cur=head->next;
pre->next = NULL;
while (cur!=NULL){
Node *node = cur->next;
cur->next = pre;
pre = cur;
cur=node;
}
*root=pre;
}删除节点数据
先找到需要删除的节点,之后将后一个结点赋值给前一个结点的next,然后将删除位置的结点释放即可
/**
* @brief delNode 删除指定节点
*/
void delNode(Node **root, void *key){
Node *head = *root;
//根节点单独处理
if(head->data == key&&head->next != NULL){
*root = head->next;
free(head->data);
free(head);
return;
}
Node *head1 = head->next;
Node *pre = head;//根节点
while (head1!=NULL){
if(head1->data == key){
pre->next = head1->next;
free(head1->data);
free(head1);
break;
}
pre = head1;//当前节点
head1 = head1->next; //下一个节点
}
}销毁链表
/**
* @brief destroyList 销毁链表
* @param head 链表头指针
*/
void destroyList(Node *head){
Node *cur = head;
while(head != NULL){
cur = head->next;
free(head->data);//清除当前节点数据内存
free(head);//清除当前节点内存
head = cur;
}
}
测试
int main(int argc, char *argv[]) {
//创建链表
Node *head = createList();
//插入数据
printf("insert ====================\n");
double *f = (double *)malloc(sizeof(double));
*f=2.1;
insertEndNode(head, f);
double *f1 = (double *)malloc(sizeof(double));
*f1=1.1;
insertEndNode(head, f1);
double *f2= (double *)malloc(sizeof(double));
*f2=0.1;
insertEndNode(head, f2);
double *f3= (double *)malloc(sizeof(double));
*f3=3.1;
insertHeadNode(&head, f3);
double *se = (double *)malloc(sizeof(double));
*se=111.1;
double *f4= (double *)malloc(sizeof(double));
*f4=7.1;
insertNode(head,se, f4);
free(se);
printNodeListDouble(head);
//获取长度
printf("listLength ====================\n");
int i = listLength(head);
printf("listLength = %d\n", i);
//搜索
printf("searchList ====================\n");
Node *pNode = searchList(head, f1);
printf("currentData = %f\n", *((double *)pNode->data));
//排序
printf("sortDouble ====================\n");
sortDouble(head);
printNodeListDouble(head);
//反转
printf("reverseList ====================\n");
reverseList(&head);
printNodeListDouble(head);
//删除节点
printf("delNode ====================\n");
delNode(&head, f1);
printNodeListDouble(head);
//销毁
destroyList(head);
return 0;
}
加载全部内容