2019-04-14 考研-线性表-链表

王道书上的代码

LinkList CreatList1(LinkList &L)
{
    LNode *s;
    int x;
    L = (LinkList)malloc( sizeof(LNode) );
    L->next=NULL;
    scanf("%d",&x);
    while(x!=0)
    {
        s = (LinkList)malloc( sizeof(LNode) );
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x); 
    }
    return L;   
} 

LinkList CreatList2(LinkList &L)
{
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s,*r=L;
    scanf("%s",&x);
    while(x!=0)
    {
        s=(LinkList)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;
    }
    r->next=NULL;
    return L;
}

LNode* GetElem(LinkList L,int i)
{
    int j=1;
    LNode *p=L->next;
    if(i==0) return L;
    if(i<0) return NULL;
    while( p && j<i ) //如果当前没有到达第 i 个节点( p没有指向第i个节点 )
    {
        p=p->next;
        j++;    
    } 
    return p; 
}

LNode *LocateElem(LinkList L,ElemType e)
{
    LNode *p=L->next;//指向第一个存放数据的节点 
    while(p!=NULL && p->data!=e) p=p->next;
    return p;
} 

自己写的和书上的答案

题目：1 
LinkList deletex(LinkList L,ElemType x)
{
    if(L!=NULL)
    {
        if(L->data==x) 
        {
            LNode *p=L->next;
            free(L);
            return deletex(p,x);
        }
        else
        {
            L->next=deletex(L->next,x);
            return L;
        }
    }
    return NULL;
} 
答案：
void delx(LinkList&L,ElemType x)
{
    LNode*p;
    if(L==NULL) return ;
    if(L->data==x)
    {
        p=L;
        L=L->next;
        free(p);
        delx(L,x);  
    } 
    else
    {
        delx(L->next,x);
    }
}
题目：2

// 这是一个带头结点的链表，真是让人窒息 
void delx(LinkList &L,ElemType x)
{
    if(L==NULL) return ; //如果头结点是空的，直接返回 
    while(L!=NULL && L->data==x) //如果头结点不为空并且值为x,删除这个结点并且修改头结点。 
    {
        LNode *p=L;
        L=L->next;
        free(p);
    }
    // 头结点为空或者不等于x的元素 
    LNode *p=L; 
    while( p != NULL )
    {
        //如果p指向的结点的下一个结点存在并且等于x 
        if( p->next!=NULL && p->next->data==x)
        {
            Node*tmp = p->next;
            p->next=p->next->next;
            free(tmp);      
        }
        p=p->next;
    }
}
答案：
void delx(LinkList&L,ElemType x)
{
    LNode *p=L->next,*pre=L,*q;
    while(p!=NULL)
    {
        if(p->data==x)
        {
            q=p;
            p=p->next;
            pre->next=p;
            free(q);    
        }
        else
        {
            pre=p;
            p=p->next;  
        }   
    } 
}


void delx(LinkList&L,ElemType x)
{
    LNode *p=L->next,*r=L,*q;
    while(p!=NULL)
    {
        if(p->data!=x)
        {
            r->next=p;
            r=p;
            p=p->next;  
        }   
        else
        {
            q=p;
            p=p->next;
            free(q);
        }
    } 
    r->next=NULL;
}
题目：3
void print(LinkList L)
{
    if(L==NULL) return;
    print(L->next);
    printf(L->data); 
}
void printLinkList(LinkList L)
{
    print(L->next);
}
答案：
题目：4
//  高兴的太早 
void delMin(LinkList& L)
{
    LNode*minpre=L,*minp=L->next;
    LNode*pre=L,*p=L->next;
    while(p!=NULL)
    {
        if(p->data < minp->data)
        {
            minp=p;
            minpre=pre;
        }
        pre=p;
        p=p->next;
    }
    minpre->next=minp->next;
    free(minp);
}
答案：
LinkList Delete_Min(LinkList &L)
{
    LNode *pre=L,*p=L->next;
    LNode *minpre=pre,*minp=p;
    while(p!=NULL)
    {
        if(p->data < minp->data)
        {
            minp=p;
            minpre=pre;
        }
        pre=p;
        p=p->next;
    }
    minpre->next=minp->next;
    free(minp);
    return L;   
} 
题目：5
LinkList reverse(LinkList L)
{
    // 写的完全不对啊啊啊啊啊啊啊啊啊啊 
    LNode *r=L,*p=L->next;
    while(p!=NULL)
    {
        r->next=p;
        r=p;
        p=p->next;
    }
    r->next=NULL;
    return L;
}
答案：
LinkList Reverse(LinkList L)
{
    LNode *p,*r;
    p=L->next;
    L->next=NULL;
    while(p!=NULL)
    {
        r=p->next;
        p->next=L->next;
        L->next=p;
        p=r;    
    }   
} 

