©2020-2024 ioDraw All rights reserved
<>单链表的实现
首先创建头文件
#pragma #include<stdio.h> #include<assert.h> #include<stdlib.h> //定义数据类型
typedef int SLDataType; //创建单链表 typedef struct SLinkListNode { SLDataType data;
struct SLinkListNode* next; }SLNode;
以下是所需要实现的函数接口
//不会改变头指针，传一级指针 //可能改变头指针，传二级指针 // //创建结点 SLNode* BuySLNode(SLDataType x); //打印
void SListPrint(SLNode* phead); //尾插 void SListPushBack(SLNode** pphead,
SLDataType x); //头插 void SListPushFront(SLNode** pphead, SLDataType x); //尾删
void SListPopBack(SLNode** pphead); //头删 void SListPopFront(SLNode** pphead);
//在pos前插入x void SListInsert(SLNode** pphead, SLNode* pos, SLDataType x);
//找到x的位置并返回 SLNode* SListFind(SLNode* phead, SLDataType x); //删除pos位置的值 void
SListErase(SLNode** pphead, SLNode* pos);
接下来是函数的实现
#include"SLinkList.h" //创建新结点 SLNode* BuySLNode(SLDataType x) { SLNode* newnode
= (SLDataType*)malloc(sizeof(SLDataType)); if (newnode == NULL) { printf(
"malloc fail\n"); exit(-1); } newnode->data = x; newnode->next = NULL; return
newnode; } //打印 void SListPrint(SLNode* phead) { SLNode* cur = phead; while (cur
!= NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
//尾插 void SListPushBack(SLNode** pphead, SLDataType x) { SLNode* newnode =
BuySLNode(x); if (*pphead == NULL) { *pphead = newnode; } else { // 找尾节点的指针
SLNode* tail = *pphead; while (tail->next) { tail = tail->next; } // 尾节点，链接新节点
tail->next = newnode; } } //头插 void SListPushFront(SLNode** pphead, SLDataType x
) { SLNode* newnode = BuySLNode(x); newnode->next = *pphead; *pphead = newnode;
} //尾删 void SListPopBack(SLNode** pphead) { if (*pphead == NULL) { return; }
else if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else {
SLNode* prev = NULL; SLNode* tail = *pphead; while (tail->next != NULL) { prev =
tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; } } //头删
void SListPopFront(SLNode** pphead) { SLNode* next = (*pphead)->next; free(*
pphead); *pphead = next; } //在pos前插入x void SListInsert(SLNode** pphead, SLNode*
pos, SLDataType x) { if (pos == *pphead) { SListPushFront(pphead, x); } else {
SLNode* newnode = BuySLNode(x); SLNode* prev = *pphead; while (prev->next != pos
) { prev = prev->next; } prev->next = newnode; newnode->next = pos; } }
//找到x的位置并返回 SLNode* SListFind(SLNode* phead, SLDataType x) { SLNode* cur = phead
; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; }
return NULL; } //删除pos位置的值 void SListErase(SLNode** pphead, SLNode* pos) { if (
pos== *pphead) { SListPopFront(pphead); } else { SLNode* prev = *pphead; while (
prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos
= NULL; } }