单链表的几类操作介绍(头结点没有数据)

1.定义一个单链表的结构体

typedef struct _Node
{
  int data;
  struct _Node *next; 
}node;

2.创建一个链表，这里分为头插法和尾插法

node *CreatNode_Head(int n)
{
   int i=0;
   node *head,*p;
   head=(node*)malloc(sizeof(node));
   if(head==NULL)
        return NULL;
   head->next=NULL;
   srand(time(0));
   for(int i=0;i<n;++i)
   {
   	  p=(node*)malloc(sizeof(node));
   	  p->data=rand()%100+1;
	  printf("p->data:%d\t",p->data);
   	  p->next=head->next;
   	  head->next=p;
   }
   return head;
}
node *CreatNode_Tail(int n)
{
   int i=0;
   node *head,*p,*q;
   head=(node*)malloc(sizeof(node));
   if(head==NULL)
        return NULL;
   head->next=NULL;
   q=head;
   srand(time(0));
   for(int i=0;i<n;++i)
   {
   	  p=(node*)malloc(sizeof(node));
   	  p->data=rand()%100+1;
   	  p->next=NULL;
	  printf("p->data:%d\t",p->data);
   	  q->next=p;
   	  q=p;
   }
   return head;
}

3.获取链表的长度

由于头结点没有数据，所以循环从头结点->next开始遍历，直到遇到NULL为止。最后返回链表的长度

int length(node *p)
{
	if(p==NULL)
	   return -1;
    int len=0;
    while(p->next!=NULL)
    {
       len++;
       p=p->next;
    }
    return len;
}

4.打印链表中存储的数据

这个其实和获取链表的长度一样的道理，都是需要遍历链表，但是在遍历前需要判断链表是否为空，若为空，立即返回，不为空开始遍历，直到遇到NULL为止。

void printnode(node *p)
{
  if(p==NULL)
     return;
  node *q;
  if(p->next==NULL)
  {
      printf("the node is empty:\n");
      return;
  }
  else
  {
      q=p->next;
      while(q!=NULL)
      {
          printf("%d\t",q->data);
          q=q->next; 
     }
  }
  printf("\n"); 
}

5.链表的定位

   链表的定位返回值分两种，一种可以返回定位到某个节点的数据，另一种是返回以此节点的地址

   两个函数传入的参数都是一样，一个参数是需要操作的链表，另一个参数是节点在链表中的位置

int SearchNode(node *head,int pos)
{
    if(head==NULL)
        return -1;
   if(pos<=0)
   {
        printf("the pos can not smaller than 0\n");
        return -1;
   }
   else if(head->next==NULL)
   {
      printf("the node is empty\n");
      return -1;
   }
   else if(pos>length(head))
   {
      printf("the pos over the length of the node\n");
      return -1;
   }
   else
   {
      while(pos--)
      {
        head=head->next;
      }
   }
   return head->data; 
}
node * SearchNode1(node *head,int pos)
{
   if(pos<0)
   {
        printf("the pos can not smaller than 0\n");
        return NULL;
   }
   else if(head->next==NULL)
   {
      printf("the node is empty\n");
      return NULL;
   }
   else if(pos>length(head))
   {
      printf("the pos over the length of the node\n");
      return NULL;
   }
   else
   {
      while(pos--)
      {
        head=head->next;
      }
   }
   return head; 
}

6.删除链表中的节点

   先找到要删除节点的前一个节点，如果已经到了尾节点，则不能删除

bool DeleteNode(node *head,int pos,int &data)
{
   if(head==NULL)
     return false;
   node *item=NULL;
   node *p=head;
   node *q=SearchNode1(head,pos-1);
   if((!q)||(!q->next))
   {
   	   printf("delete failed:\n");
   	   return false;
   }
   item=q->next;
   data=item->data;
   q->next=item->next;
   free(item);
   item=NULL;
   printf("Delete success:\n");
   return true;
}

7.插入节点

先找到要插入节点的前一个节点

bool InsertNode(node *head,int pos,int data)
{
   if(head==NULL)
     return false;
   node *item=NULL;
   node *p=head;
   node *q=SearchNode1(head,pos-1);
   if(!q)
   {
   	   printf("Insert failed:\n");
   	   return false;
   }
   item=(node*)malloc(sizeof(node));
   item->data=data;
   item->next=q->next;
   q->next=item;
   printf("Insert success:\n");
   return true;
}

8.逆置操作

void ReverseNode(node *head)
{
	if(head==NULL)
	   return ;
    if(head->next==NULL)
       return ; 
	node *p,*q,*r;
	p=head->next;
	q=p->next;
	p->next=NULL;
	while(q!=NULL)
	{
		r=q->next;
		q->next=p;
		p=q;
		q=r;
	}
	head->next=p;
}

