链表实验报告总结

1 / 40 链表实验报告总结 数据结构实验报告 姓名； 方钢 学号： 20165567 专业： 电子商务 班 级： 10-1班 指导教师： 实验时间： 实验地点：新区实验楼 4 楼 单链表实验 1.实验内容和要求 实验要求 本次实验中的链表结构均为带头结点的单链表； 链表结构定义，算法实现放入库文件 “” ； 运算和变量命名直观易懂，并有相应的注释 2 / 40 实验内容 求链表中第 i个结点的指针，若不存在，则返回 NULL。 在第 i个结点前插入值为 x的结点。 删除链表中第 i个元素结点。 在一个递增有序的链表 L 中插入一个值为 x的元素，并保持其递增有序特 性。 将单链表中的奇数项和偶数项结点分解开，申请 2 个头结点，把分开的奇数项和偶数项分别链接到这 2 个头结点上，然后再 将 这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照 3 / 40 求解 结果。 求两个递增有序链表 L1和 L2中的公共元素，并以同样方式连接成链表 L3。 2.实验目的 理解线性表的链式存储结构。 熟练掌握单链表结构及有关算法的设计。 根据具体问题的 需要，设计出合理的表示数据的链表结构，并设计相关 算法。 3.数据结构设计 求链表中第 i个结点的指针，若不存在，则返回 NULL。 实验代码 node *L,*p; 4 / 40 int i; createNode(*&L); /尾插法创建一个链表， cout p=L-next; while(p) coutdata p=p-next; cout cout cini; locateNode (L, i, &p ); if(p!=NULL) coutdata else 5 / 40 cout destroyList(L); /销毁链表，释放 heap 内存 _CrtDumpMemoryLeaks(); /debug 模式下检测是否内存泄漏 测试截图 在第 i个结点前插入值为 x的结点。 实验代码 node *L,*p; int i; elementType x; createNode(L); /尾插法创建一个链表， cout p=L-next; 6 / 40 while(p) coutdata p=p-next; cout cout cout cinx; cout cini; /调用插入函数，并检查是否插入成功 if(insertNode (L,i,x) cout cout /打印插入元素后的链表 cout p=L-next; while(p) 7 / 40 coutdata p=p-next; cout cout destroyList(L); /销毁链表，释放heap内存 _CrtDumpMemoryLeaks(); /debug 模式下检测是否内存泄漏 测试截图 删除链表中第 i个元素结点。 实验代码 node *L,*p; int i; elementType x; 8 / 40 creatNode(L); /尾插法创建一个链表， cout p=L-next; while(p) coutdata p=p-next; cout cout cout cini; /调用删除函数，并检查是否删除成功 if(deleteNode (L,i) cout cout /删除节点后的链表 cout cout p=L-next; 9 / 40 while(p) coutdata p=p-next; cout destroyList(L); /销毁链表，释放 heap 内存 _CrtDumpMemoryLeaks(); /debug 模式下检测是否内存泄漏 测试截图 实验报告 实验目的：学生管 理系统 实验要求： 1.建表 2.求表长 10 / 40 3.插入 4.查找 5.删除 6.列表 7.退出 源程序： #include #include #include #define MaxSize 1000 typedef struct 11 / 40 char xh40; char xm40; int cj; DataType; /学生的结构 typedef struct DataType dataMaxSize; /定义表的数据类型 int length; / 数 据 元 素 分 别 放 置 在 data0 到datalength-1当中 SqList; /表的结构 void liebiao(SqList *L) / 12 / 40 int k,n; char q; printf(请输入 ,输入学生的个数： n); fflush(stdin); scanf(%d,&n); for(k=0;k printf(请输入学生学号 n); scanf(%s,L-datak.xh); printf(请输入学生名字 n); scanf(%s,L-datak.xm); 13 / 40 printf(请输入学生成绩 n); scanf(%d,&L-datak.cj); 建立表格 L-length=n; void qb(SqList *L) /全部输出 int k,w; for(k=0;klength;k+) 14 / 40 w=k+1; printf(第 %d位学生： ,w); printf(%s %s %dn,L-datak.xh,L-datak.xm,L-datak.cj); int cr(SqList *L,DataType *xs,int i) /插入信息 int j; if(L-length=MaxSize) 15 / 40 printf(没有 !); return 0; else if(iL-length) printf(程序溢出，不符合 ); return 0; else for(j=L-length-1;j=i;j-) 16 / 40 strcpy(L-dataj+1.xh,L-dataj.xh); strcpy(L-dataj+1.xm,L-dataj.xm); L-dataj+1.cj=L-dataj.cj; strcpy(L-datai.xh,xs-xh); strcpy(L-datai.xm,xs-xm); L-datai.cj=xs-cj; L-length=L-length+1; return 0; 17 / 40 int cz(SqList *L) /查找信息 char xh40; char xm40; int cj; int i=0,u; printf( 1、按学号查询 n); printf( 1、按姓名查询 n); printf( 1、按成绩查询 n); printf(请选择： ); fflush(stdin); scanf(%d,&u); 18 / 40 if (u=1) printf(请输入要查找学生的学号： ); scanf(%s,xh); for(i=0;ilength;i+) 链表实验报告 一、实验名称 链表操作的实现 -学生信息库的构建 二、实验目的 理解单链表的存储结构及基本操作的定义 掌握单链表存储基本操作 学会设计实验数据验证程序 【实验仪器及环境】计算机 Window XP 操作系统 三、实验19 / 40 内容 1、建立一个学生成绩信息的单链表，按学号排序 2、对链表进行插入、删除、遍历、修改操作。 3、对链表进行读取、存储 四、实验要求 给出终结报告 -打印版 对程序进行答辩 五、实验过程、详细内容 1、概念 及过程中需要调用的函数 链表的概念结点定义 结构的递归定义 struct stud_node int num; char name20; int score; struct stud_node *next; ; 链表的建立 20 / 40 1、手动输入 struct stud_node*Create_Stu_Doc() struct stud_node *head,*p; int num,score; char name20; int size=sizeof(struct stud_node); 【链表建立流程图】 2、从文件中直接获取 先建立一个 (3)链表的遍历 删除结点 ptr2=ptr1-next ptr1-next=ptr2-next free 21 / 40 动态储存分配函数 malloc void *malloc(unsigned size) 在内存的动态存储区中分配一连续空间，其长度为 size 若申请成功，则返回一个指向所分配内存空间的起始地址的指针 若申请不成功，则返回 NULL 返回值类型： (void *) 通用指针的一个重要用途 将 malloc 的返回值转换到特定指针类型，赋给一个指针 动态储存释放函数 free 当某个动态分配的存储块不再用时，要及时将它释放 void free(void *ptr) 释放由动态存储分配函数申请到的整块内存空间， ptr 为指向要释放空间的首地址。 链表写入文件 链表的读取 22 / 40 六、实验总结 链表弥补了许多数组的缺点，例如， 1、数组在添加新元素时，如果添加的位置是数组的首部或者数组中间，那么我们必须设计算法移动相关元素，并且涉及到许多相关元素； 2、删除元素时，如果删除的不是尾部元素，同样会移动其他元素。 因此使用数组处理 大量元素时，会影响程序的整体效率。 但是链表在搜索或随机读写内部元素的时远不如数组操作起来方便。 计算机 1403 班 李彦霖 1416010319 实验 一 线性表的基本操作实现及其应用 一、实验目的 23 / 40 1、熟练掌握线性表的基本操作在两种存储结构上的实现。 2、会用线性链表解决简单的实际问题。 二、实验内容 题目一 链表基本操作 该程序的功能是实现单链表的定义和操作。该程序包括单链表结 构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示： please input the operation： 1.初始化 2.清空 3.求链表长度 4.检查链表是否为空 5.检查链表是否为满 6.遍历链表 7.从链表中查找元素 8.从链表中查找与给定元素值相同的元素在表中的位置 24 / 40 9.向链表中插入元素 10. 从链表中删除元素 其他键退出。 题目二 约瑟夫环问题 设编号为 1， 2， 3， ， n 的 n(n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限 m，从第一个人开始顺时 针方向自 1 起顺序报数，报到 m时停止报数，报 m的人出列，将他的密码作为新的 m值，从他的下一个人开始重新从 1 报数。如此下去，直到所有人全部出列为止。令 n最大值取 30。要求设计一个程序模拟此过程，求出出列编号序列。 struct node /结点结构 int number; /* 人的序号 */ int cipher; /* 密码 */ 25 / 40 struct node *next; /* 指向下一个节点的指针 */ ; 三实验步骤 题目一 链表基本操作 (一 )、数据结构与核心算法的设计描述 1、单链表的结点类型定义 /* 定义 DataType 为 int类型 */ typedef int DataType; /* 单链表的结点类型 */ typedef struct LNode DataType data; 26 / 40 struct LNode *next; LNode,*LinkedList; 2、初始化单链表 LinkedList LinkedListInit() /函数功能：对链表进行初始化 参数：链表 (linklist L) 成功初始化返回 1,否则返回 0 3、清空单链表 void LinkedListClear(LinkedList &L) /函数功能：把链表清空 参数：链表 (linklist L) 成功清空链表返回 1 4、 检查单链表是否为空 27 / 40 int LinkedListEmpty(LinkedList L) /函数功能 :判断链表是否为空 参数：链表 (linklist L) 链表为空时返回 0,不为空返回 1 5、 遍历单链表 void LinkedListTraverse(LinkedList L) /函数功能 :遍历链表 ,输出每个节点的 elem 值 参数：链表 (linklist L) 通过循环逐个输出节点的 elem值 6、 求单链表的长度 int LinkedListLength(LinkedList L) /函数功能 :返回链表的长度 参数：链表 (linklist L) 函数返回链表的长度 7、 从单链表表中查找元素 LinkedList LinkedListGet(LinkedList L,int i) 28 / 40 /函数功能 : 从链表中查找有无给定元素 参数 ;链表(linklist L),给定元素 (int i) 如果链表中有给定元素 (i)则返回 1,否则返回 0 8、从单链表表中查找与给定元素值相同的元素在链表中的位置 LinkedList LinkedListLocate(LinkedList L, DataType x) /函数功能 : 从链表中查找给定元素的位置 参数 ;链表(linklist L),给定元素 (int i) 如果链表中有给定元素 i 则返回元素的位置 , 没有则返回0 9、 向单链表中插入元素 void LinkedListInsert(LinkedList &L,int i,DataType x) 29 / 40 / L 为带头结点的单链表的头指针，本算法 / 在链表中第 i 个结点之前插入新的元素 x 10、 从单链表中删除元素 void LinkedListDel(LinkedList &L,DataType x) 删除以 L 为头指针的单链表中第 i 个结点 、函数调用及主函数设计 zhujiemian(); cina; do switch(a) case 1: if(init(L)=1) b; if(find(L,b)=1) coutb; if(location(L,b)=0) cout break; case 9: do coutbc; while (bgetlength(L)+1) 30 / 40 coutbc; if(insert(L,b,c)=0) coutYES; while(YES=Y|YES=y); break; case 10: do if(getlength(L)=0) coutb; while(bgetlength(L) coutb; if(deleteelem(L,b)=0) coutYES; while(YES=Y|YES=y); break; default: break; (三 )、程序调试及运行结果分析 程序首先要进行初始化，否则程序不能运行。进行初始化之后，可 以进行链表的其他 操作。 (四 )、实验总结 链表的操作是 C+中的重点，这次试验让我看到了对链表的操作能力，发现了不足之处。事实证明：只有不停的练习，实践，才能编号程序。 四、程序清单 / #include iostream 31 / 40 #include #include #include using namespace std; #define MAXSIZE 100 typedef int elemtype; typedef struct STD elemtype elem; STD *next; list, * linklist; 32 / 40 void zhujiemian() cout int init(linklist&L) L=(linklist)malloc(sizeof(list); if(!L) C 语言实验报告 实验目的：链表的基本操作添加，删除，排序 #include #include 33 / 40 #include struct StuNode char ID10; char Name10; int Height; StuNode *next; ; typedef StuNode stulist; void Addafter (stulist * list,char * id,char * name,int height) 34 / 40 if(!list|!id) return; StuNode *p=new StuNode; strcpy(p-ID,id); strcpy(p-Name,name); p-Height=height; StuNode *q=list; while(q-next) q=q-next; 35 / 40 q-next=p; p-next=NULL; void ShowNode(stulist * list) cout StuNode *p=list-next; while(p) coutIDNameHeight p=p-next; cout 36 / 40 (转载于 : 海 达 范 文网 : 链 表 实 验 报 告 总 结 ) void Insert (stulist * list) char Beid10=2016002; char id10=1112223; char name10=狗蛋 ; int height=177; if(!list|!id) return; StuNode *p=new StuNode; strcpy(p-ID,id); strcpy(p-Name,name); 37 / 40 p-Height=hei