[信息与通信]贵州大学数据结构实验1-线性表及应用

1、实验一线性表及应用一、实验目的1 .复习C语言的上机环境，掌握C语言的基本结构2 .会定义线性表的顺序存储结构和链表的存储结构3 .熟悉对顺序表的一些基本操作和具体的函数定义。4 .掌握顺序表和单链表的存储结构及相关运算5 .掌握顺序表和单链表的基本应用二、实验硬软件环境硬件环境：赛扬433以上CPU, 10GB以上硬盘，64MB以上内存软件环境：DOS+Turbo C 2.0 或 Borland C+ 3.1 以上Windowx 9X+VC+ 5.0 以上三、实验要求1 .认真阅读和掌握本实验内容所给的全部程序。2 .保存和打印出程序运行结果，并结合程序进行分析。3 .按照你对顺序表操作的需

2、要，屏幕考贝运行结果到实验报告中。4 .撰写实验报告并准时上交四、注意事项在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的 工作目录， 专门用来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。工作目录建议如下建立，最后注明实验作者（张三）：数据结构实验（张三）|+-实验一|+-实验二|.+-实验九实验一至九的有关材料请同学在网上下载（下载网址：.crn）,本实验设计完全由老师设计，版权限本班同学使用，勿外传。实验材料下载到本机后，请用winrar软件释放到你的电脑磁盘的“数据结构 实验（张三）”文件夹中，形成如上图的文件夹结构。上交实验

3、报告时，请把“实验一”的所有内容（含实验报告）用 winrar打包 成.rar文件后一并交上来。上传名字为“实验一（张三）.rar”五、基本理论线性表：线性表（linear list ）是这样的数据对象，其实例形式为：（el , e2， en ）,其中n是有穷自然数。e是表中的元素，n是表的长度。元素 可以被视为原子，因为它们本身的结构与线性表的结构无关。当 n = 0时，表为 空；当n 0时，ei是第一个元素，en是最后一个元素，可以认为e优先于e2, e2优先于e3,如此等等。除了这种优先关系之外，在线性表中不再有其他的结构。基本操作：?创建一个线性表。?确定线性表是否为空。?确定线性表的

4、长度。?查找第k个元素。?查找指定的元素。?删除第k个元素。?在第k个元素之后/之前插入一个新元素。线性表ADT （图1）：抽象数据类型上也取此如（实例。成多卜元素的有序集合探作Clears 0：创建一个空线ft去Destroy （）:删除去七Eh里中0如果去为空则返阿任期返回血能5a 0：返回去的大小（即去中元素个数）用松（匕0:寻找去中第上个元素卜并把它保存到工中；如果不存在，则返回囿耀SWGTh （即返同元素K在表中的位置；如果工不在去中，则返网0D皿加代工）:珊际去中第k个元素，并把它保存到式中、函数返同修改后的茂件去 加门依。在第个元素之后插入函数返PI修改后的线性去OiitVliT

5、 （OUt）.双线性去放入球出流。迎之中图1线性表抽象数据类型顺序表：采用数组来表示一个对象的实例，数组中的每个位置被称之为单元（ cell ） 或节点（node）,每个数组单元应该足够大，以便能够容纳数据对象实例中的任 意一个元素。在某些情况下，每个实例可分别用一个独立的数组来描述，而在其他情况下，可能要使用一个数组来描述几个实例。实例中每个元素在数组中的位 置可以用一个数学公式来指明。假定使用一个数组来描述表，需要把表中的每个元素映射到数组的具体位置 上。第一个元素在什么地方？第二个元素在什么地方？在公式化描述中，可用一个数学公式来确定每个元素的位置。一个简单的映射公式如下：locatio

6、n （i）= i - 1（式 1-1）式1-1表明第i个元素的存储位置在数组的第i-1个位置；如果每个元素的长度为 m,则可以通过公式计算第i个元素的存储地址：Address(i)=Address(1)+(i-1)*m (式 1-2)Address(1)为第1个元素的址，即数组的首地址。特别要记住的是第1个元素保存在数组的第0个位置。element (0 1 2 3 4,Maxsize-1I 5 I 2 ： 4 | 8 |口二二| |length = 5a)element 0 I 2 3 4MaxSize-1I 51418 i n r -1 I length = 4b)图2表性表实例简而言之，

