顺序表可以看作有序元素的线性排列，它们之间是相互紧密挨着对方。
而链表可以看作有序结点的线性排列，它们之间并不是紧密相连，前后有随机长度的距离。
可以看出，链表和顺序表可以两个本质不同的地方：
- 顺序表存储的单位是元素；链表存储的单位是结点（元素+指针）
- 顺序表各个元素的地址是连续相连的；链表各个元素的地址是不一定连续的
那么链表各个结点的地址是不连续的，那么用什么方法保证前后的元素线性相连呢？答案就是指针。指针在我们脑海中的画面就像一个连线一样可以指向下一个元素。而指针的实质其实也是一个变量，只不过这个变量存储的是其他变量的地址（迷糊的同学可以去重新复习一下指针和内存管理）。
既然知道了顺序表和链表的本质不同，那么它们在做相同基本操作的时候，时间复杂度就会大大不同。
- 顺序表由于地址连续，则可以利用下标进行查找，时间复杂度为常数；但是插入删除元素需要移动后面的元素，平均时间复杂度为O(n)。
- 链表由于地址不连续，但是查找得利用指针去遍历，时间复杂度为O(n)；但是插入删除元素仅需修改指针即可，时间复杂度为常数。
#pragma once #includeusing namespace std; typedef int elemtype; typedef struct Node { elemtype data; Node *next; }; template class linkList { public: //初始化链表 linkList(); //头插法建链表 void InitlinkList(); //在特定位置插入元素 void InsertList(int index, elemtype e); //删除指定元素 void deleteList(elemtype e); //打印链表 void ShowList(); //返回表长 int Printlength(); //链表排序 void SortList(); //反转链表 void RevList(); //删除重复元素 void delfunction(); private: Node *head; };
#include "linkList.h" //初始化链表 templateinline linkList ::linkList() { head = new Node; head->data = 0; head->next = NULL; } //以头插法建表 template void linkList ::InitlinkList() { elemtype e; while (cin >> e) { Node* s = new Node; s->data = e; s->next = head->next; head->next = s; } cout << "构建完成" << endl; } //在指定位置插入元素结点 template void linkList ::InsertList(int index, elemtype e) { int i; Node* p; p= head; for (i = 1; i < index; i++) { p = p->next; } Node* s = new Node; s->data = e; s->next = p->next; p->next = s; } //删除指定元素 template void linkList ::deleteList(elemtype e) { Node* p = head; Node* q = p->next; while (q->data) { if (q->data == e) { p->next = q->next; q->next = nullptr; } p = p->next; q = p->next; } } //打印链表 template void linkList ::ShowList() { int i; Node* p=head->next; cout << "链表元素为:" << endl; while (p!=NULL) { cout << p->data<<","; p = p->next; } } //返回长度 template int linkList ::Printlength() { int count=0; Node* p = head; while (p->next != nullptr) { count++; } return count; } //以冒泡排序排列链表 template void linkList ::SortList() { int i; int count=0; int temp; Node* p = head; Node* q = NULL; cout << "排序开始" << endl; while (p->next!=NULL) { count++; p = p->next; } for (i = 0; i < count - 1; i++) { int num = count - 1 - i; p = head->next; q = p->next; while (num > 0) { if (q->data < p->data) { temp = q ->data; q->data = p->data; p->data = temp; } p = p->next; q = p->next; num--; } } } //反转链表 template void linkList ::RevList() { Node* p1 = head; Node* p2= head->next; Node* p3 = p2->next; while (p2 != NULL) { p2->next = p1; p1 = p2; p2 = p3; if (p2->next != NULL) { p3 = p2->next; } } } //删除重复元素 template void linkList ::delfunction() { this->SortList(); Node* p = head->next; Node* q = p->next; while (q != NULL) { if (p->data == q->data) { p->next = q->next; q->next = NULL; q = p->next; } p = p->next; q = p->next; } }
