2020考研专业课自测试题及答案计算机组成原理ppt课件

1、顺序存储结构顺序存储结构线性表线性表(List)(List)部分操作的实现部分操作的实现逻辑结构和主要操作逻辑结构和主要操作小结和作业小结和作业逻辑结构逻辑结构Da1, a2, , ai ,anS |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,

2、&pre_e)NextElem(L, cur_e, &next_e)ListEmpty(L)ListLength(L)顺序存储结构顺序存储结构 用一组地址连续的存储单元依次存放线性表中的数据元素用一组地址连续的存储单元依次存放线性表中的数据元素 a1 a2 ai-1 ai an线性表的起始地址(基地址)定义数据类型定义数据类型 SqList#defineLIST_INIT_SIZE 100#defineLISTINCREMENT10typedefstructElemType*elem;intlength;intlistsize; SqList;运用运用 SqList SqLis

3、tSqListL;Lelemlengthlistsizeint a; elemlength=6listsize= 100L运用运用 SqList SqList部分操作的实现部分操作的实现InitList(&L)DestroyList(&L)ListInsert(&L, i, e)ListDelete(&L, i, &e)GetItem(L, i, &e)ListMerge(&La, Lb)ListMerge(La, Lb, &Lc)InitList功能功能过程：1、申请存储空间，首地址存放到elem2、length=03、list

4、size= LIST_INIT_SIZE原型：Status InitList( SqList &L)作用：给elem，length和listsize赋值LInitList功能功能 0100elemlengthlistsizeInitList-申请内存申请内存elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType)#include 0elem1100elem没有获得内存，出错InitListStatus InitList(SqList &L)L.elem=(ElemType *)malloc(LIST_INIT_SI

