数据结构题集 | 第2章 线性表

内容纲要

@[toc]

一、基础知识题

2.1(1) 描述以下三个概念的区别:头指针、头结点、首元结点。

首元结点是指链表中存储线性表中第一个数据元素a~1~的结点。为了操作方便,通常在链表的首元结点之前附设一个结点,称为头结点,其数据域中不存储线性表的数据元素,作用是为了对链表进行操作时,对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点(头结点或首元结点)的指针。若链表中附设头结点,则不管线性表是否为空表,头指针均不为空,否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点,是不同存储结构表示同一逻辑结构的问题。

2.2(1)
(1) 在顺序表中插入或删除一个元素,需要平均移动表中一半元素,具体移动的元素个数与表长和该元素所在位置有关。
(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。
(3) 在单链表中,除了首元结点外,任一结点的存储位置由其直接前驱结点的链域的值指示。
(4) 在单链表中设置头结点的作用是插入和删除首元素时不必进行特殊处理

2.3(2) 在什么情况下用顺序表比链表好?

当线性表的数据元素在物理位置上是连续存储的时候,其特点是可以随机存取。

2.9(2) 简述以下算法的功能。

(1) Status A(LinkedList L)  // L是无表头结点的单链表
{
    if (L && L->next)
    {
        Q = L, L = L->next, P = L;
        while (P->next)
            P = P->next;
        P->next = Q;
        Q->next = NULL;
    }
    return OK;
}   // A

若 L 的长度不小于 2,将 L 的首元结点变为尾元结点。

(2) void BB(LNode * s, LNode * q)
{
    p = s;
    while (p->next != q)
        p = p->next;
    p->next = s;
}   // BB
void AA(LNode * pa, LNode * pb) // pa 和 pb 分别指向单循环链表中的两个结点
{
    BB(pa, pb);
    BB(pb, pa);
}   // AA

将单循环链表拆成两个单循环链表。

二、算法设计题

涉及的顺序表和链表的类型定义如下:

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
    ElemType * elem;    // 存储空间基址
    int length; // 当前长度
    int listsize;   // 当前分配的存储容量
} SqLIst;   // 顺序表类型

typedef struct LNode {
    ElemType data;
    Struct LNode * next;
} LNode, * LinkList;    // 链表类型

2.10(2) 指出以下算法中的错误和低效之处,并将它改写为一个既正确又高效的算法。

Status DeleteK(SqList&a, int i, int k)
{

}

2.11(2) 设顺序表va中的数据元素递增有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。

Status InsertOrderList(SqList &va, ElemType x)
{
    // 在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法
    int i;
    if (va.length == va.listsize)   return OVERFLOW;
    for (i = va.length; i > 0, x < va.elem[i - 1]; i--)
        va.elem[i] = va.elem[i - 1];
    va.elem[i] = x;
    va.length++;
    return OK;
}

2.13(2) 试写一算法在带头结点的单链表结构上实现线性表操作 LOCATE(L, X)。

int LocateElem_L(LinkList &L, ElemType x)
{
    int i = 0;
    LinkList p = L;
    while (p && p->data != x)
    {
        p = p->next;
        i++;
    }
    if (p)  return i;
    else    return 0;
}

2.14(2) 试写一算法在带头结点的单链表结构上实现线性表操作 LENGTH(L)。

int ListLength_L(LinkList &L)
{
    int i = 0;
    LinkList p = L;
    if (p)  p = p->next;
    while (p)
    {
        p = p->next;
        i++;
    }
    return i;
}

2.15(2) 已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起,假设指针hc指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。

void MergeList_L(LinkList &ha, LinkList &hb, LinkList &hc)
{
    LinkList pa, pb;
    pa = ha, pb = hb;
    while (pa->next && pb->next)
    {
        pa = pa->next;
        pb = pb->next;
    }
    if (!pa->next)
    {
        hc = hb;
        while (pb->next)
            pb = pb->next;
        pb->next = ha->next;
    }
}

2.16(3) 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后,将它们插入到表lb中第j个元素之前。试问此算法是否正确?若有错,则请改正之。

