单链表查找图示（三链表结构图解）

电子计算机的本质是对输入(input)的数据进行处理(processing)，对处理的结果形成输出(output)。程序表现为数据（data）和对数据的操作（operation）。冯诺依曼的自动存储程序概念，就是将数据和处理数据的代码（操作步骤）存入内存，由CPU对数据按预先定义好的操作步骤进行处理。数据和代码都通过内存地址进行访问。操作代码的存储是静态的（一条条按顺序取出即可），但数据不一样，因为可能需要处理的数据量巨大且关系复杂，那数据存储的空间效率和操作的时间效率就是不得不需要考虑的问题。所以数据的存储不仅包括数据自身，且包括数据之间的关系（relation），称为数据结构(data structure)，数据的关系包括实际存储的物理关系，还包括逻辑关系。逻辑关系包括一对一的线性关系，一对多的树形关系，以及多对多的图形关系。逻辑关系都可以通过物理的线性存储和链式存储体现出来。也就是说，不够是什么逻辑关系，对于数据元素都可以通过线性存储的线性关系或链式额外存储的地址或指针关连起来。

链表是一种动态分配存储空间的链式存储结构。它包括一个“头指针”变量，头指针中存入一个地址，该地址指向一个元素。链表中的每一个元素称为“结点”。每个结点由两部分组成：存储数据元素的数据域和存储直接后继存储位置的指针域（指针域中存储的即是链表的下一个结点的存储位置，是一个指针）。多个结果连结成一个链表。如下图所示：

单链表查找图示,三链表结构图解(1)

数据在内存中的存储，需要讲究“存得进去、取得出来”。在链表中体现链表的建立、节点的插入、删除、查询。且需要体现空间节省、时间效率的原则。但往往“鱼和熊掌不可兼得”。相对于其它数据结构，链表的特点是存储空间较浪费、节点查询较慢，但插入、删除效率高。

结点的数据结构一般用结构体加指针来实现：

struct 结构名称
{
数据类型数据变量
......
struct 结构名称 *next;
};
typedef struct 结构名称 Node;
typedef node *link;

一个简单的单链接及查找实例的代码如下（用来实现查找的代码用粗体字标识）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct student
{
char name[15];
int mark;
struct student *next;
}Node, *node;
int search(char *value, node head)
{
node p;
p=head->next;
while(p!=NULL)
if (strcmp(p->name,value)==0)
{
return p->mark;
}
else
{
p=p->next;
}
return -1;
}
int main()
{
int num,i,j;
char name[15];
node p,pTemp,head;
head = (node)malloc(sizeof(Node));
if(head==NULL)
{
printf("error");
exit(1);
}
else
head->next = NULL;
printf("Please input the number of students:\n");
scanf("%d",&num);
printf("Please input the information:");
for(i=0;i<num;i )
{
p = (node)malloc(sizeof(Node));
if(p==NULL)
{
printf("error");
exit(1);
}
else
{
printf("\nname:");
scanf("%s",p->name);
printf("mark:");
scanf("%d",&p->mark);
if(head->next == NULL)
{
head->next = p;
pTemp=p;
}
else
{
pTemp->next = p;
pTemp=p;
}
}
}
pTemp->next=NULL;
p=head->next;
printf("\nthe list:\n");
while(p!=NULL)
{
printf("name:%s ",p->name);
printf(" mark:%d\n",p->mark);
p=p->next;
}
printf("please input the name while do you want to find\n");
scanf("%s",name);
j = search(name,head);
if(j==-1)
printf("no find\n");
else
printf("the mark is:%d\n",j);
system("pause");
return 0;
}