7、顺序表就是把线性表的元素存储在数组中，元素之间的关系直接 通过相邻元素的位置来表达。优点：简单，数据元素的提取速度快；缺点：(1)静态存储，无法预知问题规模的大小，可能空间不足，或浪费存 储空间；(2)插入元素和删除元素时间复杂度高一一O (n)链表：在存储线性表List中的每个元素e时，同时存储元素的下一个元素的首地址 (指针)Address(i+1),通过这种方法建立起元素之间的关系，从“逻辑”上看所 有元素构成了图3所示的“链”，所以称为链表。first图3 一个单链表从图3可以看出元素之间的 链接关系，为了 “访问”每个元素e的，必须知 道e的首地址，而这个首地址存储在其“直接前驱”结

8、点ei-i中，按此规 律，可以回推到元素ei的首地址。即要访问List中任一元素e,都必须从第一个 元素ei开始，所以，必须保存首元素 ei的地址在一个变量中first),有的书使用 Head作为变量名。图3的单链表的首元素的地址在 巾rst中，我们可以直接用吓irst” 称呼此单链表。List中所有元素可以占用连续的存储空间，也可以占用不连续的存储空间。 但是从“逻辑”上来看所有元素仍然满足“一对一”的关系，即：(1)首元素没有“直接前驱”，尾元素没有“直接后继”。（2）中间元素有且仅有一个直接前驱”和“直接后继为了实现这种存储结构，可以使用 C语言作如下定义:typedef struct

9、Lnode DataType data;struct Lnode *next;/*递归定义，保存下一个元素的首地址 */LinkNode;关键字“typedef”的作用把结构体类型定义成一种新的类型LinkNode,即链表中的一个结点类型（用以存储一个数据元素，这样可以定义一个结点变量存储一个 数据元素：LinkNode a;也可定义一个“结点”指针保存某个结点的首地址：LinkNode *p;对于其它可能不支持动态存储分配的高级语言来说，上述LinkNode类型定义 时就内部就不能使用地址，但是我们可以利用数组“ 模拟”链表的功能，这种链 表可以这样定义：typedef strut node

