集美大学课程实验报告-实验2：线性表
| 项目名称 | 内容 |
|---|---|
| 课程名称 | 数据结构 |
| 班级 | 网安2512 |
| 指导教师 | 郑如滨 |
| 学生姓名 | 蔡华杰 |
| 学号 | 202521336054 |
| 实验项目名称 | 线性表的使用 |
| 上机实践日期 | 3月19日 |
| 上机实践时间 | 2学时 |
一、目的（本次实验所涉及并要求掌握的知识点）
- 掌握顺序表的基本操作：创建、删除区间元素、输出,释放
- 掌握单链表的基本操作：头插法建表、尾插法建表、链表逆置、输出
- 引用参数&进行链表操作
- 理解顺序表和链表的区别及各自的特点
- 掌握指针操作和动态内存管理
二、实验内容与设计思想
题目1：区间删除
函数相关伪代码
伪代码:
函数1: CreateList(L, n):输入: 顺序表指针 L(引用), 元素个数 n输出: 无(通过引用修改 L)为 L 分配新的 List 内存空间设置 L.length = n循环 i 从 0 到 n-1:读取输入值并存入 L.data[i]函数2 DelNode(L, min, max):输入: 顺序表指针 L(引用), 删除区间 [min, max]输出: 无(通过引用修改 L)如果 L 为空 或 L.length ≤ 0:返回初始化 newlength = 0循环 i 从 0 到 L.length-1:如果 L.data[i] < min 或 L.data[i] > max:// 该元素不在删除区间内，保留L.data[newlength] = L.data[i]newlength = newlength + 1// 更新顺序表长度L.length = newlength函数3 DispList(L):输入: 顺序表指针 L输出: 无(打印结果)如果 L 为空 或 L.length ≤ 0:打印 "线性表为空！"返回循环 i 从 0 到 L.length-1:如果 i > 0:打印一个空格打印 L.data[i]打印换行返回
函数代码
void CreateList(SqList &L,int n){L=new List;L->length = n;for(int i=0;i<n;i++){cin >>L->data[i];}
}void DelNode(SqList &L,int min,int max){if(L == NULL ||L->length <=0)return;//ElemType newlength=0;for (int i = 0; i <= L->length-1; i++){if(L->data[i]<min||L->data[i]>max){L->data[newlength++] = L->data[i]; }}L->length = newlength;
}void DispList(SqList L){if(L==NULL || L->length<=0){cout<<"线性表为空！"<<endl;return;}for(int i=0;i<L->length;i++){if(i>0){cout<<" ";}cout<<L->data[i];}cout<<endl;return;
}复杂度
| 函数 | 时间复杂度 | |
|---|---|---|
题目2：头插法或尾插法创建链表
函数相关伪代码
伪代码:
头插法:
函数1 CreateListF(L, n):输入: 链表头指针 L(引用), 元素个数 n输出: 无(通过引用修改 L)为 L 分配新的 LNode 内存空间L.next = NULL循环 i 从 1 到 n:为 newNode 分配新的 LNode 内存空间读取输入值存入 newNode.datanewNode.next = L.next L.next = newNode
函数2 DispList(L):输入: 链表头指针 L输出: 无(打印链表内容)如果 L 为空 或 L.next 为空:打印 "空链表!"返回p = L.nextisFirst = true当 p 不为空时:如果 isFirst 为假:打印一个空格打印 p.datap = p.nextisFirst = false尾插法:
函数 CreateListR(L, n):输入: 链表头指针 L(引用), 元素个数 n输出: 无(通过引用修改 L)为 L 分配新的 LNode 内存空间L.next = NULL如果 n < 0:返回r = L循环 i 从 1 到 n:为 newNode 分配新的 LNode 内存空间读取输入值存入 newNode.datanewNode.next = NULLr.next = newNode r = newNode
函数代码
头插法:
void CreateListF(LinkList &L,int n){L = new LNode;//头节点L,要分配内存,因为不知道头节点有无L->next = NULL;for(int i=0;i<n;i++){LinkList newLNode = new LNode;cin >> newLNode->data;newLNode ->next = L ->next;L->next = newLNode;}
}
void DispList(LinkList L){if(L==NULL||L->next==NULL){//记住链表带头节点时，L 永远不为NULL（除非没创建）cout<<"空链表!"<<endl;//上行注意顺序return;}LinkList p = L->next;// p指向第一个数据节点bool first = true; // 标记是否是第一个输出的元素while(p!=NULL){if(!first){cout<<" ";}cout<<p->data;p = p->next;first = false;}
}
尾插法:
void CreateListR(LinkList &L, int n){L = new LNode;L->next = NULL;//别忘记了要指向空if(n<0)return;LinkList r = L;//定义尾巴指针rearfor(int i=0; i<n;i++){LinkList newNode = new LNode;cin>>newNode->data;newNode->next = NULL;//别忘记r->next = newNode;//记住r = newNode;}
}
题目3：单链表的逆置
函数相关伪代码
函数 ReverseList(L):输入: 链表头指针 L(引用)输出: 无(通过引用修改 L)如果 L.next == NULL 或 L.next.next == NULL:返回pre = L.next cur = pre.next pre.next = NULL当 cur != NULL 时:temp = cur.next cur.next = pre pre = cur cur = temp L.next = pre
函数代码
void ReverseList(LinkList &L){if(L->next==NULL||L->next->next ==NULL)return;//忘记考虑呢空链表,即无数据,或只有一个数据LinkList cur,pre,temp;pre = L->next;cur = pre->next;pre->next = NULL;//别忘记了,将第一个节点变成尾节点while(cur!=NULL){temp = cur->next;cur->next = pre;pre = cur;//别打错打反了cur = temp;//}L->next = pre;
}
三、实验使用环境（本次实验所使用的平台和相关软件）
- 操作系统：Windows 11专业版
- 编程语言：C++
- 开发工具：Visual Studio 18.3.2
- 编译器：MSVC 14.40
四、实验步骤和调试过程（实验步骤、测试数据设计、测试结果分析）
题目1：区间删除
本机运行截图
![[Pasted image 20260322170853.png|1277]]
PTA提交截图
![[Pasted image 20260322171032.png]]
题目2：头插法或尾插法创建链表
头插法:
本机运行截图
![[Pasted image 20260322171617.png]]
PTA提交截图
![[Pasted image 20260322171217.png]]
尾插法:
本机运行截图
![[Pasted image 20260322172000.png]]
PTA提交截图
![[Pasted image 20260322171317.png]]
题目3：单链表的逆置
本机运行截图
![[Pasted image 20260322172251.png]]
PTA提交截图
![[Pasted image 20260322172325.png]]
五、实验小结（实验中遇到的问题及解决过程、实验体会和收获）
遇到的问题及解决方法：
- 问题: 在实现DelNode函数时,未成考虑链表为空
- 解决方法：增加对空链表的判断,当L == NULL或L->length <= 0时直接返回
- 问题：头插法过程忘记将L->next设置为NULL,导致链表尾节点指向随机地址
- 解决方法：在L = new LNode;后立即添加L->next = NULL;
- 问题：在ReverseList函数中，先移动cur再移动pre
- 解决方法：先保存cur的下一个节点(temp)，再反转cur的指针方向，然后依次移动pre和cur，确保遍历过程中不会丢失链表。
实验体会和收获：
- 掌握了指针操作的核心技巧:通过多次练习头插法、尾插法和链表逆置，对指针的指向、移动和修改有了更清晰的认识。特别是三个指针配合进行链表逆置的过程
- 养成了边界条件检查的习惯:在编写函数时，必须充分考虑各种边界情况：空表、只有一个元素、全部元素被删除、输入n为0等
- 学会了引用参数的使用:实验中使用LinkList &L这样的引用参数,使得在函数内部对链表的修改可以直接影响外部的链表，避免了返回指针的麻烦。
六、附件（参考文献和相关资料）
- 实验2-线性表