课程试验报告线性表

1、课程实验报告线性表作者： 日期：课程实验报告专业年级2012级软件工程课程名称数据结构 C 语言描述指导教师申红婷学生姓名王晓霞学号02实验日期212.1.31实验地点A3 笃行楼 A 栋 306实验成绩教务处制203 年 10 月 31 日实验项目 名称线性表实验一. 目的：. 使学生对线性表的顺序存储结构、 基本操作和应用 , 能通过实验达到掌握和应用的目的。实验 目的及要求2. 使学生对线性表的线性表的链式结构、 基本操作和应用 , 能通过实验达到掌握和 应用的目的。二. 要求 :实验时自觉遵守课堂纪律，严格按操作规程操作 , 既实验前认真预习实验内容。要独立操作又要与其他同学配合，在实

2、验过程中必须按照实验内容认真做完实验， 并认真填写相关实验报告。实验 内容线性表的顺序存储结构和线性表的链式结构、基本操和应用。、阅读下面程序 , 在横线处填写函数的基本功能。并运行程序, 写出结果。#i clude#in udm ll c #defi e RROR# efine OK 1#efi e IN T SIZE 5/ 初始分配的顺序表长度 /#eine N EM *溢出时 , 顺序表长度的增量 */typedef n le Type； * 定义表元素的类型 /typedef struct q is ?El Type sl t;* 存储空间的基地址 */?int ength;/ 顺序表

3、的当前长度 */?in l stsize;Sqlist;/ 当前分配的存储空间 * int i Li _s (S l /int C eate ist s( Sqlist ); * 初始化顺序表 , 为其分配存储空间 *L ，int n); / 创建一个顺序表 */i t istInse t_s ( ql实验步骤ist *L,int i,Ele T e )；/* 将新元素 e 插入到顺序表第 i 个位置 */ t P Lis _ q(Sqli t *L); / 输出顺序表的元素 */ nt Li Delet sq(Sqi L, nt i ); / 删除第个元素 */int is Loc te (

4、Sql s *L,E eType e); /* 查找值为 e的元素 */nt I itList_sq ( qlis *L)L-slist= ( Elem yp *)m loc ( INIT SI *siz of( l Ty);if(!L- sl st) retu n ERR R;L-l ng h=0;- istsize=I _IZE;ret rn O ；/*InitL t* int CreaLs_sq（Sqlis *L,i t n） Ele T pe e; int i;for（ =0;i ； i+） pr tf（ nut data ,i 1）；sanf （% , e）;f（ ！ L nser

5、sq（L, +1,e） ） re urn E ROR；re un O ;/ C eateList*/* 输出顺序表中的元素 */int rin st_s （ ist *L）i t i ；for （ = ; len th;i +） rintf（ %5d,L si -1） ； re rn OK;/*Pri tL */in Li t nse t_s （Sqli t * ,i t i,E emTye e） k;if（iLle h+） return RR R;if（L-length =L- listsize ）L- list （ lemType* ）re loc （L slis ,（ INIT_SIZE

6、+I CREM）*i eof（ lemType） ） ; f（!L-s i ） eturn E RO ; L-listsiz +=INCRE ;f r（ = - len th-1 ； k=i- ； k-） L-sli tk+1 = L slistk;L-sl st -1 e;L len t +; eturn OK;/* i tIns r */* 在顺序表中删除第 i 个元素 *nt ListDelete_sq（qli L,int i ）?if （ L-length =0） r tu 0;?if（i -leng ） etu n 0 ； for（i ;j ngth;j +）L-s istj-1=

7、-s stj;L- en th-;ern 1;/* 在顺序表中查找指定值元素，返回其序号*/in L s ocate（Sql s * ,El Typ e）f r（in i= ; L ength;i +）?i?f（L- li i-1=e） return ;?r? turn ;i t ain（）S lis sl; nt n,m,k ；printf（p ease input :） ； / 输入顺序表的元素个数 */ scanf（%d,& ）;if（n 0）prin （ n1- r ate qlist ： n ）;nitL st_sq （ sl） ；Cre teL t_s （&sl,n ） ;prin

8、tf （ n2-Print Sq is : n）;P ntLi t sq（&sl）;pr ntf（np ase i pu nsert l cti n an d ta:（loc ion, ta）n）;sc （%d, d ， &m,&k）；? ListI se _ q（&sl,m ， k）;? rintf（ n3-Print qlist ：n） ；Pr nt ist_ q（ l） ；printf （ nplease in u el te locat on: octi nn） ； canf（ %d， &m）;Lis D le e s（ sl ，） ;p tf（n4- i q is n） ；Prin

9、List_ q（& l） ； in f（ n e input d ta dat n）;s nf （ %d,&m ）； istLo （ &sl,m）;? rintf （ n5-Print qlistn）;P i List （&sl）;? r nf（n）;e seprint （ ERRO） ;r turn ;运行结果算法分析首先应该选择顺序表的动态存储方式进行顺序表结构的定义，然后在程序的开头进行顺序表各种操作函数的声明以及预定义命令, 接着编写各种操作函数的函数体，而 在主函数中要首先调用 Ini List_sq（& l） 函数初始化， 然后调用 i List q（） 创建顺序表 ,调用 rin

10、 Li t_sq（）函数输出该顺序表中元素的值； 然后调用 ListIns rt_s （）函数, 进行插入操作，并输出插入新元素后的状态。2、为第 1 题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。 删除算法代码：int Li telet sq（Sq st * ,i t i ）if （L- leng h=0） re r 0;?if （ iL-length）etur 0;?f r （ nt j ;j l ngth ；j +）L- sli t j-1=L-slist ；L-le g -;? ret rn 1;运行结果算法分析 当在主函数里面调用删除功能函数并传参数进去时 , 程序

11、将自动跳到函数体里面 利用所传参数一步步执行， 在该函数里面 , 当把顺序表和序号 i 传值进去时 , 程序可以先判断所传值是否满足条件，若满足 , 则开始从顺序表第一个元素开始依次遍历，直到找 到第个位置的元素，并将其删除，后面的元素依次前移 , 填补。而表的长度则减一删除成功。若不满足，则返回 0，表示删除失败。 查找算法代码：int Li tL cte（S list * ， lemTpe e） r （i =； lengt ; +） ?if （L slist i-1 ） eturn i ；? return 0; 运行结果算法分析当在主函数里面调用查找功能函数并传参数进去时, 程序将自动跳到

12、函数体里面, 利用所传参数一步步执行 , 在该函数里面 , 当把顺序表和要查找的值 e 传值进去时 程序开始从顺序表第一个元素开始依次遍历 ,直到找到值为 e 的元素 ,并返回其位置序e 的值 , 则返回 0，表示查号, 查找成功。若遍历了顺序表所有元素依然没有符合条件的 找失败。3、阅读下面程序 , 在横线处填写函数的基本功能。并运行程序,写出结果。#include #in lude #def n E ROR 0din K 1 lemTyp d a;struc Node* e ；LNod ， *Lik i t ；LinkLi tCreate i (int n)/vo P intLis ( L

13、i k t L); /*int e El m(LinkL st ,int i,Elem第 i 个节点的值LinkLi t Cr ateList( t n)Node p,*q, ead;in i;head=( i k ist) a loc(sizeof( ext=NULL ；p=h a ；typede n Ele Tp; * 定义表元素的类型 */ t pedef struct LNode / 线性表的单链表存储 * /*建 立 带 表 头 节 点 的 单 链 表输出带头结点单链表的所有元素 * ype *e） ； * 在单链表中查找 ode） ）；head- int */*o（ i= ; da

