链表的一些操作（新建，输出，删除，插入，查找，逆序，排序，释放链表，链表长度计算，查找倒数第k节点的元素）
一. 链表的概念
1、链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，有一系列结点（地址）组成，结点可动态的生成。
2、结点包括两个部分：
一、存储数据元素的数据域（内存空间）
二、存储指向下一个结点地址的指针域。
3、相对于线性表顺序结构，操作复杂。
二.链表的作用
1、实现数据元素的存储按一定顺序储存，允许在任意位置插入和删除结点。
2、包括单向结点，双向结点，循环接点
3、C/C++/Java都可以实现
三.链表的优缺点
优点：链表实现数据元素储存的顺序储存，是连续的
缺点：因为含有大量的指针域，所以占用空间大，同时因为只有头结点（后面说明）是明确知道地址的，所以查找链表中的元素需要从头开始寻找，非常麻烦。
四.建立一个链表结点结构
struct linked_list
{
int num;
linked_list *next;
};
五.对链表的操作
介于本人初学链表，只能对单链表进行一些基础操作
1.新建链表（新建一个长度为n的链表）
linked_list* create(linked_list *head,int n)
{
linked_list *ptr,*tail=NULL;
head=NULL;
for(int i=0;i { ptr=(linked_list*)malloc(sizeof(linked_list)); scanf("%d",&ptr->num); ptr->next=NULL; if(!head) head=ptr;//对首节点进行赋值 else tail->next=ptr;//新增链表尾部 tail=ptr;//尾节点移动 } return head; }//新建一个长度为n的链表并返回首节点的地址 2.删除（释放）链表 在单链表中我们在程序的最后加上一个释放内存的方法或者操作，这是一个很好的习惯。（我对这个操作其实不是很懂，有问题请指出，以下是我对代码） void release(linked_list *head) { linked_list *ptr=head; while(head) { ptr=head; head=head->next; free(ptr); } free(head); if(!head) cout<<"链表已删除，请重新输入链表长度\n"; }//删除整个链表 3.插入一个数据到链表中的某个位置 linked_list* insert(linked_list* head, linked_list* ptr, int n, int l) { linked_list* h = head; if (n == 1)//插入到第一个位置 { ptr->next = head; head = ptr; } else { for (int i = 0;i < n - 2;i++) h = h->next; ptr->next = h->next; h->next = ptr; } return head; }//插入某个数据到n位置 ，并返回首节点 4.删除链表中的第n个位置的的节点 我用的方法是覆盖法 当需要删除一个节点p时，只需要将p的前一个节点的next赋为p->next,但是由于是单向的，只知道p，无法知道p前一个节点，所以需要转换思路。将p下一个的节点覆盖到p节点即可，这样就等效于将p删除了。（当然呢我这并没有把那个节点给释放掉，不知道会不会出问题） linked_list* del(linked_list* head, int l, int n) { linked_list* h = head; if (l == 1)//删除首节点 head = head->next; else//删除中间节点 { for (int i = 0;i < l - 2;i++) h = h->next; h->next = h->next->next; } return head; }//删除第l个位置的节点，并返回首节点 5.对单向链表第a到第b位置的节点反转 思路是这样的： 要求将一带链表头List head的单向链表逆序。 分析： 1). 若链表为空或只有一个元素，则直接返回； 2). 设置两个前后相邻的指针p,q. 将p所指向的节点作为q指向节点的后继； 3). 重复2),直到q为空 4). 调整链表头和链表尾 Alt linked_list* reverse(linked_list *head,int a,int b,int n) { linked_list *p=head,*q=head->next,*s=NULL,*h=head; if(a>b) { int temp=a; a=b; b=temp; } int qq=b-a,t=a-2; if(head==NULL||head->next==NULL||a==b)//当链表为空或者链表只有一个节点或者a==b时候，直接返回head return head; if(a==1&&b>1)//a==1时候对链表a到b进行逆序 { b--; while(b--) { s=q->next; q->next=p; p=q; q=s; } head->next=q; head=p; return head; } //a!=1的时候对a到b位置进行逆序 a--; while(a--) { p=p->next; q=q->next; }//p移动到第a个位置，q移动到a+1个位置 while(t--) h=h->next;//h是p的前一个位置 while(qq--)//对第a个位置到第b个位置的链表进行倒序 { s=q->next; q->next=p; p=q; q=s; } h->next->next=q; h->next=p; return head; }//对链表a到b位置的数据逆序并返回head的位置； 6.查找链表中数据为a的第一个节点的位置 int find(linked_list *head,int a,int n) { int sum=1; while(head) { if(head->num==a) break; sum++; head=head->next; } if(sum>n) return -1; return sum; }//查找数据为a的节点的位置 7.链表排序操作 linked_list* linked_listsort(linked_list *head,int p)//p判断进行升序还是降序操作 { linked_list *slow=head,*fast=NULL; int temp; if(p==1)//升序排序 { while(slow)//冒泡思想，就不解释了 { fast=slow->next; while(fast) { if(fast->num { temp=slow->num; slow->num=fast->num; fast->num=temp; } fast=fast->next; } slow=slow->next; } cout<<"你已进行了升序排序，查看排序结果请输入1\n"; } else//降序排序 { while(slow) { fast=slow->next; while(fast) { if(fast->num>slow->num) { temp=slow->num; slow->num=fast->num; fast->num=temp; } fast=fast->next; } slow=slow->next; } cout<<"你已进行了降序排序，查看排序结果请输入1\n"; } return head; } 8.计算链表长度 int lengthofLinklist(linked_list *head) { int len = 0; while(head) { head=head->next; len++; } return len; }//计算链表长度 9.查找链表倒数第k个元素 //两次遍历查找倒数第k元素 linked_list* findKthTail(linked_list *head, int k) { if (head==NULL || k<=0) return NULL; int len = 0; linked_list *root=head; while (head) { head=head->next; len++; } if (len int countdown = len-k; while (countdown--) root=root->next; return root; } //快慢指针 查找倒数第k元素 linked_list* findKthTail2(linked_list* head, int k) { if (head == NULL || k <= 0) return NULL; linked_list *slow = head; linked_list *fast = head; for(int i=0;i { //快指针先走k步 if(fast) fast = fast->next; else return NULL;//如果k>链表长度 返回NULL； } while(fast) //相当于slow移动了 链表长度len - k步； { fast = fast->next; slow = slow->next; } return slow; } 10.代码整合 #include using namespace std; struct linked_list { int num; linked_list* next; }; linked_list* reverse(linked_list* head, int a, int b, int n) { linked_list* p = head, * q = head->next, * s = NULL, * h = head; if (a > b) { int temp = a; a = b; b = temp; } int qq = b - a, t = a - 2; if (head == NULL || head->next == NULL || a == b)//当链表为空或者链表只有一个节点或者a==b时候，直接返回head return head; if (a == 1 && b > 1)//a==1时候对链表a到b进行逆序 { b--; while (b--) { s = q->next; q->next = p; p = q; q = s; } head->next = q; head = p; return head; } //a!=1的时候对a到b位置进行逆序 a--; while (a--) { p = p->next; q = q->next; }//p移动到第a个位置，q移动到a+1个位置 while (t--) h = h->next;//h是p的前一个位置 while (qq--)//对第a个位置到第b个位置的链表进行倒序 { s = q->next; q->next = p; p = q; q = s; } h->next->next = q; h->next = p; return head; }//对链表a到b位置的数据逆序并返回head的位置； //head是首节点，l是待删除位置，n是链表长度 //这个函数的l和n和上个插入函数的不大一样，无伤大雅吧，嘿嘿 linked_list* del(linked_list* head, int l, int n) { linked_list* h = head; if (l == 1)//删除首节点 head = head->next; else//删除中间节点 { for (int i = 0;i < l - 2;i++) h = h->next; h->next = h->next->next; } return head; }//删除第l个位置的节点，并返回首节点 //head是首节点，ptr是存放待插入数据的节点，l是链表长度，n是待插入的位置 linked_list* insert(linked_list* head, linked_list* ptr, int n, int l) { linked_list* h = head; if (n == 1)//插入到第一个位置 { ptr->next = head; head = ptr; } else { for (int i = 0;i < n - 2;i++) h = h->next; ptr->next = h->next; h->next = ptr; } return head; }//插入某个数据到n位置 ，并返回首节点 void release(linked_list* head) { linked_list* ptr = head; while (head) { ptr = head; head = head->next; free(ptr); } free(head); if (!head) cout << "链表已删除，请重新输入链表长度\n"; }//删除整个链表 linked_list* create(linked_list* head, int n) { linked_list* ptr, * tail = NULL; head = NULL; for (int i = 0;i < n;i++) { ptr = (linked_list*)malloc(sizeof(linked_list)); cin >> ptr->num; ptr->next = NULL; if (!head) head = ptr;//对首节点进行赋值 else tail->next = ptr;//新增链表尾部 tail = ptr;//尾节点移动 } return head; }//新建一个长度为n的链表并返回首节点的地址 int find(linked_list* head, int a, int n) { int sum = 1; while (head) { if (head->num == a) break; sum++; head = head->next; } if (sum > n) return -1; return sum; }//查找数据为a的节点的位置 int lengthofLinklist(linked_list* head) { int len = 0; while (head) { head = head->next; len++; } return len; }//计算链表长度 linked_list* linked_listsort(linked_list* head, int p)//p判断进行升序还是降序操作 { linked_list* slow = head, * fast = NULL; int temp; if (p == 1)//升序排序 { while (slow)//冒泡思想，就不解释了 { fast = slow->next; while (fast) { if (fast->num < slow->num) { temp = slow->num; slow->num = fast->num; fast->num = temp; } fast = fast->next; } slow = slow->next; } cout << "你已进行了升序排序，查看排序结果请输入1\n"; } else//降序排序 { while (slow) { fast = slow->next; while (fast) { if (fast->num > slow->num) { temp = slow->num; slow->num = fast->num; fast->num = temp; } fast = fast->next; } slow = slow->next; } cout << "你已进行了降序排序，查看排序结果请输入1\n"; } return head; } //两次遍历查找倒数第k元素 linked_list* findKthTail(linked_list* head, int k) { if (head == NULL || k <= 0) return NULL; int len = 0; linked_list* root = head; while (head) { head = head->next; len++; } if (len < k) return NULL; int countdown = len - k; while (countdown--) root = root->next; return root; } //快慢指针 查找倒数第k元素 linked_list* findKthTail2(linked_list* head, int k) { if (head == NULL || k <= 0) return NULL; linked_list* slow = head; linked_list* fast = head; for (int i = 0;i < k;i++) { //快指针先走k步 if (fast) fast = fast->next; else return NULL;//如果k>链表长度 返回NULL； } while (fast) //相当于slow移动了 链表长度len - k步； { fast = fast->next; slow = slow->next; } return slow; } int main() { int n, q, op, a, b, p, k; cout << "请输入链表长度\n"; while (cin >> n) { linked_list* head; head = (linked_list*)malloc(sizeof(linked_list)); cout << "请输入" << n << "个数据存入链表\n"; head = create(head, n); cout << "请输入你要进行的操作:\n"; cout << "1.输出链表\n"; cout << "2.删除链表第q个位置的数据\n"; cout << "3.输入一个数据插入到第q个位置\n"; cout << "4.对链表a到b位置的数据进行逆序\n"; cout << "5.查找某个元素所在节点的位置\n"; cout << "6.对链表进行排序\n"; cout << "7.查找链表导数第k个元素\n"; cout << "8.删除并释放链表\n"; while (1) { linked_list* h = head; cin >> op; if (op == 1) { h = head; cout << "长度为" << lengthofLinklist(h) << "的链表为:\n"; while (h) { cout << h->num << " "; h = h->next; } cout << endl << endl << "你还要进行什么操作？" << endl; } else if (op == 2) { cout << "请输入你要删除的位置:"; cin >> q; head = del(head, q, n); cout << "你已删除第" << q << "位置的数据，要看输出结果请输入1\n"; n--;//链表长度-1 } else if (op == 3) { linked_list* ptr = NULL; ptr = (linked_list*)malloc(sizeof(linked_list)); cout << "请输入待插入的数据:"; cin >> ptr->num; ptr->next = NULL; cout << "你要将" << ptr->num << "这个数据插入哪个位置？\n" << "请输入待插入的位置:"; cin >> q; head = insert(head, ptr, q, n); cout << "要看输出结果请输入1\n"; n++;//链表长度+1； } else if (op == 4) { cout << "请输入a和b，对链表第a位置和第b位置的链表反转\n"; cin >> a >> b; head = reverse(head, a, b, n); cout << "已对链表第" << a << "到第" << b << "位置的数据进行了反转\n"; cout << "要看输出结果请输入1\n"; } else if (op == 5) { cout << "请输入你要查找的元素:"; cin >> a; int node = find(head, a, n); if (node < 0) cout << "链表中没有这个元素\n"; else cout << a << "在第" << node << "个位置\n"; cout << endl << "你还要进行什么操作？" << endl; } else if (op == 6) { cout << "你要进行升序（1）排序还是降序（2）排序？请输入你选择的排序方法:"; cin >> p; head = linked_listsort(head, p); } else if (op == 7) { cout << "请输入你想查找链表中倒数第几个节点位置的值："; cin >> k; if (k > lengthofLinklist(head)) { cout << "输入的长度不合法，此时链表长度为：" << lengthofLinklist(head); cout << "请重新输入7 进行此操作\n"; } else { linked_list* q = findKthTail(head, k); cout << "链表中倒数第" << k << "个位置节点的值为：" << q->num << endl << "你还要进行什么操作？" << endl; } } else if (op == 8) { release(head); break; } else cout << "输入的操作不对哦！\n请重新输入\n"; } } return 0; } 在借鉴了好多大牛写的博客之后，写出了我第一篇博客； 希望有任何问题大家可以指出，我会改进的！！！