数据结构第二周 ：（顺序表求差集 +左奇右偶调整顺序表 + 合并有序单链表）

目录

• 两个顺序表集合的差集
• 顺序表左奇右偶的调整
• 两个���序单链表的合并

  两个顺序表集合的差集

  【问题描述】两个顺序表集合的差集

  （）

  【样例输入】

  25 33 57 60 48 9 13 0

  （）

  12 50 23 60 4 34 25 13 0

  【样例输出】

  33 57 48 9

  #include#define Maxsize 100#define Elemtype inttypedef struct{    Elemtype elem[Maxsize];    int last;}SeqList;void InitList(SeqList * L){    L->last = -1; //表示表中无元素}void Input(SeqList * L){    int i = -1;    while(1){        Elemtype num;        scanf("%d",&num);        if(num != 0){            i++;            L->elem[i] = num;            L->last++;        }        else break;    }}void Output(SeqList * L){    int i;    for(i = 0; i last; i++){ //last为最后一个元素在数组中的位置        printf("%d ",L->elem[i]);    }    printf("\n");}void Difset(SeqList * La,SeqList * Lb,SeqList * Lc){    int i,j,k;    k = -1;    for(i = 0; i last; i++){        int flag = 0;        for(j = 0; j last; j++){            if(La->elem[i] == Lb->elem[j]){                flag = 1;                break;            }            if(La->elem[i] != Lb->elem[j]){                continue;            }        }        if(!flag){            k++;            Lc->elem[k] = La->elem[i];            Lc->last++;        }    }}int main(){    SeqList La,Lb,Lc;    InitList(&La);    InitList(&Lb);    InitList(&Lc);    Input(&La);    Input(&Lb);    Difset(&La,&Lb,&Lc);    Output(&Lc);    return 0;}

  顺序表左奇右偶的调整

  【问题描述】用课堂中讲解的方法调整顺序表的数据，使得左边为奇数，右边为偶数，要求时间复杂度为O(n)。

  【样例输入】25 34 57 50 16 48 9 62 0

  【样例输出】25 9 57 50 16 48 34 62

  【注意】0代表输入的结束

  #include#define Maxsize 100typedef struct{    int elem[Maxsize];    int last;}SeqList;void IniList(SeqList * L){    L->last = -1; //表示表中无元素}void Input(SeqList * L){    int i = -1;    while(1){        int num;        scanf("%d",&num);        if(num != 0){            i++;            L->elem[i] = num;            L->last++;        }        else break;    }}void Fanz(SeqList * L){    int i = 0;    int j = L->last;    while(i elem[i] % 2 != 0){ //为奇数            i++;        }        while(L->elem[j] % 2 == 0){            j--;        }        if(i elem[i];            L->elem[i] = L->elem[j];            L->elem[j] = temp;        }    }}void Output(SeqList * L){    int i; //int i 要单独写在for外面    for(i = 0; i last; i++){ //last为最后一个元素在数组中的位置        printf("%d ",L->elem[i]);    }    printf("\n");}int main(){    SeqList L;    IniList(&L);    Input(&L);    Fanz(&L);    Output(&L);    return 0;}

  两个有序单链表的合并

  【问题描述】两个不带头结点的有序单链表LA和LB的合并，请合并到LA表中再输出，LB表的空间全部释放。

  【样例输入】

  1 3 5 7 9 0

  1 2 3 4 15 20 0

  【样例输出】

  1 2 3 4 5 7 9 15 20

  【注意】0代表输入结束

  #include#includetypedef struct Node{    int data;    struct Node* next;}Node,*Linklist;void InitList(Linklist* L){ //指针指向 一个指向节点的 指针    *L = (Linklist)malloc(sizeof(Node)); //建立头节点    (*L)->next = NULL; //头节点next为空}void CreatFromTail(Linklist L){ //L是指向带头结点的空链表    Node *p,*pr;    pr = L;    p = NULL;    while(1){        int num;        scanf("%d",&num);        if(num == 0){            break;        }        else{            p = (Linklist)malloc(sizeof(Node));            p->data = num;            if(L->next == NULL){                L->next = p;                p->next = NULL;                pr = pr->next; //pr永远指向最后一个节点            }            else{                pr->next = p;                p->next = NULL;                pr = pr->next;            }        }    }}void MergeList(Linklist La,Linklist Lb,Linklist Lc){    Linklist p,q,t;    p = La->next;    q = Lb->next;    t = Lc;    while(p != NULL && q != NULL){        if(p->data data){            t->next = p;            t = p; //t指向p指的位置，而不是t跟着p            p = p->next;        }        else if(q->data == p->data){ //if 后的两个else只可择其一            if(q->next != NULL){                q = q->next;            }            else{                p = p->next;            }        }        else{//不能用if(q->data data) 可能会存在空的现象，if会判断，else会跳过            t->next = q;            t = q;            q = q->next;        }    }        if(p != NULL){            t->next = p;        }        if(q != NULL){            t->next = q;        }}void Output(Linklist L){    Linklist p;    p = L->next; //指向头节点后的第一个节点    while(p->next != NULL){        printf("%d ",p->data);        p = p->next;    }    printf("%d",p->data); //输出最后一个节点    printf("\n");}int main(){    struct Node* La = NULL;    struct Node* Lb = NULL;    struct Node* Lc = NULL;    InitList(&La); //形参为二级指针，应该传指针的地址    InitList(&Lb);    InitList(&Lc);    CreatFromTail(La);    CreatFromTail(Lb);    MergeList(La,Lb,Lc);    Output(Lc);    return 0;}