c++链表基本操作

阅读说明：以下创建的都是data域为节点编号（1，2，3..）且头节点不算进节点数，data为节点数的链表。

目录

一.单链表操作

1.单链表创建

2.单链表访问 

3.得到第k个节点

4. 单链表按值查找

5.单链表插入

6. 链表节点删除

7. 单链表销毁

二.双向链表

1. 双链表创建

 2.得到双链表的第k节点（同单链表）

三.循环链表

1.循环链表创建

2.循环链表访问

 3.循环链表合并

 约瑟夫问题

一.单链表操作

注意事项：

(1)注意节点边界问题，指针声明时必须初始化为空（0/null）–结构体内的也需初始化。

(2)访问链表的时候注意：

 linklist* q = 0; for (int j = 1; j <= k; j++) { q = node;//q为第k个节点 node = node->next;//node为第k+1个节点 }

q为本节点，node始终为下一节点，勿错用。 

1.单链表创建

struct linklist { int data; linklist* next; }; linklist* creat(int n) {//创建含有n个节点的链表 linklist* head; linklist* node; linklist* end; head = new linklist;//申请表头空间 end = head; head->data = n; //可以选择从表头开始存放所需数据，也可以选择独立表头； //这里选择独立表头，并且表头 data表示节点数； for (int j = 1; j <= n; j++) { node = new linklist; node->data = j;//存放数据 end->next = node; end = node; //靠end的移动来创建链表 } return head;//头指针表示一个链表 }

2.单链表访问 

void vist(linklist* head) {//访问head链表前n个节点的data linklist* temp = head->next; while(temp) { cout << temp->data << " "; temp = temp->next; } } int main() { int n; cin >> n; vist(creat(n));//访问链表前n个节点的值 }

 输出结果：

3.得到第k个节点

这种写法不需要知道表长，但是容易出现边界问题，须慎重。

如果不传入节点参数，默认返回尾节点–c不支持这种操作

linklist* getnode(linklist* head, int k=-1) {//得到head链表的第k个节点 //不传入k，默认返回尾节点，重要操作，cnt>=0,所以cnt++！=-1 linklist* node = head->next; linklist* q = 0; int cnt = 0; while (node && cnt++ != k) { //没到尾且没到k节点循环（正常执行了k-1次循环，node为第k节点 q = node; node = node->next; } if (k != -1 && node == 0) return 0;//不存在该节点返回0 return q;//如果没有找到k节点，返回null } int main() { int n, k; cin >> n >>k; cout << getnode(creat(n),k)->data; }

示例： 

//不传入k

4. 单链表按值查找

struct linklist { int data; linklist* next=0; }; int check(linklist* head, int k) {//查找head链表中有无值k linklist* temp = head->next; linklist* q=0; while (temp && k != temp->data) {//这种查询方式要记得初始化结构体指针为0，不然会出问题 q = temp;//保留原节点 temp = temp->next; } if (temp == 0) return 0; return temp->data; } int main() { int n,k; cin >> n>>k; int judge = check(creat(n), k); if (judge == 0)cout << "该链表不存在值为"< 
   

示例：

5.单链表插入

linklist* insert(linklist* head, int num, int k=-1) {//在第k个节点后插入num //支持尾插（不传k的值）和头插（k=0） linklist* node = head->next; linklist* q = head; int cnt = 0; while(node&&cnt++!=k){//这里实现了不传k的参数时实现尾插，但较难理解 q = node;//q表示第k个节点 node = node->next;//node表示k+1个节点 } linklist* temp = new linklist; temp->data = num; q->next = temp; temp->next = node; head->data++; return head; } int main() { int n, num,k; cin >> n>>num>>k; linklist* head = creat(n); insert(head, num,k);//不传k，默认尾插num vist(head);//输出该链表所有节点 }

 示例：

 （1）中间节点插入

（2）头插一个节点

 （3）尾插一个节点（不输入k）

6. 链表节点删除

linklist* earse(linklist* head, int k)// 删除第k个节点 { linklist* node = head->next; linklist* q=0; for (int j = 1; j < k; j++) { q = node; node = node->next; }//循环结束后q为第k-1个节点，node为第k个节点 q->next = node->next;//跳过第k节点链接相邻节点 delete node; head->data--; return head; } int main() { int n,k; cin >> n>>k; linklist* head = creat(n); earse(head, k);//删除head链表第k个节点 vist(head, head->data); }

示例：

7. 单链表销毁

linklist* destroy(linklist* head) {//销毁head链表(留下表头） linklist* node = head->next; linklist* q = 0; while (node) { q = node; node = node->next;//注意：node必须先移动到下一节点再删除 delete q; } head->data = 0; }

二.双向链表

简述双链表：在单链表的基础上多了前驱节点使后一节点可以访问前一节点（头尾单向）使链表更灵活但也更复杂——知道其中任一节点即可访问整个链表。

1. 双链表创建

dullist* dul_creat(int n) {//创建n个节点的双链表 dullist* head; dullist* node; dullist* end; dullist* q=0;//上一节点 head = new dullist;//申请表头空间 end = head; head->data = n; for (int j = 1; j <= n; j++) { q = end; //不用讨论头尾，头尾各指向0即可 node = new dullist; node->data = j; end->next = node; end = node; end->pre = q; } return head; }

 2.得到双链表的第k节点（同单链表）

dullist* dul_getnode(dullist* head, int k=-1) {//得到head链表的第k个节点 //不传入k，默认返回尾节点，重要操作cnt++！=k dullist* node = head->next; dullist* q = 0; int cnt = 0; while (node && cnt++ != k) { //没到尾且没到k节点循环（正常执行了k-1次循环，node为第k节点 q = node; node = node->next; } if (k != -1 && node == 0) return 0; return q;//如果没有找到k节点，返回null } int main() { int n, k; cin >> n >>k; dullist* node = dul_creat(n); cout << dul_getnode(node,k)->pre->data;//输出第k个节点的前一个节点的data }

示例：

三.循环链表

1.循环链表创建

struct linklist { int data; linklist* next=0; }; linklist* cy_creat(int n) {//创建一个有n个数据的循环链表 //这里创建一个头节点也存所需数据的循环链表（个人习惯） linklist* head; linklist* node; linklist* end; head = new linklist; end = head; for (int j = 1; j <= n; j++) { node = new linklist; end->data = j;//数据域存编号 if (j == n) //相比单链表，多一部尾节点与头节点相接 end->next = head; else { end->next = node; end = node; } } return head; }

2.循环链表访问

linklist* cy_vist(linklist* head, int k) {//得到head链表第k个顺序节点的地址 linklist* temp = head; linklist* q = 0; for (int j = 1; j <= k; j++) { q = temp;//q表示第k个节点 temp = temp->next; } return q; } int main() { int n,k; cin >> n>>k; linklist* head = cy_creat(n); cout< 
   
     data;//第k个顺序节点的data } 
   

示例： 

 3.循环链表合并

linklist* merge(linklist* head1, linklist* head2,int len1,int len2) {//合并表1和表2 //思路就是解开表1和表2的头尾节点，并交叉相连,但问题是需要得到数据长 //这里处理的是data存放编号的圆桌问题情况 linklist* end1 = cy_vist(head1, len1);//得到两个表的尾指针 linklist* end2 = cy_vist(head2, len2); end1->next = head2;//交叉链接 end2->next = head1; return head1;//合为一个表了，这里以head1为表头 } int main() { int n,m; cin >> n>>m; linklist* head1 = cy_creat(n); linklist* head2 = cy_creat(m); linklist* head = merge(head1, head2, n, m); for (int j = 1; j <= n+m; j++) { cout << head->data << " "; head = head->next; } }

示例：

 其他操作与单链表大同小异，不一一列举

下面以一道经典的圆桌问题为例：

 约瑟夫问题

题目描述：

n个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

输入格式：

输入两个整数 n,m。

输出格式：

输出一行 n 个整数，按顺序输出每个出圈人的编号。

样例：

输入：

10 3

输出：

3 6 9 2 7 1 8 5 10 4 

1≤m,n≤100

int main() { int n,m; cin >> n>>m; linklist* head=cy_creat(n); linklist* node = head; linklist* q=0; for (int j = 1; j <= n; j++) { for (int i = 1; i < m; i++) { q = node; node = node->next; } cout << node->data << " "; q->next = node->next; node = q->next; } }

未完待续