开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

数据结构——双向链表PTA习题

简介: 数据结构——双向链表PTA习题
+关注继续查看

单选题



image


image.png


函数题


6-1 链式表操作集 (20分)


本题要求实现链式表的操作集。


函数接口定义:


Position Find( List L, ElementType X );
List Insert( List L, ElementType X, Position P );


List Delete( List L, Position P );


其中List结构定义如下:



typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;


各个操作函数的定义为:


Position Find( List L, ElementType X ):返回线性表中首次出现X的位置。若找不到则返回ERROR;


List Insert( List L, ElementType X, Position P ):将X插入在位置P指向的结点之前,返回链表的表头。如果参数P指向非法位置,则打印“Wrong Position for Insertion”,返回ERROR;


List Delete( List L, Position P ):将位置P的元素删除并返回链表的表头。若参数P指向非法位置,则打印“Wrong Position for Deletion”并返回ERROR。


输入样例:


6
12 2 4 87 10 2
4
2 12 87 5


输出样例:


2 is found and deleted.
12 is found and deleted.
87 is found and deleted.
Finding Error: 5 is not in.
5 is inserted as the last element.
Wrong Position for Insertion
Wrong Position for Deletion
10 4 2 5 


代码


#include <stdio.h>
#include <stdlib.h>

#define ERROR NULL
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

Position Find( List L, ElementType X );
List Insert( List L, ElementType X, Position P );
List Delete( List L, Position P );

int main()
{
    List L;
    ElementType X;
    Position P, tmp;
    int N;

    L = NULL;
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        L = Insert(L, X, L);
        if ( L==ERROR ) printf("Wrong Answer\n");
    }
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        P = Find(L, X);
        if ( P == ERROR )
            printf("Finding Error: %d is not in.\n", X);
        else {
            L = Delete(L, P);
            printf("%d is found and deleted.\n", X);
            if ( L==ERROR )
                printf("Wrong Answer or Empty List.\n");
        }
    }
    L = Insert(L, X, NULL);
    if ( L==ERROR ) printf("Wrong Answer\n");
    else
        printf("%d is inserted as the last element.\n", X);
    P = (Position)malloc(sizeof(struct LNode));
    tmp = Insert(L, X, P);
    if ( tmp!=ERROR ) printf("Wrong Answer\n");
    tmp = Delete(L, P);
    if ( tmp!=ERROR ) printf("Wrong Answer\n");
    for ( P=L; P; P = P->Next ) printf("%d ", P->Data);
    return 0;
}

/* 你的代码将被嵌在这里 */

List Insert(List L, ElementType X, Position P)
{
    List head = L;
    List p = (List)malloc(sizeof(List) );
    p->Next = NULL;
    p->Data = X;
    // 判断插入的是不是空链表
    if (P==L)
    {
        p->Next = L;
        return p;
    }
    // 循环遍历链表
    while (L)
    {
        // 插入条件的筛选
        if (P==L->Next)
        {
            p->Next = L->Next;
            L->Next = p;
            return head;
        }   
        L = L->Next;
    }

    printf("Wrong Position for Insertion\n");
    return ERROR;

}

Position Find(List L, ElementType X)
{
    while (L) 
    {
        if (L->Data == X) 
        {
            return L;
        }
        L = L->Next;
    }
    return ERROR;
}

List Delete(List L, Position P)
{
    //如果是头结点
    if (L == P)
    {
        L =L->Next;
        return L;
    }
    List head = L;
    // 循环遍历链表
    while (L)
    {
        if (L->Next == P) 
        {
            L->Next = P->Next;
            return head;
        }
        L = L->Next;
    }
    printf("Wrong Position for Deletion\n");
    return ERROR;
}


6-2 带头结点的链式表操作集 (20分)


本题要求实现带头结点的链式表操作集。


函数接口定义:


List MakeEmpty(); 
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );


其中List结构定义如下:


typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;


各个操作函数的定义为:


List MakeEmpty():创建并返回一个空的线性表;


Position Find( List L, ElementType X ):返回线性表中X的位置。若找不到则返回ERROR;


bool Insert( List L, ElementType X, Position P ):将X插入在位置P指向的结点之前,返回true。如果参数P指向非法位置,则打印“Wrong Position for Insertion”,返回false;


bool Delete( List L, Position P ):将位置P的元素删除并返回true。若参数P指向非法位置,则打印“Wrong Position for Deletion”并返回false。


输入样例:


6
12 2 4 87 10 2
4
2 12 87 5


输出样例:


2 is found and deleted.
12 is found and deleted.
87 is found and deleted.
Finding Error: 5 is not in.
5 is inserted as the last element.
Wrong Position for Insertion
Wrong Position for Deletion
10 4 2 5 


代码


#include <stdio.h>
#include <stdlib.h>

#define ERROR NULL
typedef enum {false, true} bool;
typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

List MakeEmpty(); 
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );

