【推薦】資料結構:單連結串列 插入,刪除,等功能

【推薦】資料結構:單連結串列  插入,刪除,等功能

以下為單連結串列(不帶頭節點,不帶環)的C語言實現程式碼
注:更多功能的實現請檢視 單連結串列(進擊版)

實現功能(基礎版)

//初始化連結串列頭節點

//連結串列尾插

//連結串列頭插

//連結串列尾刪

//連結串列頭刪

//查詢元素在連結串列中的地址

//查詢元素在連結串列中的下標

標頭檔案程式碼link.h


#pragma once   //防止標頭檔案重複包含
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Datatype char        
typedef struct LinkNode     //定義結構體
{
Datatype data;           //儲存內容
struct LinkNode* next;     //指向下一個節點
}LinkNode;         
//建立節點       
LinkNode* LinklistCreat(void);
//刪除節點
void LinklistDestroy(LinkNode* head);
//初始化連結串列頭節點
void LinklistInit(LinkNode** phead);    //使用LinkNode** 型別因為連結串列可能需要修改頭指標指向
//連結串列尾插
void LinklistPushback(LinkNode** phead, Datatype value);
//連結串列頭插
void LinklistPushfront(LinkNode** phead, Datatype value);
//連結串列尾刪
void LinklistPopback(LinkNode** phead);
//連結串列頭刪
void LinklistPopfront(LinkNode** phead);
//查詢元素在連結串列中的地址
LinkNode* LinklistFind(LinkNode* head, Datatype to_find);
//查詢元素在連結串列中的下標
size_t  LinklistFind1(LinkNode* head, Datatype to_find);

函式實現程式碼link.c

#include "link.h"
//建立節點
LinkNode* LinklistCreat(void)
{
LinkNode* new = malloc(sizeof(LinkNode));
return new;
}
//刪除節點
void LinklistDestroy(LinkNode* head)
{
if (head == NULL)
{
printf("空指標");
return;
}
free(head);
}   
//初始化連結串列頭節點
void LinklistInit(LinkNode** phead)
{
if (phead == NULL)
{
printf("空指標");
return;
}
*phead = NULL;
}
//連結串列尾插
void LinklistPushback(LinkNode** phead, Datatype value)
{
if (phead == NULL)
{
printf("非法輸入");
return;
}
//空連結串列尾插
if (*phead == NULL)
{
*phead = LinklistCreat();    //建立節點
(*phead)->data = value;        //節點賦值
(*phead)->next = NULL;              //插入空連結串列即新節點指向空
return;        
}
//常規尾插
LinkNode* new = LinklistCreat();   //建立新節點
LinkNode* cur = *phead;          
new->data = value;
new->next = NULL;       
while (cur->next!= NULL)     //使cur指向最後一個節點
{
cur = cur->next;
}
cur->next = new;          //最後節點的下一個節點即指向新節點
return;                   
}
//連結串列頭插
void LinklistPushfront(LinkNode** phead, Datatype value)
{
if (phead == NULL)
{
printf("非法輸入");
return;
}
LinkNode* new = LinklistCreat();   //建立節點 
new->data = value; 
LinkNode* cur = *phead;     //cur指向頭指標
*phead = new;         
new->next = cur;                   //新節點指向,指向頭節點的指標
}
//連結串列尾刪
void LinklistPopback(LinkNode** phead)
{
if (phead == NULL)
{
printf("非法輸入");
return;
}
if (*phead == NULL)
{
printf("空連結串列");
return;
}
//只有一個元素
if ((*phead)->next == NULL)
{
LinkNode* tmp = *phead;  //儲存頭指標指向
*phead = NULL;          //置空
LinklistDestroy(tmp);   //銷燬節點
return;
}
//兩個及以上元素
LinkNode* cur = *phead;   
LinkNode* pre = NULL; 
while (cur->next != NULL)    //使cur指向最後一個節點
{                            //使pre指向倒數第二個節點
pre = cur; 
cur = cur->next;
}
pre->next = NULL;    //尾刪,即倒數第二個節點指向空
LinklistDestroy(cur);  //銷燬最後一個節點
}
//連結串列頭刪
void LinklistPopfront(LinkNode** phead)
{
if (phead == NULL)
{
printf("非法輸入");
return;
}
if (*phead == NULL)
{
printf("空連結串列");
return;
}
//常規頭刪
LinkNode* cur = *phead;  //建立指向頭節點的指標
*phead = (*phead)->next;  //頭節點指向下一個節點
LinklistDestroy(cur);    //銷燬指向頭節點的指標
return;
}
//查詢元素在連結串列中的地址
LinkNode*  LinklistFind(LinkNode* head, Datatype to_find)
{
if (head == NULL)
{
printf("空連結串列");
return NULL ;
}
LinkNode *cur = head;      
while (cur != NULL)
{
if (cur->data == to_find)  
{
return cur;   //找到則返回結構體地址
}
cur = cur->next;   //遍歷要查詢的元素
}
printf("沒有找到\n");
return NULL;
}
//查詢元素在連結串列中的下標
size_t  LinklistFind1(LinkNode* head, Datatype to_find)
{
if (head == NULL)
{
printf("空連結串列");
return ;
}
size_t count = 0;
LinkNode *cur = head;  
while (cur != NULL)
{
count  ;    //定義計數器
if (cur->data == to_find)
{
return count;
}
cur = cur->next;
}
printf("沒有找到\n");
return ;
}

