数据结构实验指导书

数据结构与算法分析课程实验说明一、实验目的数据结构与算法分析是信息管理与信息系统专业一门重要的专业基础课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度：1）内容丰富，学习量大，给学习带来困难； 2）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； 3）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据数据结构与算法分析课程本身的技术特性，设置课程实验环节十分重要。通过实验实践内容的训练，突出创新性思维训练的特征，可以达到以下几方面目标： （1）加深对课堂讲授内容的理解实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变"活"，起到深化理解和灵活掌握教学内容的目的。不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。（2）培养学生软件设计的综合能力平时的练习较偏重于如何编写功能单一的"小"算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练，有利于培养和提高学生的实践创新能力。二、实验实施方式整个课程实验题目根据涉及的知识点范围、难度及工作量，共分三种类型：（1）基础型实验：该类实验的目的在于强化学生对课程基础知识的掌握，实验题目一般设置为对教材算法的设计和实现，一个题目通常只覆盖课程中一个知识点，工作量及难度小，所有学生均有能力完成，在教学中属于必选实验内容，要求所有学生必须按规定时间独立完成；（2）提升型实验：该类实验的目的在于提升学生对课程知识掌握及运用的水平，培养学生分析及解决问题的能力，实验题目一般设置为一些具体应用问题的数据结构及算法设计和实现，一个题目通常会覆盖课程中几个知识点，工作量和难度会高于基础验证型实验，此类题目属于可选的实验项目，教学中鼓励同学们自主选题并在规定时间内独立完成，完成情况将在实验成绩中予以反映，有助于加强学生学习自主性、创新思维和实践动手能力培养。（3）综合训练项目：综合训练项目题目往往涉及课程中多个章节中的多个知识点，而且都与实际问题有关，分析、设计和实现的工作量及难度较大，属于可选的实验内容，鼓励学生自由组合，以项目小组的形式完成，每个小组人数最多不得超过三人。综合训练项目的引入，可以有效激发学生探究知识的积极性，增强课程学习的趣味性，可以进一步提升学生综合运用课程理论知识分析和解决实际问题的能力以及培养学生正确的设计思想、理论联系实际的作风、团结协作和团队精神、严肃认真、实事求是的科学态度和勇于探索的创新精神。具体实施共分两个环节：（1）课内环节：本课程实验课内学时共16学时，共安排了8个实验，每个实验2学时，由于学时有限，课内学时的主要实验任务是在教师指导下完成基础型实验项目，以保证课程实验基本目标的达成。在完成基础型实验任务的前提下，学生可以利用剩余课内学时完成提升型实验项目；（2）课外环节：在完成基础型实验的前提下，学生可利用课外时间完成提升型实验和综合训练项目，教师利用课外时间对学生进行指导，并利用少量理论课学时对提升型实验及综合训练项目进行讲评，学生也可以利用这段学时进行综合训练项目的汇报和展示。三、实验基本要求课程实验要求学生在规定的时间内完成实验项目并参加验收。具体要求学生根据所选问题分析设计思路、选择数据结构描述、确立算法过程、用一种计算机语言（例如Turbo C）编写出详细的实现程序，然后通过上机反复调试与修改，直到获得满意的结果为止。不要求所有学生编写的算法和程序完全一致，但应力求编写的算法和程序更优秀、综合指标更好。通过本课程的实验，应使学生达到以下的基本要求 : 1. 能根据加工数据对象的特征，选择适当的数据结构、存贮结构及相应算法，基本掌握各种算法在时间和空间的分析技巧。 2. 能够进行算法设计和程序设计，并且使所设计的程序结构清楚，正确易读，并上机调试通过。 3初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5. 设计的题目要求达到一定工作量，并具有一定的深度和难度。6. 较强的实习、实践能力；较强的分析问题、解决问题的能力。四、实验考核 1、考核内容（1）基础型实验及提升型实验：每位学生每个实验在规定时间前提交程序代码及实验报告书一份（实验报告书规范见本指导书后“综合训练及实验报告书规范”），指导教师根据学生所编写实验程序运行情况及实验报告质量进行评分；（2）综合训练项目：每组学生每个项目在规定时间前提交报告书一份（报告书规范见本指导书后“综合训练及实验报告书规范”），并可在课内讲评时对项目实现情况公开汇报和展示，指导教师根据小组所编写程序运行情况、报告书质量及展示汇报表现进行评分。2、考核方法（1）课程实验成绩：基础型实验及提升型实验评分结果计入课程实验成绩，课程实验成绩再以4/18的比例计入课程总评成绩，其中实验1至实验6每个实验程序评分满分5分，报告评分满分5分，实验7、8每个实验程序评分满分10分，报告评分满分10分。若学生某个实验只完成基础型实验，则其程序和报告至多只能得到该次实验程序和报告满分的60%，在此基础上，若学生完成了提升型实验，则由考核教师酌情加分，多做多加，质量高的多加，但该次实验的最终得分不得超过规定的该次实验程序和报告满分；（2）综合训练项目考核成绩直接计入课程总评成绩，每个综合训练项目满分4分，由考核教师酌情给分。五实验指导材料课程实验任务、要求及指导以本指导书为主，还可参考以下材料：1严蔚敏 吴伟民，.数据结构(C语言版)，2012，清华大学出版社；2严蔚敏 吴伟民，.数据结构题集(C语言版)，1999，清华大学出版社；3徐孝凯，数据结构课程实验，2002，清华大学出版社；4孟佳娜 胡潇琨，算法与数据结构实验与习题，2004，机械工业出版社；VisualC+6.0实验环境介绍一进入C+工作环境双击Windows桌面上的Visual C+ 6.0图标或单击Windows桌面上“开始”按钮，在“程序”中选择“Visual C+6.0”运行即可。二编译、运行C程序1.创建一个新的工程文件（Project file）启动Visual C+6.0 编译系统后，出现“Microsoft Developer Studio”窗口，该窗口菜单条有个菜单项（如图1所示）：（1）单击“File”菜单，在其下拉菜单中选择“New”，屏幕上出现一个“New”对话框，在该对话框中选择“Projects”标签，出现“Project”对话框。（2）选择工程类型为“Win32 Console Application”，这时，在右边的Platforms选框中就会出现Win 32。（3）输入工程名字。在“Project name”选框中输入所指定的工程文件名字，例如： 1st。（4）输入路径名。在“Location”选框中，输入你将要把所建立的工程文件放人何处的路径名。例如，要将工程文件放在E 盘下已建立好的子目录E:sw1001子目录中，所以该选取路径为：E:sw10011st。选择“OK”按钮，该工程文件已建立。图1 创建新的工程文件2.建立源文件再次选择“File”菜单中的“New”选项，在四个标签中选择“File”标签，在其对话框选项中，选择“C+ Source File”，并在右边的Add project的选择框内打勾，激活其下面的选项，然后在File框内输入源文件名（如1st），单击“OK”按钮，出现编辑屏幕，即可编写程序（如图2和图3所示）。图2 建立源文件图3 编辑源文件3.编译连接和运行源程序程序编好后要进行编译连接和运行，步骤如下：选择“Build”菜单，单击下拉菜单中的“Compile 1st.cpp”，这时系统开始对当前的源程序进行编译，在编译过程中,将所发现的错误显示在屏幕下方的“Build”窗口中。根据错误提示，修改程序后再重新编译，如还有错误，再继续修改、编译，直到没有错误为止。编译无误后进行连接，这时选择“Build”菜单中的“Build 1st.exe”选项。同样，对出现的错误要进行更改，直到编译连接无错为止。这时，在“Build”窗口中会显示如下信息：1st.obj- 0 error(s), 0 warning(s)，说明编译连接成功，并生成以源文件名为名字的可执行文件（1st.exe）。运行程序，选择“Build”菜单中的“! Execute 1st.exe”选项。这时，会出现一个“MS-DOS”窗口，输出结果显示在该窗口中（如图4和图5所示）。运行结束后，可以回到“File”菜单，点击“Close Workspace”选项，关闭当前文件窗口。若要编辑新的源程序，可以再次打开“File”菜单，重新建立工程文件，步骤如上所述; 也可以点击“File”菜单中的“Open Workspace”选项，打开一个已经存在的源文件。图4 编辑运行源程序图5 编译连接及结果实验一 线性表的顺序表示实现实验目的：1、熟悉TC环境的使用以及程序的输入，编辑，调试，运行的全过程；2、掌握线性表的顺序结构的静态及操作特点；3、掌握线性表的顺序结构的静态存储和常见操作在C语言环境中的实现方法；实验要求：1、认真阅读和掌握本实验相关知识及算法；2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。实验内容：A.基础型实验:1、根据教材所给类C语言算法，结合C语言特点，实现程序完成对于以整型数据为数据元素的顺序表的定义、初始化及数据的显示等操作。2、根据教材所给类C语言算法，结合C语言特点，实现程序完成对于以整型数据为数据元素的顺序表的插入、删除及数据的显示等操作。B.提升型实验：1、有一个表元素按值递增排列的顺序表，在A.1的基础上编写函数实现删除表中多余的元素。2、完成程序，实现顺序表元素的就地逆置（即申请少量变量的前提下进行元素逆置）3、实现程序利用顺序表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。实验内容示例：A.1 源代码：#define LIST_INIT_SIZE 100#define LISTINCREMENT 10struct sqlist int *elem; int length; int listsize;int initlist(struct sqlist *l) /* 初始化 */ (*l).elem=(int *)malloc(100*sizeof(struct sqlist); if(!(*l).elem) return(-1); (*l).length=0; (*l).listsize=100; return(1);void show_flag(int fl,char *func_name) /* 函数执行状态判断 */ switch(fl) case -2:printf("n%s PARA ERROR!",func_name);exit(0); case -1:printf("n%s OVERFLOW!",func_name);exit(0); case 1:printf("n%s OK!",func_name);break; ;int show_elem(struct sqlist *l) /* 数据显示 */ int loopnum,i; loopnum=(*l).length; for(i=1;i<=loopnum;i+) printf("nNO.%d element data=%d",i,(*l).elemi-1); ; return(1);int list_insert(struct sqlist *l,int e,int i) /* 数据插入 */ int *p; int *q; if(i>(*l).length+1)|(i<1) return(-2); q=&(*l).elemi-1); for(p=&(*l).elem(*l).length-1);p>=q;-p)*(p+1)=*p; *q=e; +(*l).length); return(1); int list_delete(struct sqlist *l,int i) /* 数据删除 */ int *p; int *q; int *x; int y; if(i<1)|(i>(*l).length)return(-2); q=(*l).elem+(*l).length-1; p=&(*l).elemi-1); y=(*l).elemi-1; for(+p;p<=q;+p) *x=*(p-1); *(p-1)=*p; printf("n* %d <<- %d ",*x,*p); ; printf("n NO.%d elem VALUE=%d was deleted!",i,y); -(*l).length; return 1;main()struct sqlist *sq; char *func_namep; int flag; clrscr(); printf("n<<<<< PROGRAM START >>>>>>"); flag=initlist(sq); func_namep="initlist" show_flag(flag,func_namep); (*sq).elem0=111; (*sq).elem1=222; (*sq).elem2=333; (*sq).length=3; flag=show_elem(sq); func_namep="show_elem" show_flag(flag,func_namep); flag=list_insert(sq,456,4); func_namep="list_insert" show_flag(flag,func_namep); show_elem(sq); flag=list_delete(sq,2); func_namep="list_delete" show_flag(flag,func_namep); show_elem(sq); printf("n<<<<<< PROGRAM END >>>>>>"); B.1源代码：Void delete(List A,int n) int i=0,j; while(i<=n-2) if (Ai!=Ai+1) i+; else for(j=(i+2);j<=n;j+) Aj-1=Aj; n-; 实验二 线性表的链式表示实现实验目的：1、掌握线性表的链式结构的静态及操作特点；2、掌握线性表的链式结构的存储结构和常见操作在C语言环境中的实现方法；实验要求：1、认真阅读和掌握本实验相关知识及算法；2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。实验内容：A.基础型实验:1、根据教材所给类C语言算法，结合C语言特点，实现程序完成对于以整型数据为数据元素的线性单链表的定义、初始化、插入、删除及数据的显示等操作。2、实现程序完成对于以整型数据为数据元素的线性双向循环链表的定义、初始化、插入、删除及数据的显示等操作。3、构建一个双向链表，实现插入、查找和删除操作。B.提升型实验:1、建立一个单循环链表并实现单循环链表上的逆置。所谓链表的逆置运算(或称为逆转运算)是指在不增加新结点的前提下，依次改变数据元素的逻辑关系，使得线性表(al，a2，a3，an)成为(an，a3，a2，a1)。2、利用循环链表的结构特点解决约瑟夫环的出列问题。3、实现程序判断双循环链表是否对称。4、实现程序利用带头结点的单链表完成一个班级的一个学期的所有课程的管理：能够增加、删除、修改学生的成绩记录。5、试设计一元多项式相加（链式存储）的加法运算。 A（X）=7+3X+9X8+5X9 B（X）=8X+22X7-9X8 1建立一元多项式； 2输出相应的一元多项式； 3相加操作的实现。实验内容示例：A.1源代码：#define NULL 0#define LEN sizeof(struct linklist)struct linklist int data; struct linklist *next;struct linklist * create_list(int n) /* 初始化 */ int i; struct linklist *p,*l; l=(struct linklist *)malloc(LEN); l->next=NULL; for(i=n;i>0;i-) p=(struct linklist *)malloc(LEN); p->data=100+i; p->next=l->next; l->next=p; ; return l;void show_elem(struct linklist *l) /* 数据显示 */ struct linklist *p; int j; p=l->next; j=1; while(p) printf("nNo.%d -%d",j,p->data); j=j+1; p=p->next; ; printf("-");int listdelete_l(struct linklist *l,int i,int *e) /* 数据删除 */ struct linklist *p,*q; int j=0; p=l; while(p->next&&j<i-1) p=p->next; j=j+1; ; if(!(p->next)|(j>i-1) return(-1); q=p->next; p->next=q->next; *e=q->data; free(q); return(1);main() int m=10; int *de; struct linklist *sl; printf("n-n"); *de=3; sl=create_list(m); show_elem(sl); listdelete_l(sl,1,de); show_elem(sl); printf("n deleted elem=%d",*de);A.3源代码： #include<stdio.h> #include<malloc.h> typedef struct dupnode int data； struct dupnode *next,*prior；dulinklist；#include”hhh”dulinklist *create() /create函数用来构建双向链表dulinklist *head,*p，*r; int i，n；head=(dulinklist*)malloc(sizeof(dulinklist )；head->next=NULL；head->prior=NULL；r=head；printf(“请输入所建双向链表中结点的个数：n”)；scanf(“d”,n)；for(i=l；i<=n；i+)p=(dulinklist*)malloc(sizeof(dulinklist)； printf(”输入结点的值：n”)； scanf(”%d，&p->data)； p->next=NULL； r->next=p； p->prior=r； r=r->next； return(head)；void find(dulinklist *h) /f按序号查找某个结点的功能。int k,i；dulinklist *p；p=h；i=0：printf(”输入要查找结点的序号：n”)； scanf(”%d”,&k)； while(p!=NULL)&&(i<k) p=p->next； i+： if(p)printf(”所查到的结点的值为：n”)； printf(”%dn”,p->data)； elseprintf(”没找到该结点! n”)；/insdulist函数用来实现在双向链表中按序号插入结点的功能dulinklist *insdulist(dulinklist *head，int i，int x)dulinklist *p，*s；int j；p=head；j=0；whi1e(p->next!=head)&&(j<i-1) /找到第i-1个结点 p=p->next；j+；If(j=i-1)s(dulinklist*)malloc(sizeof(dulinklist)；s->data=x；s->prior=p；s->next=p->next；p->next->prior=s；p->next=s；elseprintf(”errorn”)；return head；/deledulist函数实现在双向链表中按序号删除某个结点的功能dulinklist *deledulist(dulinklist *head，int i)dulinklist *p；int j；p=head； j=0while(p->next!=head)&&(j<i)p=p->next； j+； If(j=i)p->prior->next=p->next；p->next->prior=p->prior；free(p)；else printf(”error n”)；return head； void output(dulinklist *h) /output函数用来输出整个双向链表的结点值 dulinklist *p；p=h->next；while(p!=NULL)printf(”输出该双向链表的结点，分别为： n”)；printf(”%dn”,p->data)；p=p->next； void main()dulinklist *head；int flag=l，i，k，x；while(flag) printf(”1建立双向链表 n”)； printf(”2查找某个结点 n”)； printf(”3插入一个结点 n”)； prtntf(”4删除一个结点 n”)； printf(”5退出 n”)；printf(”请输入选择：n“)；scanf(”%d”，&i)；switch(i) case 1：head=create0；break； case 2：find(head)；break； case 3：printf(”输入待插的结点的序号及新插入结点的data值. n”); scanf(”%d%d”，k，x)； head=insdulist(head，k，x)； output(head)； break； case 4：printf(”输入要删除的结点的序号. n”)；scanf(”%d，k)；head=deledulist(head，k)；output(head)；break；case 5: flag=0；/while循环结束B.1源代码：#define NULL 0#include<stdioh>#include<malloch>typedef struct node int num；struct node *next； linklist；#include”h1h”void output(linklist *head)linklist *p；p=head->next；while(p!=head)printf(”d”，p->num)；p=p->next；printf(”n”)；Linklist *creat(int n) /建立单循环链表 int k; linklist *head,*r,*p； p=(linklist*)malloc(sizeof(linklist)； head=p； r=p； p->next=p；for(k=1；k<=n；k+) p=(linklist *)malloc(sizeof(linklist)； p->num=k； r->next=p； r=p； p->next=head；return(head)；linklist *invert(linklist *head) 逆置函数Linklist *p，*q，*r；p=head->next；q=head；while(p!=head) r=q； q=p； p=p->next； q->next=r； head->next=q； return(head)； void main() int n； Linklist *head； printf(“输入所建立的循环链表的结点个数：n”)； scanf(“%d”，n)； head=creat(n)； printf(”输出建立的单循环链表：n”)； output(head)； printf(”现在进行逆置! n”)； head=invert(head)； printf(”输出进行逆置运算后的单循环链表的结点信息! n”)； output(head)； B.2源代码：#include<stdio.h>typedef struct linknode int n,m; struct linknode *next; node;node *p,*q;int i,j,k=0,m1;void create() node *head,*s; int x,y; printf("nplease input number of node:"); scanf("%d",&k); printf("nplease input digital & code:"); scanf("%d%d",&x,&y); head=(node *)malloc(sizeof(node); p=head; p->n=x; p->m=y; p->next=NULL; i=2; while(i<=k) printf("nplease input digital & code:");scanf("%d%d",&x,&y);s=(node *)malloc(sizeof(node);s->n=x;s->m=y;s->next=NULL;p->next=s;p=s;if(i=k) p->next=head; q=p; p=head; i=i+1; p=head; for(i=1;i<=k;i+) printf("%dt",p->n);p=p->next; void joseph() j=1; printf("nplease input inital password :"); scanf("%d",&m1); for(i=1;i<=k;i+) while(j<m1) q=p;p=p->next;j+; m1=p->m; getch(); printf("%d",p->n); q->next=p->next; free(p); p=q->next; j=1; main() create(); joseph();B.3源代码：struct NodeT data;Node *next;Node *prior;class DLinkListprivate:Node *Head;int count;public:DLinkList() ;/构造函数， 创建空双循环链表DLinkList();/析构函数，删除表空间void CreateList(int n);/创建具有n个元素的双循环链表void ListDisplay();/输出表元素 void symmetry();/判断链表中的元素是否对称;/双循环链表类的实现DLinkList:DLinkList()/构建函数，建一空双循环链表Head=new Node;Head->next=Head;Head->prior=Head;count=0;DLinkList:DLinkList()/析构函数，释放链表所占空间Node *p,*q;while(q->next!=Head) q=q->next; /定位q到尾结点？while(Head!=Head->next)/从头结点开始，依次释放结点p=Head;Head=Head->next;q->next=Head;Head->prior=q; delete p;count-;Head=NULL;/头结点指向空void DLinkList:CreateList(int n)/尾插法(正序)创建具有n个元素的双循环链表Node *p,*s;/设置工作指针。p指向尾结点p=Head;cout<<"请依次输入"<<n<<"个元素值："<<endl;for(int i=1;i<=n;i+)s=new Node;/新建元素结点 cin>>s->data;/输入新建数据元素值s->next=p->next;/新结点链入表尾p->next=s;s->prior=p;Head->prior=s;p=s;count+;void DLinkList:ListDisplay()/显示链表Node *p;p=Head->next;int i=1;while(p!=Head)cout<<i<<"t"cout<<p->data<<endl;p=p->next;i+;void DLinkList:symmetry()Node *p,*s;int i;p=Head->next;s=Head->prior;for(i=1;i<=count/2;i+)if(p->data!=s->data)cout<<"链表不对称"<<endl;break;p=p->next;s=s->prior;if(i=count/2+1)cout<<"链表对称"<<endl;#include<iostream.h>/cout,cintypedef int T;#include "dLinklist.h"void main() /主函数int i;DLinkList L;/int choice; do/显示主菜单cout<<"1-创建双循环链表n"cout<<"2-判断链表是否对称n"cout<<"3-显示链表n"cout<<"4-退出n"cout<<"Enter choice:"cin>>choice;switch(choice)case 1:/创建链表cout<<"请输入要创建的链表中元素个数:"cin>>i;/将创建的链表中数据元素的个数cout<<endl;L.CreateList(i);break;case 2:/判断链表是否为空L.symmetry();break;case 3:/显示表L.ListDisplay();cout<<endl;break;case 4:/退出cout<<"结束运行"<<endl;break;default:/cout<<"Invalid choicen"break;while(choice!=4);/结束实验三 串的表示实现实验目的：1、掌握串结构的静态及操作特点；2、掌握串结构的静态存储和常见操作在C语言环境中的实现方法；实验要求：1、认真阅读和掌握本实验相关知识及算法；2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。实验内容：A.基础型实验:1、实现程序，基于串的定长顺序存储表示方法，参照教材所述类C语言算法，主要实现对于以字符型数据为数据元素的串结构的定义、初始化、赋值等操作。2、实现程序，基于串的堆分配存储表示方法，参照教材所述类C语言算法，主要实现对于以字符型数据为数据元素的串结构的定义、初始化、赋值、求子串等操作。3、编程实现字符串复制。4、编程实现求字符串的子串。5、编程实现字符串连接程序。B.提升型实验:1、编程实现串查找和替换。2、编程实现字符串模式匹配的KMP算法。实验内容示例:A.3源代码：#include <stdio.h>#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN +1;void strLengh(Sstring S) int m; for(m=1;Sm!='0'm+); S0=m-1; int stringcopy(SString &T,SString S) int i; for(i=1;i<=S0;i+) Ti=Si; Ti='0' T0= S0; return T0; void main( ) Sstring T; unsigned char SMAXSTRLEN+1; printf("Please input the main String:"); scanf("%s",S+1); strlength(S); printf("n THE COPY STRING IS :%s(length=%d)n",T+1,stringcopy(T,S);A.4源代码：#include <stdio.h >#define MAXSTRLEN 255Typedef unsigned char SstringMAXSTRLEN+1;void strLengh(SString S)int m;for(m = 1;Sm!='0;m+);S0=m-1; int SubString(SString &Sub,SString S,intpos,int len)int i;if(pos<1 |pos > S0 |len<0 | len > S0 -pos+1)printf("Error!positon or length is out of range n“);return 0;for(i=1;i<=len;i+)Subi = Spos+i - 1;Subi='0'Sub0=len;return 1;void main()SString Sub;int pos,len;unsigned char SMAXSTRLEN+1;printf("Please input the main String: n"); scanf("%s",S+1);strLengh(S);printf("Please input the position of SubString:");scanf("%d",&pos);printf("Please input the length of SubString:");scanf("%d",&len);if(SubString(Sub,S,pos,len)printf("nThe SubString is: % s nSubString.length =%d n",Sub+1,Sub0);B.2源代码：#include < stdio.h >#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1;void strLength(SString S)int m;for(m=1;Sm!='0'm+);S0=m-1;void get_next(SStringT,int *next) int j,k;j=1;next1=-1;k=-1; while(j<T0)if(k=-l|Tj=Tk) +j; +k; nextj=k; else nextj=k; int Index_KMP(Sstring S,Sstring T,int pos,int *next) int i,j; i=pos; j=1; get_next(T,next); while (i<S0&&j<T0) if(j=-1|Si=Tj) +i; +j; else j =nextj; if (j>=T0) return (i-T0); else return 0; void main() SString S,T; int pos; int nextMAXSTRLEN; int *p=&next1; int r;pintf("输入主串S:");scanf("* s",s+i);printf("# # T:");scanf("% s",T+1);scanf("% d",&pos);if(r=Index_KMP(S,T,pos,p)printf("模式串在主串中的位置为: %dn", r);else printf("匹配失败！：");实验四 特殊矩阵、稀疏矩阵的表示实现实验目的：1、掌握特殊矩阵的压缩存储思路和方法以及操作特点；2、掌握特殊矩阵的存储方法以及常见操作在C语言环境中的实现方法；3、掌握稀疏矩阵的压缩存储思路和方法以及操作特点；4、掌握稀疏矩阵的存储方法以及常见操作在C语言环境中的实现方法；实验要求：1、认真阅读和掌握本实验相关知识及算法；2、从实验内容所给题目中任选至少一题编写程序并调试运行通过；3、保存及打印所编程序及运行结果，并结合所学课堂内容深入分析理解。实验内容：A.基础型实验:1、实现程序，基于对称矩阵的压缩存储表示方法，实现对于以整数数据为数据元素的对称矩阵的压缩存储及按行、列下标查询特定元素等操作。2、实现程序，基于稀疏矩阵三元组表存储表示方法，参照教材所述类C语言算法，实现对于以整数数据为数据元素的稀疏矩阵的存储、求转置阵等操作。B.提升型实验:1、利用三元组的存储结构实现矩阵的创建及其相加。2、利用三元组的存储结构实现矩阵的创建及其相乘。实验内容示例：B.1源代码：#define maxsize 100typedef int elemtp;typedef struct int i,j,v; tripletp;tripletp amaxsize,bmaxsize,cmaxsize;int k,m,n,ta,tb,pa,pb,pc,sum;create(int t,tripletp lmaxsize) l0.i=m; l0.j=n; l0.v=t; printf("please input triple table:n"); for(k=1;k<=t;k+) scanf("%d%d%d",&lk.i,&lk.j,&lk.v);matadd(tripletp a,tripletp b,tripletp c) pa=1; pb=1; pc=1; while(pa<=ta&&pb<=tb) if(apa.i=bpb.i) if(apa.j=bpb.j) sum=apa.v+bpb.v; if(sum) cpc.v=sum; cpc.i=apa.i; cpc.j=apa.j; pc+; pa+; pb+; else pa+; pb+; else if(apa.j>bpb.j) cpc.v=bpb.v; cpc.i=bpb.i; cpc.j=bpb.j; pc+; pb+; else cpc.v=apa.v; cpc.i=apa.i; cp