实验一线性表地实验

实验1线性表及其应⽤实验报告暨南⼤学本科实验报告专⽤纸课程名称数据结构成绩评定实验项⽬名称线性表及其应⽤指导教师王晓明实验项⽬编号实验⼀实验项⽬类型综合性实验地点南海楼601 学⽣姓名朱芷漫学号2010051875学院信息科学技术学院系计算机专业计算机科学与技术实验时间2011年9⽉7⽇18:30午～9⽉7⽇20:30午温度℃湿度⼀、实验⽬的和要求实验⽬的：熟练掌握线性表基本操作的实现及应⽤实验要求：在上机前写出全部源程序完毕并调试完毕。

⼆、实验原理和主要内容1.建⽴4个元素的顺序表SqList={2，3，4，5}，实现顺序表的基本操作；在SqList={2,3,4,5}的元素4与5之间插⼊⼀个元素9，实现顺序表插⼊的基本操作；在SqList={2,3,4,9,5}中删除指定位置(i=3)上的元素，实现顺序表删除的操作。

2.利⽤顺序表完成⼀个班级的⼀个学期的课程的管理：能够增加、删除、修改学⽣的成绩记录。

三、主要仪器设备PC机，Windows XP操作平台，Visual C++四、调试分析学⽣课程管理系统的调试过程中发现⼀些错误，主要是参数设置的问题，经过修改，错误得到排除。

五、测试结果1.顺序表2.学⽣课程管理系统附录（源程序）1.顺序表的操作#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 10 #define LISTINCREMENT 2 typedef struct shunxubiao{ElemType *list;int size;int Maxsize;}SqList;int InitList_Sq(SqList &L) {// 构造⼀个空的线性表L。

实验一线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现。

2、会用线性链表解决简单的实际问题。

二、实验内容题目一、该程序的功能是实现单链表的定义和操作。

该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。

其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。

单链表操作的选择以菜单形式出现，如下所示：please input the operation：1.初始化2.清空3.求链表长度4.检查链表是否为空5.检查链表是否为满6.遍历链表（设为输出元素）7.从链表中查找元素8.从链表中查找与给定元素值相同的元素在表中的位置9.向链表中插入元素 10. 从链表中删除元素其他键退出。

其中黑体部分必做题目二、约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。

开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。

如此下去，直到所有人全部出列为止。

令n最大值取30。

要求设计一个程序模拟此过程，求出出列编号序列。

struct node(一)1．进入选择界面后，先选择7，进行插入：2.选择4，进行遍历，结果为：3.选择2，得出当前链表长度.4.选择3，得出当前链表为.5.选择分别选择5、6进行测试.6.选择8，分别按位置和元素值删除.7.选择9，或非1-8的字符，程序结束.(二) 实验总结通过这次实验，我对线性链表有了更深的理解，深入明白了线性存储结构与链式存储结构在内存存储的不同特点，同时我还学会了用这些知识实际解决一些问题，能够更加熟练地将算法转化为实际程序。

同时，在写程序和调试程序的过程中，学会了一些书写技巧和调试技巧，这对于自己能在短时间高效的写出正确地程序有很大作用。

