数据结构学习心得

数据结构是计算机科学与技术专业的重要基础课程之一，也可以说是我们将来软件能力的基础。通过这门课程的学习，特别是四道上机题的实践，我感觉提高很大。不但对数据结构有了更深刻的理解，甚至自己对世界，生活的认识也发生了巨大的变化。我想这就是银河人的成长吧！呵呵！

我觉得数据结构，不仅仅是对实际世界的简单抽象，它更是对各个事物之间关系的高度抽象和精炼。它将对事物的处理抽象到对某些特定的结构数据的简单操作，使处理事物更加简单和高效。可以说是一种新的、高度抽象的世界观。

我很喜欢思考问题，学习了数据结构，让我又有了一个认识世界的新角度。也让我对计算机科学有了更浓厚的兴趣。提高了自己的编程能力，和软件能力。

感谢老师的悉心教导，在此祝老师新春快乐，工作顺利，身体健康！

姓名：XXX

学号：XXXXXX

院别：XXXX

 

第二篇：数据结构学习与实验

数据结构学习与实验

第1章

(一)学习内容

1．什么是数据结构2．基本概念和术语

3．抽象数据类型的表示于实现4．算法和算法分析(二)自学内容：

1．数据的逻辑结构主要有哪两类？2．算法有哪些特征？

3．算法的时间复杂性可以从哪些角度进行分析（三种）？4．学会以下单词ElementStructureEmptyAdjacent

AbstractOVERFLOWPriorTraverse

StatusINFEASIBLEInsertAppend

InitialAscendingAssignVertex

InitializtionDescendingDestroyalgorithm

绪论

(三)学习目的与要求

1．理解数据、数据元素、数据对象、数据项、数据类型的概念及相互关系；2．理解数据结构的概念，数据结构的表示方法（形式化定义方法）；

3．理解数据的逻辑结构与数据的物理结构的关系，理解抽象数据类型的概念；

数据的逻辑结构和物理结构怎样表示4．了解四种基本的数据结构及其特点

5．理解算法的概念；了解算法分析、时间复杂性、空间复杂性的概念。(四)笔头作业

1．各举一个问题实例说明三种典型数据结构的应用，要求说明实例中的数据元素2．分析以下算法的时空复杂性intmain(){inta[10];inti,j,t;

for(i=0;i<9;i++)scanf("%d",a+i);scanf("%d",&t);for(i=8;i>=0;i--)

if(a[i]<t)break;elsea[i+1]=a[i];a[i+1]=t;

for(i=0;i<10;i++)}

3．书上1.81.101.111.12

4．*设计一个算法，将数组A(0..n-1)中的元素循环右移k位，假设原数组序列为a,a,…,a,a；移动后的序列为a

1

n-2

n-1

n-k

printf("%3d",a[i]);

,a,…,a,a,,…,a

n-k+1

1

。要求只用一个元

n-k-1

素大小的附加存储空间，元素移动或交换次数为O(n)

5．指出下列程序中变量的存储方式

intn=15;

intmian()

{staticinta=5;

int*start;

intb[20],i;

start=(int*)malloc(n*sizeof(int));

for(i=0;i<n;i++)

a++;

for(i=0;i<20;i++)

}

6．写出下列程序的执行结果,并分析原因

voidf1(intx)

{x++;printf(“inf1,x=%d\n”,x);}

voidf2(int&x)

{x++;printf(“inf2,x=%d\n”,x);}

intmain()

{intn=1;

f1(n);

printf(“afterf1,n=%d\n”,n);

n=1;

f2(n);

printf(“afterf2,n=%d\n”,n);

return0;

}

(五)实验练习

1．输入n个整数，输出其中的最大值。n和数组元素的值都从键盘输入。

2．阅读如下程序，总结什么时候使用运算符“．”，什么时候使用运算符“->”structone

{intnum;

charname[20];

};

intmain()

{structonex1,x2,*p;

x1.num=23;strcpy(x1.name,“zhangsan”);

p=&x2;

p->num=x1.num;strcpy(p->name,x1.name);

}

3．sy01.c是学生成绩管理程序。将sy01.c做如下修改：

（1）将结构体类型名STU改为ElemType;

（2）去掉全局变量number的定义

