精品建站,网站内页seo,公司做网站那家好,免费域名和空间申请实验名称:设计单循环链表
(1#xff09;实验目的:掌握线性表的链式存储结构;掌握单循环链表及其基本操作的实现。
(2#xff09;主要内容:实现单循环链表的初始化、求数据元素个数、插入、删除、取数据元素等操作;用插入法建立带头结点的单循环链表;设计一个测试主函数验证…实验名称:设计单循环链表
(1实验目的:掌握线性表的链式存储结构;掌握单循环链表及其基本操作的实现。
(2主要内容:实现单循环链表的初始化、求数据元素个数、插入、删除、取数据元素等操作;用插入法建立带头结点的单循环链表;设计一个测试主函数验证所设计单循环链表的正确性。
1.实验目的
掌握线性表的链式存储结构;掌握单循环链表及其基本操作的实现。
2.问题描述
利用C语言设计实现单循环链表并实现初始化、求数据元素个数、插入、删除、取数据元素等基本操作。使用插入法建立带头结点的单循环链表并设计一个测试主函数验证所设计单循环链表的正确性。
3.基本要求
具体要求如下 设计一个结构体表示链表的节点包括数据域和指针域。 实现单循环链表的初始化操作即创建一个空链表。 实现求数据元素个数的操作即统计链表中已有的节点数。 实现插入操作在指定位置插入一个节点并将新节点链接到链表中。 实现删除操作删除指定位置的节点。 实现取数据元素的操作返回指定位置的节点值。 使用插入法建立带头结点的单循环链表即通过用户输入逐个插入节点来创建链表直到用户结束输入。 编写一个测试主函数验证所设计单循环链表的正确性包括对各个操作的测试。测试包括但不限于以下内容创建一个空链表并输出链表元素个数。 插入若干节点并验证插入后链表的正确性。 删除某个位置的节点并验证删除后链表的正确性。 取某个位置的节点值并输出验证结果。
4.测试数据
初始链表为空链表元素个数为0
插入后的链表元素10
插入后的链表元素5 15 10 20
删除后的链表元素15 20
取节点值的结果
Position 0: 15
Position 1: 20
Position 2: -1
5.算法思想
链表数据结构的基本操作包括初始化链表、获取链表元素个数、在指定位置插入节点、删除指定位置的节点、获取指定位置节点的值以及打印链表中的元素。其中链表是一种线性结构每个节点包括数据和指向下一个节点的指针头结点不包含数据。
该算法通过遍历链表的方式来找到指定位置的节点然后进行相应的操作。具体实现方法包括在空链表中插入第一个节点时直接将头结点指向新节点在链表头部插入节点时将新节点的指针指向原头结点再将头结点指向新节点在链表中间和尾部插入节点时在找到插入位置的前一个节点后将新节点的指针指向原位置的节点再将前一个节点的指针指向新节点删除节点时首先找到要删除节点的前一个节点将前一个节点的指针指向要删除节点的下一个节点然后释放要删除节点的内存空间获取节点值时找到指定位置的节点返回其数据域的值。
6.模块划分
initList()初始化链表返回头结点。listLength(Node* head)获取链表的元素个数。insertNode(Node* head, int position, int data)在链表指定位置插入节点。deleteNode(Node* head, int position)删除链表指定位置的节点。getNodeData(Node* head, int position)获取链表指定位置节点的值。printList(Node* head)打印链表中的元素。main()主函数。
7.数据结构
(1) 数据类型DataType定义如下
typedef struct {int number;int cipher;
} DataType;这个定义表示DataType结构体包含两个成员变量即number和cipher分别表示一个整数的数字和位数。
(2) 带头结点单循环链表结点的结构体定义如下
typedef struct SCLNode {DataType data;struct SCLNode* next;
} SCLNode;这个定义表示SCLNode结构体是一个带头结点的单循环链表的节点包含两个成员变量。其中data是存储数据元素的DataType类型的变量。next是指向下一个节点的指针类型为指向SCLNode结构体的指针。
通过这样的定义可以创建一个带头结点的单循环链表每个节点存储一个数据元素并且通过next指针连接起来形成循环链表。头结点的作用是指示链表的起始位置尾节点的next指针指向头结点形成循环。
8.源程序
#include stdio.h
#include stdlib.htypedef struct Node {int data;struct Node* next;
} Node;// 初始化链表返回头结点
Node* initList() {Node* head (Node*)malloc(sizeof(Node));head-next NULL; // 初始化时头结点指向NULL形成空链表return head;
}// 获取链表的元素个数
int listLength(Node* head) {int count 0;Node* current head-next;while (current ! NULL) {count;current current-next;}return count;
}// 在链表指定位置插入节点
void insertNode(Node* head, int position, int data) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data data;Node* current head;int count 0;while (current ! NULL count position) {current current-next;count;}newNode-next current-next;current-next newNode;
}// 删除链表指定位置的节点
void deleteNode(Node* head, int position) {Node* current head;int count 0;while (current-next ! NULL count position) {current current-next;count;}if (current-next ! NULL) {Node* temp current-next;current-next temp-next;free(temp);}
}// 获取链表指定位置节点的值
int getNodeData(Node* head, int position) {Node* current head-next;int count 0;while (current ! NULL count position) {current current-next;count;}if (current ! NULL)return current-data;elsereturn -1; // 返回-1表示节点不存在
}// 打印链表中的元素
void printList(Node* head) {Node* current head-next;while (current ! NULL) {printf(%d , current-data);current current-next;}printf(\n);
}int main() {Node* head initList();printf(初始链表为空链表元素个数为%d\n, listLength(head));insertNode(head, 0, 10); // 在空链表中插入第一个节点printf(插入后的链表元素);printList(head);insertNode(head, 0, 5); // 在链表头部插入节点insertNode(head, 1, 15); // 在链表中间插入节点insertNode(head, 3, 20); // 在链表尾部插入节点printf(插入后的链表元素);printList(head);deleteNode(head, 0); // 删除头结点deleteNode(head, 1); // 删除链表中的某个节点deleteNode(head, 2); // 删除尾节点printf(删除后的链表元素);printList(head);int data1 getNodeData(head, 0); // 取链表头结点的数据int data2 getNodeData(head, 1); // 取链表中间某个节点的数据int data3 getNodeData(head, 2); // 取链表尾节点的数据printf(取节点值的结果\n);printf(Position 0: %d\n, data1);printf(Position 1: %d\n, data2);printf(Position 2: %d\n, data3);return 0;
}
9.测试情况 进行测试结果分析
初始化链表后链表为空元素个数为0。
在空链表中插入第一个节点插入后的链表元素为10。可以看到插入操作正常。
在链表头部插入节点5链表中间插入节点15链表尾部插入节点20。插入后的链表元素为5 15 10 20。可以看到在不同位置插入节点的操作正常。
删除头结点删除链表中的某个节点删除尾节点。删除后的链表元素为5 10。可以看到删除操作正常。
取链表头结点的数据取链表中间某个节点的数据取链表尾节点的数据。取节点值的结果如下
Position 0: 5 Position 1: 10 Position 2: -1 可以看到成功获取了节点的值并且当位置越界时返回了-1。说明获取节点值的功能正常。
综上所述根据测试结果代码实现了链表的基本操作并且功能正常。
描述存在的问题及建议
存在的问题是在插入和删除节点时没有进行越界检查可能导致访问非法内存。建议在插入和删除节点的代码中增加对位置的合法性检查确保不会越界。
另外代码中的打印函数printList()可以优化避免每次都要遍历整个链表才能打印出结果。可以考虑在插入、删除和修改节点时维护链表的长度并在需要打印时直接使用链表长度进行循环打印。这样可以提高效率。
