您的位置:js12345金沙官网登入 > 网络编程 > 链表习题

链表习题

2019-10-02 10:01
  1. 设计一个递归算法,删除不带头结点的单链表L中的所有值为x的结点。

本习题均不配备主函数程序,但是代码全通过编译且运行结果正确,各位看官老爷可以自己写所需要的主程序然后测试。

习题所需要的数据结构和基础函数

void delX(linkList &L, int x) { Node *p; if (L == NULL) return; if (L->data == x) { p = L; L = L->pNext; free; delX; } else delX(L->pNext, x);}

0.1 基础数据结构

  1. 在带头结点的单链表L中,删除所有值为x的结点,并释放其空间,假设值为x的结点不唯一。
typedef int ElemType;

typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, LinkList;

typedef struct DulNode {
    ElemType data;
    ElemType fred;
    struct DulNode *prior;
    struct DulNode *next;
} DulNode, DuLinkList;

0.2 初始化链表函数:

void delX_1(linkList &L, int x) { Node *p = L->pNext, *pre = L, * q; while (p!=nullptr){ if (p->data == x) { q = p; p = p->pNext; pre->pNext = p; free; } else { pre = p; p = p->pNext; } }}void delX_2(linkList &L, int x) { Node *p = L->pNext, *r = L, *q; while (p != nullptr) { if (p->data != x) { r->pNext = p; r = p; p = p->pNext; } else { q = p; p = p->pNext; free; } } r->pNext = nullptr;}
LinkList *linkInit(LinkList *L, int length) {
    Node *p, *q;
    L = malloc(sizeof(Node));
    p = L;
    for (int i = 1; i <= length; i++) {
        q = malloc(sizeof(Node));
        q->data = i;
        p->next = q;
        p = q;
    }
    p->next = NULL;
    return L;
}
  1. 设L为带头结点的单链表,编写算法实现从尾到头反向输出每个结点的值。

0.3 输出链表函数:

void linkPrint(LinkList *L) {
    LinkList *q;
    q = L->next;
    while (q != NULL) {
        printf("data: %dn", q->data);
        q = q->next;
    }
}
void reverse_traverse(linkList L,int cnt) { Node *p = L->pNext; if  { reverse_traverse(p, cnt + 1); if  cout << p->data << " "; else cout << p->data << endl; }}//我带了格式化输出

习题部分

  1. 试编写在带头结点的单链表L中删除一个最小值结点的高效算法(假设最小值结点是唯一的)
  1. 设计一个递归算法,删除不带头结点的单链表 L 中所有值为 x 的结点。
void deleteMin(linkList &L) { Node *p = L->pNext, *pre = L,*minNode = p , *minNodePre = L; while (p != nullptr) { if ( p->data < minNode->data ) { minNode = p; minNodePre = pre; } pre = p; p = p->pNext; } minNodePre->pNext = minNode->pNext; free;}
void linkFunc1(LinkList *L, ElemType x) {
    LinkList *p;
    if (L->next == NULL)
        return;
    if (L->data == x) {
        p = L;
        L = L->next;
        free(p);
        linkFunc1(L, x);
    } else
        linkFunc1(L->next, x);
}
  1. 试编写算法将带头指针的单链表就地逆置,辅助空间复杂度为O

注:递归过程中,传递进去的 L 实际上是 L->next 的引用。所以递归的时候就等价于:L->next = L->next->next; 因此不存在断链。

  1. 在带头结点的单链表 L 中,删除所有值为 x 的结点,并释放其空间,假设值为 x 的结点不唯一,试编写算法以实现上述操作。
void reverse_1(linkList &L) { Node *p = L->pNext, *next; L->pNext = nullptr; while  { next = p->pNext; p->pNext = L->pNext; L->pNext = p; p = next; }}void reverse_2(linkList &L) { Node *p = L->pNext, *next = p->pNext; Node *pre; p->pNext = nullptr; while  { pre = p; p = next; next = next->pNext; p->pNext = pre; } L->pNext = p;}
  1. 有一个带头结点的单链表L,设计一个算法使其元素递增有序。