四、主要算法流程图及程序清单 1. 主要算法流程图：(1) 从单链表表中查找与给定元素值相同的元素在链表中的位置p=p->nextp&&!(p->data==xtrue调用函数，传入参数L ，xp=L->next2.程序清单：#include<iostream> using namespace std; #include<>#include<>/* 预处理命令 */#define OK 1;#define ERROR 0;#define OVERFLOW -1;/* 单链表的结点类型 */typedef struct LNode{int data;struct LNode *next;}LNode,*LinkedList;/*初始化单链表*/LinkedList LinkedListInit(){空"<<endl;cout<<"\t\t\t"<<"2.求链表长度"<<endl;cout<<"\t\t\t"<<"3.检查链表是否为空"<<endl;cout<<"\t\t\t"<<"4.遍历链表"<<endl;cout<<"\t\t\t"<<"5.从链表中查找元素 "<<endl;cout<<"\t\t\t"<<"6.从链表中查找与给定元素值相同的元素在表中的位置"<<endl;cout<<"\t\t\t"<<"7.向链表中插入元素"<<endl;cout<<"\t\t\t"<<"8.从链表中删除元素"<<endl;cout<<"\t\t\t"<<"9.退出"<<endl;}/*主函数*/int main(){链表长度case 2:{cout<<"\t\t\t链表长度为："<<LinkedListLength(L)<<endl;getch();}break;查链表是否为空case 3:{if (!LinkedListEmpty(L)){cout<<"\t\t\t链表不为空！"<<endl;}else{cout<<"\t\t\t链表为空！"<<endl;}getch();}break;历链表case 4:{LinkedListTraverse(L);getch();}break;链表中查找元素case 5:{cout<<"\t\t\t请输入要查询的位置i：";int j;cin>>j;if (LinkedListGet(L,j)){cout<<"\t\t\t位置i的元素值为："<<LinkedListGet(L,j)->data<<endl;}else{cout<<"\t\t\ti大于链表长度！"<<endl;}getch();}break;链表中查找与给定元素值相同的元素在表中的位置case 6:{cout<<"\t\t\t请输入要查找的元素值：";int b;cin>>b;if (LinkedListGet1(L,b)){cout<<"\t\t\t要查找的元素值位置为："<<LinkedListGet1(L,b)<<endl;cout<<"\t\t\t要查找的元素值内存地址为："<<LinkedListLocate(L,b)<<endl;}else{cout<<"\t\t\t该值不存在！"<<endl;}getch();}break;链表中插入元素case 7:{cout<<"\t\t\t请输入要插入的值：";int x; cin>>x;cout<<"\t\t\t请输入要插入的位置：";int k; cin>>k;if(LinkedListInsert(L,k,x)){cout<<"\t\t\t插入成功！"<<endl;}else{cout<<"\t\t\t插入失败！"<<endl;}getch();}break;链表中删除元素case 8:{cout<<"\t\t\t1.按位置删除"<<endl;cout<<"\t\t\t2.按元素删除"<<endl;int d;cout<<"\t\t请选择：";cin>>d;switch(d){case 1:{cout<<"\t\t\t请输入删除位置：";cin>>d;int y;if (LinkedListDel(L,d,y)){cout<<"\t\t\t"<<y<<"被删除！"<<endl;}else{cout<<"\t\t\t删除失败！"<<endl;}}break;case 2:{cout<<"\t\t\t请输入删除元素：";int y;cin>>y;if (LinkedListDel(L,y)){cout<<"\t\t\t"<<y<<"被删除！"<<endl;}else{cout<<"\t\t\t删除失败！"<<endl;}}}getch();}break;}}return 1;}题二约瑟夫环问题算法、思想为了解决这一问题，可以先定义一个长度为30（人数）的数组作为线性存储结构，并把该数组看成是一个首尾相接的环形结构，那么每次报m的人，就要在该数组的相应位置做一个删除标记，该单元以后就不再作为计数单元。

实验01 线性表的基本操作一、实验目的1. 了解线性表的结构特点及有关概念；2. 理解线性表的存储结构；3. 掌握顺序表及单链表的基本操作算法。

二、实验内容1、编写程序实现顺序表的各种基本运算：初始化、插入、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。

在此基础上设计一个主程序完成如下功能：（1）初始化顺序表L；（2）依次在表尾插入a，b，c，d，e五个元素；（3）输出顺序表L；（4）输出顺序表L的长度；（5）判断顺序表L是否为空；（6）输出顺序表L的第4个元素；（7）输出元素c的位置；（8）在第3个位置上插入元素f，之后输出顺序表L；（9）删除L的第2个元素，之后输出顺序表L；（10）销毁顺序表L。

2、编写程序实现单链表的各种基本运算：初始化、插入、删除、取表元素、求表长、输出表、销毁、判断是否为空表、查找元素。

在此基础上设计一个主程序完成如下功能：（1）初始化单链表L；（2）依次在表尾插入a，b，c，d，e五个元素；（3）输出单链表L；（4）输出单链表L的长度；（5）判断单链表L是否为空；（6）输出单链表L的第4个元素；（7）输出元素c的位置；（8）在第3个位置上插入元素f，之后输出单链表L；（9）删除L的第2个元素，之后输出单链表L；（10）销毁单链表L。

三、实验要点及说明一．顺序表1.顺序表初始化:(1)为顺序表L动态分配一个预定大小的数组空间，使elem 指向这段空间的基地址。

(2)将表的当前长度设为0.2.顺序表的取值:(1)判断指定的位置序号i值是否合理（1<=i<=L.length），若不合理则返回ERROR.(2)若i值合理，则将i个数据元素L.elem[i]赋给参数e,通过e返回第i个数据元素的传值。

3.顺序表的查找:(1)从第一个元素起，依次和e相比较，若找到与e相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1.(2)若查遍整个顺序表都没要找到，则查找失败，返回0.4．顺序表的插入:(1)判断插入位置i是否合法(i值的合法范围是1<=i<=n+1)，若不合法则返回值ERROR.(2)判断顺序表的存储空间是否已满，若满则返回值ERROR(3)将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置(i=n+1时无需移动)。

实验报告2013学年第一学期任课老师：2、在实验过程中遇到的问题与解决方法：问题有很多，比如局部变量与全局变量的声明，常常顾此失彼，此处概念仍然不清。

填写内容时，可把表格扩大。

附：实验源程序代码顺序表（链表）：// 线性表（链表）#include <stdio.h>#include "malloc.h"#include <iostream>using namespace std;typedef struct LNode{int data;struct LNode *next;}LNode,*LinkList;//创建一个长度为n的链表void CreateList(LinkList &L, int n) {L = (LinkList)malloc(sizeof(LNode));L->next = NULL;for (int i=n; i>0; --i){LinkList p = (LinkList)malloc(sizeof(LNode));cin>>p->data;p->next = L->next;L->next = p;}}// 在链表L第i个元素之前插入元素eint ListInsert(LinkList &L, int i, int e) {LinkList p=L;int j=0;while(p&&j<i-1) {p=p->next; ++j;}if(!p ||j>i-1) return 0;LinkList s = (LinkList)malloc(sizeof(LNode)); s->data=e;s->next=p->next;p->next=s;return 1;}// 在链表L中删除第i个元素，并由e返回其值int ListDelete(LinkList &L, int i, int &e) { LinkList p=L;int j=0;while(p->next&&j<i-1) {p=p->next; ++j;}if(!(p->next)||j>i-1) return 0;LinkList q=p->next;p->next=q->next;e=q->data;free(q);cout<<"被删除的元素数据为"<<e<<"\n"; return 0;}//查找第i个元素,并由e返回其值int GetElem(LinkList &L,int i, int &e) {LinkList p=L->next;int j=1;while (p && j<i) {p=p->next; ++j;}if (!p||j>i) return 0;e=p->data;cout<<"该元素的值为"<<e<<"\n";return 1;}//让链表L中的元素按从小到大的顺序排列LinkList Sort(LinkList L){ LinkList p,q;int temp;for(p=L;p!=NULL;p=p->next){for(q=p->next;q!=NULL;q=q->next){if(p->data>q->data){temp=q->data;q->data=p->data;p->data=temp;}}}return L;}//归并L和La得到新的单链性表Lbvoid MergeList_L(LinkList &L,LinkList &La,LinkList &Lb) { LinkList p,pa,pb;p=L->next;pa=La->next;Lb=pb=L; //用L的头结点作为Lb的头结点while (p&&pa) {if (p->data<=pa->data) {pb->next=p;pb=p;p=p->next;}else {pb->next=pa;pb=pa;pa=pa->next;}}pb->next=p?p:pa;free(La);}int main(){LinkList L;int n,s,e,i,f,g,h;cout<<"输入链表长度n:";cin>>n;cout<<"请输入L中的元素:"<<endl;CreateList( L, n);cout<<"输入的链表为:"<<" ";LNode *q=L->next;while(q){cout<<q->data<<" ";q=q->next;} cout<<endl;int choice;cout<<"请选择功能:"<<endl;cout<<"1.插入元素"<<endl;cout<<"2.删除元素"<<endl;cout<<"3.查找元素"<<endl;cout<<"4.给元素排序"<<endl;cout<<"5.合并链表"<<endl;cout<<"0.退出程序"<<endl;cout<<"PS:若先排序再合并，可将得到新的排序后的合并链表。

实验一:线性表的基本操作【实验目的】学习掌握线性表的顺序存储结构、链式存储结构的设计与操作.对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。

【实验内容】1.顺序表的实践1）建立4个元素的顺序表s=sqlist［］=｛1，2，3，4，5}，实现顺序表建立的基本操作.2) 在sqlist ［]=｛1，2，3,4,5}的元素4和5之间插入一个元素9,实现顺序表插入的基本操作。

