数据结构 线性表.docx

上传人:b****4 文档编号:13910296 上传时间:2023-06-19 格式:DOCX 页数:28 大小:22.17KB
下载 相关 举报
数据结构 线性表.docx_第1页
第1页 / 共28页
数据结构 线性表.docx_第2页
第2页 / 共28页
数据结构 线性表.docx_第3页
第3页 / 共28页
数据结构 线性表.docx_第4页
第4页 / 共28页
数据结构 线性表.docx_第5页
第5页 / 共28页
数据结构 线性表.docx_第6页
第6页 / 共28页
数据结构 线性表.docx_第7页
第7页 / 共28页
数据结构 线性表.docx_第8页
第8页 / 共28页
数据结构 线性表.docx_第9页
第9页 / 共28页
数据结构 线性表.docx_第10页
第10页 / 共28页
数据结构 线性表.docx_第11页
第11页 / 共28页
数据结构 线性表.docx_第12页
第12页 / 共28页
数据结构 线性表.docx_第13页
第13页 / 共28页
数据结构 线性表.docx_第14页
第14页 / 共28页
数据结构 线性表.docx_第15页
第15页 / 共28页
数据结构 线性表.docx_第16页
第16页 / 共28页
数据结构 线性表.docx_第17页
第17页 / 共28页
数据结构 线性表.docx_第18页
第18页 / 共28页
数据结构 线性表.docx_第19页
第19页 / 共28页
数据结构 线性表.docx_第20页
第20页 / 共28页
亲,该文档总共28页,到这儿已超出免费预览范围,如果喜欢就下载吧!
下载资源
资源描述

数据结构 线性表.docx

《数据结构 线性表.docx》由会员分享,可在线阅读,更多相关《数据结构 线性表.docx(28页珍藏版)》请在冰点文库上搜索。

数据结构 线性表.docx

数据结构线性表

基础理论

结构体内存分配

结构体中的各个字段在内存中的出现的位置时随它们被声明的顺序而依次递增的。

并且第一个字段的首地址等于整个结构体实例的首地址。

说明:

结构体类型是一个类型,就好比int是一个类型一样,它是一个构造类型,独立类型,这个类型的大小就是sizeof(struct)当一种类型作为实参传递后,那么它同一个内置类型传递是一样的(int类型)值传递

对于同种类型的struct,同内置类型一样,可以进行赋值,两个int类型的可以赋值,两个struct同样可以。

期待实验:

综上,结构体变量名不能看作是内存的首地址(inta,谁也没说a是变量的地址,而且感觉&struct是结构体内存的首地址,待实验)

以上实验完成:

&(取地址符号)+结构体名字,就是结构体首地址,就把结构体相成普通变量一样,inta,&a就是变量a的地址.

内存对齐(使的成员变量不是连续排不,增添了一些多余的内存)

1.结构体每个成员相对于结构体首地址的偏移量(offset)都是(这个)成员大小的整数倍,如有需要编译器会在成员之间加上填充字节(internaladding);

例如有以下一个结构体

structex{

inti;

chart;

intn;

}

第1个成员偏移量为0,是int型成员大小4(假设这太机器的整型长度占4个字节)的整数倍。

第2个成员t为char型,他的大小为1,首先假设在成员i和t之间没有填充字节,由于i是整型,占4个字节那么在没有填充之前,第2个成员t相对于结构体的偏移量为4,他是t成员大小1的4倍,符合此条件,所以系统在给结构体第2个成员分配内存时,不会在i和t之间填充字节以到达对齐的目的。

当分配结构体第3个成员n时,首先发现是一个整型数据,大小为4,没有填充之前,n相对于结构体首地址偏移量为:

前面2个成员+填充字节=5,所以当系统发现5不是4(成员大小)的整数倍时,会在成员t之后(或者说n之前)填充3个字节,以使n的偏移量到达8而成为4的整数倍。

这样这个结构体占用内存情况暂时为4+1+3+4。

2.结构体的总大小为结构体最宽基本类型成员大小的整数倍,如有需要编译器会在最末一个成员之后加上填充字节(trailingpadding)。

