第二章線性表

1、第二章線性表1什么是順序存儲(chǔ)結(jié)構(gòu)？什么是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)？線性表的順序存儲(chǔ)指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，它的特點(diǎn)是，線性表中相鄰的元素ai和ai+1賦以相鄰的存儲(chǔ)位置LOC(ai) 和LOC(a i+ 1 ) 。即，以元素在計(jì)算機(jī)內(nèi)"物理位置相鄰"來(lái)表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。簡(jiǎn)言之邏輯相鄰，物理相鄰。相鄰元素之間查一個(gè)元素所占的物理空間，因此，只要確定了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。線性量的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素(這組存儲(chǔ)單元可以

2、是連續(xù)的，也可以是不連續(xù)的) . 因此，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素a i+ 1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素a i 來(lái)說(shuō)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)-個(gè)指示其直接后繼的信息即直接接后繼的存儲(chǔ)位置 . 這兩部份信息組成數(shù)據(jù)元素ai的存儲(chǔ)映映像，稱為結(jié)點(diǎn)(node) . 它包括兩個(gè)域:其中存儲(chǔ)數(shù)據(jù)元素信息的稱為數(shù)據(jù)域，存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域. 指針域中存儲(chǔ)的信息稱做指針或鏈.2線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各有什么特點(diǎn)？順序存儲(chǔ)結(jié)構(gòu)，邏輯相鄰的元素，物理上也相鄰，每個(gè)結(jié)點(diǎn)只需存儲(chǔ)數(shù)據(jù)本身，不許存儲(chǔ)邏輯關(guān)系，節(jié)約存儲(chǔ)空間，查找元素方便，但插入或刪除元素需要大量移

3、動(dòng)元素，效率低。適合查找多但插入刪除少的情況。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，邏輯上相鄰的元素，物理上不一定相鄰，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)元素本身外，還要存儲(chǔ)元素之間的邏輯關(guān)系，占用存儲(chǔ)空間大，但查找元素都要從頭開始，查找費(fèi)時(shí)間，但插入或刪除元素不需要大量移動(dòng)元素，只需要知道插入或刪除位置結(jié)點(diǎn)的前驅(qū)指針，進(jìn)行簡(jiǎn)單的指針變換即可。適合查找少，插入刪除相對(duì)多的情況。3設(shè)線性表中數(shù)據(jù)元素的總數(shù)基本不變，并很少進(jìn)行插入或刪除工作，若要以最快的速度存取線性表中的數(shù)據(jù)元素，應(yīng)選擇線性表的何種存儲(chǔ)結(jié)構(gòu)？為什么?用順序存儲(chǔ)，原因在1 和2之間；4線性表的主要操作有哪些？1） InitList(&L) 初始化：構(gòu)造一個(gè)

