AI 助理
备案控制台
开发者社区 云计算 文章 正文

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

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

单选题



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”的存储形式。本题要求你找出两个链表的公共后缀。



函数接口定义：


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的公共后缀的起点位置。


输入样例：


如图存储的链表



输出样例：


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;
}
文章标签：
存储
关键词：
数据结构链表
数据结构习题
数据结构双向链表
数据结构链表习题
链表习题
流楚丶格念
目录
相关文章
ephemerals__
|
24天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
50 4
肾透侧视攻城狮
|
25天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
22 2
肾透侧视攻城狮
|
25天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
30 2
肾透侧视攻城狮
|
25天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的；不然别给我家鸽鸽丢脸好嘛？】
顺序表的定义和基本操作之插入；删除；按值查找；按位查找习题精讲等具体详解步骤以及举例说明
肾透侧视攻城狮
21 1
java冯坚持
|
1月前
|
算法 Java
数据结构与算法学习五：双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现，并通过实例演示了双向链表的优势和应用。
java冯坚持
17 0
数据结构与算法学习五：双链表的增、删、改、查
ephemerals__
|
24天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
40 0
白子寰
|
1月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
白子寰
24 0
阿客不是客
|
1月前
|
存储
探索数据结构：便捷的双向链表
探索数据结构：便捷的双向链表
阿客不是客
18 0
阿客不是客
|
1月前
|
存储
探索数据结构：单链表的实践和应用
探索数据结构：单链表的实践和应用
阿客不是客
66 0
java冯坚持
|
1月前
|
算法 Java
数据结构与算法学习六：单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例，详细讲解了约瑟夫环问题的解决方案，并提供了Java代码实现。
java冯坚持
21 0