單鏈表概述
線性表的順序表的優點是隨機存取表中的任意元素，但是它的缺點也是明顯的，那就是在進行基本操作中的向順序表中插入和刪除數據元素時需要移動大量的元素。因此產生線性表的另一種鏈式存儲結構，也就是單鏈表。它沒有順序表的弱點，但是也失去了順序表的優點。
線性表的鏈式存儲結構的特點是用一組任意的存儲單元線性表的數據元素(這組存儲單元可以是連續的，也可以是不連續的)。因此，為了表示每個數據元素ai與其直接後繼數據元素ai+1之間的邏輯關系，對數據元素ai來說，除了存儲其本身的信息之外，還需要存儲一個指示其直接後繼的信息(即直接後繼的村相互位置)。這兩部分信息組成數據元素ai的存儲映像，稱為結點。它包括兩個域：其中存儲數據元素信息的域稱為數據域，存儲直接後繼存儲位置的域稱為指針域。指針域存儲的信息稱為指針或鏈。n個結點的鏈結成一個鏈表，即為線性表的鏈式存儲結構。又由於此鏈表的每個結點中只包含一個指針域，故又稱為線性鏈表或單鏈表。
下面示例
線性表（zhao,qian,sun, li, zhou,wu,zheng,wang）
線性鏈表
頭指針 H 31
存儲地址 數據域 指針域
1 li 43
7 qian 13
13 sun 1
19 wang NULL
25 wu 37
31 zhao 7
37 zheng 19
43 zhou 2
整個鏈表的存取必須從頭指針開始進行，頭指針指示鏈表中的第一個結點(即第一個數據元素的存儲映像)的存儲位置。同時由於最後一個數據元素沒有直接後繼，則線性鏈表中最後一個結點的指針為“NULL”。
用線性鏈表表示線性表時，數據元素之間的邏輯關系是由結點中的指針指示的。換句話說，指針為數據元素之間的邏輯關系的映像，則邏輯上相鄰的兩個數據元素其存儲的物理位置不要求緊鄰，這種存儲結構為非順序存儲映像或鏈式映像。
通常我們把鏈表畫成用箭頭相連接的結點的序列，結點之間的箭頭表示鏈域中的指針。因此上述的示例的線性鏈表的邏輯狀態為：
單鏈表的存儲結構為：
typedef struct LNode//重新定義結構類型為LNode
{
ElemType date;//定義的結點的數據域
struct LNode *next;//定義的結點的指針域
}LNode,*LinkLIst//定義的LNode類型的變量LinkList
有時我們在單鏈表中的第一個頭結點之前附設一個結點，稱為頭結點。因此帶頭結點的單鏈表表示為：
單鏈表進行插入和刪除的圖片為：
單鏈表的基本操作：
0基本操作前的准備
#include
using namespace std;
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
typedef struct LNode//重新定義結構類型為LNode
{
ElemType data;//定義的結點的數據域
struct LNode *next;//定義的結點的指針域
}LNode,*LinkList;//定義的LNode類型的變量LinkList
1初始化鏈表
//1初始化鏈表
Status InitList(LinkList &L)
{
L=(LinkList)malloc(sizeof(LNode));
if(!L)
{
return(OVERFLOW);
}
L->next=NULL;
return OK;
}
2銷毀鏈表
//2銷毀鏈表
Status DestoryList(LinkList &L)
{
LinkList q;
while(L)
{
q=L->next;
free(L);
L=q;
}
return OK;
}
3清空鏈表
//3清空鏈表
Status CLearList(LinkList &L)
{
LinkList p,q;
p=L->next;
while(p)
{
q=p->next;
free(p);
p=q;
}
L->next=NULL;
return OK;
}
4判斷鏈表是否為空
//4判斷鏈表是否為空
Status ListEmpty(LinkList L)
{
if (L->next)
{
return FALSE;
}
else
{
return TRUE;
}
}
5返回鏈表的長度
Status ListLength (LinkList L)
{
int i=0;
LinkList p;
p=L->next;
while(p)
{
i++;
p=p->next;
}
return i;
}
6返回線性表第i個數據元素的值
//6返回線性表第i個數據元素的值
Status GetElem_L(LinkList L,int i,ElemType &e)//L為帶頭結點的單鏈表的頭指針
{
LinkList p=L->next;
int j=1;//初始化，p指向第一個結點，j為指示器
while (p&&jnext;
++j;
}
if(!p||j>i)
{
return ERROR;//第i個元素不存在
}
e=p->data; //取第i個元素
return OK;
}
7向鏈表插入數據元素
//7向鏈表插入數據元素
Status ListInsert(LinkList &L,int i,ElemType e)
{
LinkList p=L;
int j=0;
while(p&&jnext;
++j;
}
if(!p||j>i-1)
{
return ERROR;
}
LinkList s=(LinkList)malloc(sizeof(LNode)); //生成新結點
s->data=e;
s->next=p->next; //插入L中
p->next=s;
return OK;
}
8刪除鏈表中的元素
//8刪除鏈表中的元素
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{
LinkList p=L;
int j=0;
while(p->next&&jnext;
++j;
}
if (!(p->next)||j>i-1)
{
return ERROR;
}//刪除位置不合理
LinkList q=p->next;
p->next=q->next;//刪除並釋放結點
e=q->data;
free(q);
return OK;
}
