• /*编写函数void delx(linklist head, datatype x),删除带头结点单链表head中第一个值为x 的结点。 并构造测试用例进行测试。 */ /**********************************/ /*文件名称:lab3_01.c */ /****************...
    /*编写函数void delx(linklist head, datatype x),删除带头结点单链表head中第一个值为x 的结点。
    并构造测试用例进行测试。
    */
    /**********************************/
    /*文件名称:lab3_01.c                 */
    /**********************************/
    #include "slnklist.h"
    /*请将本函数补充完整,并进行测试*/
    linklist delx(linklist head,datatype x)
    {
        linklist p,pre=head; //别忘了pre=head 
        p = head->next;
        while(p->info!=x) 
        {
            pre = p;
            p = p->next;
        }
        if(p)
        {
            pre->next = p->next;
            free(p);
        }
        return head;
    }
    
    int main()
    {   datatype x;
        linklist head;
        head=creatbyqueue();        /*尾插入法建立带头结点的单链表*/
        print(head);
        printf("请输入要删除的值:");
        scanf("%d",&x);
        head=delx(head,x);            /*删除单链表的第一个值为x的结点*/
        print(head);
        delList(head);                /*释放单链表空间*/
        return 0;
    }
    /**********************************/
    /*文件名称:lab3_02.c                 */
    /**********************************/
    /*
    假设线性表(a1,a2,a3,…an)采用带头结点的单链表存储,请设计算法函数linklist reverse(linklist  head),
    将带头结点的单链表head就地倒置,使表变成(an,an-1,…a3.a2,a1)。并构造测试用例进行测试。
    */
    #include "slnklist.h"
    /*请将本函数补充完整,并进行测试*/
    linklist reverse(linklist head)
    {
        //不带头节点是head,带头节点是head->next 
        linklist p,q;
        p = head->next;
        head->next = NULL;
        while(p)  
        {
            q = p->next;
            p->next = head->next;
            head->next = p;
            p = q;
        }
        return head;
    }
    int main()
    {   datatype x;
        linklist head;
        head=creatbystack();            /*头插入法建立带头结点的单链表*/
        print(head);                    /*输出原链表*/
        head= reverse(head);            /*倒置单链表*/
        print(head);                    /*输出倒置后的链表*/
        delList(head);
        return 0;
    }
    /*
    假设带头结点的单链表head是升序排列的,设计算法函数linklist insert(linklist head,datatype x),
    将值为x的结点插入到链表head中,并保持链表有序性。
    分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。
    */
    /**********************************/
    /*文件名称:lab3_03.c                 */
    /**********************************/
    #include "slnklist.h"
    /*请将本函数补充完整,并进行测试*/
    linklist insert(linklist head ,datatype x)
    {
        //要插入的数据s,位于pre和 p之间 
        linklist pre,p,s;
        s = (linklist)malloc(sizeof(node));
        s->info = x;
        p = head->next;
        pre = head;
        while(p&&p->info<x)   
        {
            pre = p;
            p = p->next; 
        } 
        pre->next = s;
        s->next = p;
        return head;
    }
    int main()
    {   datatype x;
        linklist head;
        printf("输入一组升序排列的整数:\n");
        head=creatbyqueue();                /*尾插入法建立带头结点的单链表*/
        print(head);
        printf("请输入要插入的值:");
        scanf("%d",&x);
        head=insert(head,x);                /*将输入的值插入到带头结点的单链表适当位置*/
        print(head);
        delList(head);
        return 0;
    }
    /*
    编写算法函数linklist delallx(linklist head, int x),删除带头结点单链表head中所有值为x的结点。
    */
    /**********************************/
    /*文件名称:lab3_04.c                 */
    /**********************************/
    #include "slnklist.h"
    /*请将本函数补充完整,并进行测试*/
    linklist delallx(linklist head,int x)
    {
        //不带头节点是head,带头节点是head->next 
        linklist p,t;
        while(head->next)//如果要删除的是第一个 
        {
            if(head->next->info==x)//如果第一个数=x 
            {
                p=head->next;//删除操作 
                head->next=head->next->next; 
                free(p);//回收p 
            } else {
                break;
            }
        }
        if(head->next)//如果删除的不是第一个 
        {
            p=head->next;
            while(p->next)
            {
                if(p->next->info==x)
                {
                    t=p->next;
                    p->next=p->next->next;
                    free(t);
                } else {
                    p=p->next;
                }
            }        
        }
        return head;
    }
    int main()
    {   datatype x;
        linklist head;
        head=creatbyqueue();                /*尾插入法建立带头结点的单链表*/
        print(head);
        printf("请输入要删除的值:");
        scanf("%d",&x);
        head=delallx(head,x);
        print(head);
        delList(head);
        return 0;
    }
    /*
    已知线性表存储在带头结点的单链表head中,请设计算法函数void sort(linklist head),将head中的结点按结点值升序排列。
    */
    /**********************************/
    /*文件名称:lab3_05.c                 */
    /**********************************/
    #include "slnklist.h"
    /*请将本函数补充完整,并进行测试*/
    void  sort(linklist head)
    {
         int temp; //temp是int类型,notice 
         linklist p,pre;
         pre=p=head->next;
         while(pre) //pre是前面那个数,p是后面那个数 
         {
             p=pre;//notice,p是从pre后面数里走 
             while(p)
             {
    
                 if(pre->info>p->info) //交换 
                 {
                     temp=p->info;
                     p->info=pre->info;
                     pre->info=temp;
                 }    
                 p=p->next;
             }
             pre=pre->next;
         }
         return head;
    }
    int main()
    {        linklist head;
             head=creatbyqueue();           /*尾插法建立带头结点的单链表*/
             print(head);                    /*输出单链表head*/
             sort(head);                     /*排序*/
             print(head);
             delList(head);
             return 0;
    }
    /*
    已知两个带头结点的单链表L1和L2中的结点值均已按升序排序,设计算法函数
    linklist mergeAscend (linklist L1,linklist L2)将L1和L2合并成一个升序的
    带头结单链表作为函数的返回结果;
    设计算法函数linklist mergeDescend (linklist L1,linklist L2)
    将L1和L2合并成一个降序的带头结单链表作为函数的返回结果;
    并设计main()函数进行测试。
    */
    /**********************************/
    /*文件名称:lab3_06.c                 */
    /**********************************/
    #include "slnklist.h"
    /*请将本函数补充完整,并进行测试*/
    linklist mergeAscend(linklist L1,linklist L2)//升序 
    {
        linklist head,x,y,p;
        head=(linklist)malloc(sizeof(node));
        head->next=NULL;
        p=head;
        x=L1->next;
        y=L2->next;
        while(x&&y)
        {
            //当比到最好一个元素的时候,会出现x->next=NULL或者是y->next=NULL
            if(x->info<=y->info)//L1里的数<L2的数 
            {
                //这两句是尾插法的核心 
                p->next=x; //把新元素插到当前元素后面去 
                p=x;  //吧当前指针指向新元素 
                x=x->next;
            }
            else
            {
                //这两句是尾插法的核心 
                p->next=y; //把新元素插到当前元素后面去 
                p=y;  //吧当前指针指向新元素 
                y=y->next;
            }
        }
        p->next=x?x:y; //把最后一个数加进去 
        return head;
    }
    linklist mergeDescend(linklist L1,linklist L2)//降序 
    {
    }
    int main()
    {       linklist h1,h2,h3;
             h1=creatbyqueue();     /*尾插法建立单链表,请输入升序序列*/
             h2=creatbyqueue();
             print(h1);
             print(h2);
             //升序合并请调用 
             h3=mergeAscend(h1,h2);
             //降序合并请调用
    //         h3=mergeDescend(h1,h2); 
             print(h3);
             delList(h3);
             return 0;
    }
    /*
    /*
    设计一个算法linklist interSection(linklist L1,linklist L2),
    求两个单链表表示的集合L1和L2的交集,并将结果用一个新的带头
    结点的单链表保存并返回表头地址。
    */
    /**********************************/
    /*文件名称:lab3_07.c                 */
    /**********************************/
    #include "slnklist.h"
    /*请将本函数补充完整,并进行测试*/
    linklist   interSection(linklist L1, linklist L2)
    {
        linklist head,p,s,x,y; //s是临时存储的结点 
        head=(linklist)malloc(sizeof(node));
        head->next=NULL;
        p = head;
        x = L1->next;
        y = L2->next;
        while(x) 
        {
            while(y)
            {
                if(x->info==y->info)
                {
                    s = (linklist)malloc(sizeof(node));
                    s->info = x->info;
                    p->next = s;  //这两句不能互换,因为是添加数据 
                    p = s;
                    break; //notice,不可省略 ,跳出本层循环 ,不执行y=y->next 
                }
                y = y->next;    
            }
            x = x->next;
        }
        p->next = NULL;
        return head;
    }
    int main()
    {
     linklist h1,h2,h3;
     h1=creatbyqueue();           /*尾插法建立单链表,输入时请勿输入重复数据*/
     h2=creatbyqueue();
     print(h1);                   /*输出单链表h1*/
     print(h2);
     h3=interSection(h1,h2);      /* 求h1和h2的交集*/
     print(h3);
     delList(h1);
     delList(h2);
     delList(h3);
     return 0;
    }
    /*
    请编写一个算法函数void partion(linklist head),
    将带头结点的单链表head中的所有值为奇数的结点调整
    到链表的前面,所有值为偶数的结点调整到链表的后面。
    */
    
    /**********************************/
    /*文件名称:lab3_08.c             */
    /**********************************/
    #include "slnklist.h"
    /*请将本函数补充完整,并进行测试*/
    void partion(linklist head)
    {
        linklist p,s,pre;
        pre=head;
        p=head->next;
        while(p)
        {
            if(p->info%2==0) //偶数 
            {
                pre=p;
                p=p->next;
            }
            else
            {
                s=p;
                pre->next=p->next;
                p=pre->next;
                s->next=NULL;
                s->next=head->next;
                head->next=s;
            }
        }
    
    }
    int main()
    {        linklist head;
             head=creatbyqueue();           /*尾插法建立带头结点的单链表*/
             print(head);                   /*输出单链表head*/
             partion(head);
             print(head);
             delList(head);
             return 0;
    }
    /*
    编写一个程序,用尽可能快的方法返回带头结点单链表中倒数第k个结点的地址,如果不存在,则返回NULL。
    */
    /**********************************/
    /*文件名称:lab3_09.c             */
    /**********************************/
    #include "slnklist.h"
    /*请将本函数补充完整,并进行测试*/
    linklist   search(linklist head,int k)
    {
        linklist p = head->next,x;
        int count = 0,i;
        x = p;
        while(x) //求链表长度 
        {
            count++;
            x=x->next;
        }        //获得倒数第k的值 
        for(i=0;i<count-k;i++)
        {
            p = p->next;
        }
        return p;
    }
    int main()
    {
         int k;
         linklist head,p;
         head=creatbyqueue();        /*尾插法建立带头结点的单链表*/
         print(head);                  /*输出单链表head*/
         printf("k=");
         scanf("%d",&k);
         p=search(head,k);
         if (p) printf("%d\n",p->info);
         else
             printf("Not Found!\n");
         delList(head);
         return 0;
    }

    slnklist.h

    #include <stdio.h>
    #include <stdlib.h>
    /**************************************/
    /* 链表实现的头文件,文件名slnklist.h */
    /**************************************/
     typedef int datatype;
     typedef struct link_node{
       datatype info;
       struct link_node *next;
     }node;
    typedef node *linklist;
    /******************************************/
    /*函数名称:creatbystack()                      */
    /*函数功能:头插法建立带头结点的单链表    */
    /******************************************/
    linklist creatbystack()
    {
    
        linklist  head,s;
        datatype x;
        head=(linklist)malloc(sizeof(node));
        head->next=NULL;
    
        printf("请输入整数序列(空格分开,以0结束):\n");
        scanf("%d",&x);
        while (x!=0)
        {
            s=(linklist)malloc(sizeof(node));
            s->info=x;
    
            s->next=head->next;
            head->next=s;
    
            scanf("%d",&x);
        }
        return head;
    }
    /***************************************/
    /*函数名称:creatbyqueue()                */
    /*函数功能:尾插法建立带头结点的单链表 */
    /***************************************/
    linklist creatbyqueue()
    {
        linklist head,r,s;
        datatype x;
        head=r=(linklist)malloc(sizeof(node));
        head->next=NULL;
        printf("请输入整数序列(空格分开,以0结束):\n");
        scanf("%d",&x);
        while (x!=0)
        {
             s=(linklist)malloc(sizeof(node));
             s->info=x;
             r->next=s; //把新元素放到当前元素后面 
             r=s;    //把当前指针指向新元素 
             scanf("%d",&x);
       }
        r->next=NULL;
        return head;
    }
    /**********************************/
    /*函数名称:print()                      */
    /*函数功能:输出带头结点的单链表      */
    /**********************************/
    void print(linklist head)
    {
        linklist p;
        int i=0;
        p=head->next;
        printf("List is:\n");
        while(p)
        {
            printf("%7d",p->info);
            i++;
            if (i%10==0)    printf("\n");
            p=p->next;
        }
        printf("\n");
    
    }
    
    /******************************************/
    /*函数名称:creatLink()                   */
    /*函数功能:从文件中读入n个数据构成单链表 */
    /******************************************/
    linklist creatLink(char *f, int n)
    {
        FILE *fp;
        int i;
        linklist s,head,r;
        head=r=(linklist)malloc(sizeof(node));
        head->next=NULL;
        fp=fopen(f,"r");
        if (fp==NULL)
            return head;
        else
        {
             for (i=0;i<n;i++)
                {
                    s=(linklist)malloc(sizeof(node));
                    fscanf(fp,"%d",&(s->info));
                    r->next=s;
                    r=s;
                }
            r->next=NULL;
            fclose(fp);
            return head;
        }
    }
    
    /*
        函数名称:writetofile
        函数功能:将链表内容存入文件f
    */
    void writetofile(linklist head, char *f)
    {
        FILE *fp;
        linklist p;
        int i=0;
        fp=fopen(f,"w");
        if (fp!=NULL)
        {
            p=head->next;
            fprintf(fp,"%s","List is:\n");
            while(p)
            {
                fprintf(fp,"%7d",p->info);
                i++;
                if (i%10==0)    fprintf(fp,"%c",'\n');
                p=p->next;
            }
            fprintf(fp,"%c",'\n');
            fclose(fp);
        }
        else    printf("创建文件失败!");
    
    }
    
    
    /**********************************/
    /*函数名称:delList()                  */
    /*函数功能:释放带头结点的单链表      */
    /**********************************/
    void delList(linklist head)
    { linklist p=head;
      while (p)
      { head=p->next;
        free(p);
        p=head;
      }
    }

    本文地址:http://liuyanzhao.com/3596.html

    转载请注明

    展开全文
  • 单链表的删除是将下一个节点移到待删除的节点上,只需移动这两个位置,其他的位置不用变化,这也是链表的优点。而数组的删除则是将待删除数值之后的所有数据移动一遍。 下面的程序是按照位置对链表的数值进行删除。...

    单链表的删除是将下一个节点移到待删除的节点上,只需移动这两个位置,其他的位置不用变化,这也是链表的优点。而数组的删除则是将待删除数值之后的所有数据移动一遍。

    下面的程序是按照位置对链表的数值进行删除。

    #include <stdio.h>  
    #include <malloc.h>  
    #include <time.h>
      
    typedef struct list  
    {  
        int vaule; //数据域  
        struct list *PNext; //指针域  
    }TNODE, *TPNODE;  
      
    TPNODE Creat_list();  
    void Trave_list(TPNODE _PHead);  
    int Delete_List(TPNODE _pHead, int _pos, int  *_iVal);
    
    int main()  
    {  
        int iVal = 0;
        int pos = 0;
        TPNODE PHead;
        srand((int)time(NULL));
        
        PHead = Creat_list();   //创建链表
        Trave_list(PHead);   //遍历链表
        
        printf("please input delete pos\n"); //想删除第几个数值
        scanf("%d", &pos);
    
        if(1 == Delete_List(PHead, pos, &iVal))//删除链表
        {
            printf("Delete fail\n");
        }
        else
        {
            Trave_list(PHead);   //遍历链表
            printf("%d had Delete\n", iVal); //输出刚才被删除的数值
        }
        
        return 0;  
    }  
      
    //创建链表  
    TPNODE Creat_list()  
    {  
        int i = 0;  
        int len = 0;  
        int iVaule = 0;  
      
        TPNODE pHead;  
        pHead = (TPNODE)malloc(sizeof(TNODE));  //创建一个头结点  
        if(NULL == pHead)   //创建失败
        {  
            printf("create list fail\n");  
        }  
      
        TPNODE PTail = pHead;  
        pHead->PNext = NULL;  
          
        printf("please input len of list\n");  
        scanf("%d", &len);  //输入想要的个数
        for(i = 0; i < len; i++)  
        {  
            iVaule = rand()%100+1;
      
            TPNODE pNew = (TPNODE)malloc(sizeof(TNODE)); //分配内存
              
            pNew->vaule = iVaule;  //将数据域赋予数据  
            PTail->PNext = pNew;  
            pNew->PNext = NULL;  
            PTail = pNew;  
        }  
          
        return  pHead;  
    }  
          
    //链表输出  
    void Trave_list(TPNODE _PHead)  
    {  
        int i = 0;
        TPNODE P = _PHead->PNext;  
      
        while(NULL != P)  
        {  
            i = 1;
            printf("%d ", P->vaule);  
            P = P->PNext;  
        }  
        if(1 == i)
        {
            printf("\n");
        }
    }  
    
    //链表删除
    int Delete_List(TPNODE _pHead, int _pos, int  *_iVal)
    {
        int i = 0;
        TPNODE p = _pHead;
        while(NULL != p->PNext && i < _pos-1)
        {
            p = p->PNext;
            //printf("val: %d\n", p->vaule);
            i++;
        }
    
       if(i > _pos -1 || NULL == p->PNext)
       {
            return 1; 
       }
    
        TPNODE q = p->PNext;
        *_iVal = p->PNext->vaule;
        p->PNext = p->PNext->PNext; //将待删除节点后面的一个节点放到待删除节点的位置
        
        free(q);
        q = NULL;
        return 0;
    }
    此程序的运行结果:



    创建链表:http://blog.csdn.net/z_dream_st/article/details/77142223

    链表的插入:http://blog.csdn.net/z_dream_st/article/details/77726255

    展开全文
  • 6-2单链表结点删除(20分) 时间限制: 400 ms 内存限制: 64 MB 代码长度限制: 16 KB 本题要求实现两个函数,分别将读入的数据存储为单链表、将链表中所有存储了某给定值的结点删除。链表结点定义如下: struct ...

    6-2 单链表结点删除 (20 分)

    时间限制: 400 ms     内存限制: 64 MB      代码长度限制: 16 KB

    本题要求实现两个函数,分别将读入的数据存储为单链表、将链表中所有存储了某给定值的结点删除。链表结点定义如下:

    struct ListNode {
        int data;
        ListNode *next;
    };
    

    函数接口定义:

    struct ListNode *readlist();
    struct ListNode *deletem( struct ListNode *L, int m );
    

    函数readlist从标准输入读入一系列正整数,按照读入顺序建立单链表。当读到−1时表示输入结束,函数应返回指向单链表头结点的指针。

    函数deletem将单链表L中所有存储了m的结点删除。返回指向结果链表头结点的指针。

    裁判测试程序样例:

    #include <stdio.h>
    #include <stdlib.h>
    
    struct ListNode {
        int data;
        struct ListNode *next;
    };
    
    struct ListNode *readlist();
    struct ListNode *deletem( struct ListNode *L, int m );
    void printlist( struct ListNode *L )
    {
         struct ListNode *p = L;
         while (p) {
               printf("%d ", p->data);
               p = p->next;
         }
         printf("\n");
    }
    
    int main()
    {
        int m;
        struct ListNode *L = readlist();
        scanf("%d", &m);
        L = deletem(L, m);
        printlist(L);
    
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    

    输入样例:

    10 11 10 12 10 -1
    10
    

    输出样例:

    11 12 

    struct ListNode *readlist()
    {
        struct ListNode *p1,*p2,*head;
        head=(struct ListNode*)malloc(sizeof(struct ListNode));
        p2=head;
        while(1)
    	{
            p1=(struct ListNode*)malloc(sizeof(struct ListNode));
            scanf("%d",&p1->data);
            if(p1->data==-1)
    		{
            break;
    		}
            p2->next=p1;
            p2=p1;
    	}
        p2->next=NULL;
    	head=head->next;
        return head;
    }
    
    struct ListNode *deletem( struct ListNode *L, int m )
    {
        struct ListNode *head1,*head2,*p1,*p2,*p;
    	p=L;
    	head1=(struct ListNode *)malloc(sizeof(struct ListNode));
    	head2=(struct ListNode *)malloc(sizeof(struct ListNode));
    	head1->next =NULL;
    	head2->next =NULL;
    	p1=head1;
    	p2=head2;
    	while(p)
    	{
    		if(p->data !=m)
    		{
    			p1->next =p;
    			p1=p;
    		}
    		else
    		{
    			p2->next =p;
    			p2=p;
    		}
    		p=p->next ;
    	}
    	p1->next =NULL;
    	p2->next =NULL;
    	return head1->next ;
    }

     

    展开全文
  • 数据结构-单链表节点的删除 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte 总提交:210 测试通过:106 描述 单链表节点的删除操作是线性表数据结构对象操作的重要内容,请您写一个程序...

    数据结构-单链表节点的删除

    时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
    总提交:210            测试通过:106

    描述

    单链表节点的删除操作是线性表数据结构对象操作的重要内容,请您写一个程序完成对一个单链表某一个节点的删除操作。

    请用如下函数完成上述功能,线性表List的定义如下(强烈建议使用下面的定义和函数结构)

    typedef struct LNode
    {
    Elemtype data;
    struct LNode *next;
    }LNode,*LinkList;

    int ListDelete_L(LinkList &L,int i,Elemtype &e)

    输入

    输入有多组测试数据,每组测试数据包括1行,用空格隔开的1个数字和多个字母,数字表示要删除节点在线性表中的位置,紧接着几个字母表示要删除节点线性表的名称,后面的字母表示线性表的当前的内容。

    输出

    如果删除失败,输出ERROR,否则输出OK,并输出删除节点后线性表的内容。

    样例输入

    7 L1 = (DEGIKNQTV)
    4 L2 = (CFG)

    样例输出

    ListDelete_L(L1, 7, e) = OK, L1 = (DEGIKNTV),  e = 'Q'
    ListDelete_L(L2, 4, e) = ERROR, L2 = (CFG)

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    typedef char  Elemtype;
    char a[10];
    char st;
    typedef struct LNode
    {
        Elemtype data;
        struct LNode *next;
    } LNode,*LinkList;
    void create(LinkList &l)
    {
        l=new LNode;
        LinkList k=new LNode;
         l->next=k->next=NULL;
        char str;
        int f=0;
        while(cin>>str&&str!='(')
        {
    
        }
        while(cin>>str&&str!=')')
        {
            LinkList p=new LNode;
            p->data=str;
            p->next=NULL;
            k->next=p;
            k=p;
            if(f==0)
            {
                l->next=k;
                f=1;
            }
        }
    }
    int ListDelete_L(LinkList &l,int i)
    {
        int j=1;
        LinkList k;
        LinkList p=new LNode;
        p=l;
        while(p&&j<i)
        {
            j++;
            p=p->next;
        }
        if(!p->next||j<i)
        {
            return 0;
        }
        k=p->next;
        st=k->data;
        //cout<<(p->next)->data<<endl;
        p->next=k->next;
        return 1;
    }
    void input(LinkList l)
    {
        LinkList p=new LNode;
        p=l->next;
        while(p)
        {
            cout<<p->data;
            p=p->next;
        }
    }
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            char b[100];
            LinkList la;
            scanf("%s",b);
            create(la);
            int k=ListDelete_L(la,n);
            if(k==0)
            {
                printf("ListDelete_L(%s, %d, e) = ERROR, %s = (",b,n,b);
                input(la);
                printf(")\n");
            }
            if(k==1)
            {
                printf("ListDelete_L(%s, %d, e) = OK, %s = (",b,n,b);
                input(la);
                printf("),  e = '%c'\n",st);
            }
        }
        return 0;
    }
    


    展开全文
  • 单链表的接本操作,有在单链表中插入,删除数据的功能,以及...1.单链表数据结构的建立实现。 2.单链表元素结点插入操作实现。 3.单链表元素结点删除操作实现。 4.实现单链表的合并。 5.实现一元多项式的相加。
  • PTA 习题11-8 单链表结点删除 (20分) 这道题我用了大概3个小时,在pta上提交了三次之后才最终正确。作为一个初次学习指针与链表的初学者,第一次做这种题的时候我觉得还是挺有难度的。主要还是因为作为初学者对指针...

    PTA 习题11-8 单链表结点删除 (20分)

    这道题我用了大概3个小时,在pta上提交了三次之后才最终正确。作为一个初次学习指针与链表的初学者,第一次做这种题的时候我觉得还是挺有难度的。主要还是因为作为初学者对指针和链表的理解与操作不够深入和熟练。在这里插入图片描述
    本题要求实现两个函数,分别将读入的数据存储为单链表、将链表中所有存储了某给定值的结点删除。链表结点定义如下:

    struct ListNode{
        int data;
        ListNode *next;
    };

    函数接口定义:

    struct ListNode *readlist();
    struct ListNode *deletem( struct ListNode *L, int m );

    函数 readlist 从标准输入读入一系列正整数,按照读入顺序建立单链表。当读到−1时表示输入结束,函数应返回指向单链表头结点的指针。
    函数 deletem 将单链表L中所有存储了m的结点删除。返回指向结果链表头结点的指针。

    裁判测试程序样例:

    #include <stdio.h>
    #include <stdlib.h>
    
    struct ListNode {
        int data;
        struct ListNode *next;
    };
    
    struct ListNode *readlist();
    struct ListNode *deletem( struct ListNode *L, int m );
    void printlist( struct ListNode *L )
    {
         struct ListNode *p = L;
         while (p) {
               printf("%d ", p->data);
               p = p->next;
         }
         printf("\n");
    }
    
    int main()
    {
        int m;
        struct ListNode *L = readlist();
        scanf("%d", &m);
        L = deletem(L, m);
        printlist(L);
    
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */

    输入样例:

    10 11 10 12 10 -1
    10

    输出样例:

    11 12

    代码

    struct ListNode *readlist()
    {
        struct ListNode *head = NULL;//链表头指针
        int num;
        scanf("%d", &num);
        while(num != -1)
        {
            //需要加上的节点
            struct ListNode *p = (struct ListNode *)malloc(sizeof(struct ListNode));
            p->data = num;
            p->next = NULL;
            struct ListNode *last = head;//指向链表的最后一个节点
            //第一个节点是一种特殊情况,此时last=NULL,必须让头指针指向第一个节点
            if(last)
            {
                while(last->next)
                {
                    last = last->next;
                }
                last->next = p;
            }
            else
            {
                head = p;
            }
            scanf("%d", &num);
        }
        return head;
    }
    
    struct ListNode *deletem( struct ListNode *L, int m )
    {
        struct ListNode *head = L;
        struct ListNode *p, *q, *r;//p指针在前用于遍历每个节点,q指针在后用于链接非m节点
        int ret = 1;
        for(q = NULL, p = head; p;)
        {
            if(p->data == m)
            {
                //移动p指针,直到p指向的节点不是m
                r = p;
                p = p->next;
                free(r);
            }
            else
            {
                ret = 0;
                //如果链表第一个节点不是m,此时q=NULL,这种特殊情况下,需要让q指向第一个节点
                if(q)
                {
                    q->next = p;
                    q = p;
                    p = p->next;
                    q->next = NULL;/*这句很重要,否则原链表以m结束时最后一个非m节点的next将会指向之后的节点,这会导致
                    最后一个或连续的m节点无法删除,因为虽然p是非m节点但之后是否还有非m节点并不知道,所以必须让q->next=NULL*/
                }
                else
                {
                    head = p;
                    q = p;
                    p = p->next;
                    q->next = NULL;
                }
            }
        }
        if(ret)//全是m节点,删除后是空链表,则需要让head = NULL
        {
            head = NULL;
        }
        return head;
    }
    展开全文
  • 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储...
  • 单链表结点的阶乘和 本题要求实现一个函数,求单链表L结点的阶乘和。这里默认所有结点的值非负,且题目保证结果在int范围内。 函数接口定义 int FactorialSum( List L ); 其中单链表List的定义如下: ...
  • C++ 单链表结点结构

    2019-12-22 21:40:22
    链表是一种常见的重要的数据结构。它是动态进行储存分配的一种结构 结点 每个结点包括两个数据,用户实际的数据+下一个结点的地址 最后一个元素 该元素不在指向其他元素,它的地址部分放NULL; 一串代码 struct ...
  • 单链表结点个数

    2016-08-28 15:30:52
    要获取单链表结点个数,需要判断单链表是不是空链表,如果是空链表,则返回0,如果不是,遍历单链表,定义当前结点指向头指针,然后while循环,只要满足当前结点不等于null,结点长度加1。实现过程分别是循环遍历和...
  • 111
  • 数据结构-单链表-基本操作(C/C++实现) 注意:本代码为了测试运行默认含有操作所需数据,如有需要可自己增删改相关数据 涉及基本运算 初始化单链表 依次采用尾插法插入元素 输出单链表 输出单链表的长度 判断...
  • 实现代码:#include #include<stdio.h>#define N 15typedef struct linklist { int data; struct linklist *next; }list, *plist;void create_list(plist* head) { int i;... if (NULL == *head)/*
  • 数据结构-单链表02

    2019-04-28 15:20:45
    单链表结构 将线性表L=(a 0 ,a 1 ,……,a n-1 )中各元素分布在存储器的不同存储块,称为结点,通过地址或指针建立它们 之间的联系,所得到的存储结构为链表结构。表中元素a i 的结点形式如图所示。 其中,结点的data...
  • 单链表是一种链式存取的数据结构,用一组地址任意的存储单元 存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结 点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位 置),元素就是存储数据...
  • 数据结构单链表插入、删除和修改实验报告 一、实验目的 1.理解数据结构中带头结点单链表的定义和逻辑图表示方法。 2.掌握单链表中结点结构的JAVA描述。 3.熟练掌握单链表的插入、删除和查询算法的设计与JAVA实现...
  • 数据结构-单链表建立

    2018-06-06 21:41:06
    顺序表是一组连续的存储单元来依次存储线性表中的结点,而链表是用一组任意的存储单元来存放线性表中的结点,这组存储单元可不连续分布在内存中的任何位置上。因此,链表中结点的逻辑顺序与存储顺序不一定相同。为了...
  • 线性表---单链表 typedef struct node {  ElemType data; //数据域  struct node *next;...链表:n个结点链接成起来形成一个链表,即为线性表的 链式存储结构 单链表结点中只包含一个指针域 ...
  • 在链表存储中,每个结点不仅包含所有的元素的信息,还包含元素之间逻辑关系的信息,如单链表中前驱结点包含后继结点的地址信息,这样就可以通过前驱结点中的地址信息找到后继结点的位置。 (2)单列表 在每个节点...
  • 链表:单链表、双链表、循环链表、静态链表 思考 单链表的定义 1.什么是单链表 2.用代码定义一个单链表 3.两种实现方式 1).带头结点 2).不带头结点 一、顺序表和单链表的对比 顺序表 单链表 ...
1 2 3 4 5 ... 20
收藏数 34,622
精华内容 13,848