单链表数据结构 C语言

程序员文章站 2022-05-26 11:35:27

...

单链表-有头结点

环境：VisualStudio2019
操作：

初始化 + 判断表是否为空
创表（图解）
– 头插法
– 尾插法
打印单链表 + 求表长
查找
– 按位查找
– 按值查找
插入(图解)
– 后插（在第i个位置插入元素e）
– 前插（在第i个结点插入）
删除（图解）
– 按位删除（删除第i个位置的元素）
– 按结点删除（删除第i个结点的元素）

头文件

#include<stdio.h>
#include<stdbool.h>

void Cut(); //分割线

//初始化
bool InitList(LinkList* L); //初始化（没用到，包含在创表里了）
bool Empty(LinkList L);//判断表是否为空（没用到）

//创表
LinkList HeadCreate(LinkList* L);
LinkList TailCreate(LinkList* L);
void Show(LinkList L);
int Length(LinkList L);

//查找
LNode* GetElem(LinkList L, int i);
int LocateElem(LinkList L, int e);

//插入
bool InsertNextNode(LNode* p, int e); //被ListAfterInsert调用
bool ListAfterInsert(LinkList* L, int i, int e);
bool InsertFormerNode(LNode* p, int e); //被ListBeforeInsert调用
bool ListBeforeInsert(LinkList* L, int i, int e);

//删除
bool ListOrderDelete(LinkList* L, int i);
bool DeleteNode(LNode* p); //被ListNodeDelete调用
bool ListNodeDelete(LinkList* L, int i);

typedef struct LNode  //单链表节点类型
{
    int data;      //存放数据元素
    struct LNode* next;  //指向下个节点的指针

} LNode, *LinkList;//给LNode两个名字

主函数：

int main(void)
{
	LinkList L;
	int i = 1;
	int e = 1;

	printf("================开始=================\n");

	printf("请输入向链表中插入的值，以999作为结束：\n");
	HeadCreate(&L);                                  //创表：头插法
	printf("链表元素是：");
	Show(L);
	Cut();

	printf("请输入向链表中插入的值，以999作为结束：\n");
	TailCreate(&L);                                  //创表：尾插法
	printf("链表元素是：\n");
	Show(L);
	printf("链表当前长度是：%d",Length(L));
	Cut();
	
	printf("您想查看第几个位置的元素？");
	scanf_s("%d", &i);
	LNode* p = GetElem(L, i);                        //查找：按位查找
	printf("查询结果是：%d", p->data);
	Cut();

	printf("您想查值为几的元素位置？");
	scanf_s("%d", &e);
	int num = LocateElem(L, e);                      //查找：按值查找
	printf("查询结果是：%d", num);
	Cut();

	printf("在第几个位置插入？");
	scanf_s("%d",&i);
	printf("插入值的值是？");
	scanf_s("%d", &e);
	printf("插入结果如下：\n");
	if(ListAfterInsert(&L, i, e))                     //插入：后插
		Show(L);
	else
		printf("插入失败\n");
	Cut();

	printf("在第几个结点插入？");
	scanf_s("%d", &i);
	printf("插入值的值是？");
	scanf_s("%d", &e);
	printf("插入结果如下：\n");
	if (ListBeforeInsert(&L, i, e))                   //插入：前插
		Show(L);
	else
		printf("插入失败\n");
	Cut();
	
	printf("删除第几个位置的元素？");
	scanf_s("%d",&i);
	printf("删除结果如下：\n");
	if(ListOrderDelete(&L, i))                        //删除：按位删除
		Show(L);
	else
		printf("删除失败\n");
	Cut();

	printf("删除第几个结点的元素？");
	scanf_s("%d",&i);
	printf("删除结果如下：\n");
	if(ListNodeDelete(&L,i))                          //删除：指定结点删除
		Show(L);
	else
		printf("删除失败\n");
	Cut();

	getchar();
	return 0;
}

函数：
可爱的分割线

void Cut()
{
    printf("\n=============== 完成 ===================\n");
}

初始化+判断表是否位空