完整程序如下：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
typedef struct _Node
{
  int data;
  struct _Node *next; 
}node;
node *CreatNode_Head(int n)
{
   int i=0;
   node *head,*p;
   head=(node*)malloc(sizeof(node));
   if(head==NULL)
        return NULL;
   head->next=NULL;
   srand(time(0));
   for(int i=0;i<n;++i)
   {
   	  p=(node*)malloc(sizeof(node));
   	  p->data=rand()%100+1;
	  printf("p->data:%d\t",p->data);
   	  p->next=head->next;
   	  head->next=p;
   }
   return head;
}
node *CreatNode_Tail(int n)
{
   int i=0;
   node *head,*p,*q;
   head=(node*)malloc(sizeof(node));
   if(head==NULL)
        return NULL;
   head->next=NULL;
   q=head;
   srand(time(0));
   for(int i=0;i<n;++i)
   {
   	  p=(node*)malloc(sizeof(node));
   	  p->data=rand()%100+1;
   	  p->next=NULL;
	  printf("p->data:%d\t",p->data);
   	  q->next=p;
   	  q=p;
   }
   return head;
}
int length(node *p)
{
	if(p==NULL)
	   return -1;
    int len=0;
    while(p->next!=NULL)
    {
       len++;
       p=p->next;
    }
    return len;
}
void printnode(node *p)
{
  if(p==NULL)
     return;
  node *q;
  if(p->next==NULL)
  {
      printf("the node is empty:\n");
      return;
  }
  else
  {
      q=p->next;
      while(q!=NULL)
      {
          printf("%d\t",q->data);
          q=q->next; 
     }
  }
  printf("\n"); 
}

int SearchNode(node *head,int pos)
{
    if(head==NULL)
        return -1;
   if(pos<=0)
   {
        printf("the pos can not smaller than 0\n");
        return -1;
   }
   else if(head->next==NULL)
   {
      printf("the node is empty\n");
      return -1;
   }
   else if(pos>length(head))
   {
      printf("the pos over the length of the node\n");
      return -1;
   }
   else
   {
      while(pos--)
      {
        head=head->next;
      }
   }
   return head->data; 
}
node * SearchNode1(node *head,int pos)
{
   if(pos<0)
   {
        printf("the pos can not smaller than 0\n");
        return NULL;
   }
   else if(head->next==NULL)
   {
      printf("the node is empty\n");
      return NULL;
   }
   else if(pos>length(head))
   {
      printf("the pos over the length of the node\n");
      return NULL;
   }
   else
   {
      while(pos--)
      {
        head=head->next;
      }
   }
   return head; 
}

bool DeleteNode(node *head,int pos,int &data)
{
   if(head==NULL)
     return false;
   node *item=NULL;
   node *p=head;
   node *q=SearchNode1(head,pos-1);
   if((!q)||(!q->next))
   {
   	   printf("delete failed:\n");
   	   return false;
   }
   item=q->next;
   data=item->data;
   q->next=item->next;
   free(item);
   item=NULL;
   printf("Delete success:\n");
   return true;
}

bool InsertNode(node *head,int pos,int data)
{
   if(head==NULL)
     return false;
   node *item=NULL;
   node *p=head;
   node *q=SearchNode1(head,pos-1);
   if(!q)
   {
   	   printf("Insert failed:\n");
   	   return false;
   }
   item=(node*)malloc(sizeof(node));
   item->data=data;
   item->next=q->next;
   q->next=item;
   printf("Insert success:\n");
   return true;
}

void ReverseNode(node *head)
{
	if(head==NULL)
	   return ;
    if(head->next==NULL)
       return ; 
	node *p,*q,*r;
	p=head->next;
	q=p->next;
	p->next=NULL;
	while(q!=NULL)
	{
		r=q->next;
		q->next=p;
		p=q;
		q=r;
	}
	head->next=p;
}

int main()
{
  int len=0;
  node *head,*head1;
  node *head2=NULL;
  printf("please input some date and creat a node\n");
  head=CreatNode_Head(10);
  printnode(head);
  printf("the length of the list is:%d\n",length(head));
  head1=CreatNode_Tail(10);
  printnode(head1);
  printf("the length of the list is:%d\n",length(head1));
  
  
  for(int i=0;i<length(head1);i++)
  {
  	  printf("SearchNode:index:%d,data:%d\n",i+1,SearchNode(head1,i+1));
  	  printnode(SearchNode1(head1,i+1));
  }
  InsertNode(head1,1,101); 
  printnode(head1);
  InsertNode(head1,13,102); 
  printnode(head1);
  
  int data=0;
  DeleteNode(head1,1,data);
  printf("the data is:%d\n",data);
  printnode(head1);
  
  DeleteNode(head1,12,data);
  printf("the data is:%d\n",data);
  printnode(head1);

  ReverseNode(head1);
  printnode(head1);

  return 0;
}