资源描述:
《软件技术基础实验指导书6》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、软件技术基础实验指导书主编:张志文易茗卢小勇2006年3月改编实验一线性表的基本运算一、实验目的:(1)理解线性表的基本概念、特点和抽象数据类型。(2)创建链式存储结构线性表,实现查找、插入、删除等算法。(3)实现链式存储结构线性表的遍历算法。二、实验内容:(1)用C语言编制单链表的初始化程序及主程序。(2)按尾接法创建单链表,单链表中含5个数据元索:'a','b','c',Q,匕',编制相应的函数。(3)编制查找、插入、删除等算法的函数。(4)编制链式存储结构线性表的遍历算法函数。(5)单步调试程序
2、:按Ctrl+F7键,在打开的窗口中输入观察变量,如观察p结点指针域的值输入:p->nexto按F7键,单步执行程序,纪录单链表在创建、插入、删除等操作时各结点的数据域及指针域的内容,填入以下各表:创建链表:插入元索:节点序号数据域指针域节点序号数据域指针域112233445566删除元素:查找元素:节点序号数据域指针域节点序号数据域指针域1122334455三、实验步骤:(1)编辑源程序,程序名为DLBCL、CPP:/*************DLBCLCPP************//*单链表数据
3、结构处理*/#include(stdio.h)#include(stdlib.h)/*定义数据域的数据类型*/typedefstructstudent/*定义一个与structstudent同类型的变量elemtype*/{charname:}elemtype;/*定义单链表的数据元素,数据元素为抽象数据类型*/structnodetypeelemtypedata;/*数据域structnodetypenext;/指针域*/};/*建立一个空表,初始化链表头结点*/intinitl(structnod
4、etype**head){head=(structnodetype)malloc(sizeof(structnodetype));/*给头结点分配一个内存空间*//*并将头结点指针指向该地址*/讦(*head==NULL)return0;(*head)->next=NULL;return1;/*若不成功,则返冋0*//*将头结点的指针域初始化为*//*成功,返冋*//*以尾接法方式创建链表*/intcreatLl(structnodetype**head,elemtypea[],intn)struct
5、nodetype*p,*s;intj;讦(initl(head)==O)return0;p=*head;for(j=0;j<=n-l;++j)/*初始化链表头结点*//*指针P指向链表头*//*n个结点,从0到n・l*/if((s=(structnodetype*)malloc(sizeof(structnodetype)))==NULL)retum0;s->data=a[j];s->next=NELL;p->next=s;p=s;/*为当前结点分配一个内存空间,并以s指向之*//*当前结点数据域赋*
6、//*当前结点指针域置为空*//*使P结点指针域指向当前结点*//*调整P使之指向当前结点*/return1;/*在链表中搜索x元素*/nodetype*searchL(structnodetype*head,elemtypex){structnodetype*p;p=head->next;/*p指向头结点指针域指向的位置*/while(p!=NULL&&p->data.name!=x.name)/*如果p结点不为空或其数拯域不与搜*//*索x元素的数据域相等,则继续查找*/p=p->next;/*p
7、扌旨向p结点指针域指向的位置,即下一个结点*/if(p!=NULL)printf(”%c",p=>data.name);ruturnp;}/*在链表中y元素前插入x元素*/intinsertL(structnodetype*head,elemtypex,elemtypey)structnodetype*p,*q,*s;q=head;p=head->next;while(p!=NULL&&p->data.name!=y.name)/*先找到y元素所在位置*/q=p;/*q,p指针后移*/p=p->n
8、ext;}/*循环结束后,q指向y元素结点或最后一个结点,p指向y元素后一个结点或为NULL*/if((s=(structnodetype*)malloc(sizeof(structnodetype)))==NULL)return0;s->data=x;/*给新结点赋数据*/s-next=p;/*新结点指向P*/q・>next=s;return1;/*q结点指向新结点*//*删除链表中X元素*/intdeleteL(structnodetype*head