void linkFunc2(LinkList *L, ElemType x) {
    LinkList *pre = L, *p = L->next, *q;
    while (p != NULL) {
        if (p->data == x) {
            q = p;
            p = p->next;
            pre->next = p;
            free(q);
        } else {
            pre = p;
            p = p->next;
        }
    }
}
  1. 设 L 为带头结点的单链表,编写算法实现从尾到头反向输出每个结点的值。
void sort_increase(linkList &L) { Node *p = L->pNext, *pre; Node *r = p->pNext; p->pNext = nullptr; p = r; while  { r = p->pNext; pre = L; while (pre->pNext != nullptr && pre->pNext->data < p->data) pre = pre->pNext; p->pNext = pre->pNext; pre->pNext = p; p = r; }}
  1. 设在一个带表头结点的单链表中所有元素结点的数据值无序,编写一函数,删除表中所有介于给定的两个值之间的元素。
void linkFunc3(LinkList *L) {
    if (L->next != NULL)
        linkFunc3(L->next);
    printf("%dn", L->data);
}

注:个人感觉这个递归的思路很巧妙,说实话递归感觉是比较难想到的。

void del_between_AandB(linkList &L, int a, int b) { Node *p = L->pNext, *pre = L; while  { if (p->data >= a && p->data <= b) { Node *temp = p; p = p->pNext; pre->pNext = p; free; } else { pre = p; p = p->pNext; } }}
  1. 试编写在带头结点的单链表 L 中删除一个最小值结点的高效算法(假设最小值结点是唯一的)。
  1. 给定两个单链表,找出两个链表的公共结点。
void linkFunc4(LinkList *L) {
    LinkList *pre = L, *p = L->next, *minPre = L, *min = L->next, *q;
    while (p->next != NULL) {
        if (p->data < min->data) {
            minPre = pre;
            min = p;
        } else {
            pre = p;
            p = p->next;
        }
    }
    q = min;
    min = min->next;
    minPre->next = min;
    free(q);
}
linkList search_first_common(linkList L1, linkList L2) { int len1 = length, len2 = length; int sub = abs(len1 - len2); linkList long_list, short_list; if (len1 > len2) long_list = L1->pNext, short_list = L2->pNext; else long_list = L2->pNext, short_list = L1->pNext; while  long_list = long_list->pNext; while (long_list) { if (long_list == short_list) return long_list; else long_list = long_list->pNext, short_list = short_list->pNext; } if (long_list == nullptr) return nullptr;}
  1. 金沙澳门娱乐网址,试编写算法将带头结点的单链表就地逆置,所谓 “就地” 是指空间复杂度为 O(1)。
    解 1 :
    注:采用头插法,可以把 L 断链后当成新初始化的链表,然后从原链表摘下一个结点插入到头部。
  1. 给定一个带表头结点的单链表,按递增次序输出单链表中各个结点的数据元素,并释放结点所占的存储空间。(不允许使用数组作为辅助空间)
void linkFunc5_1(LinkList *L) {
    LinkList *p = L->next, *q;
    L->next = NULL;
    while (p != NULL) {
        q = p;
        p = p->next;
        q->next = L->next;
        L->next = q;
    }
}
void print_increase(linkList &L) { linkList pre, p; while (L->pNext) { pre = L; p = pre->pNext; while (p->pNext) { if (p->pNext->data < pre->pNext->data) pre = p; p = p->pNext; } cout << pre->pNext->data; linkList temp = pre->pNext; pre->pNext = temp->pNext; free; } free;}

解 2:
注:这个不好想,但是注意这几道题,链表的操作顺序是有共性的。基本都是保存第一顺位的结点,然后向后递延。

  1. 将一个带头结点的单链表A分解为两个带头结点的单链表A和B,使得A中含有原表中序号为奇数的元素,B中含有原表中序号为偶数的元素,保持相对顺序不变。