4、空的線性表L。2）. DestroyList(&L) 銷毀：銷毀一個(gè)業(yè)已存在的線性表L。3）. ClearList(&L) 清空：將一業(yè)已存在的線性表L重置為空表。4）. ListEmpty(L) 判表空：若L為空表，則返回TRUE；否則返回FALSE 。5） ListLength(L) 求長(zhǎng)度：對(duì)給定的線性表L，返回線性表L的數(shù)據(jù)元素的個(gè)數(shù)。6） GetElem(L,i,&e) 對(duì)給定的線性表L，取第i個(gè)數(shù)據(jù)元素。0iLength(L)-1），用e返回L中第i個(gè)數(shù)據(jù)元素的值。7）. LocateElem(L,e,compare() 定位 返回L中第

5、一個(gè)與e滿足關(guān)系compare( )的數(shù)據(jù)元素的位序, 若這種數(shù)據(jù)元素不存在, 則返回0 。8）. PriorElem(L,cur_e,&pre_e) 求前驅(qū)：若cur_e是L的數(shù)據(jù)元素, 且不是第一個(gè), 則用pre_e返回它的前驅(qū), 否則操作失敗, pre_e無(wú)定義。9）. NextElem(L,cur_e,&next_e)求后繼 若cur_e是L的數(shù)據(jù)元素,且不是最后一個(gè),則用next_e返回它的后繼,否則操作失敗, next_e無(wú)定義。10）. ListInsert(&L,i,e) 插入 在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e,L的長(zhǎng)度加1 。1=<i &l

6、t;=Listlength(L)+111）. ListDelete(&L,i,&e) 刪除 刪除L的第i個(gè)數(shù)據(jù)元素,并用e返回其值,L的長(zhǎng)度減1 。1=<i <=Listlength(L)+112）. ListTraverse(L,visit() 遍歷 對(duì)給定的線性表L，依次輸出L的每一個(gè)數(shù)據(jù)元素。遍歷時(shí)不許重復(fù)13）. Copy(L,C) 復(fù)制 將給定的線性表L復(fù)制到線性表C中。14）. Merge(A,B,C) 合并 將給定的線性表A和B合并為線性表C。 5簡(jiǎn)述數(shù)組與順序存儲(chǔ)結(jié)構(gòu)線性表的區(qū)別和聯(lián)系。順序存儲(chǔ)結(jié)構(gòu)的線性表，它是用一個(gè)結(jié)構(gòu)體變量來(lái)描述一個(gè)線性表，該變

7、量包含三個(gè)分量，一個(gè)是一維數(shù)組來(lái)存儲(chǔ)線性表中的元素，一個(gè)是線性表的元素個(gè)數(shù)length ，一個(gè)是線性表最大長(zhǎng)度。對(duì)于線性表中的數(shù)組，每個(gè)元素必須是連續(xù)存放，若是對(duì)線性表插入或刪除，對(duì)應(yīng)位置需要靠右移或左移來(lái)重新保持緊密連接關(guān)系。而且插入或刪除只能在合理位置（插入在1length +1的位置，且不能越界，刪除在1length 的位置上，）。而數(shù)組要靈活很多，數(shù)組里的元素不必連續(xù)存放，插入刪除也不必重新保持元素緊密相聯(lián)，可以在任意位置插入刪除元素，只要不越界即可。 6順序表和鏈表在進(jìn)行插入操作時(shí)，有什么不同？順序表插入時(shí)，先找到插入位置，然后從表尾部到插入位置的所有結(jié)點(diǎn)順次后移一個(gè)元素，再把要插入

8、的元素放在預(yù)定位置，插入需要大量移動(dòng)元素，效率低。而鏈?zhǔn)酱鎯?chǔ)插入時(shí)只需找到要插入元素應(yīng)在位置的前驅(qū)元素的指針，然后開辟新結(jié)點(diǎn)，將新元素放入新結(jié)點(diǎn)，再用兩條語(yǔ)句就把新結(jié)點(diǎn)插入鏈表適當(dāng)位置了，不需大量移動(dòng)元素，效率高.7畫出下列數(shù)據(jù)結(jié)構(gòu)的圖示：順序表單鏈表 雙鏈表循環(huán)鏈表 順序存儲(chǔ) 單鏈表 雙向鏈表 循環(huán)鏈表a0a1an-1b1a0a1an-1 8試給出求順序表長(zhǎng)度的算法。 ilength t listlelength gth(Seqlist *L) returlength (L->lelength ) ; 9若順序表A中的數(shù)據(jù)元素按升序排列，要求將x插入到順序表中的合適位置，以保證表的有序

9、性，試給出其算法。答：設(shè)原表 (1)順序存儲(chǔ)Void Insert(sqllist *L , elemtype x) Int i = 0; While( i < L->length && L ->elemi < X) i+; If( I = L-> length) L ->elemi = X; L->length+ ; Else For(j =L->length 1; j = i ;j-) L->elemj+1 = L->elemj; L->elemj = X; L->length+;(2)鏈?zhǔn)酱鎯?chǔ)Int