（3）定义结构体类型Example

typedefstructlistprintf(“%d\n”,b[i]);scanf(“%d”,start+i);

{ElemTypehead[20];//存放学生数据的数组，大小可根据需要改变

intnumber;

}Example;

（4）在main函数中定义变量L表示所有的学生数据

intmain(void)

{inthaveread=0;

ExampleL;

...................

}

（5）将以下函数增加形式参数L

voidinput(Example&L)；//从文件中装入学生数据

voidsort(ExampleL)；//根据总成绩排序

voidprint(ExampleL)；//按总成绩从高到低输出学生数据

voidsearch(inthaveread,ExampleL)；//查找学生数据

（6）修改源程序，使之与原来的程序功能相同

（7）程序的扩展名需要修改吗？

5．实现一种排序算法

6．定义集合的抽象数据类型，并实现整数集合和复数集合。集合的运算有：创建一个空集、插入一个元素、删除一个元素、求两个集合的并集、交集。

第2章

(一)课程内容

1．线性表的类型定义

2．线性表的顺序表示和实现

3．线性表的链式表示和实现

4．一元多项式的表示及相加

(二)自学内容

1．将两个有序的数组合并为一个有序的数组（相同的元素只保留一个）

2．将两个有序链表合并为一个有序链表（相同的元素只保留一个）

3．比较线性表的顺序结构与链式结构的特点与优劣

4．在线性表中数据及数据之间的关系是如何表示的？

5．什么是随机存储，什么是顺序存储？

6．建立链表有头插法和尾插法，书上的方法是头插法，尾插法如何实现？

7*．利用单链表结构实现多项式相加算法

8*．O(n),Ω(n)、Θ(n)

(三)学习目的与要求

1．深刻理解线性结构的定义和特点；了解线性表的物理结构

2．熟练掌握顺序表和链表的物理结构及实现基本运算的算法，并进行算法的分析比较；

3．掌握在顺序表和链表上进行算法设计的基本技能；

集合操作，有序表合并

4．链表中设置头结点的作用

(四)笔头作业

1．2.22.62.72.82.112.122.192.212.222.242.41线性表//是否装入数据标志//学生人数

2．设A={a,d,f,c,h,t}，B={c,r,w,g,t,p}，以静态链表为物理结构，画出计算(A-B)∪(B-A)的静态链表

3．实现单链表的所有基本操作（不含已实现的）

4．如果顺序表采用以下的存储方式，其基本操作该如何实现？

#defineMaxlen50

typedefstruct

{ElemTypedata[Maxlen];

intlen;

}SqList3;

(五)实验练习

1．采用如下顺序表结构：

#defineLIST_INIT_SIZE

#defineLISTINCREMENT

typedef

ElemType

int

int

}SqList;

2．实现顺序表的基本操作

（1）构造一个空的线性表LStatusInitList_Sq(SqList

（2）在顺序线性表L中第i个位置之前插入新的元素e

StatusListInsert_Sq(SqList&L,inti,ElemTypee)

（3）在顺序线性表L中删除第i个元素,并用e返回其值

StatusListDelete_Sq(SqList&L,inti,ElemType&e)

（4）在顺序线性表L中查找第1个值与e满足compare()的元素的位序

intLocateElem_Sq(SqListL,ElemTypee,Status*compare)(ElemType,ElemType))

（5）已知顺序线性表La和Lb的元素按值非递减排列，合并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列

voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc)

3．利用以上基本操作实现学生运动会成绩统计和查询系统

（1）有N个学校参加运动会，比赛分为男子项目和女子项目，比赛取前5名，得分依次为7，5，3，2，1；

（2）比赛结果放在M个文件中（一个项目一个文件，取前八名，包括未取得成绩的数据）

组别

项目

名次

第一名

第二名

第三名

第四名

第五名

