美文网首页
线性表的链式存储-单链表

线性表的链式存储-单链表

作者: yeshan333 | 来源:发表于2018-12-14 21:00 被阅读4次

单链表操作

  • [x] 单链表的创建（尾插法、头插法）
  • [x] 单链表的查找操作
  • [x] 单链表的删除操作
  • [x] 单链表的逆置操作(使用头插法)
  • [x] 单链表表长的计算
  • [x] 打印单链表

单链表的创建

头插法

forward_list* creat_3()    //头插法 
{
    forward_list *head,*s;
    int num; 
    head = NULL;//链表初始状态为空
    while(scanf("%d",&num) && num)
    {
        s = (forward_list*)malloc(sizeof(forward_list));
        s->data = num;
        
        s->next = head;
        
        head = s;//将新结点插入到表头 
    }
    return head;
}

尾插法（不含头结点）

//尾插法建表 
forward_list* creat_1()
{
    forward_list *head=NULL;//头指针，初始状态为空 
    forward_list *rear=NULL;//尾指针，初始状态为空
    int num;
    forward_list *s;
    while(scanf("%d",&num) == 1 && num)//输入0结束 
    {
        s = (forward_list*)malloc(sizeof(forward_list));
        
        s->data = num;
        if(head == NULL)//将新节点加入空表 
            head = s;
        else            //原表非空，将新节点链接到表尾之后 
            rear->next = s;
        rear = s;//尾指针指向新的表尾 
    }
    if(rear!= NULL)//对于非空表，将尾结点的下一个结点置空 
        rear->next = NULL; 
    
    return head; 
}

尾插法（含头结点）

//尾插法建表,包含头结点 
forward_list* creat_2()
{
    forward_list *s;
    forward_list *head, *rear;
    int num;
    
    head = (forward_list*)malloc(sizeof(forward_list));
    rear = head;
    
    while(scanf("%d",&num)==1 && num)
    {
        s = (forward_list*)malloc(sizeof(forward_list));
        
        s->data = num;
        rear->next = s;
        rear = s;//表指针指向新的表尾 
    }
    rear->next = NULL; 
    
    return head;
}

单链表的查找操作

按值查找

void search_1(forward_list *s, int x)
{
    forward_list *p;
    p = s;
    while(p != NULL)
    {
        if(p->data == x)
        {
            printf("\nthe value : %d is exist !\n",x);
            return ;
        } 
        p = p->next;
    }
    printf("\nthe value : %d is not fonud !\n",x);
}

按值查找（包含头结点）

void search_2(forward_list *s, int x)//带头节点 
{
    forward_list *p;
    p = s->next;//emmmm 
    while(p != NULL)
    {
        if(p->data == x)
        {
            printf("\nthe value : %d is exist !\n",x);
            return ;
        } 
        p = p->next;
    }
    printf("\nthe value : %d is not fonud !\n",x);
}

单链表的删除操作

按给定结点的位置删除（带头结点）

void delete_1(forward_list *head,int i)        //删除第i个节点(单链表包含头节点)
{
    int j=0;
    forward_list *p,*q;
    p=head;
    j=0;
    while((p->next!=NULL)&&(j<i-1))
    {
        p=p->next;
        j++;
    }
    if(p->next!=NULL)
    {
        q=p->next;
        p->next=p->next->next;
        free(q);
    }
    else
        printf("illegal delete position,delete failed!");
}

按照指定值删除结点(不带头结点)

void forward_list_delete_1(forward_list *s,int x)//删除链表（不带头节点）中指定值的元素 
{
    forward_list *p;
    forward_list *temp;//用来存放被删除元素的前一个结点 
    p = s;
    if(x == p->data)
        free(p);
    
    temp = p;
    p = p->next;
    while(p != NULL)
    { 
        if(p->data == x)
        {
            temp->next = p->next;
            free(p);
            return ;
        }
        temp = p;
        p = p->next;    
    }
    printf("\n你要删除的元素 %d 不在表中\n",x);
    return ; 
}

单链表的逆置

头插法逆置(带头结点)

void reverse_2(forward_list *head)//头插法逆置,带头节点 
{
    forward_list *p,*q;
    p=head->next;
    head->next=NULL;
    while(p)
    {
        q=p;
        p=p->next;
        q->next=head->next;
        head->next=q;
    }
}

计算单链表的表长

*** 带头结点 ***

void list_length_2(forward_list *s)
{
    int count;
    forward_list *p=s->next;
    while(p)
    {
        count++;
        p = p->next;
    }
    printf("\nlist length: %d\n",count);
}

*** 不带头结点 ***

