单链表的头插法和尾插法的示例

/*
  程序功能：单链表的头插法和尾插法实验示例
  说明：本程序的增删改查功能部分实现
  作者：九天一声啸
  邮箱：946585434@qq.com
  日期：2022.09.09
*/
#include
#include
#include
#include
#include
 
#define BOOL  int
#define TRUE  1
#define OK    1
#define FALSE 0
#define NO    0
#define ERROR -1
 
//链表长度
 
int length = 16;
 
//TRUE 为自然数列，FALSE 为随机数
bool choose = true;
//bool choose = false;
 
//定义结构体
typedef struct Node 
{
    int data;
    struct Node *next;
    
}Node, *LinkList;
 
LinkList head = NULL;
LinkList end = NULL; //尾插法时使用的结构体指针
 
//头插法函数
void addHead(int data)
{
    LinkList L;
    L = (LinkList)malloc(sizeof(Node));
    L->data = data;
    L->next = head->next;
    head->next = L;
    
}
 
//尾插法函数
void addEnd(int data) {
 
    LinkList L;
    L = (LinkList)malloc(sizeof(Node));
    L->next = NULL;
    L->data = data;
 
    if(NULL == head)
    {
        head = L;
    } else {
        end->next = L;
    }
 
    end = L;
    
}
 
//头插法遍历链表并输出
void showListHead()
{
 
    LinkList tmp;
    tmp = head->next;
 
    while (tmp != NULL)
    {
        printf ("%d ", tmp->data);
        tmp = tmp->next;
    }
    
}
 
//尾插法遍历链表并输出
void showListEnd()
{
 
    LinkList tmp;
    tmp = head;
 
    while(tmp)
    {
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }
    
}
 
int main()
{
 
    int i;
    char str[10];
    BOOL tag;
    srand(time(0));
 
    printf("请输入内容，true 是尾插法；false 是头插法：\n\t->");
    scanf("%s",&str);
 
    /*
      判断输入内容
    
      tag = 1  为true；
      tag = 0  为false
      tag = -1 为error
    */
    if(strcmp(str, "true") == 0)
        tag = TRUE;
    else if(strcmp(str, "false") == 0)
        tag = FALSE;
    else
        tag = ERROR;
 
    if(tag == TRUE) {
 
        //头插法需要这段代码，否则错误
        head = (LinkList)malloc(sizeof(Node));
        head->next = NULL;
 
        //头插法插入数据
        for(i = 0; i < length; i++)
        {
            if(choose == true)
                addHead(i);
            else
                //随机数
                addHead(rand()%100 + 1);
        }
 
        printf("头插法：\n");
 
        //头插法显示
        showListHead();
 
    } else if(tag == FALSE) {
 
        //尾插法插入数据
        for(i = 0; i < length; i++)
        {
            if(choose == true)
                addEnd(i);
            else
                //随机数
                addEnd(rand()%100 + 1);
        }
 
        printf("尾插法：\n");
 
        //尾插法显示
        showListEnd();
 
    } else {
 
        printf("输入错误！");
 
    }
 
    return 0;
    
}

/*
  程序功能：单链表的头插法和尾插法实验示例
  说明：本程序的增删改查功能全部实现
  作者：九天一声啸
  邮箱：946585434@qq.com
  日期：2022.09.09
*/
#include
#include
#include
#include
#include
 
//自定义布尔类型
#define BOOL int
#define TRUE  1
#define OK    1
#define FALSE 0
#define ERROR -1
 
BOOL tag;
 
//自定义数据类型 ElemType
#define ElemType int
 
//链表长度
int length = 16;
 
/*
  true 为自然数列，false 为随机数
*/
//bool choose = true;
bool choose = false;
 
//定义结构体
typedef struct Node{
 
    /*
      data 代表的是数据元素，
      实际应用中 data 应该是另一个结构体，
      并且在结构体中定义数据项。
    */
    int data;          //结点数据
    struct Node *next; //结点指针
}Node, *LinkList;
 
LinkList head = NULL;
LinkList end  = NULL;  //尾插法时使用的结构体指针
 
/*
  功能：头插法算法函数
  
  @param int data 链表数据
  @return void
*/
void addHead(int data){
    LinkList L;
    
    //头插法核心代码 begin
    if(NULL == head)
    {
        //如果没有头节点，创建头节点
        head = (LinkList)malloc(sizeof(Node));
        head->next = NULL;
    }
    else
    {
        L = (LinkList)malloc(sizeof(Node));
        L->data = data;
        L->next = head->next;
        head->next = L;
    }
    //头插法核心代码 end.
}
 
