线性表-链式表示和实现

/* 线性表---链式表示和实现 由于线性表--顺序实现时，线性表中元素是放在一群紧紧挨着的存储单元， 所以在进行元素的插入和删除时，需要移动大量的元素 为了解决上述问题，我们这里就提出了链式存储结构，它可以实现逻辑上相邻而物理结构上不相邻 的结构，这样我们就可以避免了顺序结构带来的问题，但是，同时也失去线性结构随机存取的优点 链式结构的原理： 线性表中的每个元素都有两个属性：数据域和指针域， 数据域是存放该元素的值的 指针域是存放该线性表中，该元素下一个元素的地址 */ #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 <