数据结构线性表部分习题(一)

最近有考研的打算，准备考研科目，先是数据结构部分。习题如下；

1、求从大到小排序的L1,L2,L3交集（其中可能有多个相同元素在里面），最终结果也要按照从大到小的顺序排列，且不允许有重复值！！！

Linklist Interaction(Linklist L1,Linklist L2,Linklist L3){
    node *p = L1->next;
    node *q = L2->next;
    node *r = L3->next;
    L1->next=NULL;  #条件是求L1，使其包含三个表的交集，所以保留L1的结构
    free(L2);
    free(L3);
    while(p&&q&&r){
        node *tep;
        #node *t;
        if(p->data == q->data == r->data)#都相等把元素插入到L1中，然后三个表都做后移操作，进行下一轮比较
        {
            tem = p;
            p = p->next;
            tem->next = L1->next;
            L1->next = tem;#此法为前插法，后插法的操作是加一个指针t，移动t的位置进行插入，上述的让t=L1,然后把L1换成t,
            tem = q;#在这一步前面加上t=tem操作就可实现后插操作
            q = q->next;
            free(tem);
            tem = r;
            r = r->next;
            free(tem);
        }
        if(p->data <= q->data&&p->data <= r->data)
        {
            tem = p;
            p = p->next;
            free(tem);
        }
        elif(q->data <= p->data&&q->data <= r->data)
        {
            tem = q;
            q = q->next;
            free(tem);
        }
        else
        {
            tem = r;
            r = r->next;
            free(tem);
        }
        while(p){#到这一步说明有一个表已经到最后了，这样其他的表里面剩余的元素就没有共同的了，全部删除就可
            tem = p;
            p = p->next;
            free(tem);
        }
        while(q){
            tem = q;
            q = q->next;
            free(tem);
        }
        while(r){
            tem = r;
            r = r->next;
            free(tem);
        }
        return L1;

    }
}
#总结一下
###三个表的元素一起拿出来比大小，最小的往后推一位，
####如果都相等就把元素插入（前插法）L1中（要是题目要求最后目标也是有顺序的话，可以进行后插法的操作

2、已知L为链表的头结点地址,表中共有m(m>3)个结点,从表中第i个结点l

个结点构成一个循环部分链表,设计将这部分循环链表中所有结点顺序完全倒置的算法。

void Reverse(Linklist h){
    node *p = h->next;
    h->next = NULL;
    while(p){
        node *q = p;
        p = p->next;
        q->next = h->next;
        h->next = q;

    }
}
void Cicular_Reverse(lisklist head, int i, int m){
    node *pi,*pm,*p = head;
    for(int j = 0; j<m ;++j){
        p = p->next;       //一直循环后移，知道j=i-1，这时候p指向第i-1个元素，赋值给pi
        if(j = i-1){
            pi = p;
        }
    }
    p = p->next;   //出循环后p指向第m-1个元素在后移一个到最后一个元素m上
    pm = p;
    p = pi;
    pi = pi->next; //此时p指向i的前驱，pi指向i ，pm指向最后一个元素m
    Reverse(p);  //把p后面所有元素逆置，就是相当于把p做头节点，p后面一个元素做首元结点也就是pi(i元素)
    pi->next = pm;
}

3、

设有一个由正整数组成的无序单链表,编写算法实现下列功能:

(1) 找出最小值结点,且显示该数值。

(2) 若该数值为奇数,则将其与直接后继结点的数值交换。

(3) 若为偶数,则将其直接后继结点删除。

void outmin(LinkList L)
{
    LinkList p=L,q=L;
    int temp;
    while(q)
    {   
        if(p.data>q.data)
        {
            p=q;
        }
        q=q.next;
        
    }
    printf("%d",p.data);
    if(p.next)
    {   
        if(p.data%2==1)
        {
            temp=p.data;p.data=p.next.data;p.next.data=temp;
        }
    else
    {
        q=p.next;p.next=q.next;free(q);
        }
    }
}

 4、L1，和L2分别为两个单链表头结点地址指针，且两个表中数据结点的数据域均为一个字母（见图1-1-5)，设计一个空间复杂度为0(1）且时间上尽可能高效的算法，把L与L中相同的一段链结点顺序完全倒置（一个结点最多倒置一次)。

 

typedef struct node{
    char data;
    struct node *next;
}node,Linklist;
linklist a,b;
void Reverse(Linklist h, Linklish q){
    node *p = h->next;
    h->next = q;  //指向最后一个元素，相当于头插逆置
    while(p!=q){
        node *tem = p;
        p = p->next;
        tem->next = h->next;
        h->next = tem;
    }
}

void  Substr_Reverse(Linklist L1, Linklist L2){
    if(!L1->next ||!L2->next){//有一个为空就退出
        return;
    }
    node *start = L1, *p = start->next, *q = L2->next; //p指向L1第一个元素，q指向L2的第一个元素
    while(p){
        while(p&&q&&p-data == q->data){ //让q和p进行模式比较
            p = p->next;
            q = q->next;
        }
        if(!q){   //执行这一步模式匹配完，进行逆置操作
            Reverse(start,p); //逆置说明q的所有元素在p某一段，那就从头逆置
            start = p;  //从匹配成功的后一个元素开始匹配下一次，q还是从头来
            p = start->next;
            q = L2->next;
        }
        else if(!p){ //目标串匹配完，直接结束
            break;
        }
        else{ // 匹配失败 ，p从第二个元素开始，q还是从第一个元素开始匹配
            start = start->next;
            p = start->next;
            q = L2->next;
        }
    }
}