c语言——数据结构【链表：单向链表】

 上篇→快速掌握C语言——数据结构【创建顺序表】多文件编译-CSDN博客

一、链表

二、单向链表

2.1 概念

2.2 单向链表的组成

2.3 单向链表节点的结构体原型

//类型重定义,表示存放的数据类型
typedef int DataType;//定义节点的结构体类型
typedef struct node
{union{int len; //头结点的数据域，表示链表的长度DataType data;//普通节点的数据域};struct node *next; //节点的指针域
}linkList,*linkListPtr;

2.4 单向链表的相关操作 （功能函数的封装）

1>创建

#include "test.h"//创建链表==创建头结点
linklistPtr create()
{//在堆区申请节点大小空间，将地址放回给主程序使用linklistPtr H=(linklistPtr)malloc (sizeof(linklist));if (NULL==H){printf("创建失败\n");return NULL;}
//申请成功，将头节点的数据域为0，指针域NULLH->len=0;H->next=NULL;printf("创建成功\n");return H;}

2>判空

//判空
int  empty(linklistPtr H)
{if (NULL==H){printf("判空失败");return -1;}return H->len==0;}

3>申请节点，封装数据

//申请节点封装数据
linklistPtr create_node(int e)
{linklistPtr p=(linklistPtr)malloc (sizeof(linklist));if(NULL==p){printf("申请失败");return NULL;}p->data=e;p->next=NULL;return p;
}

4>头插

//头插
int   head_add(linklistPtr H,int e)
{if (NULL==H){printf("插入失败");return 0;}//申请节点封装数据linklistPtr p=create_node(e);
//头插p->next =H->next;H->next =p;
//插入成功长度自增H->len++;return 1;
}

 5>遍历

void show (linklistPtr H)
{if (NULL==H ||empty(H)){printf("遍历失败");return ;}
//定义一个指针指向头结点linklistPtr p =H;for (int i=0;i<H->len;i++){p=p->next;printf("%d ",p->data);}
putchar(10);
}

6>尾插

//尾插
int tail_add(linklistPtr H,int e)
{if (NULL== H){printf("插入失败");return 0;}
//申请节点封装数据linklistPtr p=create_node(e);linklistPtr q=H;while(q->next !=NULL){q= q->next;}
//尾插q->next =p;//插入成功长度自增H->len++;return 1;
}

7>任意位置插入

//任意位置插入
int insert(linklistPtr H,int index , int e)
{//链表是否合法//插入位置是否合理if (NULL==H || index <1 ||index>H->len+1){printf("插入失败\n");return 0;}
//申请节点封装数据 linklistPtr p=create_node(e);//定义一个指针指向要插入位置的前一个节点linklistPtr q=H;for (int i=0;i<index-1;i++){q=q->next ;}//插入（头插）p->next =q->next;q->next =p;//插入成功长度自增 H->len++;return 1;
}

8>头删

//头删
int head_del(linklistPtr H)
{//判空 //判断合法性if (NULL==H ||empty(H)){printf(" 删除失败\n");	return 0;}//定义一个指针指向普通节点的第一个节点linklistPtr q= H->next;//删除 （孤立）H->next=q->next ;//释放空间free(q);q=NULL;//删除成功 链表长度自减H->len--;return 1;
}

9>尾删

//尾删
int tail_del(linklistPtr H)
{if(NULL==H ||empty(H)){printf("删除失败 ");return 0;}
//定义一个指针，指向 最后一个节点的 前一个节点linklistPtr q=H;for (int i=0;i<H->len-1;i++){q=q->next;}
//删除free(q->next);q->next=NULL;
//删除成功 长度自减H->len--;return 1;
}

10>任意位置删除

//任意位置删除
int index_del(linklistPtr H ,int index)
{if (NULL==H ||empty(H)||index<0||index>H->len){printf("删除失败");return 0;}//定义指针，指向要删除的节点linklistPtr p=NULL;//定义一个指针，指向要删除的前一个节点linklistPtr q=H;for (int i=0;i<index-1;i++){q=q->next;}if (p=NULL){printf("删除失败");return  0;}//保存删除节点的位置p=q->next;q->next=p->next;//删除节点的内存free (p);
//删除成功 长度自减H->len--;return 1;
}

11>按位置修改

//按位置修改
int index_change(linklistPtr H,int index ,int e)
{if (NULL==H||empty(H)){printf("修改失败");return 0;}//定义一个指针，指向要修改的前一个节点linklistPtr q=H;
//定义指针，指向要修改的节点linklistPtr p=NULL;for (int i=0;i<index;i++){q=q->next;}//保存修改节点的位置p=q->next;//修改值p->data=e;return 1;}

12>按值查找返回地址

//按值查找返回
linklistPtr  index_find(linklistPtr H,int e)
{if (NULL==H||empty(H)){printf("查找失败");return NULL;}//定义一个指针指向头结点 linklistPtr p=H->next;while(p!=NULL){if (p->data==e){printf("%p\n",p);return p;}p=p->next;}//没找到printf("没找到目标值\n");return NULL;}

13>反转

//反转 
void reverse(linklistPtr H)
{if(NULL==H || H->len<=1){return ;}//定义一个指针，指向头结点的后一个节点linklistPtr H2=H->next;//头指针的next置空H->next=NULL;while (H2 !=NULL){//标记要插入的节点linklistPtr p=H2;H2=H2->next;//头插p->next =H->next ;H->next =p;}
}

14>销毁

//销毁void my_free(linklistPtr H)
{if (NULL==H){printf("销毁失败");return;}while (H->next !=NULL)//意味着还有节点{//头删head_del(H);}free (H);//释放头结点H=NULL;printf("销毁成功");
}

三、完整代码

1>头文件test.h

#ifndef __TEST_H__
#define __TEST_H__#include <stdio.h>
#include <stdlib.h>//定义节点的结构体类型
typedef struct node
{union{int len;//头结点的数据域，表示链表的长度int data;//普通节点的数据域};struct node *next;//节点的指针域
}linklist,*linklistPtr;//创建链表==创建头结点
linklistPtr create();int  empty(linklistPtr H);linklistPtr create_node(int e);int   head_add(linklistPtr How,int e);void show (linklistPtr H);int tail_add(linklistPtr H,int e);int insert(linklistPtr H,int index , int e);//头删
int head_del(linklistPtr H);//尾删
int tail_del(linklistPtr H);int index_del(linklistPtr H ,int index);
//按位置修改
int index_change(linklistPtr H,int index ,int e);
//按值查找返回
linklistPtr  index_find(linklistPtr H,int e);
//反转
void reverse(linklistPtr H);
//销毁
void my_free(linklistPtr H);#endif

2>源文件test.c

#include "test.h"//创建链表==创建头结点
linklistPtr create()
{//在堆区申请节点大小空间，将地址放回给主程序使用linklistPtr H=(linklistPtr)malloc (sizeof(linklist));if (NULL==H){printf("创建失败\n");return NULL;}
//申请成功，将头节点的数据域为0，指针域NULLH->len=0;H->next=NULL;printf("创建成功\n");return H;}
//判空
int  empty(linklistPtr H)
{if (NULL==H){printf("判空失败");return -1;}return H->len==0;}
//申请节点封装数据
linklistPtr create_node(int e)
{linklistPtr p=(linklistPtr)malloc (sizeof(linklist));if(NULL==p){printf("申请失败");return NULL;}p->data=e;p->next=NULL;return p;
}//头插
int   head_add(linklistPtr H,int e)
{if (NULL==H){printf("插入失败");return 0;}//申请节点封装数据linklistPtr p=create_node(e);
//头插p->next =H->next;H->next =p;
//插入成功长度自增H->len++;return 1;
}void show (linklistPtr H)
{if (NULL==H ||empty(H)){printf("遍历失败");return ;}
//定义一个指针指向头结点linklistPtr p =H;for (int i=0;i<H->len;i++){p=p->next;printf("%d ",p->data);}
putchar(10);
}
//尾插
int tail_add(linklistPtr H,int e)
{if (NULL== H){printf("插入失败");return 0;}
//申请节点封装数据linklistPtr p=create_node(e);linklistPtr q=H;while(q->next !=NULL){q= q->next;}
//尾插q->next =p;//插入成功长度自增H->len++;return 1;
}
//任意位置插入
int insert(linklistPtr H,int index , int e)
{//链表是否合法//插入位置是否合理if (NULL==H || index <1 ||index>H->len+1){printf("插入失败\n");return 0;}
//申请节点封装数据 linklistPtr p=create_node(e);//定义一个指针指向要插入位置的前一个节点linklistPtr q=H;for (int i=0;i<index-1;i++){q=q->next ;}//插入（头插）p->next =q->next;q->next =p;//插入成功长度自增 H->len++;return 1;
}//头删
int head_del(linklistPtr H)
{//判空 //判断合法性if (NULL==H ||empty(H)){printf(" 删除失败\n");	return 0;}//定义一个指针指向普通节点的第一个节点linklistPtr q= H->next;//删除 （孤立）H->next=q->next ;//释放空间free(q);q=NULL;//删除成功 链表长度自减H->len--;return 1;
}
//尾删
int tail_del(linklistPtr H)
{if(NULL==H ||empty(H)){printf("删除失败 ");return 0;}
//定义一个指针，指向 最后一个节点的 前一个节点linklistPtr q=H;for (int i=0;i<H->len-1;i++){q=q->next;}
//删除free(q->next);q->next=NULL;
//删除成功 长度自减H->len--;return 1;
}//任意位置删除
int index_del(linklistPtr H ,int index)
{if (NULL==H ||empty(H)||index<0||index>H->len){printf("删除失败");return 0;}//定义指针，指向要删除的节点linklistPtr p=NULL;//定义一个指针，指向要删除的前一个节点linklistPtr q=H;for (int i=0;i<index-1;i++){q=q->next;}if (p=NULL){printf("删除失败");return  0;}//保存删除节点的位置p=q->next;q->next=p->next;//删除节点的内存free (p);
//删除成功 长度自减H->len--;return 1;
}//按位置修改
int index_change(linklistPtr H,int index ,int e)
{if (NULL==H||empty(H)){printf("修改失败");return 0;}//定义一个指针，指向要修改的前一个节点linklistPtr q=H;
//定义指针，指向要修改的节点linklistPtr p=NULL;for (int i=0;i<index;i++){q=q->next;}//保存修改节点的位置p=q->next;//修改值p->data=e;return 1;}
//按值查找返回
linklistPtr  index_find(linklistPtr H,int e)
{if (NULL==H||empty(H)){printf("查找失败");return NULL;}//定义一个指针指向头结点 linklistPtr p=H->next;while(p!=NULL){if (p->data==e){printf("%p\n",p);return p;}p=p->next;}//没找到printf("没找到目标值\n");return NULL;}//反转 void reverse(linklistPtr H)
{if(NULL==H || H->len<=1){return ;}//定义一个指针，指向头结点的后一个节点linklistPtr H2=H->next;//头指针的next置空H->next=NULL;while (H2 !=NULL){//标记要插入的节点linklistPtr p=H2;H2=H2->next;//头插p->next =H->next ;H->next =p;}
}
//销毁
void my_free(linklistPtr H)
{if (NULL==H){printf("销毁失败");return;}while (H->next !=NULL)//意味着还有节点{//头删head_del(H);}free (H);//释放头结点H=NULL;printf("销毁成功");
}

3>测试文件main.c

#include "test.h"int main(int argc, const char *argv[])
{//创建linklistPtr H=create();//头插 head_add(H,10);head_add(H,20);head_add(H,30);head_add(H,40);head_add(H,50);show(H);
//尾插 tail_add(H,11);tail_add(H,22);tail_add(H,33);tail_add(H,44);tail_add(H,55);show(H);//任意位置插入insert(H,3,888);show (H);	//头删  	head_del(H);show(H);head_del(H);show(H);tail_del(H);show(H);index_del(H,3);show(H);index_change (H,5,666);show(H);index_find (H,666);reverse(H);show(H);return 0;
}