14、ta） qnet NULL ； p- next= ;pq; etu n ead ；/ r t L t*/ oi Pr ntL st（L nkListLN d p; (s z of(LNo e) ； p )； /* 输入元素值 */ 结点指针域置空 / 新结点连在表末尾）=Ln xt ； /* 指向单链表的第 1 个元素 */w il （p ！ NUL）pr ntf （%5d,p-data） p-n t;i,E yp *e)/*P in List*/n GetElem（LinkLis L，intL ode *p;it j= ;p- xt;while（p& n t;j+ if（!p|ji)r u

15、n RROR;*e=p-da a;r tunOK ； GtEle*/int ns rtList（Link i L,inti,E T pe e)int j 1 ； LN d p,*q;L- ext;wh l ( &jnext;j+;if（ !p） r tu n E ROR；q（ ode ） alloc（sieof（ e） ；q-data= ; q-next xt; p next q;r turn K;in De teList（ kLi t L,ElemT pe e） ? L o e *p, q; p=L-next;whil （ &-d ta!=e）? =p;p=p ne ; ? if （! ）

16、return E RO; ls nex return =p- e t;free(p) K; intmain ( ) i t ,i nkList L=in f(pElemTypULL;e se inpuan ( %d,&n);0)e； n:)* 定义指向单链表的指针 */* 输入单链表的元素个数 rintf( n1-C a Li k i t ： n ）； Cre teL st(n) ；printf( n2-P nti kLis:n );PrintList(L);printf ( n3 GetE m from Ln is ：n);r nt （input i= ）scanf(%,&i);if(Get

17、Elem( ,i,&e)rint（ o%i i%d ,i,）elsepr nt ( exis）;?prin f ( n -Ins trom inkList： ); * 调用插入函数/p i tf( put =) can （ d, i)； /* 指定插入位 if(n置* ? intf 素的值 */%d,输入欲插入元? InsertList (L,i ，); Prin s （ L）;/* 输出调用后的结果 */ rintf （n5-Dele e fro LinkL t:n)； /* 调用删除函数? printf(inpu e ） ; anf( %d,&e )；/* 输入欲删除元素的值*/ elet

18、 ist(L,e);Pin Lst ( L);/* 输出调用后的结果*/? p intf ( n）； e); /*npel=）； sc nfreturneri tf(ERR R);0；运行结果算法分析当在主函数里面调用查找功能函数并传参数进去时 , 程序将自动跳到函数体里面 , 利用所传参数一步步执行 , 在该函数里面，当把单链表，要插入的位置序号和元素内容 传值进去时， 程序开始从单链表第一个元素开始依次遍历， 直到找到插入位置的前一个 节点,用指针 p 指向它。然后创建一个以为值的新节点指针q,修改节点的 nxt域指向节点 p 的下一个节点 , 再将节点 *p 的 e t 域修改为指向新节点 * 。返回 ok, 表示插入成功。最后打印输出插入后的新链表。删除算法代码：int DeleteList（LinkLis L,E emTyp ）LNode *p,*q ； p=L-n t;? wil （&p-dt !=e）? =p; =p- ext;? if（!p） ret rn ER OR; l e? q-n xt=p-ne t;fr e（ ）;? r trn OK;运行结果算法分析当在主函数里面调用删除功能函数并传参数进去时 , 程序将自动跳到函数体里面， 利用所传参数一步步执行， 在该函数里面， 当把单链表， 要删除的元素内容传值进去时， 程序开始从单链表第一个元