不带头结点的单链表的基本操作

不带头结点的单链表

头指针没有插入任何的数据
唯一的起始：头指针
唯一的结尾：最后一个结点的指针域（NULL）

整体结构

SqeList.h函数声明

void init(Node** phead);
Node* buyNode(ElemType val);
int insertHead(pList* phead, ElemType val);
int insertTail(pList* ptwohead, ElemType val);
int empty(Node* phead);
int deleteHead(pList* ptwohead);
int deleteTail(pList* ptwohead);
void Show(Node* phead);
void destroy(pList* ptwohead);

代码实现

SqeList.cpp实现代码

#include<stdio.h>
#include<stdlib.h>
#include"SeqList.h"
typedef int ElemType;
typedef struct Node
{
 ElemType data;
 struct Node* next;
}Node,*pList;
void init(Node** phead)
{
 *phead = NULL;
}
Node* buyNode(ElemType val)
{
 Node* pnewnode = (Node*)malloc(sizeof(Node));
 pnewnode->data = val;
 pnewnode->next = NULL;
 return pnewnode;
}
int insertHead(pList* phead, ElemType val)
{
 Node* pnewnode = buyNode(val);
 pnewnode->next = (*phead);
 (*phead) = pnewnode;
 return 1;
}
int insertTail(pList* ptwohead, ElemType val)
{
 Node* pnewnode = buyNode(val);
 Node* ptail = *ptwohead;
 if (*ptwohead == NULL)
 {
  (*ptwohead) = pnewnode;
 }
 
 while (ptail->next != NULL)
 {
  ptail = ptail->next;
 }
 ptail->next = pnewnode;
 return 1;
}

int empty(Node* phead)
{
 return phead == NULL ? 1 : 0;
}
int deleteHead(pList* ptwohead)
{
 if (empty(*ptwohead))
 {
  return 0;
 }
 Node* pCur = *ptwohead;
 *ptwohead = pCur->next;
 free(pCur);
 return 1;
}

int deleteTail(pList* ptwohead)
{
 if (empty(*ptwohead))
 {
  return 0;
 }
 Node* pfront = *ptwohead;//指向第一个结点
 Node* pCur = pfront->next;//NULL  只有一个结点  not NULL 至少两个结点
 if (pCur == NULL)
 {
  *ptwohead = NULL;
  free(pfront);
  return 1;
 }
 while (pfront->next != NULL)
 {
  pCur = pfront->next;
  if (pCur->next == NULL)
  {
   break;
  }
  pfront = pfront->next;
 }
 //pfront  倒数第二个
 //pCur    倒数第一个
 pfront->next = NULL;
 free(pCur);
 return 1;
}
void Show(Node* phead)
{
 Node* pCur = phead;
 while (pCur != NULL)
 {
  printf("%d ", pCur->data);
  pCur = pCur->next;
 }
 printf("\n");
}
void destroy(pList* ptwohead)
{
 Node* pCur = *ptwohead;
 Node* pNext = NULL;
 while (pCur != NULL)
 {
  pNext = pCur->next;
  free(pCur);
  pCur = pNext;
 }
 *ptwohead = NULL;
}

代码测试

main.cpp

#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include"SeqList.h"
int main()
{
 Node* phead;
 init(&phead);
 int i = 0;
 for (i; i < 3; i++)
 {
  insertHead(&phead, i + 1);//3 2 1
 }
 Show(phead);
 for (i = 0; i < 3; i++)
 {
  insertTail(&phead, i + 1);//3 2 1 1 2 3
 }
 Show(phead);
 deleteHead(&phead);// 2 1 1 2 3
 Show(phead);
 for (i = 0; i < 5; i++)
 {
  deleteHead(&phead);
 }
 Show(phead);
 return 0;
}