C++实现单链表基础操作：初始化、长度计算与元素插入
需积分: 9 32 浏览量
更新于2024-09-14
收藏 23KB DOC 举报
本篇文档是关于C++版数据结构上机实验中的单链表操作，主要涵盖了单链表的基本概念、数据结构以及关键函数的实现。单链表是一种线性数据结构，每个节点由一个数据元素和一个指向下一个节点的指针组成。在C++中，我们首先定义了`ElemType`用于存储元素类型，以及`LNode`结构体表示链表节点，包括`data`和`next`两个成员。
1. **初始化单链表**:
`init`函数用于动态分配内存并创建一个新的链表节点。如果内存分配成功，返回`OK`；否则返回`ERROR`。初始链表的长度为`LIST_INIT_SIZE`，并且第一个节点的`next`指针为`NULL`。
2. **求表长**:
`ListLength`函数通过遍历链表，计算节点总数来确定链表的长度。它通过一个计数器`j`递增直到遇到`NULL`节点，返回计数器的值。
3. **获取表中第i个元素的值**:
`GetElem`函数根据索引`i`从头节点开始遍历链表，找到目标位置后返回节点的`data`值。若索引越界或链表不包含相应元素，返回`ERROR`。
4. **判断元素是否在链表中**:
`LocateElem`函数遍历链表查找指定元素`e`，如果找到则返回该元素的相对位置（从0开始计数），否则返回`0`，表示元素不在链表中。
5. **打印链表元素值**:
`PrintList`函数用于输出链表中的所有元素值。从头节点开始，逐个访问节点并输出其数据，每输出一个元素后换行。
6. **插入操作**:
`ListInsert`函数实现将新元素`e`插入到给定链表的指定位置`i`。首先找到插入位置前的节点，然后在该节点之后插入新节点，更新指针关系。
这些函数展示了单链表的基本操作，包括创建、查找、修改和显示。在实际编程中，链表常用于需要频繁插入和删除元素的数据结构场景，由于它不需要连续的存储空间，所以在处理大量数据时具有一定的优势。通过理解并熟练掌握这些函数，可以有效地实现和操作单链表数据结构。
#include<iostream.h>
#include<malloc.h>
#include<conio.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ERROR 0
#define OK 1
typedef int ElemType;
struct LNODE
{
ElemType data;
struct LNODE *next;
};
typedef struct LNODE LNode;
typedef struct LNODE *LinkList;
//初始化单链表
int init(LinkList &L)
{
L=(LNode *)malloc(sizeof(LNode));
if(!L) return(ERROR);
L->next=NULL;
return OK;
}/*init */
//求表长
int ListLength(LinkList L)
{
int j=0;
while (L->next)
{
L=L->next;
j++;
}
return j;
}
//获取表中第 i 个元素的值
int GetElem(LinkList L,int i,ElemType &e)
{
LinkList p; int j;
下载后可阅读完整内容，剩余4页未读，立即下载
2019-04-12 上传
2012-09-10 上传
2016-11-12 上传
2011-07-15 上传
2013-01-31 上传
2023-02-06 上传
