GDPU 数据结构 天码行空3

GDPU 数据结构 天码行空3

一、【实验目的】

1、掌握建立单链表的基本方法。
2、掌握单链表的插入、删除算法的思想和实现

二、【实验内容】

仿照教材中的单链表实现例子，自己设计一个有序单链表，单链表中的数据元素为整型并递增有序。有序单链表的定义:
逻辑结构:有序线性表，数据元素递增有序
存储结构:链式
操作集合:初始化、插入、删除、撤销
(1)ListInitiate(L) 初始化线性表，生成一个空表L。
(2)ListInsert(L,x) 在有序表L中插入数据元素x,使得新表仍然有序。
(3)ListDelete(L,x) 删除有序表L中的数据元素x，若删除成功则返回1，不成功则返回0。
(4)Destroy(L) 撤销单链表
要求:
1.有序单链表的操作集合有如下操作:初始化、插入、删除、撤销，使用头文件单链表的代码。
2.编写主函数main()验证所设计的有序单链表是否能正确插入、删除。
提示:
1.插入操作时，从链表的第一个数据元素结点开始，逐个比较每个结点的data域值和x的值，当data小于等于x时，进行下一个结点的比较；否则就找到了插入结点的合适位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾。
2.删除操作时，从链表的第一个数据元素结点开始，逐个比较每个结点的data域值和x的值，当data不等于x时，进行下一个结点的比较；否则就找到了要删除的结点，删除结点后释放结点。如果到了表尾还没有找到值为x的结点，则链表中没有要删除的元素。

3. 实验源码

🍺 head.h

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct node
{int data;node* next;
}SingleLinkedList;void init(node* l)
{l->data = 0;//头结点的 data 可以记录链表的元素个数l->next = nullptr;
}//初始化建立头节点void insertOne(node *l,int x)
{node* h = l;//head 前驱节点node* t = l->next;//tail 后继结点node* n = new node;n -> data = x;
//	cout << "debug" <<endl;while(t != nullptr)//找到第一个比 x 大的元素{if(t->data > x){h->next = n;n->next = t;break;}h = t;t = t->next;}if(t == nullptr)//处理x插入链表尾部的情况{n -> next = nullptr;h ->next = n;}l->data++;cout<< "插入成功！"<<endl;
}void insertArray(node* l,int* sz,int len)
{sort(sz, sz + len);l->data = len;node* tmp = l;for (int i = 0; i < len; i++){node* s = new node;s->data = sz[i];s->next = nullptr;tmp->next = s;tmp = s;}//直接按顺序插入
}int del(node* l,int x)
{node* h = l;node* t = l -> next;int flag = 0;while (t != nullptr){if (t->data == x){h->next = t->next;node* tmp = t;free(tmp);//清除占的内存t = h->next;flag = 1;l->data--;}else{//h不满足条件就一起动h = t;t = t->next;}}string res = flag==0?"元素不存在，删除失败":"删除元素成功";cout << res << endl;return flag;
}void print(node* l)
{cout <<"当前链表长度为" << l -> data <<",数据为 ";node* tmp = l->next;if(tmp == nullptr)cout << "空";while (tmp != nullptr){cout << tmp->data << " ";tmp = tmp->next;}cout << endl << endl;
}
void destroy(node* l)
{node* tmp = l->next;//遍历清除while (tmp != nullptr){node* t = tmp;tmp=tmp->next;free(t);l->data--;}cout << "链表自动销毁......" << endl;cout << "链表销毁成功!" << endl;
}

🍺 exp3.cpp

#include "head.h"
using namespace std;int main(void)
{node* head = new node;init(head);//初始化cout << "请输入单链表元素个数：" << endl;int x = 0;cin >> x;cout << "请输入" << x << "个元素" << endl;int sz[1000];for (int i = 0; i < x; i++) cin >> sz[i];//填入数据insertArray(head, sz,x);print(head);cout << "请输入需要增加的元素" << endl;cin >> x;insertOne(head,x);print(head);cout << "请输入想要删除的元素" << endl;cin >> x;del(head, x);//删除print(head);destroy(head);//销毁,但不删头节点
}

仅供参考