LinkList Reverse(LinkList L)
{
    LNode *pre,*p=L->next,*r=p->next;
    p->next=NULL;
    while(r!=NULL)
    {
        pre=p;
        p=r;
        r=r->next;
        p->next=pre;
    }
    L->next=p;
    return L;
}
题目：6
void sort(LinkList &L)
{
    LinkList LL;
    LL->next=NULL;
    while(L->next!=NULL)//  当原来的链不为空表 
    {
        //  找到L剩下元素中最大的元素 
        LNode *maxpre=L,*maxp=L->next;
        LNode *pre=L,*p=L->next;
        while(p!=NULL)
        {
            //  找到最大的数据 
            if(maxp->data < p->data)
            {
                maxp=p;
                maxpre=pre;
            }
            pre=p;
            p=p->next;
        }
        
        maxpre->next=maxp->next;
        
        maxp->next=LL->next;
        LL->next=maxp;
        
        L=LL;       
    }
}
答案：
void Sort(LinkList &L)
{
    LNode *p=L->next,*pre;
    LNode *r=p->next;
    p->next=NULL;
    p=r;
    while(p!=NULL)
    {
        r=p->next;
        
        pre=L;
        while( pre->next->data!=NULL && pre->next->data < p->data )
            pre = pre->next;
            
        p->next=pre->next;
        pre->next=p;
        
        p=r;
    }
}
题目：7
void del(LinkList &L,ElemType a,ElemType b)
{
    LNode *pre=L,*p=L->next;
    while( p!=NULL )
    {
        if( p->data>a && p->data<b )
        {
            LNode *tmp = p;
            p=p->next;
            pre->next=p;
            free(tmp);
        }
        else
        {
            pre=p;
            pre->next=p;
        }
    }
}
答案：
void RangeDelete(LinkList &L,int min,int max)
{
    LNode *pr=L,*p=L->link;
    while(p!=NULL)
    {
        if(p->data>min && p->data<max)
        {
            pr->link=p->link;
            free(p);
            p=pr->link;
        }
        else
        {
            pr=p;
            p=p->link;
        }
    }
}
题目：8
LinkList theSame(LinkList L1,LinkList L2)
{
    int len1=0,len2=0,len;
    LNode *p1=L1->next,*p2=L2->next;
    
    while(p1!=NULL)
    {
        len1++;
        p1=p1->next;
    }
    
    while(p2!=NULL)
    {
        len2++;
        p2=p2->next;
    }
    
    p1=L1->next;
    p2=L2->next;
    if(len1>len2) 
    {
        for(int i=0;i<len1-len2;i++) p1=p1->next; 
    } 
    else
    {
        for(int i=0;i<len2-len1;i++) p2=p2->next;
    }
    
    len=min(len1,len2); 
    for(int i=0;i<len;i++)
    {
        if(p1->next==p2->next) return p1->next;
    }
    return NULL;
}
答案：
LinkList Search_lst_Common(LinkList L1,LinkList L2)
{
    int len1=Length(L1),len2=Length(L2);
    LinkList longList,shortList;
    if(len1>len2)
    {
        longList=L1->next; shortList=L2->next;
        dist=len1=len2;
    }
    else
    {
        longList=L2->next; shortList=L1->next;
        dist=len2-len1; 
    }
    
    while(dist--) longList=longList->next;
    
    while(longList!=NULL)
    {
        if(longList==shortList) return longList;
        else
        {
            longList=longList->next;
            shortList=shortList->next;
        }
    }
    return NULL;
}
题目：9
//   这种写法更加容易理解 
void solve(LinkList head)
{
    LNode *minpre,*minp;
    LNode *pre,*p;
    
    while(head->next!=NULL)
    {
        minpre=head,minp=head->next;
        pre=head,p=head->next;
        while(p!=NULL)
        {
            if(p->data < minp->data)
            {
                minpre = pre;
                minp = p;   
            }   
            pre = p;
            p = p->next;
        }   
        
        printf(minp->data);
        minpre->next=p->next;
        free(p);
        
    }
    free(head); 
}
答案：
void Min_Delete(LinkList &head)
{
    while(head->next!=NULL)
    {
        //用pre记录上一个最小值的上一个结点 
        LNode *pre=head,*p=head->next;//此时p指向第一个结点 
        while(p->next!=NULL)
        {
            //此时p指向第一个结点，p->next指向第二个结点
            //也就是说，这里的p充当了我的代码中的pre,这里的p->next充当了我的p 
            if(p->next->data < pre->next->data) pre = p;
            p=p->next;
        }
        print(pre->next->data);
        
    }
    free(head);
}
题目：10
void apart(LinkList& A,LinkList& B)
{
    LNode *pre=A,*p=A->next,*r;
    int cnt=0;
    B = (LNode*)malloc(sizeof(LNode));
    r = B;
    while(p!=NULL)
    {
        cnt++;
        if(cnt%2==0)
        {
            pre->next=p->next;
            r->next=p;
            r=p;
            p=p->next;
        }
        else
        {
            pre=p;
            p=p->next;
        }
    }
    r->next=NULL;
} 
答案：
LinkList DisCreat(LinkList &A)
{
    int i=0;
    B=(LinkList)malloc(sizeof(LNode));
    B->next=NULL;
    LNode *ra=A,*rb=B;
    LNode *p=A->next;
    A->next=NULL;
    while(p!=NULL)
    {
        i++;
        if(i%2==0)
        {
            rb->next=p;
            rb=p;   
        } 
        else
        {
            ra->next=p;
            ra=p;
        }
    }
    ra->next=NULL;
    rb->next=NULL;
    return B; 
}
题目：11
LinkList apart(LinkList& hc)
{
    LNode *p=hc->next,*hc2,*r=hc;//r记录最后一个结点的位置
    hc2 = (LinkList)malloc(sizeof(LNode));
    hc->next=NULL;
    hc2->next=NULL;
    int cnt=0;
    while(p!=NULL)
    {
        cnt++;
        LNode *tmp=p->next;
        if(cnt%2==1)
        {
            p->next=r->next;
            r->next=p;  
        }
        else
        {
            p->next=hc2->next;
            hc2->next=p;
        }
        p=tmp;  
    }
    return hc2;
}
答案：
LinkList DisCreat(LinkList& A)
{
    LinkList B=(LinkList)malloc(sizeof(LNode));
    B->next=NULL;
    LNode *p=A->next,*q;
    LNode *ra=A;
    while(p!=NULL)
    {
        ra->next=p; 
        ra = p;
        
        p=p->next;
        q=p->next;
        
        p->next=B->next;
        B->next=p;
        
        p=q; 
    }
    ra->next=NULL;
    return B;
}
题目：12
//  审题啊啊啊啊，拜托了，审题啊啊 
LinkList unique(SqList A)
{
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    LNode *r = L;
    for(int i=0;i<A.length;i++)
    {
        if(i==0 || A.data[i]!=A.data[i-1])
        {
            LNode *p = (LNode*)malloc(sizeof(LNode));
            p->data=A.data[i];
            p->next=r->next;
            r->next=p;
            r=p;
        }
    }
    return L;
}
答案：
void Del_same(LinkList &L)
{
    LNode *p=L->next,*q;
    if(p==NULL) return ;
    while(p->next!=NULL)
    {
        q=p->next;
        if(p->data==q->data)
        {
            p->next=q->next;
            free(q);    
        }
        else p=p->next; 
    }   
} 
题目：13
void MergeList(LinkList &La,LinkList &Lb)
{
    LNode *r,*pa=La->next,*pb=Lb->next;
    La->next=NULL;
    while(pa && pb)
    {
        if(pa->data<pb->data)
        {
            r=pa->next;
            pa->next=La->next;
            La->next=pa;
            pa=r;   
        }
        else
        {
            r=pb->next;
            pb->next=La->next;
            La->next=pb;
            pb=r;   
        }   
    }
    if(pa) pb=pa;
    while(pb)
    {
        r=pb->next;
        pb->next=La->next;
        La->next=pb;
        pb=r;   
    }   
    free(Lb);
} 
答案：

