数据结构c(单链表的创建以及插入删除等操作)

数据结构 链表（c）

• 数据结构 链表（c）

什么是链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表主要分有单链表，双向链表还有循环链表
单链表：链表中的元素的指向只能指向链表中的下一个元素或者为空，元素之间不能相互指向。也就是一种线性链表。
双向链表：一个有序的结点序列，与单链表不同的是，除了数据域data,每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有这两种指针，即pleft和pright。pleft指针指向左边结点，pright指针指向右边结点。
循环链表：在以上链表的基础上最后一个节点存放了第一个节点的地址，使其指向第一个节点完成循环。

单链表的创建及操作

定义结构体

定义一个结构体，在这里说明一下typedef函数的作用是使NODE类型为struct Node
PNODE 类型为struct Node *
typedef struct Node
{
	int data;
	struct Node*pNext;
}NODE,*PNODE;

创建链表并返回头节点，这里创建的链表的头节点没有数据域，以便对链表的插入，删除，遍历等操作。插入方法为尾插法。

注意：循环插入结束后一定要将链表尾节点的指针域指为空（NULL）

PNODE create_list()
{
	int len;
	int val; //临时存放用户输入节点的值 
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if(NULL == pHead)
	{
		printf("分配失败，程序终止");
		exit(-1);	
	}
	PNODE pTail = pHead;
	pTail->pNext = NULL;  
	printf("请输入链表结点个数：len = ");
	scanf("%d",&len);
	for(int i=0;i<len;i++)
	{
		printf("请输入第%d个节点的值:",i+1);
		scanf("%d",&val);
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
	 	pNew->data = val;
		pTail->pNext = pNew;
		pTail = pNew; 		
	}  
		pTail->pNext  =NULL;
	return pHead;
} 

遍历链表
注意：由于头节点没有数据域，所以循环要从phead->pnext开始

void traverse_list(PNODE pHead)
{
	PNODE p = pHead->pNext;
	
	while(p!=NULL)
	{
		printf("%d ",p->data);
		p = p->pNext; 
	}
	printf("\n");
	return;	
} 

是否为空链表

bool is_empty(PNODE pHead)
{
	if(pHead->pNext==NULL)
		return true;
	else
		return false;
}

求链表的长度

int length_list(PNODE pHead)
{
	int num = 0;
	PNODE p = pHead->pNext;
	while(p!=NULL)
	{
		p = p->pNext;
		num++;
	 } 
	 return num;
}

链表的插入
插入：

这里与两整形变量值互换值原理类似，需要借助第三个变量
t = a;
a =b;
b =t;

bool insert_list(PNODE pHead,int pos,int val)
{
	int i=0;
	PNODE p = pHead;
	while(NULL!=p&&i<pos-1)
	{
		p = p->pNext;
		i++;
	}
	if(i>pos-1||NULL==p)
		return false;
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	pNew->data = val;
	PNODE q = p->pNext;
	p->pNext=pNew;
	pNew->pNext =q;
	return true;
}

删除链表指定位置的元素，pval可返回删除元素的值

一定要注意这里不能直接p->pNext = p->pNext->pNext;，一定要将要删除的节点内存释放，否则会内存泄漏

bool delete_list(PNODE pHead,int pos,int*pVal)
{
		int i=0;
	PNODE p = pHead;
	while(NULL!=p->pNext&&i<pos-1)
	{
		p = p->pNext;
		i++;
	}
	if(i>pos-1||NULL==p->pNext)
		return false;
	PNODE q = p->pNext;
	*pVal = q->data;
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;
	
	return true;
}