下载文档原格式
实验一熟悉数据结构上机环境1 实验目的1）熟悉Turbo C 2.0 上机环境2）掌握C语言与伪码之间的关系，能够很好把伪码转换为C语言程序2 实验内容1）熟悉C语言开发环境2）编写运用C语言程序3实验结果4实验分析实验二顺序表的实现1 实验目的掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构上的运算。
2 实验内容编写程序实现线性表的顺序存储表示的各种基本操作，如插入、删除、查找等。
3实验结果4实验分析实验三单链表的实现1 实验目的掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在链接存储结构上的运算。
2 实验内容编写程序实现线性表的链接存储表示的各种基本操作，如插入、删除、查找等。
3实验结果4实验分析实验四顺序栈的实现1 实验目的1）掌握栈的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
2）掌握栈的特点，即先进后出。
3）掌握栈的基本运算，如入栈与出栈等运算在顺序存储结构上的实现。
2 实验内容编写程序实现栈的顺序存储结构的实现。
3实验结果4实验分析实验五顺序队列的实现（1）1 实验目的1）掌握队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
2）掌握队列的特点，即先进先出。
3）掌握队列的基本运算，如入队与出队等运算在顺序存储结构的实现。
2 实验内容编写程序实现队列在顺序存储结构中的实现及循环队列的应用。
3实验结果4实验分析实验六顺序队列的实现（2）-----约瑟夫环问题的实现1 实验目的1）掌握队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。
2）掌握队列的特点，即先进先出。
3）掌握队列的基本运算，如入队与出队等运算在顺序存储结构的实现。
2 实验内容编写程序实现队列在顺序存储结构中的实现及循环队列的应用。
3实验结果4实验分析实验七稀疏矩阵转置算法的实现1 实验目的1）掌握稀疏矩阵的两种压缩方法的特点和适用范围，领会稀疏矩阵运算采用的处理方法。
《算法与数据结构》实验报告实验一约瑟夫环问题（2学时）将编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个正整数作为报数上限值m，从第一个开始按顺时针方向自1开始报数，报到m时停止报数。
报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。
试设计一个程序求出出列顺序。
实验二链表的操作（4学时）编一程序：①建立一个数据域为1至10的带头结点的链表；②将此链表就地逆转。
链表的类型说明如下：#include <iostream.h>#include <stdlib.h>class Node{public:int data;Node *next;Node( ){next=0;}friend class LinkList;};//Nodeclass LinkList {Node *head;public:LinkList( ) { head=new Node(); }void Create(); //创建长度为n的单链表int GetElem(int i); //返回第i个元素值Node* Locate(int e); //返回第一个与e匹配的元素结点指针bool IsEmpty( ) {return (head->next==0);} //判断是否为空链表void Insert(int x, int i ); //在第i个结点之前插入元素值为x的结点int Delete ( int i ); //删除第i个结点，并返回其元素值void Clear( ); //清空链表void print( );};// LinkList实验三栈的应用－中缀表达式的求值（4学时）表达式求值是计算机实现程序设计语言中的基本问题之一，也是栈应用的一个典型例子，通过本实验，对输入的一个表达式进行求值。
说明：表达式中只包含＋、－、×、/ 运算及（和）。
《数据结构》实验报告模板(附实例)---实验一线性表的基本操作实现实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。
2、巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。
二、实验内容√ 1、单链表的表示与操作实现 ( * )2、约瑟夫环问题3、Dr.Kong的艺术品三、实验要求1、按照数据结构实验任务书，提前做好实验预习与准备工作。
2、加“*”题目必做，其他题目任选；多选者并且保质保量完成适当加分。
3、严格按照数据结构实验报告模板和规范，及时完成实验报告。
四、实验步骤（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法、函数实现、程序编码、调试与分析、总结、附流程图与主要代码）㈠、数据结构与核心算法的设计描述（程序中每个模块或函数应加注释，说明函数功能、入口及出口参数）1、单链表的结点类型定义/* 定义DataType为int类型 */typedef int DataType;/* 单链表的结点类型 */typedef struct LNode{ DataType data;struct LNode *next;}LNode,*LinkedList;2、初始化单链表LinkedList LinkedListInit( ){ // 每个模块或函数应加注释，说明函数功能、入口及出口参数 }3、清空单链表void LinkedListClear(LinkedList L){// 每个模块或函数应加注释，说明函数功能、入口及出口参数}4、检查单链表是否为空int LinkedListEmpty(LinkedList L){ …. }5、遍历单链表void LinkedListTraverse(LinkedList L){….}6、求单链表的长度int LinkedListLength(LinkedList L){ …. }7、从单链表表中查找元素LinkedList LinkedListGet(LinkedList L,int i){ //L是带头结点的链表的头指针，返回第 i 个元素 }8、从单链表表中查找与给定元素值相同的元素在链表中的位置LinkedList LinkedListLocate(LinkedList L, DataType x){ …… }9、向单链表中插入元素void LinkedListInsert(LinkedList L,int i,DataType x) { // L 为带头结点的单链表的头指针，本算法// 在链表中第i 个结点之前插入新的元素 x}10、从单链表中删除元素void LinkedListDel(LinkedList L,DataType x){ // 删除以 L 为头指针的单链表中第 i 个结点 }11、用尾插法建立单链表LinkedList LinkedListCreat( ){ …… }㈡、函数调用及主函数设计（可用函数的调用关系图说明）㈢程序调试及运行结果分析㈣实验总结五、主要算法流程图及程序清单1、主要算法流程图：2、程序清单（程序过长，可附主要部分）说明：以后每次实验报告均按此格式书写。
数据结构单链表实验报告一、实验目的本次实验的主要目的是深入理解和掌握数据结构中的单链表概念、原理和操作方法，通过实际编程实现单链表的创建、插入、删除、查找等基本操作，提高对数据结构的实际应用能力和编程技能。
二、实验环境本次实验使用的编程语言为C+＋，编程工具为Visual Studio 2019。
三、实验原理单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据域和指针域。
指针域用于指向下一个节点，从而形成链表的链式结构。
单链表的优点是可以动态地分配内存，灵活地插入和删除节点，但其缺点是访问特定位置的节点需要从头开始遍历，时间复杂度较高。
四、实验内容（一）单链表的创建创建单链表的基本思路是依次创建节点，并将节点通过指针链接起来。
以下是创建单链表的代码实现：｀｀｀cppinclude ＜iostream>using namespace std;／／定义链表节点结构体struct ListNode ｛int data;ListNode next;ListNode(int x) ： data(x)， next(NULL) ｛｝｝；／／创建单链表ListNode createList(）｛int num, value;cout ＜＜＂请输入节点个数: ＂；cin ＞＞ num;ListNode head ＝ NULL;ListNode tail ＝ NULL;for （int i ＝ 0; i ＜ num; i+＋）｛cout ＜＜＂请输入第＂＜＜ i ＋ 1 ＜＜＂个节点的值: ＂；cin ＞＞ value;if （head ＝＝ NULL) ｛head ＝ newNode;tail ＝ newNode;｝ else ｛tail>next ＝ newNode;tail ＝ newNode;｝｝return head;｝｀｀｀（二）单链表的插入操作单链表的插入操作可以分为在表头插入、在表尾插入和在指定位置插入。
链表c语言经典例题
链表是计算机科学中的经典数据结构之一，常用于存储和操作动态数据。
以下是一些常见的链表例题，可以帮助理解链表的基本操作和应用。
1. 链表的创建：
- 创建一个空链表。
- 创建一个包含指定节点值的链表。
2. 链表的插入操作：
- 在链表的头部插入一个节点。
- 在链表的尾部插入一个节点。
- 在指定位置插入一个节点。
3. 链表的删除操作：
- 删除链表的头节点。
- 删除链表的尾节点。
- 删除指定数值的节点。
4. 链表的查找操作：
- 查找链表中指定数值的节点。
- 查找链表的中间节点。
5. 链表的逆序操作：
- 反转整个链表。
- 反转链表的前 N 个节点。
- 反转链表的一部分区间内的节点。
6. 链表的合并操作：
- 合并两个有序链表，使其有序。
- 合并 K 个有序链表，使其有序。
7. 链表的环检测：
- 判断链表中是否存在环，若存在，则返回环的起始节点。
8. 链表的拆分操作：
- 将一个链表按照奇偶位置拆分成两个链表。
以上是一些链表的经典例题，通过解答这些例题，可以加深对链表结构和基本操作的理解。
在编写对应的 C 语言代码时，需要注意链表节点的定义、指针的使用以及内存的动态分配和释放等问题。
数据结构课程设计实验报告实验一链表部分选题为：2.4.3—城市链表1、需求分析（1）创建一个带有头结点的单链表。
（2）结点中应包含城市名和城市的位置坐标。
（3）对城市链表能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。
（4）能够对每次操作后的链表动态显示。
2、概要设计为了实现以上功能，可以从以下3个方面着手设计。
（1）主界面设计为了实现城市链表相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以系统的各项子功能，方便用户使用本程序。
本系统主控菜单运行界面如下所示。
（2）存储结构设计本系统主要采用链表结构类型来表示存储在“城市链表”中的信息。
其中链表结点由4个分量组成：城市名name、城市的横坐标posx、城市的纵坐标posy、指向下一个结点的指针next。
（3）系统功能设计本程序设计了9个功能子菜单，其描述如下：①建立城市链表。
由函数creatLink()实现。
该功能实现城市结点的输入以及连接。
②插入链表记录。
由函数insert()实现。
该功能实现按坐标由小到大的顺序将结点插入到链表中。
③查询链表记录。
由searchName（）函数和searchPos（）函数实现。
其中searchName（）实现按照城市名查询的操作，searchPos（）实现按照城市坐标查询的操作。
④删除链表记录。
由delName（）函数和delPos（）函数实现。
其中delName（）函数实现按照城市名删除的操作，delPos（）函数实现按照城市坐标删除的操作。
⑤ 显示链表记录。
由printList （）函数实现。
该功能实现格式化的链表输出操作，可以显示修改后的链表状态。
⑥ 更新链表信息。
由update （）函数实现。
该功能实现按照城市名更新城市的坐标信息。
⑦ 返回城市坐标。
由getPos （）函数实现。
该功能实现给定一个已存储的城市，返回其坐标信息的操作。
⑧ 查看与坐标P 距离小于等于D 的城市。
由getCity （）函数实现。
数据结构单链表实验报告一、实验目的1、深入理解单链表的数据结构及其基本操作。
2、掌握单链表的创建、插入、删除、查找等操作的实现方法。
3、通过实际编程，提高对数据结构和算法的理解和应用能力。
二、实验环境1、操作系统：Windows 102、编程语言：C 语言3、开发工具：Visual Studio 2019三、实验原理单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据域和指针域。
指针域用于指向下一个节点，从而形成链表的链式结构。
单链表的基本操作包括：1、创建链表：通过动态分配内存创建链表的头节点，并初始化链表为空。
2、插入节点：可以在链表的头部、尾部或指定位置插入新的节点。
3、删除节点：根据给定的条件删除链表中的节点。
4、查找节点：在链表中查找满足特定条件的节点。
四、实验内容（一）单链表的创建｀｀｀cinclude ＜stdioh>include ＜stdlibh>／／定义链表节点结构体typedef struct Node ｛int data;struct Node next;｝ Node;／／创建单链表Node createList(）｛Node head ＝（Node)malloc(sizeof(Node)）；if （head ＝＝ NULL) ｛printf(＂内存分配失败！＼n"）；return NULL;｝head>data ＝ 0;head>next ＝ NULL;return head;｝int main(）｛Node list ＝ createList(）；／／后续操作return 0;｝｀｀｀在创建单链表时，首先为头节点分配内存空间。
若内存分配失败，则提示错误信息并返回｀NULL`。
成功分配内存后，初始化头节点的数据域和指针域。
（二）单链表的插入操作插入操作分为三种情况：头部插入、尾部插入和指定位置插入。
1、头部插入｀｀｀cvoid insertAtHead(Node head, int data) ｛Node newNode ＝（Node)malloc(sizeof(Node)）；if （newNode ＝＝ NULL) ｛printf(＂内存分配失败！＼n"）；return;｝newNode>data ＝ data;newNode>next ＝ head>next;head>next ＝ newNode;｝｀｀｀头部插入时，创建新节点，将新节点的数据域赋值，并将其指针域指向原头节点的下一个节点，然后更新头节点的指针域指向新节点。
实验一C语言数据类型的使用[实验目的]复习C语言的使用方法，特别是指针、结构体的内容，同时也为以后的各个实验做准备。
[实验内容及要求]1．建立一个简单链表（静态链表），它由3个学生数据的结点组成，每个结点包括学号和成绩。
输出各结点中的数据。
(根据题目完善程序)#define NULL 0struct student{long num；float score；struct student *next；} stu；typedef struct student stu;main (){ stu a,b,c,*head,*p；a.num=99101；a.score=89.5；b.num=99103；b.score=90；c.num=99107；c.score=85；head=&a；a.next=&b；b.next=&c；c.next=NULL；p=head；do{printf（“%ld%5.1f\n”, ）；/*输出学号和成绩*/p=p->next；}while( )；}输出：2．建立一个动态链表，它由3个学生数据的结点组成，每个结点包括学号和成绩。
输出各结点中的数据。
#define NULL 0#define LEN sizeof(struct student)struct student{long num；float score；struct student *next；}；int n；struct student *creat(void) /*尾插法建立链表*/{struct student *head；struct student *p1, *p2；n=0；p1=p2=(struct student *)malloc(sizeof(struct student))；scanf（“%ld,%f”,&p1->num,&p1->score)；head=NULL；while(p1->num!=0){n=n+1；if (n= =1)head=p1；else p2->next=p1；p2=p2->next ；p1=(struct student *)malloc(LEN)；scanf（“%ld,%f”,&p1->num,&p1->score)；}p2->next=NULL；return( head )；}void print（struct student *head）{struct student *p；printf（“\nNow,These %d records are：\n”,n)；p=head；if(head!=NULL)do{printf（“%ld%5.1f\n”,p->num,p->score)；}while(p!=NULL)；}main(){struct student *head；printf（“input records：\n”）；head=creat()；print(head)；}输入：输出：[思考题]1．将上题链表中学生的成绩从低到高排列输出，要求每行一个，包括学号和成绩。
数据结构实验报告（⼀）线性表的应⽤实验说明数据结构实验⼀ 线性表的实验——线性表的应⽤⼀、实验⽬的通过本实验使学⽣了解线性表的⼀种简单应⽤，熟悉线性表顺序存储与链式存储的特性，特别训练学⽣编程灵活控制链表的能⼒，为今后编程控制更为复杂的数据结构奠定基础。
⼆、实验内容1.⽤顺序表和链表分别分别编程实现教材中例⼦2-1与2-2。
要求：（1）只能⽤C语⾔编程实现；（2）完全保持书中算法2.1与算法2.2形式，不允许有任何变化，除⾮语法上不允许;所调⽤各函数参照书中19页的功能描述，其中函数名、参数个数及性质、函数功能必须与书中完全⼀致，不能有变化。
2.利⽤线性表表⽰⼀元多项式完成多项式的加、减、乘、求导、求值运算。
要求：（1）输⼊的⼀元多项式可以采⽤只输⼊各项的系数与指数这种简化的⽅式。
如对于多项式2x2+6x5，输⼊可为： 2,2 6,5 这样的简单形式。
（2）遇到有消项时应当处理，如2x2+6x5与3x2-6x5进⾏相加时，结果为5*x^2。
（3）当给定x的值时，能计算表达式相加或相减的结果。
（4）操作的结果放⼊⼀个新线性表中，原来的两个表达式存储表⽰不变，也可以不是产⽣新的线性表，⽽是将两上线性表合并为⼀个。
（5）要求程序功能模块划分合理（每个函数功能单⼀、可重⽤性好），使⽤空间尽可能少，算法尽可能⾼效。
实验报告1.实现功能描述使⽤线性表表⽰⼀元多项式完成多项式的加、减，乘，求导、求值运算。
2.⽅案⽐较与选择（1）因为使⽤的是线性表，所以主要⽅案有数组法和链表法。
（2）从时间复杂度来说，使⽤数组法更优；从空间复杂度来说，链表法更优。
因为数组法是指定好空间的，若式⼦⼤⼩超出设置⼤⼩，那程序必然出错；若式⼦⼤⼩⼩于设置⼤⼩，那就意味着有多余的空间被浪费了。
综合来讲，若计算式⼦较为庞⼤，使⽤链表法更佳；相反，若计算式⼦较⼩，数组法更佳。
3.设计算法描述（1）单个项式的数据存储使⽤了结构体，数组法是在⼀个结构体中定义两个⼀维数组；链表法是通过⼀个结构体作为⼀个节点，通过next指针连接起来。
实验二 链表的基本操作
一、实验目的
掌握链表的基本概念、结构的定义，通过设计程序掌握链表上的基本操作：建立、
插入、删除、查找以及链表合并等，并理解线性表的两种存储结构：顺序表和链表的区别。 二、实验准备 1. 复习C语言中指针的用法，特别是结构体的指针的用法。 2. 了解链表（含带头结点的链表、循环链表）的概念，链表的结构定义方法。 单链表是线性表的链式存储表示，是用一组任意的存储单元依次存储线性表的数据元素。因此，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置），而这部分就是用指针来完成的。 3. 掌握线性表在链式存储结构上实现基本操作：建立、查找、插入、删除等算法。 在实现这些算法的时候，要注意判断输入数据的合法性，除此之外还要要注意以下内容： 在实现查找的时候，首先要判断该顺序表是否为空，其次要判断查找后的结果(查到时输出查到的数据，未查到时给出相关提示)。 在实现插入的时候，由于是链式存储，它可以随机产生和回收存储空间，所以它不要判断线性表是否为满，但仍需判断要插入的位置是否合法，原因同实验一，其次要注意插入的时候语句的顺序不可颠倒，否则出错。 例如： p
s
s所指向结点要插入在p所指向的结点之后，则：
正确形式：s->next=p->next； p->next=s； 错误形式：p->next=s； s->next=p->next(因为此时p->next已经指向s了) 在实现删除的时候，首先要判断线性表是否为空，为空则不能删除；其次在删除后要回收空间。 p
s
例如：删除如上图所示s所指向的结点
p->next=p->next->next； free(s); 4. 链表部分相关操作代码：
⑴ 单链表的结构定义：
#include typedef int elemtype; typedef struct lnode { elemtype data; struct lnode *next; }*linklist; ⑵ 建立单链表的算法 int n; /*n作为整个程序的全局变量*/ linklist *creat(void) { linklist *head, *p1, *p2; n=0; p1=p2=(linklist *)malloc(sizeof(linklist)); scanf(“%d”,&p1->data); head=null; while(p1->data!=0) { n=n+1; if(n==1) head=p1; else p2->next=p1; p2=p1; p1=(linklist *)malloc(sizeof(linklist)); scanf(“%d”,&p1->data); } p2->next=null; return(head); } ⑶ 单链表的插入算法 int insert(linklist *head, int i,elemtype e) { linklist *p, *s; int j; p=head; j=0; while(p && j { p=p->next; ++j;
}
if(!p||j>i-1) { printf(“无法插入”)； return 0; } s=(linklist *)malloc(sizeof(lnode)); s->data=e; s->next=p->next; p->next=s; return 1; } ⑷ 单链表的删除算法 int deltree(linklist *head,int i,elemtype e) { linklist *p, *q; int j;l p=head; j=0; while(p->next && j { p=p->next; ++j; } if(!(p->next)||j>i-1) { printf(“无法删除”); return 0; } q=p->next;p->next=q->next; e=q->data; free(q); return 1; }
三、实验内容 1. /*函数link()的功能是将带头结点的单链表l2链接到l1的后面，程序中存在几处错误，请改正并调试运行*/ #include "linklist.h" void link(linklist l1,linklist l2) {linklist p,q; p=l1; while (p->next) p=q->next; q=l2; p->next=q; free(l2); } void main() { linklist l1,l2; l1=creat2(); /*生成带头结点的单链表l1*/ print(l1); /*输出单链表l1*/ l2=creat2(); /*生成带头结点的单链表l2*/ print(l2); /*输出单链表l2*/ link(l1,l2); /*将单链表l2链接到l1的后面*/ print(l1); /*输出单链表l1*/ } 2./* 编写一个函数perm,将带头结点单链表中的所有值为奇数的结点集中到链表的左边，值为偶数的结点集中到链表的右边*/ #include "linklist.h" linklist perm(linklist head) { linklist pre,p; pre=head; p=head->next; while (p && p->data%2==1) { pre= p ; p= p->next ; } while (p) { if (p->data%2==1) { pre->next=p->next; p->next=head->next; head->next=p; p=pre->next; } else { pre=p; p=p->next; } } } /*主函数,请勿改动,请将perm中的函数补充完整*/ int main() { linklist head; head=creat2(); /*尾插法建立单链表*/ print(head); /*输出单链表head*/ perm(head); print(head); delList(head); return 0; } 3.设计程序：/*建立一个带头结点的单链表，然后将该链表进行倒置。存放*/ #include "linklist.h" void verge(linklist head) {linklist p,q; p=head->next;head->next=NULL; while(p) {q =p->next ; p->next= =null ; head->next=p; p=q; } } /*主函数,请勿改动,请将verge中的函数补充完整*/ int main() { linklist head; head=creat2(); /*尾插法建立单链表*/ print(head); /*输出单链表head*/ verge(head); /*倒置*/ print(head); delList(head); return 0; } 4、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。 #include #include #define ERROR 0 #define OK 1 typedef int ElemType; /*定义表元素的类型*/ typedef struct LNode{ /*线性表的单链表存储*/ ElemType data; struct LNode *next; }LNode,*LinkList;
LinkList CreateList(int n);/构造顺序表的长度 */ void PrintList(LinkList L); /*输出带头结点单链表的所有元素*/ int GetElem(LinkList L,int i,ElemType *e); /*在顺序线性表L中 ，当第i个元素存在时，将其赋值为e */
LinkList CreateList(int n){ LNode *p,*q,*head; int i; head=(LinkList)malloc(sizeof(LNode)); head->next=NULL; p=head; for(i=0;i q=(LinkList)malloc(sizeof(LNode)); printf("input data %i:",i+1); scanf("%d",&q->data); /*输入元素值*/ q->next=NULL; /*结点指针域置空*/ p->next=q; /*新结点连在表末尾*/ p=q; } return head; }/*CreateList*/
void PrintList(LinkList L){ LNode *p; p=L->next; /*p指向单链表的第1个元素*/ while(p!=NULL){