/*
  功能：尾插法算法函数
  
  @param int data 链表数据
  @return void
*/
void addEnd(ElemType data){
    LinkList L;
    
    //尾插法核心代码 begin
    L = (LinkList)malloc(sizeof(Node));
    L->data = data;
    L->next = NULL;
    
    if(NULL == head)
    {
        //如果没有头节点，创建头节点
        head = (LinkList)malloc(sizeof(Node));
        head->next = L;
    }else{
        end->next = L;
    }
    
    end = L;
    //尾插法核心代码 end.
}
 
/*
  功能：返回头结点指针
  
  @return LinkList 自定义结构体指针类型
*/
LinkList getLinkNode()
{
    LinkList L;
    
    L = head->next;
        
    return L;
}
 
/*
  功能：根据输入链表的位置查询链表数据
  
  @param  int num 待查询链表的位置
  @return int
*/
int getElem(int num)
{
    LinkList L;
    int i;
    
    /*
      由于程序是从 0 开始计数的，见 linkCreate() 函数内容，
      我们数数时是从 1 开始的，为了让认知一致，i 应该从 1 开始
      计数。
    */
    i = 1;
    L = getLinkNode();
    
    //循环移动指针到指定位置
    while(L && i < num)
    {
        //指针向后移动一位
        L = L->next;
        ++i;
    }
    
    if(!L || i > num)
        return ERROR;
    
    //查询节点数据的核心代码，直接返回数据即可
    return L->data;
}
 
/*
  功能：根据数据位置修改链表
  
  @param  int num  待查询链表的位置
  @param  int data 待修改的数据
  @return BOOL     自定义的布尔类型
*/
BOOL changeElem(int num, ElemType data)
{
    LinkList L;
    int i;
    i = 1;
    L = getLinkNode();
    
    //循环移动指针到指定位置
    while(L && i < num)
    {
        //指针向后移动一位
        L = L->next;
        ++i;
    }
    
    if(!L || i > num)
        return ERROR;
        
    //修改节点数据的核心代码 begin
    L->data = data;
    //修改节点数据的核心代码 end
    
    return OK;
}
 
/*
  功能：根据输入链表的位置插入链表节点
  
  @param  int num  待插入链表的位置
  @param  int data 待插入的数据
  @return BOOL     自定义的布尔类型
*/
BOOL insertList(int num, ElemType data)
{
    LinkList L, s;
    int j;
    j = 1;
    L = getLinkNode();
    
    //循环移动指针到指定位置
    while(L && j < num)
    {
        //指针向后移动一个节点
        L = L->next;
        ++j;
    }
    
    if(!L || j > num)
        return ERROR;
    
    //插入节点和数据的核心代码 begin
    s = (LinkList)malloc(sizeof(Node));
    s->data = data;
    s->next = L->next;
    L->next = s;
    //插入节点和数据的核心代码 end
    
    return OK;
}
 
/*
  功能：根据输入链表的位置删除链表的节点
  
  @param int num   要删除链表的位置
  @return ElemType 自定义类型
*/
ElemType deleteList(int num)
{
    LinkList L, s;
    ElemType tmp;
    int j;
    
    /*
        由于程序是从0开始计数的，见 linkCreate() 函数内容，
      我们数数时是从1开始的，为了让认知一致，j 应该从 1 开始
      计数；
        再由于，要删除的数据是从查询到的位置的下一个位置开始删
      的，所以这里 j 再加1，即 j = 2。
    */
    j = 2;
    
    /*
      双向链表有前驱指针可以在删除第一个节点时，直接指向头节点。然而，
      由于单向链表没有前驱指针，在指向头节点后的第一个节点时，在删除
      第一个节点时删除不了第一个节点，还是删除的是第二个节点，因此
      这里如果要删除第一个节点的话，要把指针指向头节点。
    */
    if (num == 1)
    
        /*
          删除第一个节点时，指针指向头节点，头节点没有数据内容，
          即 head->data 为空。
        */
        L = head;
    else
        
        /*
          删除其它节点时，指针指向头节点后有数据内容的第一个节点，
          即 head->next->data 是 head 头节点后，第一个节点的数据。
          注意：head->next 是 head 节点后的第一个节点。
        */
        L = getLinkNode();
    
    //循环移动指针到指定位置
    while(L && j < num)
    {
        //指针向后移动一个节点
        L = L->next;
        j++;
    }
    
    if((!L || j > num) && num != 1)
        return ERROR;
    
    //删除节点的核心代码 begin
    s = L->next ;
    L->next = s->next ;
    tmp = s->data;
    free(s);
    //删除节点的核心代码 end
    
    return tmp;
}
 
