当前位置:首页 >> 其它课程 >>

数据结构 第二次作业


i

2.9 简述以下算法的功能。

(1)Status A (LinkedList 链表 if (L&&L->next ;{ Q=L;L=L->next;P=L; while(P->next)

L){ //L 是无表头结点的单

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; }//BB void AA(LNode *pa,LNode *pb){ //pa 和 pb 分别指向单循环链表中的两个结点 BB(pa,pb); BB(pb,pa); }//AA 解: (1) :作用:将第一个结点插入到表尾,表长大于 2。 (2) :作用:删除 pa 与 pb 之间的结点,使 pa 的

i

直接前驱结点或者直接后继结点为 pb。 2.11 设顺序表 va 中的数据元素递增有序。 试写一算法, 将 x 插入到顺序表的适当位置上。 , 以保持该表的有序 性。 解:Status int InsertList(Sqlist i,j; *L, int x){

i=L->Length-1; while(i>=0&&x<=L->List[i]){ i--; if (L->Length>=L->ListSize) return (OVERFLOW) else{ i=L->Length-1; for(j=i;j>=i+1;j++) L->List[j+1]=L->List[j]; L->List[i+1]=x; L->Length++; } return } 2.12 设 A=(a1,......am)和 B=(b1,.......bn)均为顺序表, A’ 和 B’ 分别为 A 和 B 中去除最大共同前缀后的子表 (例 如: A=(x,y,y,z,x,z),B=(x,y,y,z,y,x,x,z), 则两者中的最大 共同前缀为(x,y,y,z),在两表中去除最大共同前缀后 的子表分别为 A’=(x,z)和 B’=(y,x,x,z)。 若 A’=B’=空表, OK;

i

则 A=B;若 A’=空表,而 B 不等于空表,或者两者均 不为空表, 且 A’首元小于 B’首元, 则 A<B;否则 A>B。 试写一个比较 A,B 大小的算法(请注意:在算法中, 不要破坏原表 A 和 B, 并且, 也不一定先求的 A’和 B’ 才进行比较。 ) 2.13 试写一算法,在带头结点的单链表结构上实现线 性表操作 Locate(L,X). 解:int LocateElem(LinkList { ListNode *p; else i=1; else } if } } 2.14 试写一算法,在带头结点的单链表结构上实现线 性操作 Length(L). (!p) return 0; int i; head ,DataType e)

if (head->next!=NULL) return 0; p=head->next; while(p){ { p=p->next;i++; if(p->data==e) return i;

i

解: int

ListLength(LinkList head){ P=h; while (p->next!=NULL){ p=p->next; i++;} return length;

ListNode *p; int length=0;

} 2.15 已知指针 ha 和 hb 分别指向两个单链表的表结 头,并且已知两个链表的长度为m ,n.试写一算法 将这两个链表连接在一起, (即令其中一个表的首元结 点连接在另一个表的最后一个结点之后) ,假设指针 hc 指向连接后的链表的头结点,并要求算法一短的时 间完成连接运算。请分析你的算法的时间复杂度。 解:ListLink(LinkList *ha,LinkList *hb,int ListNode *p,*pre,*hc; p=hb; pre=ha; for (i=1;i<=m;i++) { pre=pre->next; while ( pre->next!=NULL) p=pre->next; } hc=ha; return OK; } 2.17 试写一算法,在无头结点的动态单链表上实现线 性操作 Insert(L,i,b). 解:int InsertList(LinkList L,int i, DataType b){ int i; m){

i

ListNode *p,*pre; pre=L; j=0;

int j;

while(pre->next!=NULL&&j<i-1){ pre=pre->next; j++;} if(j!=i-1) return error; p=(ListNode*)malloc(sizeof(ListNode)); p->data=b; p->next=pre->next; pre->next=p; return } 2.18 同 2.17 题要求,实现线性表操作 Delete(L,i). 解: int DeleteList(LinkList L, int j; j=0; int i{ ListNode *p,*pre; Pre=L; LL&& j<i-1){ Pre=pre->next;j++; } if(j!=i-1)return error; P=pre->next;pre->next=p->next; Free(p);return OK; } 2.25 假设两个元素依值递增有序的排列的线性 表 A 和 B 分别表示两个集合 (即统一表中的元素值各 OK;

While(pre->next!=NULL&&pre->next->next!=NU

i

不相同) ,现要求另辟空间构成一个线性表 C,其元素 为 A 和 B 中元素的交集, ,且表 C 中的元素也依值递 增有序排列。试对顺序表编写求 C 的算法。 解: 2.42 是编写算法,将一个用循环链表表示的稀疏多 那个项式分解成两个多项式中各自仅含奇次项或偶次 项, 并要求利用原链表中的结点空间构成这两个链表。 解: voidSeparation(LinkedPoly&&plyn,LinkedPoly&&odd) {//plyn 为指向表示稀疏多项式的循环的循环链 //表头 结点的指针, odd 为新产生的仅含奇次链表的头 //指 针,运算后 plyn 链表中仅含偶次项。 odd=(LinkedPoly)malloc(sizeof(PolyNode)); odd->next=odd; 尾节点 while(p!=plyn){ if (p->next%2==0){ q=p; p=p->next;} else { q->next=p->next; //从原表中删去奇次项结点 p->next=s->next;s->next=p;//插入至新表中 //建立奇次项空表 q=plyn;p=plyn->next;s=odd;// 指向奇次项链表的

i

p=q->next;s=s->next; }//else }//while }//split


相关文章:
中大网院2017年上半年数据结构(C++)第二次作业
中大网院2017年上半年数据结构(C++)第二次作业_计算机软件及应用_IT/计算机_专业资料。2014 年上半年数据结构(C++)第二次作业一. 单项选择题(20 分) ( )1....
数据结构(第二次作业)
数据结构(第二次作业)_计算机软件及应用_IT/计算机_专业资料。数据结构(含课程设计)·第二次作业(第 6-12 章) 1. 二叉树以后序遍历序列与前序遍历序列反映的...
数据结构第二次作业
暂无评价|0人阅读|0次下载|举报文档 数据结构第二次作业_教育学_高等教育_教育专区。// 数据结构第二次作业.cpp : 定义控制台应用程序的入口点。 // #include...
2014年9月份考试数据结构第二次作业
2014年9月份考试数据结构第二次作业_政史地_高中教育_教育专区。2014 年 9 月份考试数据结构第二次作业 一、单项选择题(本大题共 100 分,共 40 小题,每小...
数据结构第二次作业
数据结构第二次作业答案 9页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 数据结构第二次作业 数据结构的一些基本...
数据结构第二次作业解答
数据结构第二次作业解答 隐藏>> 题目1 还未回答 满分 1.00 Flag question 题干 判定一个栈 ST(最多元素为 m0)为栈满的条件是() 选择一项: a. ST-〉top...
2017上半年数据结构C语言第二次作业
2017上半年数据结构C语言第二次作业_计算机软件及应用_IT/计算机_专业资料。互联网及其应用2017上半年第1次作业 中山大学 数据结构(C 语言)作业二一、 单选题(每...
西南交通大学数据结构第二次作业2014学年
西南交通大学数据结构第二次作业2014学年_其它_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档西南交通大学数据结构第二次作业2014学年_其它_高等教育_教育...
南京工业大学 数据结构 作业答案 作业2
第二次作业 1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用...首元素结点是指链表中存储线性表中第一个数据元素 a1 的结点。 3. 已知 P ...
数据结构的第二次上机实验作业
数据结构第二次上机实验作业_教育学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 数据结构第二次上机实验作业_教育学_高等教育_教育专区。数据结构...
更多相关标签: