C语言开发的单链表实现的线程安全型数据结构.zip

# 线程安全型数据结构（单链表实现） # 一、引言 链表作为经典的数据结构，在计算机各个领域中都有着广泛的应用，为了满足用户需求，各种计算机软件的开发都需要应用到链表这一数据结构，由于程序运行在操作系统中，为了让程序更好更快更高效的在操作系统中运行，必须引入同步与互斥机制，那么实现一个线程安全性的链表就显得尤为重要，针对该问题，本课程设计将着力设计一个基于c语言实现的线程安全性链表，以期用于实践生活中。 ## 1.1 动机 在计算机系统内部，经常发生多个线程同时访问一个数据结构的现象；多个线程会同时修改或读取一个数据结构的内容；多个线程同时读写会引入读写冲突问题，这些操作如果不经过特殊处理，很容易导致读写操作无效；基于上述现象，本课程设计的动机就是为了保证读写正确性， 让程序运行速度更快，输出结果所需时间更少，为将来的研究者提供参考。 所以，本课程设计旨在设计一个能够保证线程安全的链表，在对链表同时进行多次插入删除打印等操作时，相互之间不会产生冲突，保证程序的正常运行，结果正确。 ## 1.2 要解决的问题 为实现保证线程安全的链表，本系统需要实现以下几个功能： - 用C语言设计链表这一数据结构，实现链表的插入、删除、打印等操作的函数，并保证其正确性。 - 设计一个测试函数实现对定义好的链表数据结构进行健壮性测试，保证链表自身的准确性和稳定性，继而保证对后序实现链表的线程安全测试准确 - 设计一个测试函数测试多个线程并发执行同时对其链表值修改时，不会产生冲突和错误。 - 利用读者写者模型设计一个测试函数测试多个线程并发执行同时对其链表值修改和读操作时，不会产生冲突和错误。 # 二、系统设计 ## 2.1 系统总体框架 以下是关于该课程设计的总体思路，其设计思路如图2.1所示： - 先构造单向链表的数据结构，然后用随机生成函数随机生成数对构造的数据结构多次进行测试，通过打印链表实现对链表的可视化，更加直观的验证链表是否正确，实现功能函数是否正确，保证之后验证并发操作和互斥操作不会出现问题； - 其次创建两个线程分别对链表多次进行插入节点操作和多次删除插入操作，通过简单的互斥机制实现两个线程同时启用，相互不会发生冲突，实现互斥模型，主要验证方式是打印要插入节点数，删除节点数，删除失败节点数，和最后链表的节点数来验证其是否实现的互斥同步模型正确； - 最后设计一个读者写者模型，让对链表的插入删除操作作为写者，统计节点数量和查找节点作为读者，通过屏幕的输出分析其构造的模型是否正确。  ​ 图2.1 系统框架图 ## 2.2 系统总体流程 图2.2是总的系统流程图：其中设计了一个选择菜单，用户可以根据需求对其设计的程序进行测试，最后测试完毕后，程序返回主菜单，再次选择功能进行测试，验证程序功能的准确性；利用随机生成数对程序进行测试排除主观因素对实验结果造成的影响也排除其偶然性。  ​ 图2.2系统总体流程图 ## 2.3 系统功能模块 - 验证数据结构的正确性 该模块设计思路是构造一个测试函数，初始化链表并随机生成一个链表，分别调用链表的多个实现不同功能的数据结构，每次调用完函数过后打印链表，通过打印的链表验证构造的数据结构的正确性。 - 验证并发互斥 构造一个测试函数，同时调用多次增加节点的线程和删除结点的线程，两个线程通过调用同一个互斥量对每一次删除操作或增加操作进行保护，防止冲突。 最后打印删除失败信息和节点数量信息验证其准确性。 - 验证读者写者模型 构造一个测试函数，调用多个读者写者模型线程，执行完毕后打印其链表的情况验证其模型是否实现成功。 # 三、数据结构设计 本课程设计主要用到的数据结构是单向链表：主要构造的函数如下所示，在创建构造读者写者模型中，让增加删除节点的数据结构作为读者，查找统计节点的数据结构作为写者： ## 3.1 单向链表数据结构 节点结构体信息 - 由于设计的是单链表，结点的数据结构较为简单，该数据结构包含两个变量，其中val为当前节点的值，数据类型为整数类型，next为当前数据结构类型的指针，即含义是当前节点的下一个节点的地址； ```c++ typedef struct MyLinkedList{ int val;//当前节点的值 struct MyLinkedList* next;//下一个节点的地址 } MyLinkedList; ``` 初始化链表 - 动态分配地址，创建一个头节点，由于初始化链表，头节点的下一个节点的地址为空；头节点只是用来表示链表，无含义也就没有值。 ```c++ MyLinkedList* myLinkedListCreate() { MyLinkedList* node = (MyLinkedList*)malloc(sizeof(MyLinkedList)); node->next = NULL; return node; } ``` 添加头节点 - 创建一个新的节点，动态分配地址给它，插入到链表的头部，函数的参数val为新节点的值，参数obj节点要添加到的链表。 ```c++ void myLinkedListAddAtHead(MyLinkedList* obj, int val) { MyLinkedList* head = (MyLinkedList*)malloc(sizeof(MyLinkedList)); head->val = val; head->next = obj->next; obj->next = head; } ``` 插入节点 - 该函数有三个变量，其中obj为要插入的链表，index是要插入的位值的索引值，val为要插入节点的值。实现也非常简单，先判断索引值是否和法，不合法则返回，再判断索引值是否超过了该链表的长度，超过则返回，上述条件都不成立后，用一个for循环，从头节点出发找到索引值，修改索引值前一个节点下一个节点的地址，使其指向新增节点，新增节点的下一个节点的地址为其上一个节点原下一个节点的地址，插入进去即可。 ```c++ void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) { if (index<0)return; MyLinkedList* node = obj; for (int i = 0; i<index; i++){ if (node->next == NULL)return; else node = node->next; } MyLinkedList* add = (MyLinkedList*)malloc(sizeof(MyLinkedList)); add->val = val; if (node->next != NULL)add->next = node->next; else add->next = NULL; node->next = add; } ``` 删除节点 - 删除节点和插入节点的实现思路也是一样，先解释该函数参数的含义，obj为要修改的链表，index为要删除的链表的节点位置，先判断索引值是否和法，不合法则返回，再判断索引值是否超过了该链表的长度，超过则返回，从头节点出发找到索引值将对应的节点删除即可。 ```c++ void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) { if (index<0)return; MyLinkedList* node = obj; for (int i = 0; i<index; i++){ if (node->next == NULL)return; else node = node->next; } if (node->next == NULL)return; else node->next = node->next->next; } ``` 删除尾节点 - 就是把链表的最后一个节点给删除，实现方式就是把链表原最后一个节点的上一个节点的下一个节点的地址设为空。 ```c++ void myLinkedListDeleteAtTail(MyLinkedList* obj) { MyLinkedList* nod