共计 4685 个字符，预计需要花费 12 分钟才能阅读完成。
写本文前想说明下，本文的基本原理和代码构造来源于我的编程语言大师 ——DelphiTang 先生，关于他，这里不再多说，感兴趣的朋友可以先去看下文中给出的链接，去获取部分免费课程。后面代码全文采用的是凶牙利命名法，关于代码变量及函数的命名，这里不再多说，有兴趣的朋友可以去百度。
在开始本文之前，先打个广告，大家可以去下面地址获取 DelphiTang 先生的整套课程资料。
http://item.taobao.com/item.htm?_u=i468inu54ad&id=37050555208
以下摘自 DelphiTang 先生的另一学生笔记
用一组地址任意的存储单元存放线性表中的数据元素，以元素(数据元素的映象) + 指针(指示后继元素存储位置)= 结点(表示数据元素 或 数据元素的映象)，以 “ 结点的序列 ” 表示线性表称作线性链表（单链表）。
有几个基本概念需要掌握，如下：1. 表头结点
链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息。
2. 数据结点
链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息
3. 尾结点
链表中的最后一个数据结点，其下一元素指针为空，表示无后继
这里主要介绍线性表的常用操作：
l 创建线性表
l 销毁线性表
l 清空线性表
l 将表中元素倒置
l 表元素插入
l 表元素删除
l 获取表中某个位置的元素
l 获取表长度
这里着重说下插入操作? 删除操作和倒置操作：
插入操作：
如图
插入元素方法：
首先判断线性表? 插入位置是否合法由表头开始通过 next 指针移动 pos 次后，当前元素的 next 指针即指向要插入的位置
把当前元素 (current) 的 next 指针包含的地址赋给新元素 (node) 的 next 指针
把新元素 (node) 的地址赋给当前元素 (current) 的 next 指针
最后把线性表长度加 1删除操作：
如图
删除元素方法：
首先判断线性表? 删除位置是否合法
获取第 pos 个元素
将第 pos 个元素的 next 指针保存的地址赋给第 pos 个元素前一个元素的 next 指针
最后把表长度减 1倒置操作：
如图
倒置元素方法：
把头结点指向的首元素的 next 指针赋为 NULL
然后把首元素以后的结点依次每个插入到头结点和首元素中间
下面我将用三个文件来介绍通用单链表具体的 C 语言实现：
cutil_list.h 文件：
#ifndef __CUTIL_LIST_H__
#define __CUTIL_LIST_H__
#include <stdio.h>
#include <stdlib.h>
/* 链表类型封装 */
typedef void ListType;
typedef void *pListType;
/* 链表长度类型封装 */
typedef unsigned int ListLenType;
/* 链表节点封装 */
typedef struct _ListNode ListNode;
typedef struct _ListNode *pListNode;
struct _ListNode
{pListNode Next;};
/* 链表结构体封装，包含节点和长度两个元素 */
typedef struct _StruList StruList;
typedef struct _StruList *pStruList;
struct _StruList
{
ListNode Header; //Node
ListLenType Length; //Length
};
/* 创建链表 */
pListType Cutil_List_Create();
/* 获取元素中的值 */
pListNode Cutil_List_Get(pListType pList, int nPos);
/* 销毁链表 */
void Cutil_List_Destroy(pListType pList);
/* 清空链表 */
void Cutil_List_Clear(pListType pList);
/* 获取链表长度 */
ListLenType Cutil_List_Length(pListType pList);
/* 插入节点 */
int Cutil_List_Insert(pListType pList, pListNode pNode, int nPos);
/* 删除节点，实际上是弹出节点 */
pListNode Cutil_List_Delete(pListType pList, int nPos);
#endifcutil_list.c 文件：
#include "cutil_list.h"
pListType Cutil_List_Create() //O(1)
{pStruList Ret = (pStruList)malloc(sizeof(StruList));
if(Ret)
{
Ret->Length = 0;
Ret->Header.Next = NULL;
}
return Ret;
}
pListNode Cutil_List_Get(pListType pList, int nPos) //O(n)
{pStruList pSList = (pStruList)pList;
pListType Ret = NULL;
int i = 0;
if( (pSList != NULL) && (0 <= nPos) && (nPos < pSList->Length) )
{pListNode pCurrent = (pListNode)pSList;
for(i=0;i<nPos;i++)
{pCurrent = pCurrent->Next;}
/* 有头结点，向后再移一个节点 */
Ret = pCurrent->Next;
}
return Ret;
}
void Cutil_List_Destroy(pListType pList) //O(1)
{free(pList);
}
void Cutil_List_Clear(pListType pList)
{pStruList pSList = (pStruList)pList;
if(pSList != NULL)
{
pSList->Length = 0;
pSList->Header.Next = NULL;
}
}
ListLenType Cutil_List_Length(pListType pList) //O(1)
{
ListLenType Ret = -1;
pStruList pSList = (pStruList)pList;
if(pSList != NULL)
{Ret = pSList->Length;}
return Ret;
}
/* 插入操作可类似于链表头插法，链表尾插法，链表节点中任意插入 */
int Cutil_List_Insert(pListType pList, pListNode pNode, int nPos) // 最坏情况是 O(n)
{pStruList pSList = (pStruList)pList;
int nRet = (pSList != NULL) && (0 <= nPos) && (pNode != NULL);
int i = 0;
if(nRet)
{pListNode pCurrent = (pListNode)pSList;
for(i=0;(i<nPos) && (pCurrent->Next != NULL); i++)
{pCurrent = pCurrent->Next;}
pNode->Next = pCurrent->Next;
pCurrent->Next = pNode;
pSList->Length++;
}
return nRet;
}
pListNode Cutil_List_Delete(pListType pList, int nPos) //O(n)
{pStruList pSList = (pStruList)pList;
pListNode pRet = NULL;
int i = 0;
if((pSList != NULL) && (0<=nPos) && (nPos < pSList->Length))
{pListNode pCurrent = (pListNode)pSList;
for(i=0;i<nPos;i++)
{pCurrent = pCurrent->Next;}
pRet = pCurrent->Next;
pCurrent->Next = pRet->Next;
pSList->Length--;
}
return pRet;
}
main.c 用于介绍函数调用示例：
#include "cutil_list.h"
typedef struct _Text
{
pListType Header;
int nValue;
}Text;
int main(int argc,char **argv)
{
pListType pHead = NULL;
Text *pTv = NULL;
Text t1, t2, t3;
pHead = Cutil_List_Create();
t1.nValue = 1;
t2.nValue = 2;
/* 由于封装了节点类型细节，所以插入的时候需要做类型转换
此处 pos 位置为 0，相当于链表头插法，算法复杂度为 O(1)
*/
Cutil_List_Insert(pHead, (pListNode)&t1, 0);
Cutil_List_Insert(pHead, (pListNode)&t2, 0);
/* 注意观察输出结果 */
pTv = (Text *)Cutil_List_Get(pHead,1);
printf("Get:%d\n",pTv->nValue);
pTv = (Text *)Cutil_List_Get(pHead,0);
printf("Get:%d\n",pTv->nValue);
while(Cutil_List_Length(pHead) > 0)
{pTv = (Text *)Cutil_List_Delete(pHead,0);
printf("Delete:%d\n",pTv->nValue);
}
Cutil_List_Destroy(pHead);
return 0;
}说明：转载请注明出处。www.guoziweb.com
