專業(yè)課課件數(shù)據(jù)結(jié)構(gòu)第2章部分習(xí)題

本章主要內(nèi)容線性表的類型定義線性表的兩種存儲(chǔ)結(jié)構(gòu)的定義順序表和鏈表的各種操作的算法描述及其時(shí)間復(fù)雜度的分析有序表類型及有序表操作的實(shí)現(xiàn)順序表查詢插入刪除i=0;while(i<va.length&&va.elem[i]!=x)i++;for(j=va.length;j>=i;j--)va.elem[j]=va.elem[j-1];va.length++;for(j=i;j<va.length;j--)va.elem[j-1]=va.elem[j];va.length--;單鏈表查詢插入刪除p=ha->next;while(p!=NULL&&p->data!=x)p=p->next;s=newLNode;s->next=p->next;p->next=s;q=p->next;p->next=q->next;delete(q);j=1;

j<ip=ha;p->next;++j；雙向鏈表查詢插入刪除p=ha->next;while(p!=NULL&&p->data!=x)p=p->next;s=newLnode;s->next=p->next;p->next=s;q=p->next;p->next=q->next;delete(q);s->next-prior=s;s->prior=p;p->next->prior=p;有序表操作的特點(diǎn)1.查詢的結(jié)果同時(shí)得到插入的位置i=0;while(i<va.length&&va.elem[i]<x)i++;鏈表p=ha->next;while(p!=NULL&&

p->next->data<x)p=p->next;順序表2.所有操作必須考慮其“有序”的特點(diǎn)如何學(xué)會(huì)自己編寫(xiě)算法真正理解學(xué)過(guò)的算法利用現(xiàn)有算法的設(shè)計(jì)思想利用“圖解”分析算法設(shè)計(jì)的目標(biāo)StatusInsert_Sq(SqList&va,ElemTypex){

//已知順序表va中元素依值非遞減有序排列，本算法

//插入新的元素x并保持原表的有序性,返回OK;//若順序表空間已滿，則不再插入并返回OVERFLOW

if(va.length==va.listsize)returnOVERFLOW;

i=0;

while(i<va.length&&va.elem[i]<x)i++;

for(j=va.length;j>i;j--)va.elem[j]=va.elem[j-1];//右移所有值≧x的元素

va.elem[i]=x;va.length++;returnOK;}//Insert_Sq題2.11順序表查詢插入刪除i=0;while(i<va.length&&va.elem[i]!=x)i++;for(j=va.length;j>=i;j--)va.elem[j]=va.elem[j-1];va.length++;for(j=i;j<va.length;j--)va.elem[j-1]=va.elem[j];va.length--;題2.19刪除有序表中所有其值大于mink且小于maxk的數(shù)據(jù)元素。首先分析需要?jiǎng)h除的結(jié)點(diǎn)的特點(diǎn)：

<=mink

>=maxkpreqp修改指針:

pre->next=p;釋放結(jié)點(diǎn):while(q!=p){s=q->next;delete(q);q=s;}……voiddelete(LinkList&L,intmink,intmaxk){

while(p&&p->data<=mink)

{pre=p;p=p->next;}//查找第一個(gè)值>mink的結(jié)點(diǎn)p=L->next;

while(p&&p->data<maxk)

{q=p->next;deletep;p=q;}

//查找第一個(gè)值≥maxk的結(jié)點(diǎn) 釋放結(jié)點(diǎn)，修改指針pre=L;pre->next=p;}//delete對(duì)單鏈表進(jìn)行就地逆置a2ana1

a2ana1

設(shè)計(jì)目標(biāo):改變?yōu)閷⒒静僮魍澳嫘蚪▎捂湵怼保煌巸H在于，所有結(jié)點(diǎn)取自原鏈表。題2.22逆置線性鏈表a1a2a3

LLp

succa1

psucca2psucca3p基本操作：1）標(biāo)志后繼結(jié)點(diǎn)；2）修改指針（將*p插入在頭結(jié)點(diǎn)之后）；3）重置結(jié)點(diǎn)*p（p重新指向原表中后繼）；voidinverse(LinkList&L){//逆置帶頭結(jié)點(diǎn)的單鏈表

Lp=L->next;L->next=NULL;//建空表

while(p){s