c实现无头结点单链表

头文件

#ifndef __LINKLIST_H__
#define __LINKLIST_H__


#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <malloc.h>

typedef int DataType;

typedef struct Node
{
 DataType _data;
 struct Node* _next;
}Node,*pNode,*pList;



void InitLinkList(pList* pplist);//初始化
void DestroyList(pList* pplist);//销毁单链表
void Display(pList plist);//遍历单链表

void PushBack(pList* pplist, DataType x);//尾插
void PopBack(pList* pplist);//尾删

void PushFront(pList* pplist, DataType x);//头插
void PopFront(pList* pplist);//头删

pNode Find(pList plist, DataType x);//查找元素的位置

void Insert(pList* pplist, pNode pos, DataType x);//指定位置插入
void Erase(pList* pplist, pNode pos);//指定位置删除

void Remove(pList* pplist, DataType x);//删除指定的元素
void RemoveAll(pList* pplist, DataType x);//删除指定元素的所有

void Sort(pList* pplist);//单向链表的排序
#endif

程序实现文件

#include "linklist.h"

void InitLinkList(pList* pplist)
{
 assert(pplist);
 *pplist = NULL;
}


void DestroyList(pList* pplist)
{
 pNode cur = NULL;
 pNode del = NULL;
 assert(pplist);
 cur = *pplist;
 while(cur)
 {
  del = cur;
  cur = cur->_next;
  free(del);
 }
 free(cur);
 *pplist = NULL;
}



void PushBack(pList* pplist, DataType x)
{
 pNode cur = NULL;
 pNode newnode = NULL;
 assert(pplist);
 cur = *pplist;
 newnode = (pNode)malloc(sizeof(Node));
 newnode->_data = x;
 newnode->_next = NULL;
 if(*pplist == NULL)
 {
  *pplist = newnode;
  return;
 }
 while(cur->_next)
 {
  cur = cur->_next;
 }
 cur->_next = newnode;
}


void PopBack(pList* pplist)
{
 pNode cur = NULL;
 assert(pplist);
 cur = *pplist;
 if(*pplist == NULL)
 {
  return;
 }
 if(cur->_next == NULL)
 {
  free(cur);
  *pplist = NULL;
  return;
 }
 while(cur->_next->_next)
 {
  cur = cur->_next;
 }
 free(cur->_next);
 cur->_next = NULL;
}


void PushFront(pList* pplist, DataType x)
{
 pNode cur = NULL;
 pNode newnode = NULL;
 assert(pplist);
 cur = *pplist;
 newnode = (pNode)malloc(sizeof(Node));
 newnode->_data = x;
 newnode->_next = NULL;
 if(*pplist == NULL)
 {
  *pplist = newnode;
  return;
 }
 else
 {
  newnode->_next = cur;
  *pplist = newnode;
 }

} 


void PopFront(pList* pplist)
{
 pNode cur = NULL;
 pNode del = NULL;
 assert(pplist);
 cur = *pplist;
 if(*pplist == NULL)
 {
  return;
 }
 if(cur->_next == NULL)
 {
  free(cur);
  *pplist = NULL;
  return;
 }
 del = cur;
 cur = cur->_next;
 free(del);
 *pplist = cur;
}


pNode Find(pList plist, DataType x)
{
 pNode pos = plist;
 while(pos)
 {
  if(pos->_data == x)
  {
   return pos;
  }
  pos = pos->_next;
 }
 return NULL;
}


void Insert(pList* pplist, pNode pos, DataType x)
{
 pNode cur = NULL;
 pNode newnode = NULL;
 assert(pplist);
 cur = *pplist;
 newnode = (pNode)malloc(sizeof(Node));
 newnode->_data = x;
 newnode->_next = NULL;
 if(*pplist == NULL)
 {
  *pplist = newnode;
  return;
 }
 while(cur->_next != pos)
 {
  cur = cur->_next;
 }
 newnode->_next = pos;
 cur->_next = newnode;
}


void Erase(pList* pplist, pNode pos)
{
 pNode cur = NULL;
 assert(pplist);
 cur = *pplist;
 if(*pplist == NULL)
 {
  return;
 }
 if((pos == *pplist)&&pos->_next)
 {
  *pplist = pos->_next;
  free(pos);
  return;
 }
 while((cur->_next != pos)&&cur)
 {
  cur = cur->_next;
 }
 cur->_next = pos->_next ;
 free(pos);
}



