线性表练习题超详细解答

女爷i 2023-07-18 09:36 48阅读 0赞

> *天才亦是众生，众生皆怀其才。*

链表练习：

1有一个带头结点的单链表L，设计一个算法使其元素递增有序。

算法思想：用直接插入排序的方法，将链表分成两部分，每次取后部分一个元素插入前部分正确的位置上。

void sort(LinkList &L)
    {//本算法实现将一个链表元素升序排列
        
        if(L==NULL) return;
        LNode *pre,*p=L->next; //p指向要每次插入的元素，Pre指向要插入位置的前驱位置,pre->next指向的位置就是元素插入位置。
        LNode *r=p->next; //r指针用来防止断链，始终指向下一个待插入的元素，用以逐个向下遍历链表,
        
        p->next=NULL;//p把链表头指针和第一个元素作为前一个链表，剩余元素作为待插入元素的链表，两个表先断开
        p=r;
        while(p!=NULL)
        {
            r=p->next;
            pre=L;
            if(pre->next!=NULL&&pre->next->data<p->data)//保证pre下一个节点的元素是大于要插入元素的，则pre指向的位置就是待插元素正确位置
            {
                pre=pre->next;//从前往后找待插元素的正确位置。
            }
            p->next=pre->next;//待插元素归位
            pre->next=p;//待插前驱指向它
            p=r;//拿出下一个要插入的元素
        }
            
    }

2 将带头结点的单链表逆置。

算法思想：

法一：头插法按链表遍历次序再插入一遍

LinkList Reverse(LinkList &A)
    {
        LNode *p=A->next,*r;  //r用来暂存p的后继防止断链
        A->next=NULL;
        while(p!=NULL)
        {
            r=p->next;  //r用来暂存p的后继防止断链
            p->next=A->next;//头插法精华句一
            A->next=p;     //句二
            p=r;
        }
        return A;
    }

法二：把链表所有指针反向。

LinkList Reverse(LinkList &A)
    {
        LNode *p=A->next,*r=p->next,*pre;
        A->next=NULL;   //设置成空表
        while(p!=NULL)  //指针反向
        {
            pre=p;
            p=r;
            r=r->next;
            p->next=pre;
        }
        A->next=p;  //处理最后一个结点。
        return A;
    }

3 找到两个链表的公共结点

思路：链表的公共结点，也就是两个指针指向同一个结点，由于每个结点都只有一个指针域，从第一个公共结点之后两个链表就相当于一个链表。而公共结点之前的链表长短不一，需要找到两个表长的差值再同步遍历比较。

LinkList FindCommon(LinkList A,LinkList B)
    {
        int L1=Length(A),L2=Length(B),dist;//找出两个链表长度，算出两个链表长度差
        LNode *longlist,*shortlist;
        if(L1>L2)
        {
            longlist=A->next;
            shortlist=B->next;
            dist=L1-L2;
        }
        else
        {
            longlist=B->next;
            shortlist=A->next;
            dist=L2-L1;
        }
        while(dist--)//令长的和短的对齐，开始遍历
            longlist=longlist->next;
       while(longlist!=NULL)//此时两个链表剩余长度是相等的
       {
            if(longlist==shortlist)//找到公共结点
                return longlist;
            else    //没找到公共结点继续遍历
            {
                longlist=longlist->next;
                shortlist=shortlist->next;
            }
       }
       return NULL;
    }

4将一个链表A拆分成两个链表A和B，分别存储A中第奇数序号个元素和第偶数序号元素。

LinkList DisCreat(LinkList &A)
    {
        LinkList B=(LinkList)malloc(sizeof(LNode));//再创建一个链表头结点，也就是一个空链表
        B->next=NULL;
        LNode *p=A->next;//p是工作指针，依次向下遍历
        LNode *ra=A,*rb=B;//两个链表各设一个尾指针，用来插入元素，这里使用尾插法
        A->next=NULL;//原链表置空
        int i=0;//用来记录奇偶
        while(p!=NULL)
        {
            i++;
            if(i%2==0)//偶数插到B链表
            {
                rb->next=p;
                rb=p;
            }
            else//奇数插入A链表
            {
                rb->next=p;
                ra=p;
            }
            p=p->next;
        }
        return B;//返回B链表
    }

5在单链表内删除给定范围内的数。

void Dele(LinkList &A,int a,int b)
    {
        LNode *pre=A,*p=A->next;//p指向要删除元素，pre是待删除元素的前驱
        while(p!=NULL)
        {
            if(p->data>a&&p->data<b)//符合条件删除
            {
                pre->next=p->next;
                free(p);      //重点重点重点——一定要把删除后的结点空间释放
                p=pre->next;
            }
            else//不符合条件继续向下遍历
            {
                pre=p;
                p=p->next;
            }
        }
    }