统计学专业毕业论文数据结构与算法实验

摘 要本论文通过对5个常用的数据结构实验设计的介绍，阐述每个数据结构内在的逻辑关系，讨论他们在计算机中的存储形式，以及在这些数据结构上的运算（操作），并对算法的效率进行简要的分析和讨论。第一章主要介绍了有序表的建立、插入与删除，理解插入与删除的操做方法；第二章链表及其多项式相加，了主要讨论线性表的链式储存结构，链表及其多项式相加的算法；第三章稀疏矩阵的建立与转置，主要介绍稀疏矩阵的三元存储形式和三元表存储矩阵的转置算法；第四章二叉树及其先序遍历，介绍树形结构和二叉树的先序遍历；第五章中序线索二叉树，主要叙述线索二叉树的算法和中序线索及其遍历的实现过程。并可以有效地检验学习效果和培养程序设计能力。算法是用C语言描述，并在Visual Basic C+ 6.0 环境下运行的，增强了算法的可理解性和可操作性。关键词 数据结构，实验设计，算法ABSTRACTThe paper introduces five commonly used data structure design of experiment, Mainly expounds each data structure inherent logic relationship, discuss the storage form of them in the computer, and the operations (operating) of the data structure, to analyze and discusse the efficiency of the algorithm briefly. The first chapter introduces the first chapter and orderly, insert table and delete, insert and delete operation of understanding algorithm, The second ZhangLian table and the main discussion, polynomial linear chain store structure, the watch list of the algorithm, and polynomials, The third chapter sparse matrix and transposed, mainly introduce the ternary sparse matrix forms of storage and storage of ternary table algorithm; transposed matrix, The fourth chapter binary tree and its first traverse sequence, a tree structure and binary trees first traverse sequence, The fifth chapter sequence clues binary tree, main narrative clues binary tree algorithm and traverse sequence clues and the implementation process. And can effectively inspection program design and learning effect. Algorithm is described in Visual Basic C+ 6.0 and in the operating environment, improve the algorithm of comprehensible and operability.Key Words: data structure, experimental design ,algorithmII目 录前 言5第一章 有序表的建立、插入与删除61.1实验目的61.2实验原理61.3.程序流程图71.4参考程序与运行结果81.5实验步骤141.6思考问题14第二章 链表及其多项式相加152.1.实验目的152.2.实验原理152.3.实验要求152.4.程序流程图162.5.参考程序与运行结果172.6.思考问题22第三章 稀疏矩阵的建立与转置233.1.实验目的233.2.实验内容233.3.实验步骤243.4.程序流程图243.5.参考程序与运行结果253.6.思考问题27第四章 二叉树及其先序遍历284.1.实验目的284.2.实验内容284.3.实验步骤284.4.程序流程图294.5.参考程序与运行结果294.6.思考问题31第五章 中序线索二叉树325.1.实验目的325.2.实验内容325.3.参考程序与运行结果335.4.思考问题35致 谢36参考文献37前 言数据结构与算法这门课程中，基础性实验设计十分重要。虽然有许许多多的关于数据结构与算法的书籍，但这些书籍基本上都是着重理论讲解，很少对课程中所涉及的实验进行单独的研究与开发。而本论文通过单独及全面的强化课程的核心实验研究，进一步利用C语言进行编程和调试程序，能够利用C语言编写较复杂的程序，加深对教学内容的理解，验证所学的算法和数据结构，培养了设计数据结构的能力和根据数据结构设计算法的能力，掌握了非数值问题的数据结构和算法的设计方法，通过对具体问题的分析、设计和实现，培养了软件开发所需要的实践能力。本论文总共包括五章内容即五个基本实验,系统的介绍实验环境,算法的基本知识、技术和方法。第一章有序表的建立、插入与删除，主要介绍了有序表的储存结构和有序表元素在内存中的储存方法及加深理解线性表的顺序表示与链式表示的意义和区别，理解用它们表示时插入与删除操作的算法；第二章链表及其多项式相加，了主要讨论线性表的链式储存结构，链表及其多项式相加的算法；第三章稀疏矩阵的建立与转置，主要介绍稀疏矩阵的三元存储形式和三元表存储矩阵的转置算法；第四章二叉树及其先序遍历，介绍树形结构和二叉树的先序遍历；第五章中序线索二叉树，主要叙述线索二叉树的算法和中序线索及其遍历的实现过程。本论文主要通过实验原理、实验程序说明、实验流程图以及参考程序与运行结果来介绍课程设计的题目及实现方法。论文分别从实验的六个方面（实验目的、实验原理、程序流程图、参考程序和运行结果、实验步骤以及思考问题）来组织内容，注重原理和实践,每章都以实验目的和原理为出发点,强调了每个实验要掌握的内容和达到的层次；实验内容是对文中基本实验的问题进行描述，并且对实验要求经行了规划；实验步骤是指进行实验的具体操作；经过实验流程图和详细的参考程序及运行结果来介绍所做实验的实现方法；最后以每章配有的思考问题来回忆和巩固实验。本论文从实践出发,阐述了数据结构与算法课程综合性、设计性实验项目的目的、选题、内容及实施,并对这类实验的实践成果进行了总结, 阐述了怎么样根据实际问题来取舍数据结构和算法，并且在时间复杂度和空间复杂度之间进行平衡。本论文所有程序均在C-Free 4.1环境下调试通过。第一章 有序表的建立、插入与删除1.1 实验目的1、了解有序表的顺序存贮结构。 2、掌握有序表元素在内存中是怎样存贮的。3、在有序表中实现如下操作：(1) 插入一个新元素到第i个位置。使原来标号为增1。(2) 删除第i个位置的元素。 (3) 存一个新元素到第i个位置。(4) 读表 (5) 检索表中第i个元素。(6) 寻表的长度 1.2 实验原理(一) 线性表是最常用的而且也是最简单的一种数据结构与算法，线性表是N个数据元素的有限序列。例如26个英文元素的字母表：（A，B，C，D，）。其数据结构与算法的描述为：Linear_list=(D,R)其中：D=ai|aiD0,i=1,2,3,R=N,N=|i=2,3,4,。本实验是以数组的形式把有序表存放在计算机内存的一个连续的区域内，这样便有：LOC(ai+1)=LOC(ai)+m。其中m是存放每个元素所占的内存字数。LOC(ai)=LO+m(i-1)。其中LO是ai的地址，即首地址。(二) 实验程序说明插入一个新元素到第i个位置，既把元素ai向后移一个位置，成为元素ai+1，把新元素放入到第i个位置，其他元素依次后移；存一新元素到第i个位置是把元素ai冲掉后存上新值；删除第i个元素就是把余后的元素依次向前移一个位置。即：以元素ai+1，ai+2，依次取代ai，ai+1，。删除后的表长是n-1（n是原表长）。开始循环初始化顺序表P=0 否？结束P值合适吗？P=1插入P=2删除P=3读新值P=4读表P=5检索P=6查表长调用SHOW过程显示功能表1.3. 程序流程图1.4 参考程序与运行结果/* 有序表的建立、插入与删除 */static int array100;int j,i,n,p;int ch; void du() printf(please tell me which numbers do you operate:);scanf(%d,&i); while (in) printf(ERROR,please enter new element); scanf(%d,&i); void da() printf(the list is:); for(j=0;jn;j+) printf(%3d,arrayj); printf(n); void show() printf(-n); printf( the function of the listn); printf( 1: insertn); printf( 2: deleten); printf( 3: save new elementn); printf( 4: read listn); printf( 5: checkn); printf( 6: the length of the listn); printf( 0: endn); printf(-n); main() printf(please input the length of list:); scanf(%d,&n); printf(n); printf(please enter number:); for (i=0;i=0&p=i-1;j-) arrayj+1=arrayj; printf(please enter number:n); scanf(%d,&ch); arrayi-1=ch; n+=1; da(); break; case 2: du(); for(j=i-1;jcoef,&p1-exp); /*录入多项式*/ if (p1-coef=0) head=0; else while(p1-coef!=0) n+; if (n=1) head=p1; else p2-next=p1; p2=p1; p1=(line *)malloc(sizeof(line); scanf(%d%d,&p1-coef,&p1-exp); p2-next=0; return(head); /* 以下是输出多项式的函数 */ void print(line *p) line *p0; p0=p; printf( ); if(p0!=0) do printf(%dx的%d次幂,p0-coef,p0-exp); p0=p0-next; if(p0!=0) printf(+); while(p0!=0); else printf( 空多项式!); printf(n); int compare(int m,int n) /*比较两个整数的大小的函数*/ int j; if (mn) j=1; return(j);void freeNode(line *w1) /* 释放一个表中的所有结点 */ line *w2; w2=w1-next; while(w1) free(w1); w1=w2; w2=w2-next; line *AddLine(line *ha,line *hb) /*两个非空多项式相加*/ line *la,*lb,*lc; int a,b,sum; lc=ha; la=ha; lb=hb; if (ha=0)&(hb!=0) return(hb); while (la!=0)&(lb!=0) a=la-exp; b=lb-exp; switch( compare(a,b) ) /*比较当前结点指数的大小 */ case -1: ha=la; /*只修改la的指针*/ la=la-next; break; case 0: sum=la-coef+lb-coef; if(sum!=0) /* 将其不为零的系数和保存 */ la-coef=sum; ha=la; la=la-next; /* end if*/ else /* 分别删除系数和为零的对应的两个结点 */ if (lc=la) lc=lc-next;ha=lc;la=ha; /* 刚开始时特殊处理头结点 */ else ha-next=la-next; la=ha-next; /*end else*/ hb=lb; lb=lb-next; break; case 1: /* 将指数小的项插入到la的前部 */ hb=lb-next; if(ha=la) lc=lb;lb-next=ha;la=la-next; else ha-next=lb; lb-next=la; ha=la; la=la-next; lb=hb-next; break; /*end swtich*/ /*end while*/ if (lb!=0) ha-next=lb; return(lc); /*end AddLine */ /*以下为主程序*/ main() line *la,*lb,*lc; printf(请输入多项式La: ); la=creat(); printf(请输入多项式Lb: ); lb=creat(); printf(多项式La:n); print(la); printf(多项式Lb:n); print(lb); printf(多项式La与Lb的和是: n); lc=AddLine(la,lb); print(lc); freeNode(lb); 2.6. 思考问题1、 链表的特性和优点是什么？2、 修改实验程序将系数域改写为实数域，并且修改相应的程序语句。3、 试将多项式输出按升幂排序。第三章 稀疏矩阵的建立与转置3.1. 实验目的1. 了解稀疏矩阵的三元组存储形式。2. 熟悉掌握三元表存储矩阵的转置算法。3.2. 实验内容矩阵是很多的科学与工程计算中研究的数学对象。在此，我们感兴趣的是，从数学结构这门学科着眼，如何存储矩阵的元从而使矩阵的各种运算有效的进行。本来，用二维数组存储矩阵，在逻辑上意义是很明确的，也很容易理解，操作也很容易和方便。但是在数值分析中经常出现一些阶数很高的矩阵，同时，在矩阵中又有很多值相同或者都为零的元素，可以对这种矩阵进行压缩存储：对多个值相同的元素只分配一个存储空间；对零元素不分配空间。稀疏矩阵的定义是一个模糊的定义：即非零元个数较零元个数较少的矩阵。例如下图所示的矩阵： 0 12 9 0 0 0 00 0 0 0 0 0 0 3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0为一个稀疏矩阵。为了实现稀疏矩阵的这种存储结构，引入三元组这种数据结构与算法。三元组的线性表顺序存储形式如下图：MUNUTUIIVIJVIJVA， B：ARRAY1。MAXNUMOF TUPLE3TP3.3. 实验步骤看懂书上的算法，参考书上的程序编写程序上机调试、输入数据、检验结果开 始调用建立稀疏矩阵过程调用转置矩阵过程调用输出矩阵过程结 束开始置B为A的空转置矩阵非零元个数=0 ？ Q = 1 ;COL = 1;COL列值？P非零元个数？若三元组的列号为所寻列，则置换之。Q = Q+1结 束3.4. 程序流程图 Y N Y N COL+1 Y P+13.5. 参考程序与运行结果struct tuple3tp /*稀疏矩阵的建立和转置*/int i,j;int v;struct sparmattpint mu,nu,tu;struct tuple3tp data31;struct sparmattp a,b;void crt_sparmat()int i;printf(输入稀疏矩阵行值,列值,最大非零元个数:);scanf(%d%d%d,&a.mu,&a.nu,&a.tu);for(i=1;i=a.tu;i+)printf(输入行坐标,列坐标,非零元);scanf(%d%d%d,&a.datai.i,&a.datai.j,&a.datai.v);void trans_sparmat()int col,p,q;b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;if(b.tu!=0)q=1;for(col=1;col=a.nu;col+)for(p=1;p=a.tu;p+) if (a.datap.j=col) b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.v=a.datap.v;q+;out(struct sparmattp x)int i,j,k,flag;for(i=1;i=x.mu;i+)for(j=1;j=x.nu;j+)flag=0;for(k=1;kdata); preorder(bt-lchild); preorder(bt-rchild); else if(g=2) printf(空树n); bitreptr *crt_bt() /*建立二叉树*/ bitreptr *bt; char ch; if(f=1) printf(输入根结点，#表示结束n); else printf(输入结点，#表示结束n); scanf(n%c,&ch); f=f+1; if(ch=#) bt=null; else bt=(bitreptr *)malloc(len); bt-data=ch; printf(%c 左孩子,bt-data); bt-lchild=crt_bt(); printf(%c 右孩子,bt-data); bt-rchild=crt_bt(); return(bt);main()f=1; g=1; bt=crt_bt(); preorder(bt); 4.6. 思考问题画出给出的各类型的数据示意图，理解为不同目的而建立的不同数据结构与算法意义。2. 改写程序完成中、后序遍历。3. 考虑用非递归算法完成二叉树遍历。第五章 中序线索二叉树5.1. 实验目的1. 理解线索的含义，掌握线索二叉树的算法。2. 了解中序线索及其遍历的实现过程。5.2. 实验内容从实验四可知，遍历二叉树是以一定的规则，将二叉树中的结点排列成一个线性序列，得到二叉树的先序序列、中序序列、或者后序序列。这实质是将一个非线性结构进行线性化操作。但是，当以二叉链表作为存储结构时，只能找到左右孩子的信息，而不能找到任意的结点的前驱信息和后继信息。这种信息只能在遍历的动态过程之中才能得到。试做如下的结点结构：LCHLDLTAGDATARTAGRCHILD 其中： 0 LCHILD 域指示结点的左孩子 LTAG=1 LCHILD 域指示结点的右孩子 0 RCHILD 域指示结点的左孩子 RTAG=1 RCHILD 域指示结点的右孩子以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线性链表。其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树叫做线索二叉树。对二叉树进行某种操作使其变为线索二叉树的过程叫做线索化。在线索二叉树上进行遍历，只要先找到序列的第一个结点，然后依次找结点的后继直到结点的后继为空时为止。5.3. 参考程序与运行结果#include#include# define thlinktp struct type1# define null 0# define len sizeof(struct type1) struct type1/*线索二叉树结点类型说明*/char data;int ltag, rtag;thlinktp *lchild, *rchild;int f, g;thlinktp *pre, *thrt, *bt; void inthread(thlinktp *p)/*中序线索二叉树*/ if(p)inthread(p-lchild);if(p-lchild=null)p-ltag=1;p-lchild=pre;if(pre-rchild=null)p-rtag=1;p-rchild=p;pre=p;inthread(p-rchild); thlinktp *crt_thbt()/*建立双向线索二叉树*/thlinktp *bt;char ch;if(f=1) printf(输入根结点，#表示结束n);else printf(输入结点，#表示结束n);scanf(n%c, &ch);