一、链表主体
// 链表结构体 typedef struct node { int date; struct node *next; // 还未定义别名只能使用struct node定义next指针 } Node; /*** typedef struct 结构名 { 类型 变量名; 类型 变量名; } 结构别名1, 结构别名2; 这里如果没有typedef定义别名在定义结构体的时候则需要添加 struct node n1; ***/
链表由结构体构成，结构体包含节点数据以及指向下一个节点的指针
二、创建链表
// 创建链表 Node *NodeInit(int n) { // 创建链表 Node *head = new Node; // 头节点 这里也可以使用malloc方式 // Node *head = (Node *)malloc(sizeof(Node)); // 头节点一般不存储数据 Node *per = head; for (int i = 0; i < n; i++) { // 申请新的空间存储相应数据然后放入per指针 Node *p = new Node; //申请新的空间 p->date = i * 10 + 1; //给新的空间写入数据 p->next = NULL; //新的空间指向空 per->next = p; //原来的节点指向这个新的空间 per = p; //获取新空间的数据 } return head; }
Node *MainHead = NodeInit(5);
三、链表的应用
1.打印链表
// 打印链表数据 void NodeDisplay(Node *head) { Node *p = head->next; while (p != NULL) { // 遍历节点 std::cout << p->date << " -> "; p = p->next; } std::cout << "NULL" << std::endl; }
2.求链表长度
// 链表长度 int NodeLenth(Node *head) { Node *p = head->next; int count = 0; while (p != NULL) { // 遍历节点 count++; p = p->next; } return count; }
3.插入数据（按照指定位置）
// 指定位置插入链表数据 (头节点、插入位置、插入数据) void NodeInsert(Node *head, int index, int date) { if (index < 0 || index > NodeLenth(head)) throw "index error"; //如果插入位置超出链表长度抛出异常 Node *per = head; for (int i = 0; i < index; i++) { // 循环next到index位置 per = per->next; } Node *NewNode = new Node; NewNode->date = date; NewNode->next = per->next; per->next = NewNode; }
4.插入数据（头插）
// 头插 void NodePushFront(Node *head, int date) { Node *per = head; Node *NewNode = new Node; NewNode->date = date; NewNode->next = per->next; per->next = NewNode; }
5.插入数据（尾插）
// 尾插 void NodePushBack(Node *head, int date) { Node *per = head; for (int i = 0; i < NodeLenth(head); i++) { // 让节点指向最后一个节点 per = per->next; } Node *NewNode = new Node; NewNode->date = date; NewNode->next = NULL; per->next = NewNode; }
6.查找元素是否存在
// 查找元素：如果元素存在返回true，不存在返回false bool NodeFind(Node *head, int date) { Node *p = head->next; for (int i = 0; i < NodeLenth(head); i++) { if (p->date == date) return true; else p = p->next; } return false; }
7.删除指定位置数据
// 删除指定位置数据 void NodeDeleteDate(Node *head, int index) { if (index < 0 || index > NodeLenth(head)) throw "index error"; //如果删除位置超出链表长度抛出异常 Node *per = head; for (int i = 0; i < index; i++) { per = per->next; } Node *p = per->next; per->next = per->next->next; delete p; }
8.删除最后一个节点
// 删除最后一个节点 void NodePopback(Node *head) { Node *per = head; for (int i = 0; i < NodeLenth(head) - 1; i++) { per = per->next; } Node *p = per->next; per->next = NULL; delete p; }
9.删除第一个节点
// 删除第一个节点 void NodePopFront(Node *head) { Node *per = head; Node *p = per->next; per->next = per->next->next; delete p; }
10.修改节点数据
// 修改元素 void NodeChange(Node *head, int index, int date) { if (index < 0 || index > NodeLenth(head)) throw "index error"; //如果修改位置超出链表长度抛出异常 Node *per = head; for (int i = 0; i < index; i++) { // 让节点指向index位置 per = per->next; } per->date = date; }
11.清空链表节点
// 清空链表 void NodeClear(Node *head) { while (head->next != NULL) { Node *p = head->next; head->next = head->next->next; delete p; } }
四、完整程序
/* * @Author: Stylle * @Date: 2020-08-25 18:08:28 * @LastEditors: Stylle * @LastEditTime: 2020-08-25 21:43:50 * @FilePath: \learing-master\链表.cpp */ #include <iostream> // 链表结构体 typedef struct node { int date; struct node *next; // 还未定义别名只能使用struct node定义next指针 } Node; /*** typedef struct 结构名 { 类型 变量名; 类型 变量名; } 结构别名1, 结构别名2; 这里如果没有typedef定义别名在定义结构体的时候则需要添加 struct node n1; ***/ // 创建链表 Node *NodeInit(int n) { // 创建链表 Node *head = new Node; // 头节点 这里也可以使用malloc方式 // Node *head = (Node *)malloc(sizeof(Node)); // 头节点一般不存储数据 Node *per = head; for (int i = 0; i < n; i++) { // 申请新的空间存储相应数据然后放入per指针 Node *p = new Node; //申请新的空间 p->date = i * 10 + 1; //给新的空间写入数据 p->next = NULL; //新的空间指向空 per->next = p; //原来的节点指向这个新的空间 per = p; //获取新空间的数据 } return head; } // 链表长度 int NodeLenth(Node *head) { Node *p = head->next; int count = 0; while (p != NULL) { // 遍历节点 count++; p = p->next; } return count; } // 指定位置插入链表数据 (头节点、插入位置、插入数据) void NodeInsert(Node *head, int index, int date) { if (index < 0 || index > NodeLenth(head)) throw "index error"; //如果插入位置超出链表长度抛出异常 Node *per = head; for (int i = 0; i < index; i++) { // 循环next到index位置 per = per->next; } Node *NewNode = new Node; NewNode->date = date; NewNode->next = per->next; per->next = NewNode; } // 头插 void NodePushFront(Node *head, int date) { Node *per = head; Node *NewNode = new Node; NewNode->date = date; NewNode->next = per->next; per->next = NewNode; } // 尾插 void NodePushBack(Node *head, int date) { Node *per = head; for (int i = 0; i < NodeLenth(head); i++) { // 让节点指向最后一个节点 per = per->next; } Node *NewNode = new Node; NewNode->date = date; NewNode->next = NULL; per->next = NewNode; } // 打印链表数据 void NodeDisplay(Node *head) { Node *p = head->next; while (p != NULL) { // 遍历节点 std::cout << p->date << " -> "; p = p->next; } std::cout << "NULL" << std::endl; } // 查找元素：如果元素存在返回true，不存在返回false bool NodeFind(Node *head, int date) { Node *p = head->next; for (int i = 0; i < NodeLenth(head); i++) { if (p->date == date) return true; else p = p->next; } return false; } // 清空链表 void NodeClear(Node *head) { while (head->next != NULL) { Node *p = head->next; head->next = head->next->next; delete p; } } // 删除指定位置数据 void NodeDeleteDate(Node *head, int index) { if (index < 0 || index > NodeLenth(head)) throw "index error"; //如果删除位置超出链表长度抛出异常 Node *per = head; for (int i = 0; i < index; i++) { per = per->next; } Node *p = per->next; per->next = per->next->next; delete p; } // 删除最后一个节点 void NodePopback(Node *head) { Node *per = head; for (int i = 0; i < NodeLenth(head) - 1; i++) { per = per->next; } Node *p = per->next; per->next = NULL; delete p; } // 删除第一个节点 void NodePopFront(Node *head) { Node *per = head; Node *p = per->next; per->next = per->next->next; delete p; } // 修改元素 void NodeChange(Node *head, int index, int date) { if (index < 0 || index > NodeLenth(head)) throw "index error"; //如果修改位置超出链表长度抛出异常 Node *per = head; for (int i = 0; i < index; i++) { // 让节点指向index位置 per = per->next; } per->date = date; } int main(int argc, char **argv) { Node *MainHead = NodeInit(5); NodeDisplay(MainHead); std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl; // 按位置插入数据 NodeInsert(MainHead, 2, 12); NodeDisplay(MainHead); std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl; // 尾插 NodePushBack(MainHead, 42); NodeDisplay(MainHead); std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl; // 头插 NodePushFront(MainHead, 0); NodeDisplay(MainHead); std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl; // 修改数据 NodeChange(MainHead, 1, 99); NodeDisplay(MainHead); // 查找数据 if (NodeFind(MainHead, 12)) { std::cout << "已查询到元素12" << std::endl; } // 删除指定节点 NodeDeleteDate(MainHead, 7); NodeDisplay(MainHead); std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl; // 删除最后一个节点 NodePopback(MainHead); NodeDisplay(MainHead); std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl; // 删除第一个节点 NodePopFront(MainHead); NodeDisplay(MainHead); std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl; // 清空节点 NodeClear(MainHead); NodeDisplay(MainHead); std::cout << "链表长度：" << NodeLenth(MainHead) << std::endl; return 0; }
五、运行结果
六、总结
程序的说明在注释里已经说明的比较清楚了，最后说一下链表的一般使用场景，和其他的几种链表（本文编写的链表为单链表）
1、链表包含两个部分：数据域、节点指针
2、链表一般使用在需要快速插入和删除而不需要随机访问的情况下使用
3、链表和数组的区别：链表数据随机地址存储，访问需要需要从节点遍历，而数组存储在连续的内存空间，可以使用下标访问（随机访问）
4、单向链表：
5、双向链表（不常使用）：
和单向链表相比多一个指针域，一个指向前面的数据节点，一个指向后面的数据节点
6、循环链表：
首尾节点相互链接，特点是”无头无尾“，比较利于数据存储缓存。
虽然本文只编写了单向链表，但是我相信看懂了上面的代码，写出双向链表和循环链表并不是多难。