10、DataType data;int next;LinkNode;“指针”域用一个整型变量（next）来表示，用于存储下一个元素位于数组中的“位置”，这样定义的链表如图4所示：data linknode10node(5 node24；图4静态链表链表还有“循环链表”（图5）和“双链表”（图6）,无论多么复杂的链表， 其基础都是单链表，因此，完全掌握单链表后，学习其它有关链接存储将会变得 简单得多，这是本章我们的重点任务。循环单链表，实际上是利用链表的“尾结点”的空指针来指向链表的首结点。 有循环链表后，只要知道链表中任一结点的地址，就可以访问链表中所所有结点。 注意图5b引入了一 “头结点”，目

11、的是让空链表与非空链表统一，方便操作实现。图5循环单链表双链表是在单链表的基础上，在数据元素中再增加一个 冗余项，用以保存结点 的“直接前驱”结点的地址，这样结点既可以指向“直接后继”，也可以指向“直 接前驱”，实现链表的双向查找。01：31 j4liIfLeftEndRight End图6双向链表链表最大的优点是在某个元素之后插入结点或删除结点非常方便，时间复杂度为常数O (1)。缺点是空间利用率低，存取指定元素效率低O (n)。六、实验内容与过程本实验用到的文件有(在文件夹“实验一实验材料”中)Lineast.h、Lineast.cpp LineastTest.cpp、Link.h、Lin

12、k.cpp、LinkTest.cpp 前三个文件保存在 子目录“SqList”中，后三个保存在 子目录“Link”中 后缀有“Test”的文件用以测试顺序表和链表的各项操作的正确性，里面包含了主函数“ main”。*h文件中包含了数据结构的定义，对应的同名 cpp文件包 含了对数据结构进行的各种操作的实现。请按以下提示完成所有实验。(一)文件Lineast.cpp是顺序表的实现，其中有三个函数没有完全实现，请 同学认真阅读整个程序，然后根据所学的知识完善，完善后编译Lineast.cpp,然后运行LineastText.CPP屏幕出现菜单：Lineast.CPP中需要补充的代码如下：int I

13、nsertElem(SqList *L,int i, ElemType *e) /* 在第 i 个位置插入元素，插入成功 返回1*/int j;/*请在以下部分插入程序代码*/if(GetLength(L)=LINEASTMAXSIZE|iGetLength(L)+1|iLength+1;ji;j-)L-dataj=L-dataj-1;L-Length+;L-datai=*e;/*插入代码结束*/return 1;int DeleteElem(SqList *L,int i) /*删除第i个元素删除成功返回1*/ int j;int n=GetLength(L);/*请在以下部分插入程序代码*

14、/if(n=0|in)printf(error);return 0; elsefor(j=i;jLength;j+)L-dataj=L-dataj+1;L-Length-;/*插入代码结束*/return 1;,.int SearchElem(SqList *L,ElemType *e) /*查找元素*e 的位置 j,找到返回，失败 返回-1 */int j;int n=GetLength(L);/*请在下面插入你的代码*/j=GetLength(L)+1;for(int m=1;mdatam=*e)j=m;break;elsecontinue;/*插入代码结束*/return jebugli

15、nk.EXFour List isIS 2039 4R 5。66?0 Hg1CreateList寺piny Lit3Delete 日 Eliainent4. Insc-rt & Ele-ncrnt5. Pisplav List 工心ngtii， Change 5/m七 Element uhIue7. Gc t i, st EIe non t Ualue8lC124即 第ur* Lit0-Exit ny pres gran?3Flcasc Enter a Hd of Elcnrenit vou waiinit to de leteT 1203040 St GM 70901.CrBateList2

16、.Display List3 Delete a ElsnentHI-Insert a Elcncnt5.Di&pgy Li&t length&,Cliang*; i* st Element!7.Get i. st Elsment Ualnol-xClcF ybur List0dExit; ny progfrant屏显:(4)输入3,回车后，根据屏幕提示输入 3,回车C:UsersAdnni nistratorXOocumeritsWisual Studio 2Q10Projed:sJinkDebijgyiink.exe20 3B 40506070 SB 9011 .CieateList2 .D

17、i.splay List3 .Delete a Element4 - Ln-sert a Element 5Lit length G.Change i*st Elcnent value 7*Get 1Jst Element UaluB8-Clcflr your ListDm Exit ny pFOqHdZ 3Pleasb Enter a Ho of Elspent 叩u want to delstof 32030 SO 6070 S0 9S1 .CxatLi$t.2 .Display List3 .Dhlete a Element4 . Iner a Element5 .Display Lis

18、t lengftlib.Change i* at Elenent yaluc7 .Get 1Jst Element Ualue0-Clear yomr List0.Exit ny pr*口qiain1!屏显:(5)输入3,回车后，根据屏幕提示输入 7,回车 CAU$er$AdmKi1a2iQoscrt a ElciracntP - Display List lencrtlkPaChange ist Element u&lup?BGe-t苣inuirtt U.ue .Clear- yowr List . Exit iray pyoiam!日，冲263050&070 B0.GreatsList L

19、iet .Dti lete a E le ne nt . I nisert a EJ*?PieFt .Display List longth ,Change ist Element ualite .Ge t厚上 EleiraEnt Udlue.Clear your List .Exit him program!屏显:日白肿片口 m20305Q9769l-CreteLit. IB is play Lm土土：3 a Di- lete a Elene nt-nsc-rt a Element5 .Di”Id岁 List langth6 . Chanssie iJ t Elams nt value7a

20、Get i1* st Elene nt Ulue19 - ClediF yaur List j?xlt Fly piMiigr-a.ra?;；Please Enter a No of Elcncnt you -1典mintto de Ie t e!日胪X口 m2030581 一 C 炉e at 剪 LiiwE. display ListJ .11r：d Elcvirznt：4.1 nstrt a Elciment5.Display List lengtliB.Change iJ st Elameinit value 7,UeC i1st ElARant Ulue6 . Cl6diF 典uF L

21、lfitAl- Exit viiy piNigpani*7683口 一丰原因：此表是从1开始的，不存在-1(9)输入4,回车后，根据屏幕提示输入:35 3,回车 QUsef5AdministratorIDcumentsVisDal Studio 2010iPrajectslinkDebugl ink.exe70屏显:1 . CaKia k e Li s t2 . DisulaiLj1 List3 -a Elene Fit.Inherit a Elcnont 5.Dplay Li凿t length &. Changeat Element: v.aluc?sQet srt Elengnit Ual

22、ue H.Clear yom ListaExitmy pt*ogriamtEntet a Elennet value sndPo?it ion ljou Mill . DiSjpiliy L*t l&ng19-i .Change st Element v-alue ?aG&t ip st Elngnt Ualuei：.Clear your ListExit my pf&gramt(10)输入4,回车后，根据屏幕提示输入:10 1,回车C：U seEfiSAdiTiinistfateirXDaeu mentsViLjal Studio 201ffProjece二匚y：工2030355660 7B

23、 fifi1,CreateList W.Diwj)191y Li3t 3Delete a Elsment 4&In&eFt a Element 5.Display List length6 .Ch-dii-ijE iJ s t E ItfFwii t u-a Iue 7_e：七s t ElemE-n-fc Ualue8.Cltfir ynur List ny PTOgrami?4Plsase E mt er a iElennet value and Position 和 u uill Iniertt IB 1IS 2036355676 SBi .CrifJitBLis.t屏显:2 1rDisp

