计算机软件基础(二)实验指导书

《计算机软件基础(二)实验指导书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一线性表的插入与删除一、实验目的与要求使学生更进一步了解线性表在链接存储结构下插入与删除运算。二、实验任务1．创建带头指针的单链表2．查找指定位置的结点3.在查找到的指定位置上插入新元素4．在查找到的指定位置上删除结点三、实验指导1．创建带头指针的单链表算法：（1）置链表为空，即head=NULL；并置指针变量q为空，即q=NULL；（2）通过C语言提供的函数malloc(存储区字节数)，申请一个结点，使指针变量p指向它；（3）将数据（如数据10）赋值给p的数据域，将p的指针域置为空，并将指针head

2、和q指向该结点，（4）申请另一结点，同样使指针变量p指向该结点，对其数据域赋值，置指针域置为空；（5）将p插入在q指针所指结点之后，（6）指针q指向链表的最后一个结点，到此，在原来的链表中插入二个结点。 （7）重复执行（3）、（4）、（5）、（6）则可创建整个线性链表。链表创建函数如下：/*请注意LEN这一常量，在后面的算法函数还会用到*/structpointer*creat(){structpointer*p,*q,*head;intn;head=NULL；q=head;scanf(“%d”,&n);

3、while(n!=0)/*若输入的值不为0*/{p=(structpointer*)malloc(LEN);/*得到一个新的结点*/p->data=n;/*置数据域为输入的数值*/p->next=NULL;/*置指针域为空*/if(head==NULL)head=p;/*链表为空，头指针指向当前结点*/elseq->next=p;/*将当前结点链接到最后*/q=p;scanf(“%d”,&n);}return(head);}2．在指定元素后挤入新元素查找指定位置的结点按位置查找是线性表的一种常用运算，其功

4、能是对给定的链表查找表中第i个结点，并用一个指针变量指向该结点。算法的思想是：设一个计数变量n（初值为1），并设指针变量p指向链表的第一个结点。若计数变量n的值小于给定的参数i，则指针变量p后移（即指向下一个结点），且计数变量增一（计数变量n的值始终是指针变量p所指结点的序号）。故只需在每次执行“p后移”操作之前，增加一个判断条件，判断计数变量n是否小于给定的参数i。此条件若成立，说明尚未数到给定位置，应该继续往下“数”（即指针变量p后移，计数变量n增一），直到条件不成立（n的值与给定序号相同，即数到位了

5、，或给定的序号的值大于表中结点的总个数），则返回。查找指定位置结点的算法如下：structpointer*find_list(head,i)structpointer*head;inti;{structpointer*p;intn;p=head;n=1;while(p->next!=NULL&&nnext;}if(i==n)return(p);elsereturn(NULL);}3．在查找到的指定位置上插入新元素．在第i位置之前插入一个值为x的结点，其基本步骤如下：第一步：在单链

6、表上找到插入的位置，使得指针p指向第i-1个结点位置，这可用find_list算法实现，如图2-6；然后生成一个新结点，指针s指向该结点，并将数据x赋给其数据域。第二步：将新结点链入到指针p所指结点之后，其操作步骤为：(1)将结点*s的指针域指向结点*p的后继结点，语句为：s->next=p->next;(2)将结点*p的指针域的值改为指向新结点，语句为：p->next=s;至此，插入操作完成。算法如下：voidinsert(head,x,i)/*head为线性链表的头指针，x为待插入的数据，i为插入位置

7、*/structpointer*head;inti;datatypex;/*在头指针为head的线性链表的第i个位置上插入一个值为x的新结点*/{structpointer*s,*p;p=find_list(head,i-1);/*先找到第i-1个结点的位置，并让p指向该结点*/if(p!=NULL){s=(structpointer*)malloc(LEN);/*生成一个新结点*/s->data=x;/*将值x赋给新结点的数据域*/s->next=p->next;p->next=s;/*将新结点连接到指

8、针p所指结点之后（即第i个位置上）*/}elseprintf(“不存在第%d位置”,i);}4．在查找到的指定位置上删除结点删除链表中第i个结点的基本步骤如下：第一步：找到第i-1个结点，并使得指针p指向该结点。这一步可通过调用find_list算法实现。第二步：从链表上删除第i个结点，其操作如下(1)将指针q指向指针p所指结点的下一个结点，即第i个结点，使用语句：q=p->next;(2)将*q的指针域的值（*q的后继结