/******************************************************************************/
//初始化：带头结点,头结点不存储数据
bool InitList(LinkList *L)
{
    (*L) = (LNode*)malloc(sizeof(LNode));
    //指向头结点
    if ((*L) == NULL)
        return false;//内存不足，分配失败

    (*L)->next = NULL;//头结点后暂时无其它结点
    return true;
}
/******************************************************************************/
//判断链表是否为空
bool Empty(LinkList L)
{
    if (L->next == NULL)
        return true;
    else
        return false;
}

创表：头插法（思路如图1）

/*----------------------------------------------------------------------------*/

//建表：头插法
LinkList HeadCreate(LinkList* L)
{
    //1，初始化链表
    (*L) = (LNode*)malloc(sizeof(LNode));
    (*L)->next = NULL;
    //2,定义头指针
    LNode* phead = (*L);

    int x;
    scanf_s("%d", &x);
    LNode* s;
    while (x != 999)//当输入为999时，不在增加链表长度
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = phead->next;
        phead->next = s;
        scanf_s("%d", &x);
    }
    return (*L);
}

思路：
单链表数据结构 C语言
（图1）

创表：尾插法（思路如图2）

/******************************************************************************/
//建表：尾插法
LinkList TailCreate(LinkList* L)
{
    //1,初始化LocateElem(LinkList L, int e);
    (*L) = (LNode*)malloc(sizeof(LNode));
    (*L)->next = NULL;

    //2,定义尾指针
    LNode* ptail = (*L);

    int x = 1;
    scanf_s("%d", &x);
    LNode* s;
    while (x != 999)//当输入为999时，不在增加链表长度
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        ptail->next = s;
        ptail = s;
        scanf_s("%d", &x);
    }
    ptail->next = NULL;//最后一个元素指向空
    return (*L);          //把链表传回
}

思路：
单链表数据结构 C语言
（图2）

打印单链表+求表长

/********************************************************************************/
//打印单链表
void Show(LinkList L)
{
    LNode* p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
/******************************************************************************/
//求链表长度
int Length(LinkList L)
{
    LNode* p = L;
    int length = 0;
    while (p != NULL)
    {
        p = p->next;
        length++;
    }
    return length;//算上了头结点
}

查找：按位查找+按值查找

/*-----------------------------------------------------------------------------*/
//按位查找:找到第i位的元素
LNode* GetElem(LinkList L, int i)
{
    if (i < 1)
        return false;
    LNode* p = L;
    int j = 0;
    while (p != NULL && j < i)
    {//找到第i个结点
        p = p->next;
        j++;
    }
    return p;
}
/******************************************************************************/
//按值查找，找到值位e对应的元素位置
int LocateElem(LinkList L, int e)
{
    LNode* p = L->next; //从第一个结点开始找
    int num = 1;
    while (p != NULL && p->data != e)
    {
        p = p->next;
        num++;
    }

    return num;
}

插入：后插（思路如图3）

/*------------------------------------------------------------------------------*/
//指定结点后插：在p节点后插入元素e
bool InsertNextNode(LNode* p, int e)
{
    if (p == NULL)
        return false;     //i不合法：第i-1个地址不存在
    LNode* s = (LNode*)malloc(sizeof(LNode)); //为新元素申请空间
    if (s == NULL)
        return false;     //内存malloc分配失败
    s->data = e;          //装data
    s->next = p->next;    //指向下一个元素地址
    p->next = s;          //新元素的地址给p
    return true;          //插入成功
}
/******************************************************************************/
//按位序插入:在第i个位置插入指定元素e
bool ListAfterInsert(LinkList* L, int i, int e)
{
    // 1，因为在第i个结点插入，所以需要找到第i-1个结点
    if (i < 1)
        return false; //传入的i不合法
    LNode* p;         //指针p记录当前位置
    p = (*L);            //p刚开始在表头
    int j = 0;        //当前p指向的是第几个结点,初始指向头，理解成第0个结点先
    while (p != NULL && j < i - 1)  //循环找到第i-1个结点
    {
        p = p->next;
        j++;
    }

    //2，插入
    return InsertNextNode(p, e);
}

思路：
单链表数据结构 C语言
（图3）

插入：前插（思路如图4）

/******************************************************************************/
//指定结点前插：在p节点前插入元素e
bool InsertFormerNode(LNode* p, int e)
{
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (p == NULL || s == NULL)
        return false;   //i不合法或malloc内存分配失败
    s->next = p->next;
    p->next = s;        //在p后插入空间s
    s->data = p->data;  //前一个位置的值给后一个
    p->data = e;        //相当于前插入元素e
    return true;
}
/******************************************************************************/
//按位序插入:在第i个结点插入e（头结点为第一个结点）
bool ListBeforeInsert(LinkList* L, int i, int e)
{
    // 1，找到第i-1个结点
    if (i <= 1)
        return false; //传入的i不合法
    LNode* p;         //指针p记录当前位置
    p = (*L);            //p刚开始在表头
    int j = 0;        //当前p指向的是第几个结点,初始指向头，理解成第0个结点先
    while (p != NULL && j < i-1)  //循环找到第i-1个结点
    {
        p = p->next;
        j++;
    }

    //2，插入
    return InsertFormerNode(p, e);
}

思路：
单链表数据结构 C语言
（图4）

删除：按位序删除（思路如图5）

/*-----------------------------------------------------------------------------*/
//按位序删除：删除第i个元素，并且用e返回删除元素的值
bool ListOrderDelete(LinkList* L, int i)
{
    //1,删除第i个元素，所以先找到第i-1个元素，以便断开连接
    if (i < 1)
        return false;
    LNode* p = (*L); //指针p记录当前位置；刚开始指向表头
    int j = 0;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    //2，删除并记录第i个元素
    if (p == NULL)
        return false;   //i不合法
    if (p->next == NULL)
        return false;   //i后无元素可删除
    LNode* q = p->next;
    p->next = q->next;
    int e;
    e = q->data;
    free(q);
    return true;
}

思路：
单链表数据结构 C语言
（图5）

删除：指定结点删除（思路如图6）

/******************************************************************************/
//指定结点删除：删除p结点的元素
bool DeleteNode(LNode* p)
{
    if (p->next == NULL)
        return false;
    LNode* q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);
    return true;
}//bug：p为最后一个节点时，删不了

