No.29 我与代码的日常:单链表的基本操作(单向+不带头+不循环)
学习不易,需要坚持。
//SList.h
#pragma once
typedef int SLDataType ;
typedef struct SListNode
{
int data ;
struct SListNode* next ;
}SListNode ;
typedef struct SList
{
struct SListNode* first ;
}SList ;
//初始化&销毁
void SListInit(SList* list) ;
//销毁
void SListDestroy(SList* list) ;
//头插
void SListPushFront(SList* list, SLDataType data) ;
//头删
void SListPopFront(SList* list) ;
//打印
void SListPrint(SList* list) ;
//尾插
void SListPushBack(SList* list, SLDataType data) ;
//尾删
void SListPopBack(SList* list) ;
//查找
SListNode* SListFind(SList* list, SLDataType data) ;
//在pos位置的节点后插入元素
void SListInsertAfter(SListNode* pos, SLDataType data) ;
//删除pos位置后的第一个节点
void SListEraseAfter(SListNode* pos) ;
//删除遇到的指定的第一个节点
void SListRemove(SList* list, SLDataType data) ;
//SList.c
#include "SList.h"
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//初始化
void SListInit(SList* list)
{
assert(list != NULL) ;
list->first = NULL ;
}
//销毁
void SListDestroy(SList* list)
{
SListNode* next ;
SListNode* cur ;
for(cur=list->first; cur!=NULL; cur=next)
{
next = cur->next ;
free(cur) ;
}
list->first = NULL ;
}
//头插
void SListPushFront(SList* list, SLDataType data)
{
SListNode* node = (SListNode*) malloc (sizeof(SListNode)) ;
assert(node) ;
node->data = data ;
node->next = list->first ;
list->first = node ;
}
//头删
void SListPopFront(SList* list)
{
SListNode* old_first = list->first ;
assert(list) ; //有无链表
assert(list->first != NULL) ; //有链表,链表里是否有元素,若链表为空,则删除失败
list->first = list->first->next ;
free(old_first) ;
}
//打印
void SListPrint(SList* list)
{
SListNode* cur ;
assert(list) ;
for(cur=list->first; cur!=NULL; cur=cur->next)
{
printf("%d-->", cur->data) ;
}
printf("NULL\n") ;
}
//尾插
void SListPushBack(SList* list, SLDataType data)
{
SListNode* node = (SListNode*) malloc (sizeof(SListNode)) ;
SListNode* lastone = list->first ;
assert(list != NULL) ;
for( ; lastone->next != NULL; lastone=lastone->next)
{}
assert(node != NULL) ;
node->data = data ;
node->next = lastone ->next ;
lastone->next = node ;
}
//尾删
void SListPopBack(SList* list)
{
SListNode* cur ;
SListNode* m ;
assert(list != NULL) ;
assert(list->first != NULL) ;
if(list->first->next == NULL)
{
//若链表为空,则尾删即为头删
SListPopFront(list) ;
return ;
}
for(cur=list->first; cur->next->next != NULL; cur=cur->next)
{
}//找到倒数第二个节点
m = cur->next ;
cur->next = m->next ;
free(m) ;
}
//查找
SListNode* SListFind(SList* list, SLDataType data)
{
SListNode* cur = list->first ;
for( ; cur!=NULL; cur=cur->next)
{
if(cur->data == data)
{
return cur ;
}
}
return NULL ;
}
//在pos位置的节点后插入元素
void SListInsertAfter(SListNode* pos, SLDataType data)
{
SListNode* node = (SListNode*) malloc (sizeof(SListNode)) ;
assert(node != NULL ) ;
node->data = data ;
node->next = pos->next ;
pos->next = node ;
}
//删除pos位置后的第一个节点
void SListEraseAfter(SListNode* pos)
{
SListNode* node = pos->next->next ;
free(pos->next) ;
pos->next = node ;
}
//删除遇到的指定的第一个节点
void SListRemove(SList* list, SLDataType data)
{
SListNode* prev = NULL ;
SListNode* cur = list->first ;
while(cur != NULL && cur->data != data)
{
prev = cur ;
cur = cur->next ;
}
//要删除的节点不存在
if(cur == NULL )
{
return ;
}
//要删除的节点若就是第一个节点
if(prev == NULL)
{
//即头删
SListPopFront(list) ;
return ;
}
prev->next = cur->next ;
free(cur) ;
}
//main.c
#include "SList.h"
#include <stdio.h>
SList list ;
void test1()
{
//初始化&头插
SListInit(&list) ;
SListPushFront(&list, 999) ;
SListPushFront(&list, 3) ;
SListPushFront(&list, 3) ;
SListPushFront(&list, 5) ;
SListPushFront(&list, 4) ;
SListPushFront(&list, 3) ;
SListPushFront(&list, 2) ;
SListPushFront(&list, 1) ;
}
void test2()
{
//头删
test1() ;
SListPopFront(&list) ;
}
void test3()
{
//尾插
test2() ;
SListPushBack(&list, 1024) ;
}
void test4()
{
//尾删
test3() ;
SListPopBack(&list) ;
}
void test5()
{
//在pos位置之后插入
SListNode* n = SListFind(&list, 3) ;
SListInsertAfter(n, 520) ;
}
void test6()
{
//删除pos后的第一个节点
SListNode* n = SListFind(&list, 520) ;
SListEraseAfter(n) ;
}
void test7()
{
//删除遇到的指定的第一个节点
test6() ;
SListRemove(&list, 3) ;
}
void test8()
{
//销毁单链表
test7() ;
SListDestroy(&list) ;
}
int main()
{
printf("头插: \n") ;
test1() ;
SListPrint(&list) ;
printf("\n头删: \n") ;
test2() ;
SListPrint(&list) ;
printf("\n尾插: \n") ;
test3() ;
SListPrint(&list) ;
printf("\n尾删: \n") ;
test4() ;
SListPrint(&list) ;
printf("\n查找:\n") ;
printf("999地址为: %p\n",SListFind(&list, 999) ) ;
printf("\n在pos位置之后插入: \n") ;
test5() ;
SListPrint(&list) ;
printf("\n删除pos位置之后的第一个节点:\n") ;
test6() ;
SListPrint(&list) ;
printf("\n删除遇到的指定的第一个节点:\n") ;
test7() ;
SListPrint(&list) ;
printf("销毁:\n") ;
test8() ;
SListPrint(&list) ;
printf("\n") ;
return 0 ;
}
运行结果: