/*
线性表---链式表示和实现
由于线性表--顺序实现时,线性表中元素是放在一群紧紧挨着的存储单元,
所以在进行元素的插入和删除时,需要移动大量的元素
为了解决上述问题,我们这里就提出了链式存储结构,它可以实现逻辑上相邻而物理结构上不相邻
的结构,这样我们就可以避免了顺序结构带来的问题,但是,同时也失去线性结构随机存取的优点
链式结构的原理:
线性表中的每个元素都有两个属性:数据域和指针域,
数据域是存放该元素的值的
指针域是存放该线性表中,该元素下一个元素的地址
*/
#include<iostream>
#include<cstdlib>
#include<windows.h>
using namespace std;
typedef int Elemtype;
//链式结构
struct Node
{
//结点的值
Elemtype value;
//下一个结点的地址
Node * next;
};
bool insert(Node * & head,int i, Elemtype value) {
//插入到前面的方法
int j = 0;
Node * L = head;
while ( L && j < i-1) {
L = L->next;
++j;
}
//如果插入不成功,则返回false
//不成功的标志是:!L表示已经到了线性表的末尾了,但是还没找到需要插入的那个位置
// j>i-1表示i负数或0的时候。
if (!L || j > i-1)return false;
Node * s = new Node();
s->value = value; //先对临时结点赋值
s->next = L->next; //让临时结点下一个位置指向当前需要插入前一个结点的下一个位置
L->next = s; //让前一个结点下一个位置指向临时结点,完成
return true;
}
bool del_by_index(Node * & head, int i) {
//s我们先找到需要删除那个结点的前一个结点
int j = 0;
Node * L = head;
while (L->next && j < i - 1) {
L = L->next;
++j;
}
//如果删除不成功,则返回false
//不成功的标志是:!L->next表示已经到了线性表的末尾了,但是还没找到需要删除的那个位置
// j>i-1表示i负数或0的时候。
if (!(L->next) || j > i - 1)return false;
L->next = L->next->next;
return true;
}
bool del_by_value(Node * & head,Elemtype value) {
//我们先找到我们需要删除的那个结点的位置,
//然后调用del_by_index函数
int flag = 0;
int j = 0;
Node *L = head;
//遍历整个线性表,删除所有相关结点
while (L->next)
{
L = L->next;
++j;
if (L->value==value) {
//调用依照下标删除结点的方式。
del_by_index(head, j);
//删除了一个,那么当前位置也会往前推一个
--j;
flag = 1;
}
}
if (flag == 0)return false;
return true;
}
int find_by_value(Node * & head, Elemtype value) {
//我们寻找某个值是否存在线性表中,我们采取的通过遍历整个
//线性表,如果找到了第一个,马上返回该位置,否则我们返回0
int j = 0;
Node * L = head;
while (L->next) {
L = L->next;
++j;
if (L->value == value) {
return j;
}
}
return 0;
}
bool getitem(Node * & head, int i,Elemtype & value) {
//我们要求程序返回特定位置上的值
//我们一样是从头结点开始寻找该位置
int j = 0;
Node * L = head;
while (L->next && j < i - 1) {
L = L->next;
++j;
}
if (!(L->next) || j > i - 1) { return false; }
value = L->next->value;
return true;
}
void print(Node * & head) {
//输出我们只需要传入头结点,然后循环判断当前结点下一个结点是否为空,
//这样就可以输出所有内容
Node * L = head;
while (L->next) {
L = L->next;
cout << L->value << " ";
}
cout << endl;
}
int main() {
//链表的头结点,不存放任何值,首先初始化头结点
Node * head;
head = new Node();
head->next = NULL;
while (1) {
int order = 0; //命令
int flag = 0; //标识数
int n = 0; //插入数据的个数
int i = 0;
bool j; //是否正确的获取数据
int order_del = 0; //删除方式
cout << "/******************************************************************************/";
cout << "当前所有数据为:";
print(head);
cout << "/******************************************************************************/";
cout << "/******************************************************************************/";
cout << "/* 1、插入数据 */";
cout << "/* 2、删除数据 */";
cout << "/* 3、查找数据 */";
cout << "/* 4、获取数据 */";
cout << "/* 5、退出程序 */";
cout << "/******************************************************************************/";
cout << "请输入命令" << endl;
cin >> order;
system("cls");
switch (order)
{
case 1:
cout << "/******************************************************************************/";
cout << "当前所有数据为:";
print(head);
cout << "/******************************************************************************/";
cout << "请输入需要插入的数据的个数:" << endl;
cin >> n;
cout << "请输入" << n << "个数,按回车结束输入" << endl;
for (i = 0; i<n; i++) {
Elemtype type;
cin >> type;
//通过插入方法,来初始化线性表
if (!insert(head, i + 1, type)) {
flag = 1; //出现了错误
cout << "插入第" << i + 1 << "个数据时,出现了错误" << endl;
}
}
if (flag == 0) {//所有数据添加成功
cout << "插入的" << n << "个数据为:" << endl;
print(head);
}
Sleep(2000);//让程序停留一下
break;
case 2:
cout << "/******************************************************************************/";
cout << "当前所有数据为:";
print(head);
cout << "/******************************************************************************/";
cout << "/* 1、删除特定位置上的数据 */";
cout << "/* 2、删除特定的所有数据 */";
cout << "/******************************************************************************/";
cout << "请输入命令" << endl;
cin >> order_del;
system("cls");
switch (order_del)
{
case 1:
cout << "/******************************************************************************/";
cout << "当前所有数据为:";
print(head);
cout << "/******************************************************************************/";
cout << "请输入需要删除数据的位置:" << endl;
int location;
cin >> location;
//删除一个数据,在第一个位置
if (!del_by_index(head, location)) {
cout << "删除第" << location << "个数据时,出现了错误" << endl;
}
else {
cout << "删除后的数据为:" << endl;
print(head);
}
break;
case 2:
cout << "/******************************************************************************/";
cout << "当前所有数据为:";
print(head);
cout << "/******************************************************************************/";
cout << "请输入需要删除数据的位置:" << endl;
Elemtype del_value;
cin >> del_value;
//删除一个数据,在第一个位置
if (!del_by_value(head, del_value)) {
cout << "删除" << del_value << "这个数据时,出现了错误" << endl;
}
else {
cout << "删除后的数据为:" << endl;
print(head);
}
break;
default:
break;
}
Sleep(2000);//让程序停留一下
break;
case 3:
cout << "/******************************************************************************/";
cout << "当前所有数据为:";
print(head);
cout << "/******************************************************************************/";
cout << "请输入需要查找的数据:" << endl;
Elemtype find_value;
cin >> find_value;
j = find_by_value(head, find_value);
if (j == 0) {
cout << "没有找到对应的值" << endl;
}
else {
cout << "你要找值存在,它在链表中的位置标号为:" << j << endl;
}
Sleep(2000);//让程序停留一下
break;
case 4:
cout << "/******************************************************************************/";
cout << "当前所有数据为:";
print(head);
cout << "/******************************************************************************/";
cout <