第六名米学校南城中学实验中学二中二中立志中学雷人学校&L)struct{*elem;length;∥存储空间基址∥当前长度100∥线性表存储空间的初始分配10∥线性表存储空间的分配增量listsize;∥当前分配的存储容量

第七名

第八名

（3）M、N从键盘输入

（4）查询某个同学的名次实验中学翱翔中学

（5）统计每个学校的男子总分、女子总分和团体总分

4．采用带头结点的单链表结构

typedefstruct

{ElemType

structLNodeLNodedata;*next;

}LNode,*LinkList;

5．实现单链表的基本操作

（1）在带头结点的单线性链表L中第i个位置之前插入元素e

StatusListInsert_L(LinkList&L,inti,ElemTypee)

（2）在带头结点的单链线性表L中,删除值为e的结点

StatusListDelete_L(LinkList&L,ElemTypee)

（3）建立有n个结点的线性链表voidCreateList_L(LinkList&L,intn)

（4）查询值为e的结点，返回该结点指针

LinkListLocate(LinkListL,ElemTypee)

6．用上述基本操作实现图书管理系统

7、生死者游戏。有n个旅客同乘一条船，因为船发生故障，只能留下一半旅客。大家议定如下办法：n个人围成一圈，由第一个人起，依次报数，报到m的人必须被扔进大海。如此循环。问哪些旅客仍留在船上？

第3章

(一)学习内容

1．栈

2．栈的应用

3．栈与递归的实现

4．队列

(二)自学内容

1．实现链栈的所有基本操作

2．十进制数与其他进制数之间的转换

3．利用堆栈计算后缀表达式的值

4．链队列的基本操作

(三)学习目的与要求

1．栈的特点，顺序栈和链栈的组织方式和基本运算的实现和简单算法；

2．队列的特点，循环队列和链队列的存储结构和基本运算的实现和简单算法设计；

3．栈和队列上溢、下溢的条件（空、满）

4．利用栈和队列的基本运算实现简单应用

(四)笔头作业

1．3.3

3.283.43.303.153.313.173.19*3.21栈和队列

2．*n个自然数的入栈顺序为1,2,....n,输入一个出栈序列,判断其是否是一个合法的

出栈序列

3．*n个自然数的入栈顺序为1,2,....n,输出所有的出栈序列.

4．利用栈操作实现单链表的逆置

5．实现队列逆置

(五)实验练习（栈和队列的物理结构自行选择）

1．实现栈的基本操作：

（1）栈的初始化InitStack(&S)

（2）入栈Push(&S,e)

（3）出栈Pop(&S,&e)

（4）栈空判断StackEmpty(S)

2．实现队列的基本操作：

（1）队列的初始化InitQueue(&Q)

（2）入队EnQueue(&Q,e)

（3）出队DeQueue(&Q,&e)

（4）队空判断QueueEmpty(Q)

3*．停车场管理（P96）

输入要求：

停车场容量n

车辆进入和离开情况

输出要求：

输出离开车辆收费情况（一小时5元，不足半小时不收，超过半小时按1小时收取）输出停车场的停车状况和便道上车的等待情况

4．迷宫问题

第4章

(一)学习内容

1．串类型的定义

2．串的表示和实现

3．串的模式匹配算法

(二)自学内容：

1．堆存储方式下串操作的实现

2．串操作应用举例

(三)学习目的与要求

1．理解串的七种操作的定义，了解串的最小操作子集

2．掌握串的定长顺序结构和堆存储结构上实现串的各种操作的方法。

3．掌握模式匹配算法的思想，了解算法实现过程

(四)笔头作业

4.34.4

(五)实验练习

实现模式匹配算法4.54.64.7*4.8*4.124.214.24串

第5章

(一)学习内容数组与广义表

1．数组的定义

2．数组的顺序表示和实现

3．矩阵的压缩存储

4．广义表

(二)自学内容

1．对称矩阵的压缩存储

2．广义表基本操作的应用

(三)学习目的与要求

1．了解数组的存储方法，掌握数组在以行序为主序时的数组元素地址计算方法；

2．掌握特殊矩阵压缩存储的原理；

3．掌握对稀疏矩阵的各种操作；

4．了解广义表的结构特点和存储方法

(四)笔头作业

5.1

5.12

(五)实验练习

稀疏矩阵采用三元组结构存储

1．稀疏矩阵的转置

2．稀疏矩阵的加法

3．*稀疏矩阵的乘法

第6章

(一)学习内容

1．树的定义

2．二叉树

3．遍历二叉树和线索二叉树

4．树和森林

5．赫夫曼树及其应用

(二)自学内容

1．树中基本术语：叶子、非终端节点、内部节点、双亲、兄弟、度、高度、层次、森林

2．二叉树的五种基本形态

3．二叉树的第i层上最多结点个数，深度为k的二叉树最多结点个数

4．二叉树的术语：满二叉树、完全二叉树

5．树与森林的遍历方法

(三)学习目的与要求

1．理解树的基本概念和术语；

2．掌握二叉树的定义和存储结构，二叉树的性质；

4．掌握完全二叉树的特点；

5．熟悉二叉树的遍历次序并熟练掌握遍历算法（含中序非递归）；

6．掌握二叉树的建立方法

7．掌握线索二叉树的特点及用途

8．了解树和森林的定义、树的存储结构并掌握树、森林与二叉树之间的相互转换方法；

9．了解哈夫曼编码，掌握构造哈夫曼树的方法树5.25.25*5.55.265.65.105.11

(四)笔头作业

1．6.1

6.13

6.24

6.426.26.146.266.43*6.46.196.27*6.456.56.206.286.476.66.216.296.56*6.86.23*6.33

2.用先序序列ABCΦΦDEΦGΦΦFΦΦΦ能够构造一颗二叉树，书否用类似的中序、后序序列也能构造二叉树？

3．证明二叉树中叶子结点个数与度为2的结点个数之间的关系

(五)实验练习

1．建立一棵二叉树

2．利用中序/先序/后序遍历二叉树，判断X是否是Y的祖先

3．层序遍历二叉树

4．哈夫曼编码（P149）

5．*译码（P149）

第7章

(一)学习内容

1．图的定义。

2．图的存储结构

3．图的遍历

4．图的连通性问题

5．有向无环图及其应用

6．最短路径

(二)自学内容

1．有无空图？

2．有向图/无向图与联通图/强联通图、完全图/有向完全图之间的关系

3*．克鲁斯卡尔算法

(三)学习目的与要求

1．理解图的概念并熟悉有关术语；

2．熟练掌握图的邻接矩阵表示法和邻接表表示法；

3．掌握连通图遍历的基本思想和算法；

4．掌握最小生成树的有关概念和Prim算法；

5．掌握拓扑排序的概念、步骤和应用情况

6．理解关键路径和最短路径的算法。

(四)笔头作业

7.1

7.11

(五)实验练习

1．建立一个图（用邻接表或邻接矩阵结构）

2．输出有向图的拓扑排序序列

3．实现无向图的深度/广度优先遍历

4．实现无向图的最小生成树（用Prim算法）

第9章查找表7.27.147.37.47.157.57.227.77.97.10图

(一)学习内容

1．静态查找表

2．动态查找表

3．哈希表

(二)自学内容

1．顺序查找算法

2．B—树的插入、删除方法

(三)学习目的与要求

1．理解查找表的定义、分类和特点；

2．掌握顺序查找和二分查找的思想和算法，掌握平均查找长度的概念；

3．掌握二叉排序树的概念和插入、删除、查找算法的实现方法；

4．掌握平衡的二叉排序树的概念和平衡处理方法；

5．了解多路查找树的定义和插入、删除、查找方法

6．掌握散列表、散列函数的构造方法、以及处理冲突的方法；

7．掌握散列存储和散列查找的基本思想及有关算法；

(四)笔头作业

9.19.39.99.109.119.139.14

*9.219.25*9.319.19（关键字序列改为67，01，13，30，46，53，41，22）

(五)实验练习

1．哈希函数设哈希表长为18,哈希函数为:H(k)=kMOD17建立对应的哈希表。,采用开放地址法中的二次探测再散列解决冲突,并查找值为x的元素位置

第10章

(一)学习内容

1．概述

2．插入排序

3．快速排序

4．选择排序

5．归并排序

6．基数排序

(二)自学内容

1．简单选择排序

2．冒泡排序

(三)学习目的与要求

1．深刻理解各类内部排序方法的指导思想和特点；

2．熟悉各种内部排序算法并理解其基本思想；

3．了解各种内部排序算法的优缺点、时空性能和适用场合。

(四)笔头作业

10.1

(五)实验练习

1．实现快速排序

2．双向冒泡排序（奇数趟从左到右，偶数趟从右到左）10.410.12排序