带头节点的不循环单链表相关操作

创建list.h头文件

#pragma once
//头结点：开头标识，类似旗帜，不存放数据，不参与运算
//数据结点：存放数据
typedef struct Node
{
 int data;
 struct Node *next;
}Node,*pList;

//初始化
void InitSeqList(pList plist);

//头插
bool Insert_head(pList plist,int val);

//尾插
bool Insert_tail(pList plist,int val);

//在plist中查找关键字Key，找到后返回地址，失败返回-1
Node *Search(pList plist,int key);

//判空
bool IsEmpty(pList plist);

//删除第一个key值
bool DeleteVal(pList plist,int key);

//获取数据长度
int GetLength(pList plist);

//显示
void Show(pList plist);

//清空数据
void Clear(pList plist);

//销毁动态内存
void Destroy(pList plist);

创建list.cpp文件

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"list.h"
/*
注意事项：
 1.找后一个节点是p=p->next;不能写成p++
*/

//判空
static void DeterPointNull(pList plist)
{
 assert(plist!=NULL);
 if(plist==NULL)
 {
  exit(0);
 }
}

//初始化
void InitSeqList(pList plist)
{
 DeterPointNull(plist);
 plist->next=NULL;
}

//头插
bool Insert_head(pList plist,int val)
{
 DeterPointNull(plist);
 
 //程序出错，由于Node定义的是局部变量，使用后便销毁，无法传递回去
 /*Node node;
 node.data=val;
 node.next=plist->next;
 plist->next=&node;*/
 
 Node *p=(Node *)malloc(sizeof(Node));
 p->data=val;
 p->next=plist->next;
 plist->next=p;
 
 return true;
}

//尾插
bool Insert_tail(pList plist,int val)
{
 DeterPointNull(plist);
 
 //创建新节点
 Node *p=(Node *)malloc(sizeof(Node));
 
 //将值存放到新节点
 p->data=val;
 
 //找尾结点
 Node *q;
 for(q=plist;q->next!=NULL;q=q->next);
 //将新节点插入到q后面
 p->next=q->next;// 相当于p->next=NULL;
 q->next=p;
 
 return true;
}

//在plist中查找关键字Key，找到后返回地址，失败返回空指针
Node *Search(pList plist,int key)
{
 DeterPointNull(plist);
 for(Node *p=plist->next;p!=NULL;p=p->next)
 {
  if(p->data==key)
  {
   return p;
  }
 }
 return NULL;
}

//判空
bool IsEmpty(pList plist)
{
 DeterPointNull(plist);
 return plist->next==NULL;
}

//删除plist中的第一个key
bool DeleteVal(pList plist,int key)
{
 DeterPointNull(plist);
 Node *q;
 for(Node *p=plist->next;p!=NULL;)
 {
  q=p->next;
  if(p->data==key)
  {
   plist->next=p->next;
   free(p);
   return true;
  }
  if(q->data==key)
  {
   p->next=q->next;
   free(q);
   return true;
  }
 }
 return false;
}

//获取数据长度
int GetLength(pList plist)
{
 DeterPointNull(plist);
 int count=0;
 for(Node *p=plist->next;p!=NULL;p=p->next)
 {
  count++;
 }
 return count;
}

//显示
void Show(pList plist)
{
 DeterPointNull(plist);
 for(Node *p=plist;p->next!=NULL;p=p->next)
 {
  printf("%-5d",p->next->data);
 }
 printf("\n");
}

//清空数据
void Clear(pList plist)
{
 DeterPointNull(plist);
 plist->next=NULL;
}

//销毁动态内存
//总是删除第一个数据结点
void Destroy(pList plist)
{
 DeterPointNull(plist);
 Node *p;
 while (plist->next!=NULL)//还有第一个数据结点
 {
  p=plist->next;//p指向第一个数据结点
  plist->next=p->next;//将p从链表中剔除
  free(p);
 }
}
/*
//销毁动态内存
void Destroy(pList plist)
{
 DeterPointNull(plist);
 Node *p=plist->next;//指向需要删除的结点
 Node *q;//p的下一个节点，不能直接赋值=p->next
 
 while (p=plist->next!=NULL)
 {
  q=p->next;
  free(p);
  p=q;
 }
 plist->next=NULL;
}
*/

其他功能：

//算法1：利用栈实现（利用数组模拟栈）//时间复杂度：O（n）  空间复杂度：O（n）
void Reverse1(pList plist)
{
 int len=GetLength(plist);
 int *arr=(int *)malloc (len*sizeof(int));
 assert(arr!=NULL);
 int i=0;//arr的下标
 
 //从头到尾遍历plist，将数据全部存放到arr中
 for(Node *p=plist->next;p!=NULL;p=p->next)
 {
  arr[i++]=p->data;
 }
 
 //金属组中的数据从后往前，再赋值到链表中
 i=len-1;//最后一个元素的下标
 for(Node *p=plist->next;p!=NULL;p=p->next)
 {
  p->data=arr[i--];
 }
 free(arr);
}

//算法2：利用头插和尾插相反的算法 //O(n)  O(1)
void Reverse(pList plist)
{
 Node *p=plist->next;
 Node *q;
 plist->next=NULL;
 while(p!=NULL)
 {
  q=p->next;

  //将p头插到plist中
  p->next=plist->next;
  plist->next=p;
  p=q;
 }
}