24、lftv List 3-Delete q Element 4.neert a Element S -Di&pla9 Lis；t length EiCHang 包 iJ s t Elemnt ua Iue 7.Get iF St Elernn-nt Ualue 8.rClcr ynur List H.Exit： my pTOgram?(11)输入4,回车后，根据屏幕提示输入：5 0,回车屏显:原因：插入元素必须为在1到L-length+1之间(12)输入4,回车后，根据屏幕提示输入：5 -1,回车屏显:屏显:(13)输入4,回车后，根据屏幕提示输入：90 9,回车输入4,回车后，根据屏幕提示输入

25、：95 10,回车原因：插入元素必须为在1到L-length+1之间 (13)屏显:(14)输入4,回车后，根据屏幕提示输入：100 12,回车C:UsersAdm n istratorDocu mentsVisua I Studio 2OlOProjectslinklebLglinLex010口9 3560 7R 期自 90951 .GreateList2 .Display List3 a Elsment;471 iisg-r-t & ElbmKnlt5 .Pispla.y Li5C lengthG .Cliaihiye i* St Elen&nt krluE7 .Get ist Eleme

26、nt： Value84cLe/妙 you* List0-Exit nv prci gran?8Flease Enter a Elcmnct ualuic and Positian vnu will Jnsert? ISO 12 error10263550 ED 70 8BK12List及 Img i Element4-Insert a Element5,Display L工3t length6 .Chanige ia ct Ele nan t ualue7,Gct i* st ElLuFiicnt Ualuc8.ClBai* you洋 List屏显: , Ex it my PE giF4n?原

27、因：插入元素必须为在1到L-length+1之间 (15)输入5,回车屏显：(16)UJWB12ferrr-10230355B1 .CreateListb .Pisplai/ List3 r&c Icte 飙 ElementM-t Inscr-t 0 Elementp -Display List length6 Charite i st Ele-nent value7 .Get st Element UbiIuic8 rClear i/our ListRhExiit ny p及。轲即品 mlELength of List is： 10709B95a rCrctcLi&tp _ DSp lay。

28、工f t3 lete a Elementk. Insert a ElementrDi&pljii/ List length6,Change ip st EleHenl: value7_Get i* st Element UailueS .Clear- ycrnjii* ListM.EmIt ny program?C;UsFs，,MAdminis-tratcir&c?cijment5Vi5ual Studio 2010Proiedtsl inkDebuglinkiexiB输入6,回车后，根据屏幕提入示输入：70 4,回车licng-th of List 土S 10屏显:Enter a Eleme