void Remove(pList* pplist, DataType x)
{
 pNode pos = NULL;
 assert(pplist);
 pos = Find(*pplist,x);
 Erase(pplist, pos);

}


void RemoveAll(pList* pplist, DataType x)
{
 pNode cur = NULL;
 pNode dec = NULL;
 assert(pplist);
 cur = *pplist;
 while(cur)
 {
  if(cur->_data == x)
  {
   pNode del = cur;
   if(cur == *pplist)
   {
    *pplist = cur->_next;
   }
   else
   {
    dec->_next = cur->_next;
   }
   cur = cur->_next;
   free(del);
  }
  else
  {
   dec = cur;
   cur = cur->_next;
  }
 }
}



void Sort(pList* pplist)
{
 pNode cur = NULL;
 pNode dec = NULL;
 assert(pplist);
 cur = *pplist;
 for(; cur; cur = cur->_next)
 {
  for(dec = cur->_next; dec; dec = dec->_next)
  {
   if(cur->_data > dec->_data)
   { 
    DataType tmp;
    tmp = cur->_data;
    cur->_data = dec->_data;
    dec->_data = tmp;
   }
  }
 }
}





void Display(pList plist)
{
 pNode cur = plist;
 while(cur)
 {
  printf("%d->",cur->_data);
  cur = cur->_next;
 }
 printf("NULL\n");
}

测试文件

#include "linklist.h"

void test()
{
 pNode plist;
 InitLinkList(&plist);
 PushBack(&plist, 1);
 PushBack(&plist, 2);
 PushBack(&plist, 3);
 PushBack(&plist, 4);
 Display(plist);//尾插输入1234
 PopBack(&plist);
 Display(plist);//尾删一个
 PopBack(&plist);
 Display(plist);//尾删一个
 PopBack(&plist);
 Display(plist);//尾删一个
 PopBack(&plist);
 Display(plist);//尾删一个
 PopBack(&plist);
 Display(plist);//尾删一个
 DestroyList(&plist);
 Display(plist);
}


void test1()
{
 pNode plist;
 InitLinkList(&plist);
 PushFront(&plist, 1);
 PushFront(&plist, 2);
 PushFront(&plist, 3);
 PushFront(&plist, 4);
 Display(plist);//头插输入1234
 PopFront(&plist);
 Display(plist);//头删一个
 PopFront(&plist);
 Display(plist);//头删一个
 PopFront(&plist);
 Display(plist);//头删一个
 PopFront(&plist);
 Display(plist);//头删一个
 PopFront(&plist);
 Display(plist);//头删一个
 DestroyList(&plist);
 Display(plist);
}

void test2()
{
 pNode plist;
 pNode pos = NULL;
 InitLinkList(&plist);
 PushFront(&plist, 1);
 PushFront(&plist, 2);
 PushFront(&plist, 3);
 PushFront(&plist, 4);
 Display(plist);
 pos = Find(plist, 3);//找到3的位置
 printf("%d\n",pos->_data);
 Insert(&plist, pos, 5);//在3元素的位置处插入元素5
 Display(plist);
 Erase(&plist, pos);//删除3元素位置处的元素
 Display(plist);
 Remove(&plist, 5);//删除元素5
 Display(plist);
 DestroyList(&plist);
 Display(plist);
}




void test3()
{
 pNode plist;
 InitLinkList(&plist);
 PushFront(&plist, 3);
 PushFront(&plist, 1);
 PushFront(&plist, 3);
 PushFront(&plist, 2);
 PushFront(&plist, 3);
 PushFront(&plist, 4);
 PushFront(&plist, 3);
 Display(plist);
 RemoveAll(&plist, 3);//删除指定的所有相同的元素
 Display(plist);
 DestroyList(&plist);
 Display(plist);
}



void test4()
{
 pNode plist;
 InitLinkList(&plist);
 PushFront(&plist, 2);
 PushFront(&plist, 1);
 PushFront(&plist, 6);
 PushFront(&plist, 4);
 PushFront(&plist, 5);
 PushFront(&plist, 9);
 PushFront(&plist, 4);
 Display(plist);
 Sort(&plist);//排序单链表
 Display(plist);
 DestroyList(&plist);
 Display(plist);
}


int main()
{
 test();
 test1();
 test2();
 test3();
 test4();
 return 0;
}

所有程序实现图