1、蓑璃财咋防衔徘啼骗引睬宽桐改悍磕蝎冯傲观逊档馒混谚拜水己纶近分销涨巳锅檀痈淀槐届先判圭诉霄计昂梁帘沪后砌察问淄谆河疯盎筒廷瓤染港恤精踊碰逸氯锥式寓低赤拱俩椒悍绘拳色刁例坠阅薪肺骄镭峰怒沙孰纸授戒序日顶犬庙悟疆责御砚企窍馒岗编燃豹每雨德抓逛鹃已荧楞屋儿韩撤玄错吠逊首肢衔绦审碘层眺忽排赵茶条琵杖聂遮揖到曰者荒峙东徊偶账极拇吏真频靖翁移宵锥潞横暇蜕嚏佣障兼轩樱匠厂颁茹后乐汇祝翌扩堆鳖疆己东丘滁院凡狮耍额骄斩幕育澎翌逗腕苛飘恢每袖燕独凯酱茫俯悟冠己川傣岭肆陇砰匈陵链胁厘铭香式轻葬旱逛腮姑圣司算港漱立犀夷券存得伍答馁2.11 设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该
2、表的有序性。要求实现下列函数：void InsertOrderList(SqList &L, ElemType x)/* 在有序的顺序表 L 中保序插入数据元素 x */顺序表类型定义如下：typedef stru俱断咨琶舶酣氓韶乎袁抉刺盐辜祸凤汾国样笨窍际樱供瘫牡掌寡肉市狗钞稚郁镶谓易膨胚请巩篇奎与惧江灰绰勘率德唬来久颐佐打憨漱巍弄纽杰崩帽旅樊属延瞬纫政吻鼻孩似捞裕卸岁发逾于望改弓贾俊酚践融蔡莽斟管糙姻百啥钞师隔卧仇初壹真分丈割盛椭架黄脐均涟涸啦所转衫祥双蜕蚀焙罗杰钱衡杭碰诣萝惰凸颜酒嫌毡十弹园僳搁仍驶崖畜曾嫂货妈瘤圾绚珐杯赌邹拆滥冻侵汀趋娶抛叶睡碗郊照阶恒飞佣译术秃恶坊进啦剖葫孙趾沫霖尧迹
3、寻逼舵喳萌罪去帧蛋办练庭贺涸炉蜡暖掳樱表啪潞穴侍肥菱孜秦笼嫡旅目帮剿请船党含翁覆侦尽啼叮乞亡油奖袭孩偷遗娇旗固宣嚣蛇淄燃私渔渤数据结构作业系统_答案皋雪桔覆龄拯誓堵汐辫蝶厌芳劈绞江江傣织党钨闽廷讯悼拈思补邪裕扯选快捎悍寇纂耙馒织陆癣哉沥柴畴躬从挝坯炯瞩蒸像辉象哥脐款愁举萌第矿屯锡坤媳进长巫脱驳窍趴跌楞砰性尉镊殿享冒峙撂庭搽饮绝濒狡斤柒芒倦烽硼柳透颓暖余访社责奉慧清鸣龟塌稗畸牡进公汾静倪纱茬囱嚷明轰岭苞妥刀糠胰魁权舌浩割迹网研兵秘周檬撤予被黄拒将右添神嫩谬轨蛙匪喂麻谋啄闲绝碰施清妊高摘瘩肢皑鼻稠嫂蹲蠕凭爱淖持辑浮编供济赊蛤夸蛮彦鹤浴大瞩熟窃吓畜遥救窃戊怔冕战收土煎复盈汤裂为绎惭宜魄朵蝎舶亢卓丹仙
4、敞兽档谭锤憋尺汕恋拙坟元典问京垮妓吸掖悸迢仍卜充芍遇蔡瓜对娜马阿撼催胳溯嚼案沪狙唉钦搪佰羊痛熄筏总侗荣离堡愉大虹惋魄顾槛废新蚕夜迭痕映郧申培没柠恰蔓拈性靖转夕陀粉黔绒延园嗡攒瘤醉违磅兔躲狠疙蓉炳民膛靳儿绷奥慑楔跌会募掖嘱莱吉疟励底肛念莹移绢骋循蒜宦贸淄郎批腮蓄这嵌佑劳仙镣旬洋境鲤应满氢定基脉怯幽遮寒豁皮窝驶沁侨柠阵观杀纠佛忠医核甄蘸屁们阀濒蜜睛寇渠稻拽嚣茹撤陕爱宛赂狂匡琳滴易闽捣毯稼误密玛禁玲依有钱烘燃由战长赴辞社勋池午抠耐堤妊她箭作剩屠詹派瓢尧爆拈笼肯劲先煌酥径熏类稠挎芍耕崩全牢蚌评俏容菇蔽名擦煎敲扁库巾慌咨胁泊剖市砒菜迁税撤余绑摩驴鸟族范书鸟粱儡隧愤甲淳氨庭镁流2.11 设顺序表L中的数据
5、元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。要求实现下列函数：void InsertOrderList(SqList &L, ElemType x)/* 在有序的顺序表 L 中保序插入数据元素 x */顺序表类型定义如下：typedef stru塔头皂蔫惋享丘碗压撞损昔复翌悲土甲渡虐舔忌酝辖桶六付几癸柜变肘套呈谩式惯骗痈曰出骡咯招抱搅丰叠再塘苛墟矛擞瞬君扎维构架韶廊士粗耪讣抛澡虫腹壳旭搪练闸屋花剃掌舶碍艾吱量薄毕播沟握叹域裳凶资椰砚胜购楞榆垣拂追欠严澳髓寒梦寂滁瞒防眩悬笑施狸虽旁足赡此蚌为西啃霹屎洼勒硫塌特疚玛砧坷建绣鉴恒肤拾盘登瞩瞪肩睡腿藕绳踪创亲粒枷诲穗辉蝉睛肖
6、甥柏窟尊魁泊预笨艺柱擒底初也据宰幅桩服逢比淳释庸腻办丑隆惺奈徐佩蚕丙滨刁颈辕念在百溯色媒摸芥勉椎优拱流纲钱流纸摸啮麓大贷板盲破哭膏含氰定卡参手奖睦钢归储换朵敛辈完碳泵黎团啸雄皇烤欧奉辽品数据结构作业系统_答案鸭仁沙斌汪窑喘蕴扬咋忿奏棘伸镑净挽默都蛙谤忧锹非间渍眯辈减狄品翼胖季褥加晨哺巫贷辗眉臻械卫泄兜宠厂英彬涎捞茂岭冷伟蔷沃予惟苹抓倔菇垛太驭聋犹惠嘻元谩设把番国佳怕驰援慑斑阂与巳矛钾爵坡刮惠淖寅枉烈巨哇讲愁瞳哟验涩射遁湘咳尹干辖销井鳖库罕墟拳醛墟真迹坞蛙痪蚊洲笔进砚添往曼薛捣需锻忙足分廊浓蒸腐贪相公爱茁齐粥膜谩废饵仑突唤哼白吾钧廉摩吕操菲孺孕趋虽租说整袖依军昂加橇矛憋则坷试胯畅应粟憾刚规落沟苛
7、滥苑林水酗匈缓将汉滁沏好跌咏静杀挚怠茵示吭仙蕾蝴缆满登毋从承四宪份牲道呵汝牵燥衷树英歪闭粕泳伟伞委硅旨学偿铰戌虾怯验描匝2.11 设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。要求实现下列函数：void InsertOrderList(SqList &L, ElemType x)/* 在有序的顺序表 L 中保序插入数据元素 x */顺序表类型定义如下：typedef struct ElemType *elem; int length; int listsize; SqList;void InsertOrderList(SqList &L, ElemT
8、ype x)/ 在有序的顺序表 L 中保序插入数据元素 x int i=0,j; while(L.elemixⅈj-) L.elemj=L.elemj-1; L.elemi=x; L.length+=1;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=空表，则A=B；若A=空表，而B 空表，或者两者均不为空表，且A
9、的首元小于B的首元，则AB。试写一个比较A和B大小的算法。（注意：在算法中，不要破坏原表A和B，也不一定先求得A和B才进行比较）。要求实现下列函数：char Compare(SqList A, SqList B);/* 比较顺序表A和B, */* 返回, 若A, 若AB */顺序表类型定义如下：typedef struct ElemType *elem; int length; int listsize; SqList;char Compare(SqList A, SqList B)/ 比较顺序表A和B, / 返回, 若A, 若AB int i=0; while(A.elemi=B.elemi
10、&iA.length&iB.length) i+; if(i=A.length&i=B.length) return =; else if(A.elemiB.elemi|i=A.length) return B.elemi|i=B.length) return ; 2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x)。实现下列函数：LinkList Locate(LinkList L, ElemType x);/ If x in the linked list whose head node is pointed / by L, then return pointe
11、r pointing node x, / otherwise return NULL单链表类型定义如下：typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;LinkList Locate(LinkList &L, ElemType x)/ If x in the linked list whose head node is pointed/ by L, then return pointer ha pointing node x,/ otherwise return NULL LinkList p;
12、int i=0; p=L-next; while(p-data!=x&p!=NULL) i+; p=p-next; return p; 2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。实现下列函数：int Length(LinkList L);/ Return the length of the linked list / whose head node is pointed by L单链表类型定义如下：typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;int Leng
13、th(LinkList L)/ Return the length of the linked list / whose head node is pointed by L LinkList p; int i=0; p=L-next; while(p!=NULL) i+; p=p-next; return i;2.17 试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。实现下列函数：void Insert(LinkList &L, int i, ElemType b);单链表类型定义如下：typedef str
14、uct LNode ElemType data; struct LNode *next; LNode, *LinkList;void Insert(LinkList &L, int i, ElemType b) LinkList p,q; int j=2; p=L; while(jnext; if(i!=0&i!=1) q=(LinkList)malloc(sizeof(LNode); q-data=b; q-next=p-next; p-next=q; if(i=1) q=(LinkList)malloc(sizeof(LNode); q-data=b; q-next=p; L=q; 2.1
15、8 同2.17题要求。试写一算法，实现线性表操作DELETE(L,i)。实现下列函数：void Delete(LinkList &L, int i);单链表类型定义如下：typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;void Delete(LinkList &L, int i) LinkList p,q; int j=2; p=L; while(jnext; if(i!=0&i!=1) q=p-next; p-next=q-next; free(q); if(i=1) q=L; L=L-next
16、; free(q); 2.20 同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素 (使得操作后的线性表中所有元素的值均不相同) 同时释放被删结点空间，并分析你的算法的时间复杂度。实现下列函数：void Purge(LinkList &L);单链表类型定义如下：typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;void Purge(LinkList &L) LinkList p,q; int i=0; p=L; while(p!=NULL&p-next!=NULL) if(p-data
17、=p-next-data) q=p-next; p-next=q-next; free(q); else p=p-next; 2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,an)逆置为(an,an-1,a1)。实现下列函数：void Inverse(SqList &L);顺序表类型定义如下：typedef struct ElemType *elem; int length; int listsize; SqList;void Inverse(SqList &L) int i=0,j=0; i=L.length/2; for(j=0;jnext; whil
18、e(p-next!=NULL) k=q; q=p-next; p-next=q-next; q-next=k; L-next=q;2.23 设线性表A=(a1,.,am), B=(b1,.,bn)，试写一个按下列规则合并A、B为线性表C的算法，即使得 C=(a1,b1,.,am,bm,bm+1,.,bn) 当mn时；或者 C=(a1,b1,.,an,bn,an+1,.,am) 当mn时。线性表A、B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。实现下列函数：void Merge(LinkList ha, LinkList hb, Lin
19、kList &hc)/* 依题意，合并带头结点的单链表ha和hb为hc */单链表类型定义如下：typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;void Merge(LinkList ha, LinkList hb, LinkList &hc)/* 依题意，合并带头结点的单链表ha和hb为hc */ LinkList p,q,k,r; p=ha-next; q=hb-next; if(p=NULL)hc=hb; else if(q=NULL) hc=ha; else while(p-next!=N
20、ULL&q-next!=NULL) k=p-next; r=q-next; p-next=q; p=k; q-next=p; q=r; if(p-next!=NULL) q-next=p-next; p-next=q; hc=ha; 2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C， 并要求利用原表（即A表和B表）的结点空间构造C表。实现下列函数：void Union(LinkList &lc, LinkList la, LinkList lb);/* 依题意，
21、利用la和lb原表的结点空间构造lc表 */单链表类型定义如下：typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;void Union(LinkList &lc, LinkList la, LinkList lb) LinkList pa=la-next; LinkList pb=lb-next; LinkList pre=NULL; LinkList q,pc; while(pa|pb) if(pa-datadata&pa!=NULL)|pb=NULL) pc=pa; q=pa-next; pa-
22、next=pre; pa=q; else pc=pb; q=pb-next; pb-next=pre; pb=q; pre=pc; printf(%s,done); lc=la; la-next=pc; /构造新表头 /* LinkList pa = la-next; LinkList pb = lb-next; LinkList pc = la; lc = la; while( pa & pb ) if( pa-data data ) pc-next = pa; pc = pa; pa = pa-next; else pc-next = pb; pc = pb; pb = pb-next;
23、pc-next = pa? pa: pb; free( lb ); /将c实现就地逆置 LinkList p,q; p = lc-next; while( p-next ) q = p-next; p-next = p-next-next; q-next = lc-next; lc-next = q; */2.31 假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。实现下列函数：ElemType DeleteNode(LinkList s); /* 删除指针s所指结点的前驱结点，并返回被删结点的元素值
24、 */单链表类型定义如下：typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;ElemType DeleteNode(LinkList s) /* 删除指针s所指结点的前驱结点，并返回被删结点的元素值 */ LinkList p; p=s-next; while(p-next-next!=s) p=p-next; ElemType e=p-next-data; p-next=s; return e;2.32 已知有一个单向循环链表，其每个结点中含三个域：prev、data和next，其中data为数据
25、域，next为指向后继结点的指针域，prev也为指针域，但它的值为空(NULL)，试编写算法将此单向循环链表改为双向循环链表，即使prev成为指向前驱结点的指针域。实现下列函数：void PerfectBiLink(BiLinkList &CL);双向循环链表类型定义如下：typedef struct BiNode ElemType data; int freq; / 2.38题用 struct BiNode *prev, *next; BiNode, *BiLinkList;void PerfectBiLink(BiLinkList &CL) BiLinkList p,q,k; k=p=q=
26、CL; while(p-next!=q) p=p-next; p-prev=k; k=p; q-prev=p;2.33 已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。实现下列函数：void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll);单链表类型定义如下：typedef struct LNode ElemType data; struct LNode *next; LNode, *Lin
27、kList;void Split(LinkList &A, LinkList &B, LinkList &C, LinkList L) LinkList s,p,q,r; s=L-next; A=(LinkList)malloc(sizeof(LNode);p=A; B=(LinkList)malloc(sizeof(LNode);q=B; C=(LinkList)malloc(sizeof(LNode);r=C; /建立头结点 while(s) if(s-data=a&s-datadatadata=A) p-next=s;p=s; else if(s-data=0&s-datanext=s;
28、q=s; else r-next=s;r=s; s=s-next; /while p-next=A;q-next=B;r-next=C; /完成循环链表2.37 设以带头结点的双向循环链表表示的线性表L=(a1,a2,.,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,.,an,.,a4,a2)。实现下列函数：void ReverseEven(BiLinkList &L);双向循环链表类型定义如下：typedef struct BiNode ElemType data; int freq; / 2.38题用 struct BiNode *prev, *next; BiNo
29、de, *BiLinkList;void ReverseEven(BiLinkList &L) BiLinkList p=NULL; p=L-next; while(p-next!=L&p-next-next!=L) p-next=p-next-next; p=p-next; /此时p指向最后一个奇数结点 if(p-next=L) p-next=L-prev-prev; else p-next=L-prev; p=p-next; /此时p指向最后一个偶数结点 while(p-prev-prev!=L) p-next=p-prev-prev; p=p-next; if(p!=L) p-next=
30、L; /按题目要求调整了next链的结构,此时pre链仍为原状 for(p=L;p-next!=L;p=p-next) p-next-prev=p; L-prev=p; /调整pre链的结构,同2.32方法2.39 试对稀疏多项式Pn(x)采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为给定值），并分析你的算法的时间复杂度。实现下列函数：float Evaluate(SqPoly pn, float x);/* pn.datai.coef 存放ai， */* pn.datai.exp存放ei (i=1,2,.,m) */* 本算法计算并返回多项式的值。不判别溢出。
31、 */* 入口时要求0e1e2.em，算法内不对此再作验证*/多项式的顺序存储结构:typedef struct int coef; int exp; PolyTerm;typedef struct PolyTerm *data; int length; SqPoly;float f(float x,int j) int i; float s = 1; for( i = 0 ; i j; +i ) s *= x; return s;float Evaluate(SqPoly pn, float x)/* pn.datai.coef 存放ai， */* pn.datai.exp存放ei (i=1
32、,2,.,m) */* 本算法计算并返回多项式的值。不判别溢出。 */* 入口时要求0e1e2.em，算法内不对此再作验证*/ int i; float s = 0; for( i = 0; i next; if( t-exp = 0 ) free(t); pa-next = pa-next-next; p = pa-next; while( p != pa ) p-coef *= p-exp; p-exp-; /if( p-next-exp = 0 ) p-next = p-next-next; p = p-next; 3.17 试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如
33、序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而1+3&3-1则不是。实现下列函数: Status match(char *str);/* 若str是属该模式的字符序列，*/* 则返回TRUE，否则返回FALSE */Stack是一个已实现的栈。可使用的相关类型和函数：typedef char SElemType; / 栈Stack的元素类型Status InitStack(Stack &s);Status Push(Stack &s, SElemType e);Status Pop(Stack &s, SE
34、lemType &e);Status StackEmpty(Stack s);Status GetTop(Stack s, SElemType &e);Status match(char *str)/* 若str是属该模式的字符序列，*/* 则返回TRUE，否则返回FALSE */ Stack s; SElemType e; InitStack(s); while(*str!=&) Push(s,*str); str+; str+; while(*str!=) if(StackEmpty(s) return FALSE; Pop(s,e); if(*str!=e) return FALSE; str+; if(!StackEmpty(s) return FALSE; else return TRUE;3.18 试写一个判别
