一、观看PPT教程
【01】单链表
二、练习题（不清楚回头查看有关PPT）
【01】下面是“线性数据结构”的描述，如果有错误请改正：线性数据结构是最常用的数据结构，元素之间存在着“一对一”的线性关系。从存储方式可分为顺序存储结构和链式存储结构，简称为顺序表和链表；其中顺序存储结构中用一组地址连续的存储单元依次存储元素，它的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中的任一元素；链式存储结构中元素随机存储，每个元素都有指针用于指向自己的直接前导元素，常见的单向链表、双向链表、循环链表采用链式存储。【02】下面是有关“单链表的定义”的描述，如果有错误请改正：链表是一种非常重要的数据结构，它可以动态地分配内存空间，实现高效的数据操作。单链表由一系列的节点构成，每个节点包含了数据和一个指向上一个节点的指针。头指针head指向头节点。
头节点（可省略）的指针域指向第一个节点。
尾节点的指针域指向NULL，即不储存任何节点信息。
【03】下面是有关“头节点和头指针”的描述，如果有错误请改正：头指针——1．头指针是链表的必要元素；2．无论链表是否为空，头指针均不为空；3．头指针是指向链表第一个节点的指针，若链表有头节点，则是指向头节点的指针。头节点——1．头节点也是链表的必须要素；2．头节点是为了操作的统一和方便而设立的，放在第一个节点之前，其数据域一般不存储数据，但也可以用来存放链表的长度；3．有了头节点，对第一节点执行删除、插入等操作时，不用实时更新头指针的指向，对第一节点的操作也能和其他节点的操作统一。【04】下面是使用双静态数组模拟单链表（有头节点）的代码，请补全缺失的注释：
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
#include<iostream>using namespace std;const int max_size = 1001; //int head; //int val[max_size]; //int nxt[max_size]; //int idx; //int size; ////初始化void init(){ head = 0; // nxt[0] = -1; // idx = 1; // size = 0; //} //空链表：当链表中仅有头指针和头节点或仅有头指针时，此时链表为空 。//查找节点int find(int pos) //传入pos { if(pos > size || pos < 0) // { cout << "查找位置不存在" << endl; return -1; } else // { int fd = head; for(int i = 1; i <= pos; i++) // { fd = nxt[fd]; } return fd; // }}/**单链表的插入1. 头插法2. 中间插入法3. 尾插法**///头插法：将新节点插入到头部void push_front(int x) //待插入的值x{ if(idx > max_size - 1) // cout << "储存位置已超过范围" << endl; else // { val[idx] = x; // nxt[idx] = nxt[head]; // nxt[head] = idx; // idx++; // size++; //单链表长度增加1 } }//中间插入法：将新节点插入知道位置前。void insert(int pos, int x) //pos插入位置 { if(pos > size || pos <= 0) // cout << "插入位置不存在" << endl; else if(idx > max_size - 1) cout << "储存位置已超过范围" << endl; else { int temp = find(pos - 1); // val[idx] = x; // nxt[idx] = nxt[temp]; // nxt[temp] = idx; // idx++; // size++; //单链表长度增加1 } }//尾插法：将新节点插入末尾void push_back(int x) //传入待插入的值x { if(idx > max_size -1) // cout << "储存位置已超过范围" << endl; else { int temp = head; while(nxt[temp] != -1) // temp = nxt[temp]; val[idx] = x; // nxt[temp] = idx; // nxt[idx] = -1; // idx++; // size++; //单链表长度增加1 }}/**单链表的删除删除节点，前节点直接指向后节点。1. 删除第一个节点2. 删除最后一个节点3. 删除中间的某个节点。注：数组模拟的链表很难物理移除数据，故模拟代码中不含数据移除算法，模拟删除过程不是实际的删除过程，节点删除后就成了垃圾。**///删除第一个节点void pop_front(){ if(size == 0) //链表为空，什么也不用做 cout << "链表为空" << endl; else //链表不为空 { int temp = nxt[head]; //第一个节点 nxt[head] = nxt[temp]; // size--; //链表长度减1 }}//删除最后一个节点void pop_back(){ if(size == 0) //链表为空，什么也不用做 cout << "链表为空" << endl; else //链表不为空 { int temp = head; //从头指针开始查找 // while(nxt[nxt[temp]] != -1) //nxt[nxt[temp]]是temp的后继节点的后继节点 temp = nxt[temp]; nxt[temp] = -1; // size--; //链表长度减1 } }//删除中间节点void erase(int pos) //传入删除位置 { if(pos > size || pos <= 0) // cout << "删除位置不存在" << endl; else { int temp = find(pos - 1); // nxt[temp] = nxt[nxt[temp]]; // size--; //链表长度减1 }}/**单链表的修改 **/void modify(int pos, int x) //传入位置pos和新值x{ if(pos > size || pos <= 0) // cout << "修改位置不存在" << endl; else val[find(pos)] = x; // } /**单链表的遍历**/void print_list(){ int temp = nxt[head]; // while(temp != -1) // { cout << val[temp] << " "; // temp = nxt[temp]; } cout << endl;}/**单向链表测试**/ int main(){ //初始化 init(); int tvs[] = {1,20,300,4000,50000,600000}; //push_front测试 for(int i = 0; i < 6; i++) push_front(tvs[i]); //print_list测试 print_list(); //push_back测试 push_back(0); print_list(); //insert测试 insert(4, 250); print_list(); //find测试 int temp = find(4); cout << "第4个节点的位置是" << temp << "，值是" << val[temp] << "。" << endl; //modify测试 modify(4, 350); print_list(); //erase测试 erase(4); print_list(); //pop_back测试 pop_back(); print_list(); //pop_front测试 pop_front(); print_list(); return 0;}
【05】单向循环链表和单链表不同的是：尾节点会指向头节点，形成单向循环结构。把上面的程序修改为适用于单向循环链表的代码。【06】下面是单链表与顺序表优缺点分析，如果有错误请改正：单链表优点——1．动态大小：链表可以根据需要动态分配内存空间，可以在运行时灵活地添加或删除节点，而不需要事先知道存储的元素数量；2．插入和删除操作高效：在链表中插入和删除元素只需要更改相邻节点的指针，时间复杂度为O(1)。这使得链表适用于频繁进行插入和删除操作的场景；3．内存利用率高：链表使用指针来连接节点，不像顺序表存储一样需要连续的内存空间。这意味着链表可以更好地利用内存碎片，减少内存的浪费。单链表缺点——1．随机访问低效：由于链表中的节点并不是连续存储的，无法通过索引直接访问元素，而是需要从头节点（或第一个节点）开始遍历。因此，访问特定位置的元素的时间复杂度为O(n)，效率较低。2．额外的空间开销：为了维护节点之间的联系，每个节点都需要额外的指针空间来存储下一个节点的地址，这样会增加存储空间的消耗。顺序表优点——1．随机访问高效：顺序表中的元素在内存中是连续存储的，可以通过索引直接访问元素，时间复杂度为O(1)，效率较高；2．内存占用较小：相比于链表，顺序表不需要额外的指针来维护节点之间的联系，因此存储的数据本身占用的空间更小。顺序表缺点——1．固定大小：顺序表的大小通常在创建时确定，并且无法动态扩展或收缩。当需要添加或删除元素时，可能需要重新分配内存并将现有元素复制到新的位置，效率较低；2．插入和删除操作低效：对于中间位置的插入和删除操作，需要将后续元素进行移动以填补空缺或释放空间，时间复杂度为O(n)。因此，选择链表结构还是顺序表结构取决于实际需求。如果需要频繁进行插入和删除操作，并且不关心随机访问的效率，那么顺序表结构是一个更好的选择。如果需要频繁访问特定位置的元素，而插入和删除操作较少，那么链表可能更适合。【07】编程题：二进制
