本学期开设的《数据结构与算法》课程已经告一段落，现就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。
一、《数据结构与算法》知识点
第二章具体地介绍了顺序表的概念、基本运算及其应用。基本运算有：初始化表、求表长、排序、元素的查找、插入及删除等。元素查找方法有：简单顺序查找、二分查找和分块查找。排序方法有：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序及归并排序等。最后介绍了顺序串的概念，重点在于串的模式匹配。
链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。
堆栈与队列是两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。
第七章二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序。
树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。散列结构是一种查找效率很高的一种数据结构。本章的主要知识点有：散列结构的概念及其存储结构、散列函数、两种冲突处理方法、线性探测散列和链地址散列的基本算法以及散列结构的查找性能分析。
最后一章介绍了图的概念及其应用，是本书的难点。图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解aov网和拓扑排序及其算法。
二、对各知识点的掌握情况
总体来看，对教材中的知识点理解较为完善，但各个章节均出现有个别知识点较为陌生的现象。现将各个章节出现的知识点理解情况列举如下。
链表这一章中，除对双向循环链表这一知识点理解困难之外，其他的知识点像单链表的建立和基本算法等都较为熟悉。
接下来的有关堆栈以及队列的知识点比较少，除有关算法较为特殊以外，其余算法都是先前学过的顺序表和链表的知识，加上思想上较为重视，因此这部分内容是我对全书掌握最好的一部分。不足之处仍然表现在算法的性能分析上。
在学习第六章时感觉较为吃力的部分在于矩阵的应用上，尤其对矩阵转置算法的c语言描述不太理解。稀疏矩阵相加算法中，用三元组表实现比较容易理解，对十字链表进行矩阵相加的方法较为陌生。
第七章是全书的重点，却也有一些内容没有完全理解。在第一节基本概念中，二叉树的性质容易懂却很难记忆。对二叉树的存储结构和遍历算法这部分内容掌握较好，能够熟练运用，而对于二叉树应用中的哈弗曼树却比较陌生。
第八章内容较少，牵涉到所学的队列的有关内容，总体来说理解上没有什么困难，问题依旧出现在算法的性能分析上。
散列结构这一章理解比较完善的知识点有：基本概念和存储结构。散列函数中直接定址法和除留余数法学得比较扎实，对数字分析法等方法则感觉较为陌生。对两种冲突处理的算法思想的理解良好，问题在于用c语言描述上。
最后一章，图及其应用中，图的定义、基本运算如图的生成等起初理解有困难，但随着学习深入，对它的概念也逐步明朗起来。邻接矩阵、邻接表和逆邻接表掌握较好，而对十字链表和邻接多重表则较为陌生。感觉理解较为吃力的内容还有图的遍历（包括深度和广度优先遍历），最小生成树问题也是比较陌生的知识点。最短路径和aov网学习起来感觉比较轻松，而对于c语言描述却又不大明白。
三、学习体会
接触这门课程以前，我对该课程所学的内容有许多疑点，例如：这门课是否是在介绍一种新的计算机语言？如果不是，那么学习这门课程的用途是什么？为什么市面上各种介绍数据结构的资料采用了不同的计算机语言，如c、c++还有java？我的c语言学得不好，对学习这门课是否有影响
这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到
自己的程序中再加以必要的连接以完成程序的编写。针对这一情况，我会严格要求自己，熟练掌握算法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问题的能力。
四、对《数据结构与算法》课程教学的建议
1、建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生保持良好的精神状态。
2、建议在课时允许的情况下，增加习题课的分量，通过课堂的习题讲解，加深对知识点的掌握，同时对各知识点的运用有一个更为直观和具体的认识。
《数据结构与算法》课程学习总结报告
100401200510计本（4）班章兴春
本学期所学习的《数据结构与算法》课程已经告一段落，就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。以便在所学习知识有更深刻的认识。
一、《数据结构与算法》知识点：
学习数据结构之前、一直以为数据结构是一门新的语言、后来才知道学习数据结构是为了更加高效的的组织数据、设计出良好的算法，而算法则是一个程序的灵魂。经过了一学期的数据结构了，在期末之际对其进行总结。首先，学完数据结构我们应该知道数据结构讲的是什么，数据结构课程主要是研究非数值计算的研究的程序设计问题中所出现的计算机处理对象以及它们之间关系和操作的学科。
第二章具体地介绍了顺序表的定义、特点及其主要操作，如查找、插入和删除的实现。需要掌握对它们的性能估计。包括查找算法的平均查找长度，插入与删除算法中的对象平均移动次数。
第三章介绍了堆栈与队列这两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。算法上要求掌握进栈、退栈、取栈顶元素、判栈空盒置空栈等五种操作及掌握使用元素个数计数器及少用一个元素空间来区分队列空、队列满的方法。
第四章串和数组中，我们知道串是一种特殊的线性表，是由零个或多个任意字符组成的字符序列。串的储存结构分为紧缩模式和非紧缩模式。
基本运算需掌握求串长、串赋值、连接操作、求子串、串比较、串定位、串插入、串删除、串替换等。
第五章二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序。
树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。
第六章介绍了图的概念及其应用，图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解aov网和拓扑排序及其算法。
最后两章集体说明了查找和排序算法，查找教材上介绍了静态查找表和哈希查找表，静态查找表中介绍了顺序查找、折半查找以及分块查找。哈希法中，学习要点包括哈希函数的比较；解决地址冲突的线性探查法的运用，平均探查次数；解决地址冲突的二次哈希法的运用。
排序是使用最频繁的一类算法，可分为内部排序和外部排序。主要需要理解排序的基本概念，在算法上、需要掌握插入排序（包括直接插入排序算法、折半插入排序算法），交换排序（包括冒泡排序算法、快速排序递归算法）,选择排序（包括直接选择排序算法、堆排序算法）等。
三、学习体会：
多做实验！这个就没有太多理由了，我一直觉得编程是一门熟练科学，多编程，水平肯定会提高，最重要的是能够养成一种感觉，就是对程序对算法的敏感，为什么那些牛人看一个算法一下子就看懂了？而自己要看很久才能弄懂，而且弄懂了过了一阵子又忘记了？其实这个是因为牛人们以前看的程序很多，编得也很多，所以他们有了那种感觉，所以我觉得大家应该多看程序，多写程序，培养自己的感觉。
复习和考试的技巧，我想大家应该都有这样的感觉，就是觉得自己什么都掌握了，但是在考试的时候就是会犯晕，有时候一出考场就知道错在哪个了，然后考完以后一对答案，发现其实考得很简单，应该都是自己会做的，这个就是与自己的复习和考试的技巧有关系了。
然后还有一种题目，就是最后的写算法的题目，我觉得这种题目还是很好解决的，只要是能够自己做出作业的，基本上都会很容易做出来，这也是为什么我前面觉得平时做作业应该自己独立思考的原因，同时做这种题目千万要小心，尤其是题目简单的时候，那肯定会有一些小地方要考虑清楚，一不小心就会被扣掉很多分，这样很不值。
三、对《数据结构与算法》课程教学的建议
3、要更加重视实验的重要性。
金陵科技学院实验报告
学生实验报告册
课程名称：
学生学号：
所属院部：计算机工程学院
（理工类）
算法与数据结构专业班级：计算机统招(1)班
1413101006学生姓名：邢亦波
指导教师：徐永华15——2016学年第2学期
金陵科技学院教务处制
实验报告书写要求
实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用a4的纸张。
实验报告书写说明
实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。
填写注意事项
（1）细致观察，及时、准确、如实记录。（2）准确说明，层次清晰。
（3）尽量采用专用术语来说明事物。
（4）外文、符号、公式要准确，应使用统一规定的名词和符号。（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。
实验报告批改说明
实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。
实验报告装订要求
实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。
实验1顺序表
一、实验目的和要求
掌握顺序表的定位、插入、删除等操作。
二、实验仪器和设备
turboc2.0
三、实验内容与过程（含程序清单及流程图）
1、必做题
（1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。编写主函数测试结果。
（2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回－1。编写主函数测试结果。（3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。
解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新结点x插入到i位置。
（4）删除顺序表中所有等于x的数据元素。
2、选做题
（5）已知两个顺序表a和b按元素值递增有序排列，要求写一算法实现将a和b归并成一个按元素值递减有序排列的顺序表（允许表中含有值相同的元素）。
程序清单：1.（1）
#include#definemaxsize100#definedatatypeinttypedefstructshun{datatypea[maxsize];intlength;}shun;shuns;voidinit(shun*s){}voidsetup(shun*s){
}main()inti;if(s->length==0)printf(“没有数据n”);elsefor(i=0;ilength;i++){}printf(“%-5d”,s->a[i]);inti,j;printf(“需要几个数n”);scanf(“%d”,&s->length);while(s->length>=maxsize){printf(“需要几个数n”);scanf(“%d”,&s->length);}for(i=0;ilength;i++){}scanf(“%d”,&s->a[i]);s->length=0;printf(“溢出n”);
{
}init(&s);setup(&s);display(&s);
1.（2）
length;i++){inti,j;printf(“需要几个数n”);scanf(“%d”,&s->length);while(s->length>=maxsize){printf(“需要几个数n”);scanf(“%d”,&s->length);}for(i=0;ilength;i++){}scanf(“%d”,&s->a[i]);s->length=0;printf(“溢出n”);
if(s->a[i]==x)returni;}return0;}voiddisplay(shun*s){
}main(){
}intx;init(&s);setup(&s);display(&s);printf(“输入xn”);scanf(“%d”,&x);if(find(&s,x))printf(“找到位置是%dn”,find(&s,x));printf(“-1n”);elseinti;if(s->length==0)printf(“没有数据n”);elsefor(i=0;ilength;i++){}printf(“%-5d”,s->a[i]);
#definemaxsize100#definedatatypeinttypedefstructshun{datatypea[maxsize];intlength;}shun;shuns;voidinit(shun*s){s->length=0;
}voidsetup(shun*s){
}voidinsert(shun*s,intx){inti,j;if((s->length+1)>=maxsize){printf(“溢出n”);exit(0);inti,j;printf(“需要几个数n”);scanf(“%d”,&s->length);while(s->length>=maxsize){printf(“需要几个数n”);scanf(“%d”,&s->length);}for(i=0;ilength;i++){}scanf(“%d”,&s->a[i]);printf(“溢出n”);}for(i=0;ilength;i++){if(s->a[i]>=x)break;}for(j=s->length-1;j>=i;j--){s->a[j+1]=s->a[j];}s->a[i]=x;s->length++;}voiddisplay(shun*s){
length;i++)
}intx;init(&s);setup(&s);printf(“输入xn”);scanf(“%d”,&x);insert(&s,x);display(&s);{}printf(“%-5d”,s->a[i]);
1.（4）#include#definemaxsize100#definedatatypeinttypedefstructshun{datatypea[maxsize];intlength;}shun;shuns;voidinit(shun*s){}voidsetup(shun*s){
}voiddelet(shun*s,intx){inti,j;for(i=0;ilength;i++){
}intx;init(&s);setup(&s);printf(“输入xn”);scanf(“%d”,&x);delet(&s,x);display(&s);inti;if(s->length==0)printf(“没有数据n”);elsefor(i=0;ilength;i++){}printf(“%-5d”,s->a[i]);if(s->a[i]==x){
length;j++){s->a[j]=s->a[j+1];}s->length--;i--;}for(i=0;ilength;i++){}scanf(“%d”,&s->a[i]);}}
2.#include#definemaxsize100#definedatatypeinttypedefstructshun{datatypea[maxsize];intlength;}shun;shuna,b,c;voidinit(shun*s){}voidsetup(shun*s){
length;i++){}for(i=0;ilength;i++){
length;j++){
a[j]){
voidcat(shun*a,shun*b){inti,j=0,t;if((a->length+b->length)>=maxsize){
}for(i=0;ilength;i++){}for(j=0;jlength;j++){
}voiddisplay(shun*s){
}inti;if(s->length==0)printf(“没有数据n”);elsefor(i=0;ilength;i++){}printf(“%-5d”,s->a[i]);}for(i=0;ifor(j=i+1;j}if(c.a[i]}t=c.a[i];c.a[j]=t;c.a[i]=c.a[j];c.a[i]=b->a[j];i++;c.a[i]=a->a[i];printf(“溢出n”);exit(0);
main(){
}init(&a);printf(“a初始化n”);setup(&a);init(&b);setup(&b);cat(&a,&b);display(&c);printf(“b初始化n”);
四、实验结果与分析（程序运行结果及其分析）1.（1）
1．（3）
1.（4）
2.金陵科技学院实验报告
五、实验体会（遇到问题及解决办法，编程后的心得体会）
我觉得编程不能只要完成其主要功能就行了，还要考虑到边界值，考虑是否会出错等等。有时候一种方法编不通，不如换种方法编。我觉得编程挺考虑耐心的，恩，就这么多感悟了。
实验2单链表
1、实验目的
掌握单链表的定位、插入、删除等操作。
2、实验要求
（1）注意链表的空间是动态分配的，某结点不用之后要及时进行物理删除，以便释放其内存空间。
（2）链表不能实现直接定位，一定注意指针的保存，防止丢失。
（1）编写程序建立一个单链表，并逐个输出单链表中所有数据元素。（2）在递增有序的单链表中插入一个新结点x，保持单链表的有序性。
解题思路：首先查找插入的位置然后进行插入操作；从第一个结点开始找到第一个大于该新结点值的结点即为插入位置；然后在找到的此结点之前插入新结点；注意保留插入位置之前结点的指针才能完成插入操作。
（3）编写实现带头结点单链表就地逆置的子函数，并编写主函数测试结果。
已知指针la和lb分别指向两个无头结点单链表的首元结点。要求编一算法实现，从表la中删除自第i个元素起共len个元素后，将它们插入到表lb中第j个元素之前。程序清单：
1.（1）
#include#definedatatypechartypedefstructlnklist{datatypea;structlnklist*next;}list;list*s;list*setup(list*s)
}voiddisplay(list*head){list*rear;if(head==null){
}}main(){
list*head;head=setup(s);display(head);free(s);rear=head;printf(“%c”,rear->a);while(rear->next!=null){
}rear=rear->next;printf(“%c”,rear->a);printf(“没有数据n”);elselist*head=null;list*rear=null;
charc;printf(“请输入c直到$n”);c=getchar();while(c!='$'){
}if(rear!=null)rear->next=null;returnhead;s=malloc(sizeof(list));s->a=c;if(head==null){}elserear->next=s;rear=s;c=getchar();head=s;
}free(head);1.(2)#include#definedatatypechartypedefstructlnklist{datatypea;structlnklist*next;}list;list*s;list*setup(list*s){
list*rear;list*p;datatypemin;if(head==null){list*head=null;list*rear=null;
}voidinsert(list*head,datatypex){
list*p;list*q;list*r;if(head==null)printf(“空表n”);p=head;q=head;r=malloc(sizeof(list));r->a=x;while(p->next!=null){
}while(q->next!=p)q=q->next;r->next=p;q->next=r;if(p->next==null)if(xa){}p=p->next;break;}p=head;
while(p->next!=null){
do{
rear=rear->next;if(min>rear->a){
}min=rear->a;rear->a=p->a;p->a=min;
min=p->a;rear=p;printf(“空表！n”);exit(0);}while(rear->next!=null);p=p->next;}
}datatypex,c;list*head;head=setup(s);paixu(head);printf(“请输入xn”);c=getchar();x=getchar();insert(head,x);display(head);free(s);free(head);rear=head;printf(“%c”,rear->a);while(rear->next!=null){
}rear=rear->next;printf(“%c”,rear->a);printf(“没有数据n”);elsep->next=r;1.(3)#include#definedatatypechartypedefstructlnklist{datatypea;structlnklist*next;}list;list*s;
list*setup(list*s){
}list*nizhi(list*head){
list*h;list*rear;inti=0;charb[100];h=malloc(sizeof(list));h->next=head;rear=head;do{
b[i]=rear->a;rear=rear->next;i++;list*head=null;list*rear=null;
}if(rear!=null)rear->next=null;returnhead;s=malloc(sizeof(list));s->a=c;if(head==null){}elserear->next=s;rear=s;c=getchar();head=s;}while(rear->next!=null);b[i]=rear->a;rear=head;for(;i>=0;i--){
}rear->a=b[i];rear=rear->next;
}list*head;head=setup(s);head=nizhi(head);display(head);free(s);free(head);rear=head;printf(“%c”,rear->a);while(rear->next!=null){
}rear=rear->next;printf(“%c”,rear->a);printf(“没有数据n”);elsereturnhead;2.#include#definedatatypechartypedefstructlnklist{datatypea;structlnklist*next;}list;list*s1;list*s2;list*setup(list*s){
charc;printf(“请输入c直到$n”);c=getchar();while(c!='$')
}voiddein(list*la,list*lb,inti,intlen,intj){
intk;list*rear;list*t;list*h;list*r;list*q;h=null;rear=la;q=la;for(k=1;k!=i;k++){
}while(q->next!=rear){
t=malloc(sizeof(list));t->a=rear->a;if(h==null)h=t;q=q->next;for(k=1;k<=len;k++)rear=rear->next;if(rear->next==null&&k!=i){
}printf(“没找到i的位置n”);exit(0);
rear=head;printf(“%c”,rear->a);while(rear->next!=null){
}printf(“n”);rear=rear->next;printf(“%c”,rear->a);printf(“没有数据n”);else
}q->next=rear;if(r!=null)r->next=null;rear=lb;for(k=1;k!=j;k++){
}q=lb;while(q->next!=rear)q=q->next;r->next=rear;q->next=h;rear=rear->next;if(rear->next==null&&k!=j){
}printf(“没找到j的位置n”);exit(0);elser->next=t;r=t;rear=rear->next;if(rear->next==null&&k}printf(“len太长n”);exit(0);
}}main(){charc;
}list*la;list*lb;inti,len,j;printf(“建立单链表lan”);la=setup(s1);printf(“建立单链表lbn”);lb=setup(s2);printf(“请输入要删的位置in”);scanf(“%d”,&i);printf(“请输入要删减的数据长度lenn”);scanf(“%d”,&len);printf(“请输入要插入的位置jn”);scanf(“%d”,&j);dein(la,lb,i,len,j);printf(“显示lan”);display(la);printf(“显示lbn”);display(lb);free(la);free(lb);c=getchar();
1.（3）
单链表以前没怎么编过，所以现在编有点陌生，要编译好几次才能运行。我觉得还是不能光看书，还要多编几道题比较有手感。
实验3堆栈和队列
（1）掌握应用栈解决问题的方法。（2）掌握利用栈进行表达式求和的算法。
（3）掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。
（1）判断一个算术表达式中开括号和闭括号是否配对。（2）测试“汉诺塔”问题。
（3）假设称正读和反读都相同的字符序列为”回文”，试写一个算法判别读入的一个以’@’为结束符的字符序列是否是“回文”。
#include#includechara[100];intpanduan(char*a){
count1++;for(k=i+1;a[k]!='';k++){if(a[k]==')')if(a[i]=='(')
}printf(“请输入算式n”);gets(a);if(panduan(a)==1){}elseprintf(“算式（）不配对n”);printf(“算式（）配对n”);
break;}if(a[k]=='')return0;}if(a[i]==')')}if(count1!=count2)return0;return1;count2++;1.（2）
#includeinti;voidmove(intn,chara,charc){printf(“第%d步：将%d号盘子%c--->%cn”,i++,n,a,c);}voidhanno(intn,chara,charb,charc){
}hanno(n-1,a,c,b);move(n,a,c);hanno(n-1,b,a,c);move(1,a,c);else
}intn;chara,b,c;printf(“请输入要移动的盘子数n”);scanf(“%d”,&n);a='a';b='b';c='c';hanno(n,a,b,c);1.（3）
#include#includechars[100];inthuiwen(chars[]){
while(1){printf(“请输入字符直到@n”);gets(s);if(huiwen(s))
}printf(“是回文n”);printf(“不是回文n”);elseinti,j=0;charb[100];for(i=0;s[i]!='@';i++);for(i=i-1;i>=0;i--){
}j=0;for(i=0;s[i]!='@';i++){}return1;return0;b[j]=s[i];j++;if(s[i]!=b[j])j++;
}
2.#include#definemaxsize100typedefstructduilie{
}voidsetup(dui*s,intx){
if(x<((s->a[s->head]+s->a[s->rear])/2)){
}else{s->rear=(s->rear++)%maxsize;s->head=(s->head--)%maxsize;s->a[s->head]=x;s->head=maxsize-1;s->rear=maxsize-1;s->a[s->head]=0;s->a[s->rear]=0;
}}s->a[s->rear]=x;voiddisplay(dui*s){
printf(“s队为：”);while(s->head==s->rear){printf(“%-3d”,s->a[s->head]);
}intx;while(1){printf(“请输入x直到0n”);scanf(“%d”,&x);setup(s,x);if(x==0)}if(s->head!=(s->rear+1)%maxsize)printf(“队满n”);display(s);break;}s->head=(s->head++)%maxsize;
实验4串
掌握串的存储及应用。
（1）编写输出字符串s中值等于字符ch的第一个字符的函数，并用主函数测试结果。
（2）编写输出字符串s中值等于字符ch的所有字符的函数，并用主函数测试结果。
解题思路：可以将第一题程序改进成一个子函数，在本题中循环调用。（3）设字符串采用单字符的链式存储结构，编程删除串s从位置i开始长度为k的子串。
假设以链结构表示串，编写算法实现将串s插入到串t中某个字符之后，若串t中不存在这个字符，则将串s联接在串t的末尾。
提示：为提高程序的通用性，插入位置字符应设计为从键盘输入。程序清单：
#include#includevoidfun(chars[],charch){
}printf(“没找到n”);if(ch==s[i]){
}printf(“找到字符%c在位置%dn”,s[i],i+1);exit(0);
}chars[100],ch;printf(“请输入字符串sn”);gets(s);printf(“请输入要查找的字符chn”);scanf(“%c”,&ch);fun(s,ch);1.（2）
#include#includechars[100];voidfun(chars[],charch){inti;if(strcmp(s,“")==0){printf(”字符串s为空n“);exit(0);}for(i=0;s[i]!='';i++){
#include#includetypedefstructchuanlian{charc;structchuanlian*next;}chuan;chuan*s;chuan*setup(chuan*s){
intj;chuan*p;chuan*t;if(chu==null){
}p=chu;for(j=1;jc=ch;if(head==null){}else
voiddisplay(chuan*chu){chuan*p;
inti,k;chuan*head;head=setup(s);printf(”请输入要删除字符的位置in“);scanf(”%d“,&i);p=chu;if(chu==null){
}printf(”%c“,p->c);while(p->next!=null){
}p=p->next;printf(”%c“,p->c);printf(”空串n“);exit(0);{
}t=p->next;for(j=1;j}p->next=t;if(p->next==null&&j}t=t->next;printf(”串长度太小，无法删除%d个元素n“,k);exit(0);if(p->next==null&&j}p=p->next;printf(”无法找到第%d位置n“,i);exit(0);
printf(”请输入要删除字符的个数kn“);scanf(”%d“,&k);delet(head,i,k);display(head);free(head);free(s);}2.#include#includetypedefstructchuanlian{charc;structchuanlian*next;}chuan;chuan*s,*t;chuan*setup(chuan*chu){
chu->c=ch;if(head==null){head=chu;
}}elserear->next=chu;rear=chu;ch=getchar();}if(rear!=null)rear->next=null;returnhead;
voidinsert(chuan*s1,chuan*s2,charx){
chuan*p;chuan*q;p=s1;if(s1==null){
}{
}while(p->next!=null){if(p->c==x)break;printf(”s是空串n“);exit(0);if(s2==null)printf(”t是空串n“);exit(0);
}}p=p->next;if(p->next==null)p->next=s2;else{
}q=s2;while(q->next!=null)q=q->next;q->next=p->next;p->next=s2;voiddisplay(chuan*chu){chuan*p;
}p=chu;if(chu==null){
}p=p->next;printf(”%c“,p->c);printf(”空串n“);exit(0);
charx,c;printf(”建立单链串tn“);t=setup(t);c=getchar();printf(”建立单链串sn“);s=setup(s);c=getchar();printf(”请输入要在什么字符后插入n");x=getchar();
insert(t,s,x);display(t);
数据结构和算法设计与分析
谈到计算机方面的专业课程，我觉得数据结构算是一门必不可少的课了，它是计算机从业和研究人员了解、开发及最大程度的利用计算机硬件的一种工具。数据结构与算法分析是两门紧密联系的课程,算法要靠好的数据结构来实现,二者的关系是密不可分的,谈到算法不得不讲数据结构,谈数据结构也不可避免的要了解算法,好的算法一定有一个好的数据结构，很多算法实际上是对某种数据结构实行的一种变换,研究算法也就是研究在实行变换过程中数据的动态性质。这两门课程分别是我在大二和研一的时候学的，因为它们密切的联系，这里将其放在一起总结如下。
什么是数据结构呢？研究数据的逻辑结构和存储结构（物理结构）以及它们之间的关系，且为该结构定义相应的运算设计相应的算法。这里的数据是指可输入到计算机能被程序处理的符号的集合。其中，数据的逻辑结构是指数据之间逻辑关系的描述，逻辑结构的分类有线性结构、树形结构和图结构。数据的存储结构是指数据在计算机中存储结构，也称为物理结构，它有4类基本的存储映射方法：1.顺序的方法；2.链接的方法；3.索引的方法；4.散列的方法。在程序设计语言中，数据结构直接反映在数据类型上，比如一个整型变量就是一个节点，根据类型给他分配内存单元。抽象数据类型：一组值以及在这些值上定义的操作集合，它是描述数据结构的一种理论工具，其特点是把数据结构作为独立于应用程序的一种抽象代数结构。
线性表结构：由一系列元素组成的有序的序列，除了第一个元素和最后一个元素外，每个元素都只有一个直接前趋和直接后继，元素的个数称为线性表的长度。它的存储方式有顺序存储和链式存储。顺序存储方式它的优点是存储单元是连续的，适合快速访问元素内容，链表的特点是动态申请内存空间，并通过指针来链接结点，按照线性表的前驱关系把一个个结点链接起来，这样可以动态地根据需要分配内存空间，经常用于插入新结点或删除节点的需要，链表还可以根据结点中指针个数分为单链表、双链表、循环链表等。在线性表结构中有两类特别的线性表：栈和队列。栈是一种限制访问端口的线性表，常称为后进先出表。正是这种特殊的性质使得栈的用途非常广泛，比如在计算表达式的值时处理运算符的先后次序，另外一个大的用处就是递归了，hanoi塔就是最典型的用了递归的思想，在算法中，也有很多运用递归思想的例子。队列也属于限制访问点的线性表，它的特点就是加入和删除元素都只能在队列的一端进行，即队列首出，队列尾进，最大的特点是先来先服务，先进先出。因为这个特点，队列常被用作消息缓冲器。
在算法设计中，顺序表主要用于检索，而利用栈中的递归思想在算法中则应用非常广泛，如递归排序，分治算法等。
树结构：是一种非常重要的非线性数据结构，它是由一个根结点和若干叶结点组成的树状结构，除了根结点每个结点只能有一个父节点，可以有若干子结点，若干个树结构还可以构成森林，树的存储结构也分为顺序存储和链式存储，最典型的是左孩子右兄弟法。在树结构中比较重要的算法就是周游（遍历）树，有先根次序、后根次序以及中根次序。树结构中有几类非常重要的特殊树结构，如二叉树，b树，b+树等，其中，二叉树应用最为广泛。
二叉树：是指每个结点最多有两个子结点的树结构，具体细分，根据叶子结点的特性可分为满二叉树、完全二叉树等。二叉树的遍历也分为深度优先和广度优先。另外，二叉树有几条非常重要的性质，这也使得它的应用非常广泛。
在算法设计中，典型的利用树的深度优先遍历的算法是回溯法，而典型的广度优先搜索算法是分枝定界法。
图：是一种较线性表和树更为复杂的数据结构。一般来讲，数据的逻辑结构可表示为结点的有穷集合k和k上的一个关系r,如果对k中结点相对于r的前驱、后继个数加以限制，则可以分别定义线性结构、树形结构和图结构，即：
线性结构：惟一前驱，惟一后继，反映一种线性关系；树形结构：惟一前驱，多个后继，反映一种层次关系；
图结构：不限制前驱的个数，亦不限制后继的个数，反映一种网状关系。
通常用g=(v,e)代表一个图，其中v是顶点集，e是边集。图分为有向图和无向图，图的存储方式有邻接表和邻接矩阵法。和树类似的，图中也需要周游，同样有深度优先搜索和广度优先搜索，而比树的周游要更复杂，也更重要。在这一块中，有两种比较典型的求最短路径和最小支撑树的算法需要注意，它们分别是dijkstra算法和prim算法。另外需要注意的是图的连通性。
在算法设计中，典型的用到图论的算法有贪心算法和动态规划算法。
对于计算机科学来说，算法的概念至关重要。通俗的讲，算法是指解决问题的一种方法或一个过程，或者严格来讲，是由若干条指令组成的有穷序列，且满足以下4条性质；
（1）输入：有零个或多个由外部提供的量作为算法的输入。（2）输出：算法产生至少一个量作为输出。
动态规划算法和贪心算法：与分治算法类似，动态规划的基本思想也是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治算法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。动态规划算法适用于解最优化问题。通常可按以下4个步骤：
（1）找出最优解的性质，并刻画其结构特征。（2）递归的定义最优值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造最优解。
动态规划算法的基本要素是最优子结构性质和子问题重叠性质。
最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
子问题重叠性质。子问题重叠性质是指在用递归演算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
另外一点要素是备忘录方法，它作为动态规划算法的变形，用表格保存已解决问题的答案，在下次需要解此子问题时，只要简单查看子问题的解答，而不必重新计算。与动态规划不同的是备忘录方法的递归是自顶向下的，而动态规划则是自底向上的。
动态规划算法设计策略典型的应用案例有：矩阵连乘、最大字段和、流水作业调度等。有时满足动态规划条件的问题可以有更好的算法，比如贪心算法。贪心算法即总是做出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑，它所做的总是做出的选择只是在某种意义上的局部最优。这种启发式的策略并不能总是奏效，然而对某些特定的问题确能达到预期目的。比如活动安排的例子。
贪心算法的基本要素主要有贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法与动态规划的主要区别，它们的共同点是都要求问题具有最优子结构性质。
贪心算法的典型案列是：活动安排、最优装载问题、最短路径和最优生成树问题。回溯法和分枝定界法：回溯法有“通用的解题法”之称。用它可以系统的搜索一个问题的所有解或任一解。它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。其算法框架包含递归回溯和迭代回溯，两个特别的解空间树为子集树和排列树。典型的回溯法的案例有：批处理作业调度、图的m着色、旅行售货员问题、0-1背包问题等。
分枝定界法类似于回溯法，也是在问题的解空间上搜索问题解的算法。一般情况下，分治定界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间中满足约束条件的所有的解，而分枝定界法的求解目标则是找出满足约束条件的一个解，或是满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。由于求解目标不同，导致分支定界法与回溯法对解空间的搜索方式也不相同。回溯法以深度优先的方式搜索解空间，而分枝定界法则以广度优先或以最小耗费优先的方式搜索解空间。
小结一下，在算法设计这么课中学了这么几大类典型的算法，里面也涉及到具体的应用案例，但我觉得学算法的目的远不是学会这几种固定的特殊问题的解法而已，事实上领会这些巧妙算法背后的思想然后学会迁移到其他新的问题中去才是领会了算法设计的精髓。