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

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

作者: 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

    相关文章

      网友评论

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

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