目录

一、链表

  1.1 链表的概念

二、单链表

  2.1 单链表的概念

  2.2单链表的操作

    2.2.1 单链表的结点创建

    2.2.2 单链表的头插

    2.2.3 单链表遍历

    2.2.4 单链表的头删

    2.2.5 单链表的尾插

    2.2.6 单链表的尾删

    2.2.7 单链表按位置插入

    2.2.8 单链表按位置删除

    2.2.9 单链表按位置修改

    2.2.10 单链表按位置查找

    2.2.11 单链表按元素查找

    2.2.12 单链表按元素删除

    2.2.13 单链表按元素修改

    2.2.14 单链表逆置

    2.2.15 单链表查找倒数第n个节点

    2.2.16 单链表排序

    2.2.17 单链表释放内存

  2.3 单链表所有程序

    2.3.1 head.h

    2.3.2 main.c

    2.3.3 fun.c

    2.3.4 效果

---

一、链表

  1.1 链表的概念

        1. 引入目的：顺序表的方便修改和查找，不方便插入和删除，插入的和删除的时间复杂度是O(n),并且顺序表存在满的情况，顺序表是否用于数据量较小的情况，所以引出链表。

        2.链表：线性表的链式存储，称为链表

                逻辑结构：线性结构(一对一关系）

                存储结构：链式存储（内存空间任意一段),

                逻辑相邻，物理不一定相邻

        3.链表的分类：单向链表，单向循环链表，双向链表，双向循环链表

                

二、单链表

  2.1 单链表的概念

        1.单链表：只能从头开始单向向后遍历访问节点的链表，称为单链表

        2.结点：包含数据域，指针域

                数据域：存储数据元素

                指针域：下一个节点的地址

        3.结点结构体的定义

        4.链表的插入和删除的思想

  2.2单链表的操作

  PS:head.h中函数声明，在main.c和fun.c中引用head.h

    2.2.1 单链表的结点创建

// 创建单链表---------------
Linklist creat_node()
{// 1.创建一个新的节点Linklist s=(Linklist)malloc(sizeof(struct Node));// 2. if(NULL==s)return NULL;// 初始化新节点的数据域s->data=0;// 初始化新节点的指针域s->next=NULL;return s;
}

    2.2.2 单链表的头插

// 头插---------------
Linklist insert_head(Linklist head,datatype element)
{Linklist s=creat_node();s->data=element;// 1.判断链表是否为空if(NULL==head)head=s;else  // 链表中存在多个节点 >=1{s->next=head;head=s;}return head;
}

    2.2.3 单链表遍历

// 循环遍历---------------
void output(Linklist head)
{//  1.判断链表是否为空if(NULL==head)return;// 2.循环遍历Linklist p=head;printf("Linklist=");while(p!=NULL){printf("%d ",p->data);p=p->next;}putchar(10);return;
}

    2.2.4 单链表的头删

// 单链表的头删---------------
Linklist delete_head(Linklist head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.头删Linklist del;del=head;head=head->next;free(del);del=NULL;return head;
}

    2.2.5 单链表的尾插

// 单链表的尾插---------------
Linklist insert_tail(Linklist head,datatype element)
{// 1.创建新节点，并输入值Linklist s=creat_node();s->data=element;s->next=NULL;// 2.判断链表是否为空if(NULL==head){head=s;}else{// 3.尾插Linklist p=head;while(p->next)  // 找到最后一个节点{p=p->next;}p->next=s;  // 链接:p指针域指向新节点的地址}return head;
}

    2.2.6 单链表的尾删

// 单链表的尾删---------------
Linklist delete_tail(Linklist head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.只有一个节点时else if(head->next==NULL){free(head);head=NULL;}// 3.有多个节点时else{Linklist del=head;// 找到倒数第二个节点while(del->next->next){del=del->next;}// 删除p的后继free(del->next);del->next=NULL;}return head;
}

    2.2.7 单链表按位置插入