上面的结构体内存分配以后还要看是否满足此条件,假设在最末一个成员之后不需填充字节数,那么这个结构体的大小为12。

而ex结构体中最宽基本类型成员为int,大小为4,12为4的整数倍,所以无须再在最末一个成员之后加上填充字节了。

所以sizeof(ex)=12;

如果一个结构体如下所示structex1{

inti;

chart;

intn;

charadd;

}

那么sizeof(ex1)=16;原因就是在最后一个成员之后填充了3个字节。

3.还有一个额外的条件:

结构体变量的首地址能够被其最宽基本类型成员的大小所整除;

4.对于结构体成员属性中包含结构体变量的复合型结构体再确定最宽基本类型成员时,应当包括复合类型成员的子成员。

但在确定复合类型成员的偏移位置时则是将复合类型作为整体看待。

2.函数的参数传递

形参:

只是在被调用时临时分配内存,调用结束后,释放内存,(值传递,一般传递都属于这种,包括结构体,也只是临时分配了一块内存)

实参:

无论实参是什么类型(包括指针类型),在进行调用时,它必须有确定的值(如果使用指针,必须分配内存或者指向正确的内存地址)

单向传递:

实参->形参

函数的首地址:

函数名

数组的首地址:

数组名

结构体的首地址:

不是结构体名,而是&结构体名字.

指针传递的是内存地址,例如将函数首地址传递,则就是指向这个函数,(如果要想指向这个结构体,就必须找到结构体的首地址,如上待实验)

逻辑结构

线性表:

顾名思义是逻辑上连续的一组先性单元的集合

这样的逻辑结构:

在计算机中有两种对应的存储结构(顺序表,链表)

顺序表:

(物理相邻或者相隔固定参数)

特点:

逻辑结构的位序明显,可以随机存取,插入/删除操作困难.

一般利用高级语言数组实现.

顺序表定义:

typedefstruct{

ElemType*elem;//存储空间首地址

intlength;//当前长度

intlistsize;//当前分配存储的容量(以sizeof(ElemType)为单位)

}SqList;

借助高级语言数组定义:

typedefstruct{

intdata[LISTSiZE];//listsize之前的#define定义

intlength;//当前长度

}SqList;

链表:

通过指针实现

特点:

逻辑结构的位序不明显,必须按照顺序查找,插入/删除操作不需要移动元素.

一般利用指针实现.

头指针:

指示链表中第一个结点的存储位置(如果有头结点,则指向头结点)

头结点:

第一个存储结点之前添加一个结点(为了方便操作一致性,插入操作)

首结点:

真正存储元素的第一个结点.

单链表定义:

typedefstructLNode{

ElemTypedata;

structLNode*next;

}LNode,*LinkList;

头结点的作用说明,如下例子:

//单链表的插入操作(建立单链表,逆序)

voidCreateList_L(LinkListl,intn){

l=(LinkList)malloc(sizeof(LNode));//头结点

l->next=NULL;

for(i=n;i>0;--i){

p=(LinkList)malloc(sizeof(LNode));//生成新结点

scanf(&p->data);

p->next=l->next;

l->next=p;//逆序插入

}

}

循环链表定义:

(循环链表也是个单链表,定义同单链表,只是表尾指针不为NULL,而是指向头结点,判断时注意)

双向链表定义:

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;//指向前驱

structDuLNode*next;//指向后继

}DuLNode,*DuLinkList;

实例推荐

1.(2.19练习册)

[cpp]viewplaincopyprint?

#include"stdio.h"

1#include"alloc.h"

2#include"stdlib.h"

3

4typedefstructLNode{

5intdata;/*数据存储*/

6structLNode*next;/*后继指针*/

7}LNode,*LinkList;

8

9

10/*创建链表*/

11voidCreateLinkList(LinkListl,intn)

12{

13inti;

14LinkListp=NULL;

15/*l=(LinkList)malloc(sizeof(LNode));建立头结点*/

16l->next=NULL;

17for(i=n;i>0;i--){

18p=(LinkList)malloc(sizeof(LNode));

19p->data=i*2;

20p->next=l->next;

21l->next=p;

22}

23}

24

25

