c语言单向链表的基本功能的实现

时间：2021-12-25 01:34:08

1.单链表整体以结构提为框架，为了简单实现基本功能，里面的结点数据元素就定义为一个int data 型元素和next指针

具体如下：

typedef struct Node
{
DataType data;//数据
struct Node *next;//指针
}Node;
首先给Lists.h出头文件部分，主要是头文件和功能函数的声明 

#define _CRT_SECURE_NO_WARNINGS 1
#ifndef __LISTS_H__
#define __LISTS_H__


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

typedef int DataType;

typedef struct Node
{
DataType data;//数据
struct Node *next;//指针
}Node;

void InitLists(Node **head);//初始化
void destory(Node **head);//free开辟的结点
void pushback(Node **head, int d);//从尾部插入
void diaplay(Node *head);//打印
void popback(Node **head);//从尾部删除
void pushfront(Node **head, int d);//从首部插入
void popfront(Node **head);//从首部删除
Node *Listfind(const Node *head, const int locate);//指定位置查找
void Listinsert(Node **head, int locate,int d);//指定位置插入
void Erase(Node **head, int locate);//指定位置删除
void Remove(Node **head, int d);//删除相同结点元素的第一个结点
void remove_all(Node **head, int d);//删除相同指定结点元素所在的所有结点

#endif
接下来给出具体实现函数的文件部分Lists.c 

#define _CRT_SECURE_NO_WARNINGS 1
#include"Lists.h"

void InitLists(struct Node **head)//二级指针接受指针变量的地址
{
*head = NULL;//头指针指向空
}
void pushback(Node **head, int d)//插尾函数
{
Node *cur = *head;//*head表示指针head里面的内容
Node *p =(Node *) malloc(sizeof(Node));//开辟头结点
memset(p, 0, sizeof(Node));//初始化头结点
p->data = d;//给结点里面赋值
p->next = NULL;//头结点指向的下一个结点为NULL,因为还没有开辟
if (cur == NULL)
{
*head = p;//将头结点的地址赋值给头指针
}
else
{
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = p;
}
}
void diaplay(Node *head)//打印函数
{
Node *cur = head;//将头指针指向的内容给cur
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
}
void popback(Node **head)//从尾删除
{
Node *str = NULL;
Node *cur = *head;
if (*head == NULL)
return;
while (cur->next != NULL)
{
str = cur;
cur = cur->next;
}
if (str != NULL)
{
str->next = NULL;
free(cur);
}
else
{
free(cur);
*head = NULL;
}
}
void pushfront(Node **head, int d)//从头插入
{
assert(*head);
Node *cur = *head;//*head表示指针head里面的内容
Node *p = (Node *)malloc(sizeof(Node));//开辟头结点
memset(p, 0, sizeof(Node));//初始化头结点
p->data = d;//给结点里面赋值
p->next = NULL;//头结点指向的下一个结点为NULL,因为还没有开辟
p->next = *head;//开辟的新结点里面 的next指向之前的旧结点
*head = p;//把新开辟的结点的地址给头指针
}
void popfront(Node **head)//从头删除
{
Node *str = NULL;
Node *cur = *head;
if (*head == NULL)
return;
*head= cur->next;
free(cur);
}
Node *Listfind(const Node *head,const int locate)//查找指定位置的结点
{
assert(head);
if (head == NULL)
return;
int count = 1;
Node *cur = head;//指向第一个结点cout赋值为1;
while (cur!=NULL&&count<locate)
{
cur = cur->next;
count++;
}
if (cur == NULL)
return;
else
 return cur;
}
void Listinsert(Node **head, int locate,int d)//指定位置插入结点和结点元素
{
assert(*head);
int count = 1;
Node *cur = *head;
Node *p = (Node *)malloc(sizeof(Node));//申请节点
memset(p, 0, sizeof(Node));
p->data = d;
p->next = NULL;
while (count < locate - 1)
{
cur = cur->next;
count++;
}
if (locate == 1)
{
p->next = *head;
*head = p;
return;
}
p->next = cur->next;//把第locate的地址给p->next，把p的地址给locate-1的next
cur->next = p;
}
void Erase(Node **head, int locate)//删除指定的结点
{
assert(*head);
if (*head == NULL)
return;
int count =1;
Node *cur = *head;
while (count < locate-1)
{
cur = cur->next;
count++;
}
if (locate == 1)
{
*head = cur->next;
free(cur);
return;
}
Node *p = cur->next;//cur->next是locate的位置
cur->next = p->next;//cur->next里面存的是第四个的地址，p->next第四个
free(p);
}
void Remove(Node **head, int d)//删除指定重复结点元素的出现的第一个元素
{
assert(*head);
int count = 1;
int n = 1;
Node *cur = *head;//cur里面是第一个元素
Node *str= *head;//cur里面是第一个元素
while (cur!= NULL)
{
if (cur->data == d&&count==1)//要删除结点出现在第一个的位置上面的时候
{
*head=cur->next;
free(cur);
return;
}
if (cur->data == d)
{
while (n <count-1)
{
str = str->next;
n++;
}
str->next = cur->next;
free(cur);
return;
}
cur = cur->next;
count++;
}
exit(EXIT_FAILURE);
}
void remove_all(Node **head, int d)//删除所有重复的结点
{
assert(*head);
int count = 1;
int n = 1;
Node *cur = *head;//cur里面是第一个元素
Node *str = *head;//cur里面是第一个元素
 flag:  while (cur != NULL)
{
if (cur->data == d&&count == 1)//要删除结点出现在第一个的位置上面的时候
{
*head = cur->next;
free(cur);
cur = *head;
str = *head;
count = 1;
n = 1;
goto flag;
}
if (cur->data == d)
{
while (n <count - 1)
{
str = str->next;
n++;
}
str->next = cur->next;
free(cur);
cur = *head;//删除一个以后要重新赋值
str = *head;
count = 1;
n = 1;
goto flag;//goto回去重新开始计算
}
cur = cur->next;
count++;
}
}
void destory(Node **head)//free链表函数释放
{
assert(*head);
Node *cur = *head;
while (cur!= NULL)
{
*head = cur;//从前向后释放
cur=cur->next;
free(*head);
}
}

接下来给出测试部分文件test.c,里面主要是主函数和测试函数

#define _CRT_SECURE_NO_WARNINGS 1
#include"Lists.h"
void test()
{
struct Node *head;//头指针
InitLists(&head);//初始化需要将头指针赋值成为NULL,所以将指针的地址传过去
pushback(&head,1);
pushback(&head, 2);
//pushback(&head, 4);
//pushback(&head, 2);
//pushback(&head, 4);
//pushback(&head, 2);
//pushback(&head, 4);
diaplay(head);//把头指针传给
printf("\n");
destory(&head);//free所有结点
/*Remove(&head, 2);*/
//remove_all(&head, 2);//删除所有重复的2结点
diaplay(head);//把头指针传给
//printf("\n");
//Listinsert(&head,1, 10);
//Erase(&head, 1);
//pushfront(&head, 1);
//pushfront(&head, 2);
//pushfront(&head, 3);
//pushfront(&head, 4);
//popfront(&head);
//popfront(&head);
//popfront(&head);
//diaplay(head);//把头指针传给
//printf("\n");
//popback(&head);
//diaplay(head);//把头指针传给
//printf("\n");
//printf("%d",Listfind(head, 1)->data);
}

int main()
{
test();
system("pause");
return 0;
}
注意：记得在测试最后面使用destory();函数来释放所动态开辟的结点

如果有什么问题，欢迎大家留言一起学习交流！







标签：

相关文章