第二章線性表知識小結

線性表學問小結線性結構的基本特點是由n(n>=0)個結點組成的有窮序列.(干脆)前驅(干脆)后繼一個結點代表一個數據元素,通常要求同一個線性結構中的全部結點所代表的數據元素具有相同的屬性(比如:數據項個數相同;對應數據項的類型相同)所含結點的個數稱為線性表的長度(表長),表長為0的線性表稱為空表.線性表的依次實現----依次表基本思想：按邏輯關系來確定排列依次，實際就是一維數組，數組的下標可以看成是元素的相對地址。邏輯上相鄰的元素的物理位置必緊鄰。存儲特點：優(yōu)點：可隨機存取(訪問)；缺點：插入和刪除操作時，需移動大量元素需事先確定表的容量簡潔產生“碎片”長度為n的依次表中，等概率狀況下，插入一個元素的平均移動元素次數為n/2，刪除一個元素的平均移動元素次數為（n-1）/2，其時間困難度都為O（n）。線性表的鏈式存儲----單鏈表基本思想：用一個指針表示結點間的邏輯關系。每個結點的存儲單元都分為兩部分：一部分存放結點的數據，另一部分存放指向結點后繼結點的指針。存儲特點：優(yōu)點：對任何位置進行插入和刪除操作只需修改指針；不須要預先安排空間；缺點：依次存?。ㄔL問）的結構（不能從當前結點動身訪問到任一結點）帶頭結點的單鏈表sq為空的條件：sq->next==NULL不帶頭結點的單鏈表sq為空的條件sq==NULL在單鏈表中,刪除某一指定結點時,需找到該結點的前驅結點。在單鏈表中設置頭結點的作用：不管單鏈表是否為空表，頭結點指針均不空，并使得對單鏈表的操作在各種狀況下統(tǒng)一。在單循環(huán)鏈表中通常設置尾指針（指向最終一個結點）比設置頭指針好

從一個具有n個結點的單鏈表中查找其值等于x的結點時，在查找成功狀況下平均需比較個結點思索：對于一個有n個結點的單鏈表，在已知p所指結點后插入一個結點的時間困難度是？在給定值為x的結點后插入一個結點的時間困難度是？（n+1）/2使得查找起先結點和終端結點都很便利，其查找時間都是O（1）；一元多項式的表示在計算機中，可以用一個線性表來表示:P=(p0,p1,…，pn)一元多項式但是對于形如

S(x)=1+3x10000–2x20000的多項式，上述表示方法是否合適？一般狀況下的一元稀疏多項式可寫成Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi是指數為ei的項的非零系數，0≤e1<e2<┄<em=n可以下列線性表表示：（（p1,e1）,(p2,e2),┄,(pm,em)）

P999(x)=7x3-2x12-8x999例如:可用線性表

((7,3),(-2,12),(-8,999))表示一元多項式的實現：typedefstruct{//項的表示

floatcoef;//系數

intexpn;//指數}

term,ElemType;typedefOrderedLinkListpolynomial;//用帶表頭結點的有序鏈表表示多項式結點的數據元素類型定義為:已知sq是帶頭結點的非空單鏈表，且p指向的結點既不是第一個結點也不是最終一個結點，則寫出下列語句序列：刪除*p的干脆后繼結點刪除*p的干脆前驅結點刪除*p結點刪除第一個結點刪除最終一個結點依次表算法舉例依次結構線性表LA與LB的結點關鍵字為整數。LA與LB的元素按非遞減有序，線性表空間足夠大。試用類C語言給出一種高效算法，將LB中元素合到LA中，使新的LA的元素仍保持非遞減有序。高效指最大限度的避開移動元素。voidUnion(SqList&LA,SqListLB)//LA和LB是依次存儲的線性表，元素按非遞減有序排列，本算法將LB合并到LA中，元素仍非遞減有序。{m=LA.length;n=LB.length;//m，n分別為線性表LA和LB的長度k=m+n-1;//k為結果線性表的工作指針（下標）i=m-1;j=n-1;//i，j分別為線性表LA和LB的工作指針（下標）while(i>=0&&j>=0){if(LA.data[i]>=LB.data[j])LA.data[k--]=LA.data[i--];elseLA.data[k--]=LB.data[j--];}while(j>=0)LA.data[k--]=LB.data[j--];LA.length=m+n;}設計算法將一個帶頭結點的單鏈表A分解為兩個具有相同結構的鏈表B、C。其中B表的結點是A表中值小于零的點，而C表中的結點為A表中值大于零的結點

（鏈表A的元素類型為整型，要求B、C表運用A表的結點，即不再開拓新的結點空間）

voidsplit(linklist&lb,linklist&lc,linklistla){

linklistp=la->next,r,s;

lb=(linklist)malloc(sizeof(lnode));lc=(linklist)malloc(sizeof(lnode));

r=lb;s=lc;

while(p!=NULL){

if(p->data<0)//將結點鏈入B表中{r->next=p;r=r->next;}elseif(p->data>0)//將結點鏈入C表中{s->next=p;s=s->next;}

p=p->next;

}r->next=NULL;s->next=NULL;free(la);}在非遞減有序的依次表中插入元素x，使其仍保持有序。分析:從后向前查找插入位置,同時向后移動大于x的元素statusOrderlistinsert(sqlist&L,ElemTypee){if(L.length==MAXSIZE)returnERROR;for(i=L.length-1;i>=0&&L.elem[i]>x;i--)L.elem[i+1]=L.elem[i];L.elem[i+1]=x;L.length++;returnOK;}有兩個帶頭結點的循環(huán)單鏈表ha和hb，設計一個算法將它們首尾合并成一個帶頭結點的單鏈表hc，要求不再開拓新的空間。過程：令hc指向ha，再用一指針p遍歷鏈表ha，找到ha的最終一個結點，然后將hb（除頭結點之外的其他結點）鏈在其后，再找到hb最終一個結點,修改其后繼為空.最終釋放hb。voidlink(linklist&hc,linklistha,linklisthb){hc=ha;p=ha->next;while(p->next!=ha)