第七章線性表7.1線性表的基本概念及運(yùn)算線性表是計算機(jī)程序設(shè)計中最常遇到的一種操作對象，也是數(shù)據(jù)結(jié)構(gòu)中最簡單、最重要的結(jié)構(gòu)形式之一。實際上，線性表結(jié)構(gòu)在程序設(shè)計中大量使用，它對我們來說并不是一個陌生的概念。在這一章里，我們將從一個新的角度來更加系統(tǒng)地討論它。7.1線性表的基本概念及運(yùn)算7.1.1線性表的邏輯結(jié)構(gòu)定義學(xué)生成績登記表

線性表是由n（n≥0）個數(shù)據(jù)元素a1,a2,…,an構(gòu)成的有限序列。其中，將數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，通常將非空的線性表（n>0）記作：（a1,a2,…,an）。7.1線性表的基本概念及運(yùn)算7.1.2線性表的運(yùn)算1.置空表SETNULL(L)2.求長度LENGTH(L)3.取結(jié)點(diǎn)GET(L,i)4.定位LOCATE(L,x)5.插入INSERT(L,x,i)6.刪除DELETE(L,i)7.取直接前趨PRIOR(L,ai)8.取直接后繼NEXT(L,ai)7.1線性表的基本概念及運(yùn)算7.1.2線性表的運(yùn)算[例7.1]利用線性表的基本運(yùn)算清除表Ｌ中多余的重復(fù)結(jié)點(diǎn)。7.1線性表的基本概念及運(yùn)算7.1.2線性表的運(yùn)算PURGE(L) /*刪除線性表Ｌ中重復(fù)出現(xiàn)的多余結(jié)點(diǎn)*/Linear_list*L; {inti=1,j,x,y; while(i<LENGTH(L))/*每次循環(huán)使當(dāng)前第i個結(jié)點(diǎn)是無重復(fù)值的結(jié)點(diǎn)*/{x=GET(L,i);/*取當(dāng)前第i個結(jié)點(diǎn)*/j=i+1;while(j<=LENGTH(L)){y=GET(L,j); /*取當(dāng)前第j個結(jié)點(diǎn)*/if(x==y)DELETE(L,j); /*刪除當(dāng)前第j個結(jié)點(diǎn)*/elsej++;}i++;}} /*PURGE*/7.2線性表的順序存儲結(jié)構(gòu)7.2.1順序表Loc?(ai+1)=Loc?(ai)+cLoc?(ai)=Loc?(a1)+(i

1)

c1≤i≤n7.2線性表的順序存儲結(jié)構(gòu)7.2.2順序表的基本運(yùn)算1．插入運(yùn)算2.刪除運(yùn)算7.2線性表的順序存儲結(jié)構(gòu)7.2.2順序表的基本運(yùn)算1．插入運(yùn)算我們在線性表的第i?(1≤i≤n+1)個位置上，插入一個

新結(jié)點(diǎn)x，使長度為n的線性表

（a1,…,ai

1,ai,…,an）變成長度為n+1的線性表

（a1,…,ai

1,x,ai,…,an）7.2線性表的順序存儲結(jié)構(gòu)7.2.2順序表的基本運(yùn)算1．插入運(yùn)算7.2線性表的順序存儲結(jié)構(gòu)7.2.2順序表的基本運(yùn)算2．刪除運(yùn)算線性表的刪除運(yùn)算是指將表的第i（1≤i≤n）個結(jié)點(diǎn)

刪去，使長度為n的線性表

（a1,…,ai

1,ai,ai+1,…,an）變成長度為n

1的線性表

（a1,…,ai

1,ai+1,…,an）7.2線性表的順序存儲結(jié)構(gòu)7.2.2順序表的基本運(yùn)算2．刪除運(yùn)算7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)上一節(jié)研究了線性表的順序存儲結(jié)構(gòu)，它的特點(diǎn)是邏輯關(guān)系上相鄰的兩個元素在物理位置上也相鄰。這一特點(diǎn)使得順序表具有如下的優(yōu)缺點(diǎn)，其優(yōu)點(diǎn)是：可以隨機(jī)存取表中任意元素；其存儲位置可用一個簡單直觀的公式來表示。然而，這一特點(diǎn)也鑄成了這種存儲結(jié)構(gòu)的三個缺點(diǎn)：第一，在進(jìn)行插入或刪除運(yùn)算時，需移動大量元素；第二，在給長度變化較大的線性表預(yù)先分配空間時，必須按最大空間分配，使存儲空間不能得到充分利用；第三，表的容量難以擴(kuò)充。7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)為了克服順序表的缺點(diǎn)，可以采用鏈接方式存儲線性表，通常我們將鏈接方式存儲的線性表稱為鏈表（LinkedList）。從實現(xiàn)的角度看，鏈表可分為動態(tài)鏈表和靜態(tài)鏈表。靜態(tài)鏈表是順序的存儲結(jié)構(gòu)，在物理地址上是連續(xù)的，而且需要預(yù)先分配地址空間大小。所以靜態(tài)鏈表的初始長度一般是固定的，在做插入和刪除操作時不需要移動元素，僅需修改指針。動態(tài)鏈表是用內(nèi)存申請函數(shù)動態(tài)申請內(nèi)存的，所以在鏈表的長度上沒有限制。動態(tài)鏈表因為是動態(tài)申請內(nèi)存的，所以每個節(jié)點(diǎn)的物理地址不連續(xù)，要通過指針來順序訪問。7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.1單鏈表結(jié)點(diǎn)結(jié)構(gòu)：data域：數(shù)據(jù)域next域：指針域7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算1．建立單鏈表 1）頭插法建表 2）尾插法建表2．插入及刪除運(yùn)算 1）插入運(yùn)算 2）刪除運(yùn)算2．查找運(yùn)算 1）按序號查找 2）按值查找7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算1.建立單鏈表-頭插法建表7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算linklist