測試程式碼test.c

#include "link.h"
#include<stdio.h>
#include<stdlib.h>
/************************************************************************
*                            tset
***********************************************************************/
//定義一個巨集來列印除錯函式提示資訊
#define FUNCTION() printf("****************   %s  ************\n" , __FUNCTION__)
void printChar(LinkNode* head ,const char *msg)
{
if (head == NULL)
{
printf("空指標");    
return;
}
printf("%s\n", msg);            
for (; head != NULL; head = head->next)
{
printf("%c\n", head->data);
}
printf("\n");
return;
}
void TestPushback()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
printChar(head, "尾插a,b,c,d");
}
void TestPushfront()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushfront(&head, 'a');
LinklistPushfront(&head, 'b');
LinklistPushfront(&head, 'c');
LinklistPushfront(&head, 'd');
printChar(head, "頭插a,b,c,d");
}
void TestPopback()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
printChar(head, "尾插a,b,c,d");
LinklistPopback(&head);
LinklistPopback(&head);
printChar(head, "尾刪兩節點");
}
void TestPopfront()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
printChar(head, "尾插a,b,c,d");
LinklistPopfront(&head);
LinklistPopfront(&head);
printChar(head, "頭刪兩節點");
}
void TestFind()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
LinkNode* ret = LinklistFind(head, 'b');
printf("a的儲存位置%p\n", ret->data);
}
void TestFind1()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
LinklistFind1(head, 'a');
size_t ret = LinklistFind1(head, 'a');
printf("a的下標 %lu \n", ret);
}
void TestInsert()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
printChar(head, "尾插a,b,c,d");
LinklistInsert(&head, head ,'x');
printChar(head, "a之前插入x");
}
void TestInsertAfter()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
printChar(head, "尾插a,b,c,d");
LinklistInsertAfter(&head, head->next, 'x');
printChar(head, "b之後插入x");
}
void TestErase()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
printChar(head, "尾插a,b,c,d");
LinklistErase(&head, head);
printChar(head, "刪除頭節點的元素a");
}
void TestRemove()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
printChar(head, "尾插a,b,c,d");
LinklistRemove(&head, 'a');
printChar(head, "刪除指定元素a");
}
void TestSize() 
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
LinklistSize(head);
size_t count = LinklistSize(head);
printf("count=%lu\n", count);
printChar(head, "求連結串列元素的個數");
}
void TestEmpty()
{
FUNCTION();
LinkNode* head;
LinklistInit(&head);
LinklistPushback(&head, 'a');
LinklistPushback(&head, 'b');
LinklistPushback(&head, 'c');
LinklistPushback(&head, 'd');
LinklistPopback(&head);
LinklistPopback(&head);
LinklistEmpty(head);
int i = LinklistEmpty(head);
printf("i=%d\n", i);
printChar(head, "判斷連結串列是否為空");
}
int main()
{
TestPushback();
TestPushfront();
TestPopback();
TestPopfront();
TestFind();
TestFind1();
return 0;
}

這裡寫圖片描述

這裡寫圖片描述