10、insert(slnodetype *h ,Elemtype X) slnodetype *p,*s; p=h;q = h->next; while( p->next !=NULL && q->data < X) p=q; q = q->next;/ if ( p ->next =NULL) s = (slnode *)malloc(sizeof(slnode) ; s->data = X;p ->next = s;s ->next = NULL; return true ; else (s=(slnodetype*)mal

11、loc(sizeof(slnodetype)=NULL) return FALSE; s->data=x; s->next=p->next; p->next=s; return TRUE;10.將一個(gè)線性表從第i個(gè)位置起拆開，變成兩個(gè)線性表答：void seperate(link L , int i , link A, link B) int j = 1; link p = L ;while( j<= i -1 &&p !=NULL) j+; P = P->next;if(p =NULL) printf("the i is over

12、flow"); exit(); else q = p->next; p->next = NULL; LA = L; LB -> next = q ; 11把一個(gè)值為的結(jié)點(diǎn)插到表中值為的結(jié)點(diǎn)之前的算法 typedef struct Lnode Elemtype data; struct Lnode *next; Lnode, *LinkList ,slnodetype*link ;Void insert(link L , elem x , elem y)/采用鏈?zhǔn)酱鎯?chǔ)的方式 Link p = L; /放的q的前驅(qū)Link q = L;While( q != NULL

13、&& q->data !=x) /找到的前驅(qū) P = q;q = q ->next; S = (link)malloc(sizeof(slnode); S ->data = y; s->next = q; p ->next = s;12.將線性表（順序存儲(chǔ)），偶數(shù)下標(biāo)的元素都變成0，奇數(shù)下標(biāo)的元素都置為1；typedef struct ElemType *elem; int length; int listsize; /當(dāng)前分配的存儲(chǔ)容量（以sizeof(ElemType)為單位）SqList;Change_list (SqList &L)

14、 int i = 0; for ( i = 0; i< L->length ; i+) if(i%2= 0) L->elementi = 0; else L->elementi = 1;13，將線性表中偶數(shù)下標(biāo)的元素都刪除，只留下奇數(shù)下標(biāo)的元素構(gòu)成一個(gè)新的線性表；假設(shè)用鏈?zhǔn)酱鎯?chǔ)typedef struct Lnode Elemtype data; struct Lnode *next; Lnode, *LinkList ,slnodetype*link ;Link insert(link L ,) /設(shè)線性表的第一個(gè)元素下標(biāo)是1 link L_even ; L_even

15、 =(link)malloc(sizeof(Lnod); / L_even是新奇數(shù)鏈表的頭指針r= L_even; /r是新的奇數(shù)鏈表的尾部指針 i=1;Link p = L->next ; /放的q的前驅(qū) /r放新鏈表的最后一個(gè)結(jié)點(diǎn)的指針While( p != NULL ) /是q的前驅(qū)If(i %2 = = 1) r->next = p; r = p; P = p->next;14試將一個(gè)無(wú)序的線性表A=(11,16,8,5,14,10,38,23)轉(zhuǎn)換成一個(gè)按升序排列的有序線性表（用鏈表實(shí)現(xiàn)）。11已知 L為單鏈表指針,數(shù)據(jù)結(jié)點(diǎn)遞增有序,編寫表中值從大于MIN開始到小于

16、MAX值為止所有結(jié)點(diǎn)完全倒置的算法.typedef struct Lnode Elemtype data; struct Lnode *next; Lnode, *LinkList ,slnodetype*link ;Void converse(link L , elem x, elem y) Link p = L; /放的q的前驅(qū)Link q = L;Link temp;While( q != NULL && q->data <= min ) /是q的前驅(qū)P = q; q= q->next;If(q = NULL)Printf(“ the min is to

17、o big”); exit();Protect = q; temp ->next =null; /protect是指向min 結(jié)點(diǎn)指針，temp->next存放倒置過(guò)的最后一個(gè)結(jié)點(diǎn)While(q->data < max)N = q->next;/為下一個(gè)要處理的結(jié)點(diǎn)q->next = temp->next;Temp->next = q;q = N;P ->next = temp->next;Protect ->next = q;15 .遞增有序線性表，（同表中元素各不同，另構(gòu)建一個(gè)新表，值為，交集且遞增有序答(1)順序存儲(chǔ)voi

18、d merge(Elemtype La, Elemtype Lb, snode *Lc) int i,j,k; int La_length, Lb_length; i=j=0;k=0; La_length=Length(La); Lb_length=Length(Lb); /*取表La,Lb的長(zhǎng)度*/ Initiate(Lc); /*初始化表Lc*/ While (I < La_length&&j< Lb_length) a=get(La,i);b=get(Lb,j); if(a<b) +i; else if(a >b)+j;Else Insert(LC

19、->elelm , k+, a); i+;j+; /while LC->length = k; (2)鏈?zhǔn)酱鎯?chǔ)Void (link a ,link b,link c)Link pa = a ->next, pb = b-next , pc = c;While(pa !=NULL && pb !=NULL)If(pa ->data < pb->data)Pa = pa->next;Else if(pa->data > pb->data)Pb = pb->next;Else /若相等，插入到表中c->next

