写本文前想说明下，本文的基本原理和代码构造来源于我的编程语言大师——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);
#endif
cutil_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
- 微信扫码赞助
-
- 支付宝赞助
-