// 查询链表长度---------------
int get_len(Linklist head)
{Linklist p=head;int len=0;while(p!=NULL){p=p->next;len++;}return len;
}
// 单链表按位置插入---------------
Linklist insert_pos(Linklist head,datatype element,int pos)
{// 1.判断插入的位置是否合法if(pos<1||pos>get_len(head)+1){return head;}// 2.头插if(pos==1){head=insert_head(head,element);return head;}// 3.尾插if(pos==get_len(head)+1){head=insert_tail(head,element);}// 4.位置大于1，且合法Linklist del=head;// 找到要插入的前一个位置for(int i=1;i<pos-1;i++){del=del->next;}// 创建一个新的节点,并赋值Linklist s=creat_node();s->data=element;// 链接指针域s->next=del->next;del->next=s;return head;
}

    2.2.8 单链表按位置删除

// 单链表按位置删除---------------
Linklist delete_pos(Linklist head,int pos)
{// 1.判断链表是否为空// 2.判断删除位置是否合法if(NULL==head||pos<1||pos>get_len(head)){return head;}// 3.头删if(pos==1){head=delete_head(head);return head;}// 4.位置大于1，且位置合法Linklist del=head;for(int i=1;i<pos-1;i++)  // 找到删除位置前一个位置{del=del->next;}Linklist s=del->next;del->next=s->next;  // 让删除位置前一个节点与后一个节点链接free(s);  // 释放删除位置空间s=NULL;return head;
}

    2.2.9 单链表按位置修改

// 单链表按位置修改---------------
Linklist change_pos(Linklist head,datatype element,int pos)
{// 1.判断链表是否为空// 2.判断修改的位置是否合法if(NULL==head||pos<0||pos>get_len(head)){return head;}// 3.按位置修改else{// 找到修改的位置Linklist del=head;for(int i=1;i<pos;i++){del=del->next;}del->data=element;return head;}
}

    2.2.10 单链表按位置查找

// 单链表按位置查找---------------
int find_pos(Linklist head,int pos)
{// 1.判断链表是否为空// 2.判断查找位置是否合法if(NULL==head||pos<0||pos>get_len(head)){return FALSE;}// 3.查询位置元素else{// 找到查询位置Linklist del=head;for(int i=1;i<pos;i++){del=del->next;}// 返回该位置元素return del->data;}
}

    2.2.11 单链表按元素查找

// 单链表按元素查找---------------
int find_element(Linklist head,datatype element)
{// 1.判断链表是否为空if(NULL==head){return FALSE;}// 2.判断查找元素是否存在,存在则记录位置Linklist del=head;int pos=0;int data;for(int i=1;i<=get_len(head);i++){if(del->data==element){pos=i;// 调用按位置查找函数find_pos(head,pos);}del=del->next;}return pos;
}

    2.2.12 单链表按元素删除

// 单链表按元素删除---------------
Linklist delete_element(Linklist head,datatype element)
{// 1.判断链表是否为空if(NULL==head){return head;}// 2.判断删除元素是否存在,存在则记录位置Linklist del=head;int pos;for(int i=1;i<=get_len(head);i++){if(del->data==element){pos=i;  // 记录元素位置head=delete_pos(head,pos);  // 调用按位置删除函数，删除元素del=head;}else{del=del->next;}}return head;
}

    2.2.13 单链表按元素修改

// 单链表按元素修改---------------
void change_element(Linklist head,datatype element,datatype element2)
{// 1.判断链表是否为空if(NULL==head){return;}// 2.判断修改元素是否存在，若存在则直接修改Linklist del=head;while(del){if(del->data==element){del->data=element2;return;}del=del->next;}
}

    2.2.14 单链表逆置

// 单链表逆置---------------
Linklist reve_list(Linklist head)
{// 1.判断链表是否为空if(NULL==head){return head;}// 2.用切断再链接的方法逆置链表Linklist p=head->next;  // 记录后续被切断的节点地址head->next=NULL;  // 切断第一个节点Linklist s;  // 中间值while(p){s=p;  // 记录被切断节点p=p->next;  // 记录被切断节点下一个节点s->next=head;  // 让被切断节点指向上一个被切断节点head=s;  // 让刚链接过来的节点成为头节点}return head;
}

    2.2.15 单链表查找倒数第n个节点