29、nt value and pasit ion you hrill Cliftngc J my progrsmTy口uir Listmy ppijg单tSiml8 - C le ar H.Exit i6Please :70 41. CreateLi&t .Display List;3.De Lete a ELencmt4.insert a El&ncnt E.Display List length6 .Change iBst Elenent value7 - Get ip st Element Ualuciel.Oeat eList2 .Display List3 .De Let& a Elen

30、ent Insei4t a Elenent5 . Display List lengt!ifc . Chftngfc i* st Elencnt value7 .Gtit i-st fl&nenit Value8 Lisi;(17)输入6,回车后，根据屏幕提入示输入：5 0,回车7WStudio 201 iJrcjectshnDcbLigXIinkira(19)输入6,回车后，根据屏幕提入示输入：110 11,回车10 ZM 3U 7H5 修6 修 70 SU?Sh. .Crc ante Listb -Displaiij List b.Dcl&tE ii Elcmcitt4.nscrt a E

31、lcncnt 5i笈口 1地y List length 6,Change i* St Elenent value b,Get ipst Elcmriit U蠹lue HlClear* you1k List REm It my pHnainl 匕Pleaise Enter a Element ualue! and position 9011 will Changef p 0IB 203070 SB ED 7080?095p .Cieiat EiListp Dis play Listpl .DeLota a Elementk. 1 nsBrt a ELmntp -Display List 工心n斗

32、 1thfc .ClhansfE i毋七 El&n&nt vain已r?.Gct i# st Element Ualuc,Clear iKiur Li5t屏显:M.Exit my pi*Dgi产ee1!原因：(18)对表操作必须在 1到L-length输入6,回车后，根据屏幕提入示输入：100 9,回车屏显:5 B9095102B1070506。70国01 = CreateList2 B DisplA LiEt3 . De lete a Eleiterit4 .LnseiM a Elenent8 . Displai List lemsTth6 . Changiost Element walue

