数据结构-链式存储

数据结构

一.数据结构的定义：

二.数据与数据之间的关系:

<1>数据的逻辑结构(数据元素与元素之间的关系):

集合:关系平等

线性结构:元素之间一对一的关系(表,队列,栈...)

树形结构:元素之间一对多的关系

图形结构:元素之间多对多的关系(网状结构)

<2>数据的物理结构(数据的逻辑结构在计算机内存中的存储形式):

顺序存储:采用一段连续的内存空间保存元素

链式存储:采用一组非连续的内存空间保存元素

索引存储:通过关键字构建索引表,通过索引表找到数据存储的位置

散列存储:将数据元素的存储位置与关键码之间建立确定的对应关系从而实现查找的存储方式

链式存储:

链表:

//以下函数中交互的协议
/*存储数据的类型*/
typedef int DataType;
/*节点类型*/
typedef struct node
{	
	DataType Data;		//数据域
	struct node * pNext;	//指针域
}LinkNode;
/*标签类型*/
typedef struct list
{
	LinkNode * pHead;	//头节点指针
	int clen;		//节点个数
}LinkList;

(1).创建链表

LinkList * creatLinkList()
{
	LinkList * pList = malloc(sizeof(LinkList))
	if(NULL == pList)
	{
		perror("fail to malloc");
		return NULL;
	}
	pList->pHead = NULL;
	pList->clen = 0;
	return pList;
}

(2).往链表里插入节点
插入节点可分为头插,尾插和指定位置插入,以下举例为头插

int insertHeadLinkList(LinkList * pList,DataType Data)//pList为链表头,Data为要存入的数据
{
	LinkNode *pInsertNode = malloc(sizeof(LinkNode));
	if(NULL == pInsertNode)
	{
		perror("fail to malloc");
		return -1;
	}
	pInsertNode->Data = Data;
	pInsertNode->pNext = pList->pHead;
	pList->pHead = pInsertNode;
	pList->clen++;
	return 0;
}

(3).删除链表的节点
删除节点可分为头删,尾删和指定删除,以下举例为头删

int deleteHeadLinkList(LinkList * pList)
{
	if(pList->pHead == NULL)
	{
		return 0;
	}
	LinkNode * pTmpNode = pList->pHead;
	pList->pHead = pTmpNode->pNext;
	free(pTmpNode);
	pList->clen--;
	return 0;
}

(4).查找链表的某个节点

LinkNode *findNodeLinkList(LinkList * pList,DataType data)//pList链表头,data查找节点的数据
{
	LinkNode * pTmpNode = pList->pHead;
	while(pTmpNode != NULL)
	{
		if(pTmpNode -> Data == data)
		{
			return pTmpNode;
		}
		pTmpNode = pTmpNode->pNext;
	}
	return NULL;
} 

(5).销毁链表;

void destroyLinkList(LinkList **ppList)
{
	while((*ppList)->pHead != NULL)
	{
		deleteHeadLinkList(*ppList);//该函数为上面的头删函数
	}
	free(*ppList);
	*ppList = NULL;
	return;
}

注:若有疑问可在讨论区询问或者私信!