用链表实现线性表的各种操作(C语言)

#include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
//定义节点结构体
typedef struct Node
{
  int data;//数据域
  struct Node * pNext;//指针域
}NODE,* PNODE;
//函数声明
PNODE create_list(void); //创建链表
void traverse_list(PNODE pHead);//遍历链表
bool is_empty(PNODE pHead);//判断链表是否为空
int length_list(PNODE);//计算链表的长度
bool insert_list(PNODE, int, int);//插入数据
bool delete_list(PNODE, int, int *);//删除数据
void sort_list(PNODE); //链表排序

int main(void)
{
  
   PNODE pHead=create_list();
   traverse_list(pHead);
  // printf("%d\n",length_list(pHead));
   //insert_list(pHead,3 ,100);
   //traverse_list(pHead);
  // int val;
  // delete_list(pHead,2,&val);
   //traverse_list(pHead);
   sort_list(pHead);
	traverse_list(pHead);
   return 0;
   
}
//创建链表函数实现
PNODE create_list(void)
{
   int len;//存放有效节点的个数
   int i;
   int val ; //临时存放用回输入的节点的值
   //创建头结点
   PNODE pHead =(PNODE)malloc(sizeof(NODE));
   if(NULL==pHead)
   {
      printf("分配内存失败,程序终止\n");
	  exit(-1);
   }
   PNODE pTail = pHead;//定义一个临时指针始终指向最后一个节点，辅助指针思想方法
   pTail->pNext=NULL; 
   printf("请输入要生成的节点的个数：len=");
   scanf("%d",&len);
   for(i=0;i<len;i++)
   {
      printf("请输入第%d个节点的值：",i+1);
	  scanf("%d",&val);
	  PNODE pNew=(PNODE)malloc(sizeof(NODE));
	  if(NULL==pNew)
	  {
	     printf("分配失败，程序终止\n");
		 exit(-1);
	  }
	  pNew->data=val;
	  pTail->pNext=pNew;
	  pNew->pNext=NULL;
	  pTail=pNew;//注意点 pTail要移动
   }
  return pHead;
}
//遍历链表
void traverse_list(PNODE pHead)
{
	PNODE p = pHead->pNext;
	while (NULL != p)
	{
		printf("%d  ", p->data);
		p = p->pNext;
	}
	printf("\n");
	
	return;
}
bool is_empty(PNODE pHead)//判断链表是否为空
{
  if(NULL==pHead->pNext)
  
     return true;
  
  else 
  
    return false;
   
}
//计算链表的长度
int length_list(PNODE pHead)
{
   int i=0;
   PNODE p=pHead->pNext;
   while(NULL!=p)
   {
     i++;
	 p=p->pNext;
   }
   return i;
}
//插入数据
bool insert_list(PNODE pHead , int pos , int val)
{
   PNODE p=pHead;
   if(pos>0&&pos<=(length_list(pHead)+1))
   {
       for(	int i=0;i<pos-1;i++)
	   {
	     p=p->pNext;
	   }
       PNODE pNew = (PNODE)malloc(sizeof(NODE));
       pNew->data=val;
       PNODE temp=p->pNext;
       p->pNext=pNew;
       pNew->pNext=temp;
	   return true;
   }
   else
   {
	   return false;
   }
}
//删除数据
bool delete_list(PNODE pHead,int pos ,int *pVal)
{
   PNODE p=pHead;
   if(pos>0&&pos<=(length_list(pHead)))
   {
       for(	int i=1;i<pos;i++)
	   {
	     p=p->pNext;
	   }
       PNODE temp=p->pNext->pNext;
       *pVal=p->pNext->data;
	   p->pNext=temp;
	   return true;
   }
   else
   {
	   return false;
   }
}
//链表排序
void sort_list(PNODE pHead)
{
	PNODE p=pHead;
   for(p=pHead->pNext;p!=NULL;p=p->pNext)
   {
	for(PNODE q=p->pNext;q!=NULL;q=q->pNext)
	{
		if(q->data<p->data)
		{
		  int temp=p->data;
		  p->data=q->data;
		  q->data=temp;
		}
	   
	}
   }
   
}

排序还可以用这种算法

 

void sort_list(PNODE pHead)
{
	int i, j, t;
	int len = length_list(pHead);
	PNODE p, q;
	
	for (i=0,p=pHead->pNext; i<len-1; ++i,p=p->pNext)
	{
		for (j=i+1,q=p->pNext; j<len; ++j,q=q->pNext)
		{
			if (p->data > q->data)  //类似于数组中的:  a[i] > a[j]
			{
				t = p->data;//类似于数组中的:  t = a[i];
				p->data = q->data; //类似于数组中的:  a[i] = a[j];
				q->data = t; //类似于数组中的:  a[j] = t;
			}
		}
	}
	return;
}

数据插入还可用这种算法

 

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));
	if (NULL == pNew)
	{
		printf("动态分配内存失败!\n");
		exit(-1);
	}
	pNew->data = val;
	PNODE q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;
	return true;
}

数据删除还可用这种算法

 

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节点后面的结点
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;
	
	return true;
}