链表的一些基本操作(C语言版)

链表的算法实现

链表的正向建立

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef struct pNODE
{
	int data;
	struct pNODE * pnext;
}NODE,*PNODE;//建立结构体，NODE等价于struct，PNODE等价于struct pNODE *

PNODE create_list(void)
{
	int len,val;
	printf("请输入建立链表元素个数：");
	scanf("%d",&len);
	PNODE phead = (PNODE)malloc(sizeof(NODE));
	if(phead == NULL)
	{
		printf("分配失败！");
		exit(-1);
	}//检验链表的头结点是否生成，如果程序出现错误，则退出程序
	PNODE ptail = phead;//建立一个形式上的指针指向头结点

	for(int i = 0;i < len;++i)
	{
		printf("请输入第%d个元素：",i+1);
		scanf("%d",&val);
		PNODE pnew = (PNODE)malloc(sizeof(NODE));//动态分配一个新节点的地址
		if(pnew == NULL)
	{
		printf("分配失败！");
		exit(-1);
	}//检验链表的新结点是否生成，如果程序出现错误，则退出程序
		pnew->data = val;
		ptail->pnext = pnew;
		pnew->pnext = NULL;
		ptail = pnew;//正向建立链表
	}
	return phead;
}//链表的正向建立

链表的逆向建立

PNODE fancreate_list(void)
{
	int len,val;
	printf("请输入建立链表元素个数：");
	scanf("%d",&len);
	PNODE phead = (PNODE)malloc(sizeof(NODE));
	phead->pnext = NULL;
	if(phead == NULL)
	{
		printf("分配失败！");
		exit(-1);
	}//检验链表的头结点是否生成，如果程序出现错误，则退出程序

	for(int i = len;i > 0;--i)
	{
		printf("请输入第%d个元素：",len - i+1);
		scanf("%d",&val);
		PNODE pnew = (PNODE)malloc(sizeof(NODE));
		pnew->data = val;
		pnew->pnext = phead->pnext;
		phead->pnext = pnew;//逆向建立链表
	}
	return phead;
}

链表的遍历

void trasever_list(PNODE phead)
{
	PNODE p = phead->pnext;//定义新指针指向头结点的下一个结点
	while(p != NULL)
	{
		printf(" %d",p->data);
		p = p->pnext;
	}//在每个结点的指针域不为空的时候，输出数值，指针指向下一个有效结点
	printf("\n");
}

链表常用的算法

插入算法

bool insert_list(PNODE phead,int pos,int val)
{
	int j = 0;
	PNODE p = phead;

	while(NULL != p && j < pos-1)
	{
		p = p->pnext;
		j++;
	}

	if(NULL == p || j > pos-1)
		return false;

	PNODE q = p->pnext;
	PNODE pnew = (PNODE)malloc(sizeof(NODE));
	pnew->data = val;
	p->pnext = pnew;
	pnew->pnext = q;
	return true;
}//在第pos个元素前面插入某一个需要插入的元素

删除算法

bool delete_list(PNODE phead,int pos,int * pval)
{
	int j = 0;
	PNODE p = phead;

	while(NULL != p && j < pos-1)
	{
		p = p->pnext;
		j++;
	}
	if(NULL == p || j > pos-1)
	{
		return false;
	}

	PNODE q = p->pnext;
	*pval = q->data;
	p->pnext = p->pnext->pnext;
	free(q);
	return true;
}//删除第pos个元素

合并两个有序单链表

void merge_list(PNODE la,PNODE lb,PNODE lc)
{
	PNODE pa = la->pnext;
	PNODE pb = lb->pnext;
	PNODE pc;
	lc = pc = la;
	while(pa && pb)
	{
		if(pa->data <= pb->data)
		{
			pc->pnext = pa;
			pc = pa;
			pa = pa->pnext;
		}
		else
		{
			pc->pnext = pb;
			pc = pb;
			pb = pb->pnext;
		}
	}
	if(pa)
	{
		pc->pnext = pa;
	}
	else
	{
		pc->pnext = pb;
	}
	free(lb);
}

主函数实现

int pval = 0;
	PNODE phead = NULL;
	phead = create_list();
	//insert_list(phead,2,69);
	//trasever_list(phead);
	delete_list(phead,4,&pval);
	//phead = fancreate_list();
	trasever_list(phead);//需要使用哪一个函数就讲其他的注释掉
	return 0;