/******************************************************************************/
//按结点删除：删除第i个结点的元素
bool ListNodeDelete(LinkList* L, int i)
{
    //1,删除第i个元素，所以先找到第i-1个元素，以便断开连接
    if (i < 1)
        return false;
    LNode* p = (*L); //指针p记录当前位置；刚开始指向表头
    int j = 0;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }

    //2，删除并记录第i个元素
    return DeleteNode(p);
}

思路：
单链表数据结构 C语言
（图6）

相关标签：笔记数据结构单链表 c语言 visual studio

上一篇：关于PHP优化速度的有关问题，文件缓存，影响会大吗

下一篇： PHP网页游戏学习之Xnova(ogame)源码解读（十六）_PHP

单链表数据结构 C语言

单链表-有头结点

仅用C语言可以构造出Python中Dict那种数据结构吗？

数据结构C语言：单链表

数据结构之---C语言实现二叉树的顺序存储

C语言实现双向非循环链表（不带头结点）的清空

C语言版单向链表的简单实现教程

浅谈PHP链表数据结构(单链表)_php实例

C_数据结构与算法（一）：C语言基础 - Rudolph_Browne

PHP实现双向链表、栈，c语言实现双向链表

数据结构---带头结点的双向链表的增删查改1（C语言实现）

数据结构（一）线性表-线性表的顺序表示顺序表 C语言实现

单链表 数据结构 C语言

单链表-有头结点

仅用C语言可以构造出Python中Dict那种数据结构吗？

数据结构C语言：单链表

数据结构之---C语言实现二叉树的顺序存储

C语言实现双向非循环链表（不带头结点）的清空

C语言版单向链表的简单实现教程

浅谈PHP链表数据结构(单链表)_php实例

C_数据结构与算法（一）：C语言基础 - Rudolph_Browne

PHP实现双向链表、栈，c语言实现双向链表

数据结构---带头结点的双向链表的增删查改1（C语言实现）

数据结构（一）线性表-线性表的顺序表示 顺序表 C语言实现

单链表数据结构 C语言

数据结构（一）线性表-线性表的顺序表示顺序表 C语言实现