单链表的定义、表示及操作（一）_单链表定义

一、链式存储结构的特点

用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，每个结点都必须有指针域。

二、单链表

1.定义：每一个结点只含有一个指针域的链式结构称为单链表。
2.单链表结点的类型定义：

typedef struct Lnode{
      int data;    //数据域
      struct Lnode *next; //指针域
}Lnode,*LinkList;
1
2
3
4

3、关于带头节点的单链表及不带头节点的单链表
（1）带头节点的单链表为空时：L->next==NULL；
(2)不带头节点的单链表为空时：L=NULL;

三、单链表的基本操作

1、单链表中获取一个元素
（1）找第i个结点

GetElem(LinkList L,int i,int e)
{
    int j;
    LinkList p;
    p=L->next;j=1;//p指向第一个结点，j为计数器
    i=3;  //假设需要找第3个结点
    while(p&&j<i)  //当p指针不为空并且还未到达第i个结点
    {
      p=p->next;  //p指向下一个结点
      j++;    //计数器加一
    }
   if(!p||j>i)
   return ERROR;//第i个元素不存在
   else e=p->data;
   return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(2)找值为x的元素

GetElem(LinkList L,int x,int e)
{
      while(p&&p->data!=x)
      {
         p=p_>next;
      }
      if(!p)
      return ERROR;//不存在值为x的结点
      else e=p->data;
      return OK;
}
1
2
3
4
5
6
7
8
9
10
11