// 单链表查找倒数第n个节点---------------
int find_repos(Linklist head,int pos)
{// 1.判断链表是否为空// 2.判断位置是否合法if(NULL==head||pos<0||pos>get_len(head)){return FALSE;}// 3.找到查找位置pos=get_len(head)-pos+1;// 4.调用按位置查找函数输出int data;data=find_pos(head,pos);return data;
}

    2.2.16 单链表排序

// 单链表排序---------------
void sort_list(Linklist head)
{// 1.判断链表是否为空// 2.判断节点数是否为1if(NULL==head||head->next==NULL){return;}// 3.排序Linklist del=head;int temp;for(int i=1;i<get_len(head);i++){for(int j=1;j<get_len(head);j++){if(del->data>del->next->data){temp=del->data;del->data=del->next->data;del->next->data=temp;}del=del->next;}del=head;}return;
}

    2.2.17 单链表释放内存

// 单链表释放内存---------------
void free_list(Linklist head)
{// 1.判断链表是否为空if(NULL==head){return;}// 2.释放内存Linklist s=head;while(head){s=head;  // 记录头结点位置head=head->next;  // 使头结点下一个节点成为新的头结点s->next=NULL;  // 断开原头结点free(s); // 释放原头结点}s=NULL;return;
}

  2.3 单链表所有程序

    2.3.1 head.h

#ifndef __HEAD_H__
#define __HEAD_H__#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef int datatype;
enum passble{SUCCSSES,FALSE=-1};
// 节点结构定义
// 节点：数据、指针域
// Node不可省略
typedef struct Node
{datatype data;  // 数据域：数据元素struct Node *next;  // 指针域：节点之间的关系，下一个节点的地址
}*Linklist;Linklist creat_node();
Linklist insert_head(Linklist head,datatype element);
void output(Linklist head);
Linklist delete_head(Linklist);
Linklist insert_tail(Linklist head,datatype element);
Linklist delete_tail(Linklist head);
int get_len(Linklist head);
Linklist insert_pos(Linklist head,datatype element,int pos);
Linklist delete_pos(Linklist head,int pos);
Linklist change_pos(Linklist head,datatype element,int pos);
int find_pos(Linklist head,int pos);
int find_element(Linklist head,datatype element);
Linklist delete_element(Linklist head,datatype element);
void change_element(Linklist head,datatype element,datatype element2);
Linklist reve_list(Linklist head);
int find_repos(Linklist head,int pos);
void sort_list(Linklist head);
void free_list(Linklist head);#endif

    2.3.2 main.c

#include "head.h"
int main(int argc, const char *argv[])
{
// 单链表的创建
// 单链表的头插Linklist head=NULL;int n;printf("请输入插入个数:");scanf("%d",&n);datatype element;for(int i=0;i<n;i++){printf("请输入插入的第 %d 个元素:",i+1);scanf("%d",&element);head=insert_head(head,element);}output(head);// 单链表的头删head=delete_head(head);printf("头删后");output(head);
// 单链表的尾插printf("请输入尾插个数:");scanf("%d",&n);for(int i=0;i<n;i++){printf("请输入尾插元素:");scanf("%d",&element);head=insert_tail(head,element);}output(head);// 单链表的尾删head=delete_tail(head);printf("尾删后");output(head);// 单链表按位置插入int pos;printf("请输入插入位置:");scanf("%d",&pos);printf("请输入插入元素:");scanf("%d",&element);head=insert_pos(head,element,pos);output(head);// 单链表按位置删除printf("请输入删除位置:");scanf("%d",&pos);head=delete_pos(head,pos);output(head);// 单链表按位置修改printf("请输入要修改位置:");scanf("%d",&pos);printf("请输入修改后的值:");scanf("%d",&element);head=change_pos(head,element,pos);output(head);// 单链表按位置查找printf("请输入要查询的位置:");scanf("%d",&pos);datatype data;data=find_pos(head,pos);if(pos==FALSE){printf("查询出错\n");}else{printf("第%d位是%d\n",pos,data);}// 单链表按元素查找printf("请输入查找的元素:");scanf("%d",&element);pos=find_element(head,element);if(pos==FALSE||pos==0){printf("查询有误\n");}else{printf("%d在第%d位\n",element,pos);}// 单链表按元素删除printf("请输入要删除的元素:");scanf("%d",&element);head=delete_element(head,element);output(head);// 单链表按元素修改printf("请输入要修改的元素:");scanf("%d",&element);datatype element2;printf("请输入修改后的元素:");scanf("%d",&element2);change_element(head,element,element2);output(head);// 单链表逆置head=reve_list(head);printf("逆置后:");output(head);// 单链表查找倒数第n个节点printf("请输入要查找倒数第几个节点的值:");scanf("%d",&pos);data=find_repos(head,pos);if(pos==FALSE){printf("查询出错\n");}else{printf("倒数第%d位是%d\n",pos,data);}// 单链表排序sort_list(head);printf("对链表顺序排序后:");output(head);// 单链表释放内存free_list(head);return 0;
}

    2.3.3 fun.c

