第17讲：综合应用2
实现Python风格列表

《计算机程序设计》

苏醒

计算机学院计算机研究所编译系统研究室

课前准备

  • 在WSL Ubuntu中建立一个专门的目录用于课上练习，如~/course
$ mkdir ~/course
  • 打开VSCode并连接到WSL，打开此目录并新建文件，如~/course/main.cpp
  • 编辑main.cpp，随堂编程练习的代码请直接在此文件中编辑
main.cpp
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
  // ============= begin =============

  // =============  end  =============
  return 0;
}

学习目标

任务

本次综合练习中，基于C++链表实现Python风格列表，支持以下操作

Python风格列表操作
操作 说明
int len(Node *list) 获取列表长度
void print(Node *list) 打印列表
Node *appendInt(Node *&list, int x) 在列表末尾添加整数结点
Node *appendStr(Node *&list, const char *s) 在列表末尾添加字符串结点
Node *get(Node *list, int index) 索引操作，支持负向索引
Node *slice(Node *list, int start, int end, int step) 切片操作

学习目标

综合运用结构体、联合体、枚举类型、链表、指针、函数等知识构建实用数据结构

实现Python风格列表

列表结点

  • 构造Python风格列表，首先需要定义相关数据结构类型
    • 以单向链表形式构造列表
    • 支持整数结点与字符串结点
列表结点定义
enum { INT, STR } type; // 结点类型

struct Node {





};
列表结点定义
enum Type { INT, STR }; // 结点类型

struct Node {
  Type type;
  union {
    int i;     // 整数值
    char *s;   // 字符串值
  } data;
  Node *next;  // 结点指针
};

列表长度

  • 定义len函数，获取列表长度
列表长度
int len(Node *list) {
  int n = 0;



  return n;
}
列表长度
int len(Node *list) {
  int n = 0;
  for (Node *p = list; p != nullptr; p = p->next) {
    n++;
  }
  return n;
}

考考你

列表长度函数可以通过一次遍历实现，可否应用相同的程序结构实现列表打印函数？

列表打印

  • 定义print函数，打印列表
列表打印
void print(Node *list) {
  for (Node *p = list; p != nullptr; p = p->next) {





  }
}
列表打印
void print(Node *list) {
  for (Node *p = list; p != nullptr; p = p->next) {
    if (p->type == INT) {
      cout << p->data.i << " ";
    } else {
      cout << p->data.s << " ";
    }
  }
}

一次遍历

  • 列表长度函数与列表打印函数均通过一次遍历实现
  • 二者具有相似的程序控制结构
列表长度
int len(Node *list) {
  int n = 0;
  for (Node *p = list; p != nullptr; p = p->next) {
    n++;
  }
  return n;
}
列表打印
void print(Node *list) {
  for (Node *p = list; p != nullptr; p = p->next) {
    if (p->type == INT) {
      cout << p->data.i << " ";
    } else {
      cout << p->data.s << " ";
    }
  }
}

追加结点

  • 定义appendInt与appendStr函数，向列表末尾追加结点
追加结点
void appendInt(Node *&list, int i) {
  Node *p = new Node;
  p->type = INT;
  p->data.i = i;
  p->next = nullptr;










  return p;
}
追加结点
void appendInt(Node *&list, int i) {
  Node *p = new Node;
  p->type = INT;
  p->data.i = i;
  p->next = nullptr;

  if (list == nullptr) {
    list = p;
  } else {
    Node *q = list;
    while (q->next != nullptr) {
      q = q->next;
    }
    q->next = p;
  }
  return p;
}
追加结点
void appendStr(Node *&list, const char *s) {
  Node *p = new Node;
  p->type = STR;
  // 拷贝字符串


  p->next = nullptr;
  if (list == nullptr) {
    list = p;
  } else {
    Node *q = list;
    while (q->next != nullptr) {
      q = q->next;
    }
    q->next = p;
  }
}
追加结点
void appendStr(Node *&list, const char *s) {
  Node *p = new Node;
  p->type = STR;
  // 拷贝字符串
  p->data.s = new char[strlen(s) + 1];
  strcpy(p->data.s, s);
  p->next = nullptr;
  if (list == nullptr) {
    list = p;
  } else {
    Node *q = list;
    while (q->next != nullptr) {
      q = q->next;
    }
    q->next = p;
  }
}

索引结点

  • 定义get函数，根据索引值返回结点指针
    • 支持负向索引
    • 索引值越界时返回nullptr

考考你

应该如何支持负向索引？提示：考虑正向索引与负向索引的有效取值范围

  • 正向索引与负向索引的取值范围分别为\(i \in [0, n)\)与\(j \in [-n, 0)\)，其中\(n\)为列表长度
  • 负向索引可以通过正则化转换为正向索引

\[i \leftarrow j + n\]

索引节点

索引结点
Node *get(Node *list, int index) {
  int n = len(list);
  // 索引正则化


  // 索引越界判定


  // 搜索指定索引结点



  return p;
}
索引结点
Node *get(Node *list, int index) {
  int n = len(list);
  // 索引正则化
  if (index < 0)
    index += n;
  // 索引越界判定
  if (index < 0 || index >= n)
    return nullptr;
  // 搜索指定索引结点
  Node *p = list;
  for (int i = 0; i < index; i++)
    p = p->next;
  return p;
}

列表切片

  • 定义slice函数，根据切片参数返回子链表
    • 支持负向索引
    • 索引值越界时返回空链表

考考你

切片参数start、end、step分别表示起始索引、结束索引与步长，都有哪些情况应判定为无效切片？

  • 无效切片判定
    • step == 0
    • step > 0但start >= end
    • step < 0但start <= end
    • start与end其中任意一个越界

列表切片

  • 定义slice函数，根据切片参数返回子链表
    • 支持负向索引
    • 索引值越界时返回空链表

考考你

如何从一个有效索引创建新的列表？

  • 分别考虑正向切片与负向切片，二者构造循环的方向相反
    • 正向切片
    for (int i = start; i < end; i += step) {}
    • 负向切片
    for (int i = start; i > end; i += step) {}

列表切片

列表切片
Node *slice(Node *list, int start, int end, int step) {
  // 索引正则化



  // 无效切片判定



  // 创建新链表
  Node *slice = nullptr;













  return slice;
}
列表切片
Node *slice(Node *list, int start, int end, int step) {
  // 索引正则化
  int n = len(list);
  if (start < 0) start += n;
  if (end < 0) end += n;
  // 无效切片判定
  if (step == 0 || (step > 0 && start >= end) || (step < 0 && start <= end) ||
      (start < 0 || start >= n) || (end < 0 || end >= n))
    return nullptr;
  // 创建新链表
  Node *slice = nullptr;
  if (step > 0) {
    for (int i = start; i < end; i += step) {
      Node *p = get(list, i);
      Node *q = new Node; *q = *p; q->next = nullptr;
      append(slice, q);
    }
  } else {
    for (int i = start; i > end; i += step) {
      Node *p = get(list, i);
      Node *q = new Node; *q = *p; q->next = nullptr;
      append(slice, q);
    }
  }
  return slice;
}

总结

本节内容

---
config:
  look: handDrawn
  themeVariables:
    fontSize: 20px
---
mindmap
Python风格列表
  列表结点定义
  列表长度
  列表打印
  追加节点
  索引节点
  列表切片

学习目标

综合运用结构体、联合体、枚举类型、链表、指针、函数等知识构建实用数据结构

课后作业

  • 实训
    • 实现Python风格列表（截止时间2025.05.5）
  • 预习
    • 教材9.4–9.5节 文件IO

计算机程序设计