文档介绍：南阳理工学院
数据结构(C语言版)上机实验指导书
软件学院·软件工程
目 录
实验１ 线性表应用
实验2 栈和队列的应用 14
实验３ 线性表应用 27
实验４ 图论及其应用 ４6
实验5 查找
实验6 排序 64
实验1 线性表应用
实验目的
３，了解和掌握线性表顺序存储和链式存储在计算机中的表示，基本操做在计算机中的实
2，能够利用线性表结构对实际问题进行分析建模,利用计算机求解。
1，能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
二、实验内容及步骤
1、利用程序设计语言分别实现顺序表和链表的抽象数据类型。
2、掌握程序分文件（头文件和实现文件)书写的方式.
3、:合并两个非递减有序序列，并对其时间性能做出分析。
三、实验步骤与调试过程
以线性表来描述一元多项式,储存结构采用单链表，每个结点储存的多项式中某一项的系数和指数，建立单链表时指数高的结点列于指数低的结点之后，即线性表的元素按指数递增有序排列。
四、实验结果
五、疑难小结
当线性表的长度变化较大，难以估计其存储规模,另外对线性表频繁进行插入和删除操作时，:（１）应有利于运算的实现；(2）
应有利于数据的特性；(3)应有利于软件环境。
六、主要算法和程序清单
顺序表的非递减数列合并
#inclｕde<stdｉｏ．ｈ> ﻩ ﻩ /*包含输入输出头文件*/
＃define ListSize １00
typedeｆ ｉnt DataTyｐe;
typedef struct
｛
ﻩDatａType lｉｓt[ListＳｉｚe]；
int leｎgth;
}SeqLisｔ；
ｖoid InｉtＬｉｓt（SeqLｉst *L)
/*将线性表初始化为空的线性表只需要把线性表的长度length置为０＊/
｛
L－＞lenｇth=0； /＊把线性表的长度置为0*/
｝
ｉnt ＬisｔEｍpty(SｅqＬｉst Ｌ)
/*判断线性表是否为空，线性表为空返回1,否则返回0＊/
{
iｆ（L．ｌength=＝0） ／＊判断线性表的长度是否为9＊/
rｅｔurn １；ﻩﻩ /＊当线性表为空时,返回1;否则返回0＊/
else
ｒetｕｒn 0；
｝
int GetElem（ＳeqList L，int i，DataType *e）
/＊，并返回1表示成功；否则返回-１表示失败.＊/
｛
ﻩif（i<１||i〉L．length) ／＊在查找第ｉ个元素之前,判断该序号是否合法＊/
return —１；
ﻩ*ｅ=［ｉ-1］；ﻩ ﻩ／*将第i个元素的值赋值给e＊／
reｔurｎ １;
｝
ｉnt LｏｃatｅEｌeｍ（ＳeqLisｔ L,ＤaｔaType ｅ)
/＊查找线性表中元素值为ｅ的元素,查找成功将对应元素的序号返回，否则返回0表示失败。*/
{
iｎｔ i；
ﻩfor(ｉ=0；i<；i＋+) ／＊从第一个元素开始比较*/
if(L。list［i]=＝e）
ﻩ reｔuｒn i+１；
ﻩ retｕrn 0；
}
iｎt InsｅrtList(ＳeqLｉst *L，int i,DａtａTypｅ e)
/＊在顺序表的第i个位置插入元素e，插入成功返回1，如果插入位置不合法返回－1,顺序表满返回0*／
{
int j;
if(ｉ〈1||i>L—＞lｅnｇtｈ+1）ﻩ ﻩﻩ/*在插入元素前，判断插入位置是否合法＊/
{
pｒinｔｆ(”插入位置i不合法！\n＂）；
ｒｅｔｕｒn -1;
ﻩ}
ﻩelse if（L-＞lenｇｔｈ>=ListSｉze) /＊在插入元素前，判断顺序表是否已经满,不能插入元素＊／
{
ﻩｐrintｆ（”顺序表已满,不能插入元素。＼n”);
ﻩﻩreturｎ 0;
｝
ﻩｅlse
ﻩ｛
ﻩfor（j=L—＞ｌｅngtｈ；j＞＝i;j--） ﻩ/＊将第i个位置以后的元素依次后移*/
ﻩﻩ L->list［j]=L—〉list［j-1］;
L->lｉｓt[i—１]＝e； ／*插入元素到第ｉ个位置*/
Ｌ－>length＝L