devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言线性表的链式存储（详解）_c语言设计线性链表存储结构

作者：小小林熬夜学编程 | 2024-04-15 07:59:24

赞

踩

c语言设计线性链表存储结构

线性表的链式存储
线性表的顺序存储：用一块连续的内存空间

线性表的链式存储：不连续的内存空间

链表是由一系列的节点组成，每个节点包含两个域，一个是数据域，一个是指针域
链表的插入和删除原理
在这里插入图片描述单项链表框架的搭建
头文件
在这里插入图片描述具体的代码如下所示

#ifndef LINKLIST_H
#define LINKLIST_H
#include <stdio.h>
#include <stdlib.h>
// 链表节点
typedef struct LINKNODE {
	// 使用无类型的指针：该指针可以指向任何类型的数据
	void * data;
	struct LINKNODE* next;

}LinkNode;

// 链表结构体
typedef struct LINKLIST {
	LinkNode* head;
	int size;
	// 根据需要申请内存，没有容量的概念

}LinkList;

// 打印回调函数指针
typedef void(*PRINTLINKNODE)(void*);

// 初始化链表
LinkList* Init_LinkList();
// 在指定的位置插入
void Insert_LinkList(LinkList* list, int pos, void* data);
// 删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos);
// 获得链表的长度
void Size_LinkList(LinkList* list);
//查找链表
int Find_LinkList(LinkList* list,void * data);
// 打印链表节点
void Print_LinkList(LinkList* list, PRINTLINKNODE print);



// 返回第一个节点
void* Front_LinkList(LinkList* list);
// 释放链表内存
void FreeSpace_LinkList(LinkList* list);

#endif 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

c语言文件
在这里插入图片描述

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include "LinkList.h"

// 初始化链表
LinkList* Init_LinkList() {
	return NULL;
};
// 在指定的位置插入
void Insert_LinkList(LinkList* list, int pos, void* data) {

};
// 删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos) {

};
// 获得链表的长度
void Size_LinkList(LinkList* list) {
	//return 0;
};
//查找链表
int Find_LinkList(LinkList* list, void* data) {
	return 0;
};
// 打印链表节点
void Print_LinkList(LinkList* list, PRINTLINKNODE print) {

};

// 返回第一个节点
void* Front_LinkList(LinkList* list) {
	return 0;
};
// 释放链表内存
void FreeSpace_LinkList(LinkList* list) {

};