void list_length_1(forward_list *s)
{
    int count;
    forward_list *p=s;
    while(p)
    {
        count++;
        p = p->next;
    }
    printf("\nlist length: %d\n",count);
}

打印单链表

*** 带头结点 ***

void print_forward_list_2(forward_list *s)//打印含头节点的单链表 
{
    forward_list *p;
    p = s->next;//因为含有头节点，head->data的数据域的数据未知 
    while(p != NULL)
    {
        printf("%-3d",p->data);
        p = p->next;
    }
    return ;
}

*** 不带头结点 ***

void print_forward_list_1(forward_list *s)//打印单链表 
{
    forward_list *p;
    p = s;
    while(p != NULL)
    {
        printf("%4d",p->data);
        p = p->next;
    }
    return ;
}

试试

源程序

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//定义单链表结点类型 
typedef struct node{
    int data;                         //结点数据域 
    struct node *next;                //结点指针域 
    
}forward_list;

//尾插法建表 
forward_list* creat_1()
{
    forward_list *head=NULL;//头指针，初始状态为空 
    forward_list *rear=NULL;//尾指针，初始状态为空
    int num;
    forward_list *s;
    while(scanf("%d",&num) == 1 && num)//输入0结束 
    {
        s = (forward_list*)malloc(sizeof(forward_list));
        
        s->data = num;
        if(head == NULL)//将新节点加入空表 
            head = s;
        else            //原表非空，将新节点链接到表尾之后 
            rear->next = s;
        rear = s;//尾指针指向新的表尾 
    }
    if(rear!= NULL)//对于非空表，将尾结点的下一个结点置空 
        rear->next = NULL; 
    
    return head; 
}

//尾插法建表,包含头结点 
forward_list* creat_2()
{
    forward_list *s;
    forward_list *head, *rear;
    int num;
    
    head = (forward_list*)malloc(sizeof(forward_list));
    rear = head;
    
    while(scanf("%d",&num)==1 && num)
    {
        s = (forward_list*)malloc(sizeof(forward_list));
        
        s->data = num;
        rear->next = s;
        rear = s;//表指针指向新的表尾 
    }
    rear->next = NULL; 
    
    return head;
}

forward_list* creat_3()    //头插法 
{
    forward_list *head,*s;
    int num; 
    head = NULL;//链表初始状态为空
    while(scanf("%d",&num) && num)
    {
        s = (forward_list*)malloc(sizeof(forward_list));
        s->data = num;
        
        s->next = head;
        
        head = s;//将新结点插入到表头 
    }
    return head;
}

void search_1(forward_list *s, int x)
{
    forward_list *p;
    p = s;
    while(p != NULL)
    {
        if(p->data == x)
        {
            printf("\nthe value : %d is exist !\n",x);
            return ;
        } 
        p = p->next;
    }
    printf("\nthe value : %d is not fonud !\n",x);
}

void search_2(forward_list *s, int x)//带头节点 
{
    forward_list *p;
    p = s->next;//emmmm 
    while(p != NULL)
    {
        if(p->data == x)
        {
            printf("\nthe value : %d is exist !\n",x);
            return ;
        } 
        p = p->next;
    }
    printf("\nthe value : %d is not fonud !\n",x);
} 

void reverse_1(forward_list *head)//头插法逆置单链表 
{
    forward_list *p;
    forward_list *temp;
    
    p = head;//存好之前的单链表
    //printf("\n%d\n",p->data);
    head->next = NULL; 
    while(p)
    {
        temp = p;
        //printf("1");
        p = p->next;
        temp->next = head->next;
        head = temp;
        printf("\n%d\n",head->data); 
    }
}

void reverse_2(forward_list *head)//头插法逆置,带头节点 
{
    forward_list *p,*q;
    p=head->next;
    head->next=NULL;
    while(p)
    {
        q=p;
        p=p->next;
        q->next=head->next;
        head->next=q;
    }
} 


void forward_list_delete_1(forward_list *s,int x)//删除链表（不带头节点）中指定值的元素 
{
    forward_list *p;
    forward_list *temp;//用来存放被删除元素的前一个结点 
    p = s;
    if(x == p->data)
        free(p);
    
    temp = p;
    p = p->next;
    while(p != NULL)
    { 
        if(p->data == x)
        {
            temp->next = p->next;
            free(p);
            return ;
        }
        temp = p;
        p = p->next;    
    }
    printf("\n你要删除的元素 %d 不在表中\n",x);
    return ; 
}

void delete_1(forward_list *head,int i)        //删除第i个节点(单链表包含头节点)
{
    int j=0;
    forward_list *p,*q;
    p=head;
    j=0;
    while((p->next!=NULL)&&(j<i-1))
    {
        p=p->next;
        j++;
    }
    if(p->next!=NULL)
    {
        q=p->next;
        p->next=p->next->next;
        free(q);
    }
    else
        printf("illegal delete position,delete failed!");
} 




