數(shù)據(jù)結(jié)構(gòu)主講人：米曉紅hongxiaomi@163.com

線性表習(xí)題課1)在非空的線性表，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a1，它沒(méi)有直接前趨，而僅有一個(gè)直接后繼a22)有且僅有一個(gè)終端結(jié)點(diǎn)an，它沒(méi)有直接后繼，而僅有一個(gè)直接前趨an-1；3)其余的內(nèi)部結(jié)點(diǎn)ai(2in-1)都有且僅有一個(gè)直接前趨ai-1和一個(gè)直接后繼ai+1。1、線性表的邏輯特征：一、要點(diǎn)回顧d1d2d3d4d5d6d72、線性表的順序表示和實(shí)現(xiàn)#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;

}Sqlist;（1）存儲(chǔ)結(jié)構(gòu)的定義（2）操作的實(shí)現(xiàn)StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//

在順序表L的第i個(gè)元素之前插入新的元素eIf(i<1||i>L.Length+1)returnERROR;if(L.length>=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;

}q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;++L.length;//表長(zhǎng)增1return

OK;}//ListInsert_SqStatusListDelete_sq(Sqlist&L，inti，ElemType&e){//在順序線性表L中刪除第i個(gè)元素，并用e返回其值

if(i<1||i>L.length)returnERROR;p=&(L.Elem[i-1]);//p指示刪除位置e=*p;q=L.elem+L.length-1;//q指示表尾位置for(++p；p<=q；++p)*(p-1)=*p;//刪除位置之后元素前移L.length--;//表長(zhǎng)減1returnOK;}//ListDelete_sqStatusLocateElem_sq(SqListL,ElemTypee){//在順序表中查找第一個(gè)值為e的元素的位序

i=1;p=L.elem;while(i<=L.length&&（*p++!=e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_sq3、線性表的單鏈表存儲(chǔ)結(jié)構(gòu)typedefstructLNode{Elemtypedata;structLNode*next;}Lnode,*LinkList;（1）存儲(chǔ)結(jié)構(gòu)的定義（2）操作的實(shí)現(xiàn)StatusGetElem_L(LinkListL,inti,ElemType&e){//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針//取第i個(gè)元素

p=L->next;j=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;

e=p->data;returnOK;}//GetElem_LStatusListInsert_L(LinkList&L,inti,ElemTypee){//在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置之前插入元素e

p=L;j=0;while(p&&j<i-1){p=p->next;++j;}//尋找第i-1個(gè)結(jié)點(diǎn)if(!p||j>i-1)return

ERROR;

s=(LinkList)malloc(sizeof(Lnode));s->data=e;s->next=p->next;p->next=s;returnOK;}//ListInsert_LStatusListDelete_L(LinkList&L,inti,ElemType&e){//在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第i個(gè)元素，并用e返回p=L;j=0;while(p->next&&j<i-1){//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū)

p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;

q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}//ListDelete_L

voidCreateList_L(LinkList&L,intn){//逆位序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表

L=(LinkList)malloc(sizeof)(LNode));L->next=NULL;for(i=n;i>0;i--){p=(LinkList)malloc(sizeof)(LNode));scanf(&p->data);p->next=L->next;L->next=p;

}}//CreatList_LStatusInsert_SqList(SqList&va,intx)//把x插入遞增有序表va中

{

if(va.length==va.listsize)return(OVERFLOW);

for(i=va.length-1;va.elem[i]>x&&i>=0;i--)

va.elem[i+1]=va.elem[i];

va.elem[i+1]=x;

va.length++;

returnOK;

}//Insert_SqList2.11設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試編寫(xiě)一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。二、作業(yè)點(diǎn)評(píng)2.14試寫(xiě)一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作LENGTH(L）。intLength(LinkListL)//求鏈表的長(zhǎng)度{p=L->next;k=0;while(p){p=p->next;k++;}returnk;}

2.19已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫(xiě)一高效的算法，刪除表中所有值大于mink且小于maxk的元素（若表中存在這樣的元素）同時(shí)釋放被刪結(jié)點(diǎn)空間，并分析算法時(shí)間復(fù)雜度（mink和maxk是給定參變量）StatusDelete_Between(Linklist&L,intmink,intmaxk){//刪除遞增鏈表L中值大于mink且小于maxk的所有元素if(L!=NULL){q=L;p=L->next;}while(p!=NULL&&p->data<=mink){q=p;p=p->next;}while(p!=NULL&&p->data<maxk){r=p;p=p->next;free(r);}q->next=p;returnOK;}//Delete_Between三、習(xí)題講解例1、已知線性表中元素?zé)o序，且采用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)結(jié)構(gòu)，要求刪除所有大于min且小于max的結(jié)點(diǎn)。StatusDelete_Between(Linklist&L,intmink,intmaxk){//刪除無(wú)序單鏈表中所有大于min且小于max的結(jié)點(diǎn)q=head;p=q->next;while(p){if(p->data<=mink||p->data>=maxk){q=p;p=p->next;}else{q-next=p->next;free(p);}p=q->next;}returnOK;}//Delete_Between例2、有一單鏈表（不帶頭結(jié)點(diǎn)）頭指針為head，試設(shè)計(jì)一算法使得單鏈表插入x后仍遞增有序。StatusInsert(Linklist&head,Elemtypex){//不帶頭結(jié)點(diǎn)單鏈表插入x后仍遞增有序s=(LinkList)malloc(sizeof(Lnode));s->data=x;s->next=NULL;if(head=NULL||x<head->data){s->next=head;head=s;}else{q=head;p=head->next;while(p!=NULL&&p->data<x){q=p;p=p->next;}s->next=p;q->next=s;}returnOK;}//InsertStatusInsert(Linklist&head,Elemtypex){//帶頭結(jié)點(diǎn)單鏈表插入x后仍遞增有序s=(LinkList)malloc(sizeof(Lnode));s->data=x;s->next=NULL;q=head;p=head->next;if(p!=NULL&&p->data<x){q=p;p=p->next;}s->next=p;q->next=s;returnOK;}//Insert例3、試分別以不同的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆轉(zhuǎn)算法，即在原表的存儲(chǔ)空間內(nèi)將線性表（a1,a2,...,an）逆置為（an,an-1,...,a1）。

（1）順序存儲(chǔ)結(jié)構(gòu)//結(jié)構(gòu)類(lèi)型定義：

#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;

}Sqlist;

//算法voidreverse(SqList&L){//順序表的就地逆置

for(i=1,j=L.length-1;i<j;i++,j--)

{

temp=L.elem[i];L.elem[i]=L.elem[j];L.elem[j]=temp;}//reverse（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)—單鏈表//結(jié)構(gòu)類(lèi)型定義：typedefstructLNode{Elemtypedata;structLNode*next;}Lnode,*LinkList;void

convert(linklist

head){

//帶頭結(jié)點(diǎn)的單鏈表head就地逆置

LNode

*p,

*q;

p=head->next;

//指向開(kāi)始結(jié)點(diǎn)

head->next=NULL;

//逆置后初表為空

while(p)

//p為NULL，表示已經(jīng)全部逆置

{q=p->next;

//p指向下一個(gè)需要逆置的結(jié)點(diǎn)

p->next=head->next;

//將需要逆置結(jié)點(diǎn)插入頭結(jié)點(diǎn)后面

head->next=p;p=q;}returnOK;

}//convert