搜索
1实验一线性表的基本操作及应用一、实验目的1．通过实际操作掌握定义线性表的顺序存储类型，熟悉线性表的基本操作的算法实现(具体的函数定义)，掌握单链表的结点类型的定义及单链表的基本操作算法实现(具体的函数定义)。2．顺序存储和链式存储的应用。二、实验要求1．认真阅读和掌握所给的程序。2．上机运行程序，并对程序进行分析。3．完成自编程序，并上机调试运行。三、实验内容1．建立顺序表，及其基本操作（包括查找、插入、删除等），并且用数据进行测试。（1）建立工程启动VisualC++，选择“文件|新建”弹出如图1所示的对话框，选择Project选项卡中的Win32ConsoleApplication选项，在Projectname文本框中输入工程的名字“SeqList”，在Location中输入工程存放的路径，如“D:\数据结构实验\SeqList”。设置如图1所示。然后选择“OK按钮”，弹出如图2所示对话框，单击“Finish”按钮弹出如图3所示对话框，单击“OK”按钮，则创建工程成功，界面如图4所示。2图1选择新建弹出的对话框图23图34图4（2）创建common.h头文件选择“文件|新建”弹出如图5所示的对话框，选择“Files”选项卡中的“C/C++HeaderFile”，在“File”文本框中输入头文件的名字“common”，如图5所示。选择“OK”按钮。头文件中包含文件包含命令和宏定义，在“common.h”中输入如下内容：#includestdio.h#includestdlib.h#includemalloc.h#defineOK1#defineERROR0#defineTRUE1#defineFALSE05图5（3）创建“seqlist.h”头文件“seqlist.h”头文件中主要包含了顺序表的定义以及基本操作。创建方法与创建“common.h”文件相同。“seqlist.h”文件内容如下：#defineElemTypeint#defineMAXSIZE100/*此处的宏定义常量表示线性表可能达到的最大长度*/typedefstruct{ElemTypeelem[MAXSIZE];/*线性表占用的数组空间*/intlast;/*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1*/}SeqList;intLocate(SeqListL,ElemTypee){inti=0;/*i为扫描计数器，初值为0，即从第一个元素开始比较*/6while((i=L.last)&&(L.elem[i]!=e))/*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/i++;if(i=L.last)return(i+1);/*若找到值为e的元素，则返回其序号*/elsereturn(-1);/*若没找到，则返回空序号*/}/*在顺序表L中第i个数据元素之前插入一个元素e。插入前表长n=L-last+1，i的合法取值范围是1≤i≤L-last+2*/intInsList(SeqList*L,inti,ElemTypee){intk;if((i1)||(iL-last+2))/*首先判断插入位置是否合法*/{printf(插入位置i值不合法);return(ERROR);}if(L-last=MAXSIZE-1){printf(表已满无法插入);return(ERROR);}for(k=L-last;k=i-1;k--)/*为插入元素而移动位置*/L-elem[k+1]=L-elem[k];L-elem[i-1]=e;/*在C语言数组中，第i个元素的下标为i-1*/L-last++;return(OK);}7intDelList(SeqList*L,inti,ElemType*e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1*/{intk;if((i1)||(iL-last+1)){printf(删除位置不合法!);return(ERROR);}*e=L-elem[i-1];/*将删除的元素存放到e所指向的变量中*/for(k=i;k=L-last;k++)L-elem[k-1]=L-elem[k];/*将后面的元素依次前移*/L-last--;return(OK);}voidDisplay(SeqListL)/*显示顺序表L中的数据元素*/{inti;for(i=0;i=L.last;i++){printf(%d,L.elem[i]);}printf(\n);}（4）创建“seqlist.c”文件完成顺序表的创建、查找、插入、删除等操作。选择“文件|新建”弹8出如图6所示的对话框，选择“Files”选项卡中的“C++SourceFile”，在“File”文本框中输入文件的名字“seqlist.c”，如图6所示，然后选择“OK”按钮。图6在文件“seqlist.c”中输入代码如下：#includecommon.h#includeseqlist.hvoidmain(){SeqList*l;intp,r,q;int*e;inti;l=(SeqList*)malloc(sizeof(SeqList));e=(int*)malloc(sizeof(int));printf(请输入线性表的长度:);scanf(%d,&r);l-last=r-1;9printf(请输入线性表的各元素值:\n);for(i=0;i=l-last;i++){scanf(%d,&l-elem[i]);}/*在顺序表中查找*/printf(请输入要查找的元素值:\n);scanf(%d,&q);p=Locate(*l,q);if(p==-1)printf(在此线性表中没有该元素!\n);elseprintf(该元素在线性表中的位置为:%d\n,p);/*顺序表的插入操作*/printf(请输入要插入的位置:\n);scanf(%d,&p);printf(请输入要插入的元素值:\n);scanf(%d,&q);InsList(l,p,q);printf(插入后的顺序表为：);Display(*l);/*顺序表的删除操作*/printf(请输入要删除的元素位置:\n);scanf(%d,&p);DelList(l,p,e);printf(删除后的顺序表为：);Display(*l);printf(删除的元素值为:%d\n,*e);}（5）测试数据10输入线性表的长度为：5输入线性表的各元素值：1223564567输入要查找的元素值：23输入要插入的位置：2输入要插入的元素值：33输入要删除的元素位置：3（6）运行结果图7运行结果图2．建立单链表，实现其基本操作（包括创建、查找、插入、删除等），并且用数据进行测试。【提示】实现方法同顺序表。3．若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标。要求：（1）给定一个城市名，返回其位置坐标。（2）给定一个位置坐标P和距离D，返回所有距P的距离小于等于D的城市。4．约瑟夫环问题。约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方11向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如m的初值为20；n=7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。12实验二栈和队列的基本操作实现一、实验目的1．掌握栈的基本操作和具体的函数定义。2．掌握队列的基本操作和具体的函数定义。3．栈的应用。二、实验要求1．认真阅读和掌握本实验内容所给的程序。2．上机运行实验内容中的程序，并对程序进行分析。3．完成自编程序，并上机调试运行。三、实验内容1．以顺序栈为存储结构，实现栈的基本操作，包括初始化栈、进栈、出栈、判断栈空等。2．数制转换。编写程序，将十进制整数N转换为d进制数，其转换步骤是重复以下两步，直到N等于0。X=Nmodd（其中mod为求余运算）N=Ndivd（其中div为整除运算）测试数据：以十进制到二进制转换为例输出结果为：（789）10→（1100010101）2注意：要求使用栈的基本运算（包括InitStack（S），Pop（S），Push（S），IsEmpty（S）。应引用栈的头文件实现）。3．编写程序，判别表达式中左、右括号是否配对。4．回文判断。称正读与反读都相同的字符序列为“回文”序列。试编写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属于该模式的字符序列，而‘1+3&3-1’则不是。13实验三串和数组的应用一、实验目的1．掌握串的定义和基本操作。2．掌握数组的顺序存储及操作。二、实验要求1．认真阅读和掌握本实验内容所给的程序。2．上机运行实验内容中的程序，并对程序进行分析。3．完成自编程序，并上机调试运行。三、实验内容1．运行如下程序。程序一：串的操作。以下程序实现用于判定串s2是否是串s1的子串。若是子串，返回其在主串中的位置；否则返回-1。#include“stdio.h”#include“string.h”#defineMaxLen20typedefstruct{charch[MaxLen];intlen;}strtype;voidcreate(strtype*s,charstr[])//建立字符串{strcpy(s-ch,str);s-len=strlen(str);}intindex(strtype*s1,strtype*s2)//模式匹配{inti=0,j,k;while(is1-len){j=0;if(s1-ch[i]==s2-ch[j]){k=i+1;j++;while(ks1-len&&s2-len&&s1-ch[k]==s2-ch[j]){k++;j++;}if(j==s2-len)break;14elsei++;}elsei++;}if(i=s-len)return–1;elsereturn(i+1);}voidmain()//主程序{strtype*s1,*s2;intn;charstr[MaxLen];s1=(strtype*)malloc(sizeof(strtype));s2=(strtype*)malloc(sizeof(strtype));printf(“thestring：”);gets(str);create(s1,str);printf(“thesubstring：”);gets(str);create(s2,str);n=index(s1,s2);if(n0)printf(“thesubstring’slocation：%d\n”,n);elseprintf(“nosubstring.\n”);}2．对于二维数组A[m][n]，其中m≤80,n≤80，读入m和n，然后读该数组的全部元素，对如下二种情况分别编写相应函数：a.求数组A靠边元素之和；b.当m=n时，分别求两条对角线上的元素之和，否则打印出m≠n的信息。3．编写程序，实现将A[0…n-1]中所有奇数移到偶数之前。要求不另增存储空间，且时间复杂度为为O(n)。4．以下是一个5×5阶螺旋方阵。编写程序实现输出该形式的n×n(n10)阶方阵(顺时针方向旋进)。151234516171819615242520714232221813121110916实验四二叉树的操作一、实验目的掌握二叉树的遍历操作及应用。二、实验要