数据结构实验C语言版.docx

数据结构实验C语言版

第一篇：数据结构实验C语言版南阳理工学院数据结构(C语言版)上机实验指导书软件学院·软件工程目录实验1线性表应用实验2栈和队列的应用.......................................................................14实验3线性表应用...............................................................................27实验4图论及其应用...........................................................................46实验5查找实验6排序...........................................................................................64实验1线性表应用一、实验目的3，了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实2，能够利用线性表结构对实际问题进行分析建模，利用计算机求解。1，能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。二、实验内容及步骤1、利用程序设计语言分别实现顺序表和链表的抽象数据类型。2、掌握程序分文件（头文件和实现文件）书写的方式。3、分别用顺序表和链表实现课本算法2.2：合并两个非递减有序序列，并对其时间性能做出分析。三、实验步骤与调试过程以线性表来描述一元多项式，储存结构采用单链表，每个结点储存的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指数递增有序排列。四、实验结果五、疑难小结当线性表的长度变化较大，难以估计其存储规模，另外对线性表频繁进行插入和删除操作时，则采用链表作为存储结构可能会更好一些。在实际应用中应该考虑以下因素：(1)应有利于运算的实现；(2)应有利于数据的特性；(3)应有利于软件环境。六、主要算法和程序清单顺序表的非递减数列合并#include/*包含输入输出头文件*/#defineListSize100typedefintDataType;typedefstruct{DataTypelist[ListSize];intlength;}SeqList;voidInitList(SeqList*L)/*将线性表初始化为空的线性表只需要把线性表的长度length置为0*/{L->length=0;/*把线性表的长度置为0*/}intListEmpty(SeqListL)/*判断线性表是否为空，线性表为空返回1，否则返回0*/{if(L.length==0)/*判断线性表的长度是否为9*/return1;/*当线性表为空时，返回1；否则返回0*/elsereturn0;}intGetElem(SeqListL,inti,DataType*e)/*查找线性表中第i个元素。查找成功将该值返回给e，并返回1表示成功；否则返回-1表示失败。*/{if(iL.length)/*在查找第i个元素之前，判断该序号是否合法*/return-1;*e=L.list[i-1];/*将第i个元素的值赋值给e*/return1;}intLocateElem(SeqListL,DataTypee)/*查找线性表中元素值为e的元素，查找成功将对应元素的序号返回，否则返回0表示失败。*/{inti;for(i=0;iif(L.list[i]==e)returni+1;return0;}intInsertList(SeqList*L,inti,DataTypee)/*在顺序表的第i个位置插入元素e，插入成功返回1，如果插入位置不合法返回-1，顺序表满返回0*/{intj;if(iL->length+1)/*在插入元素前，判断插入位置是否合法*/{printf(“插入位置i不合法！n”);return-1;}elseif(L->length>=ListSize)/*在插入元素前，判断顺序表是否已经满，不能插入元素*/{printf(“顺序表已满，不能插入元素。n”);return0;}else{for(j=L->length;j>=i;j--)/*将第i个位置以后的元素依次后移*/L->list[j]=L->list[j-1];L->list[i-1]=e;/*插入元素到第i个位置*/L->length=L->length+1;/*将顺序表长增1*/return1;}}intDeleteList(SeqList*L,inti,DataType*e){intj;if(L->length{printf(“顺序表已空不能进行