20、= pa;C = pa;Pa = pa->next;Pb = pb->next;16刪除線性表a中第i個(gè)元素起的k個(gè)元素 順序存儲(chǔ)typedef struct ElemType *elem; int length; int listsize; /當(dāng)前分配的存儲(chǔ)容量（以sizeof(ElemType)為單位）SqList;Delete_k(SqList &L) int j;   if(i<1|k<0|i+k-1>a.length) return error; For ( j = i;j +k <=L->length ; j+)

21、 Elemj = elemj+k ; 17把x插入遞增有序表L中 (順序，鏈?zhǔn)蕉家㏒tatus Insert_SqList(SqList &L,int x)/把x插入遞增有序表L中  if(L.length+1>L.listsize) return ERROR;  L.length+;  for(i=L.length-1;L.elemi>x&&i>=0;i-)    L.elemi+1=L.elemi;  L.elemi+1=x;  

22、;return OK;/Insert_SqList 18在無(wú)頭結(jié)點(diǎn)鏈表L的第i個(gè)元素之前插入元素bStatus Insert(LinkList &L,int i,int b)/在無(wú)頭結(jié)點(diǎn)鏈表L的第i個(gè)元素之前插入元素b  p=L;q=(LinkList*)malloc(sizeof(LNode);  q.data=b;  if(i=1)      q.next=p;L=q; /插入在鏈表頭部    else    &#

23、160; while(-i>1) p=p->next;    q->next=p->next;p->next=q; /插入在第i個(gè)元素的位置  /Insert 19鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于2 算法如下：void converse(slnodetype *head)slnodetype *p,*q; p=head->next; head->next=NULL;/*帶頭結(jié)點(diǎn)*/ while(p!=NULL) q=p->next; p->next=head->next; head-&g

24、t;next=p; p=q;20把鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲(chǔ)空間void merge1(LinkList &A,LinkList &B,LinkList &C)/   p=A->next;q=B->next;C=A;  while(p&&q)      s=p->next;p->next=q; /將B的元素插入    if(s)          

25、;t=q->next;q->next=s; /如A非空,將A的元素插入        p=s;q=t;  /while/merge1 21刪除元素遞增排列的鏈表L中值大于mink且小于maxk的所有元素Status Delete_Between(Linklist &L,int mink,int maxk)/   p=L;  while(p->next->data<=mink) p=p->next; /p是最后一個(gè)不大于mink的元素  if(p->next)    /如果還有比mink更大的元素      q=p->next;    while(q->data<maxk) q=q->next; /q是第一個(gè)不小于maxk的元素    p->next=q