线性表-链式表示和实现

  • l4_649149
    了解作者
  • 11MB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-05-20 05:52
    上传日期
本文档是有关使用c++,完成对线性表的链式存储实现的代码,包括了链表的插入、删除、查找、返回值等
线性表---链式表示和实现.zip
内容介绍
/* 线性表---链式表示和实现 由于线性表--顺序实现时,线性表中元素是放在一群紧紧挨着的存储单元, 所以在进行元素的插入和删除时,需要移动大量的元素 为了解决上述问题,我们这里就提出了链式存储结构,它可以实现逻辑上相邻而物理结构上不相邻 的结构,这样我们就可以避免了顺序结构带来的问题,但是,同时也失去线性结构随机存取的优点 链式结构的原理: 线性表中的每个元素都有两个属性:数据域和指针域, 数据域是存放该元素的值的 指针域是存放该线性表中,该元素下一个元素的地址 */ #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 <
评论
    相关推荐