◆2.11② 設順序表l中的資料元素遞增有序。
試寫一演算法,將x插入到l的適當位置上,並保
持該表的有序性。
要求實現下列函式:
void insertorderlist(sqlist &l, elemtype x)
/* 在有序的順序表 l 中保序插入資料元素 x */
順序表型別定義如下:
typedef struct sqlist;
void insertorderlist(sqlist &l, elemtype x)
// 在有序的順序表 l 中保序插入資料元素 x
l.elem[i]=x;
l.length+=1;
}◆2.12③ 設a=(a1,…,am)和b=(b1,…,bn)均為有序順序表,
a'和b'分別為a和b中除去最大共同字首後的子表(例如,
a=(x,y,y,z,x,z),b=(x,y,y,z,y,x,x,z),則兩者中最大
的共同字首為(x,y,y,z), 在兩表中除去最大共同字首後
的子表分別為a'=(x,z)和b'=(y,x,x,z))。若a'=b'=空表,
則a=b;若a'=空表,而b'≠ 空表,或者兩者均不為空表,
且a'的首元小於b'的首元,則ab。試寫乙個比
較a和b大小的演算法。(注意:在演算法中,不要破壞原表a
和b,也不一定先求得a'和b'才進行比較)。
要求實現下列函式:
char ***pare(sqlist a, sqlist b);
/* 比較順序表a和b, */
/* 返回'<', 若a若a=b; */
>', 若a>b */
順序表型別定義如下:
typedef struct sqlist;
char ***pare(sqlist a, sqlist b)
// 比較順序表a和b,
// 返回'<', 若a若a=b;
>', 若a>b
2.13② 試寫一演算法在帶頭結點的單鏈表結構上實現線性表操作
locate(l,x)。
實現下列函式:
linklist locate(linklist l, elemtype x);
// if 'x' in the linked list whose head node is pointed
// by 'l', then return pointer pointing node 'x',
// otherwise return 'null'
單鏈表型別定義如下:
typedef struct lnode lnode, *linklist;
linklist locate(linklist &l, elemtype x)
// if 'x' in the linked list whose head node is pointed
// by 'l', then return pointer ha pointing node 'x',
// otherwise return 'null'
return p;
}2.14② 試寫一演算法在帶頭結點的單鏈表結構上實現線性表
操作length(l)。
實現下列函式:
int length(linklist l);
// return the length of the linked list
// whose head node is pointed by 'l'
單鏈表型別定義如下:
typedef struct lnode lnode, *linklist;
int length(linklist l)
// return the length of the linked list
// whose head node is pointed by 'l'
return i;
}2.17② 試寫一演算法,在無頭結點的動態單鏈表上實現
線性表操作insert(l,i,b),並和在帶頭結點的動態單
鍊錶上實現相同操作的演算法進行比較。
實現下列函式:
void insert(linklist &l, int i, elemtype b);
單鏈表型別定義如下:
typedef struct lnode lnode, *linklist;
void insert(linklist &l, int i, elemtype b)
if(i!=0&&i!=1)
if(i==1)
}2.18② 同2.17題要求。試寫一演算法,
實現線性表操作delete(l,i)。
實現下列函式:
void delete(linklist &l, int i);
單鏈表型別定義如下:
typedef struct lnode lnode, *linklist;
void delete(linklist &l, int i)
if(i!=0&&i!=1)
if(i==1)
}2.20② 同2.19題條件,試寫一高效的演算法,刪除表中所
有值相同的多餘元素 (使得操作後的線性表中所有元素的
值均不相同) 同時釋放被刪結點空間,並分析你的演算法的
時間複雜度。
實現下列函式:
void purge(linklist &l);
單鏈表型別定義如下:
typedef struct lnode lnode, *linklist;
void purge(linklist &l)
else
p=p->next;
}}◆2.21③ 試寫一演算法,實現順序表的就地逆置,
即利用原表的儲存空間將線性表(a1,a2,…,an)
逆置為(an,an-1,…,a1)。
實現下列函式:
void inverse(sqlist &l);
順序表型別定義如下:
typedef struct {
資料結構和作業系統
資料結構 研究生入學考試學習大綱 作業系統 1 作業系統引論 1 1 作業系統的目標 作用和型別 1 2 作業系統的發展與分類 1 3 作業系統的功能與組成 1 4 市場上常用的作業系統的介紹 2 程序的描述與控制 2 1 程序的描述 2 1 1 程序的定義 2 1 2 程序的狀態 2 2 程序的控...
資料結構作業系統80題
免費版 1.16 試寫一演算法,如果三個整數x,y和z 的值不是依次非遞增的,則通過交換,令其為 非遞增。要求實現下列函式 void descend int x,int y,int z 按從大到小順序返回x,y和z的值 void descend int x,int y,int z 按從大到小順序返回...
資料結構作業系統第五章答案
k n else if a.data k i else if k a.tu while n b.tu else while k a.tu c.mu a.mu c.nu a.nu c.tu p 1 return true 5.23 三元組表的一種變型是,從三元組表中去掉 行下標域得到二元組表,另設乙個...