链表
成都创新互联公司是一家专注于网站设计、网站制作与策划设计,汝南网站建设哪家好?成都创新互联公司做网站,专注于网站建设10多年,网设计领域的专业建站公司;建站业务涵盖:汝南等地区。汝南做网站价格咨询:18980820575
链表链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操作。
概况
链表(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语言描述）
#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;ip;i++)
{
if(tmp == NULL)
return ;
if(ip-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;ip;i++)
{
if(tmp == NULL)
return -1;
if(ip-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;
}
编辑本段结语
C语言是学习数据结构的很好的学习工具。理解了C中用结构体描述数据结构，那么对于理解其C++描述，Java描述都就轻而易举了！
编辑本段两种链表形式
一、循环链表 循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。 循环链表的运算与单链表的运算基本一致。所不同的有以下几点： 1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。 2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。
二、双向链表 双向链表其实是单链表的改进。 当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。 在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。
1、添加头文件"stdio.h"
2、struct student * creat(void)，但是你的main函数中返回接收却是用的int*类型。
3、主函数main应当明确声明为void main()
4、最为严重的是：struct student * creat(void) 函数体中使用了局部变量struct student *head; struct student *p1,*p2; 但是函数结束的地方却要返回这些指针，因此返回的值是无效数据。返回时，已经不再作用域了，是无效的空间。建议把这些数据当作输入参数，指针类型的。就可以正确的接收分配的struct student空间以及指针了。
5、struct student * creat(void) 函数体中，临时指针*p1、*p2再函数返回之前应当设置为NULL，避免因为局部变量的作用域结束导致相关的空间被清除。
总之，我建议把struct student * creat(void)定义修改为：
void creat(struct student **head).
以上内容经过调试，可以使用。
==================我的程序，经过完整的调试
#include "stdafx.h"
#include "malloc.h"
#include "stdio.h"
#define NULL 0
#define LEN sizeof(struct student)
struct student
{
long num;
float score;
struct student *next;
};
int n;
void creat(struct student **head) /*定义函数,此函数带回一个指向链表头的指针*/
{
struct student *p1,*p2;
n=0;
do
{
p1=(struct student *)malloc(LEN); /*开辟一个新单元*/
p1-next=NULL;
scanf("%ld,%f",p1-num,p1-score);
if(p1-num==0)
break;
n++;
if(n==1)
*head=p1;
else
p2-next=p1;
p2=p1;
} while(p1-num!=0) ;
p1=NULL;
p2=NULL;
}
void main()
{
struct student *p;
creat(p);
if(p!=NULL)
do
{
printf("%ld %5.1f\n",p-num,p-score);
p=p-next;
}while(p!=NULL);
flushall(); //清除键盘缓冲区，避免输入混淆
getchar(); //等待键盘任意输入，以便观察运算结果
}
看我的回答怎么样？
单链表的插入呀
for的意思是先创建一个空节点，p指向它，然后你输入一个元素，把这个元素放到这个节点的info域，即scanf（“%c”，p-info），这句应该在printf后面，你掉了
然后把这个p赋值给q的next域，应该是q-next=p;你写错了，即头节点指向下一个节点了
之后q=p;是让q指向这个新节点，继续循环。
正确代码：
for(i=1;in;i++)
{
p=(NODE*)malloc(sizeof(NODE));
printf("Enter a element\n");
scanf（“%c”，p-info）;
q-next=p;
q=p;
}
//insert "OL" into Order_Linear_List @ "i"
Status ListInsert_OL(Order_Linear_List L , int i , Order_Linear_List OL){
cout"this function begain to run ...\n";
//check the "i" illegal or not
if(i1 || iL.length) return ERROR ;
//realloc the RAM when the previous storage space is full ...
if(L.length = L.listSize){
Order_Linear_List * newBaseAdd ;
newBaseAdd = (Order_Linear_List *)realloc(L.listBase,(L.listSize+LIST_INCREAMENT)*sizeof(Order_Linear_List));
if(!newBaseAdd)return(OVERFLOW);
L.listBase = newBaseAdd ;
L.listSize += LIST_INCREAMENT ;
}
//get the index of where to insert the element
Order_Linear_List *q ;
q = L.listBase[i-1];
//move the element behand of the insert-index
Order_Linear_List *p ;
for (p = L.listBase[L.length-1] ; p = q ; --p) *(p+1) = *p ;
*q = OL ;
L.length += 1;
return OK ;
}
