链表的回顾与总结（一）正序、逆序、有序、插入、修改、删除

逆序链表

#include<iostream>
using namespace std;
struct node
{int data;node* next;
};//最好不要全局定义指针，很麻烦
void show(node* head)
{while (head){cout << head->data << ' ';head = head->next;}
}
int main()
{int i, j, k, ch;node* head = NULL;node* p, * s;cin >> ch;//这个相比cin>>p->num更方便while (ch != 0){p = new node;p->data = ch;p->next = head;head = p;cin >> ch;//当最后一位是0的时候连新的结点都不需要建立}show(head);return 0;
}

升级版：

#include<iostream>
using namespace std;
struct node
{int data;node* next;
};
void show(node*head)
{while (head){cout << head->data << ' ';head = head->next;}
}
int main()
{int n, i, j, k;node* head = NULL;node* q=NULL, * p;;cin >> n;while (n--){cin >> k;p = new node;p->data = k;p->next = head;head = p;}show(head);return 0;
}

正序链表

方法一：（逆序建立链表，再逆序输出链表）
struct node
{int data;node* next;
};
void show(node* head)//指针传参新建一个匿名对象
{if (head == NULL){return;//代码块的结束}else{show(head->next);//递归:入栈出栈的方式cout << head->data << ' ';}
}
int main()
{int i, j, k, ch;node* head = NULL;node* p, * s;cin >> ch;while (ch != 0){p = new node;p->data = ch;p->next = head;head = p;cin >> ch;}show(head);return 0;
}
方法二：（正序建立链表，正序输出）
int main()
{int n, i, j, k;node* head = NULL;node* q = NULL;//把q初始化为空指针的原因是VS会显示“使用了可能未初始化的本地指针变量”node* p;cin >> k;while (k!=0){p = new node;p->data = k;p->next = NULL;if (head == NULL)head = p;else q->next = p;q = p;cin >> k;}show(head);return 0;
}

升级版：

while(head)
{
cout<<head->data<<' ';
head=head->next;
}
int main()
{
int n,i,j,k;
cin>>n;
node*head=NULL;
node*q=NULL;//把q初始化为空指针的原因是VS会显示“使用了可能未初始化的本地指针变量”
node *p;
while(n--)
{
cin>>k;
p=new node;
p->data=k;
p->next=NULL;
if(head==NULL)
head=p;
else q->next=p;
q=p;
}
show(head);
return 0;
}

有序链表，输入一串数。

#include<iostream>
using namespace std;
struct node
{int data;node* next;
};
void insert(node*& head, int k)
{node* s, * p, * q;s = new node;s->data = k;s->next = NULL;if (head == NULL){head = s;return;//头是空的}if (head->data > s->data){s->next = head;head = s;return;}for (q = head, p = head->next; p; q = p, p = p->next){if (p->data > s->data){s->next = p;q->next = s;return;}}q->next = s;return;
}void show(node*head)
{while (head){cout << head->data << ' ';head = head->next;}
}
int main()
{int n, i, j, k;node* head = NULL;cin >> k;while (k!=0){insert(head, k);cin >> k;}show(head);return 0;
}

建立有序链表，为该有序链表中插入值，插值结束后链表仍然有序。

#include<iostream>
using namespace std;
struct node
{int data;node* next;
};
void insert(node*& head, int k)
{node* s, * p, * q;s = new node;s->data = k;s->next = NULL;if (head == NULL){head = s;return;//头是空的}if (head->data > s->data){s->next = head;head = s;return;}for (q = head, p = head->next; p; q = p, p = p->next){if (p->data > s->data){s->next = p;q->next = s;return;}}q->next = s;return;
}
void show(node*head)
{while (head){cout << head->data << ' ';head = head->next;}
}
int main()
{int n, i, j, k;node* head = NULL;node* q = NULL;//把q初始化为空指针的原因是VS会显示“使用了可能未初始化的本地指针变量”node* p;cin >> n;while (n--){cin >> k;insert(head, k);}cin >> j;insert(head, j);show(head);return 0;
}

节点修改

#include<iostream>
using namespace std;
struct node
{int num;string name;int age;node* next;
};
void show(node*head)
{while (head){cout << head->num << ' ' << head->name << ' ' << head->age << ' ' << endl;head = head->next;}
}
node *change(node* head, int m, string ming, int agee)
{node* h1 = head;while (head){if (head->num == m){head->name = ming;head->age = agee;break;}head = head->next;}return h1;
}
int main()
{int n, i, j, k, m, agee;string ming;cin >> n;node* head = NULL;node* q=NULL, * p;while (n--){p = new node;cin >> p->num >> p->name >> p->age;p->next = NULL;if (head == NULL)head = p;else q->next = p;q = p;}cin >> m >> ming >> agee;head=change(head, m, ming, agee);show(head);return 0;
}

删除结点

#include<iostream>
using namespace std;
struct node
{int num;string name;int age;node* next;
};
void show(node*head)
{while (head){cout << head->num << ' ' << head->name << ' ' << head->age << ' ' << endl;head = head->next;}
}
node* del(node* head, int k)
{node* pre = head;node* cur = head->next;while (cur!=NULL)//先遍历除头结点之外的部分{if (cur->age == k){pre->next = cur->next;}else pre = cur;cur = cur->next;}if (head->age == k)//最后看节点head = head->next;return head;
}
int main()
{int n, i, j, k, m, agee;string ming;cin >> n;node* head = NULL;node* q=NULL, * p;while (n--){p = new node;cin >> p->num >> p->name >> p->age;p->next = NULL;if (head == NULL)head = p;else q->next = p;q = p;}cin >> k;head=del(head, k);show(head);return 0;
}