数据结构作业-线性表2

数据结构作业-线性表2

ID:11268893

大小:41.00 KB

页数:6页

时间:2018-07-11

数据结构作业-线性表2_第1页
数据结构作业-线性表2_第2页
数据结构作业-线性表2_第3页
数据结构作业-线性表2_第4页
数据结构作业-线性表2_第5页
资源描述:

《数据结构作业-线性表2》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、1 简述以下算法的功能:(1)Status A(LinkedList L)   {//L是无表头结点的单链表      if(L&&L->next){       Q=L;L=L->next;P=L;       While(P->next)P=P->next;P->next=Q;Q->next=NULL;}return OK;}//A(2)void BB(LNode*s,LNode*q) {       p=s;       While(p->next!=q) p=p->next;       p->next=s;       }//BBVoid AA(LNode*pa,LNo

2、de*pb) {       //pa和pb分别指向单循环链表中的两个节点       BB(pa,pb);       BB(pb,pa);       }//AA2 指出以下算法中的错误和低效(既费时)之处,并将它改写为一个即正确又高效的算法。Status DeleteK(SqList&a,int i,int k){//本过程从顺序存储结构的线性表a中删除第i个元素起的K个元素If (i<1

3、

4、k<0

5、

6、i+k>a.length) return  INFEASIBLE; //参数不合法else{   for(count=1;count 

7、除一个元素     For(j=a.length;j>=i+1;j- -) a.elem[j- 1]=a.elem[j];a.length- -;}Return OK;}//DeleteK下列算法设计题涉及的顺序表和线性链表的类型定义如下:#defineLIST_INIT_SIZE100#defineLISTINCREMENT10Typedefstruct{ElemType*elem;//存储空间基址intlength;//当前的长度intlistsize;//当前分配的存储容量}SqList;//顺序表类型TypedefstructLNode{ElemTypedata;stru

8、ctLNode*next;}LNode,*LinkList;//线性链表类型2.11设顺序表va中的数据元素递增有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。2.13试写一算法在带头结点的单链表结构上实现线性表操作LOCATE(L,X)。2.14试写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)。2.15已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后),假设指针hc指向连接后的链表头结点,并要求算法以尽可能短的时间完成连

9、接运算。请分析你的算法的时间复杂度。2.17试写一算法,在无头结点的动态单链表结构上实现线性表操作INSERT(L,i,b),并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.18试写一算法,在无头结点的动态单链表结构上实现线性表操作DELETE(L,i),并和在带头结点的动态单链表上实现相同操作的算法进行比较。2.19已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效算法,删除表中所有值大于maxk的元素(若表中存在这样的元素)同时释放被删结点空间,并分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,

10、也可以不同)。2.21试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。2.22试写一算法,对单链表实现就地逆置。参考答案2.10StatusDeleteK(SqList&a,inti,intk)//删除线性表a中第i个元素起的k个元素{  if(i<1

11、

12、k<0

13、

14、i+k-1>a.length)returnINFEASIBLE;  for(count=1;i+count-1<=a.length-k;count++)//注意循环结束的条件    a.elem[i+count-1]=a.elem[i+count

15、+k-1];  a.length-=k;  returnOK;}//DeleteK2.11StatusInsert_SqList(SqList&va,intx)//把x插入递增有序表va中{  if(va.length+1>va.listsize)returnERROR;  va.length++;  for(i=va.length-1;va.elem[i]>x&&i>=0;i--)    va.elem[i+1]=va.elem[i];  va.elem[i+1]=x;  re

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。