第一篇：数据结构学习心得
数据结构学习心得
北京大学信息科学技术学院
04级计算机2班
00448245 柳明海
1． 前言
首先感谢张老师给我这样一个机会，来和大家分享学习数据结构的经验。2． 学习方法。
因为要准备这个话题，所以我认真的思考了我的学习方法，但是我觉得基本上我就是上课前看看书、上课时认真听课、下课以后复习复习、当然还有做作业时很认真的去做。根本谈不上什么好方法，不过我还是有一些话要送给大家。我能行！
个人觉得这句话非常重要，不知道大家是怎样看待数据结构这门课的，有多少人觉得数据结构很难呢？我知道还是有一些同学这样觉得的，有时候我跟我的朋友讲要怎样学，讲了一大堆以后，他就向我抱怨：我以前c＋＋都没有学好，数据结构更学不好了，这哪跟哪的话啊，数据结构与c＋＋没有什么关系，我想假如抱有这样的心态，自己就不相信自己，那是不可能学好的，然后那些觉得数据结构很难的同学，我想他们应该会很看重数据结构的吧，然后就一天到晚捧着一本数据结构，这样不会觉得很累吗？而且因为觉得很难，就容易不相信自己，学的效率也不会很好，个人认为数据结构很好学，很容易学，或许这有点妄自菲薄吧，但是因为我觉得很容易，当然就会觉得自己没问题，学得很轻松，效果也还可以。大家都是从高考走过来的，应该知道心态的重要性吧，两种不同的心态，完全就是两种不同的效果。
学了这么久数据结构了，我们到底在学些什么呢？ 不知道大家有没有想过，那现在我们现在来归纳一下我们学习的内容吧，其实学到现在我们也就学了几种普通的数据结构，象二叉树，树，图，还有排序的问题，前面的线性表和字符串也就是一些概念，当然还有一个很重要的KMP算法，然后在每种数据结构中我们也就是学到了若干处理的算法，我想真正数起来也就是几十个算法吧。学习数据结构也就是要掌握这几十种算法，多简单。至于如何掌握每个算法呢，我想就是多看看书，重要的是能够理解。
我能独自完成作业！
这里我的定义和张老师的不同，张老师是鼓励大家讨论的，不过我发现还是有一些同学就是先问好别人算法，然后再自己写，虽然这个不算抄袭作业，但自己基本上没有一个思考问题的过程，虽然要理解算法也会要思考很多，但是因为没有自己独立的思考过程，要自己写程序、写算法的时候根本写不出来，所以我想如果真的想学好数据结构的话，最好是能够自己思考问题，不要刚想了一会就觉得做不出来，然后就去问其他人。其实张老师给我们的作业还是基于我们的水平的，我绝对相信我们自己能够独自想出算法，虽有可能会比较长时间吧，但是这样肯定会比问其他人学到更多的东西。当然我并不是说不要问同学，有时候就是脑筋转不过来，一问别人就懂了，当然问了别人不能只是我知道了这个算法，还应该去想如何思考才能得到这个算法，这样水平会提高很多。多实验！这个就没有太多理由了，我一直觉得编程是一门熟练科学，多编程，水平肯定会提高，最重要的是能够养成一种感觉，就是对程序对算法的敏感，为什么那些牛人看一个算法一下子就看懂了？而自己要看很久才能弄懂，而且弄懂了过了一阵子又忘记了？其实这个是因为牛人们以前看的程序很多，编得也很多，所以他们有了那种感觉，所以我觉得大家应该多看程序，多写程序，培养自己的感觉。3． 复习和考试的技巧
我想大家应该都有这样的感觉，就是觉得自己什么都掌握了，但是在考试的时候就是会犯晕，有时候一出考场就知道错在哪个了，然后考完以后一对答案，发现其实考得很简单，应该都是自己会做的，这个就是与自己的复习和考试的技巧有关系了。
首先就是复习，前面已经说过其实我们学的算法也就是几十个，那么我们的任务也就是理解这几十个算法，复习也就是要加深你的理解。如何理解算法，然后理解到什么程度呢？ 是能默出整个算法吗？其实不是这样的，数据结构的考试有它的特点，考过期中考试了，大家应该都发现数据结构其实不要求你把整个算法背出来，它注重考察你的理解，那么怎么考察呢？其实也就是两种方式吧，一种就是用实例，就是给你一个例子，要你用某个算法运行出结果，我想这个期末考试的时候仍然会有很多这样的题目，比如排序那块就很好出这样的题目，要复习这种题目我觉得很简单，就是每个算法都自己用例子去实践一下，以不变应万变，我期中复习的时候就是这样去做的，而且考试之前我就觉得那个并查集的题目就很有可能会考，于是就自己出了几个例子，做了一下。另外一种考察方式就是算法填空和算法改错，可能有一些同学觉得这种题目很难，其实我们首先可以确定这两种题目肯定是与书上算法有关系的，只要理解了书上的算法就可以了，有人觉得看完书以后什么都懂了，而且要默也默得出来，其实不是这样的，算法改错和填空主要是考察的细微处，虽然你觉得你默得出来，那是能够默出算法的主体部分，很多细微的地方你就会很容易忽略。我想大家考过期中考以后应该都有这种感觉吧？那要怎样解决这种问题呢？ 我觉得有两种方法，一种就是自己去编程实现，这种方法比较有意义，还能够提高编程水平，另外一种就是用实例分析算法的每句话，我认为这种方法是最有效的。
然后还有一种题目，就是最后的写算法的题目，我觉得这种题目还是很好解决的，只要是能够自己做出作业的，基本上都会很容易做出来，这也是为什么我前面觉得平时做作业应该自己独立思考的原因，同时做这种题目千万要小心，尤其是题目简单的时候，那肯定会有一些小地方要考虑清楚，一不小心就会被扣掉很多分，这样很不值。
我觉得考试的时候没有太多要讲的，只要复习好了，考试的时候细心一点就可以了，然后就是做一个题目开始就要尽量保证正确，如果觉得留在那里等后面做完了再来检查，这样错误还是很有可能检查不出来，我期中考试的时候就基本上没有检查，因为我做每个题目都是确保正确，用的时间也挺多的，然后也觉得没有检查的必要了。4． 结语
谢谢大家，祝大家期末考出理想的成绩！
2005年11月22日于北京大学
第二篇：数据结构参考材料
数据结构参考题目
一、选择
1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）
A.栈 B.队列 C.树 D.图 2.下面程序段的时间复杂度为（）for(i=0;i
A.串的长度相等 B.含有相同的字符集
C.都是非空串 D.串的长度相等且对应的字符相同 5．若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（）
A.SXSSXXXX B.SXXSXSSX C.SXSXXSSX D.SSSXXSXX 6.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）A.0 B.1 C.48 D.49 7.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为
（35，51，24，13，68，56，42，77，93）
（35，24，13，51，56，42，68，77，93）所采用的排序方法是（）
A.插入排序 B.冒泡排序 C.快速排序 D.归并排序
8.已知散列表的存储空间为T[0..16]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（）
A.T[2] B.T[4] C.T[8] D.T[10] 9.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),(a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（）A.head(tail(head(L)))B.head(head(head(L)))C.tail(head(tail(L)))D.head(head(tail(L)))10.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout，则所有顶点的入度之和为（）
A.Dout B.Dout-1 C.Dout+1 D.n 11．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构
12．栈的插入和删除操作在()进行。
A．栈顶 B.栈底 C.任意位置 D指定位置 13．由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A.24 B.71 C.48 D.53 14．一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是()A.2 3 1 B.3 2 1 C.3 1 2 D.1 2 3 15．关于栈和队列的说法中正确的是（）
A．栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构 16．关于存储相同数据元素的说法中正确的是（）A．顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间
C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间
17．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）A.q→next=s；p→next=s； B.q→next=s；s→next=p； C.q→next=s；q→next=p； D.q→next=s；s→next=q；
18．设一组记录的关键字key值为{62，50，14，27，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）A.1 B.2 C.3 D.4 19．执行下面程序段时，S语句被执行的次数为：（）for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)S;A.n*n B.n*n/2 C.n(n+1)D.n(n+1)/2 20．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（）A．O(n)B.O(1)C.O(log2n)D.O(n2)21．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）
A.a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b 22．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串 B.空串是只含有空格字符的串
C.空串是含有零个字符或含有空格字符的串
D.串是含有一个或多个字符的有穷序列
23．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）
A．front==rear
B.(front+1)%m==rear
C.rear+1==front
D.(rear+1)%m==front 24．设有二维数组
1A［n］［n］表示如下：23456，则A［i］［i］（0≤i≤n-1）的D.i2/2 值为（）
A．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 25．高度为h的完全二叉树中，结点数最多为（）
hA．2h-1 B.2h+1 C.2-1 D.2h 26．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）
A.mn B.mn-1 C.n(m-1)D.m(n-1)27．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A.n B.n-1 C.n+1 D.2(n-1)28．关于无向图的邻接矩阵的说法中正确的是（）A.矩阵中非全零元素的行数等于图中的顶点数
B.第i行上与第i列上非零元素总和等于顶点Vi的度数 C.矩阵中的非零元素个数等于图的边数
D.第i行上非零元素个数和第i列上非零元素个数一定相等
29．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（）A.1 B.2 C.3 D.4 30．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（）
A.36，44，49，55，81，88 B.44，36，49，55，81，88 C.44，36，49，81，55，88 D.44，36，49，55，88，81
二、填空题
1.数据是计算机加工处理的对象（）。2.数据结构的概念包括数据的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面()。
3.线性表是由n≥0个相同类型组成的有限序列（）。4.栈是一种后进先出的线性表（）。
5.从循环链表的某一结点出发，只能找到它的后继结点，不能找到它的前驱结点（）。6.单链表设置头结点的目的是为了简化运算（）。7.树的最大特点是一对多的层次结构（）。8.组成数据的基本单位称为数据元素（）。
9.从非循环链表的某一结点出发，既能找到它的后继结点，又能找到它的前驱结点（）。
10.单链表结点的指针域是用来存放其直接后继结点的首地址的（）
11.数据的存储结构是数据的逻辑结构的存储映象（）。
12.用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系（）。
13.在非线性结构中，至少存在一个元素不止一个直接前驱或不止一个直接后驱（）。14.树的最大特点是一对多的层次结构（）。15.队列的特点是先进先出（）。
16.由后序遍历序列和中序遍历序列能唯一确定一颗二叉树（）。17.数据的存储结构独立于计算机（）。18.线性表简称为”顺序表”。（）
19.对数据的任何运算都不能改变数据原有的结构特性（）。20.从循环单链表的任一结点出发，可以找到表中的所有结点（）。21.栈是一种先进先出的线性表（）。22.链表的主要缺点是不能随机访问（）。23.二叉树是树的特殊形式（）。24.冒泡排序法是稳定的排序（）。25.算法是对解题方法和步骤的描述（）。26.算法可以用任意的符号来描述（）。
27.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型（）。
28.线性表的顺序存储方式是按逻辑次序将元素存放在一片地址连续的空间中（）。29.栈是一种先进后出的线性表（）。
30.将插入和删除限定在表的同一端进行的线性表是队列（）。
三、画图题
1.请根据下列二元组画出相应的数据结构
K={15,11,20,8,14,13 } R={<15,11>,<15,20>,<11,8>,<11,14>,<14,13>} 2.请根据下列二元组画出相应的数据结构
K={A,B,C,D,E,F,G,H,I,J} R={
K={1,2,3,4,5} R={<1,2>,<1,3>,<2,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>} 5．请根据下列二元组画出相应的数据结构 K={0,1,2,3,4,5,6,7} R={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6),(3,7),(4,7),(5,6)} 6．请根据下列二元组画出相应的数据结构
K={1,2,3,4,5,6,7} R={(1,2),(1,3),（2,3），(2,4),(2,5),(3,7),(4,6),(5,6)，（6,7）}
四、运算题
1．已知一个图的顶点集V和边集H分别为：
V＝{0，1，2，3，4，5，6，7}
E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照克鲁斯卡尔算法得到最小生成树，拭写出在最小生成树中依次得到的各条边。______，______，______，______，______，______，______。
2.一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。
平均查找长度：（写出计算过程）
3．已知一个图的顶点集V和边集H分别为：
V＝{0，1，2，3，4，5，6，7}
E＝{（0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20}；
按照普里姆算法得到最小生成树，试写出在最小生成树中依次得到的各条边。（从顶点2出发）
____
__，___
_，___
___，__
____，___ ___，__ ____，___ ___。4.写出下图所示的二叉树的前中后序遍历结果：
前序： 中序： 后序：
5.设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉排序树。
五、编程题
1.请编写一个算法，实现十进制整数与二进制数的转换。Void shi_to_er(unsigned x){ 2.写出二分法查找的算法：
Int search_bin(Keytype k,sstable st){ 3.请编写一个算法，实现单链表的就地逆置（单链表不带头结点）。LINKLIST *INVERTLINK(LINKLIST *H){
第三篇：2012数据结构课程设计
数 据 结 构
课程设计报告
题 目： 一元多项式计算 专 业： 信息管理与信息系统 班 级： 2012级普本班 学 号： 201201011367 姓 名： 左帅帅 指导老师： 郝慎学 时 间：
一、课程设计题目分析
本课程设计要求利用C语言或C++编写，本程序实现了一元多项式的加法、减法、乘法、除法运算等功能。
二、设计思路
本程序采用C语言来完成课程设计。
1、首先，利用顺序存储结构来构造两个存储多项式A(x)和 B(x)的结构。
2、然后把输入，加，减，乘，除运算分成五个主要的模块：实现多项式输入模块、实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块。
3、然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能，尽量减少程序运行时错误的出现。
4、最后编写main()主函数以实现对多项式输入输出以及加、减、乘、除，调试程序并将不足的地方加以修改。
三、设计算法分析
1、相关函数说明：
(1)定义数据结构类型为线性表的链式存储结构类型变量
typedef struct Polynomial{}
(2)其他功能函数
插入函数void Insert(Polyn p,Polyn h)
比较函数int compare(Polyn a,Polyn b)
建立一元多项式函数Polyn Create(Polyn head,int m)
求解并建立多项式a+b，Polyn Add(Polyn pa,Polyn pb)
求解并建立多项式a-b，Polyn Subtract(Polyn pa,Polyn pb)2
求解并建立多项式a*b，Polyn Multiply(Polyn pa,Polyn pb)
求解并建立多项式a/b，void Device(Polyn pa,Polyn pb)
输出函数输出多项式，void Print(Polyn P)
销毁多项式函数释放内存，void Destroy(Polyn p)
主函数，void main（）
2、主程序的流程基函数调用说明(1)typedef struct Polynomial {
float coef;
int expn;
struct Polynomial *next;} *Polyn,Polynomial;
在这个结构体变量中coef表示每一项前的系数，expn表示每一项的指数，polyn为结点指针类型，属于抽象数据类型通常由用户自行定义，Polynomial表示的是结构体中的数据对象名。
(2)当用户输入两个一元多项式的系数和指数后，建立链表，存储这两个多项式，主要说明如下：
Polyn CreatePolyn(Polyn head,int m)建立一个头指针为head、项数为m的一元多项式
p=head=(Polyn)malloc(sizeof(struct Polynomial));为输入的多项式申请足够的存储空间
p=(Polyn)malloc(sizeof(struct Polynomial));建立新结点以接收数据
Insert(p,head);调用Insert函数插入结点
这就建立一元多项式的关键步骤
(3)由于多项式的系数和指数都是随即输入的，所以根据要求需要对多项式按指数进行降幂排序。在这个程序模块中，使用链表，根据对指数大小的比较，对各种情况进行处理，此处由于反复使用指针对各个结点进行定位，找到合适的位置再利用void Insert(Polyn p,Polyn h)进行插入操作。(4)加、减、乘、除、的算法实现：
在该程序中，最关键的一步是实现四则运算和输出，由于加减算法原则是一样，减法可通过系数为负的加法实现；对于乘除算法的大致流程都是：首先建立多项式a*b，a/b，然后使用链表存储所求出的乘积，商和余数。这就实现了多项式计算模块的主要功能。
(5)另一个子函数是输出函数 PrintPolyn（）；
输出最终的结果，算法是将最后计算合并的链表逐个结点依次输出，便得到整链表，也就是最后的计算式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理。
四、程序新点
通过多次写程序，发现在程序在控制台运行时总是黑色的，本次写程序就想着改变一下，于是经过查资料利用system(“Color E0”);可以函数解决，这里“E0，”E是控制台背景颜色，0是控制台输出字体颜色。
五、设计中遇到的问题及解决办法
首先是，由于此次课程设计里使用指针使用比较多，自己在指针多的时候易脑子混乱出错，对于此问题我是采取比较笨的办法在稿纸上写明白后开始进行 4
代码编写。
其次是，在写除法模块时比较复杂，自己通过查资料最后成功写出除法模块功能。
最后是，前期分析不足开始急于写代码，中途出现各种问题，算是给自己以后设计时的一个经验吧。
六、测试（程序截图）
1.数据输入及主菜单
2.加法和减法模块
3.乘法和除法模块
七、总结
通过本次应用C语言设计一元多项式基本计算程序，使我更加巩固了C语言程序设计的知识，以前对指针这一点使用是比较模糊，现在通过此次课程设计对指针理解的比较深刻了。而且对于数据结构的相关算法和函数的调用方面知识的加深。本次的课程设计，一方面提高了自己独立思考处理问题的能力；另一方面使自己再设计开发程序方面有了一定的小经验和想法，对自己以后学习其他语言程序设计奠定了一定的基础。
八、指导老师评语及成绩
附录：（课程设计代码）
#include
float coef;6
int expn;
struct Polynomial *next;} *Polyn,Polynomial;
//Polyn为结点指针类型 void Insert(Polyn p,Polyn h){
if(p->coef==0)free(p);
//系数为0的话释放结点
else
{
Polyn q1,q2;
q1=h;q2=h->next;
while(q2&&p->expn
{
q1=q2;q2=q2->next;}
if(q2&&p->expn==q2->expn)//将指数相同相合并 {
q2->coef+=p->coef;
free(p);
if(!q2->coef)//系数为0的话释放结点
{ q1->next=q2->next;free(q2);}
}
else { p->next=q2;q1->next=p;
}//指数为新时将结点插入
} 7
} //建立一个头指针为head、项数为m的一元多项式 Polyn Create(Polyn head,int m){
int i;
Polyn p;
p=head=(Polyn)malloc(sizeof(struct Polynomial));
head->next=NULL;
for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新结点以接收数据 printf(“请输入第%d项的系数与指数:”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //调用Insert函数插入结点 } return head;} //销毁多项式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指针后移 q2=q2->next; } } //输出多项式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//项数计数器 if(!q)//若多项式为空，输出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项 9 if(q->coef!=1&&q->coef!=-1)//系数非1或-1的普通情况 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多项式已空，但b多项式非空 else return 1;//b多项式已空，但a多项式非空 } //求解并建立多项式a+b，返回其头指针 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//当相加系数为0时，释放该结点 } return headc;} //求解并建立多项式a-b，返回其头指针 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//将pb的系数取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢复pb的系数 p->coef*=-1;13 return pd;} //求解并建立多项式a*b，返回其头指针 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点 hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//调用Insert函数以合并指数相同的项 } } return hf;} //求解并建立多项式a/b，返回其头指针 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点,存储商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点，存储余数 pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余数是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定义各式的头指针，pa与pb在使用前付初值NULL printf(“请输入A(x)的项数:”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多项式A printf(“n”);printf(“请输入B(x)的项数:”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多项式B printf(“n”);printf(“**********************************************n”);printf(“* 多项式操作菜单 printf(”**********************************************n“);printf(”tt 1.输出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.减法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”执行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多项式A(x):“);Print(pa);*n”); printf(“多项式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多项式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多项式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多项式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 数据结构课程设计 1.赫夫曼编码器 设计一个利用赫夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。要求： 1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2)初始化：键盘输入字符集大小26、26个字符和26个权值（统计一篇英文文章中26个字母），建立哈夫曼树； 3)编码：利用建好的哈夫曼树生成哈夫曼编码； 4)输出编码（首先实现屏幕输出，然后实现文件输出）； 5)界面优化设计。 代码如下： #include typedef struct HTNode //结构体 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把权值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼树，进行编码 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n请输入权值和字符(用空格隔开): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“输入成功！”);} void Coding_H(int n,HTNode *HT) //对结点进行译码 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]=' '; printf(“************************n”);printf(“Char Codingn”); for(k=1;k<=n;k++) { sp=n-1;p=k;fp=HT[k].Parent; for(;fp!=0;p=fp,fp=HT[fp].Parent) if(HT[fp].Lchild==p) cd[--sp]='0'; else cd[--sp]='1'; HC[k]=(char *)malloc((n-sp)*sizeof(char)); strcpy(HC[k],&cd[sp]); printf(“%c %sn”,HT[k].ch,HC[k]); } printf(“************************n”);free(cd);} void Read(int n,HTNode *HT) //从文件中读出数据 { int i;FILE * fp;if((fp=fopen(“data.txt”,“rb”))==NULL){ printf(“cannot open filen”); exit(0);} for(i=0;i fread(&HT[i].Weight,sizeof(struct HTNode),1,fp);// printf(“%d n”,HT[i].Weight); } Coding_H(n,HT); fclose(fp);} void Print_H(int m,HTNode *HT) //输出赫夫曼造树过程 { int k;printf(“************************n”);printf(“Num Weight Par LCh RCh n”);for(k=1;k<=m;k++){ printf(“%d ”,k); printf(“ %d”,HT[k].Weight); printf(“ %d”,HT[k].Parent); printf(“ %d”,HT[k].Lchild); printf(“ %dn”,HT[k].Rchild); } printf(“************************n”);} void Decode(int m,HTNode *HT) //对输入的电文进行译码 { int i,j=0;char a[10];char endflag='2';i=m;printf(“输入发送的编码，以‘2’结束:”);scanf(“%s”,&a);printf(“译码后的字符：”);while(a[j]!='2'){ if(a[j]=='0') i=HT[i].Lchild; else i=HT[i].Rchild; if(HT[i].Lchild==0) //HT[i]是叶结点 { printf(“%c”,HT[i].ch); i=m; //回到根结点 } j++;} printf(“n”);if(HT[i].Lchild!=0&&a[j]!='2') printf(“ERROR”);} int main() //主函数 { int n,m,c;HTNode HT[N];do { system(“color 2f”); //运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 赫夫曼编译码系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入权值、字母nttt2.把数据写入文件nttt3.输出赫夫曼编码表nttt”); printf(“4.输出赫夫曼译码表nttt5.输入编码并译码.nttt6.从文件中读出数据nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);printf(“输入多少结点:”); scanf(“%d”,&n);m=2*n-1;Create_H(n,m,HT);break; case 2:system(“cls”);Save(n,HT);break; case 3:system(“cls”);Print_H(m,HT);break; case 4:system(“cls”);Coding_H(n,HT);break; case 5:system(“cls”);Decode(m,HT);break; case 6:system(“cls”);Read(n,HT);break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 2.学生成绩管理（链表实现）要求： 实现如下功能：增加、查找、删除、输出、退出。 代码如下： #include //定义成绩信息结构体 { char Number[20];char Name[20];char Chinese[20];char English[20];char Math[20];}score;typedef struct node_score //定义成绩信息链表结点，包括数据域和指针域 { score data;struct node_score *next;}node_score,*p_node_score;p_node_score headScore;//定义链表的头指针为全局变量 void PrintScore(score s)//输出信息函数 { printf(“ %10s”,s.Number);printf(“ | %-6s”,s.Name);printf(“ | %-3s”,s.Chinese);printf(“ | %-3s”,s.English); printf(“ | %-3sn”,s.Math);} void View()//输出函数 { p_node_score pNodeScore; pNodeScore=headScore;printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”);while(pNodeScore!= NULL){ PrintScore(pNodeScore->data);//输出学生信息和成绩信息 pNodeScore=pNodeScore->next;} } void Add(){ p_node_score pNodeScore;// 定义一个节点 pNodeScore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间 printf(“请输入学号：”);scanf(“%s”,pNodeScore->data.Number);printf(“请输入姓名：”);scanf(“%s”,pNodeScore->data.Name);printf(“请输入语文成绩：”);scanf(“%s”,pNodeScore->data.Chinese);printf(“请输入英语成绩：”);scanf(“%s”,pNodeScore->data.English);printf(“请输入高数成绩：”);scanf(“%s”,pNodeScore->data.Math);if(headScore==NULL){ //如果头结点为空 headScore=pNodeScore; pNodeScore->next=NULL;} else { //如果头结点不为空 pNodeScore->next=headScore; headScore=pNodeScore;//将头结点新结点 } } void Input(){ int n,i;printf(“输入几个学生的数据：”);scanf(“%d”,&n);for(i=0;i Add();printf(“输入成功！”);} int Delete(){ p_node_score pNodeScore,p1;//p1为pNodeScore的前驱 p1=headScore;if(p1==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char DeleteNumber[20]; printf(“请数入要删除的学生学号:”);scanf(“%s”,DeleteNumber);if(strcmp(p1->data.Number,DeleteNumber)==0) { //如果要删除的结点在第一个 headScore=p1->next; pNodeScore=p1; printf(“学号为%s的学生信息已经删除！n”,DeleteNumber); return 0;} else { pNodeScore=p1->next; while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,DeleteNumber)==0) { p1->next=pNodeScore->next; printf(“学号为%s的学生信息已经删除！n”,DeleteNumber); return 0; } else { //否则，结点向下一个，p1仍为pNodeScore的前驱 p1=pNodeScore; pNodeScore=pNodeScore->next; } } } printf(“没有此学号的学生！”);} int Change(){ p_node_score pNodeScore; pNodeScore=headScore;if(pNodeScore==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char EditNumber[20];printf(“请输入你要修改的学生学号：”);scanf(“%s”,EditNumber);while(pNodeScore!=NULL){ if(strcmp(pNodeScore->data.Number,EditNumber)==0) { //用strcmp比较两字符串是否相等，相等则返回0 printf(“原来的学生成绩信息如下：n”);//输出原来的成绩信息 printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); printf(“语文新成绩:”); scanf(“%s”,pNodeScore->data.Chinese); printf(“英语新成绩:”); scanf(“%s”,pNodeScore->data.English); printf(“高数新成绩:”); scanf(“%s”,pNodeScore->data.Math); printf(“成绩已经修改！”); return 0; } pNodeScore=pNodeScore->next;//如果不相等，pNodeScore则指向下一个结点 } printf(“没有此学号的学生！n”);//如果找到最后都没有，则输出没有此学号的学生 } int Find(){ p_node_score pNodeScore; pNodeScore=headScore;if(pNodeScore==NULL){ printf(“成绩表中没有数据！请先添加数据！n”); return 0;} char FindNumber[20];printf(“请输入你要查找的学生学号：”);scanf(“%s”,FindNumber);while(pNodeScore!=NULL){ if(strcmp(pNodeScore->data.Number,FindNumber)==0) { printf(“你要查找的学生成绩信息如下：n”); printf(“ 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩n”); PrintScore(pNodeScore->data); return 0; } pNodeScore=pNodeScore->next;} printf(“没有此学号的学生！n”);} int main() //主函数 { int choice=0;headScore=NULL;int c;do { system(“color 2f”); //运行环境背景颜色.printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt 学生成绩管理系统 ttt”); printf(“nntt*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=ntt”); printf(“nttt1.输入成绩信息nttt2.输出成绩信息nttt3.添加成绩信息nttt”); printf(“4.修改成绩信息nttt5.删除成绩信息nttt6.查询成绩信息nttt7.退出”); printf(“nnttt请选择:”); scanf(“%d”,&c); switch(c) { case 1:system(“cls”);Input();break; case 2:system(“cls”);View();break; case 3:system(“cls”);Add();break; case 4:system(“cls”);Change();break; case 5:system(“cls”);Delete();break; case 6:system(“cls”);Find();break; case 7:system(“cls”);exit(0); } }while(1);return 0;} 运行界面如下： 注意：实验结束后提交一份实验报告电子文档 电子文档命名为“学号+姓名”，如：E01214058宋思怡 《数据结构》实验报告 （一）学号：姓名：专业年级： 实验名称：线性表 实验日期：2014年4月14日 实验目的： 1、熟悉线性表的定义及其顺序和链式存储结构； 2、熟练掌握线性表在顺序存储结构上实现基本操作的方法； 3、熟练掌握在各种链表结构中实现线性表基本操作的方法； 4、掌握用 C/C++语言调试程序的基本方法。 实验内容： 一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）初始化顺序表L； （2）依次在L尾部插入元素-1,21,13,24,8； （3）输出顺序表L； （4）输出顺序表L长度； （5）判断顺序表L是否为空； （6）输出顺序表L的第3个元素； （7）输出元素24的位置； （8）在L的第4个元素前插入元素0； （9）输出顺序表L； （10）删除L的第5个元素； （11）输出顺序表L。 源代码 调试分析（给出运行结果界面） 二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： „„„„ „„„„ 小结或讨论: （1）实验中遇到的问题和解决方法 （2）实验中没有解决的问题 （3）体会和提高第四篇：数据结构课程设计
第五篇：数据结构实验报告
点击咨询 