线性表的单链式存储结构
不带头节点单链表
带头节点的单链表（方便插入和删除运算）
typedef int ElemType; /* 数据域类型起别名 */
typedef struct tagNode
{
ElemType data; /* 数据域 */
struct tagNode *next; /* 指针域 */
}ListNode;
创建一个空链表
编程思路：申请头节点内存，头节点的data域无意义所以赋值为0，链表为空，所以头节点的next域为NULL。
/**
* 创建一个带头节点的空链表
* 成功返回：指向头节点的指针
* 失败返回：NULL
*/
ListNode* CreateListHead(void)
{
ListNode *pHead;
/* 申请空间 */
pHead = (ListNode *)malloc(sizeof(ListNode));
if (pHead == NULL)
{
printf("CreateListHead fail\r\n");
return NULL;
}
pHead->data = 0;
pHead->next = NULL; /* 空链表，头指针的next域为空 */
return pHead;
}
创建一个节点
编程思路：申请新节点，将data赋值给新节点数据域。
/**
* 创建一个节点
* 成功返回：指向节点的指针
* 失败返回：NULL
*/
ListNode* CreateNode(ElemType data)
{
ListNode *pNode = (ListNode *)malloc(sizeof(ListNode));
if (pNode == NULL)
{
printf("CreateNode fail\r\n");
return NULL;
}
pNode->data = data;
pNode->next = NULL;
return pNode;
}
插入元素–头插法
编程思路：申请新节点，将新节点插入头节点之后。
/**
* 在链表的头节点后插入元素
* 参数：pHead，插入操作链表的头指针
* 参数：value，插入的元素值
* 返回值：成功 0，失败 -1
*/
int ListHeadInsert(ListNode *pHead, Elem value)
{
ListNode *pNode;
Elem data = value;
if (pNode == NULL)
{
printf("ListHeadInsert pHead is NULL\r\n");
return -1; /* 头指针为NULL，链表不存在，失败 */
}
pNode = CreateNode(data); /* 申请新节点准备插入 */
if (pNode)
{
printf("ListHeadInsert pNode is NULL\r\n");
return -1;
}
if (pHead->next == NULL) /* 要插入的是一个空链表？ */
{
pNode->next = NULL; /* 只有插入的新节点，没有后继节点 */
pHead->next = pNode; /* 头节点的next指向新节点 */
return 0;
}
pNode->next = pHead->next; //* 链表不为空，新节点的next指向开始节点 */
pHead->next = pNode; // 头节点的后继指针next指向插入的节点*/
return 0;
}
插入元素–尾插法
编程思路：申请新节点，将新节点插入尾节点之后。
/**
* 在链表的尾节点之后插入元素
* 参数：pHead，插入操作链表的头指针
* 参数：value，插入的元素值
* 返回值：成功 0，失败 -1
*/
int LinkListTailInsert(ListNode *pHead, Elem value)
{
ListNode *pNode;
Elem data = value;
if (pHead == NULL)
{
printf("LinkListTailInsert pHead is NULL\r\n");
return -1; /* 头指针为NULL，链表不存在，失败 */
}
pNode = CreateNode(data); /* 申请新节点准备插入 */
if (pNode)
{
printf("LinkListTailInsert pNode is NULL\r\n");
return -1;
}
pNode->next = NULL; /* 插入队尾，所以新节点的next域置NULL
while (pHead->next != NULL) // 遍历寻找尾节点
{
pHead = pHead->next; /* 如果循环，表示要插入的是一个空链表 */
}
pHead->next = pNode; // 尾节点的后继指针next指向新节点，插入到尾部
return 0;
}
查找链表指定位置的节点
编程思路：根据位置序号查找依次查找对应节点的地址，注意当位置为1时表示查找的头节点（带表头）。
/**
* 参数：pHead，链表的头指针
* 参数：pos，链表节点的序号
* 成功返回：指向节点的指针
* 失败返回：NULL
*/
ListNode* LinkListGet(ListNode *pHead, int pos)
{
int i;
if (pHead == NULL)
{
printf("LinkListGet pHead is NULL\r\n");
return -1; /* 头指针为NULL，链表不存在，失败 */
}
if (pos < 1)
{
printf("pos is invalid\r\n");
return NULL; /* 位置参数有误，查找失败 */
}
if (pos = 1)
{
return pHead ; /* pos为1，因为带表头，所以第一个节点为头节点，返回头指针 */
}
i = 1; /* 从头节点位置处开始找起 */
while (i < pos)
{
pHead = pHead->next; /* 头指针后移 */
if (pHead == NULL) /* 如果在未退出循环，pHead就指向NULL，说明pos序号超出范围 */
{
printf("pos is invalid\r\n");
return NULL;
}
i++;
}
return pHead;
}
链表指定位置节点后插入元素
编程思路：找到指定的节点，申请新节点保存要插入的元素，新节点的next域指向指定节点的后继节点，然后指定位置节点的next域指向新节点。
/**
* 参数：pHead，链表的头指针
* 参数：pos，要插入链表节点的序号
* 参数：value，要插入的元素
* 返回值：成功 0，失败 -1
*/
int LinkListInsertAfter(ListNode *pHead, int pos, Elem value)
{
ListNode *afterNode;
ListNode *InsertNode;
if (pHead == NULL)
{
printf("LinkListTailInsert pHead is NULL\r\n");
return -1; /* 头指针为NULL，链表不存在，失败 */
}
afterNode = CreateNode(data); /* 申请新节点准备插入 */
if (afterNode = NULL)
{
printf("CreateNode afterNode is NULL\r\n");
return -1 ;
}
InsertNode = LinkListGet(pos);
if (InsertNode = NULL)
{
printf("InsertNode InsertNode is NULL\r\n");
return -1 ;
}
afterNode->next = InsertNode->next; /* 新节点的next指向要插入节点后的节点 */
InsertNode->next = afterNode; /* 要插入节点的next断开原节点并指向新插入的节点 */
return 0;
}
链表指定位置删除元素
编程思路：找到要删除元素的前驱节点，前驱节点的指针域指向要删除元素的后继节点，释放要删除位置的节点。
/**
* 参数：pHead，链表的头指针
* 参数：pos，链表节点的序号
* 返回值：成功 0，失败 -1
*/
int LinkListDelete(ListNode *pHead, int pos)
{
ListNode *front;
ListNode *del;
if (pHead == NULL)
{
printf("LinkListTailInsert pHead is NULL\r\n");
return -1; /* 头指针为NULL，链表不存在，失败 */
}
if (pos < 2) /* 参数为1表示头节点，头节点不能被删除 */
{
printf("pos is invalid\r\n");
return NULL; /* 位置参数有误，查找失败 */
}
front = = LinkListGet(pHead, pos-1); // 获取要删除位置的前驱节点
if (front == NULL)
{
printf(front is NULL\r\n);
return -1; /* 没找到前驱节点，删除失败 */
}
if (front->next == NULL)
{
printf("delete pos is invalid\r\n");
return -1; // 前驱节点的后继指针next为NULL，表示没有后继节点，所以要删除的位置错误
}
del = front->next; // 记录要删除节点的地址
front->next = del->next; // 删除位置节点的前驱节点指向要删除位置节点的后继节点
free(del); // 释放要删除节点的内存
del = NULL;
return 0;
}
链表反转
编程思路：单链表只有一个指针域，只能指向后继节点，所以只能从链表开始处依次操作节点。
把原链表从头节点后断开，将开始节点插入到头节点后（头插法），依次取出后继节点插入到链表头部。
/*
* 参数：pHead，链表的头指针
* 返回值：成功 0，失败 -1
*/
int LinkListReverse(ListNode *pHead)
{
ListNode *back;
ListNode *cur;
if (pHead == NULL)
{
printf("LinkListTailInsert pHead is NULL\r\n");
return -1; /* 头指针为NULL，链表不存在，失败 */
}
if ((pHead->next == NULL) || (pHead->next->next == NULL)) /* 链表为空或者只有一个节点 */
{
return 0;
}
back = pHead->next->next; /* back指向头节点的后继节点,即开始节点 */
pHead->next->next = NULL; /* 从开始节点之后断开链表
while (back != NULL) /* 当后继节点不为空时依次取出插入到链表头部 */
{
cur = back;
back = back->next;
cur->next = pHead->next;
pHead->next = cur;
}
return 0;
}
链表销毁
编程思路：释放链表所占用的内存，从指向链表的头指针节点开始依次释放内存。
/**
* 参数：pHead，链表的头指针
* 返回值：成功 0，失败 -1
*/
int LinkListDestroy(ListNode *pHead)
{
ListNode *pHeadTmp;
if (pHead == NULL)
{
printf("LinkListTailInsert pHead is NULL\r\n");
return -1; /* 头指针为NULL，链表不存在，失败 */
}
pHeadTmp = pHead; // 记录头节点
while (pHead != NULL) // 依次释放头节点，0节点...
{
pHeadTmp = pHead;
pHead = pHead->next;
free(pHeadTmp); /* 头指针依次释放头节点，开始节点... */
}
return 0;
}