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

線性表是由n（n≥0）個數據元素a1,a2,…,an構成的有限序列。其中，將數據元素的個數n定義為表的長度。當n=0時稱為空表，通常將非空的線性表（n>0）記作：（a1,a2,…,an）。7.1線性表的基本概念及運算7.1.2線性表的運算1.置空表SETNULL(L)2.求長度LENGTH(L)3.取結點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線性表的基本概念及運算7.1.2線性表的運算[例7.1]利用線性表的基本運算清除表Ｌ中多余的重復結點。7.1線性表的基本概念及運算7.1.2線性表的運算PURGE(L) /*刪除線性表Ｌ中重復出現的多余結點*/Linear_list*L; {inti=1,j,x,y; while(i<LENGTH(L))/*每次循環使當前第i個結點是無重復值的結點*/{x=GET(L,i);/*取當前第i個結點*/j=i+1;while(j<=LENGTH(L)){y=GET(L,j); /*取當前第j個結點*/if(x==y)DELETE(L,j); /*刪除當前第j個結點*/elsej++;}i++;}} /*PURGE*/7.2線性表的順序存儲結構7.2.1順序表Loc?(ai+1)=Loc?(ai)+cLoc?(ai)=Loc?(a1)+(i

1)

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

新結點x，使長度為n的線性表

（a1,…,ai

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

（a1,…,ai

1,x,ai,…,an）7.2線性表的順序存儲結構7.2.2順序表的基本運算1．插入運算7.2線性表的順序存儲結構7.2.2順序表的基本運算2．刪除運算線性表的刪除運算是指將表的第i（1≤i≤n）個結點

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

（a1,…,ai

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

1的線性表

（a1,…,ai

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

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

head,

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

)malloc(sizeof(linklist));/*生成新結點*/s－>data=ch; /*將輸入數據放入新結點的數據域中*/s－>next=head;head=s; /*將新結點插入到表頭上*/ch=getchar(); /*讀入下一個結點的值*/}returnhead; /*返回鏈表頭指針*/} /*CREATLISTF*/7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算1.建立單鏈表-尾插法建表7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算linklist

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

head,

s,

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

)malloc(sizeof(linklist));/*生成新結點

s*/s－>data=ch;if(head==NULL)head=s;/*新結點

s插入空表*/elser－>next=s;/*非空表，新結點

s插入到尾結點*/ r=s;/*尾指針r指向新的表尾*/ch=getchar(?);/*讀入下一結點值*/}if(r!=NULL)r－>next=NULL;/*對非空表，將尾結點的指針域置空*/returnhead;/*返回單鏈表頭指針*/} 7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算簡化后的尾插法-附加頭節點7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算linklist

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

head,

s,

r;head=(linklist

)malloc(sizeof(linklist));/*生成頭結點head*/r=head;

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

)malloc(sizeof(linklist));

/*生成新結點*s*/s－>data=ch;r－>next=s; /*新結點插入表尾*/r=s; /*尾指針r指向新的表尾*/ch=getchar(); /*讀入下一個結點的值*/}r－>next=NULL;returnhead; /*返回表頭指針*/} /*CREATLISTR1*/簡化后的尾插法-附加頭節點7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算2.插入與刪除-插入運算7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算2.插入與刪除-插入運算INSERTAFTER?(linklist

p,datatypex) /*將值為x的新結點插入

p之后*/{linklist

s;s=(linklist

)?malloc?(sizeof?(linklist)); /*生成新結點

s*/s－>data=x;s－>next=p－>next;p－>next=s;/*將*s插入*p之后*/} /*INSERTAFTER*/7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算[例7.2]

在單鏈表上，將值為x的新結點插入在結點

p前。7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算/*在帶頭結點的單鏈表head中，將值為x的新結點插入

p之前*/INSERTBEFORE(linklist

head,linklist

p,datatypex){linklist

s,

q;s=(linklist

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

p的前趨結點

q*/s－>next=p;q－>next=s;/*將新結點

s插入

p之前*/} /*INSERTBEFORE*/7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算[例7.3]

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

L,datatypex,inti){linklist

p;intj;j=i

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

1個結點

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

p之后*/} /*INSERT*/7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算2.插入與刪除-刪除運算7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算2.插入與刪除-刪除運算DELETE(linklist

p,linklist

head)/*刪去單鏈表head的結點

p*/{linklist

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

p的前趨結點

q*/q－>next=p－>next; /*刪除結點

p*/free(p); /*釋放結點

p*/} /*DELETE*/7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算[例7.4]

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

L,inti)/*刪去帶頭結點的單鏈表L的第i個結點*/{linklist

p,

r;intj;j=i

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

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

r為結點

p的后繼*/p－>next=r－>next; /*將結點

r從鏈表上摘下*/free(r); /*釋放結點

r*/}else /*i<1或i>n*/printf(″error″)} /*DELETE*/7.3線性表的鏈式存儲結構7.3.2單鏈表的基本運算[例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線性表的鏈式存儲結構7.3.2單鏈表的基本運算3.查找運算-按序號查找/*在帶頭結點的單鏈表head中查找第i個結點，若找到，則返回該結點的存儲位置；否則返回NULL*/linklist

GET(linklist

head,inti){intj;linklist

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

LOCATE(linklist

head,datatypekey){linklist

p; p=head－>next; /*從開始結點比較*/while(p!=NULL)if(p－>data!=key)p=p－>next; /*沒找到，繼續循環*/if(p==NULL)returnNULL;elsereturnp;

/*找到結點key，退出循環*/} /*LOCATE*/7.3線性表的鏈式存儲結構7.3.3循環鏈表單循環鏈表7.3線性表的鏈式存儲結構7.3.3循環鏈表僅設尾指針rear的單循環鏈表7.3線性表的鏈式存儲結構7.3.3循環鏈表[例7.6]

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

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

s; intj;s=(

linklist)malloc(sizeof(linklist));s－>data=x; /*生成值為x的新結點*/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線性表的鏈式存儲結構7.3.3循環鏈表[例7.7]

一元多項式的表示及相加。多項式結點形式多項式的循環鏈式存儲結構7.3線性表的鏈式存儲結構7.3.3循環鏈表polynode*polyadd(polynode

pa,polynode

pb); /*多項式相加運算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{