CREATLISTF(){charch; /*逐個輸入字符，以“$”為結(jié)束符，返回單鏈表頭指針*/linklist

head,

s;head=NULL; /*鏈表開始為空*/ch=getchar(); /*讀入第一個結(jié)點(diǎn)的值*/while(ch!='$'){s=(linklist

)malloc(sizeof(linklist));/*生成新結(jié)點(diǎn)*/s－>data=ch; /*將輸入數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中*/s－>next=head;head=s; /*將新結(jié)點(diǎn)插入到表頭上*/ch=getchar(); /*讀入下一個結(jié)點(diǎn)的值*/}returnhead; /*返回鏈表頭指針*/} /*CREATLISTF*/7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算1.建立單鏈表-尾插法建表7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算linklist

CREATLISTR()/*尾插法建立單鏈表，返回表頭指針*/{charch;linklist

head,

s,

r;head=NULL;/*鏈表初值為空*/r=NULL;/*尾指針初值為空*/ch=getchar();/*讀入第一個結(jié)點(diǎn)值*/while(ch!=′$′)/*以“$”為輸入結(jié)束符*/{s=(linklist

)malloc(sizeof(linklist));/*生成新結(jié)點(diǎn)

s*/s－>data=ch;if(head==NULL)head=s;/*新結(jié)點(diǎn)

s插入空表*/elser－>next=s;/*非空表，新結(jié)點(diǎn)

s插入到尾結(jié)點(diǎn)*/ r=s;/*尾指針r指向新的表尾*/ch=getchar(?);/*讀入下一結(jié)點(diǎn)值*/}if(r!=NULL)r－>next=NULL;/*對非空表，將尾結(jié)點(diǎn)的指針域置空*/returnhead;/*返回單鏈表頭指針*/} 7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算簡化后的尾插法-附加頭節(jié)點(diǎn)7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算linklist

CREATLISTR1()/*尾插入法建立帶頭結(jié)點(diǎn)的單鏈表，返回表頭指針*/{charch;linklist

head,

s,

r;head=(linklist

)malloc(sizeof(linklist));/*生成頭結(jié)點(diǎn)head*/r=head;

/*尾指針指向頭結(jié)點(diǎn)*/ch=getchar();while(ch!=′$′) /*“$”為輸入結(jié)束符*/{s=(linklist

)malloc(sizeof(linklist));

/*生成新結(jié)點(diǎn)*s*/s－>data=ch;r－>next=s; /*新結(jié)點(diǎn)插入表尾*/r=s; /*尾指針r指向新的表尾*/ch=getchar(); /*讀入下一個結(jié)點(diǎn)的值*/}r－>next=NULL;returnhead; /*返回表頭指針*/} /*CREATLISTR1*/簡化后的尾插法-附加頭節(jié)點(diǎn)7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算2.插入與刪除-插入運(yùn)算7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算2.插入與刪除-插入運(yùn)算INSERTAFTER?(linklist

p,datatypex) /*將值為x的新結(jié)點(diǎn)插入

p之后*/{linklist

s;s=(linklist

)?malloc?(sizeof?(linklist)); /*生成新結(jié)點(diǎn)

s*/s－>data=x;s－>next=p－>next;p－>next=s;/*將*s插入*p之后*/} /*INSERTAFTER*/7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算[例7.2]

在單鏈表上，將值為x的新結(jié)點(diǎn)插入在結(jié)點(diǎn)

p前。7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算/*在帶頭結(jié)點(diǎn)的單鏈表head中，將值為x的新結(jié)點(diǎn)插入

p之前*/INSERTBEFORE(linklist

head,linklist

p,datatypex){linklist

s,

q;s=(linklist

)malloc(sizeof(linklist)); /*生成新結(jié)點(diǎn)*s*/s－>data=x;q=head; /*從頭指針開始*/while(q－>next!=p)q=q－>next;/*查找

p的前趨結(jié)點(diǎn)

q*/s－>next=p;q－>next=s;/*將新結(jié)點(diǎn)

s插入

p之前*/} /*INSERTBEFORE*/7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算[例7.3]

