毓秀数据结构实验二:单链表
实验二 单链表实验
一、实验目的
1、掌握用Visual C++6.0上机调试单链表的基本方法
2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现
二、实现内容
1、单链表基本操作的实现
[问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。
[基本要求]用链式存储结构实现存储
[实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。
2、求表长以及有序单链表的合并算法的实现
[问题描述] 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。
[基本要求]用链式存储结构实现存储
报告内容为小组共同完成
一、实验目的
1、熟练掌握单链表的结构特点，掌握单链表的基本操作。
2、验证单链表存储及其基本操作的实现；
3、有序单链表的合并算法的实现
4、理解算法与程序的关系，灵活运用单链表算法。
二、实验内容
1、单链表的建立，建立 n 个元素的单链表；
2、对已建立的顺序表实现基本操作：包括初始化单链表、显示单链表、查找指定元素值的序号、获取单链表指定位置取值、删除元素、两个有序单链表的合并。
编写程序实现单链表的各种基本运算：
（1）初始化顺序表L；
（2）显示单链表
（3）查找
（4）取值
（5）插入元素
(6) 删除指定位置的元素
（6）删除指定值的元素
（7）求两个有序单链表的并归
三、代码实现
#include <iostream>
using namespace std;
#define ElemType int
typedef struct LNode {
ElemType data; //数据域
struct LNode* next; //指针域
}LNode, * LinkList;
void Insert(LinkList& L, int j, ElemType e) { //插入元素
LinkList p = L;
int i = 0;
//判断要插入的位置是否存在
LinkList p1 = L->next;
int length = 0;
while (p1) {
length++;
p1 = p1->next;
}
if (j > length) {
cout << "要插入的位置不存在!" << endl;
return;
}
while (p && i < j - 1) {
p = p->next;
++i;
}
LNode* s = new LNode(); //生成新节点
s->data = e; //将数据域置为e
s->next = p->next;
p->next = s;
cout << "插入成功!" << endl;
}
void CreateList(LinkList& L) { //初始化单链表
int n;
cout << "请输入单链表的长度：" << endl;
cin >> n;
L = new LNode;
L->next = NULL;
LinkList r = L;
cout << "请输入单链表的数据元素：" << endl;
for (int i = 0; i < n; i++) {
LinkList p = new LNode;
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
}
}
void Display(LinkList& L) { //输出单链表
cout << "该单链表为：" << endl;
LinkList p = L->next;
while (p) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
void FindElem(LinkList& L, int i) { //检索元素
LinkList p1 = L;
LinkList p2 = L;
int n = 0;
bool sign = false;
while (p1) {
if (i == p1->data) {
sign = true;
break;
}
p1 = p1->next;
}
if (sign) {
cout << "值为" << i << "的元素是表中的第";
while (p2) {
if (i == p2->data) {
cout << n;
}
p2 = p2->next;
n++;
}
cout << "个元素" << endl;
}
else {
cout << "单链表中不存在该元素!" << endl;
}
}
void GetElem(LinkList L, int i) { //定位元素
LinkList p = L->next;
int j = 1;
while (p && j < i) {
p = p->next;
j++;
}
if (!p || j > i) {
cout << "您输入的位置已超出单链表的长度!" << endl;
return;
}
cout << "该单链表第" << i << "个元素为 " << p->data << endl;
}
void Delete(LinkList& L, int x, int op = 1) { //删除指定位置的元素
LinkList p = L;
int i = 0;
while (p && i < x - 1) {
p = p->next;
++i;
}
if (!p->next || i > x - 1) {
cout << "删除位置不合理!" << endl;
}
LNode* r = new LNode();
r = p->next;
p->next = r->next;
delete r;
if (op == 1)
cout << "删除成功!" << endl;
}
void DeleteElem(LinkList& L, ElemType e) { //删除指定值的元素
LinkList p = L;
bool sign = false;
while (p) {
if (p->next->data == e) {
LNode* r = new LNode();
r = p->next;
p->next = r->next;
delete r;
sign = true;
}
p = p->next;
}
if (sign) {
cout << "删除成功!" << endl;
Display(L);
}
else {
cout << "要删除的元素不存在!" << endl;
return;
}
}
void ListDestroy(LinkList& L)
{
if (L == nullptr) return;
while (L->next)
Delete(L, 1, 2);//利用已有资源，每次都删除第一个元素
delete L;
cout << "原单链表已删除" << endl;
}
void Merger() { //两个有序单链表的归并
LinkList LA;
LinkList LB;
LinkList LC;
LNode* pa = new LNode();
LNode* pb = new LNode();
LNode* pc = new LNode();
cout << "请初始化单链表PA:" << endl;
CreateList(LA);
Display(LA);
cout << "请初始化单链表PB:" << endl;
CreateList(LB);
Display(LB);
pa = LA->next; //pa和pb的初值分别指向两个表的第一个节点
pb = LB->next;
LC = LA; //用LA的头结点作为LC的头结点
pc = LC; //pc的初值指向LC的头结点
while (pa && pb) { //当LA和LB均未达到表尾时，选取最小值插入LC后
if (pa->data <= pb->data) {
pc->next = pa;
pc = pa;
pa = pa->next;
}
else {
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb; //将非空表的剩余片段插入到PC之后
delete LB; //释放LB的头结点
if (LC->next)//这就怕熊孩子连输两个小于等于0的数导致表里一个元素都没有
{
pc = LC;//pc是当前处理到的位置
LNode* pcNext = pc->next;//pcNext是在pc的next改变后找到原链表中下一个节点
LNode* rec = pcNext; //记录首元节点，目的是在链表反向后删除原来的头节点
while (pcNext)
{
LNode* recordedNode = pc;//记录pc改动前的位置
pc = pcNext; //pc跳到pcNext的位置
pcNext = pcNext->next; //pcNext移动位置
pc->next = recordedNode; //改动pc->next
}
pcNext = new LNode;
pcNext->next = pc;
LC = pcNext;
delete rec->next;
rec->next = NULL;
}
cout << "这两个单链表归并完毕!" << endl;
Display(LC);
ListDestroy(LC);
}
void menu() {
cout << "1.创建单链表" << endl;
cout << "2.显示单链表" << endl;
cout << "3.查找" << endl;
cout << "4.取值" << endl;
cout << "5.插入元素" << endl;
cout << "6.删除指定位置的元素" << endl;
cout << "7.删除指定值的元素" << endl;
cout << "8.求两个有序单链表的并归" << endl;
cout << "0.结束程序" << endl;
cout << "请输入你要进行的操作：" << endl;
}
int main() {
LinkList L = nullptr;
int choice;
while (true) {
menu();
cin >> choice;
switch (choice) {
case 1: //创建单链表
ListDestroy(L);//多次执行1操作时先摧毁原来的表
L = nullptr;
CreateList(L);
Display(L);
system("pause");
system("cls");
cout << "请输入你要进行的操作：" << endl;
break;
case 2: //显示单链表
Display(L);
system("pause");
system("cls");
cout << "请输入你要进行的操作：" << endl;
break;
case 3: //查找数据元素
cout << "请输入要检索的元素：" << endl;
int n;
cin >> n;
FindElem(L, n);
system("pause");
system("cls");
cout << "请输入你要进行的操作：" << endl;
break;
case 4: //查看指定位置的元素
cout << "请输入要查看的元素位置：" << endl;
int i;
cin >> i;
GetElem(L, i);
system("pause");
system("cls");
cout << "请输入你要进行的操作：" << endl;
break;
case 5: //插入元素
cout << "请输入要插入的位置:" << endl;
int j;
cin >> j;
cout << "请输入要插入的元素:" << endl;
ElemType e;
cin >> e;
Insert(L, j, e);
Display(L);
system("pause");
system("cls");
cout << "请输入你要进行的操作：" << endl;
break;
case 6: //删除指定位置的元素
cout << "请输入要删除元素的位置:" << endl;
int x;
cin >> x;
Delete(L, x);
Display(L);
system("pause");
system("cls");
cout << "请输入你要进行的操作：" << endl;
break;
case 7: //删除指定值的元素
cout << "请输入要删除的元素:" << endl;
ElemType ee;
cin >> ee;
DeleteElem(L, ee);
system("pause");
system("cls");
cout << "请输入你要进行的操作：" << endl;
break;
case 8:
Merger();
system("pause");
system("cls");
cout << "请输入你要进行的操作：" << endl;
break;
case 0: //结束程序
ListDestroy(L);//最后再摧毁一次
cout << "程序运行结束!!!" << endl;
return 0;
default:
cout << "您选择的操作无效,请重新选择:" << endl;
break;
}
}
return 0;
}
四、实验难点
1、单链表结构定义
单链表存储特点是用任意的存储单元存储线性表的数据元素，其存储结点包含两部分，数据域和指针域。在定义单链表的存储结构时应包含这两部分。
2、初始化单链表
即构造一个长度为0的单链表L。要判断储存分配是否成功(L.elem)。
3、在单链表中插入元素
要判断插入的位置是否合法，即插入的位置要在1和表长加1之间；要判断顺序表的存储空间是否已满，如果已满。就为其增加分配容量。在元素插入位置及之后的元素要一次往后移动一个位置，并且从最后一个元素开始移动，利用for循环实现；在完成元素插入后，表长要加1。
4、在单链表中删除元素
实现和在顺序表中删除元素大同小异，需要注意的是元素从删除位置之后的一位开始依次前移，最后表长减1。
5、在单链表中查找元素
在单链表中查找值为e的数据元素，返回e的序号，需要从第一个元素起，依次和e相比较，查找成功返回序号i+1，失败返回0。
6、单链表合并
如LA和LB合并为LC分别初始化指向链表第一个结点的两个指针pa和pb，用LC的头结点取值为LA的头结点，pc的初值指向LC的头结点，当指针pa和pb均未到达相应表尾时，依次比较pa和pb所指向元素值，从LA或LB中选取较小值插入LC后；将非空表的剩余片段插入到pc之后，最后释放LB头结点。
这一步之后我们就得到了一个升序的单链表，而我们现在的任务就是将单链表反向（原来p->next为q，现在q->next是p）。我们想用线性的时间从头到尾一次完成这个反向过程，这样就有一个考虑。我们对当前节点处理时是会把当前节点的后继设为其在原表中的前驱（虽然不是双向链表但还是这么说），这么做的话我们会发现这个单链表中间有一个断层，并且随着我们依次往后处理，这个断层也会依次向后移动，断层移动到最后了，也就反向成功了，因此我们可以从这个断层上做文章。
这时我们就可以想到，为了连接“断层”两边，我们自然需要去分别记录“断层”两侧的地址。
然后我们再考虑移动时的细节，我们会发现断层移动时涉及到的是旧断层左端元素，新断层右端元素，以及新旧断层中间元素（也就是上图中右边的三个元素），只要把这三个地址记录下来就可以完美实现断层的移动。具体到实现就是使用pc记录原断层左边的元素的地址，用pcNext记录断层右边元素的地址。然后移动时我们先用recordedNode记录pc的地址，然后让pc跳到pcNext的位置，此时pcNext处在断层右边，直接通过next指针移动到下一个位置（断层左右都是连续的），这时只需要把pc的next指针指向pc原来所在的位置就完成了断层的移动，如下图。此时依然是pc在断层左边，pcNext在断层右边，所以这一步骤可重复进行。
最后是一些细节上的问题，首先就是，这种方法什么时候停止，其实停止的条件也很简单，因为我们是以断层的存在为基础去实现这个算法的，那么我们很自然的就可以想到，如果pcNext变成空了，这个断层就自然不存在了，所以while循环的终止条件就是pcNext == NULL。还要考虑一个起始值，由于我们反向后最末尾节点是原表的首元节点，还要考虑其后继，所以顺利成章地把头节点和首节点之间想象成有一个断层（反正头节点最后要被销毁，它的next指针也就是起赋初值的作用），然后就可以往下做了。鉴于我我们要一直执行算法直至断层右边节点为空也就是单链表末尾，我们自然可以把原单链表中头节点到最末尾节点中所有点全部反向。
这时，有细心观众就会发现，万一我给了两个空表，合并之后首元节点是空节点怎么办呢？这也就是为什么我要加上这最外层的这个if语句。
因为你总是需要把尾节点的后继设为空，那么你自然需要记录尾节点（原表的首元节点）的地址，但是如果我不加外层的if，那么我会因为首元节点为空，我还去删除它的后继，导致程序崩溃。并且，我们在上面已经论证过了，只要表中有元素就可以实现单链表反向，所以我们就只需要加入对空表的判断（也就是外层的if）即可。
五、程序运行
省略
六、实验心得
收获：在定义单链表存储结构时，对同一结构体指针类型起了两个名称，LinkList和LNode*，两者本质上是等价的，但提高了程序可读性。通常用LinkList定义单链表，强调定义的是单链表的头指针；用LNode*定义指向单链表中任意结点的指针变量。在单链表进行有序合并时，因为链表结点之间的关系是通过指针建立起来的，所以链表进行合并时不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程只需把两个表的结点重新进行链接。在写程序的过程中，线性表的链式结构的相关代码已经渐渐熟悉，基本算法思想学习得到进一步的复习与巩固。在后来的调试过程中，又因各种各样的错误和不断解决问题而丰富了个人编程的经历和经验和提高个人解决问题的能力。对于已经忘记的知识，在进行实验过程中查阅书籍，使得知识得到复习与巩固。
2.若有相关文章侵犯您的权益，请联系源儿删除，谢谢！
3.相关软件、资料仅供学习参考使用，在24h内务必删除！
腾龙梦屋 » 数据结构实验二:单链表
加速支持