数据结构第二章作业

---

第一题

假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

节点结构：

typedef struct node
{
    int data;
    struct node *next;
} linknode, *link;

link Union(link la, link lb)

解：

先分别逆序，再正常归并即可。

void Reverse(link head) {
    if (head->next == NULL) return;
    link pre = NULL;
    link cur = head->next;
    link nex = NULL;
    while (cur != NULL) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    head->next = pre;
}
link Union(link la, link lb) {
    Reverse(la), Reverse(lb);
    link a = la->next; 
    link b = lb->next;
    link head = (link) malloc(sizeof(linknode));
    link tail = head;
    while (a != NULL && b != NULL) {
        if (a->data > b->data) {
            tail->next = a;
            a = a->next;
        } else {
            tail->next = b;
            b = b->next;
        }
        tail = tail->next;
    }
    tail->next = (a != NULL) ? a : b;
    free(la), free(lb);
    return head;
}

---

第二题

请在下列算法的横线上填入适当的语句。

typedef struct node
{
    int data;
    struct node *next;
} linknode, *link;

bool inclusion(link ha, link hb) : boolean;
/* 以ha和hb为头指针的带头节点单链表分别表示递增有序表A和B，本算法判别表A是否包含在表B内，若是，则返回“true”，否则返回“false” */
{
    pa = ha->next; pb = hb->next; (1) ;
    while ( (2) )
    {
        if (pa->data == pb->data)
            (3) ;
        else
            (4) ;
    }
    (5) ;
}

解：

bool inclusion(link ha, link hb) : boolean;
/* 以ha和hb为头指针的带头节点单链表分别表示递增有序表A和B，本算法判别表A是否包含在表B内，若是，则返回“true”，否则返回“false” */
{
    pa = ha->next; pb = hb->next; bool ok;
    while (pa != NULL && pb != NULL and pa->data >= pb->data)
    {
        if (pa->data == pb->data)
            pa = pa->next, pb = pb->next;
        else
            pb = pb->next;
    }
    return ok = (pa == NULL);
}

---

第三题

请写一算法link LinkListSort(link la)，将不带头结点的单链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。

typedef struct node
{
    int data;
    struct node *next;
} linknode, *link;

link LinkListSort(link list)

解：

link LinkListSort(link list) {
    if (list == NULL || list->next == NULL) {
        return list;  // 空链表或单节点直接返回
    }
    bool swapped;
    do {
        swapped = false;
        link pre = NULL;      // 前驱节点
        link cur = list;      // 当前节点
        link nex = cur->next; // 后继节点
        while (nex != NULL) {
            if (cur->data > nex->data) {
                if (pre == NULL) {
                    list = nex; 
                } else {
                    pre->next = nex;
                }
                cur->next = nex->next;
                nex->next = cur;
                swapped = true;
                pre = nex;     
                nex = cur->next; 
            } else {
                pre = cur;
                cur = nex;
                nex = nex->next;
            }
        }
    } while (swapped);
    return list;
}

---

第四题

写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。 结点结构为：(prev,data,next)

void solve(link p) {
    link q = p->prev;
    q->prev->next = p;
    p->next->prev = q;
    q->next = p->next;
    p->prev = q->prev;
    q->prev = p;
    p->next = q;
}