题目：14
void Get_Common(LinkList A,LinkList B)
{
    LNode *p=A->next,*q=B->next,*r,*s;
    LinkList C=(LinkList)malloc(sizeof(LNode));
    r=C; 
    while(p!=NULL && q!=NULL)
    {
        if(p->data<q->data) p=p->next;
        else if(p->data>q->data) q=q->next;
        else
        {
            s=(LNode*)malloc(sizeof(LNode));
            s->data=p->data;
            r->next=s;
            r=s;
            p=p->next;
            q=q->next;  
        } 
    }
    r->next=NULL;
}
答案：

题目：15
LinkList Union(LinkList &La,LinkList &Lb)
{
    LNode *pa=La->next;
    LNode *pb=Lb->next;
    LNode *pc=La;
    LNode *u;
    while(pa&&pb)
    {
        if(pa->data==pb->data)
        {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
            u=pb;
            pb=pb->next;
            free(u);    
        }
        else if(pa->data<pb->data)
        {
            u=pa;
            pa=pa->next;
            free(u);    
        }   
        else
        {
            u=pb;
            pb=pb->next;
            free(u);
        }       
    } 
    while(pa)
    {
        u=pa;
        pa=pa->next;
        free(u); 
    }
    while(pb)
    {
        u=pb;
        pb=pb->next;
        free(u);
    }
    pc->next=NULL;
    free(Lb);
    return La;
}
答案：