int main()
{
    List L;
    ElementType X;
    Position P;
    int N;
    bool flag;

    L = MakeEmpty();
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        flag = Insert(L, X, L->Next);
        if ( flag==false ) printf("Wrong Answer\n");
    }
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        P = Find(L, X);
        if ( P == ERROR )
            printf("Finding Error: %d is not in.\n", X);
        else {
            flag = Delete(L, P);
            printf("%d is found and deleted.\n", X);
            if ( flag==false )
                printf("Wrong Answer.\n");
        }
    }
    flag = Insert(L, X, NULL);
    if ( flag==false ) printf("Wrong Answer\n");
    else
        printf("%d is inserted as the last element.\n", X);
    P = (Position)malloc(sizeof(struct LNode));
    flag = Insert(L, X, P);
    if ( flag==true ) printf("Wrong Answer\n");
    flag = Delete(L, P);
    if ( flag==true ) printf("Wrong Answer\n");
    for ( P=L->Next; P; P = P->Next ) printf("%d ", P->Data);
    return 0;
}
/* 你的代码将被嵌在这里 */
/* 你的代码将被嵌在这里 */
List MakeEmpty()
{
    List L = (List)malloc(sizeof(List));
    L->Next = NULL;
    return L;
}
Position Find(List L, ElementType X)
{
    L = L->Next;
    while (L != NULL) {
        if (L->Data == X) {
            return L;
        }
        L = L->Next;
    }

    return ERROR;
}
bool Insert(List L, ElementType X, Position P)
{
    // 这个传入的是头结点的下一个,所以不用检验是否为头结点
    List q = (List)malloc(sizeof(struct LNode));
    q->Data = X;
    q->Next = P;
    while (L != NULL) {
        if (L->Next == P) {
            L->Next = q;
            return true;
        }
        L = L->Next;
    }
    printf("Wrong Position for Insertion\n");
    return false;

}
bool Delete(List L, Position P)
{
    while (L != NULL) {
        if (L->Next == P) {
            L->Next = P->Next;
            return true;
        }
        L = L->Next;
    }
    printf("Wrong Position for Deletion\n");
    return false;

}


6-4 共享后缀的链表(25分)


有一种存储英文单词的方法,是把单词的所有字母串在一个单链表上。为了节省一点空间,如果有两个单词有同样的后缀,就让它们共享这个后缀。下图给出了单词“loading”和“being”的存储形式。本题要求你找出两个链表的公共后缀。


image


函数接口定义:


PtrToNode Suffix( List L1, List L2 );


其中List结构定义如下:


typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */


L1和L2都是给定的带头结点的单链表。函数Suffix应返回L1和L2的公共后缀的起点位置。


输入样例:


如图存储的链表


image


输出样例:


ing


代码


#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

void ReadInput( List L1, List L2 ); /* 裁判实现,细节不表 */
void PrintSublist( PtrToNode StartP ); /* 裁判实现,细节不表 */
PtrToNode Suffix( List L1, List L2 );

int main()
{
    List L1, L2;
    PtrToNode P;

    L1 = (List)malloc(sizeof(struct Node));
    L2 = (List)malloc(sizeof(struct Node));
    L1->Next = L2->Next = NULL;
    ReadInput( L1, L2 );
    P = Suffix( L1, L2 );
    PrintSublist( P );

    return 0;
}
/* 你的代码将被嵌在这里 */
PtrToNode Suffix(List L1, List L2)
{
    int num1 = 0, num2 = 0;
    List t = L1->Next, a = L1->Next, b = L2->Next;
    // 先算出两条链表的长度
    while (t) {
        num1++;
        t = t->Next;
    }
    t = L2->Next;
    while (t) {
        num2++;
        t = t->Next;
    }
    while (num1 > num2) {
        num1--;
        a = a->Next;
    }
    while (num2 > num1) {
        num2--;
        b = b->Next;
    }
    while (a) {
        // 如果一样a后面的都是  返回a就行
        if (a == b)
            return a;
        a = a->Next;
        b = b->Next;
    }
    return NULL;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【Java数据结构】通过Java理解和实现——无头双向链表
【Java数据结构】通过Java理解和实现——无头双向链表
26 0
【数据结构】链表最强结构-带头双向循环链表(超详解)
本章将带你们走进带头双向循环链表的实现与讲解
25 0
Java数据结构与算法——双向链表
Java数据结构与算法——双向链表
23 0
Java数据结构与算法(五)-双向链表
什么是双向链表 每个结点除了保存了xui下一个结点的引用,同时还保存这对前一个节点的引用。 从头部进行哈如 要对链表进行判断,如果为空则这是尾结点为信添加的结点。
710 0
数据结构与算法(三) 线性表之双向链表
 掌握了单链表的结构和实现方法后,再来看双向链表,其实就是在每个节点上添加一个指向其前驱节点的指针,这样就可以实现链表的双向遍历,提高了访问效率。  下面是几个方法的实现: 首先依旧是节点的结构 template struct Node{ ...
818 0
《恋上数据结构第1季》单向链表、双向链表
《恋上数据结构第1季》单向链表、双向链表
8 0
数据结构——堆PTA习题
数据结构——堆PTA习题
10 0
数据结构---树(待补充)
数据结构-树的总结
1173 0
与“十“俱进 阿里数据库运维10年演进之路
阿里巴巴集团拥有超大的数据库实例规模,在快速发展的过程中我们在运维管理方面也在不断的面临变化,从物理器到容器、从独占到混布、从本地盘到存储计算分离、从集团内到大促云资源,从开源的MySQL到自研分布式数据库,运维管控进行了自我革新与进化
2875 0
【数据结构与算法】—— * 双向链表 *
【数据结构与算法】—— * 双向链表 *
29 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载