C++鏈表難倒了不少小萌新，今天我來寫一下心得喂急，以后忘了還能復習,先講用malloc和free這一對cp版的單鏈表吧。
拓展一：
補充c的free和c++的delete的區(qū)別：
delete 用于釋放new分配的內存笛求，和new成對調用
free 用于釋放malloc分配的內存廊移，和malloc成對調用
使用free釋放時需要判斷指針是否為NULL??，delete不用
free 釋放內存探入，但不調用對象的析構函數
delete 不僅釋放內存狡孔，還調用對象的析構函數
delete 和new是對對象的操作，是運算符??
free 和malloc是對內存空間的操作??
（這一段參考https://blog.csdn.net/amf12345/article/details/99656492）
拓展二：
SqList *L和SqList * &L的區(qū)別（這的Sqlist相當于我的Node）https://www.cnblogs.com/xiang-little/p/5840809.html
不過我一般用結構體指針Link蜂嗽，應該沒有上面顧慮那么多
頭指針一定要有苗膝，頭節(jié)點不一定。但是帶上頭節(jié)點好處很多植旧，比如
頭指針數據域沒有東西辱揭，頭節(jié)點數據域一般沒有東西。鏈表的有效長度從首元節(jié)點算起病附。
拓展四：
前一節(jié)點的next可以看成是下一節(jié)點（但在創(chuàng)建節(jié)點時不要犯Link s->next=head這樣的錯誤Ｎ是浴！完沪！還有偶爾會把next看成一條線）域庇。
拓展五：
頭指針是以確定線性表中第一個元素對應的存儲位置，一般用于處理數組覆积，鏈表听皿，隊列等數據結構。單鏈表可以用頭指針的名字來命名宽档。單鏈表中頭指針指向頭節(jié)點写穴。頭指針指向上述數據結構的起始數據的指針，如指向數組首地址的指針雌贱，指向鏈表表頭節(jié)點的指針啊送。
頭指針也就是表頭指針
在單鏈表的第一個結點之前附設一個結點（是個結構體），稱之為頭結點欣孤。頭結點的數據域可以不存儲任何信息馋没，頭結點的指針域存儲指向第一個結點的指針（即第一個元素結點的存儲位置）。頭結點的作用是使所有鏈表（包括空表）的頭指針非空降传，并使對單鏈表的插入篷朵、刪除操作不需要區(qū)分是否為空表或是否在第一個位置進行，從而與其他位置的插入、刪除操作一致声旺。
第一節(jié)點笔链，不太清楚，應該是鏈表有效數據存儲的第一個節(jié)點吧腮猖，就是去除了頭結點的第一個節(jié)點鉴扫。（來自https://zhidao.baidu.com/question/1173824466773596459.html）
第一步，弄一個結構體
typedef struct node
{
int data;
struct node* next;
}Node, * Link;//結構體別名澈缺，Node等價于 struct node; Link等價于struct node*
第二步坪创，寫一個創(chuàng)建鏈表的函數
Link create()
{
Link head = (Link)malloc(sizeof(Node));//創(chuàng)建頭節(jié)點,Node不可以改成Link，免得以后操作出錯姐赡，head是頭指針
head->next = NULL;//空表
return head;
}
當時沒做刪除操作時莱预，因為Link head = (Link)malloc(sizeof(Node));最后那個Node改為Link發(fā)現鏈表的創(chuàng)建、插入项滑、打印正常依沮，所以覺得三個Link行得通，然后刪除操作的free老報錯枪狂，最后發(fā)現是Node改為Link的錯誤（被某同學嘲諷了QAQ）
插入分兩種講悉抵，第三步講頭插法
先補充個東西：假如單鏈表有相鄰三點，從左往右順序為a摘完，b姥饰，c，那么a->next是b孝治，a->next->next是c列粪。
void headadd(Link head, int newdata)
{
Link s = (Link)malloc(sizeof(Node));//創(chuàng)建空節(jié)點s
s->data = newdata;
s->next = head->next;//這句和下一句不能弄反,此時s->next=NULL
head->next = s;
}
頭插法從一個空表開始，生成新結點谈飒，讀取數據存放到新結點的數據域中岂座，然后將新結點插入到當前鏈表的表頭上，直到結束為止杭措。
簡單來說费什，就是把新加進的元素放在表頭后的第一個位置:先讓新節(jié)點的next指向頭點之后（s->next = head->next），然后讓表頭的next指向新節(jié)點（head->next = s手素，或者說s點放在head后面）鸳址。
嗯，用現實環(huán)境模擬的話就是插隊的方法泉懦，始終讓新結點插在第一的位置稿黍。因此插入的東西打印出來為倒序
尾插法
void tailadd(Link head, int newdata)
{
Link s = (Link)malloc(sizeof(Node));//創(chuàng)建空節(jié)點s
s->data = newdata;
Link r = head;//創(chuàng)建運動節(jié)點r，指向head
while (r->next)//要找到NULL前面那點r
{
r = r->next;
}
r->next = s;//從尾部插入
s->next = NULL;
}
嗯崩哩，用現實環(huán)境模擬的話就是插隊的方法巡球，始終讓新結點插在最后的位置言沐。尾插法插入的東西打印出來是順眼的正序。感覺這r尾指針是工具人酣栈，但是最后又不能釋放掉险胰，釋放就報錯，為什么??
初始化賦值后插入數據
詳情見整個代碼
按照數值修改數據
詳情見整個代碼
按照位置修改數據
詳情見整個代碼
詳情見整個代碼
打印鏈表
void print(Link head)
{
Link temp = head->next;//從第二個節(jié)點開始打印
while (temp)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << "\n";
}
單鏈表的銷毀
void destroy(Link head)
{
Link p = head;
Link q ;
while (p)
{
q = p->next;//先保留下一點的地址
free(p);
p = q;//此時p已經移動到q的位置矿筝，有點像繼承遺產
}
head->next = NULL;
}
這里沒有頭節(jié)點起便，所以只有銷毀單鏈表，沒有清空單鏈表的情況跋涣。如果有頭節(jié)點缨睡，銷毀（參數是頭指針）和清空（參數是頭節(jié)點）的區(qū)別是頭指針的保留與否鸟悴。
……………………………………………………………………………………………………………
整個代碼示例（多了頭節(jié)點略微有點不同陈辱，上面都基于沒有頭節(jié)點的情況）
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef struct node
{
int data;
struct node* next;
}Node, * Link;//結構體別名，Node等價于 struct node; Link等價于struct node*
Link create()
{
Link head = (Link)malloc(sizeof(Node));//創(chuàng)建頭指針,Node不可以改成Link细诸，免得以后操作出錯
Link L = (Link)malloc(sizeof(Node));//創(chuàng)建頭節(jié)點
head->next = L;
L->next = NULL;//空表
return head;
}
void headadd(Link L, int data)
{
Link s = (Link)malloc(sizeof(Node));//創(chuàng)建空節(jié)點s
s->data = data;
s->next = L->next;//和下一句不能弄反,此時s->next=NULL
L->next = s;
}
void tailadd(Link L, int data)
{
Link s = (Link)malloc(sizeof(Node));//創(chuàng)建空節(jié)點s
s->data = data;
Link r = L;//創(chuàng)建運動節(jié)點r沛贪，指向L
while (r->next)
{
r = r->next;
}
r->next = s;//從尾部插入
s->next = NULL;
}
void insert(Link L, int i, int data2)//一般人家插入都是按位置插入的，按值插其前后少見
{ //i從L開始震贵，i>=1
Link p = L;
Link s = (Link)malloc(sizeof(Node));
s->data = data2;
for (int j = 1; j < i; j++)//找到插入位置i的前一個位置利赋，找的方法for循環(huán)比while循環(huán)更易懂
{
p = p->next;
}
s->next = p->next;
p->next = s;
}
void change1(Link L, int data, int data2)//按值查找
{
Link p = L;
while (p && p->data != data)//直接找到修改點，想修改數據為data的點
{
p = p->next;
}
p->data = data2;//修改data為data2
}
void change2(Link L, int i, int data2)//按位查找
//修改第i個有值點猩系，i>=1
{
Link p = L;
int j = 1;
while (p && j < i)//這個while和上面的while少了一個移動媚送，一般刪除和這個一樣都是找相應點的前一點
{
p = p->next;
j++;
}
p->next->data = data2;
}
void del1(Link L, int data)//按值查找刪除
{
Link p = L;
while (p->next && p->next->data != data)//找到刪除點的前一點
{
p = p->next;
}
if (p->next->next == NULL)//如果要刪除的是最后一個點
{
free(p->next);//與下面兩句不要弄錯順序，因為弄錯順序的意思不一樣寇甸，如果先指空的話塘偎，程序還是沒有釋放掉該節(jié)點空間
p->next = NULL;
}
else
{
Link q = p->next;
p->next = q->next;
free(q);//q為臨時節(jié)點，用完就釋放拿霉，不要弄錯成釋放p
}
}
void del2(Link L, int i)
{
Link p = L;
int j = 1;
while (p && j < i)//找到刪除點的前一點
{
p = p->next;
j++;
}
if (p->next->next == NULL)//如果要刪除的是最后一個點
{
free(p->next);//與下面兩句不要弄錯順序吟秩，因為弄錯順序的意思不一樣，如果先指空的話绽淘，程序還是沒有釋放掉該節(jié)點空間
p->next = NULL;
}
else
{
Link q = p->next;
p->next = q->next;
free(q);//q為臨時節(jié)點涵防，用完就釋放，不要弄錯成釋放p
}
}
void print(Link L)
{
Link temp = L->next;//從第二個節(jié)點開始打印
while (temp)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << "\n";
}
void destroy(Link head)
{
Link p = head;
Link q;
while (p)
{
q = p->next;
free(p);
p = q;//此時p已經移動到q的位置沪铭，有點像繼承遺產
}
}
int main()
{
Link head1 = create();
for (int i = 0; i < 5; i++)
{
int data = i;
headadd(head1->next, data);
}
cout << "鏈表1創(chuàng)建并賦值后為：";
print(head1->next);
cout << endl << "分別輸入鏈表1插入的位置和插入的值：";
int a, b;
scanf("%d %d", &a, &b);
insert(head1->next, a, b);
print(head1->next);
printf("\n分別輸入你要修改的值和修改后的值：");
int n0, n1;
scanf("%d %d", &n0, &n1);
change1(head1->next, n0, n1);
cout << endl << "鏈表1修改值后為：";
print(head1->next);
cout << endl << "輸入你要刪去的值：";
int n2;
scanf("%d", &n2);
del1(head1->next, n2);
cout << endl << "鏈表1刪除值后為：";
print(head1->next);
destroy(head1);
cout << "——————————————————————————————————————————————————————" << endl;
Link head2 = create();
for (int i = 5; i < 10; i++)
{
int data = i;
headadd(head2->next, data);
}
cout << "鏈表2創(chuàng)建并賦值后為：";
print(head2->next);
printf("\n分別輸入你要修改的值的位置和修改后的值：");
int j, m1;
scanf("%d %d", &j, &m1);
change2(head2->next, j, m1);
cout << endl << "鏈表2修改值后為：";
print(head2->next);
cout << endl << "輸入你要刪去的值的位置：";
int k;
scanf("%d", &k);
del2(head2->next, k);
cout << endl << "鏈表2刪除值后為：";
print(head2->next);
destroy(head2);
return 0;
}
new和delete版的壮池，在原基礎上，把
Link head = (Link)malloc(sizeof(Node));
和相應的free
改為
Link head = new Node;
和相應的delete
就行了
題目思考：單鏈表反轉杀怠、求未知長度單鏈表的中間節(jié)點
多編程自己才會掌握知識火窒！
循環(huán)單鏈表??????
循環(huán)單鏈表，與普通單鏈表的區(qū)別就是驮肉，單鏈表的最后一個元素s的next指向空熏矿，而循環(huán)鏈表的末尾元素s的next指向頭節(jié)點（注意，不是指向頭指針）
#include "iostream"
using namespace std;
constexpr auto TRUE = 1;
constexpr auto FALSE = 0;
constexpr auto OK = 1;
constexpr auto ERROR = 0;
typedef int Elemtype;
typedef int Status;
typedef struct Node
{
Elemtype data;
struct Node* next;
} Node;
typedef struct Node* Link;
/*
功能：初始化一個循環(huán)空鏈表
*/
Link create()
{
Link head;
head = (Link)malloc(sizeof(Node));
head->next = head;//循環(huán)無數據表
return head;
}
/*
功能：創(chuàng)建循環(huán)鏈表
*/
void tailadd(Link head)
{
Link p = head;
int flag = 1;
double c;
while (flag)
{
cin >> c;
if (c != -99999)
{
Link s = (Link)malloc(sizeof(Node));
s->data = c;
s->next = head; // 因為是尾插法，所以申請結點的next指向鏈表頭票编，構成循環(huán)
p->next = s;
p = s;
}
else
{
flag = 0;
}
}
}
/*
功能：循環(huán)鏈表中元素的個數
*/
int getlength(Link head)
{
Link p = head;
int count = 0;
while (p->next != head)
{
count++;
p = p->next;
}
return count;
}
/*
功能：在第 i 個位置插入一個元素
*/
Status insert(Link head, int i, Elemtype e)
{
Link pre = head;
int k = 1;
while (pre && k < i) // 找到第 i-1 個元素
{
pre = pre->next;
k++;
}
if (!pre || k > i || i > getlength(head) + 1)
{
cout << "插入位置錯誤褪储！" << endl;
return ERROR;
}
else
{
Link s = (Link)malloc(sizeof(Node));
s->data = e;
s->next = pre->next;
pre->next = s;
}
return OK;
}
/*
功能：刪除第 i 個元素，并將其值賦給*e
*/
Status del(Link head, int i, Elemtype* e)
{
Link pre = head;
int k = 1;
while (pre && k < i) // 找到第 i-1 個元素
{
pre = pre->next;
k++;
}
if (!pre || k > i || i > getlength(head))
{
cout << "刪除位置錯誤慧域！" << endl;
return ERROR;
}
else
{
Link r = pre->next;
pre->next = pre->next->next;
*e = r->data;
free(r);
}
return OK;
}
/*
功能：查找第 i 個元素鲤竹，并將查找到的元素放入 *e 中
*/
Status find(Link head, int i, Elemtype* e)
{
Link p = head;
int k = 0;
while (p && k < i) // 找到第 i 個元素
{
p = p->next;
k++;
}
if (!p || k > i || i > getlength(head) || i <= 0)
{
cout << "查找位置錯誤！" << endl;
return ERROR;
}
else
{
*e = p->data;
}
return OK;
}
/*
功能：打印整個鏈表
*/
Status print(Link head)
{
Link p;
p = (head)->next;
if (p != NULL)
{
while (p != head)
{
cout << p->data << " ";
p = p->next;
}
}
else
{
cout << "沒有元素昔榴！" << endl;
return ERROR;
}
cout << endl;
return OK;
}
void main()
{
Link head;
Elemtype e;
cout << "開始初始化..............................................." << endl;
head = create();
cout << "初始化操作完畢辛藻！" << endl;
cout << "開始建表，請輸入元素：(這里是尾插法建表互订，輸入-99999結束建表)..........." << endl;
tailadd(head);
cout << "建表操作完畢吱肌！" << endl;
cout << "打印線性表中的所有數據：";
print(head);
cout << "打印線性表的長度：";
int count = getlength(head);
cout << count << endl;
cout << "-------------------------------------------------" << endl;
cout << "開始插入（在第6個位置插入81）............................" << endl;
insert(head, 6, 81);
cout << "插入操作完畢！" << endl;
cout << "打印線性表中的所有數據：";
print(head);
cout << "打印線性表的長度：";
int count2 = getlength(head);
cout << count2 << endl;
cout << "-------------------------------------------------" << endl;
cout << "開始刪除（這里刪除第2個元素）............................" << endl;
del(head, 2, &e);
cout << "刪除操作完畢!" << endl;
cout << "刪除后打印線性表中的所有數據：";
print(head);
cout << "-------------------------------------------------" << endl;
cout << "開始查找（這里查找第5個元素）............................." << endl;
if (find(head, 5, &e))
{
cout << "查找操作完畢!" << endl;
cout << "打印查找到的數據：";
cout << e << endl;
}
else
{
cout << "查找位置錯誤仰禽！" << endl;
}
system("pause");
}
void headadd(Link head)
{
int flag = 1;
double c;
while (flag)
{
cin >> c;
if (c != -99999)
{
Link s = (Link)malloc(sizeof(Node));
s->data = c;
s->next = head->next;
head->next = s;
}
else
{
flag = 0;
}
}
}
實際應用：約瑟夫環(huán)問題
約瑟夫環(huán)問題，是一個經典的循環(huán)鏈表問題吐葵，題意是：已知 n 個人（以編號1规揪，2，3温峭，…猛铅，n分別表示）圍坐在一張圓桌周圍，從編號為 k 的人開始順時針報數凤藏，數到 m 的那個人出列奸忽；他的下一個人又從 1 還是順時針開始報數，數到 m 的那個人又出列清笨；依次重復下去月杉，要求找到最后出列的那個人。
例如有 5 個人抠艾，要求從編號為 3 的人開始苛萎，數到 2 的那個人出列：
出列順序依次為：
編號為 3 的人開始數 1，然后 4 數 2检号，所以 4 先出列腌歉；
4 出列后，從 5 開始數 1齐苛，1 數 2翘盖，所以 1 出列；
1 出列后凹蜂，從 2 開始數 1馍驯，3 數 2阁危，所以 3 出列；
3 出列后汰瘫，從 5 開始數 1狂打，2 數 2，所以 2 出列混弥；
最后只剩下 5 自己趴乡，所以 5 出列。
作者：小Q_wang
鏈接：http://www.reibang.com/p/24734b20c81b
來源：簡書
著作權歸作者所有蝗拿。商業(yè)轉載請聯(lián)系作者獲得授權晾捏，非商業(yè)轉載請注明出處。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int number;
struct node* next;
}person;
person* initLink(int n) {
person* head = (person*)malloc(sizeof(person));
head->number = 1;
head->next = NULL;
person* cyclic = head;
int i;
for (i = 2; i <= n; i++) {
person* body = (person*)malloc(sizeof(person));
body->number = i;
body->next = NULL;
cyclic->next = body;
cyclic = cyclic->next;
}
cyclic->next = head;//首尾相連
return head;
}
void findAndKillK(person* head, int k, int m) {
person* tail=NULL;//一般指針定義都要初始化哀托，免得有未知錯誤惦辛，這里不初始化就有錯
person* p = head;
//找到編號為k的人
while (p->number != k) {
tail = p;//tail為刪除點前一點
p = p->next;
}
//從編號為k的人開始，只有符合p->next==p時萤捆，說明鏈表中除了p結點裙品，所有編號都出列了俗批，
while (p->next != p) {
int i;
//找到從p報數1開始俗或，報m的人，并且還要知道數m-1de人的位置tail岁忘，方便做刪除操作辛慰。
for (i = 1; i < m; i++) {
tail = p;
p = p->next;
}
tail->next = p->next;//從鏈表上將p結點摘下來，過了這一句此時是tail->next是原來的p->next
printf("出列人的編號為:%d\n", p->number);
free(p);
p = tail->next;//繼續(xù)使用p指針指向出列編號的下一個編號干像，游戲繼續(xù)
}
printf("出列人的編號為:%d\n", p->number);
free(p);
}
int main() {
printf("輸入圓桌上的人數n:");
int n;
scanf("%d", &n);
person* head = initLink(n);
printf("從第k人開始報數(k>1且k<%d)：", n);
int k;
scanf("%d", &k);
printf("數到m的人出列：");
int m;
scanf("%d", &m);
findAndKillK(head, k, m);
return 0;
}
代碼略改動
單鏈表逆轉https://blog.csdn.net/LMengi000/article/details/79130114