26/*显示链表*/

27voidShowLinkList(LinkListl)

28{

29LinkListp;

30p=l->next;

31while(p){

32printf("%d,",p->data);

33p=p->next;

34}

35printf("\n");

36}

37

38/*删除操作*/

39voidDelLinkList(LinkListl,intmink,intmaxk)

40{

41LinkListp,q;

42q=l;

43p=l->next;

44while(p){

45if(p->data>=mink&&p->data<=maxk){

46q->next=p->next;

47free(p);

48}

49else{

50q=p;

51}

52p=q->next;

53

54}

55}

56

57intmain()

58{

59LinkListm;

60m=(LinkList)malloc(sizeof(LNode));/*头结点,分配内存空间*/

61CreateLinkList(m,10);

62ShowLinkList(m);

63DelLinkList(m,10,20);

64ShowLinkList(m);

65getchar();

66getchar();

67}

2.(2.22练习册)

[cpp]viewplaincopyprint?

68/*Thisprogramforthe2.22(parctice)

69**Author:

kevin

70**Date:

2012/02/17

71*/

72

73#include"stdio.h"

74#include"stdlib.h"

75#include"alloc.h"

76

77typedefstructLNode{

78intdata;

79structLNode*next;

80}LNode,*LinkList;

81

82

83/*CreateLinkList*/

84voidCreateLinkList(LinkListl,intn)

85{

86inti;

87LinkListp=NULL;

88l->next=NULL;

89for(i=0;i

90p=(LinkList)malloc(sizeof(LNode));

91p->data=i*2;

92p->next=l->next;

93l->next=p;

94}

95}

96

97/*showLinklist*/

98voidShowLinkList(LinkListl)

99{

100LinkListp;

101p=l->next;

102while(p){

103printf("%d,",p->data);

104p=p->next;

105}

106printf("\n");

107}

108

109/*directchange,onlychangepointer*/

110voidNizhi(LinkListl)

111{

112LinkListp,q,r;

113q=l;

114p=l->next;

115r=p->next;

116while(p){

117if(q==l){

118p->next=NULL;

119}

120else{

121p->next=q;

122}

123q=p;

124p=r;

125r=r->next;

126

127}

128l->next=q;

129}

130

131intmain()

132{

133LinkListm;

134m=(LinkList)malloc(sizeof(LNode));

135CreateLinkList(m,10);

136ShowLinkList(m);

137Nizhi(m);

138ShowLinkList(m);

139getchar();

140}

3.(2.24练习册)

[cpp]viewplaincopyprint?

141/*Thisprogramisfor2.24(practice)

142**Author:

kevin

143**Date:

2012/02/17

144*/

145

146#include"stdio.h"

147#include"stdlib.h"

148#include"alloc.h"

149

150typedefstructLNode{

151intdata;

152structLNode*next;

153}LNode,*LinkList;

154

155

156/*CreateLinkList*/

157voidCreateLinkList(LinkListl,int*a,intn)

158{

159inti;

160LinkListp=NULL;

161l->next=NULL;

162for(i=0;i

163p=(LinkList)malloc(sizeof(LNode));

164p->data=*(a+i);

165p->next=l->next;

166l->next=p;

167}

168}

169

170/*showLinklist*/

171voidShowLinkList(LinkListl)

172{

173LinkListp;

174p=l->next;

175while(p){

176printf("%d,",p->data);

177p=p->next;

178}

179printf("\n");

180}

181

182/*Thefirstchangetheposition*/

183voidNizhi(LinkListl)

184{

185LinkListp,q,r;

186q=l;

187p=l->next;

188r=p->next;

189while(p){

190if(q==l){

191p->next=NULL;

192}

193else{

194p->next=q;

195}

196q=p;

197p=r;

198r=r->next;

199

200}

201l->next=q;

202}

203

204/*Sort*/

205voidSortLinkList(LinkLista,LinkListb,LinkListc)

206{

207LinkListp,q,r;

208p=a->next;

209q=b->next;

210r=c

211;

212while(p&&q){

213if(p->data>=q->data){

214r->next=p;

215r=p;

216p=p->next;

217}

218else{

219r->next=q;

220r=q;

221q=q->next;

222}

223

224}

225if(p){

226r->next=p;

227}

228if(q){

229r->next=q;

230}

231}