Status DeleteAndInsertSub(LinkedList la, LinkedList lb, int i, int j, int len)
{
    if (i < 0 || j < 0 || len < 0)
        return INFEASIBLE;
    p = la, k = 1;
    while (k < i)
    {
        p = p->next;
        k++;
    }
    q = p;
    while (k <= len)
    {
        q = q->next;
        k++;
    }
    s = lb, k = 1;
    while (k < j)
    {
        s = s->next;
        k++;
    }
    s->next = p, q->next = s->next;
    return OK;
}   // DeleteAndInsertSub

解:

Status DeleteAndInsertSub(LinkList &la, LinkList &lb, int i, int j, int len)
{
    LinkList p, q, s, prev = NULL;
    int k = 1;
    if (i < 0 || j < 0 || len < 0)
        return INFEASIBLE;
    // 在la表中查找第i个结点
    p = la;
    while (p && k < i)
    {
        prev = p;
        p = p->next;
        k++;
    }
    if (!p)
        return INFEASIBLE;
    // 在la表中查找第i + len - 1个结点
    q = p, k = 1;
    while (q && k < len)
    {
        q = p->next;
        k++;
    }
    if (!q)
        return INFEASIBLE;
    // 完成删除,注意i = 1的情况要特殊处理
    if (!prev)
        la = q->next;
    else
        prev->next = q->next;
    // 将从la中删除的结点插入到lb中
    if (j = 1)
    {
        q->next = lb;
        lb = p;
    }
    else
    {
        s = lb, k = 1;
        while (s && k < j - 1)
        {
            s = s->next;
            k++;
        }
        if (!s)
            return INFEASIBLE;
        q->next = s->next;
        s->next = p; // 完成插入
    }
    return OK;
}

2.17(2) 试写一算法,在无头结点的动态单链表上实现线性表操作 INSERT(L, i, b), 并和在带头结点的动态单链表上实现相同操作的算法进行比较。

// 单链表定义
typedef struct LNode
{
    ElemType data;
    struct LNode * next;
} LNode, * LinkLIst;

// 实现函数
Status Insert(LinkList &L, int i, int b)    // 在无头结点链表 L 的第 i 个元素之前插入元素 b
{
    p = L, q = (LinkList *) malloc(sizeof(LNode));
    q.data = b;
    if (i == 1)
    {
        q.next = p, L = q;  // 插入在链表头部
    }
    else
    {
        while (--i > 1)  p = p->next;
        q->next = p->next;
        p->next = q; // 插入在第 i 个元素的位置
    }
}   // Insert

2.18(2) 试写一算法。实现线性表操作 DELETE(L, i)。

Status Delete(LinkList &L, int i)
{
    if (i == 1) L = L->next;
    else
    {
        p = L;
        while (--i > 1)
            p = p->next
        q = p;
        p->next = p->next->next;
        free(q->next)
    }
}

2.19(3) 已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值大于 mink 且小于 maxk 的元素,同时释放被删结点空间,并分析算法时间复杂度。

Status ListDelete_L(LinkList &L, ElemType mink, ElemType maxk)
{
    LinkList p, q, prev = NULL;
    if (mink > maxk)
        return ERROR;
    p = L, prev = p;
    p = p->next;
    while (p && p->data < maxk)
    {
        if (p->data <= mink)
        {
            prev = p;
            p = p->next;
        }
        else
        {
            prev->next = p->next;
            q = p;
            p = p->next;
            free(q);
        }
    }
    return OK;
}

2.20(2) 同上题条件,试写一高效算法,删除表中所有值相同的多余元素,同时释放被删结点空间,并分析算法时间复杂度。

void ListDelete_LSameNode(LinkList &L)
{
    LinkList p, q, prev;
    p = L, prev = p;
    p = p->next;
    while (p)
    {
        if (p->data == p->next->data)
        {
            prev->next = p->next;
            q = p;
            p = p->next;
            free(q);
        }
    }
}

2.21(3) 试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表 (a~1~, a~2~, ..., a~n~) 逆置为 (a~n~, a~n-1~, ..., a~1~)。

Status ListOppose_Sq(SqList &L)
{
    int i;
    ElemType x;
    for (i = 0; i < L.length / 2; i++)
    {
        x = L.elem[i];
        L.elem[i] = L.elem[L.length - i - 1];
        L.elem[L.length - i - 1] = x;
    }
    return OK;
}

2.22(3) 对单链表实现就地逆置。

Status ListOppose_L(LinkList &L)
{
    LinkList p, q;
    p = L;
    p = p->next;
}

留下评论

您的电子邮箱地址不会被公开。