#include "head.h"
// 创建单链表---------------
Linklist creat_node()
{// 1.创建一个新的节点Linklist s=(Linklist)malloc(sizeof(struct Node));// 2. if(NULL==s)return NULL;// 初始化新节点的数据域s->data=0;// 初始化新节点的指针域s->next=NULL;return s;
}
// 头插---------------
Linklist insert_head(Linklist head,datatype element)
{Linklist s=creat_node();s->data=element;// 1.判断链表是否为空if(NULL==head)head=s;else  // 链表中存在多个节点 >=1{s->next=head;head=s;}return head;
}// 循环遍历---------------
void output(Linklist head)
{//  1.判断链表是否为空if(NULL==head)return;// 2.循环遍历Linklist p=head;printf("Linklist=");while(p!=NULL){printf("%d ",p->data);p=p->next;}putchar(10);return;
}
// 单链表的头删---------------
Linklist delete_head(Linklist head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.头删Linklist del;del=head;head=head->next;free(del);del=NULL;return head;
}
// 单链表的尾插---------------
Linklist insert_tail(Linklist head,datatype element)
{// 1.创建新节点，并输入值Linklist s=creat_node();s->data=element;s->next=NULL;// 2.判断链表是否为空if(NULL==head){head=s;}else{// 3.尾插Linklist p=head;while(p->next)  // 找到最后一个节点{p=p->next;}p->next=s;  // 链接:p指针域指向新节点的地址}return head;
}
// 单链表的尾删---------------
Linklist delete_tail(Linklist head)
{// 1.判断链表是否为空if(NULL==head)return head;// 2.只有一个节点时else if(head->next==NULL){free(head);head=NULL;}// 3.有多个节点时else{Linklist del=head;// 找到倒数第二个节点while(del->next->next){del=del->next;}// 删除p的后继free(del->next);del->next=NULL;}return head;
}// 查询链表长度---------------
int get_len(Linklist head)
{Linklist p=head;int len=0;while(p!=NULL){p=p->next;len++;}return len;
}
// 单链表按位置插入---------------
Linklist insert_pos(Linklist head,datatype element,int pos)
{// 1.判断插入的位置是否合法if(pos<1||pos>get_len(head)+1){return head;}// 2.头插if(pos==1){head=insert_head(head,element);return head;}// 3.尾插if(pos==get_len(head)+1){head=insert_tail(head,element);}// 4.位置大于1，且合法Linklist del=head;// 找到要插入的前一个位置for(int i=1;i<pos-1;i++){del=del->next;}// 创建一个新的节点,并赋值Linklist s=creat_node();s->data=element;// 链接指针域s->next=del->next;del->next=s;return head;
}// 单链表按位置删除---------------
Linklist delete_pos(Linklist head,int pos)
{// 1.判断链表是否为空// 2.判断删除位置是否合法if(NULL==head||pos<1||pos>get_len(head)){return head;}// 3.头删if(pos==1){head=delete_head(head);return head;}// 4.位置大于1，且位置合法Linklist del=head;for(int i=1;i<pos-1;i++)  // 找到删除位置前一个位置{del=del->next;}Linklist s=del->next;del->next=s->next;  // 让删除位置前一个节点与后一个节点链接free(s);  // 释放删除位置空间s=NULL;return head;
}// 单链表按位置修改---------------
Linklist change_pos(Linklist head,datatype element,int pos)
{// 1.判断链表是否为空// 2.判断修改的位置是否合法if(NULL==head||pos<0||pos>get_len(head)){return head;}// 3.按位置修改else{// 找到修改的位置Linklist del=head;for(int i=1;i<pos;i++){del=del->next;}del->data=element;return head;}
}// 单链表按位置查找---------------
int find_pos(Linklist head,int pos)
{// 1.判断链表是否为空// 2.判断查找位置是否合法if(NULL==head||pos<0||pos>get_len(head)){return FALSE;}// 3.查询位置元素else{// 找到查询位置Linklist del=head;for(int i=1;i<pos;i++){del=del->next;}// 返回该位置元素return del->data;}
}// 单链表按元素查找---------------
int find_element(Linklist head,datatype element)
{// 1.判断链表是否为空if(NULL==head){return FALSE;}// 2.判断查找元素是否存在,存在则记录位置Linklist del=head;int pos=0;int data;for(int i=1;i<=get_len(head);i++){if(del->data==element){pos=i;// 调用按位置查找函数find_pos(head,pos);}del=del->next;}return pos;
}// 单链表按元素删除---------------
Linklist delete_element(Linklist head,datatype element)
{// 1.判断链表是否为空if(NULL==head){return head;}// 2.判断删除元素是否存在,存在则记录位置Linklist del=head;int pos;for(int i=1;i<=get_len(head);i++){if(del->data==element){pos=i;  // 记录元素位置head=delete_pos(head,pos);  // 调用按位置删除函数，删除元素del=head;}else{del=del->next;}}return head;
}// 单链表按元素修改---------------
void change_element(Linklist head,datatype element,datatype element2)
{// 1.判断链表是否为空if(NULL==head){return;}// 2.判断修改元素是否存在，若存在则直接修改Linklist del=head;while(del){if(del->data==element){del->data=element2;return;}del=del->next;}
}// 单链表逆置---------------
Linklist reve_list(Linklist head)
{// 1.判断链表是否为空if(NULL==head){return head;}// 2.用切断再链接的方法逆置链表Linklist p=head->next;  // 记录后续被切断的节点地址head->next=NULL;  // 切断第一个节点Linklist s;  // 中间值while(p){s=p;  // 记录被切断节点p=p->next;  // 记录被切断节点下一个节点s->next=head;  // 让被切断节点指向上一个被切断节点head=s;  // 让刚链接过来的节点成为头节点}return head;
}// 单链表查找倒数第n个节点---------------
int find_repos(Linklist head,int pos)
{// 1.判断链表是否为空// 2.判断位置是否合法if(NULL==head||pos<0||pos>get_len(head)){return FALSE;}// 3.找到查找位置pos=get_len(head)-pos+1;// 4.调用按位置查找函数输出int data;data=find_pos(head,pos);return data;
}// 单链表排序---------------
void sort_list(Linklist head)
{// 1.判断链表是否为空// 2.判断节点数是否为1if(NULL==head||head->next==NULL){return;}// 3.排序Linklist del=head;int temp;for(int i=1;i<get_len(head);i++){for(int j=1;j<get_len(head);j++){if(del->data>del->next->data){temp=del->data;del->data=del->next->data;del->next->data=temp;}del=del->next;}del=head;}return;
}// 单链表释放内存---------------
void free_list(Linklist head)
{// 1.判断链表是否为空if(NULL==head){return;}// 2.释放内存Linklist s=head;while(head){s=head;  // 记录头结点位置head=head->next;  // 使头结点下一个节点成为新的头结点s->next=NULL;  // 断开原头结点free(s); // 释放原头结点}s=NULL;return;
}

    2.3.4 效果