台州网站建设慕枫,wordpress浏览,个人如何开发小程序,国内wordpress云免备案本文参考朱战力老师的数据结构与算法--使用C语言一书 目录 文章目录 前言 一、链表是什么#xff1f; 二、具体实现 1.单链表的定义 2.初始化ListInitiate#xff08;SLNode **head#xff09; 3.求当前元素的个数ListLength#xff08;SLNode *head#xff09; 4.插入Lis… 本文参考朱战力老师的数据结构与算法--使用C语言一书 目录 文章目录 前言 一、链表是什么 二、具体实现 1.单链表的定义 2.初始化ListInitiateSLNode **head 3.求当前元素的个数ListLengthSLNode *head 4.插入ListInsertSLNode *headint iDataType x 5.删除ListDeleteSLNode *headint iDataType *x 6.取元素ListGetSLNode *headint iDataType *x 7.撤销单链表DestroySLNode **head 8.链表排序ListSort(SLNode* head) 9.链表查找ListSearch(SLNode* head, DataType target) 10.小试牛刀 总结 前言 本文所介绍的内容为数据结构与算法的基础内容--顺序表操作的实现笔者通过不断的深入学习发现后续的数据结构中包括堆栈、队列、串、数组、表、数和二叉树无不是通过线性表去实现故很好的理解线性表的操作对于广大的读者来说非常的有必要 一、链表是什么 本篇文章讨论线性表的链式存储结构和链式存储结构下操作的实现。链式存储结构存储线性表元素的方法是把存储有元素的结点用指针域构造成链。指针是指向物理内存单元地址的变量。我们把一个由元素域及一个或若干个指针域组成的结构体称为一个结点。其中数据域用来存放元素指针域用来构造元素之间的关联关系。链式存储结构的特点是元素间的逻辑关系表现在结点的链接关系上。链式存储结构的线性表称为链表。根据指针域的不同和结点构造链的方法不同链表主要有单链表、循环单链表和双向循环链表三种。其中单链表是最经常使用的链表。
二、具体实现
1.单链表的定义
代码如下示例
typedef struct Node {DataType data;struct Node* next;
}SLNode;2.初始化ListInitiateSLNode **head
代码如下示例
void ListInitiate(SLNode** head) { //初始化*head (SLNode*)malloc(sizeof(SLNode)); //申请头结点由head指示其地址(*head)-next NULL; //置结束标志NULL
}
说明在初始化操作前头指针参数head没有具体的地址值。在初始化操作时头指针参数head才得到了具体的地址值而这个地址值要返回给调用函数所以此时头指针参数head要设计成双重指针指针的指针类型。如果此时头指针参数head设计成指针类型那么调用函数将无法得到在初始化函数中被赋值的头指针参数head的值。
3.求当前元素的个数ListLengthSLNode *head
代码如下示例
int ListLength(SLNode* head) {SLNode* p head; //p指向头结点int size 0; //size初始为0while (p-next ! NULL) { //循环计数p p-next;size;}return size;
}
算法实现过程 4.插入ListInsertSLNode *headint iDataType x
代码如下示例
int ListInsert(SLNode* head, int i, DataType x) {//在带头结点的单链表head的第i给结点前插入一个存放元素x的结点//插入成功则返回1失败则返回0SLNode* p, * q;int j;p head;j -1;while (p-next ! NULL j i - 1) {//最终让指针p指向第i-1个结点p p-next;j;}if (j ! i - 1) {printf(插入元素位置参数错);return 0;}q (SLNode*)malloc(sizeof(SLNode)); //生成新结点q-data x; //新结点数据域赋值q-next p-next; //插入步骤1p-next q; //插入步骤2return 1;
}
算法实现过程 5.删除ListDeleteSLNode *headint iDataType *x
代码如下示例
int ListDelete(SLNode* head, int i, DataType* x) {//删除带头结点单链表head的第i0~size-1)个结点//被删除结点的数据域值由x带回删除成功则返回1失败则返回0SLNode* p, * s;int j;p head;j -1;while (p-next ! NULL p-next-next ! NULL j i - 1) {//循环结束时指针p指向第i-1个结点p p-next;j;}if (j ! i - 1) {printf(删除元素位置参数错);return 0;}s p-next; //指针s指向第i个结点*x s-data; //把指针s所指结点的数据域值赋予xp-next p-next-next; //删除free(s); //释放指针s所指结点的内存空间return 1;
}
算法实现过程 6.取元素ListGetSLNode *headint iDataType *x
代码如下示例
int ListGet(SLNode* head, int i, DataType* x) {SLNode* p;int j;p head;j -1;while (p-next ! NULL j i) {p p-next;j;}if (j ! i) {printf(取元素位置参数错);return 0;}*x p-data;return 1;
} 7.撤销单链表DestroySLNode **head
代码如下示例
void Destroy(SLNode** head) {SLNode* p, * p1;p *head;while (p ! NULL) {p1 p;p p-next;free(p1);}*head NULL;
} 8.链表排序ListSort(SLNode* head)
代码如下示例
void ListSort(SLNode* head) {if (head NULL || head-next NULL) {return; //空链表或只有一个结点无需进行排序}SLNode* p, * q;DataType temp;int len ListLength(head);for (int i 0; i len - 1; i){p head-next;q head-next-next;for (int j 0; j len - 1 - i; j){if (p-data q-data){temp p-data;p-data q-data;q-data temp;}p p-next;q q-next;}}
} 9.链表查找ListSearch(SLNode* head, DataType target)
代码如下示例
int ListSearch(SLNode* head, DataType target) {if (head NULL){return -1; //空链表查找失败}SLNode* p head-next;int index 0;while (p ! NULL){if (p-data target){return index; //找到目标值返回索引}p p-next;index;}return -1;
} 10.小试牛刀 代码如下示例
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h //包含printf
#includemalloc.h //包含malloc等函数
typedef int DataType; //定义DataType为int
#includeLinList.h //包含LinList.h头文件
void main() {SLNode* head; //定义头指针变量int i, x;ListInitiate(head); //初始化for (i 0; i 10; i) //插入10个元素{ListInsert(head, i, i 1);}ListDelete(head, 3, x); //删除元素4for (i 0; i ListLength(head); i) { //显示当前的元素ListGet(head, i, x); //取元素printf(%d , x); //显示}// 测试排序函数printf(\n\n排序后的链表\n);ListSort(head);for (i 0; i ListLength(head); i) { //显示当前的元素ListGet(head, i, x); //取元素printf(%d , x); //显示}// 测试查找函数int target 7;int index ListSearch(head, target);if (index ! -1) {printf(\n\n目标值 %d 在链表中的索引位置为 %d\n, target, index);}else {printf(\n\n目标值 %d 不在链表中\n, target);}Destroy(head); //撤销单链表
}
运行结果 总结 单链表是一种常见的数据结构它由节点组成每个节点包含数据和指向下一个节点的指针。在本文中我们实现了单链表的一些基本操作包括插入、删除、排序和查找等。 通过插入操作我们可以在链表中添加新的节点。删除操作可以帮助我们删除指定节点。排序操作可以根据特定的规则对链表进行排序使得节点按照一定的顺序排列。查找操作可以在链表中寻找特定的节点并返回其位置或者相关信息。 这些操作的实现需要注意指针的运用以确保链表的结构正确。在排序和查找过程中需要考虑不同的算法和复杂度选择合适的方法来提高效率。 总的来说通过实现这些操作我们可以灵活地对单链表进行操作实现了对节点的添加、删除、排序和查找等功能。熟练掌握这些操作为我们日后学习哈希表和二叉树都打下了非常坚实的基础。