5、ZE*sizeof(ElemType);if(!L.elem) return(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return(OK);DestroyList功能功能过程：1、释放elem指示的连续存储单元2、L.length=03、L.listsize=0原型：Status DestroyList( SqList &L)作用：释放L以前申请的内存LDestroyList功能功能 610000DestroyListStatus DestroyList(SqList &L)free(L.elem);L.length=0;L

6、.listsize=0;return(OK);GetIem功能功能过程：1、判断i的合法性2、e=ai原型：Status GetItem( SqList L, int i, ElemType &e)作用：取出ai的值GetItem功能功能L10100a1 a2 a3 a4 a5 a6 a7 a8 a9 a10GetItem(L, 6, e)eGetIem合法性判断合法性判断线性表中L有length个元素 a1 a2 a3 . alength数据元素的下标为1， 2，length1ilengthGetItemai的位置的位置a1 a2a3a4a5a6 a7a8 a9 a10数据元素ele

7、ma1 elem + 0a2 elem + 1a3 elem + 2ai elem + i - 1e=*(elem + i 1)GetItemai的位置的位置a1 a2a3a4a5a6 a7a8 a9 a10数据元素elem0a1 elem0a2 elem1a3 elem2ai elem i 1e=elem i 1elem1elem9GetItemStatus GetItem(SqList L, int i, ElemType &e) if(iL.length) return(ERROR); e=L.elemi - 1; / e=*(L.elem + i 1) return (OK)L

8、istInsert功能功能原型：Status ListInsert( SqList &L, int i, ElemType e)作用：把e插入线性表，作为第i个数据元素ListInsert功能功能逻辑结构的变化 , (a1, , ai-1, ai, , an) (a1, , ai-1, e, ai, , an)ListInsert功能功能存储结构的变化a1 a2 e a3 a4 a5 a6a1 a2 a3 a4 a5 a6 ListInsert(L, 3, e)6length7lengthListInsert功能功能过程：1、判断i的合法性2、挪动3、赋值4、length+ListIn

9、serti的合法性的合法性L7100a1 a2 a3 a4 a5 a6 a71i8一般的 1ilength+1ListInsert挪动挪动a1 a2 e a3 a4 a5 a6a1 a2 a3 a4 a5 a6 6length7lengtha7a6a6a5a5a4a4a3ak+1=akk=length iListInsert挪动挪动方法一：数组元素j=L.length-1;L.elemi-1=e;ak+1 = akk=length iWhile( j=i-1) L.elemj+1=L.elemj; j-;for(int j=L.length;j=i;j+) L.elemj= L.elemj-1

10、;L.elemi-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; ak+1=akk=length iListInsert挪动挪动q=L.elem + (i-1); for(p=L.elem + L.length-1; p=q; p-) *(p+1)=*p;*q=e;ListInsert(L, 5, 66) L.length-10pppq87564266p21 18 30 75 42 56 87ListInsert挪

11、动挪动L77a1 a2 a3 a4 a5 a6 a7a1 a2 a3 a4 a5 a6 a7表满的条件？length=listsize10ListInsert挪动挪动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

12、 i, ElemType e) if( 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;while( p=q) *(p+1)=*p; p-*q=

13、e; L.length+;return(OK);挪动赋值长度增加for(int j=L.length-1;j=i-1;j+) L.elemj+1= L.elemj;L.elemi-1=e;+L.length;ListInsert1、在什么情况下，移动次数最少，最少移动次数是、在什么情况下，移动次数最少，最少移动次数是多少？多少？2、在什么情况下，移动次数最多，最多移动次数是、在什么情况下，移动次数最多，最多移动次数是多少？多少？3、在插入每个位置的概率相同的情况下，移动次数、在插入每个位置的概率相同的情况下，移动次数的期望值是多少？的期望值是多少？11) 1(11niisinnE2nList

14、Delete功能功能原型：Status ListDelete( SqList &L, int i, ElemType &e)作用：取出线性表L的第i个数据元素的值，并删除ListDelete功能功能逻辑结构的变化 (a1, , ai-1, ai, ai+1, an) (a1, , ai-1, ai+1, , an)ListDelete功能功能存储结构的变化a1 a2 a4 a5 a6a1 a2 a3 a4 a5 a6 ListDelete(L, 3, e)6length5lengtheList Delete功能功能过程：1、判断i的合法性2、取值3、挪动4、length-Lis

15、tDeletei的合法性的合法性L7100a1 a2 a3 a4 a5 a6 a71i7一般的 1ilengthListDelete挪动挪动a3a4a4a5a5a6ak-1=akk=i+1 lengtha1 a2 a4 a5 a6a1 a2 a3 a4 a5 a6 6length5lengthListDelete挪动挪动p=L.elem + (i-1); e=*p;q=L.elem + L.length-1;for(+p; p=q; p+) *(p-1) =*p;方法一：移动指针方法一：移动指针p指向了aiq开始时指向了alengthp指向了ai+1ListDelete挪动挪动方法二：数组元素

16、j=i;while(j=L.length-1) L.elemj-1=L.elemj; j+;ak-1=akk=i+1 lengthListDeleteStatus ListDelete(SqList &L, int i, ElemType &e) if( 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.elemi-1; for(int j=i;j=L.length-1;j+) L.el

17、emj-1= L.elemj;-L.length;ListDelete1、在什么情况下，移动次数最少，最少移动次数是、在什么情况下，移动次数最少，最少移动次数是多少？多少？2、在什么情况下，移动次数最多，最多移动次数是、在什么情况下，移动次数最多，最多移动次数是多少？多少？3、在删除每个位置的概率相同的情况下，移动次数、在删除每个位置的概率相同的情况下，移动次数的期望值是多少？的期望值是多少？nidlinnE1)(121nListMerge功能功能原型：Status ListMerge( SqList &La, SqList Lb)作用：把Lb中的数据元素添加到La的表尾留意：不破坏L

18、b表ListMerge功能功能a1 a2 a3 a4 a5 a6b1 b2 b3 LaLbb1b2b3ListMerge功能功能过程：1、取出Lb的一个数据元素bi2、把bi插入到La的表尾3、重复1-2，使得i=1, 2, Lb.lengthListMergeStatus ListMerge(SqList &La, SqList Lb)for(int i=1; i=Lb.length; i+)GetItem(Lb, i, e);code=ListInsert(La, La.length+1, e);return(OK);if(code != OK) return(ERROR);Lis

19、tMergeStatus ListMerge(SqList &La, SqList Lb)For (int i=1; i=Lb.length; i+)La.elemLa.length=Lb.elemi-1; La.length+;return(OK);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.leng

20、th+Lb.length; ListMerge功能功能原型：Status ListMerge( SqList La, SqList Lb, SqList &Lc)作用：把有序表La和Lb合并得到一个新的有序表La: a1 a2 a3 amLb: b1 b2 b3 bnLc: c1 c2 c3 cm+nci=aj or ci=bkListMerge功能功能1 3 6 10 2 8 9 LaLb 1 2 3 6 8 9 10LcListMerge分析分析 1 3 6 10 11 2 8 9 LaLb Lapapb12368910papapapbpbpb11papaListMerge分析分析分析：1、首先建立空表Lc2、从La和Lb中余下未处理的数据元素中选取最小的一个e3、把e插入表尾4、反复 n+m次2和3ListMerge 分析分析1、首先建立空表LcInitList(Lc);2、pa和pb分别表示La和Lb中余下未处理的第一个数据元素初始时pa=1, pb=1）GetItem(La, pa, Ea); GetItem(Lb, pb, Eb); if(EaEb) e=Ea; pa+;elsee=Eb;pb+;ListM