题目：16
int Pattern(LinkList  A,LinkList B)
{
    LNode *p=A;
    LNode *pre=A;
    LNode *q=B;
    while(p&&q)
    {
        if(p->data==q->data)
        {
            p=p->next;
            q=q->next;
        }
        else
        {
            pre=pre->next;
            p=pre;
            q=B;
        }
    }
    if(p==NULL) return 1;
    else return 0;
}
答案：

题目：17 
int Symmetry(DLinkList L)
{
    DNode *p=L->next,*q=L->prior;
    while(p!=q && q->next!=p)
    {
        if(p->data == q->data)
        {
            p=p->next;
            q=q->next;
        }
        else 
            return 0;
            
    }
    return 1;
}
答案：

题目：18
LinkList Link(LinkList &h1,LinkList &h2)
{
    LNode *p,*q;
    p=h1;
    while(p->next!=h1) p=p->next;
    q=h2;
    while(q->next!=h2) p=p->next;
    p->next=h2;
    q->next=h1;
    return h1;
}
答案：

题目：19
void del_all(LinkList &L)
{
    LNode *p,*pre,*minp,*minpre;
    while(L->next!=L)
    {
        p=L->next; pre=L;
        minp=p,minpre=L;
        while(p!=L)
        {
            if(p->data<minp->data)
            {
                minp=p;
                minpre=pre;
            }
            p=p->next;
            pre=pre->next;
        }
        printf("%d",minp->data);
        minpre->next=minp->next;
        free(minp);
    }
    free(L)
}
答案：

题目：20
DLinkList Locate(DLinkList &L,ElemType x)
{
    DNode *p=L->next,*q;
    while(p && p->data!=x) p=p->next;
    if(!p) exit(0);
    else
    {
        p->freq++;
        p->next->pred=p->pred;
        p->pred->next=p->next;
        while(q!=L && q->freq<=p->freq)
            q=q->prior;
        p->next=q->next;
        q->next->pred=p;
        p->pred=q;
        q->next=p;
    }
    return p;
}
答案：

题目：21
int Search(LinkList list,int k)
{
    LNode *p=list->next,*q=list->next;
    int count=0;
    while(p!=NULL)
    {
        if(count<k) count++;
        else q=q->next;
        p=p->next;
    }
    if(count<k) return 0;
    else
    {
        printf("%d",q->data);
        return 1;
    }
}
答案：

题目：22
int listlen(SNode *head)
{
    int len=0;
    while(head->next!=NULL)
    {
        len++;
        head=head->next;
    }
    return len;
}
SNode *find_addr(SNode *str1,SNode *str2)
{
    int m,n;
    SNode *p,*q;
    m=listlen(str1);
    n=listlen(str2);
    for(p=str1;m>n;m--) p=p->next;
    for(q=str2;n>m;n--) q=q->next;
    while(p->next!=NULL && p->next!=q->next)
    {
        p=p->next;
        q=q->next;
    }
    return p->next;
}
答案：

题目：23
typedef struct node{
    int data;
    struct node *link;
}NODE;
typedef NODE *PNODE;

void func(PNODE h,int n)
{
    PNODE p=h,r;
    int *q,m;
    q=(int*)malloc(sizeof(int)*(n+1));
    for(int i=0;i<n;i++) *(q+i)=0;
    while(p->link!=NULL)
    {
        m=p->link->data>0?p->link->data:-p->link->data;
        if(*(q+m)==0)
        {
            *(q+m)=1;
            p=p->link;
        }
        else
        {
            r=p->link;
            p->link=r->link;
            free(r);
        }
        free(p);
    }
}