232

233

234intmain()

235{

236intdata1[8]={20,15,12,9,8,6,3,1};

237intdata2[7]={14,12,10,8,6,4,2};

238LinkListm,n,lm;

239m=(LinkList)malloc(sizeof(LNode));

240n=(LinkList)malloc(sizeof(LNode));

241lm=(LinkList)malloc(sizeof(LNode));

242CreateLinkList(m,data1,8);

243CreateLinkList(n,data2,7);

244ShowLinkList(m);

245ShowLinkList(n);

246Nizhi(m);

247Nizhi(n);

248SortLinkList(m,n,lm);

249ShowLinkList(lm);

250getchar();

251

252}

4.(2.30练习册)

[cpp]viewplaincopyprint?

253/*Thisprogramisfor2.30(practice)

254**Author:

kevin

255**Date:

2012/02/17

256*/

257

258

259#include"stdio.h"

260#include"alloc.h"

261#include"stdlib.h"

262

263typedefstructLNode{

264intdata;

265structLNode*next;

266}LNode,*LinkList;

267

268

269

270/*CreateLinkList*/

271voidCreateLinkList(LinkListl,int*a,intn)

272{

273inti;

274LinkListp=NULL;

275l->next=NULL;

276for(i=0;i

277p=(LinkList)malloc(sizeof(LNode));

278p->data=*(a+i);

279p->next=l->next;

280l->next=p;

281}

282}

283

284/*showLinklist*/

285voidShowLinkList(LinkListl)

286{

287LinkListp;

288p=l->next;

289while(p){

290printf("%d,",p->data);

291p=p->next;

292}

293printf("\n");

294}

295

296/*deletethedifferencebetweentwolinklist*/

297voidDelDifferece(LinkLista,LinkListb)

298{

299LinkListp,q,r;

300p=a->next;

301q=b->next;

302r=a;

303while(p&&q){

304if(p->data==q->data){

305r=p;

306p=p->next;

307q=q->next;

308}

309elseif(p->data>q->data){

310q=q->next;

311}

312else{

313r->next=p->next;

314free(p);

315p=r->next;

316}

317}

318

319}

320

321/*deletethesamebetweentwolinklist*/

322voidDelSame(LinkLista,LinkListb)

323{

324LinkListp,q,r;

325p=a->next;

326q=b->next;

327r=b;

328while(p&&q){

329if(p->data==q->data){

330r->next=q->next;

331free(q);

332q=r->next;

333p=p->next;

334}

335elseif(p->data>q->data){

336r=q;

337q=q->next;

338}

339else{

340p=p->next;

341}

342}

343}

344

345

346intmain()

347{

348intdata1[8]={20,15,12,9,8,6,3,1};

349intdata2[7]={14,12,10,8,6,4,2};

350intdata3[10]={20,19,18,17,16,15,14,13,12,11};

351LinkListla,lb,lc;

352la=(LinkList)malloc(sizeof(LNode));

353lb=(LinkList)malloc(sizeof(LNode));

354lc=(LinkList)malloc(sizeof(LNode));

355CreateLinkList(la,data1,8);

356CreateLinkList(lb,data2,7);

357CreateLinkList(lc,data3,10);

358ShowLinkList(la);

359ShowLinkList(lb);

360ShowLinkList(lc);

361printf("--------------TheResultis-------------\n");

362DelDifferece(la,lb);

363ShowLinkList(la);

364DelSame(la,lc);

365ShowLinkList(lc);

366getchar();

367

368}

5.(2.33练习册)

[cpp]viewplaincopyprint?

369/*Thisprogramisfor2.33(practice)

370**Author:

kevin

371**Date:

2012/02/17

372*/

373

374

375#include"stdio.h"

376#include"stdlib.h"

377#include"alloc.h"

378

379typedefstructLNode{

380chard

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 经管营销 > 经济市场

copyright@ 2008-2023 冰点文库 网站版权所有

经营许可证编号:鄂ICP备19020893号-2