/*//不对 
void list_delete(forward_list *s, int i)//删除单链表(不带头节点)的第i个结点 
{
    int count=1;
    forward_list *p,*q;
    p=s;
    
    //将p移动到被删除结点的前一个结点 
    
    while((p!=NULL)&&(count<i-1))
    {

        p=p->next;
        count++;
    }
    
    if(i == count)
    {
        q = p;
        p = p->next;
        free(q);
        return ;
    }
    if(p->next!=NULL)
    {
        q=p->next;
        p->next=p->next->next;
        free(q);
    }
    else
        printf("illegal delete position,delete failed!");   
    
}
*/ 
void list_length_1(forward_list *s)
{
    int count;
    forward_list *p=s;
    while(p)
    {
        count++;
        p = p->next;
    }
    printf("\nlist length: %d\n",count);
}

void list_length_2(forward_list *s)
{
    int count;
    forward_list *p=s->next;
    while(p)
    {
        count++;
        p = p->next;
    }
    printf("\nlist length: %d\n",count);
}

void print_forward_list_1(forward_list *s)//打印单链表 
{
    forward_list *p;
    p = s;
    while(p != NULL)
    {
        printf("%4d",p->data);
        p = p->next;
    }
    return ;
}

void print_forward_list_2(forward_list *s)//打印含头节点的单链表 
{
    forward_list *p;
    p = s->next;//因为含有头节点，head->data的数据域的数据未知 
    while(p != NULL)
    {
        printf("%-3d",p->data);
        p = p->next;
    }
    return ;
} 

int main()
{
    /*不带头结点的单链表*/
    printf("使用不带头结点的单链表:\n"); 
    forward_list *p;
    printf("尾插法建表:\n"); 
    p = creat_1();//尾插法建表 
    print_forward_list_1(p);
    list_length_1(p); 
    
    //查找是否存在值为6的结点 
    search_1(p,6);
    printf("\n删了个5后，表变为\n"); 
    forward_list_delete_1(p,5);
    print_forward_list_1(p);
    
    //头插法建表 
    forward_list *s;
    printf("\n头插法建表:\n"); 
    s = creat_3();
    print_forward_list_1(s);
    list_length_1(s);
    
    /*带头结点的单链表*/
    printf("\n\n使用带头结点的单链表:\n");
    forward_list *t;
    t = creat_2();
    print_forward_list_2(t);
    
    search_2(t,6);
    list_length_2(t);
    printf("\n逆置:\n");
    reverse_2(t);
    print_forward_list_2(t);
    list_length_2(t);
        
    return 0;
}

运行结果

image

相关文章

  • 线性表(三)——双向链表的表示和实现

    在上篇文章中我们分析讨论了线性表的链式存储结构。链式存储结构表示的线性表主要分为单链表、单循环链表和双向循环链表三...

  • 线性表的链式存储--单链表

    Java之线性表的链式存储——单链表 我们都知道，线性表的存储结构分为两种，顺序存储结构和链式存储结构，线性表的分...

  • 数据结构——线性表

    线性表分为顺序存储结构和链式存储结构（单链表，静态链表，循环链表，双向链表）。 单链表（**一种动态结构，所占空间...

  • 考研数据结构笔记——2.线性表的链式表示（单链表）

    线性表的链式表示 单链表的定义 线性表的链式存储称为单链表；每个链表节点，除存放元素自身的信息外，还需要存放一个指...

  • 线性链表

    线性链表 线性表的顺序存储结构：顺序表线性表的链式存储结构：线性链表 线性表的链式存储所占存储空间大于顺序存储。 ...

  • 数据结构-线性表

    归纳 线性关系、线性表的定义，线性表的基本操作。 线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和...

  • 数据结构之线性表

    线性表 线性表：零个或多个数据元素的有限序列线性表的两种存储结构：顺序存储&链式存储 单链表结构&顺序存储结构对比...

  • 线性表的链式存储结构1.1

    这篇文章依然介绍线性表的链式存储结构-单链表 单链表的整表创建 线性表顺序存储结构的创建，其实就是一个数组的初始化...

  • 单链表实现链式线性表（C语言）

    单链表实现链式线性表

  • 线性表

    线性表是零个或者多个具有相同的数据元素的有限序列。 线性表的二大结构：顺序存储结构、链式存储结构（单链表、静态链表...

网友评论

      本文标题：线性表的链式存储-单链表

      本文链接：https://www.haomeiwen.com/subject/rnjnhqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|线性表的链式存储-单链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！