链式表示的线性表之一——单链表1
所谓线性表的链式存储，就是采用一组任意的存储单元存放线性表的元素。这组存储单元可以是连续的，也可以是不连续的。为了表示每个元素ai与其直接后继ai+1的逻辑关系，除了存储元素本身的信息外，还需要存储一个指示其直接后继元素的信息（直接后继元素的地址）。这两部分构成的存储结构称为结点（node）。即结点包括两个域：数据域和指针域。结点结构如图所示。
通过指针域将线性表中n个结点元素按照逻辑顺序链在一起就构成链链表。
一般情况下，我们只关心链表中结点的逻辑顺序，而不关心它的实际存储位置。通常用箭头表示指针，把链表表示成通过箭头链接起来的序列。线性表（Kang,Geng,Guan,Chen,Zhou,Hua,Feng）如图所示。
为了操作上的方便，在单链表的第一个结点之前增加一个结点，称之为头结点。头结点的数据域可以存放如线性表的长度等信息，头结点的指针域存放第一个元素结点的地址信息，使其指向第一个元素结点。带头结点的单链表如图所示。
若带头结点的单链表为空链表，则头结点的指针域为“空”，如图所示。
【存储结构】
/*02_01——存储结构*/
typedef struct Node
{
DataType data;
struct Node *next;
}ListNode, *LinkList;/*ListNode是链表的结点类型，LinkList是指向链表结点的指针类型*/【基本运算】
【初始化单链表】
/*02_01——初始化单链表*/
void InitList(LinkList *head)
{
if ((*head=(LinkList)malloc(sizeof(ListNode)))==NULL)
{
/*02_01为头结点分配一个存储单元*/
exit(-1);
}
(*head)->next = NULL;/*02_01将单链表的头结点指针域置为空 */
}【判断单链表是否为空】
/*02_02判断单链表是否为空*/
int ListEmpty(LinkList head)
{
if (head->next==NULL)/*02_02如果单链表头结点的指针域为空*/
{
return 1; /*02_02返回1*/
}
else
{
return 0; /*02_02返回1*/
}
}
【按照序号查找】
/*02_03按照序号查找*/
ListNode *Get(LinkList head, int i)
/*02_03按照序号查找单链表中第i个结点，查找成功返回该结点的指针表示成功；否则返回NULL表示失败*/
{
ListNode *p;
int j;
if (ListEmpty(head))
{
return NULL;
}
if (i<1)
{
return NULL;
}
j = 0;
p = head;
while (p->next!=NULL&&j<i)
{
p = p->next;
j++;
}
if (j==i)
{
return p;
}
else
{
return NULL;
}
}
【查找元素值为e的结点】
/*02_04查找元素值为e的结点的元素，若查找成功则返回对应元素的结点指针，否则返回NULL表示失败*/
ListNode *LocateElem(LinkList head, DataType e)
{
ListNode *p;
p = head->next;
while (p)
{
if (p->data!=e)
{
p = p->next;
}
else
{
break;
}
}
return p;
}【确定元素所在单链表中的序号】
/*02_05定位操作，确定元素所在单链表中的序号*/
/*02_05从头指针出发依次访问每个结点，并将结点的值与e比较，如果相等，则返回该结点序号表示成功*/
/*02_05如果没有与e相等的元素则返回0表示失败*/
int LocatePos(LinkList head, DataType e)
{
ListNode *p;
int i;
if (ListEmpty(head))/*02_05在查找第i个元素之前，判断链表是否为空*/
{
return 0;
}
p = head->next; /*02_05指针指向第一个结点*/
i = 1;
while (p)
{
if (p->data==e) /*02_05找到与e相等的元素*/
{
return i; /*02_05返回该序号*/
}
else
{
p = p->next;
i++;
}
}
if (!p) /*02_05如果没有找到与e相等的元素*/
{
return 0; /*返回0*/
}
}【在第i个位置插入元素e】
先来看看如何在单链表中插入一个节点。假设存储元素e的结点为p，要将p指向的结点插入到pre和pre->head之间，无需移动结点元素，只需要改变p和pre指针指向即可。先把*p变成*pre的直接后继结点，如图所示，代码如下：
p->next=pre->next;
pre->next=p;注意：
插入结点的两行代码不能颠倒顺序。如果先进行pre->next=p;后进行p->next=pre->next;操作，则第一条代码就会被覆盖掉pre->next的地址，pre->next的地址就会变成p的地址，这样pre->next就相当与上一级断开了链接。如图
在单链表的第i个位置插入一个新元素e的步骤如下：
step1.在链表中找到其直接前驱结点，即第i-1个结点，并由指针pre指向该结点，如图所示：
step2.申请一个新结点空间，由p指向该结点，将值e赋值给p指向结点的数据域。
step3.修改*p和*pre结点的指针域，如图所示
/*02_06在第i个位置插入元素e*/
int InsertList(LinkList head, int i, DataType e)
/*02_06在单链表中的第i个位置插入一个结点，结点的元素值为e。插入成功返回1，失败返回0.*/
{
ListNode *pre, *p;/*02_06定义第i个元素的前驱结点指向pre，指针p指向新生成的结点*/
int j;
pre = head;/*02_06指针p指向头结点*/
j = 0;
while (pre->next != NULL&&j < i - 1)
/*02_06找到第i-1个结点，即第i个结点的前驱结点*/
{
pre = pre->next;
j++;
}
if (j!=i-1)/*02_06如果没有找到说明插入位置错误*/
{
cout << "02_06插入位置错误！" << endl;
return 0;
}
/*02_06新生成一个结点，并将e赋值给该结点的数据域*/
if ((p=(ListNode*)malloc(sizeof(ListNode)))==NULL)
{
exit(-1);
}
p->data = e;
/*02_06插入结点操作*/
p->next = pre->next;
pre->next = p;
return 1;
}【删除第i个结点】
先来看看如何删除链表的第i个结点。假设p指向第i个结点，要将*p结点删除，只需将它的直接前驱结点的指针绕过，使其直接指向它的直接后继结点即可。如图所示：
删除第i个结点的步骤如下：
step1.找到第i个结点的直接前驱结点，即第i-1个结点，并用pre指向该结点，p指向其直接后继结点，即第i个结点，如图所示
step2.将*p结点的数据域赋值给e；
step3.删除第i个结点，并释放*p结点的内存空间。过如图
/*02_07删除第i个结点*/
int DeleteList(LinkList head, int i, DataType *e)
/*02_07删除单链表中的第i个结点；删除成功返回1，失败返回0。*/
{
ListNode *pre, *p;
int j;
pre = head;
j = 0;
while (pre->next!=NULL&&pre->next->next!=NULL&&j<i-1)
/*02_07判断是否找到前驱结点*/
{
pre = pre->next;
j++;
}
if (j!=i-1)/*02_07如果没有找到要删除的节点位置，说明删除有误*/
{
cout << "02_07删除位置有误" << endl;
return 0;
}
/*02_07指针p指向单链表中的第i个结点，并将该结点的数据域赋值给e*/
p = pre->next;
*e = p->data;
/*02_07将前驱结点的指针域指向要删除结点的下一个结点，也就是将p指向的结点与单链表断开*/
pre->next = p->next;
free(p); /*02_07释放p指向的结点*/
return 1;
}【求表长的操作】
/*02_08求表长的操作*/
int ListLength(LinkList head)
{
ListNode *p;
int count = 0;
p = head;
while (p->next!=NULL)
{
p = p->next;
count++;
}
return count;
}【销毁链表操作】
/*02_09销毁链表操作*/
void DestoryList(LinkList head)
{
ListNode *p, *q;
p = head;
while (p!=NULL)
{
q = p;
p = p->next;
free(q);
}
}