int main()
{

	printf("\n");
	system("pause");
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

数据结构中的基本概念

1：算法是为了解决问题二设计的

2：数据结构是算法需要处理问题的载体

3：数据结构与算法相辅相成

算法的表示方法

《只关注最高次项》

《如果最高次项的乘数不是1，就舍去》

《如果是常数》O（1）

malloc（）容量，表示的是容器的概念

1：插入新元素，空间不足申请更大的内存空间

2：旧的空间的数据拷贝到新的空间

3：释放旧空间的内存

4：新元素插入到新的空间

链表的基本概念

1：线性表的顺序存储：用一块连续的内存空间

2：线性表的链式存储：不连续的内存空间

3：链表是由一系列的节点组成，每个节点包含两个域，一个是数据域，一个是指针域

单项链表的实现思路及代码
项目结构
在这里插入图片描述

#ifndef LINKLIST_H
#define LINKLIST_H
#include <stdio.h>
#include <stdlib.h>
// 链表节点
typedef struct LINKNODE {
	// 使用无类型的指针：该指针可以指向任何类型的数据
	void * data;
	struct LINKNODE* next;

}LinkNode;

// 链表结构体
typedef struct LINKLIST {
	LinkNode* head;
	int size;
	// 根据需要申请内存，没有容量的概念

}LinkList;

// 打印回调函数指针
typedef void(*PRINTLINKNODE)(void*);


// 初始化链表
LinkList* Init_LinkList();
// 在指定的位置插入
void Insert_LinkList(LinkList* list, int pos, void* data);
// 删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos);
// 获得链表的长度
int Size_LinkList(LinkList* list);
//查找链表
int Find_LinkList(LinkList* list,void * data);
// 打印链表节点
void Print_LinkList(LinkList* list, PRINTLINKNODE print);



// 返回第一个节点
void* Front_LinkList(LinkList* list);
// 释放链表内存
void FreeSpace_LinkList(LinkList* list);


#endif 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

项目cpp文件代码LinkTableDirection.cpp
在这里插入图片描述LinkTableDirection.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include "LinkList.h"

// 自定义的数据类型
typedef struct PERSON {
	char name[64];
	int age;
	int score;

}Person;

// 打印函数
void MyPrint(void* data) {
	Person* p = (Person*)data;
	printf("Name = %s Age = %d Score = %d\n", p->name, p->age, p->score);
};


// 初始化链表
LinkList* Init_LinkList() {
	// 分配内存空间
	LinkList* list = (LinkList*)malloc(sizeof(LinkList));
	list->size = 0; 
	// 头节点，是不保存数据信息的，方便实现链表的封装
	list->head = (LinkNode *)malloc(sizeof(LinkNode));
	list->head->data = NULL;
	list->head->next = NULL;
	return list;

};
// 在指定的位置插入
void Insert_LinkList(LinkList* list, int pos, void* data) {
	   // 判断参数是否符合我们的要求，也就是判断参数是否为空
	if (list == NULL) {
		return;
	}
	if (data == NULL) {
		return;
	}
	if (pos < 0 || pos > list->size) {
		pos = list->size;
	}
	// 创建新的节点
	LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
	// 初始化,这个位置给出一个转换
	newnode->data = (void *)data;
	newnode->next = NULL;
	// 找节点，插入操作需要的是找到pos位置的前面一个节点,辅助指针变量
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++) {
		pCurrent = pCurrent->next;
	}
	//将新的节点放入链表
	newnode->next = pCurrent->next;
	pCurrent->next = newnode;
	list->size++;

};
// 删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos) {
	if (list == NULL) {
		return;
	}
	if (pos < 0 || pos >= list->size) {
		return;
	}
	// 查找删除节点的前一个节点
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++) {
		pCurrent = pCurrent ->next;

	}
	// 缓存删除的节点
	LinkNode* pDel = pCurrent->next;
	pCurrent->next = pDel->next;
	//释放删除节点的内存
	free(pDel);
	list->size--;



};
// 获得链表的长度
int Size_LinkList(LinkList* list) {
	return list->size;
	//return 0;
};
//查找链表
int Find_LinkList(LinkList* list, void* data) {
	if (list == NULL) {
		return -1;
	}
	if (data == NULL) {
		return -1;
	}
    // 遍历查找，使用辅助指针变量
	LinkNode* pCurrent = list->head->next;
	int i = 0;
	while (pCurrent != NULL) {
		if (pCurrent->data == data) {
			break;
		}
		i++;
		pCurrent = pCurrent->next;
	}
	return i;
	
};



// 返回第一个节点
void* Front_LinkList(LinkList* list) {
	// 返回的第一个节点就是头结点的下一个节点
	return list->head->next->data;
};

// 打印链表节点
void Print_LinkList(LinkList* list, PRINTLINKNODE print) {
	if (list == NULL) {
		return;
	}
	// 辅助指针变量
	LinkNode* pCurrent = list->head->next;
	while (pCurrent != NULL) {
		print(pCurrent->data);
		pCurrent = pCurrent->next;

	}
};

// 释放链表内存
void FreeSpace_LinkList(LinkList* list) {
	if (list == NULL) {
		return;
	}
	// 辅助指针变量
	LinkNode* pCurrent = list->head;
	while (pCurrent != NULL) {
	    // 缓存下一个节点
		LinkNode* pNext = pCurrent->next;
		pCurrent = pNext;
	}
	// 释放链表内存
	list->size = 0;
	free(list);
};


int main(void)
{
	void MyPrint(void* data);
	// 创建链表
	LinkList* list = Init_LinkList();
	// 创建数据
	Person p1 = { "aa",18,100 };
	Person p2 = { "hh",22,120 };
	Person p3 = { "zz",23,150 };
	Person p4 = { "qq",12,180 };
	Person p5 = { "ww",88,888 };

	// 将数据插入链表
	Insert_LinkList(list, 0, &p1);
	Insert_LinkList(list, 0, &p2);
	Insert_LinkList(list, 0, &p3);
	Insert_LinkList(list, 0, &p4);
	Insert_LinkList(list, 0, &p5);

	// 打印
	Print_LinkList(list, MyPrint);
	// 删除3号元素
	RemoveByPos_LinkList(list, 3);
	// 打印
	printf("-----------------------\n");
	Print_LinkList(list, MyPrint);

	// 返回第一个节点
	printf("-----------------------\n");
	Person* ret =  (Person *)Front_LinkList(list);
	printf("Name = %s Age = %d Score = %d\n", ret->name, ret->age, ret->score);

	// 销毁链表
	FreeSpace_LinkList(list);

	printf("\n");
	system("pause");
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193

链表运行结果展示
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/426650
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号