链表(Linked list)，三个链表函数（C/C++语言描述）

大家好，欢迎来到IT知识分享网。

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。

　 链表(Linked list)是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表：顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据(data fields)和一或两个用来指向明上一个/或下一个节点的位置的链接（”links”）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，[1]但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个”结点”（如概述旁的图所示），表示线性表中一个数据元素 。

　　根据情况，也可以自己设计链表的其它扩展。但是一般不会在边上附加数据，因为链表的点和边基本上是一一对应的（除了第一个或者最后一个节点，但是也不会产生特殊情况）。不过有一个特例是如果链表支持在链表的一段中把前和后指针反向，反向标记加在边上可能会更方便。
　　对于非线性的链表，可以参见相关的其他数据结构，例如树、图。另外有一种基于多个线性链表的数据结构：跳表，插入、删除和查找等基本操作的速度可以达到O(nlogn)，和平衡二叉树一样。
　　其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。
　　由分别表示,,…, 的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表.

三个链表函数（C/C++语言描述）
　#include <stdio.h>
　　#include <stdlib.h>
　　#include <iostream>
　　struct Node{
　　int data;//数据域
　　struct Node * next;//指针域
　　};
　　/**************************************************************************************
　　*函数名称:insert
　　*函数功能:在链表中插入元素.
　　*输入:head 链表头指针,p新元素插入位置,x 新元素中的数据域内容
　　*输出:无
　　*************************************************************************************/
　　void insert(Node * head,int p,int x){
　　Node * tmp = head;
　　//for循环是为了防止插入位置超出了链表长度
　　for(int i = 0;i<p;i++)
　　{
　　if(tmp == NULL)
　　return ;
　　if(i<p-1)
　　tmp = tmp->next;
　　}
　　Node * tmp2 = new Node;
　　tmp2->data = x;
　　tmp2->next = tmp->next;
　　tmp->next = tmp2;
　　}
　　/**************************************************************************************
　　*函数名称：del
　　*函数功能:删除链表中的元素
　　*输入:head 链表头指针,p 被删除元素位置
　　输出:被删除元素中的数据域.如果删除失败返回-1
　　**************************************************************************************/
　　int del(Node * head,int p){
　　Node * tmp = head;
　　for(int i = 0;i<p;i++)
　　{
　　if(tmp == NULL)
　　return -1;
　　if(i<p-1)
　　tmp = tmp->next;
　　}
　　int ret = tmp->next->data;
　　tmp->next = tmp->next->next;
　　return ret;
　　}
　　void print(Node *head){
　　for(Node *tmp = head; tmp!=NULL; tmp = tmp->next)
　　printf(“%d “,tmp->data);
　　printf(“\n”);
　　}
　　int main(){
　　Node * head;
　　head = new Node;
　　head->data = -1;
　　head->next=NULL;
　　return 0;
　　}
　　例子：
　　#include<iostream>
　　#define NULL 0
　　struct student
　　{
　　long num;
　　struct student* next;
　　};
　　int main()
　　{
　　int i,n;
　　student* p=(struct student*)malloc(sizeof(struct student));
　　student* q=p;
　　printf(“输入几个值”);
　　scanf(“%d”,&n);
　　for(i=1;i<=n;i++)
　　{
　　scanf(“%d”,&(q->num));
　　q->next=(struct student*)malloc(sizeof(struct student));
　　q=q->next;
　　}
　　printf(“值 第几个”);
　　int rank;
　　scanf(“%d %d”,&(q->num),&rank);
　　student* w=p;
　　for(i=1;i<rank-1;i++)
　　{
　　w=w->next;
　　}
　　q->next=w->next;
　　w->next=q;
　　for(i=1;i<=n+1;i++)
　　{
　　printf(“%d “,p->num);
　　p=p->next;
　　}
　　return 0;
　　}
　　//指针后移麻烦