3) 在sqlist ［］=｛1,2，3，4，9，5}中删除指定位置(i=5）上的元素9，实现顺序表的删除的基本操作。

2.单链表的实践3.1) 建立一个包括头结点和4个结点的(5，4，2，1）的单链表，实现单链表建立的基本操作。

2）将该单链表的所有元素显示出来。

3) 在已建好的单链表中的指定位置（i=3)插入一个结点3，实现单链表插入的基本操作。

4) 在一个包括头结点和5个结点的（5，4，3，2，1）的单链表的指定位置（如i=2)删除一个结点，实现单链表删除的基本操作。

5) 实现单链表的求表长操作.【实验步骤】1.打开VC++.2.建立工程:点File->New,选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK-〉finish。

至此工程建立完毕.3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File.给文件起好名字,选好路径，点OK。

至此一个源文件就被添加到了刚创建的工程之中.4．写好代码5．编译－＞链接－＞调试1、#include "stdio。

h”＃include "malloc.h”#define OK 1＃define OVERFLOW -2＃define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int ElemType;typedef int Status；typedef struct ｛ElemType *elem;int length;int listsize；} SqList；Status InitList( SqList &L ) {int i，n;L。

数据结构实验总结及心得体会引言数据结构作为计算机科学的基础课程，是理解和应用计算机编程的重要部分。