/*
  功能：链表的整表删除
  
  @return BOOL 自定义布尔类型
*/
BOOL allDeletList()
{
    LinkList L, s;
    s = head->next;
    
    //整表删除的核心代码 begin
    while(s)
    {
        L = s->next;
        free(s);
        s =L;
    }
    //整表删除的核心代码 end
    
     //TRUE：头插法；FALSE：尾插法
    if(tag == TRUE)
        head->next = NULL;
    else
        head = NULL;
    
    return OK;
}
 
//----------- 以上是单链表的算法实现
//----------- 以下是辅助函数和程序，不必深究。
 
/*
  功能：头插法遍历链表并输出
  
  @return void
*/
void showListHead()
{
    LinkList tmp;
    tmp = head->next;
    
    while (tmp != NULL)
    {
        printf ("%d ", tmp->data);
        tmp = tmp->next;
    }
}
 
/*
  功能：尾插法遍历链表并输出
  
  @return void
*/
void showListEnd()
{
    LinkList tmp;
    bool flag = false ;
    
    tmp = head;
    
    while(tmp != NULL)
    {
        if (flag)
            printf("%d ", tmp->data);
        else 
            flag = true;
            
        tmp = tmp->next;
    }
}
 
/*
  功能：遍历单链表并显示
  
  @return void
*/
void showList()
{
    //TRUE：头插法；FALSE：尾插法
    if(tag == TRUE)
    {
        //头插法遍历显示
        showListHead();
    }
    else if(tag == FALSE)
    {
        //尾插法遍历显示
        showListEnd();
    }
}
 
/*
  功能：创建单链表
  
  @return BOOL 自定义的布尔类型
*/
BOOL linkCreate()
{
    
    int i;
    char str[10];
    srand(time(0));
    
    printf("1.请输入内容，true 是头插法；false 是尾插法：\n\t-> ");
    scanf("%s",&str);
    
    /*
      判断输入内容
    
      tag = 1    为true；
      tag = 0    为false
      tag = -1   为error
    */
    if(strcmp(str, "true") == 0)
        tag = TRUE;
    else if(strcmp(str, "false") == 0)
        tag = FALSE;
    else
        tag = ERROR;
    
    //TRUE：头插法；FALSE：尾插法；ERROR：错误
    if(tag == TRUE){
    
        //头插法插入数据
        for(i = 0; i < length; ++i)
        {
            if(choose == TRUE)
                addHead(i);
            else
                //随机数
                addHead(rand()%100 + 1);
        }
        
        printf("头插法：\n");
        
        //头插法遍历显示
        showListHead();
        
        return OK;
        
    }else if(tag == FALSE){
        
        //尾插法插入数据
        for(i = 0; i < length; i++)
        {
            if(choose == TRUE)
                addEnd(i);
            else
                //随机数
                addEnd(rand()%100 + 1);
        }
    
        printf("尾插法：\n");
        
        //尾插法遍历显示
        showListEnd();
        
        return OK;
        
    }else{
    
        printf("输入错误！");
        return ERROR;
        
    }
    
}
 
/*
  功能：根据输入链表的位置查询数据
  
  @return void
*/
void linkQuery()
{
    int input;
    printf("\n\n2.请输入要查询的位置：\n\t-> ");
    scanf("%d", &input);
    
    if(input <= length)
    {
        int getNum = getElem(input);
        printf("\n获取到的值：%d", getNum);
    }else{
        printf("\n╳ 没有这么长的链表！");
    }
}
 
/*
  功能：根据输入链表的位置修改数据
  
  @return void
*/
void linkRevise()
{
    int input, data;
    printf("\n\n3.请输入要修改的位置和数据，两个数据用空格隔开：\n\t-> ");
    scanf("%d%d", &input, &data);
    
    if(input <= length)
    {
        changeElem(input, data);
    
        printf("\n链表修改后的值：\n");
        
        showList();
    }else{
        printf("\n╳ 没有这么长的链表！");
    }
}
 
/*
  功能：根据输入链表的位置插入数据
  
  @return void
*/
void linkInsert()
{
    int input, data;
    printf("\n\n4.请输入要插入的位置和数据，两个数据用空格隔开：\n\t-> ");
    scanf("%d%d", &input, &data);
    
    if(input <= length)
    {
        int ret = insertList(input, data);
    
        if(ret == OK)
            length++;
            
        printf("\n链表修改后的值：\n");
        
        showList();
    }else{
        printf("\n╳ 没有这么长的链表！");
    }
}
 
