-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
2253 lines (955 loc) · 142 KB
/
Copy pathindex.html
File metadata and controls
2253 lines (955 loc) · 142 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html class="theme-next muse use-motion" lang="zh-Hans">
<head><meta name="generator" content="Hexo 3.8.0">
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="theme-color" content="#222">
<meta http-equiv="Cache-Control" content="no-transform">
<meta http-equiv="Cache-Control" content="no-siteapp">
<link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css">
<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css">
<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">
<link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">
<meta name="keywords" content="Hexo, NexT">
<meta property="og:type" content="website">
<meta property="og:title" content="进化">
<meta property="og:url" content="brczo.github.io/index.html">
<meta property="og:site_name" content="进化">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="进化">
<script type="text/javascript" id="hexo.configurations">
var NexT = window.NexT || {};
var CONFIG = {
root: '/',
scheme: 'Muse',
version: '5.1.4',
sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
fancybox: true,
tabs: true,
motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
duoshuo: {
userId: '0',
author: '博主'
},
algolia: {
applicationID: '',
apiKey: '',
indexName: '',
hits: {"per_page":10},
labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
}
};
</script>
<link rel="canonical" href="brczo.github.io/">
<title>进化</title>
</head>
<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">
<div class="container sidebar-position-left
page-home">
<div class="headband"></div>
<header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-wrapper">
<div class="site-meta ">
<div class="custom-logo-site-title">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<span class="site-title">进化</span>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<p class="site-subtitle"></p>
</div>
<div class="site-nav-toggle">
<button>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
</button>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section">
<i class="menu-item-icon fa fa-fw fa-home"></i> <br>
首页
</a>
</li>
<li class="menu-item menu-item-tags">
<a href="/tags/" rel="section">
<i class="menu-item-icon fa fa-fw fa-tags"></i> <br>
标签
</a>
</li>
<li class="menu-item menu-item-categories">
<a href="/categories/" rel="section">
<i class="menu-item-icon fa fa-fw fa-th"></i> <br>
分类
</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section">
<i class="menu-item-icon fa fa-fw fa-archive"></i> <br>
归档
</a>
</li>
</ul>
</nav>
</div>
</header>
<main id="main" class="main">
<div class="main-inner">
<div class="content-wrap">
<div id="content" class="content">
<section id="posts" class="posts-expand">
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="brczo.github.io/2019/12/03/tinyhttp源码分析/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="brczo">
<meta itemprop="description" content>
<meta itemprop="image" content="/images/avatar.gif">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="进化">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2019/12/03/tinyhttp源码分析/" itemprop="url">tinyhttpd源码分析</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2019-12-03T19:46:56+08:00">
2019-12-03
</time>
</span>
<span class="post-category">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/c-c/" itemprop="url" rel="index">
<span itemprop="name">c/c++</span>
</a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="头文件"><a href="#头文件" class="headerlink" title="头文件"></a>头文件</h2><p>tinyhttpd.h头文件。源码阅读方式 main->startup->accept_request->execute_cgi</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br></pre></td><td class="code"><pre><span class="line">#include <stdio.h></span><br><span class="line">#include <sys/socket.h></span><br><span class="line">#include <sys/types.h> </span><br><span class="line">#include <netinet/in.h></span><br><span class="line">#include <arpa/inet.h></span><br><span class="line">#include <unistd.h></span><br><span class="line">#include <ctype.h></span><br><span class="line">#include <strings.h></span><br><span class="line">#include <string.h></span><br><span class="line">#include <sys/stat.h></span><br><span class="line">#include <pthread.h></span><br><span class="line">#include <sys/wait.h></span><br><span class="line">#include <stdlib.h></span><br><span class="line">#include <stdint.h></span><br><span class="line"></span><br><span class="line">#define ISspace(x) isspace((int)(x))</span><br><span class="line"></span><br><span class="line">#define SERVER_STRING "Server: jdbhttpd/0.1.0\r\n"</span><br><span class="line">#define STDIN 0</span><br><span class="line">#define STDOUT 1</span><br><span class="line">#define STDERR 2</span><br><span class="line"></span><br><span class="line">处理从套接字上监听到的一个HTTP请求，在这里可以很大一部分地体现服务器处理请求流程</span><br><span class="line">void accept_request(void *);</span><br><span class="line"></span><br><span class="line">返回给客户端这是个错误请求，HTTP状态码 400 BAD_REQUEST</span><br><span class="line">void bad_request(int);</span><br><span class="line"></span><br><span class="line">读取服务器上某个文件写到socket套接字</span><br><span class="line">void cat(int, FILE *);</span><br><span class="line"></span><br><span class="line">主要处理发生在执行cgi程序时出现的错误</span><br><span class="line">void cannot_execute(int);</span><br><span class="line"></span><br><span class="line">把错误信息写到perror并退出</span><br><span class="line">void error_die(const char *);</span><br><span class="line"></span><br><span class="line">运行cgi程序的处理，也是个主要函数</span><br><span class="line">void execute_cgi(int, const char *, const char *, const char *);</span><br><span class="line"></span><br><span class="line">读取套接字的一行，把回车换行等情况都统一为换行符结束</span><br><span class="line">int get_line(int, char *, int);</span><br><span class="line"></span><br><span class="line">把HTTP响应的头部写到套接字</span><br><span class="line">void headers(int, const char *);</span><br><span class="line"></span><br><span class="line">主要处理找不到请求时的情况</span><br><span class="line">void not_found(int);</span><br><span class="line"></span><br><span class="line">调用cat把服务器文件返回给浏览器</span><br><span class="line">void serve_file(int, const char *);</span><br><span class="line"></span><br><span class="line">初始化httpd服务，包括建立套接字，绑定端口，进行监听等</span><br><span class="line">int startup(u_short *);</span><br><span class="line"></span><br><span class="line">返回给浏览器表明收到的HTTP请求所用的method不被支持</span><br><span class="line">void unimplemented(int);</span><br></pre></td></tr></table></figure>
<hr>
<h2 id="main函数"><a href="#main函数" class="headerlink" title="main函数"></a>main函数</h2><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">int main(void){</span><br><span class="line"> int server_sock = -1;</span><br><span class="line"> u_short port = 4000; //u_short = unsigned short</span><br><span class="line"> int client_sock = -1;</span><br><span class="line"> struct sockaddr_int client_name; //IPv4地址结构 用于接受客户端的地址数据</span><br><span class="line"> socklen_t client_name_len = sizeof(client_name); //socket_t 实为unsigned int</span><br><span class="line"> pthread_t newthread; //pthread结构</span><br><span class="line"></span><br><span class="line"> server_sock = startup(&port);</span><br><span class="line"> printf("httpd running on port %\n", port);</span><br><span class="line"></span><br><span class="line"> while(1){</span><br><span class="line"> //需强制转为sockaddr通用结构 sockadd_int -> sockaddr </span><br><span class="line"> //client_sock 唯一的标识被接受的连接</span><br><span class="line"> client_sock = accept(server_sock, (struct sockaddr *)&client_name, &client_name_len);</span><br><span class="line"> if(client_sock == -1)</span><br><span class="line"> error_die("accept");</span><br><span class="line"> if(pthread_create(&newthread, NULL, (void *)accept_request, (void *)(intptr_t)client_sock) != 0)</span><br><span class="line"> perror("pthread_create");</span><br><span class="line"> }</span><br><span class="line"> close(server_sock);</span><br><span class="line"> return 0;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>pthread_create不是linux系统默认库，所以在试用pthread_create创建线程时，<br>需要在加译中加-lphread参数： eg: gcc -o test -lphread test.c<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">/**</span><br><span class="line"> @param thread 指向线程标识符的指针</span><br><span class="line"> @param attr 用来设置线程属性</span><br><span class="line"> @param 线程运行函数的起始位置</span><br><span class="line"> @param arg 运行函数的参数</span><br><span class="line">**/</span><br><span class="line">int phread_create(pthread_t* thread, const pthread_attr_t *attr,</span><br><span class="line"> void *(*start_routine)(void *), void *arg);</span><br></pre></td></tr></table></figure></p>
<h2 id="accept-request函数"><a href="#accept-request函数" class="headerlink" title="accept_request函数"></a>accept_request函数</h2><hr>
<h2 id="start-up函数"><a href="#start-up函数" class="headerlink" title="start_up函数"></a>start_up函数</h2><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">int start_up(u_short *port){</span><br><span class="line"> int httpd = 0;</span><br><span class="line"> int on = 1;</span><br><span class="line"> struct sockaddr_in name;</span><br><span class="line"></span><br><span class="line"> httpd = socket(PF_INET, SOCK_STREAM, 0); //PF_INET TCP/IPv6协议族</span><br><span class="line"> if(httpd == -1)</span><br><span class="line"> error_die("creating socket failed!");</span><br><span class="line"> memset(&name, 0, sizeof(name));</span><br><span class="line"> name.sin_family = AF_INET; //TCP/IPv4地址族</span><br><span class="line"> name.sin_port = htons(*port);</span><br><span class="line"> name.sin_addr.s_addr = htonl(INADDR_ANY); //sin_addr为IPv4结构体, s_addr为IPv4地址</span><br><span class="line"> if((setsockopt(httpd, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on))) < 0){</span><br><span class="line"> error_die("setsockopt failed");</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="brczo.github.io/2019/11/30/c++Primer/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="brczo">
<meta itemprop="description" content>
<meta itemprop="image" content="/images/avatar.gif">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="进化">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2019/11/30/c++Primer/" itemprop="url">c++ primer</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2019-11-30T23:23:00+08:00">
2019-11-30
</time>
</span>
<span class="post-category">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/c-c/" itemprop="url" rel="index">
<span itemprop="name">c/c++</span>
</a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h2><p>c++ 是 c 语言的超集<br>面向对象编程: OOP不像过程性编程那样, 试图使问题满足语言的过程化方法,而是试图让语言来满足问题的要求.<br>c++和通用编程: 通用指的是创建独立于类型的代码.</p>
<h2 id="复习题"><a href="#复习题" class="headerlink" title="复习题"></a>复习题</h2><p>1.C++程序的模块叫什么?<br>函数</p>
<p>2.下面的预处理器编译指令是做什么用的?</p>
<p>#include <iostream><br>该预处理器编译指令导致预处理器将iostream文件的内容添加到程序中.</iostream></p>
<p>3.下面的语句是做什么的?<br>using namespace std;<br>这个using编译指令使得std命名空间下的所有名称都可以用.</p>
<p>4.什么语句可以用来打印短语“Hello world”, 然后开始新的一行<br>cout << “hello world” << endl;</p>
<p>7.什么语句可以用来将从键盘输入的值读入变量cheeses中?<br>cin >> cheeses;</p>
<p>8.什么语句可以用来打印“We have X varieties of cheese”, 用cheeses当前变量的值来替代X?<br>cout << “We have “ << cheeses << “varieties of cheese” << endl;</p>
<p>10.定义函数时,什么情况下不必使用关键字return?<br>当没有返回值或不需要返回值时.</p>
<h2 id="short、int和long"><a href="#short、int和long" class="headerlink" title="short、int和long"></a>short、int和long</h2><ul>
<li>short至少16位</li>
<li>int至少与short一样长</li>
<li>long至少32位, 且至少与int一样长</li>
</ul>
<h2 id="使用new和delete时-应遵循一下规则"><a href="#使用new和delete时-应遵循一下规则" class="headerlink" title="使用new和delete时,应遵循一下规则:"></a>使用new和delete时,应遵循一下规则:</h2><ul>
<li>不要使用delete来释放不是new分配的内存</li>
<li>不要使用delete释放同一个内存块两次</li>
<li>如果使用new[]为数组分配内存, 则应使用delete[]来释放</li>
<li>如果使用new[]为一个实体分配内存, 则应使用delete(没有方括号)来释放</li>
<li>对空值指针应用delete是安全的</li>
</ul>
<h2 id="引用是已定义变量的别名"><a href="#引用是已定义变量的别名" class="headerlink" title="引用是已定义变量的别名"></a>引用是已定义变量的别名</h2><h2 id="应尽可能使用const"><a href="#应尽可能使用const" class="headerlink" title="应尽可能使用const"></a>应尽可能使用const</h2><ul>
<li>使用const可以避免无意中修改数据的编程错误</li>
<li>使用const是函数能够处理const和非const实参, 否则将只能接受非const参数</li>
<li>使用const引用使函数能够正确生成并使用临时变量</li>
</ul>
<h2 id="何时使用引用参数"><a href="#何时使用引用参数" class="headerlink" title="何时使用引用参数"></a>何时使用引用参数</h2><p>使用引用参数的主要原因有两个:</p>
<ul>
<li>程序员能够修改调用函数中数据对象</li>
<li>通过传递饮用而不是整个数据对象, 可以提高程序的运行速度</li>
</ul>
<h2 id="对于使用传递的值而不做修改的函数"><a href="#对于使用传递的值而不做修改的函数" class="headerlink" title="对于使用传递的值而不做修改的函数:"></a>对于使用传递的值而不做修改的函数:</h2><ul>
<li>如果对象很小, 如内置数据类型或小型结构,则按值传递</li>
<li>如果数据对象是数组, 则使用指针, 因为这是唯一的选择,并将指针声明为指向const的指针.</li>
<li>如果数据对象是较大的结构, 则使用const指针或const引用,以提高程序的效率.这样可以节省复制结构所需的时间和空间.</li>
<li>如果数据对象是类对象, 则使用const引用. 类设计的语言常常要求使用引用,这是c++新增引用特性的主要原因.因此, 传递类对象的标准方式是引用.</li>
</ul>
<h2 id="对于修改调用函数中数据的函数"><a href="#对于修改调用函数中数据的函数" class="headerlink" title="对于修改调用函数中数据的函数:"></a>对于修改调用函数中数据的函数:</h2><ul>
<li>如果数据对象是内置函数类型, 则使用指针. </li>
<li>如果数据对象是数组, 则只能用指针.</li>
<li>如果数据对象是结构, 则使用引用或指针</li>
<li>如果数据对象是类对象, 则使用引用.</li>
</ul>
<h2 id="将程序分成三部分"><a href="#将程序分成三部分" class="headerlink" title="将程序分成三部分"></a>将程序分成三部分</h2><ul>
<li>头文件: 包含结构声明和使用这些结构的函数原型</li>
<li>源代码文件: 包含与结构有关的函数的代码</li>
</ul>
<h2 id="template的声明和定义都只能放到-h文件"><a href="#template的声明和定义都只能放到-h文件" class="headerlink" title="template的声明和定义都只能放到.h文件"></a>template的声明和定义都只能放到.h文件</h2>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="brczo.github.io/2019/07/16/数据结构/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="brczo">
<meta itemprop="description" content>
<meta itemprop="image" content="/images/avatar.gif">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="进化">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2019/07/16/数据结构/" itemprop="url">数据结构</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2019-07-16T16:30:05+08:00">
2019-07-16
</time>
</span>
<span class="post-category">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/编程/" itemprop="url" rel="index">
<span itemprop="name">编程</span>
</a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="基本概念和术语"><a href="#基本概念和术语" class="headerlink" title="基本概念和术语"></a>基本概念和术语</h2><p>数据：对客观事物符号的表示，在计算机科学中，是指所有能输入到计算机中并被计算机程序处理的符号的总成。<br>数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。有时一个数据元素可由若干个数据项组成。数据项是是数据的不可分割的最小单位。<br>数据对象：是性质相同的数据元素的集合，是数据的一个子集。<br>数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。</p>
<hr>
<h2 id="线性表"><a href="#线性表" class="headerlink" title="线性表"></a>线性表</h2><p>线性表是最常用且最简单的一种数据结构。线性表是n个数据元素的有限序列。线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除。<br>抽象数据类型线性表的定义</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line">ADT List {</span><br><span class="line"> 数据对象: D = {a[i] | a[i] ∊ ElemSet, i = 1, 2, ...,n n >= 0}</span><br><span class="line"> 数据关系: R1 = { <a[i-1], a[i]>|a[i-1], a[i]∊D, i = 2,...,n }</span><br><span class="line"> 基本操作:</span><br><span class="line"> InitList(&L)</span><br><span class="line"> 操作结果: 构造一个空的线性表L</span><br><span class="line"> DestroyList(&L)</span><br><span class="line"> 初始条件: 线性表L已存在</span><br><span class="line"> 操作结果: 销毁线性表L</span><br><span class="line"> ClearList(&L)</span><br><span class="line"> 初始条件: 线性表L已存在</span><br><span class="line"> 操作结果: 将L重置为空表</span><br><span class="line"> ListEmpty(L)</span><br><span class="line"> 初始条件: 线性表L已存在</span><br><span class="line"> 操作结果: 若L为空表,则返回True,否则返回FALSE</span><br><span class="line"> ListLength(L)</span><br><span class="line"> 初始条件: 线性表L已存在</span><br><span class="line"> 操作结果: 返回L中数据元素个数</span><br><span class="line"> GetElem(L, i, &e)</span><br><span class="line"> 初始条件: 线性表L已存在,1 <= i <= ListLength(L)</span><br><span class="line"> 操作结果: 用e返回L中第i个数据元素的值</span><br><span class="line"> LocateElem(L, e compare())</span><br><span class="line"> 初始条件: 线性表L已存在,compare()是数据元素判定函数</span><br><span class="line"> 操作结果: 返回L中第一个与e满足关系compare()的数据元素的位序.若这样的数据元素不存在,则返回0</span><br><span class="line"> PriorELem(L, cur_e, &pre_e)</span><br><span class="line"> 初始条件: 线性表L已存在</span><br><span class="line"> 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义.</span><br><span class="line"> NextElem(L, cur_e, &next_e)</span><br><span class="line"> 初始条件: 线性表L已存在</span><br><span class="line"> 操作结果: 若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义.</span><br><span class="line"> ListInsert(&L, i, e)</span><br><span class="line"> 初始条件: 线性表L已存在, 1 <= i <= ListLength(L) + 1</span><br><span class="line"> 操作结果: 在L中第i个位置之前插入新的数据元素e,L的长度加1.</span><br><span class="line"> ListDelete(&L, i, &e)</span><br><span class="line"> 初始条件: 线性表L已存在且非空, 1 <= i <= ListLength(L)</span><br><span class="line"> 操作结果: 删除L的第i个数据元素,并用e返回其值,L的长度减1.</span><br><span class="line"> ListTraverse(L, visit())</span><br><span class="line"> 初始条件: 线性表L已存在</span><br><span class="line"> 操作结果: 依次对L的每个数据元素点用函数visit().一旦visit()失败,则操作失败</span><br><span class="line">} ADT List</span><br></pre></td></tr></table></figure>
<p>两个线性表LA和LB分别表示两个集合A和B,求A = A ∪ B.<br>分析: 扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去.只要从线性表LB中依次取得每个数据元素,并依值在线性表LA中进行查访,若不存在,则插入之.<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">#define LIST_INIT_SIZE 100 // 线性表存储空间的初始分配量</span><br></pre></td></tr></table></figure></p>
<hr>
<h2 id="数组与广义表"><a href="#数组与广义表" class="headerlink" title="数组与广义表"></a>数组与广义表</h2><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br></pre></td><td class="code"><pre><span class="line">// ----------- 数组的顺序存储表示 ---------------</span><br><span class="line">#include <stdarg.h> // 提供宏va_start、va_arg和va_end, 用于存储变长参数表</span><br><span class="line">#include <stdbool.h></span><br><span class="line">#include <stdlib.h></span><br><span class="line">#include <stddef.h></span><br><span class="line">#define MAX_ARRAY_DIM 8 //假设数组维数的最大值为8</span><br><span class="line"></span><br><span class="line">typedef struct{</span><br><span class="line"> int *base; // 数组元素基址, 由initArray分配</span><br><span class="line"> int dim; // 数组维数</span><br><span class="line"> int *bounds; // 数组维界基址, 由initArray分配</span><br><span class="line"> int *constants; // 数组映像函数常量基址, 由initArray分配 cn = l, c(i-1) = bi X ci 其中 bi为第i行元素个数</span><br><span class="line">}Array;</span><br><span class="line"></span><br><span class="line">// ----------- 基本操作的函数原型说明 -------------</span><br><span class="line"></span><br><span class="line">// 若维数dim和随后的各维长度合法, 则构造相应的数组A, 并返回ok</span><br><span class="line">bool initArray(Array *a, int dim, ...); //... 表示参数不确定</span><br><span class="line"></span><br><span class="line">// 销毁数组A</span><br><span class="line">bool destroyArray(Array *a);</span><br><span class="line"></span><br><span class="line">// a是n维数组, e为元素变量, 随后是n个下标值, 若各下标不超界,则将e的值赋给指定的a的元素, 并返回ok.</span><br><span class="line">bool value(Array a, int *e, ...);</span><br><span class="line"></span><br><span class="line">// a是n维数组, e为元素变量, 随后是n个下标值, 若下标不超界, 则将e的值赋给所指定的a的元素,并返回ok.</span><br><span class="line">bool assign(Array *a, int e, ...);</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">// ---------------- 基本操作的算法描述 ----------------</span><br><span class="line">bool initArray(Array *a, int dim, ...){</span><br><span class="line"> if(dim < 1 || dim > MAX_ARRAY_DIM) return false;</span><br><span class="line"> a->dim = dim;</span><br><span class="line"> a->bounds = (int*)malloc(dim * sizeof(int));</span><br><span class="line"> if(!a->bounds) exit(0);</span><br><span class="line"> // 若各维长度合法, 则存入a.bounds, 并求出a的元素总数elemtotal</span><br><span class="line"> int elemtotal = 1;</span><br><span class="line"> va_list ap; </span><br><span class="line"> va_start(ap,dim); //以固定参数的地址为起点确定变参的内存起始地址</span><br><span class="line"> for(int i = 0; i < dim; i++){</span><br><span class="line"> a->bounds[i] = va_arg(ap, int); // 得到下一个可变参数的值</span><br><span class="line"> if(a->bounds[i] < 0) return false;</span><br><span class="line"> elemtotal *= a->bounds[i];</span><br><span class="line"> }</span><br><span class="line"> va_end(ap); // 用完必须调用</span><br><span class="line"> a->base = (int*)malloc(elemtotal * sizeof(int));</span><br><span class="line"> if(!a->base) exit(0);</span><br><span class="line"> // 求映像函数的常数ci, 并存入a.constants[i - 1], i = 1 ... dim;</span><br><span class="line"> a->constants = (int*)malloc(dim * sizeof(int));</span><br><span class="line"> if(!a->constants) exit(0);</span><br><span class="line"> a->constants[dim - 1] = 1; // l = 1, 指针的增减以元素的大小为单位</span><br><span class="line"> for(int i = dim - 2; i >= 0; i --){</span><br><span class="line"> a->constants[i] = a->bounds[i + 1] * a->constants[i + 1];</span><br><span class="line"> }</span><br><span class="line"> return true;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">bool destroyArray(Array *a){</span><br><span class="line"> if(!a->base) return false;</span><br><span class="line"> free(a->base); a->base = NULL;</span><br><span class="line"> if(!a->bounds) return false;</span><br><span class="line"> free(a->bounds); a->bounds = NULL;</span><br><span class="line"> if(!a->constants) return false;</span><br><span class="line"> free(a->constants); a->constants = NULL;</span><br><span class="line"> return true;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">bool locate(Array a, va_list ap, int *off){</span><br><span class="line"> // 若ap指示的各下标值合法,则求出该元素在a中相对地址off</span><br><span class="line"> int off = 0, ind;</span><br><span class="line"> for(int i = 0; i < a.dim; i++){</span><br><span class="line"> ind = va_arg(ap, int);</span><br><span class="line"> if(ind < 0 || ind >= a.bounds[i]) return false;</span><br><span class="line"> off += a.constants[i] * ind;</span><br><span class="line"> }</span><br><span class="line"> return true;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">bool value(Array a, int *e, ...){</span><br><span class="line"> // a是n维数组, e为元素变量, 随后是n个下标值. 若各下标不超界, 则e赋值为所指定的a的元素值,并返回ok</span><br><span class="line"> va_list ap;</span><br><span class="line"> int off = 0;</span><br><span class="line"> va_start(ap, e);</span><br><span class="line"> if(!locate(a, ap, &off)) return false;</span><br><span class="line"> *e = *(a.base + off);</span><br><span class="line"> return true;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">bool assign(Array *a, int e, ...){</span><br><span class="line"> va_list ap;</span><br><span class="line"> int off = 0;</span><br><span class="line"> va_start(ap, e);</span><br><span class="line"> if(!locate(*a, ap, &off)) return false;</span><br><span class="line"> *(a->base + off) = e;</span><br><span class="line"> return true;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="三元组顺序表"><a href="#三元组顺序表" class="headerlink" title="三元组顺序表"></a>三元组顺序表</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line">#include <stdio.h></span><br><span class="line">#include <stdlib.h></span><br><span class="line">#include <stdbool.h></span><br><span class="line">#include <stddef.h></span><br><span class="line">#define MAXSIZE 12500 // 假设非零元个数的最大值为12500</span><br><span class="line">typedef struct {</span><br><span class="line"> int i, j; // 该非零元的行下标和列下标</span><br><span class="line"> int e;</span><br><span class="line">}triple;</span><br><span class="line"></span><br><span class="line">typedef struct {</span><br><span class="line"> triple data[MAXSIZE + 1]; // 非零元三元组组表, data[0]未用</span><br><span class="line"> int rn, cn, nzn; // 矩阵的行数、列数和非零元个数</span><br><span class="line">}tSMatrix; </span><br><span class="line"></span><br><span class="line">int transposeSMtrix(tSMatrix m, tSMtrix *t) {</span><br><span class="line"> //采用三元组表存储表示, 求稀疏矩阵m的转置矩阵t.</span><br><span class="line"> t->rn = m.cn; t->cn = m.rn; t->nzn = m.nzn;</span><br><span class="line"> if(t.nzn) {</span><br><span class="line"> int q = 1;</span><br><span class="line"> for(int col = 1; col <= m.rn; col ++){</span><br><span class="line"> for(int nz = 1; z <= m.nzn; nz ++){</span><br><span class="line"> if(m.data[z].j == col){</span><br><span class="line"> t->data[q].i = m.data[z].j; </span><br><span class="line"> t->data[q].j = m.data[z].i;</span><br><span class="line"> t->data[q].e = m.data[z].e;</span><br><span class="line"> q++;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> return true;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">// 改进 快速转置</span><br><span class="line">int fastTransposeSMatrix(tSmatrix m, tSMatrix *t){</span><br><span class="line"> // 采用三元组顺序表存储表示, 求稀疏矩阵m的转置矩阵t</span><br><span class="line"> t->rn = m.cn; t->cn = m.rn; t->nzn = m.nzn;</span><br><span class="line"> int num[m.cn + 1] = {0}, col[nzn + 1];</span><br><span class="line"> if(t.nzn){</span><br><span class="line"> for(int g = 1; g <= m.nzn; ++g) ++num[m.data[g].j]; //求m中每一列含非0元个数</span><br><span class="line"> cpot[1] = 1;</span><br><span class="line"> // 求第col列中第一个非零元在b.data中的序号</span><br><span class="line"> for(int col = 2; col <= m.rn; ++ col) cpot[col] = cpot[col - 1] + num[col - 1];</span><br><span class="line"> int col, q;</span><br><span class="line"> for(int p = 1; p <= m.nzn; ++p){</span><br><span class="line"> col = m.data[p].j; </span><br><span class="line"> q = cpot[col];</span><br><span class="line"> t->data[q].i = m.data[p].j;</span><br><span class="line"> t->data[q].j = m.data[p].i;</span><br><span class="line"> t->data[q].e = m.data[p].e;</span><br><span class="line"> ++cpot[col];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> return true;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="行逻辑链接的顺序表"><a href="#行逻辑链接的顺序表" class="headerlink" title="行逻辑链接的顺序表"></a>行逻辑链接的顺序表</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">typedef struct {</span><br><span class="line"> int i,j;</span><br><span class="line"> int e;</span><br><span class="line">}triple;</span><br><span class="line">typedef struct {</span><br><span class="line"> triple data[MAXSIZE + 1]; // 非零元三元组表</span><br><span class="line"> int rpos[MAXRC + 1]; // 各行的第一个非零元的位置表</span><br><span class="line"> int rn, cn, nzn; // 矩阵的行数、列数和非零元个数</span><br><span class="line">}rLSMatrix;</span><br></pre></td></tr></table></figure>
<h4 id="Q-M-X-N大致可描述如下"><a href="#Q-M-X-N大致可描述如下" class="headerlink" title="Q = M X N大致可描述如下"></a>Q = M X N大致可描述如下</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">Q初始化;</span><br><span class="line">if(Q是非零矩阵){ //逐行求积</span><br><span class="line"> for(int arow = 1; arow <= m.rn; ++ arow){ // 处理m的每一行</span><br><span class="line"> ctemp[] = 0; //累加器清零</span><br><span class="line"> // 计算Q中第arow行的积并存入ctemp[]中; 将ctemp[]中非零元压缩存储到Q.data;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h4 id="Q-M-X-N求精过程"><a href="#Q-M-X-N求精过程" class="headerlink" title="Q = M X N求精过程"></a>Q = M X N求精过程</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">int multSMatrix(rLSMatrix m, rLMatrix n, rLSMatrix *q){</span><br><span class="line"> // 求矩阵乘积Q = M X N, 采用行逻辑链接存储表示</span><br><span class="line"> int ctemp[m.rn + 1] = {0};</span><br><span class="line"> if(m.rn != n.cn) return false;</span><br><span class="line"> q->rn = m.rn; q->cn = m.cn; q->nzn = 0; //Q的初始化</span><br><span class="line"> if(m.nzn * n.nzn != 0) { // Q是非零矩阵</span><br><span class="line"> for(int arow = 1; arow <= m.rn; ++arow){ // 处理m的每一行</span><br><span class="line"> ctemp[] = 0; //当前行各元素累加器清零 </span><br><span class="line"> Q.rpos[arow] = Q.nzn + 1;</span><br><span class="line"> if(arow < m.rn) tp = m.rpos[arow + 1];</span><br><span class="line"> else tp = m.nzn + 1;</span><br><span class="line"> for(p = n.rpos[arow]; p < tp; ++p){ //队当前行中的每一个非零元</span><br><span class="line"> brow = m. data[p].j; //找到对应元在n中的行号</span><br><span class="line"> if(brow < n.rn) t= n.rpos[brow + 1];</span><br><span class="line"> else {t = n.tu + 1;}</span><br><span class="line"> for(q = n.rpos[brow]; q < t; ++1){</span><br><span class="line"> ccol = n.data[q].j; //乘积元素在q中列号</span><br><span class="line"> ctemp[ccol] += m.data[p].e * n.data[q].e;</span><br><span class="line"> }</span><br><span class="line"> } // 求得Q中第crow( = arow)行的非零元</span><br><span class="line"> for(col = 1; ccol <= q->cn; ++ccol){ //压缩存储改行零元素</span><br><span class="line"> if(ctemp[ccol]){</span><br><span class="line"> if(++q.nzn > MAXSIZE) return false;</span><br><span class="line"> q.data[q.nzn] = (arow, ccol, ctemp[ccol]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="十字链表"><a href="#十字链表" class="headerlink" title="十字链表"></a>十字链表</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">typedef struct OLNode{</span><br><span class="line"> int i, j; </span><br><span class="line"> int e;</span><br><span class="line"> struct QLNode * right, *down; // 该非零元所在行表和列继的后继链域</span><br><span class="line">}OLNode; *OLink;</span><br><span class="line"></span><br><span class="line">typedef struct {</span><br><span class="line"> OLink *rhead, *chead; //行和列链表头指针向量基址由createSMatrix分配</span><br><span class="line"> int rn, cn, nzn; </span><br><span class="line">}Cros</span><br></pre></td></tr></table></figure>
<h3 id="广义表的存储结构"><a href="#广义表的存储结构" class="headerlink" title="广义表的存储结构"></a>广义表的存储结构</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">typedef enum {Atom, List}ElemTag; // 0 -》原子, 0 -》 子表</span><br><span class="line">typedef struct GLNode {</span><br><span class="line"> ElemTag tag; //公共部分, 用于区分原子结点和表结点</span><br><span class="line"> union { //原子结点和表结点的联合部分</span><br><span class="line"> AtomType atom; // atom是原子结点的值域, AtomType由用户定义</span><br><span class="line"> struct{struct GLNode *hp, *tp;}ptr; // ptr是表结点的指针域, ptr.hp和ptr.tp分别指向表头和表尾</span><br><span class="line"> };</span><br><span class="line">}*GList; //广义表类型</span><br></pre></td></tr></table></figure>
<h3 id="广义表的扩展线性链表存储表示"><a href="#广义表的扩展线性链表存储表示" class="headerlink" title="广义表的扩展线性链表存储表示"></a>广义表的扩展线性链表存储表示</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">typedef enum{Atom, List}ElemTag;</span><br><span class="line">typedef struct GLNode {</span><br><span class="line"> ELemTag tag; //公共部分, 用于区分原子结点和表结点</span><br><span class="line"> union {</span><br><span class="line"> AtomType atom; //原子结点的值域</span><br><span class="line"> struct GLNode *hp; // 表结点的表头指针</span><br><span class="line"> };</span><br><span class="line"> struct GLNode *tp; // 相当于线性链表的next,指向下一个元素结点</span><br><span class="line">}*GList; //广义表类型GList是一种扩展的线性链表</span><br></pre></td></tr></table></figure>
<h2 id="树的定义与基本术语"><a href="#树的定义与基本术语" class="headerlink" title="树的定义与基本术语"></a>树的定义与基本术语</h2><p>树是n哥结点的有限集. 在任意一棵非空树中: </p>
<ul>
<li>(1)有且仅有一个特定的称为根的结点; </li>
<li>(2)当n > 1时, 其余结点可分为m(m > 0)个互不相交的有限集t1,t2,t3,…,tm,其中每个集合本身又是一棵树, 并且称为根的子树.<br>树的结点包含一个数据元素及若干指向其子树的分支.<br>结点拥有的子树数称为结点的度.<br>度为0的结点称为叶子或终端结点.<br>结点的子树的根称为该结点的孩子,相应的该结点称为孩子的双亲.<br>同一个双亲的孩子之间互称兄弟.<br>结点的祖先是从根到该结点所经分支上的所有结点.反之, 以结点为根的子树中的任一结点都成为该结点的子孙.<br>如果将树中结点的各子树看成从左往右是有次序的,则称该树为有序树,否则称为无序树.<br>森林是m(m>=0)棵互不相交的树的集合. 对树中每个结点而言, 其子树的集合称为森林.</li>
</ul>
<h2 id="二叉树的性质"><a href="#二叉树的性质" class="headerlink" title="二叉树的性质"></a>二叉树的性质</h2><p>二叉树是另一种树型结构, 它的特点是每个结点至多只有两棵子树, 并且, 二叉树的子树有左右之分, 不能随意颠倒.</p>
<ul>
<li><p>在二叉树的第i层上至多有pow(2, i -1)个结点</p>
</li>
<li><p>深度为k的二叉树至多有pow(2, i) - 1个结点</p>
</li>
<li><p>对任何一棵二叉树t, 如果其终端结点(叶子结点)数为n,度为2的结点数为m, 则 n = m + 1;</p>
</li>
<li><p>一棵深度为k且有pow(2, k) - 1个结点的二叉树称为满二叉树.</p>
</li>
<li><p>深度为k的, 有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树编号从1至n的结点一一对应时, 称为完全二叉树.</p>
</li>
<li><p>具有n个结点的完全二叉树的深度为floor(log(n,2)) + 1</p>
</li>
<li><p>如果对一棵有n个结点的完全二叉树(其深度)为floor(log(n,2))+1)的结点按层序编号(从第一层到第floor(log(n,2)) + 1层, 每层从左到右),则对任一结点i(1<= i <= n),有:</p>
<ul>
<li><p>如果i = 1, 则结点i是二叉树的根,无双亲; 如果i > 1,则其双亲parent(i)是结点floor(i/2);</p>
</li>
<li><p>如果2i>n,则结点i无左孩子(结点i为叶子结点); 否则其左孩子LCHILD(i))是结点2i;</p>
</li>
<li>如果2i + 1 > n, 则结点i无右孩子; 否则其右孩子RCHILD(i)是结点2i + 1</li>
</ul>
</li>
</ul>
<h3 id="二叉树的存储结构"><a href="#二叉树的存储结构" class="headerlink" title="二叉树的存储结构"></a>二叉树的存储结构</h3><h4 id="顺序存储结构"><a href="#顺序存储结构" class="headerlink" title="顺序存储结构"></a>顺序存储结构</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">#define MAX_TREE_SIZE 100 // 二叉树的大结点数</span><br><span class="line">typedef TElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点</span><br><span class="line">SqBiTree bt;</span><br></pre></td></tr></table></figure>
<h4 id="链式存储结构"><a href="#链式存储结构" class="headerlink" title="链式存储结构"></a>链式存储结构</h4><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">// ----------- 二叉树的二叉链表存储表示 ------------------</span><br><span class="line">typedef struct BiTNode {</span><br><span class="line"> TElemType data;</span><br><span class="line"> struct BiTNode *lchild, *rchild; // 左右孩子指针</span><br><span class="line">}BiTNode, *BiTree;</span><br><span class="line"></span><br><span class="line">// ----------- 基本操作的函数原型说明 ---------------------</span><br><span class="line"></span><br><span class="line">// 按先序次序输入二叉树中结点的值(一个字符), 空格字符表示空树. 构造二叉树链表表示的二叉树t</span><br><span class="line">int createBiTree(BiTree *t); </span><br><span class="line"></span><br><span class="line">// 采用二叉链表存储结构, visit是对结点操作的应用函数. 先序遍历二叉树t, 对每个结点调用函数visit一次且仅一次,一旦visit失败, 则操作失败</span><br><span class="line">int preOrderTraverse(BiTree t, int (*visit)(ElemType e)); </span><br><span class="line"></span><br><span class="line">// 中序遍历</span><br><span class="line">int inOrderTraverse(BiTree t, int(*visit)(ElemType e));</span><br><span class="line"></span><br><span class="line">// 后序遍历</span><br><span class="line">int postOrderTraverse(BiTree t, int (*visit)(ELemType e));</span><br><span class="line"></span><br><span class="line">// 层序遍历</span><br><span class="line">int levelOrderTraverse(BiTree t, int (*visit)(ELemType e))</span><br></pre></td></tr></table></figure>
<h3 id="二叉树的遍历"><a href="#二叉树的遍历" class="headerlink" title="二叉树的遍历"></a>二叉树的遍历</h3><p>遍历二叉树的递归算法: </p>
<p>先序遍历二叉树的操作定义<br>若二叉树为空, 则空操作</p>
<ul>
<li>访问根结点</li>
<li>先序遍历左子树</li>
<li>先序遍历右子树</li>
</ul>
<p>中序遍历二叉树的操作定义:<br>若二叉树为空, 则空操作</p>
<ul>
<li>中序遍历左子树</li>
<li>访问根结点</li>
<li>中序遍历右子树</li>
</ul>
<p>后序遍历二叉树的操作定义:<br>若二叉树为空, 则空操作,否则:</p>
<ul>
<li>后序遍历左子树</li>
<li>后序遍历右子树</li>
<li>访问根结点</li>
</ul>
<p>先序遍历 递归版<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">int preOrderTraverse(BiTee t, int(*visit)(Elemtype e)){</span><br><span class="line"> //采用二叉链表存储结构, visit是对数据元素操作的应用函数</span><br><span class="line"> //先序遍历二叉树t的递归算法, 对每个数据元素调用函数visit</span><br><span class="line"> //最简单的visit函数是</span><br><span class="line"> // int printElement(TELemType e) { //输出元素e的值</span><br><span class="line"> // printf(e); </span><br><span class="line"> // return 1;</span><br><span class="line"> // }</span><br><span class="line"> if(t) {</span><br><span class="line"> if(visit(t->data)){</span><br><span class="line"> if(preOrderTraverse(t->lchild,visit)){</span><br><span class="line"> if(preOrderTraverse(t->rchild, visit)) return 1;</span><br><span class="line"> }</span><br><span class="line"> }else{</span><br><span class="line"> return 0;</span><br><span class="line"> }</span><br><span class="line"> }else return 1;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>非递归中序遍历<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">int inOrderTraverse(BiTree t, int(*visit)(TElemType e)){</span><br><span class="line"> // 采用二叉链表存储结构,visit是对数据元素操作的应用函数</span><br><span class="line"> // 中序遍历二叉树t的非递归算法, 对每个数据元素调用函数visit</span><br><span class="line"> initStack(s); push(s, t) ;// 根指针入栈</span><br><span class="line"> while(!stackEmpty(s)){</span><br><span class="line"> while(getTop(s, p) && p) push(s, p->lchild); //向左走到尽头</span><br><span class="line"> pop(s,p); // 空指针退栈</span><br><span class="line"> if(!stackEmpty(s)) { //访问结点, 向右一步</span><br><span class="line"> pop(s, p);</span><br><span class="line"> if(!visit(p->data)) reuturn 0;</span><br><span class="line"> push(s, p->rchild);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> return 1;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<h2 id="线索二叉树"><a href="#线索二叉树" class="headerlink" title="线索二叉树"></a>线索二叉树</h2><p>遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列,得到二叉树中结点的先序序列或中序序列或后序序列.这实质上是对一个非线性结构进行线性化操作, 使每个结点每个结点在这些先行序列中有且仅有一个直接前驱和直接后继.</p>
<h2 id="树和森林"><a href="#树和森林" class="headerlink" title="树和森林"></a>树和森林</h2><h3 id="双亲表示法"><a href="#双亲表示法" class="headerlink" title="双亲表示法"></a>双亲表示法</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">// ------- 树的双亲表存储表示 ----------</span><br><span class="line">#define MAX_TREE_SIZE 100</span><br><span class="line">typedef struct PTNode { //结点结构</span><br><span class="line"> TElemType data; </span><br><span class="line"> int parent; //双亲位置域</span><br><span class="line">}PTNode;</span><br><span class="line">typedef struct { //树结构</span><br><span class="line"> PTNode nodes[MAX_TREE_SIZE];</span><br><span class="line"> int r,n; // 根的位置和结点数</span><br><span class="line">}PTree;</span><br></pre></td></tr></table></figure>
<h3 id="孩子表示法"><a href="#孩子表示法" class="headerlink" title="孩子表示法"></a>孩子表示法</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">// ---------- 树的孩子链表存储表示 ----------</span><br><span class="line">typedef struct CTNode { //孩子结点</span><br><span class="line"> ELemType data;</span><br><span class="line"> struct CTNode *next;</span><br><span class="line">}* ChildPtr;</span><br><span class="line"></span><br><span class="line">typedef struct{</span><br><span class="line"> TELemType data;</span><br><span class="line"> ChildPtr firstchild; //孩子链表头指针</span><br><span class="line">}CTBox;</span><br><span class="line"></span><br><span class="line">typedef struct {</span><br><span class="line"> CTBox nodes[MAX_TREE_SIZE];</span><br><span class="line"> int n, r; //结点数和根的位置</span><br><span class="line">}CTree;</span><br></pre></td></tr></table></figure>
<h3 id="孩子兄弟表示法"><a href="#孩子兄弟表示法" class="headerlink" title="孩子兄弟表示法"></a>孩子兄弟表示法</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">typedef struct CSNode {</span><br><span class="line"> ElemType data;</span><br><span class="line"> struct CSNode *firstchild, *nextsibling;</span><br><span class="line">}CSNode, *CSTree;</span><br></pre></td></tr></table></figure>
<h3 id="森林与二叉树的转换"><a href="#森林与二叉树的转换" class="headerlink" title="森林与二叉树的转换"></a>森林与二叉树的转换</h3><p>利用孩子兄弟表示法可以将森林转换成二叉树.</p>
<h2 id="huffman树及其应用"><a href="#huffman树及其应用" class="headerlink" title="huffman树及其应用"></a>huffman树及其应用</h2><p>huffman树又称最优树, 是一类带权路径长度最短的树.<br>路径: 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径, 路径上的分支数目称做路径长度.<br>树的路径长度是从树根到每一个结点的路径长度之和.完全二叉树是路径长度最短的二叉树.<br>若将上述概念推广到一般情况, 考虑带权的结点.结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘机.<br>树的带权路径长度为树中所有结点的带权路径长度之和</p>
<h2 id="查找树"><a href="#查找树" class="headerlink" title="查找树"></a>查找树</h2><h3 id="静态查找表"><a href="#静态查找表" class="headerlink" title="静态查找表"></a>静态查找表</h3><p>抽象数据类型<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">//创建一个含n个数据元素的静态查找表ST</span><br><span class="line">create(*ST, n);</span><br><span class="line"></span><br><span class="line">// 初始条件: 静态查找表ST存在; </span><br><span class="line">// 操作结果: 销毁表ST</span><br><span class="line">destroy(*ST);</span><br><span class="line"></span><br><span class="line">// 初始条件: 静态查找表ST存在, key为和关键字类型相同的给定值j; </span><br><span class="line">// 操作结果: 若ST中存在关键字等于key的数据元素,则函数值为该元素的值或在表中的位置, 否则为空</span><br><span class="line">search(ST, key);</span><br><span class="line"></span><br><span class="line">//初始条件: 静态查找表ST存在, visit是对元素操作的应用函数</span><br><span class="line">//操作结果; 按某种次序对ST的每个元素调用函数visit()一次且仅一次, 一旦visit()失败, 则操作失败</span><br><span class="line">traverse(ST, visit());</span><br></pre></td></tr></table></figure></p>
<h3 id="顺序表的查找"><a href="#顺序表的查找" class="headerlink" title="顺序表的查找"></a>顺序表的查找</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">typedef struct {</span><br><span class="line"> ElemType *elem; // 数据元素存储空间基址, 建表时按实际长度分配, 0号单元留空</span><br><span class="line"> int length; // 表长度 j</span><br><span class="line">}SSTable;</span><br><span class="line"></span><br><span class="line">int search_seq(SSTable ST, keyType key){</span><br><span class="line"> ST.elem[0].key = key; //哨兵</span><br><span class="line"> for(int i = ST.length; !EQ[ST.elem[i].key, key); -- i);</span><br><span class="line"> return i;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<hr>
<h2 id="串"><a href="#串" class="headerlink" title="串"></a>串</h2><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br></pre></td><td class="code"><pre><span class="line">#include <stdio.h></span><br><span class="line">#include <stdlib.h></span><br><span class="line">#include <stdbool.h></span><br><span class="line"></span><br><span class="line">// 串的对分配存储方式</span><br><span class="line">type struct {</span><br><span class="line"> char *ch; // 若是非空串, 则按串长分配存储区,否则为NULL</span><br><span class="line"> int len;</span><br><span class="line">}HString;</span><br><span class="line"></span><br><span class="line">//------ 基本操作的函数原型说明 ------</span><br><span class="line"></span><br><span class="line">// 生成一个其值等于串常量chars的串t</span><br><span class="line">bool strAssign(HString *t, char *chars);</span><br><span class="line"></span><br><span class="line">// 返回串的长度</span><br><span class="line">int strLen(HString s);</span><br><span class="line"></span><br><span class="line">// 若 s > t ,则返回值 > 0, 若s = t, 则返回值 = 0, 若 s < t, 则返回值 < 0</span><br><span class="line">int strCompare(HString s, HString t);</span><br><span class="line"></span><br><span class="line">// 将s清为空串, 并释放s所占空间</span><br><span class="line">bool clearStr(HString *s);</span><br><span class="line"></span><br><span class="line">// 用t返回由s1和s2联接而成的新串</span><br><span class="line">bool concat(HString *t, HString s1, HString s2);</span><br><span class="line"></span><br><span class="line">// 1 <= pos <= strLen(s) && 0 <= len <= strLen(s) - pos + 1</span><br><span class="line">// 返回串s的第pos个字符起长度为len的子串</span><br><span class="line">HString substr(HString s, int pos, int len);</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">// ------- 基本操作的算法描述 ----------</span><br><span class="line">bool strAssign(HString *t, char *chars){</span><br><span class="line"> // 生成一个其值等于串常量chars的串t</span><br><span class="line"> if(t->ch) free(t->ch); // 释放原有空间</span><br><span class="line"> for(int i = 0, c = chars; c; i ++, c ++); //求chars的长度i</span><br><span class="line"> if(!i) {t->ch = NULL; t->len = 0;}</span><br><span class="line"> else {</span><br><span class="line"> if(!(t->ch = (char *)malloc(i * sizeof(char)))) exit(OVERFLOW);</span><br><span class="line"> for(int j = 0; j < i; j ++){</span><br><span class="line"> t->ch[j] = char[j];</span><br><span class="line"> }</span><br><span class="line"> t->len = i;</span><br><span class="line"> }</span><br><span class="line"> return true;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">int strLen(HString s){</span><br><span class="line"> return s.len;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">int strCompare(HString s, HString t){</span><br><span class="line"> for(i = 0; i < s.len && i < t.len; i ++){</span><br><span class="line"> if(s.ch[i] != t.ch[i]) return s.ch[i] - t.ch[i];</span><br><span class="line"> }</span><br><span class="line"> return s.len - t.len;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">bool clearStr(HString *s){</span><br><span class="line"> free(s->ch);</span><br><span class="line"> s->len = 0;</span><br><span class="line"> return true;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">bool concat(HString *t, HString s1, HString s2){</span><br><span class="line"> if(t->ch) free(t->ch); // 释放旧空间</span><br><span class="line"> if(!(t->ch = (char*)malloc((s1.len + s2.len) * sizeof(char)))) exit(0);</span><br><span class="line"> for(int i = 0; i < s1.len; i ++){</span><br><span class="line"> t->ch[i] = s1.ch[i];</span><br><span class="line"> }</span><br><span class="line"> for(int j = 0; j < s2.len; j ++) {</span><br><span class="line"> t->ch[j + s1.len] = s2.ch[j];</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> return true;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">bool subStr(HString *sub, HString s, int pos, int len){</span><br><span class="line"> // 用sub返回串s的第pos个字符起长度为len的子串</span><br><span class="line"> // 其中, 1 <= pos <= strLen(s) 且 0 <= len <= strLen(s) - pos + 1</span><br><span class="line"> int lenOfs = strLen(s);</span><br><span class="line"> if(pos < 1 || pos > lenOfs || len < 9 || len > lenOfs - pos +1)</span><br><span class="line"> return false;</span><br><span class="line"> if(sub->ch) free(sub->ch);</span><br><span class="line"> if(!len) {sub->ch = NULL;sub->len = 0;} //空子串</span><br><span class="line"> else {</span><br><span class="line"> sub->ch = (char*) malloc(len * sizeof(char));</span><br><span class="line"> for(int i = 0; i < len; i ++){</span><br><span class="line"> sub->ch[i] = s.ch[pos - 1 + i];</span><br><span class="line"> }</span><br><span class="line"> sub->len = len;</span><br><span class="line"> }</span><br><span class="line"> return true;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">//串的块链存储方式不推荐使用. 存储密度低,虽然操作简单,但是内存使用率低, 且当串处理工程需要进行内外存交换的话, 则会会因为内外存交换过多影响处理的效率. 存储密度高, 操作相比前两种存储方式要更加复杂.</span><br><span class="line">#include <stdio.h></span><br><span class="line">#include <stdlib.h></span><br><span class="line">#include <stdbool.h></span><br><span class="line"></span><br><span class="line">#define CHUNKSIZE 80 //可由用户定义的块大小</span><br><span class="line">typedef struct chunk {</span><br><span class="line"> char ch[CHUNKSIZE];</span><br><span class="line"> struct chunk * next;</span><br><span class="line">}chunk;</span><br><span class="line"></span><br><span class="line">typedef struct {</span><br><span class="line"> chunk *head, *tail; // 串的头指针和尾指针</span><br><span class="line"> int curlen; 串的当前长度</span><br><span class="line">}lString;</span><br></pre></td></tr></table></figure>
<h3 id="求子串位置的定位函数"><a href="#求子串位置的定位函数" class="headerlink" title="求子串位置的定位函数"></a>求子串位置的定位函数</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">#define MAXLEN;</span><br><span class="line">typedef unsigned char SString[MAXLEN + 1]</span><br><span class="line">int index(SString s, SString t, int pos){</span><br><span class="line"> // 返回子串t在主串s中第pos个字符之后的位置. 若不存在, 则函数返回值为0</span><br><span class="line"> // 其中, t非空, 1 <= pos <= strLen(s)</span><br><span class="line"> if(pos < 1) return 0;</span><br><span class="line"> int i = pos, j = 1;</span><br><span class="line"> while(i <= s[0] && j <= t[0]){</span><br><span class="line"> if(s[i] == t[j]) {i++; j++;} // 继续比较后继字符</span><br><span class="line"> else {i = i - j + 2; j = 1;} // 指针后退重新匹配</span><br><span class="line"> }</span><br><span class="line"> if(j > t[0]) return i - t[0];</span><br><span class="line"> else return 0;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="kmp算法"><a href="#kmp算法" class="headerlink" title="kmp算法"></a>kmp算法</h3><p>kmp的算法复杂度为 o(m + n); kmp算法在每次比较不等时,不需要回溯i指针,而是利用已部分匹配得到的结果将模式滑动尽可能远的一段距离后,继续进行比较.<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line">void get_next(SString s, int next[]){</span><br><span class="line"> int j = 1, i = j + 1;</span><br><span class="line"> next[1] = 0; </span><br><span class="line"> while(i < s[0]) {</span><br><span class="line"> if(s[i] == s[j]){ // 如果 pi = pj 则 next[i] = next[j] + 1 </span><br><span class="line"> next[i] = next[j] + 1;</span><br><span class="line"> i++; j ++;</span><br><span class="line"> }else{ //如果pi != pj, 则把问题看作是p1..pj与p(i-j+1)...pi的模式匹配问题,前者为模式串, 后者为主串</span><br><span class="line"> j = next[j];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line">//进一步优化</span><br><span class="line">void get_next(SString t, int next[]){</span><br><span class="line"> // 求模式串t的next函数值并存入数组next</span><br><span class="line"> int i = 1, next[1] = 0, j = 0;</span><br><span class="line"> while(i < t[o]){</span><br><span class="line"> if(j == 0 || t[i] == t[j]){</span><br><span class="line"> i++;</span><br><span class="line"> j++;</span><br><span class="line"> next[i] = j;</span><br><span class="line"> }else{</span><br><span class="line"> j = next[j];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">//进一步优化</span><br><span class="line">void get_next(SString t, int next[]){</span><br><span class="line"> // 求模式串t的next函数值并存入数组next</span><br><span class="line"> int i = 1, next[1] = 0, j = 0;</span><br><span class="line"> while(i < t[o]){</span><br><span class="line"> if(j == 0 || t[i] == t[j]){</span><br><span class="line"> i++;</span><br><span class="line"> j++;</span><br><span class="line"> if(t[i] != t[j]) next[i] = j;</span><br><span class="line"> else next[i] = next[j];</span><br><span class="line"> }else{</span><br><span class="line"> j = next[j];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line">int index_kmp(SString s, SString t, int pos){</span><br><span class="line"> // 利用模式串t的next函数求t在主串s中第pos个字符之后的位置的kmp算法. 其中, t非空, 1 <= pos <= strLen(s)</span><br><span class="line"> if(pos < 1) return 0;</span><br><span class="line"> int i = pos, j = 1;</span><br><span class="line"> while(i <= s[0] && j <= t[0]){</span><br><span class="line"> if(j == 0 || s[i] == t[i]) {i ++; j ++;}</span><br><span class="line"> else j = next[j];</span><br><span class="line"> }</span><br><span class="line"> if(j > T[0]) return i - t[0];</span><br><span class="line"> return 0;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="brczo.github.io/2019/06/02/计算机组成原理/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="brczo">
<meta itemprop="description" content>
<meta itemprop="image" content="/images/avatar.gif">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="进化">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2019/06/02/计算机组成原理/" itemprop="url">计算机组成原理</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建于" itemprop="dateCreated datePublished" datetime="2019-06-02T15:34:39+08:00">
2019-06-02
</time>
</span>
<span class="post-category">
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/编程/" itemprop="url" rel="index">
<span itemprop="name">编程</span>
</a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="系统总线"><a href="#系统总线" class="headerlink" title="系统总线"></a>系统总线</h2><p>计算机硬件系统由中央处理器、存储器、I/O设备以及连接它们的系统总线组成。本章着重介绍系统总线的基本概念以其分类、结构和总线控制逻辑。</p>
<h3 id="总线的基本概念"><a href="#总线的基本概念" class="headerlink" title="总线的基本概念"></a>总线的基本概念</h3><ul>
<li>以前计算机使用的是分散连接方式, 后来人们希望能够随时增添设备, 于是发展出了总线.</li>
<li>总线是连接多个部件的信息传输线,是各部件共享的传输介质.</li>
<li>当多个部件和总线相连时,如果出现两个或两个以上部件同时向总线发送信息,势必导致信号冲突,传输无效.因此在某一时刻,只允许有一个部件向总线发送信息,而多个部件可以同时从总线接受信息.</li>
<li>总线实质上是由许多传输线或通路组成,每条线可一位一位的传输二进制码.</li>
</ul>
<h3 id="总线的分类"><a href="#总线的分类" class="headerlink" title="总线的分类"></a>总线的分类</h3><ul>
<li><p>片内总线 </p>
<blockquote>
<p>片内总线是指芯片内部的总线,如在CPU芯片内部,寄存器与寄存器之间,寄存器与算术逻辑单元ALU之间都由片内总线连接.</p>
</blockquote>
</li>
<li><p>系统总线 </p>
<blockquote>
<p>系统总线是指CPU、主存、I/O设备个大部件之间的信息传输线.</p>
</blockquote>
</li>
</ul>
<h4 id="按系统总线传输信息的不同"><a href="#按系统总线传输信息的不同" class="headerlink" title="按系统总线传输信息的不同"></a>按系统总线传输信息的不同</h4><ul>
<li><p>数据总线</p>
<blockquote>
<p>数据总线用来传输各功能部件之间的数据信息,它是双向传输总线,其位数与机器字长(计算机一次能处理数据的位数)和存储字长(MDR的位数)有关.数据总线的位数称为数据总线宽度,是衡量系统性能的一个重要参数.<br>如果数据总线的宽度是8位,指令字长为16位,那么cpu在取指阶段必须两次访问主存.</p>
</blockquote>
</li>
<li><p>地址总线</p>
<blockquote>
<p>地址总线主要用来指出<strong>数据总线</strong>上的源数据或目的数据在主存单元的地址或I/O设备的地址.<br>地址总线上的代码是用来指明CPU欲访问的存储单元或I/O端口的地址,由CPU输出,单向传输.地址线的位数与存储单元的个数有关.如地址线为20根,则对应的存储单元个数为pow(2,20)</p>
</blockquote>
</li>
<li><p>控制总线</p>
<blockquote>
<p>由于数据总线、地址总线都是被挂在总线上的所有部件共享,如何使各部件在不同时刻占有总线使用权,需依靠控制总线来完成,因此控制总线是用来发出各种控制信号的传输线.<br>对CPU而言,控制信号既有输出,又有输入.</p>
</blockquote>
</li>
</ul>
<p>常见的控制信号:</p>
<ul>
<li>时钟: 用来同步各种操作</li>
<li>复位: 初始化所有部件</li>
<li>总线请求: 表示某部件需获得总线使用权</li>
<li>总线允许: 需要获得总线的使用权的部件已获得控制权</li>
<li>中断请求: 表示某不见提出中断请求</li>
<li>中断相应: 表示中断请求已被接受</li>
<li>存储器写: 将数据总线上的数据写至存储器的指定地址单元内</li>
<li>存储器读: 将指定存储单元中的数据读到数据总线上.</li>
<li>I/O读: 从指定的I/O端口将数据读到数据总线上</li>
<li>I/O写: 将数据总线上的数据输出到指定的I/O端口内</li>
<li>传输响应: 表示数据已被接受,或已将数据送至数据总线上.</li>
</ul>
<h3 id="通信总线"><a href="#通信总线" class="headerlink" title="通信总线"></a>通信总线</h3><p>这类总线用于计算机系统之间或计算机系统与其他系统之间的通信. 按传输方式分为串行通信和并行通信:<br>串行通信是指数据在单条1位宽的传输线上,一位一位地按顺序分时传送.<br>并行通信是指数据在多条并行1位宽的传输线上,同属由源到目的地.</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="brczo.github.io/2019/05/29/随想/">