通过实验的形式，我们可以更加深入地理解不同数据结构的特点和应用场景。

本文将总结我在数据结构实验中的学习经验和心得体会。

实验一：线性表在线性表实验中，我学习了顺序表和链表两种基本的线性表结构。

顺序表使用数组来存储数据，具有随机访问的特点；链表使用指针来连接数据元素，具有插入和删除操作方便的特点。

通过这个实验，我深刻认识了线性表的存储结构和操作方法。

我遇到的难点是链表的插入和删除操作，因为涉及到指针的重新指向。

通过调试和分析代码，我逐渐理解了指针指向的含义和变化规律。

在实验结束后，我还进一步学习了循环链表和双向链表的特点和应用。

实验二：栈和队列栈和队列是两种常用的数据结构，可以用来解决很多实际问题。

在这个实验中，我学习了顺序栈、链式栈、顺序队列和链式队列四种基本实现方式。

实验中我遇到的最大困难是队列的循环队列实现，因为需要处理队列尾指针的位置变化。

我通过画图和调试发现了队列尾指针的变化规律，并在实验中成功实现了循环队列。

熟练掌握了栈和队列的操作方法后，我进一步学习了栈的应用场景，如表达式求值和括号匹配等。

队列的应用场景还有优先级队列和循环队列等。

实验三：串串是由零个或多个字符组成的有限序列，是实际应用中十分常见的数据类型。

在这个实验中，我学习了串的存储结构和常规操作。

实验中最具挑战性的部分是串的模式匹配。

模式匹配是在一个主串中查找一个子串的过程，可以使用暴力匹配、KMP 算法和BM算法等不同的匹配算法。

在实验中，我实现了KMP算法，并在实际应用中进行了测试。

从实验中我学到了使用前缀表和后缀表来提高模式匹配的效率。

同时，在应用中也了解到了串的搜索和替换等常见操作。

实验四：树和二叉树树是一种重要的非线性数据结构，应用广泛。

在这个实验中，我学习了树的基本概念、存储结构和遍历方式。

实验中最困难的部分是二叉树的遍历。

《数据结构与算法》实验指导书实验及学时数分配几点要求：一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。

二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。

上机时签到；下机时验收签字。

三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。

实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。

【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。

(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。

若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。

若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。

【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。

1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i，和要插入的元素值；实现插入；显示插入后的线性表）3、指定一个元素，删除此元素。

（从键盘接受删除元素位置i，实现删除；显示删除后的线性表）二、用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素。