linklist::linklist() {//创建一个只有头结点的链表,数据域类容为0,next指向null head = new Lnode; head->data = 0; head->next = NULL; } linklist::~linklist() {//销毁链表,链表不像顺序表那样free申请的空间的首地址就可以,而是每个节点都需要free Lnode* p; while (head->next!=NULL) { p = head; head = head->next; delete p; } delete head; head=nullptr; cout<<"链表已经销毁"<<endl; }
链表中函数的实现:
链表创建:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
void linklist::createLinklist(int n) {//从头结点开始延长链表 Lnode* pnew, * ptemp; ptemp = head; if (n < 0) { cout << "输入的节点数有误" << endl; return; } for (int i = 0; i < n; i++) { pnew = new Lnode; cout << "请输入第" << i + 1 << "个节点的里的值:"; cin >> pnew->data; pnew->next = NULL; ptemp->next = pnew; ptemp = pnew; } }
遍历链表:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
void linklist::travalLinklist() {//遍历链表,输出链表的值 if (head == NULL || head->next == NULL) { cout << "链表为空表" << endl;/*链表为空表的判断方法:就是头结点是空节点 或者头结点的指针域指向的是空节点,则这个链表为空表*/ } else { Lnode* p = head; while (p->next != NULL) { p = p->next; cout << p->data<<" "; } } }
链表长度:
1 2 3 4 5 6 7 8 9 10
int linklist::GetLength() { int count=0; Lnode* p = head; while (p->next!=NULL) { count++; p = p->next; } return count; }
寻找数据:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Lnode* linklist::find(int n) {//输入这个节点的数据,返回节点的地址 if (head == NULL || head->next == NULL) { cout << "链表为空表,不存在这个数据" << endl; returnNULL; } else { Lnode* p = head->next; while (p->next != NULL) { if (p->data == n) { return p; } p = p->next; } returnNULL; } }
删除数据:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
void linklist::DeleteElem(int n) { Lnode* ptemp = find(n); if (ptemp==head->next) { Deleteheadelem(); } else { Lnode* p = head; while (p->next!=ptemp)//寻找删除的节点的上一个节点 { p = p->next; } p->next = ptemp->next; delete ptemp; ptemp = nullptr; }
}
链表排序:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
void linklist::sort() {//使用冒泡排序 int len = GetLength(); int temp; Lnode* p = head; for (int i = 0; i < len - 1; i++) { p = head->next; for (int j = 0; j < len - i - 1; j++) { if (p->data>p->next->data)//大的放后面,小的放前面 { temp = p->data; p->data = p->next->data; p->next->data = temp; } p = p->next; } } }
删除头节点后的第一个节点:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
void linklist::Deleteheadelem() { Lnode* p = head; if (p==nullptr||p->next==nullptr) { cout << "该表为空表" << endl; } else { Lnode* temp = nullptr; p = p->next; temp = p->next; delete p; p = nullptr; head->next = temp; } }
链表逆转:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
void linklist:: reserve() { Lnode* temp = new Lnode; temp->next = nullptr; Lnode* cur = head->next; Lnode* net = cur->next; while (net != nullptr) { cur->next = temp->next; temp->next = cur; cur = net; net = cur->next; } cur->next = temp->next; head->next = cur; delete temp; cout << "链表已逆转" << endl; }
classpoint//创建一个point类来存放矩阵中每个点的位置坐标与下一次的方向 { public: int i; int j; int direction;//上下左右移动 point(int r = 0, int c = 0, int d = 0) :i(r), j(c), direction(d) {}; };