void linkFunc5_2(LinkList *L) {
    LinkList *p = L->next, *r = p->next, *pre;
    p->next = NULL;
    while (r != NULL) {
        pre = p;
        p = r;
        r = r->next;
        p->next = pre;
    }
    L->next = p;
}
  1. 暂时略过

  2. 设有一个代表头结点的单链表中所有元素结点的数据值无序,试编写一个函数,删除表中所有介于给定两个值之间的元素(s<t)

void split_list_to_a_b(linkList L, linkList a, linkList b) { Node *p = L; int i = 0; Node *pa = a; Node *pb = b; while (p->pNext) { if (i % 2 == 1) { pa->pNext = p->pNext; pa = pa->pNext; p = p->pNext; print_node; } else { pb->pNext = p->pNext; pb = pb->pNext; p = p->pNext; print_node; } i++; } pa->pNext = nullptr; pb->pNext = nullptr;}
  1. 在一个线性递增的有序单链表中,有数值相同的元素存在,设计算法去除数值相同的元素,使表中不再有重复的元素。
void linkFunc7(LinkList *L, int s, int t) {
    LinkList *pre = L, *p = L->next, *q;
    while (p)
        if (p->data > s && p->data < t) {
            q = p;
            p = p->next;
            pre->next = p;
            free(q);
        } else {
            pre = p;
            p = p->next;
        }
}
  1. 给定两个单链表,编写算法找出两个链表的公共结点
void uniquify_sortedList(linkList L) { linkList p = L->pNext, temp = p; while (p->pNext) { temp = p->pNext; if (temp->data == p->data) { p->pNext = temp->pNext; free; }else p = p->pNext; }}

哇题目好多,写到晕厥!!加上链表实现快400行代码了。。下次再补!!

LinkList *linkList8(LinkList *A, int lengthA, LinkList *B, int lengthB) {
    int dist;
    LinkList *longList, *shortList;
    if (lengthA > lengthB) {
        dist = lengthA - lengthB;
        longList = A->next;
        shortList = B->next;
    } else {
        dist = lengthB - lengthA;
        longList = B->next;
        shortList = A->next;
    }
    while (dist--)
        longList = longList->next;
    while (longList)
        if (longList == shortList)
            return longList;
        else {
            longList = longList->next;
            shortList = shortList->next;
        }
    return NULL;
}
  1. 给定一个代表头结点的单链表,设 head 为头指针,结点结构为(data,next),data 为整型元素,next 为指针,试写出算法: 按递增次序输出单链表中各结点的数据元素,并释放节点所占空间(要求:不允许使用数组作为辅助空间)
void linkList9(LinkList *L) {
    while (L->next) {
        LinkList *pre = L, *p = pre->next, *q;
        while (p->next) {
            if (p->next->data < pre->next->data)
                pre = p;
            p = p->next;
        }
        printf("%d", pre->next->data);
        q = pre->next;
        pre->next = q->next;
        free(q);
    }
    free(L);
}
  1. 将一个带头节点的单链表 A 分解为两个带头结点单链表 A 和 B,使得 A 表中含有原表中序号为奇数的元素,而 B 表中含有原表中序号为偶数的元素,且保持其相对顺序不表。
LinkList *linkList10(LinkList *A) {
    LinkList *B = malloc(sizeof(Node));
    LinkList *ra = A, *rb = B, *p = A->next;
    A->next = NULL;
    B->next = NULL;
    while (p) {
        ra->next = p;
        ra = p;
        p = p->next;
        rb->next = p;
        rb = p;
        p = p->next;
    }
    ra->next = NULL;
    rb->next = NULL;
    return B;
}

本文由js12345金沙官网登入发布于网络编程,转载请注明出处:链表习题

关键词:

  • 上一篇:没有了
  • 下一篇:没有了