33、?-Gfet ijlst Elencnt Uaiueg . Clear your Lizt0.Exit ny progranJPIcasc Enter a Elenent ualucandpos it ion youwillChange!1 (e i100 91020307050&B 700180951 . CreafccLi.st2 . Display Lit3 = Delete a Elcnent-Tflsert a 1匕m尊蛇t5BDisplay List leMthB B Change 1B st Eleirinit ualue7.Giet 1*st Elenent lllalueS

34、B Cleai* yuuF List0 , Exit ny prog pan!inistratorDocum e ntVieual Studio iOlOXPrajectsXlinDebugJirik.e:原因修改元素后并为对 L-length进彳+ +(20)输入7,回车后，根据屏幕提入示输入：6,回车屏显:(21)输入7,回车后，根据屏幕提入示输入：0,回车屏显:1 .CpeateLlst1 .CreateList1nept a Elenent2.1H钟lay liit 3vDelete a Elenent 4.nscrt 昌 Elcnent 5,Display List length G

35、.Change ifst Element value 7.Get i* st Elcmnt Ualwe 8 . Clear your List M.Exit my pr-ogran!Get st Element value.Disulajj List3 , DeIcte a Element4.Jn&ert a ElenBntS - Diplajyi Lisrt length b.Chdinge lst ElenenC value 7 .Get i.r st Elencnt Ualue b-Clea* ynur List 出 Exit e* pagpan!1Please Enter a Elem

36、ent vaLuc 由nd it ion you will Change! 110 11后* List lengthG .Change i* st Elene nt value7-Gct st ElenErnt Ualuc8Cleai* jiour List H.Escit e* progsianJPlease Entep i1.CreatcList2.Display List3.Delete d Elciwnt4. nsert a Elcmnt!Displai/ List lengtlh& .Change i* st ElenKmt ualu.e V.Get i*st Eleognt Ual

37、ue8-CleaF 9口uf List 0_Ex:it em pDpan*U蒯9 1W 2U3 970i SO bH 708 99SIS 2B 3B k,CreateList12.Display List P DeletB a Elen&nt1 .CieateLisI:Q,List3 De lets 由 ElenntH*nsert a Elenent5 .Display List lengthf.Change i* st Element ualug7 .Get iJst Element Ualuc8 . Clear yuiur Listny progirrtfiT7Get i/st Eleme

38、nt value Please Enter 1：1 .CreateLi&t2 .Di&play List3 .Delete a Element4 -nsert a Element5 .Display Llt length6 .Charte i st EIgm腔nt7 .Get i*st Element8 .C1wl your List B.Exit m* program!B data(0 J=-l屏显：原因数组是从1开始的(22)输入7,回车后，根据屏幕提入示输入：10,回车CfSUsersvAdmi nistratoDoc uit cntVis u 1口 X1 .CreatEList2 .D

39、isplay ListB.Delete a Elzment4-Insert a El启meet5List length& diansre L* st Elenent value7&Get i1st ELbment ValueB.Clear our ListB- Exit ny progfram?7Get i,st Elcnent valueFlease Entei* 1- i Gl119riata101=y51CreateList2 .Display Li&t3 let a Elenient4 - Insert a Element5 .Display List lengthG .CliaiiE

40、 1? st Elcpicrkt yaluc7-Get ist Elenient ValueS.CleAr your ListB.Exit my program! 原因：第10号元素存在，并且为 95(23)输入8,回车1 .CreateLit空三 Display List：3 . De lete a Elemenit4 .Insert a Element5 .Dsplmy List length6 . Cangb i 3 Create Licit B Di&plav List De Lctc a Element 4. nsert a. Element .Display List Itn卬1t

41、hb. Ghangie i - st Elene mt value7,Get V st Element ValueS,Clear your ListH Exit my progpanT1 st ElemBrit value7B Get iJ st ElenKiot Ualue8.Clear your Li隼tB.Exit my programJ8Hgu, iou List lias no e leiniEMit f f 1.CreateListZ.Display List3. De lete a E lente nt4.1 insert a Element5 4 Display List le

42、nyth6 .Change ist Elenent ualue7 .Get i1st Element Value8 .Clear 9our Lit屏显:9 . Ex it my piqa gvani f(24)输入2,回车Hoy you list has no c Icneint ? ?1.CreateList2,Display List3,Delete a Elenent4 insert a Element4.Di臂pl事y Ligt length6 Chainsfe st Elenent yalue7-Get iJ st Element Ualus8 . Clear your ListYu

43、u胪 List is Lineast is Emptj/?T!屏显:原因:L-length 被清 0进一步思考并回答：(1)步骤1、2分别用来干什么？答：初始化一个顺序表(2)步骤2-8用来干什么？其中步骤5-8有什么用？答：2到8是用来删除一个元素，5到8是用来验证当删除条件不满足时是否能 执行删除。(3)步骤9-14用来干什么？其中11、12、13、14的目的是什么？答：9到14是用来加入一个元素，11到14是用来验证当插入条件不满足时是否 能进行插入。(4)步骤16-19作用是什么?答：是用来改变一个表内元素的值。（5）步骤20-21作用是什么？答：是用来验证当改变条件不满足时，是否能改

44、变一个表内元素的值。（二）单链表的操作实现放在Link.CPP中，其中有几个函数未完成（如下），请 同学们认真这个文件中的所有操作的实现，在适当的地方补充完成本实验：LKList FindElem(LKList *L,int i) /*查找第i个元素的操作，近到返回元素地址, 找不到返回空*/LKList p=*L;int j=0;/*以下补充代码*/if(*L=NULL) return NULL;int n=GetLength(L);if(in)return NULL;if(i=1) return p;for(j=0;jnext;elsebreak;/*代码补充结束*/ return p;int InsertElem(LKList *L,int i, ElemType *e)/*在第 i 个位置插入元素 */LKList p=FindElem(L,i-1);LNode *s;/*构造待插入的结点*/s=(LNode*)malloc(sizeof(LNode);s-data=*e;s-next=NULL;/*以下补充代码*/if (i=1) s-next=*L;*L=s;return 1;if