概念介绍
链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表(单链表),单链表是链式存取的结构。
链接存储方法
链接方式存储的线性表简称为链表(Linked List)。
链表的具体存储表示为:
① 用一组任意的存储单元来存放线性表的结点(这组存储单元既可以是连续的,也可以是不连续的)
② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还必须存储指示其后继结点的地址(或位置)信息(称为指针(pointer)或链(link))
链式存储是最常用的存储方式之一,它不仅可用来表示线性表,而且可用来表示各种非线性的数据结构。
List 头部文件 //List.h class LNode { public: int data; //数据域 LNode * next; //指针域 }; class List { public: List(); ~List(); void CreateList(); void Insert(int data, int index, bool flag = true); void Delete(int index); void printList(); void getData(int index); void exchange(int index1, int index2); int getLength(); private: LNode *head;//头结点 }; List 实现部分 及 main函数 //List.cpp #include<iostream> #include"List.h" using namespace std; List::List() { head = new LNode; head->next = NULL; cout << "创建对象成功!" << endl; } List::~List() { LNode *p = head, *s; while (p->next != NULL){ s = p->next; p = s->next; delete s; } delete p; delete head; } int List::getLength() { int len = 0; LNode *p = head; while (p->next!=NULL) { len++; p = p->next; } return len; } void List::CreateList() { int data_num,data; cout << "开始创建链表(尾插),请输入数据个数: "; cin >> data_num; for (int i = 0; i < data_num;i++) { cout << "请输入第" << i + 1 << "个数据: "; cin >> data; Insert(data, getLength() + 2, false);//这里我就没有用正儿八经的尾插,因为已经有Insert函数了 } cout << "CreateList: 创建完成" << endl; } //把元素data,插入第index个位置 void List::Insert(int data, int index,bool flag) { LNode *p = head, *s; if (index<=0) { cout << "插入失败,请输入大于0的数!" << endl; return; } if (getLength() + 1 < index) { while (p->next != NULL) { p = p->next; } s = (LNode *)new LNode[1]; s->data = data; s->next = NULL; p->next = s; if (flag != false) { cout << "Insert: 链表长度为" << getLength()-1 << ",无法插入到第" << index << "个位置;"; cout << "现将数据" << data << "插入链表尾部!" << endl; } } else { for (int i = 0; i < index-1; i++) { p = p->next; } s = (LNode *)new LNode[1]; s->data = data; s->next = p->next; p->next = s; cout << "数据" << data <<"插入" << "第" << index <<"位置成功!" << endl; } } //删除元素 void List::Delete(int index) { LNode *p = head, *s; int i = 0; if (index <= 0 || index>getLength()) { cout << "待删除元素不在链表中" << endl; return; } while (i<index-1) { i++; p = p->next; } s = p->next; p->next = s->next; cout << "第" << index <<"个元素删除成功!" << endl; delete s; } //打印链表 void List::printList() { LNode *p = head; cout << "printList: "; if (p->next==NULL) { cout << "空链表" << endl; return; } p = p->next; while (p!=NULL) { cout << p->data << " "; p = p->next; } cout << endl; } //交换元素 void List::exchange(int index1, int index2) { LNode *p = head, *s1, *s2; s1 = (LNode *)new LNode[1]; s2 = (LNode *)new LNode[1]; int data; int min = (index1 > index2) ? index2 : index1; int max = (index1 > index2) ? index1 : index2; if (min<=0 || max>getLength()) { cout << "待交换元素超过链表范围" << endl; return; } p = p->next; for (int i = 1; i <= max;i++) { if (i==min) { s1 = p; } if (i==max) { s2 = p; } p = p->next; } data = s1->data; s1->data = s2->data; s2->data = data; cout << "第" << index1 << "个元素和" << "第" << index2 << "个元素交换成功" << endl; } //打印第index个元素 void List::getData(int index) { LNode *p = head; if (index <= 0 || index>getLength()) { cout << "待查找元素不在链表中" << endl; return; } for (int i = 0; i < index;i++) { p = p->next; } cout << "第" << index << "元素为" << p->data << endl; } int main() { List list; list.CreateList(); list.printList(); list.Insert(10, 2); list.Insert(20, 10); list.printList(); list.Delete(2); list.printList(); list.getData(1); list.getData(2); list.getData(3); list.getData(4); list.getData(10); list.exchange(1,2); list.printList(); list.exchange(4, 3); list.printList(); return 0; }
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END
喜欢就支持一下吧