数据结构顺序表实验报告优质资料.doc

数据结构顺序表实验报告优质资料(可以直接使用，可编辑 优质资料，欢迎下载）洛阳理工学院实验报告系别计算机班级学号姓名课程名称数据结构实验日期10/23实验名称顺序表的基本操作成绩实验目的：熟悉掌握线性表顺序存储结构，掌握与应用顺序表的查找、插入、删除等基本操作算法，训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台，Visual C+6.0实验内容：1. 问题描述以顺序表为存储结构实现以下基本操作：(1) 在第i个元素前插入一个新元素。(2) 查找值为x的某个元素。若成功，给出x在表中的位置；不成功给出提示信息。(3) 删除第i个元素，若成功，给出提示信息并显示被删元素的值；不成功给出失败的提示信息。2. 数据结构类型定义typedef struct ElemTypeelemMAXSIZE; Intlast; SeqList;3. 模块划分(1)创建顺序表输入函数：void Input(SeqList *L,int n)；(2)创建顺序表输出函数：void Output(SeqList *L)；(3)创建顺序表的内容查找函数：int Locate(SeqList L,ElemType e)； (4)创建顺序表的插入函数：int InsList(SeqList *L,int i,ElemType e)；(5)创建顺序表的删除函数： int DelList(SeqList *L,int i,ElemType *e)；(6)主函数：void main()4. 详细设计#include #include #include #define OK 1#define ERROR -1#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 100 /最大长度 typedef struct ElemType elemMAXSIZE; int last; SeqList;void Input(SeqList *L,int n) /输入函数 int i; printf(请输入线性表的各元素值:n);for(i=0; ielemi);void Output(SeqList *L) /输出函数 int i; for(i=0; ilast; i+) printf(%2d,L-elemi); printf(n);int Locate(SeqList L,ElemType e)/内容查找函数 int i; i=0; while(i=L.last)&(L.elemi)!=e) i+; if(i=L.last) return(i+1); /返回序号 else return(-1);int InsList(SeqList *L,int i,ElemType e)/插入数据 int k; if(iL-last+2) /*首先判断插入位置是否合法*/printf(插入位置不合法n);return(ERROR);if(L-last= MAXSIZE-1)printf(表已满无法插入);return(ERROR);for(k=L-last;k=i-1;k-) /为插入元素而移动位置L-elemk+1=L-elemk;L-elemi-1=e; /第i个元素的下标为i-1L-last+;return(OK);int DelList(SeqList *L,int i,ElemType *e) /删除函数/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1iL.last+1 */ int k;if(iL-last+1) printf(删除位置不合法!n);return(ERROR);*e = L-elemi-1; /* 将删除的元素存放到e所指向的变量中*/for(k=i; klast; k+)L-elemk-1 = L-elemk; /*将后面的元素依次前移*/L-last-;return(TRUE);void main()/主函数SeqList l,*la;int p,q,r,k,j ,m,num;printf(请输入线性表的长度:);scanf(%d,&r);l.last = r-1; la=&l; Input(la,la-last+1); Output(la); /按内容查找元素printf(请输入要查找的元素值:n);scanf(%d,&q);p=Locate(l,q); if(p = -1)printf(在此线性表中没有该元素! n);elseprintf(该元素在线性表中的位置为:%d n,p); /插入元素 （在i处插入元素e）printf(请输入要插入的位置:n); scanf(%d,&k);printf(请输入要插入的元素值:n); scanf(%d,&j);InsList(la,k,j); /调用插入函数Output(la);/删除元素 删除第i个元素printf(请输入需要删除的元素的位置：n);scanf(%d,&m); DelList(la,m,&num);printf(删除成功,删除的元素为%d,num);printf(n); Output(la); 5.测试数据及结果实验总结：经过调试与测试，实验结果与测试预期一致。顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。第10章实验实验名称：考试日程安排与成绩统计实验类型：综合性性实验班级：20210611学号：2021061118姓名：郭鑫1. 问题描述问题描述l 现要安排考试的考表（即考试日程表），假设共有10个班的学生，要安排10门必修课程的考试，必修课程是以班级来确定的，每个班各有3门必修课，因此各班的考试科目是不相同的；安排考表的原则是：相同课程采用统一的试卷，因此同一门课程的考试必须在相同时间进行，同一个班所修的科目必须安排在不同的时间进行考试，以避免考试时间的冲突。并要求全部考试的日程尽可能短。l 要求对考试结果做统计和排序。假设分别以编号0,1,2,3,4,5,6,7,8,9代表10门要考试的课程，以B1，B2，B3，B4，B5，B6，B7，B8，B9，B10代表10个班，每个人的信息包括学号、姓名、班级、各门考试课程成绩、三门课程总成绩，每个班的学生人数自行设定。要求设计一个简单的考试成绩的查询统计系统实现以下功能： 显示学生考试情况-按考试总分从高到底输出全体学生的信息。-按照从B1到B10的班级顺序，分班级按照考试总分从高到底的顺序输出各班学生的信息。-输出指定班的学生考试成绩信息。 统计学生考试成绩-按总成绩统计出90分以上、8089分、7079分、6069分、60分以下各分数段的人数，并按总分从高到低分段输出。-根据指定的某们课程的成绩，统计出上述各分数段的人数，并按分数从高到低分段输出。-统计并输出指定班级中总成绩或某一门课成绩的各分数段人数和每个人具体的信息。 查找学生成绩-查找总分或某一门课程成绩的指定分数段的人数及学生的详细信息。-查找指定班级中总分或某一门课程成绩属于某分数段的学生详细信息。-查找指定学生（例如给定学号）的具体信息，包括：姓名、班级、各科分数、总分数等。求解方法说明l 考试日程安排问题。 该问题实际上是对若干元素进行子集划分的问题，要求所划分的每个子集中的元素没有“考试冲突”关系。 假设各个班的考试课程分别为：(1,4,8),(1,3,7),(8,2,4),(1,0,5),(2,6,9),(3,0,8),(4,5,9),(2,9,7),(6,0,3),(5,6,9)。根据题中考试安排原则，各个班要进行的考试课程可以抽象为“考试冲突关系”，归纳各个班的考试课程可以整理得到考试冲突关系：R=(1,4),(1,8),(4,8),(1,3),(1,7),(3,7),(8,2),(2,4),(1,0),(1,5),(0,5),(2,6),(2,9),(6,9),(3,0),(0,8),(3,8),(4,5),(5,9),(4,5),(2,7),(9,7),(6,0),(6,3),(5,6)。显然，“考试冲突”关系R的每个有序对中的两门课程不能安排在同一时间考试，据此可以将10门课划分为若干个考试时间没有冲突的子集，并且使考场的场次尽量少，使得整个考试时间尽可能短。 上述子集划分问题可以用对集合中的元素逐个“筛选”的办法来解决。首先将集合的第1个元素置为第1个子集，再逐个检查集合中的其余元素是否和第1个元素有考试冲突，若不存在考试冲突，则将其加入到第1个子集中，继续检查集合中的其余元素，凡是不与第1个子集中的元素冲突的元素都逐个将其加入到其中；接着按同样的方法“筛选”出若干没有考试冲突的元素构成第2个子集，该过程一直到集合中的全部元素都分到某个子集中结束。得到的每一个子集中的课程就是可以安排在同一时间考试的课程。不同子集的课程则要安排在不冲突的时间考试。l 考试分数的统计与排序 考试成绩输出 每个学生的信息记录数据项应包括：学号、姓名、班级、课程1、课程2、课程10、总成绩。 按总分高低输出所有学生信息时，应该以总成绩为关键字从高分到低分对所有的学生记录进行排序，排序方法自行选定，然后依次输出各个记录。 按照班级顺序和总分高低输出各班学生信息时，要对学生记录进行多关键字排序，首先以总成绩为关键字从高分到低分对所有的学生记录进行排序，然后再以班号为关键字对全部学生记录排序，再输出结果。 统计成绩统计各分数段的人数，要求由用户输入，具体要求可以有： 按照总成绩统计各分数段的人数，并输出各分数段的学生记录，即在统计一个分数段的人数过程中，要输出满足查找条件的学生记录，再输出统计的结果。 指定某一门课程，统计各分数段的人数并输出各分数段的学生记录。 对指定班级中总成绩或指定课程成绩做各分数段人数的统计，也要输出各分数段的学生记录。 查找成绩查找要求由用户输入，可以输入以下条件： 查找指定分数项（总分或某一门课程）的某分数段的学生信息，输出查找结果。 查找指定班级、指定分数项的某分数段的学生信息，输出查找结果。 查找指定学生（给定学号）的具体信息，输出查找结果。算法提示l 考试场次的划分“无考试冲突”子集划分的算法思路。 为了把10门课程划分为时间上不冲突的若干场考试，可以利用一个循环队列来实现求解方法中说明的“筛选”过程。 首先定义一个循环队列，再把10门课程的编号从小到大依次加入到循环队列中，然后重复下列步骤： 队头元素出队并作为当前子集的第1个元素。 队头元素继续依次出队，每出队一个队头元素都要检查与当前子集中的元素是否有“考试冲突”；如果没有冲突，则将其加入到当前子集中，否则将其重新加入队列中，等待以后加入新子集的机会。 比较刚出队元素与前一出队元素编号。因为队列中原有的元素是以编号从小到大的顺序排列的，重新入队的元素编号一定小于它的前一元素，所以一旦发现目前出队的元素编号小于前一个出队的元素，就可以断定当前的“考试冲突”子集已经构建完，队列中剩余元素应该构建新的子集。为此，在当前的队头元素出队前，要先记下刚刚出队的元素，以便判断当前出队的元素是否要开始构建一个新子集。重复上述步骤一直到队列空，则“无考试冲突”子集划分完成。由上述算法思路可以知道，“无考试冲突”子集的划分过程是一个循环的执行过程，循环中的主要操作是元素出队和判断的操作。判断操作包括出队元素是否可以加入当前子集和是否要开始构建一个新子集两个方面，对后一个判断如前所述，通过比较出队元素与前一个出队元素编号大小可以确定。为了判断出队元素与当前子集中的元素是否有“考试冲突”，可以定义一个二维数组confnn来表示课程的考试冲突关系矩阵，矩阵中各元素的值根据以下规则确定，若编号为i的课程和编号为j的课程有考试冲突，则置confij=1，否则置confij=0，考试冲突关系矩阵如图1所示。0101011010100111011000001011111100001110011001001111001010011011010001011100000111111000000010111100图1 考试冲突关系矩阵利用“考试冲突”关系矩阵可以检查出队元素i是否与当前子集中的元素有考试冲突，其方法是：当课程号为j1，j2，jk的元素已经在当前子集S中，要判断目前出队的元素i是否可以加入子集S，只要检查“考试冲突”关系矩阵中第i行的元素confi j1，confi j2，confi jk的值是否为0即可。如果这些元素的值都为0，表示课程i与子集中的课程没有考试冲突，可以加入其中，否则说明表示课程i与子集中的某些课程有考试冲突，它不能加入该子集中。为了减少在二维数组conf中查找元素的操作，可以定义一个一维数组clashn来方便出队元素i是否要加入当前子集的判断，数组clashn用于记录出队元素i与当前子集中的元素是否存在考试冲突的信息。每当开始构建一个新子集时，先将数组clashn的各元素初始化为0，当有编号为i的课程加入子集时，将“考试冲突”关系矩阵中第i行的各列的值与数组clash的各对应元素的值相加，因而使得数组clash中和编号为i的元素有考试冲突的相应元素的值不再是0，当下一个队头元素j出队时，只要检查数组clash中第j个元素的值是否为0，就可以判断其是否与当前子集中的元素有考试冲突；若数组clash中第j个元素的值不为0，则说明元素j与当前子集中元素存在考试冲突，应将其重新加入队列；若数组clash中第j各元素的值为0，则说明它与当前子集中元素不存在考试冲突，应该将它加入当前子集中，同时要将“考试冲突”关系矩阵中第j行的各列的值与数组clash的各对应元素的值相加，这个过程一直到队列空，则划分无考试冲突子集完成。划分结果可以用一个二维数组来记录各子集中的元素的方式来表示，也可以用一个一维数组来记录每个元素其所属的子集号的方式来表示。上述算法的思路可以描述如下：建立表示课程考试冲突关系矩阵的二维数组confnn；定义用于检查当前子集的课程考试冲突信息的数组clashn；定义用于记录子集划分结果的数组resultn；pre=n;/pre用于记录前一个出队元素的编号，初始值置为n以新建第1个子集k=0； /k用于记录子集序号09(课程编号)依次入队；while（队列不空）队头元素i出队；if(ipre)/刚出队元素小于前一个出队元素，生成一个新子集k+;数组clash初始化；if(i可以加入当前子集)/如果刚出队元素与当前子集中的元素无考试冲突，将其加入当前子集将i加入当前子集，记录i所属子集的序号；将conf数组第i行各列的值与clash数组对应列的值相加并记入clash中；else /如果刚出队元素与当前子集中的元素有考试冲突，将其重新入队将i重新加入队列；pre=i;l 考试成绩统计和排序的实现 按总成绩或按某一门课的成绩统计并输出人数时，应该使各分数段的人数和每个学生的信息清晰的分开。 对全体学生或对某一个班的学生的成绩进行排序时，排序方法可以任意选择。就本实验问题而言，因表长不大采用简单的排序方法就可以达到目的，但为了比较各种常用排序方法性能和适用场合，还可以采用不同的排序方法实现排序。 对多关键字的排序要求，要注意排序方法的稳定性问题。例如，在按总成绩从高分到低分对全体学生进行排序后，再按班级从高分到低分进行排序，此时要求分班级排序时采用的排序方法其动态性能必须是稳定的。同样地，如果在按总成绩从高分到低分排序的基础上，再要求按某一门课的成绩从高分到低分排序，也要求第2层排序一定注意选择动态性能稳定的排序方法。 在实现查找或排序功能时，其查找或排序的依据（指定项）和目标（输出结果）通过提示用户输入来确定。2. 数据结构设计typedef int KeyType;typedef char InfoType10;typedef struct /*记录类型*/KeyType key; /*关键字项*/ InfoType data; /*其他数据项,类型为InfoType*/ RecType3. 算法设计#includeusing namespace std;#define MAXE 20/*线性表中最多元素个数*/typedef int KeyType;typedef char InfoType10;typedef struct /*记录类型*/KeyType key; /*关键字项*/ InfoType data; /*其他数据项,类型为InfoType*/ RecType;void SelectSort(RecType R,int n)/*直接选择排序算法*/int i,j,k,l;RecType temp;for (i=0;in-1;i+) /*做第i趟排序*/k=i;for (j=i+1;jn;j+) /*在当前无序区Ri.n-1中选key最小的Rk */if (Rj.keyRk.key)k=j; /*k记下目前找到的最小关键字所在的位置*/if (k!=i) /*交换Ri和Rk */temp=Ri;Ri=Rk;Rk=temp; printf( i=%d ,i);/*输出每一趟的排序结果*/for (l=0;ln;l+)printf(%2d,Rl.key);printf(n);int main()int i,k,n=10,m=5;KeyType a=6,8,7,9,0,1,3,2,4,5;RecType RMAXE;for (i=0;in;i+)Ri.key=ai;printf(n);printf( 初始关键字 );/*输出初始关键字序列*/for (k=0;kn;k+)printf(%2d,Rk.key);printf(n);SelectSort(R,n);printf( 最后结果 );/*输出初始关键字序列*/for (k=0;knext并辅助计数器来实现。4.2.2 指针保留技术 通过对第i个结点进行插入、删除等操作时，需要对第i-1个结点的指针域进行链址操作（pre-next），因此在处理过程中始终需要维持当前指针p与其前驱指针pre的关系，将这种技术称为“指针保留技术”。4.3 链表处理中的相关技术1）单链表与多重链表的差别在于指针域的个数。2）判断当前结点p是否为表尾。一半链表中，p结点是表尾的条件是：该节点的后继结点为空指针，即p-next=NULL;3）链表的长度并未显示保存。由于链表是动态生成的结构，其长度要通过顺链查找到表尾得到。因此在处理链表时，往往是以当前处理结点p是否为表尾作为控制条件，而不是长度n作为控制条件。5 设计体会及今后的改进意见通过这次实验加深了我对于单链表的进一步了解，了解到了单链表在内存中的存储结构，最重要的是学会了如何运用C语言将单链表的建立，插入、删除、添加等操作。在程序实现中也遇到了一些困难，在单链表初始化时，使用了0作为结束输入符，导致单链表不能存储数据0；单链表中只能存储相同类型的数据，在存储不同类型的数据时需要改变输入结束标志，程序通用性比较差。在进行程序设计的时候没有考虑好删除和查找的方式，只进行了输入元素的查找和删除，而且进行链表的插入时，只考虑了头插法在结尾插入，而没有考虑输入结点插入等，程序的灵活性比较低。通过这次课程设计，让我充分认识到数据结构在编写程序方面的重要地位。不仅仅是单链表的操作，还有栈和队列等特殊的单链表操作，以及其他一些常用的数据结构对于程序的效率和内存使用有很大的帮助。我希望在接下来的学习中收获更多的东西。参考文献1耿国华.数据结构-用C语言描述M.北京:高等教育出版社,2021.6.2谭浩强.C程序设计M.北京:清华大学出版社,2004.6.附录代码：结构体定义：#pragmaonce#include#includeenummy_enum_EXIT,_CREATE,_INSERT,_PRINT,_SEARCH,_DELETE,_COUNT,;staticint count = 0;typedefintElemtype;typedefstructNode/*单链表结构体的定义*/Elemtype data;structNode *next;Node, *LinkList;void test();/*测试函数*/void main_menu();/主菜单函数void CreatFromHead(LinkList *l);/*头插法建立单链表*/void Insert(LinkList l);/单链表的插入void Print(LinkList l);/*单链表的输出*/int Search(LinkList l, Elemtype e);/查找指定的元素void Deletelist(LinkList l, Elemtype e);/删除元素void Count();/计数void CREATE(LinkList *head);void INSERT(LinkList *head);void PRINT(LinkList *head);void SEARCH(LinkList* head);void DELET(LinkList *head);void COUNT();单链表操作函数：#define_CRT_SECURE_NO_WARNINGS#includelinklist.hvoid main_menu()printf(t 单链表的简单操作ttnn);printf(t 1 单链表的建立n);printf(t 2 单链表的插入n);printf(t 3 单链表的输出n);printf(t 4 单链表的查找n);printf(t 5 单链表的删除n);printf(t 6 单链表的长度n);printf(t 0 退出n);void CreatFromHead(LinkList *l)/*头插法建立单链表*/Node *s;int c = 0;int flag = 1;*l = (Node*)malloc(sizeof(Node);if (*l = NULL)printf(申请空间失败！n);return;(*l)-next = NULL;while (flag)scanf(%d, &c);if (c != 0)s = (Node*)malloc(sizeof(Node);if (s = NULL)printf(申请空间失败！n);return;s-data = c;s-next = (*l)-next;(*l)-next = s;count+;else flag = 0;void Insert(LinkListl)/单链表的插入int insert = 0;Node * s = NULL;printf(请输入需要插入的元素：);scanf(%d, &insert);s = (Node*)malloc(sizeof(Node);if (s = NULL)printf(申请空间失败！n);return;while (l-next != NULL)l = l-next;s-data = insert;s-next = l-next;l-next = s;count+;void Print(LinkListl)/*单链表的遍历*/Node *p;p = l-next;while (p != NULL)printf(%d , p-data);p = p-next;printf(n);int Search(LinkListl, Elemtypee)/查找指定的元素while (l != NULL) & (l-data != e)l = l-next;if (l = NULL)return -1;/查找失败elsereturn 1;/查找成功void Deletelist(LinkListl, Elemtypee)/删除节点Node *p, *r, *q;p = l-next; q = l;while (p != NULL)if (p-data = e)r = p;