考研專業(yè)課自測試題及答案計算機(jī)組成原理

線性表(List)邏輯結(jié)構(gòu)和主要操作順序存儲結(jié)構(gòu)部分操作的實(shí)現(xiàn)小結(jié)和作業(yè)第一頁，共六十頁。邏輯結(jié)構(gòu)D＝{a1,

a2,

…,

ai

,an}S＝{

<ai-1

,ai

>|ai-1

,ai

∈

D,

i=2,...,n

}第二頁，共六十頁。主要操作InitList(&L)DestroyList(&L)ClearList(&L)ListInsert(&L,

i,

e)ListDelete(&L,

i,

&e)LocateElem(L,

e,

Compare())GetElem(L,

i,

&e)PriorElem(L,

cur_e,

&pre_e)NextElem(L,

cur_e,

&next_e)ListEmpty(L)ListLength(L)第三頁，共六十頁。順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元依次存放線性表中的數(shù)據(jù)元素a1a2…ai-1ai…

an線性表的起始地址(基地址)第四頁，共六十頁。定義數(shù)據(jù)類型

SqList#define#definetypedefLIST_INIT_SIZE

100LISTINCREMENT

10struct{ElemTypeintint*elem;length;listsize;}

SqList;第五頁，共六十頁。使用

SqListSqList

L;Lelemlengthlistsizeint

a;第六頁，共六十頁?！璭lemlength=6listsize=

100L使用SqList第七頁，共六十頁。部分操作的實(shí)現(xiàn)InitList(&L)DestroyList(&L)ListInsert(&L,

i,

e)ListDelete(&L,

i,

&e)GetItem(L,

i,

&e)ListMerge(&La,

Lb)ListMerge(La,

Lb,

&Lc)第八頁，共六十頁。InitList—功能原型：Status

InitList(SqList

&L)作用：給elem，length和listsize賦值過程：1、申請存儲空間，首地址存放到elem2、length=03、listsize=LIST_INIT_SIZE第九頁，共六十頁。InitList—功能……01

0Lelemlengthlistsize第十頁，共六十頁。InitList-申請內(nèi)存#include

<malloc.h>elem

=

(ElemType

*)

malloc(LIST_INIT_SIZE

*

sizeof(ElemType))0elem1100elem沒有獲得內(nèi)存，出錯第十一頁，共六十頁。InitListStatus