在單鏈表上實現(xiàn)線性表的插入運(yùn)算INSERT(L,x,i)。INSERT(linklist

L,datatypex,inti){linklist

p;intj;j=i

1;p=GET(L,j); /*找第i

1個結(jié)點(diǎn)

p*/if(p==NULL)print(″error″); /*i<1或i>(n+1)*/elseINSERTAFTER(p,x);/*將值為x的新結(jié)點(diǎn)插到

p之后*/} /*INSERT*/7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算2.插入與刪除-刪除運(yùn)算7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算2.插入與刪除-刪除運(yùn)算DELETE(linklist

p,linklist

head)/*刪去單鏈表head的結(jié)點(diǎn)

p*/{linklist

q;q=head;while(q－>next!=p)q=q－>next;/*查找

p的前趨結(jié)點(diǎn)

q*/q－>next=p－>next; /*刪除結(jié)點(diǎn)

p*/free(p); /*釋放結(jié)點(diǎn)

p*/} /*DELETE*/7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算[例7.4]

在單鏈表上實現(xiàn)線性表的刪除運(yùn)算DELETE(L,i)。DELETE(linklist

L,inti)/*刪去帶頭結(jié)點(diǎn)的單鏈表L的第i個結(jié)點(diǎn)*/{linklist

p,

r;intj;j=i

1;p=GET(L,j); /*找到第i

1個結(jié)點(diǎn)*/if((p!=NULL)&&(p－>next!=NULL)){r=p－>next; /*

r為結(jié)點(diǎn)

p的后繼*/p－>next=r－>next; /*將結(jié)點(diǎn)

r從鏈表上摘下*/free(r); /*釋放結(jié)點(diǎn)

r*/}else /*i<1或i>n*/printf(″error″)} /*DELETE*/7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算[例7.5]

將兩個遞增單鏈表合并為一個遞增單鏈表，要求不另開辟空間。UNION(linklist

la,linklist

lb);/*合并遞增單鏈表la和lb*/{linklist

p,

q,

r,

u;p=la－>next;q=lb－>next;r=la; /**r為*p的直接前趨*/while((p!=NULL)&&(q!=NULL)){if(p－>data>q－>data){u=q－>next;r－>next=q;r=q;q－>next=p;q=u;}else{r=p;p=p－>next;}}if(q!=NULL)r－>next=q;} /*UNION*/7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算3.查找運(yùn)算-按序號查找/*在帶頭結(jié)點(diǎn)的單鏈表head中查找第i個結(jié)點(diǎn)，若找到，則返回該結(jié)點(diǎn)的存儲位置；否則返回NULL*/linklist

GET(linklist

head,inti){intj;linklist

p;p=head;j=0; /*從頭結(jié)點(diǎn)開始掃描*/while((p－>next!=NULL)&&(j<i)){p=p－>next; /*掃描下一個結(jié)點(diǎn)*/j++; /*已掃描結(jié)點(diǎn)計數(shù)器*/}if(i==j)returnp; /*找到了第i個結(jié)點(diǎn)*/elsereturnNULL; /*找不到，i≤0或i>n*/} /*GET*/7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.2單鏈表的基本運(yùn)算3.查找運(yùn)算-按值查找/*在帶頭結(jié)點(diǎn)的單鏈表head中查找其結(jié)點(diǎn)值等于key的結(jié)點(diǎn)，若找到則返回該結(jié)點(diǎn)的位置p；否則返回NULL*/linklist

LOCATE(linklist

head,datatypekey){linklist

p; p=head－>next; /*從開始結(jié)點(diǎn)比較*/while(p!=NULL)if(p－>data!=key)p=p－>next; /*沒找到，繼續(xù)循環(huán)*/if(p==NULL)returnNULL;elsereturnp;

/*找到結(jié)點(diǎn)key，退出循環(huán)*/} /*LOCATE*/7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.3循環(huán)鏈表單循環(huán)鏈表7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.3循環(huán)鏈表僅設(shè)尾指針rear的單循環(huán)鏈表7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.3循環(huán)鏈表[例7.6]

在循環(huán)鏈表的第i個元素之后插入元素x。INSERT(linklist

head,datatypex,inti)/*在循環(huán)鏈表第i個元素之后插入元素x*/{linklist

s; intj;s=(

linklist)malloc(sizeof(linklist));s－>data=x; /*生成值為x的新結(jié)點(diǎn)*/p=head;j=0;while((p－>next!=head)&&(j<i)){p=p－>next;j++;}if(i=j){s－>next=p－>next;p－>next=s;}/*插入操作*/elseprintf(″error″);} /*INSERT*/7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.3循環(huán)鏈表[例7.7]

一元多項式的表示及相加。多項式結(jié)點(diǎn)形式多項式的循環(huán)鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)7.3.3循環(huán)鏈表polynode*polyadd(polynode

pa,polynode

pb); /*多項式相加運(yùn)算A=A+B*/{polynode

p,

q,

r,

s; folatx; p=pa－>next;q=pb－>next; s=pa; /**s為*p的直接前趨*/ while((p!=pa)&&(q!=pb)) {if(p－>exp<q－>exp){s=p;p=p－>next;} /*p指針后移*/if(p－>exp>q－>exp){r=q－>next;q－>next=p;s－>next=q;s=q;q=r;}else{