欢迎来到天天文库
浏览记录
ID:44100726
大小:524.48 KB
页数:9页
时间:2019-10-18
《数据结构之线性表和栈和队列》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、一.顺序表:1•在第i个位置插入一个新元素算法思想:分析:即在第i-1个元素和第i个元素之间插入插入的步骤:将第i个元素之后的所有元素后移;将新的元素放置在第i个位置2•删除线性表中的第i个元素:分析:即把第i个元素之后的所有元素往前移,也就是第i+1个元素覆盖掉第i个元素,之后的元素前移如图:*在一个长度为n的顺序表(顺序存储的线性表)中,向第i个元素(1〈二i〈二n+1)之前插入一个新元素时,需后移个元素。A.n~iB.n-i+1C.n-i~1D.i答案:B二.链表:1.线性链表:①在第i个节点之前插入一个元素e:建立一
2、个新的节点p,用来存储要插入数据的信息,然后找到位置iT,判断能否找到情况。插入过程如图:首先年丸审朝軽::禺1I)>、、*今1一?听「/~»—'Ta/AF-^lED%Tnat=了②删除位置i处的元素:首先查找位置i,判断能否找到。删除过程为,先找到iT处节点p,然后将节点p与位置i后的节点相连接。如图:有关链表例题:*将两个有序链表归并为一个新的有序链表。分析:La“口、、、T区/刃iJlEJ11J—)}—>13_L/~刀a【卜^-、通过比较,Pb->data(5)比Pa->data(4)大,Pa、P后移;然后比较:pb
3、->data(5)比p->data(4)大,pb->data(5)比pa->data(6)小。此时,把5插入到4和6之间,在插入之前,需先用一个指针指向5,如果没有指向,直接把5插入到4和6之间,则会找不到Lb中的其他元素。过程如图:、、、//iT[D--^^n-^LnzH、“一iKB」p/•F片二I"I刁X("、七乍"Ext二Q;片亦咸二■.Y-t;.2•循环链表②:判断空表:H->next=H3.双向链表:在第i个节点插入新元素e。首先找到第i个节点:while(p&&jnext;++j;}插入过程如图
4、:02/1沁-p;②Spiw=prior;③pnorT/iext二S;S)pTpyi"二S;篡中®@顺舟不能真瀚・#三、栈和队列例题:1.栈的插入和删除在进行。A.栈顶B.栈底C.任意位置D•指定位置2•将整数1、2、3、4、5依次进栈,最后都出栈,出栈可以在任何时刻(只要栈不空)进行,则出栈序列不可能是OA.23415B.54132C.23145D.154323•在一个链队列中,若f,s分别为队首、队尾指针,则插入s所指节点的操作为OA.f->next二s;仁s;B.r->next=s;r=s;C.S->next=r;r二
5、s;D.s~>next=f;f=s;3.最大容量为n的循环队列,约定队尾指针是rear,指向队尾元素的下一个位置;队头指针指向队头元素,则队满的条件是OA.(rear+1)%n=frontB.rear二frontC.rear+1=frontA.(rear-1)%n=front答案:1.A2.B3.B4.A
此文档下载收益归作者所有