InitList(SqList

&L){L.elem=(ElemType

*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)

return(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return(OK);}第十二頁，共六十頁。DestroyList—功能原型：Status

DestroyList(SqList

&L)作用：釋放L以前申請的內(nèi)存過程：1、釋放elem指示的連續(xù)存儲單元2、L.length=03、L.listsize=0第十三頁，共六十頁。LDestroyList—功能……0610

0第十四頁，共六十頁。DestroyListStatus

DestroyList(SqList

&L){free(L.elem);L.length=0;L.listsize=0;return(OK);}第十五頁，共六十頁。GetIem—功能原型：Status

GetItem(SqList

L,int

i,ElemType

&e)作用：取出ai的值過程：1、判斷i的合法性2、e=ai第十六頁，共六十頁。GetItem—功能L10100a1

a2

a3

a4

a5

a6

a7

a8

a9a10GetItem(L,

6,

e)e第十七頁，共六十頁。GetIem—合法性判斷線性表中L有l(wèi)ength個元素a1

a2

a3

...alength數(shù)據(jù)元素的下標(biāo)為1，

2，…，length1≤i≤length第十八頁，共六十頁。GetItem—ai的位置a1a2

a3

a4a5

a6

a7a8

a9a10數(shù)據(jù)元素elema1

elem

+

0a2

elem

+

1a3elem

+

2ai

elem

+

i

-

1e=*(elem

+

i

–

1)第十九頁，共六十頁。GetItem—ai的位置a1

a2

a3

a4

a5

a6

a7

a8a9a10數(shù)據(jù)元素a1

elem[0]a2

elem[1]a3elem[2]aielem[

i

–

1]e=elem[

i

–

1]elem[0]

elem[1]elem[9]第二十頁，共六十頁。GetItemStatus

GetItem(SqList

L,

int

i,

ElemType

&e){if(i<1

||

i>L.length)

return(ERROR);e=L.elem[i

-

1];

//

e=*(L.elem

+

i

–

1)return

(OK)}第二十一頁，共六十頁。ListInsert—功能原型：Status

ListInsert(SqList

&L,int

i,ElemType

e)作用：把e插入線性表，作為第i個數(shù)據(jù)元素第二十二頁，共六十頁。ListInsert—功能邏輯結(jié)構(gòu)的變化(a1,

…,

ai-1,

ai,

…,

an)

→

(a1,

…,

ai-1,

e,

ai,

…,

an)<ai-1,

ai>

→

<ai-1,

e>,

<e,

ai>第二十三頁，共六十頁。ListInsert—功能存儲結(jié)構(gòu)的變化ListInsert(L,

3,

e)length6a1a2a3a4a5a6length7a1a2ea3a4a5a6第二十四頁，共六十頁。ListInsert—功能過程：1、判斷i的合法性2、移動3、賦值4、length++第二十五頁，共六十頁。ListInsert—i的合法性L7100a1

a2

a3

a4

a5

a6

a71≤i≤8一般的1≤i≤length+1第二十六頁，共六十頁。ListInsert—移動a1a2a3a4a5a6a1a2ea3a4a5a6length6length7a7

a66a

a5a5

a4a4

a3a

=ak+1

kk=length

→

i第二十七頁，共六十頁。ListInsert—移動L.elem[i-1]=e;ak+1

=

ak方法一：數(shù)組元素k=length

→

ij=L.length-1;While(

j>=i-1){L.elem[j+1]=L.elem[j];j--;}for(int

j=L.length;j>=i;j++)L.elem[j]=

L.elem[j-1];L.elem[i-1]=e;第二十八頁，共六十頁。ListInsert—移動方法二：移動指針

q=L.elem+(i-1);p=L.elem+L.length-1while(p>=q){*(p+1)=*p;p--;}q指向了aiP開始時指向了alength*q=e;k=length

→

iak+1=ak第二十九頁，共六十頁。ListInsert—移動ListInsert(L,

5,

66)q=L.elem

+

(i-1);for(p=L.elem

+

L.length-1;

p>=q;

p--)

*(p+1)=*p;*q=e;L.length-1pp

q21

18

30

75

64620p

p5462

5867

87第三十頁，共六十頁。ListInsert—移動L7a1

a2

a3

a4

a5

a6

a7表滿的條件？length=listsizea1

a2

a3

a4

a5

a6

a7710第三十一頁，共六十頁。ListInsert—移動if(L.length

==

L.listsize){newbase

=

realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)

return(OVERFLOW);L.elem=newbase;L.listsize

+=LISTINCREMENT;}第三十二頁，共六十頁。ListInsertStatus

ListInsert(SqList

&L,

int

i,

ElemType

e){if(

i<1

||

i>

L.length+1)

return(ERROR);if(

L.length

=

=

L.listsize)

{newbase

=

realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)

return(OVERFLOW);L.elem=newbase;L.listsize

+=LISTINCREMENT;}第三十三頁，共六十頁。ListInsertq=L.elem

+

(i-1);p=L.elem

+