/*
  功能：根据输入链表的位置删除数据
  
  @return void
*/
void linkDelete()
{
    int input, data, tmp;
    printf("\n\n5.请输入要删除的位置：\n\t-> ");
    scanf("%d", &input);
    
    if(input <= length)
    {
        tmp = deleteList(input);
        
        if(tmp != ERROR)
            length--;
    
        printf("\n->被删除的值：%d\n\n", tmp);
        printf("\n链表删除后的值：\n");
        
        showList();
    }else{
        printf("\n╳ 没有这么长的链表！");
    }
}
 
/*
  功能：主函数入口
  
  @return int
*/
int main()
{
    //链表操作：创建链表
    BOOL val = linkCreate();
    
    if(val != ERROR)
    {
        printf("\n--------------------------------\n");
        
        //链表查询
        linkQuery();
        printf("\n--------------------------------\n");
    
        //链表修改
        linkRevise();
        printf("\n--------------------------------\n");
        
        //链表插入
        linkInsert();
        printf("\n--------------------------------\n");
 
        //链表删除
        linkDelete();
        printf("\n--------------------------------\n");
        
        //整表删除
        allDeletList();
        printf("\n6.整表删除后的链表数据：");
        showList();
    }
    return 0;
}

#include
#include
#include
#include
 
//结构体定义的数据域
typedef struct myData{
    int  id;
    char name[20];
    short int  sex; //0为男；1为女
    char address[100];
}myData;
 
//结构体定义的节点
typedef struct Node{
 
    //数据域，这里用结构体变量，不能直接用指针，
    //如果没有变量，指针就不能指向变量的地址。
    struct myData data;
    
    //指针域
    struct Node *next;
}Node, *LinkList;
 
//性别判断
void determine(short int flag, char* e)
{
    if(flag == 0)
        strcpy(e, "男");
    else if(flag == 1)
        strcpy(e, "女");
    else
        strcpy(e, "未知");
}
 
//主函数入口
int main()
{
    char ssex[10] ="未知";
    
    //1.结构体变量,静态分配内存
    Node link1; 
    
    //赋值
    link1.data.id = 12;
    strcpy(link1.data.name, "孙悟空");
    link1.data.sex = 0;
    strcpy(link1.data.address, "花果山水帘洞");
    
    //性别判断
    determine(link1.data.sex, ssex);
    
    printf("编号：%d\n姓名：%s\n姓别：%s\n地址：%s\n\n", link1.data.id, link1.data.name, ssex, link1.data.address);
  
    //2.malloc() 函数动态分配内存
    LinkList link2 = (LinkList)malloc(sizeof(Node));
    
    //赋值
    link2->data.id = 13;
    strcpy(link2->data.name, "嫦娥");
    link2->data.sex = 1;
    strcpy(link2->data.address, "月亮广寒宫");
    
    //性别判断
    determine(link2->data.sex, ssex);
    
    printf("编号：%d\n姓名：%s\n姓别：%s\n地址：%s\n\n", link2->data.id, link2->data.name, ssex, link2->data.address);
  
    //3.如果把上面的两个结构体变量组合成一个单向链表
    
    /*
      用这种最原始的方法，才能看清楚它们的关系
    
      这里 link1 是结构体变量，
      而 link2 是 malloc() 直接返回的就是指针，非常方便。
    */
    Node L; //内存分配一个头节点
    Node* head = &L;
    //这里等效于：Node* head = (Node*)malloc(sizeof(Node));
    
    head->next = &link1;
    head->next->next = link2;
    head->next->next->next = NULL; //单链表要求尾节点的 next 为空
    /*
      单链表生成完毕，这是最直观的单链表了，上面的五段代码看明白了，
      单链表的算法已就能写出来了。
    
      说明：
      1.一般要求头节点除了 next 指针域是有效数据，data 数据域是无效数据，不用管它；
      2.也可以在头节点放置链表长度，这时头节点要单独定义一个结构体，指针域不变，数据
        域为：int length; 只需把 next 指向其它有数据的节点即可。这样的好处就是在
        获取单链表的长度时，不用遍历整个链表，也就是时间复杂度由 O(n) 变为了 O(1)，
        但是，也可以不需要头节点。
      3.一个 next 其实就是一个有数据内容的节点，而最后的尾节点为 NULL 而已。
    */
    
    printf("以下内容是从单链表输出的：\n\n");
    
    //显示第一个有数据的节点内容
    determine(head->next->data.sex, ssex);
    printf("编号：%d\n姓名：%s\n姓别：%s\n地址：%s\n\n", head->next->data.id, head->next->data.name, ssex, head->next->data.address);
    
    //显示第二个有数据的节点内容
    determine(head->next->next->data.sex, ssex);
    printf("编号：%d\n姓名：%s\n姓别：%s\n地址：%s\n", head->next->next->data.id, head->next->next->data.name, ssex, head->next->next->data.address);
 
    return 0;
}