L.length-1;*q=e;L.length++;return(OK);}移動while(

p>=q){

*(p+1)=*p;

p--}賦值長度增加for(int

j=L.length-1;j>=i-1;j+L.elem[j+1]=

L.elem[j];L.elem[i-1]=e;++L.length;第三十四頁，共六十頁。ListInsert1、在什么情況下，移動次數(shù)最少，最少移動次數(shù)是多少？2、在什么情況下，移動次數(shù)最多，最多移動次數(shù)是多少？3、在插入每個位置的概率相同的情況下，移動次數(shù)的期望值是多少？第三十五頁，共六十頁。List

Delete—功能原型：Status

ListDelete(SqList

&L,int

i,ElemType

&e)作用：取出線性表L的第i個數(shù)據(jù)元素的值，并刪除第三十六頁，共六十頁。ListDelete—功能邏輯結(jié)構(gòu)的變化(a1,

…,

ai-1,

ai,

ai+1…,

an)

→

(a1,

…,

ai-1,

ai+1,

…,

an<ai-1,

ai>

<ai,

ai+1>→

<ai-1,

ai+1>第三十七頁，共六十頁。ListDelete—功能存儲結(jié)構(gòu)的變化a1

a2

a4

a5

a6a1

a2

a3

a4

a5

a6ListDelete(L,

3,

e)65lengthelength第三十八頁，共六十頁。List

Delete—功能過程：1、判斷i的合法性2、取值3、移動4、length--第三十九頁，共六十頁。ListDelete—i的合法性L7100a1

a2

a3

a4

a5

a6

a71≤i≤7一般的1≤i≤length第四十頁，共六十頁。ListDelete—移動a3

a44a

a5a5

a6a

=ak-1

kk=i+1

→

lengthlength6a1a2a3a4a5

a6length5a1a2a4a5a6第四十一頁，共六十頁。ListDelete—移動p=L.elem

+

(i-1);e=*p;q=L.elem

+

L.length-1;方法一：移動指針p指向了aiq開始時指向了alengthfor(++p;

p<=q;

p++)

*(p-1)

=*p;p指向了ai+1第四十二頁，共六十頁。ListDelete—移動方法二：數(shù)組元素j=i;while(j<=L.length-1){L.elem[j-1]=L.elem[j];j++;}ak-1=akk=i+1

→

length第四十三頁，共六十頁。ListDeleteStatus

ListDelete(SqList

&L,

int

i,

ElemType

&e){if(

i<1

||

i>

L.length)

return(ERROR);p=L.elem

+

i

–

1;e=*p;q=L.elem

+

L.length

–

1;for(++p;

p<=q;

p++)

*(p-1)

=*p;L.length--;return(OK);}e=

L.elem[i-1];for(int

j=i;j<=L.length-1;L.elem[j-1]=

L.elem[j];--L.length;第四十四頁，共六十頁。ListDelete1、在什么情況下，移動次數(shù)最少，最少移動次數(shù)是多少？2、在什么情況下，移動次數(shù)最多，最多移動次數(shù)是多少？3、在刪除每個位置的概率相同的情況下，移動次數(shù)的期望值是多少？第四十五頁，共六十頁。ListMerge—功能原型：Status

ListMerge(SqList

&La,SqList

Lb)作用：把Lb中的數(shù)據(jù)元素添加到La的表尾注意：不破壞Lb表第四十六頁，共六十頁。ListMerge—功能b1

b2

b3La

a1

a2

a3

a4

a5

a6Lbb1b2

b3第四十七頁，共六十頁。ListMerge—功能過程：1、取出Lb的一個數(shù)據(jù)元素bi2、把bi插入到La的表尾3、重復(fù)1-2，使得i=1,2,…,Lb.length第四十八頁，共六十頁。ListMergeStatus

ListMerge(SqList

&La,

SqList

Lb){for(int

i=1;

i<=Lb.length;

i++){GetItem(Lb,

i,

e);code=ListInsert(La,

La.length+1,

e);if(code

!=

OK)

return(ERROR);}return(OK);}第四十九頁，共六十頁。ListMergeStatus

ListMerge(SqList

&La,

SqList

Lb){if(

La.listsize<

La.length+Lb.length)

{newbase

=

realloc(L.elem,(La.length+Lb.length)*sizeof(ElemType);if(!newbase)

return(OVERFLOW);L.elem=newbase;L.listsize

=

La.length+Lb.length;}For

(int

i=1;

i<=Lb.length;

i++){La.elem[La.length]=Lb.elem[i-1];

La.length++;}return(OK);}第五十頁，共六十頁。ListMerge—功能原型：Status

ListMerge(SqList

La,SqList

Lb,SqList

&LcLa:

a1≤

a2

≤a3……

≤amLb:

b1≤

b2

≤b3……

≤bn作用：把有序表La和Lb合并得到一個新的有序表Lc:

c1≤

c2

≤c3……

≤cm+nci=aj

or

ci=bk第五十一頁，共六十頁。ListMerge—功能13

6

102

8

9LaLb12

3

6

8

9

10Lc第五十二頁，共六十頁。ListMerge—分析1

3

6

10

1128

9LaLbLapb123

68910pa

pa

pa

papbpb

pb11pa

pa第五十三頁，共六十頁。ListMerge—分析分析：1、首先建立空表Lc2、從La和Lb中余下未處理的數(shù)據(jù)元素中選取最小的一個e3、把e插入表尾4、重復(fù)n+m次2和3第五十四頁，共六十頁。ListMerge

—分析1、首先建立空表LcInitList(Lc);2、pa和pb分別表示La和Lb中余下未處理的第一個數(shù)據(jù)元素（初始時pa=1,pb=1）GetItem(La,

pa,

Ea);

GetItem(Lb,

pb,

Eb);if(Ea<Eb