基于拓扑排序的排课程序

一、题目描述

某学院有n门课程,(i,j)表示课程i是课程j的先行课,及课程i必须在课程j的之前的学期开设。对任意给出的仙子那个课解s={(1,3),(2,4),(3,5),(4,6),(3,7),…},至少需要安排多少个学期?给出每个学期的课程清单。

二、程序思路

分析题目能清楚地发现此题与拓扑排序有很大的关系,拓扑排序的层数就是学期数,每个学期的课程就是每一层的点。所以只需要在拓扑排序的程序上改改就好了。

三、具体实现

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
int linkedDgraph1::course(int **b)//传入的为保存结果的二维数组
{
int number=0;//学期数
int n=verticeNumber;//顶点个数
int *indegree=new int[num1+1];//顶点的入度数组
for(int i=1;i<=num1;i++)//保存入度
indegree[i]=inDegree(i);
stack<int> astack(10000);//声明栈
while(n!=0)
{ int j=0;
for(int i=1;i<=num1;i++)//遍历将入度为零的点入栈
{
if(indegree[i]==0)
{
b[number][j++]=i;//保存此点
//cout<<i<<" ";
astack.push(i); //入栈
}
}
number++;//前一学期的课程已完
//cout<<number<<" ";
while(!astack.empty())
{ int t=astack.top();
n--;
// cout<<verticeNumber<<" ";
indegree[t]=-1;
astack.pop();
for(int i=1;i<=num1;i++)//更新各顶点的入度
if(existsEdge(t,i))
indegree[i]--;
}
}
return number;
}

四、结果展示

1528593893057

五、说明

本程序所用图的结构为邻接链表。

Android手指个数识别

一、在Android Studio导入opencv 库。

这里直接给个链接:

一个opencv的学习网站:

二、建立项目

1.整体思路:

(1):点击拍照,调用手机摄像头拍照并保存。

(2):调用刚才拍的照片进行处理。

(3):在界面显示结果。

2.具体步骤:

(1)调用手机摄像头拍照保存并读取的相关权限:

1
2
3
4
5
<uses-permission android:name="android.permission.CAMERA" />
//摄像头权限
<uses-feature android:name="android.hardware.camera" />
<uses-permission android:name="android.permission.MOUNT_UNMOUNT_FILESYSTEMS" />
<uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE" />

(2)界面:包含一个拍照按钮,一个图片展示框和一个文本输出显示手指的个数。

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
<Button
android:text="照相"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:layout_below="@+id/btn_gray_process"
android:layout_alignStart="@+id/btn_gray_process"
android:id="@+id/take_photo" />

<ImageView
android:id="@+id/picture"
android:layout_width="match_parent"
android:layout_alignParentBottom="true"
android:layout_centerHorizontal="true"
android:layout_marginBottom="16dp"
android:layout_height="wrap_content" />

<TextView
android:text="手指个数"
android:layout_width="100dp"
android:layout_height="50dp"
android:layout_alignBottom="@+id/take_photo"
android:layout_alignParentEnd="true"
android:layout_marginEnd="91dp"
android:id="@+id/textView"
android:layout_alignParentTop="true" />

(3)

三、具体实现代码:

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
package com.example.yanhuojun.handgesture1;

import android.app.Activity;
import android.content.Intent;
import android.graphics.Bitmap;
import android.graphics.BitmapFactory;

import android.net.Uri;
import android.os.Environment;
import android.provider.MediaStore;
import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.util.Log;
import android.view.View;
import android.widget.Button;
import android.widget.ImageView;
import android.widget.TextView;
import android.widget.Toast;

import com.example.yanhuojun.handgesture1.R;

import org.opencv.android.BaseLoaderCallback;

import org.opencv.android.LoaderCallbackInterface;
import org.opencv.android.OpenCVLoader;
import org.opencv.android.Utils;
import org.opencv.core.Core;
import org.opencv.core.CvType;
import org.opencv.core.Mat;
import org.opencv.core.MatOfInt4;
import org.opencv.core.MatOfPoint;
import org.opencv.core.MatOfPoint2f;
import org.opencv.core.Point;
import org.opencv.core.Scalar;
import org.opencv.core.Size;
import org.opencv.imgcodecs.Imgcodecs;
import org.opencv.imgproc.Imgproc;
import org.opencv.imgproc.Moments;


import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.Vector;

import static java.lang.Math.abs;
import static org.opencv.core.CvType.CV_8UC3;
import static org.opencv.imgproc.Imgproc.THRESH_BINARY;
import static org.opencv.imgproc.Imgproc.circle;
import static org.opencv.imgproc.Imgproc.line;
import static org.opencv.imgproc.Imgproc.moments;

//public class MainActivity extends AppCompatActivity {
public class MainActivity extends Activity {

public static final int TAKE_PHOTO = 1;
//public static final int CROP_PHOTO = 2;
private TextView textView;
private Button takephoto;
private ImageView picture;
private Uri imageUri;
double treash=100;
Mat imageMat;
private static final String TAG = "OCVSample::Activity";

private BaseLoaderCallback mLoaderCallback = new BaseLoaderCallback(this) {
@Override
public void onManagerConnected(int status) {
switch (status) {
case LoaderCallbackInterface.SUCCESS:
{
Log.i(TAG, "OpenCV loaded successfully");
imageMat=new Mat();
} break;
default:
{
super.onManagerConnected(status);
} break;
}
}
};
@Override
public void onResume()
{
super.onResume();
if (!OpenCVLoader.initDebug()) {
Log.d("OpenCV", "Internal OpenCV library not found. Using OpenCV Manager for initialization");
OpenCVLoader.initAsync(OpenCVLoader.OPENCV_VERSION_2_4_10, this, mLoaderCallback);
} else {
Log.d("OpenCV", "OpenCV library found inside package. Using it!");
mLoaderCallback.onManagerConnected(LoaderCallbackInterface.SUCCESS);
}
}



@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);

takephoto = (Button)findViewById(R.id.take_photo);
textView =(TextView) findViewById(R.id.textView);
picture = (ImageView)findViewById(R.id.picture);
takephoto.setOnClickListener(new View.OnClickListener() {
@Override
public void onClick(View v) {
File outputImage = new File(Environment.getExternalStorageDirectory(), "output_image.jpg");
try {
if (outputImage.exists()) {
outputImage.delete();
}
outputImage.createNewFile();
}catch (IOException e){
e.printStackTrace();
}
imageUri = Uri.fromFile(outputImage);
Intent intent = new Intent("android.media.action.IMAGE_CAPTURE");//调用系统相机拍照
intent.putExtra(MediaStore.EXTRA_OUTPUT, imageUri);
startActivityForResult(intent, TAKE_PHOTO);
}
});
}

@Override
protected void onActivityResult(int requestCode, int resultCode, Intent data){
switch (requestCode){
case TAKE_PHOTO:
//if (resultCode == RESULT_OK){
//Intent intent = new Intent("com.android.camera.action.CROP");
//intent.setDataAndType(imageUri, "image/*");
// intent.putExtra("scale", true);
//intent.putExtra(MediaStore.EXTRA_OUTPUT,imageUri);
//startActivityForResult(intent, CROP_PHOTO);
//}
//break;
//case CROP_PHOTO:
if (resultCode == RESULT_OK){
try{
//获取原图
Bitmap bitmap = BitmapFactory.decodeStream(getContentResolver().openInputStream(imageUri));
picture.setImageBitmap(bitmap);//设置显示图像
//图像处理
Mat mat_src = new Mat(bitmap.getHeight(), bitmap.getWidth(), CvType.CV_8UC4);//获取原图(8位无符号的四通道,带透明的RGB图像)
Utils.bitmapToMat(bitmap, mat_src);//将bitmap转化成mat
Mat mat_gray = new Mat(mat_src.cols(), mat_src.rows(), CvType.CV_8UC1);//灰度图,单通道
Imgproc.cvtColor(mat_src, mat_gray, Imgproc.COLOR_BGRA2GRAY, 1);//转变颜色

//-------------------------------------------------------------------
Mat frame = new Mat(bitmap.getHeight(), bitmap.getWidth(), CvType.CV_8UC4);//取出原图
mat_src.copyTo(frame);//复制,不会牵连改变

Mat frameHSV = new Mat(mat_src.cols(), mat_src.rows(), CV_8UC3);//三通道的RGB图像
; // hsv空间(色调,饱和度,明度)
Mat mask = new Mat(mat_src.cols(), mat_src.rows(), CvType.CV_8UC1);
Mat dst = new Mat(mat_src.cols(), mat_src.rows(), CV_8UC3); // 输出图像
//dst.copyTo(frame);
// 中值滤波,去除椒盐噪声
Imgproc.medianBlur(frame, frame, 5);
Imgproc.cvtColor(frame, frameHSV, Imgproc.COLOR_RGB2HSV, 3);//把frame的颜色空间转换后复制到frameHSV
Mat dstTemp1 = new Mat(mat_src.cols(), mat_src.rows(), CvType.CV_8UC1);
Mat dstTemp2 = new Mat(mat_src.cols(), mat_src.rows(), CvType.CV_8UC1);
// 对HSV空间进行量化,得到二值图像,亮的部分为手的形状
Core.inRange(frameHSV, new Scalar(0, 30, 30), new Scalar(40, 170, 256), dstTemp1);//比较三个通道中的元素是否在相应的区间类,不在的画的则改成255
Core.inRange(frameHSV, new Scalar(156, 30, 30), new Scalar(180, 170, 256), dstTemp2);
Core.bitwise_or(dstTemp1, dstTemp2, mask);//对前面的两张图片(二值图像)进行异或处理,并将其结果给第三章图

// 形态学操作,去除噪声,并使手的边界更加清晰
Mat element = Imgproc.getStructuringElement(Imgproc.MORPH_RECT, new Size(3, 3));//定义一个合适大小的核
Imgproc.erode(mask, mask, element);//扩大暗区,腐蚀
Imgproc.morphologyEx(mask, mask, Imgproc.MORPH_OPEN, element);//对输入图像执行开运算
Imgproc.dilate(mask, mask, element);//扩大亮区,膨胀
Imgproc.morphologyEx(mask, mask, Imgproc.MORPH_CLOSE, element);//执行闭运算

frame.copyTo(dst, mask);

List<MatOfPoint> contourList = new ArrayList<MatOfPoint>();
Vector<MatOfPoint> contours=new Vector<MatOfPoint>();
Vector<Vector<Point>> con=new Vector<Vector<Point>>();

MatOfInt4 hierarchy=new MatOfInt4();
//Imgproc.Canny(mat_src,mask,mask,treash*2,3);
// // 得到手的轮廓
Imgproc.findContours(mask, contours, hierarchy, Imgproc.RETR_EXTERNAL, Imgproc.CHAIN_APPROX_SIMPLE);
//List<Moments> mu=new ArrayList<Moments>(contourList.size()) ;
//mu.set(0,moments(contourList.get(0),true));
// for( int i = 0; i < contourList.size(); i++ )
//{ mu.set(i,moments( contourList.get(i), false )); }
/// 计算中心矩:


//Log.e(TAG, "index=:"+index+"  counter.size="+contours.size()+"  area="+area);
//**********************************************************8
// dst = Mat::zeros( mask.size(), CV_8UC3 );
//Random r = new Random();
//int nContoursNum = contours.size();
//for (int i = 0; i < nContoursNum; i++) {
// Imgproc.drawContours(dst, contours, i, new Scalar(r.nextInt(255), r.nextInt(255), r.nextInt(255)), -1);
// }
//Point center=mc.get(0);
// Mat mat_gray1 = new Mat(mat_src.cols(), mat_src.rows(), CvType.CV_8UC1);//灰度图
//Imgproc.cvtColor(dst, mat_gray1, Imgproc.COLOR_BGRA2GRAY, 1);//转变颜色
Moments moment = moments(mask,false);
Point center = new Point(moment.m10 / moment.m00, moment.m01 / moment.m00);//计算图形重心
circle(dst, center, 8, new Scalar(0, 0, 255), -1);//最后一位参数不确定*/
//-------------------------------------------------------------------
//图像显示
Vector<MatOfPoint2f> newcont=new Vector<MatOfPoint2f>();
for(MatOfPoint point : contours) {
MatOfPoint2f newPoint = new MatOfPoint2f(point.toArray());
newcont.add(newPoint);
}
Vector<MatOfPoint2f> cont=new Vector<>();
for(int i=0;i<newcont.size();i++)
{
MatOfPoint2f first=newcont.get(i);
MatOfPoint2f second=new MatOfPoint2f();
Imgproc.approxPolyDP(first,second, 80, true);
cont.add(second);
}
Vector<MatOfPoint> polyedges = new Vector<>();
for(MatOfPoint2f point : cont) {
MatOfPoint nPoint = new MatOfPoint(point.toArray());
polyedges.add(nPoint);
}
Vector<Point> poly=new Vector<Point>();
MatOfPoint aPoint = polyedges.get(0);
Point[] ab=aPoint.toArray();
//Iterator<Point> itp = poly.listIterator(0);
//Point aa=poly.get(0);
for(int j=0;j<polyedges.size();j++) {
for (int i = 0; i < polyedges.get(j).toArray().length - 1; i++) {
line(dst, polyedges.get(j).toArray()[i], polyedges.get(j).toArray()[i + 1], new Scalar(255, 255, 255), 5);
//aa=itp.next();
}
line(dst,polyedges.get(j).toArray()[polyedges.get(j).toArray().length - 1],polyedges.get(j).toArray()[0], new Scalar(255,255,255), 5);
}


//Imgproc.threshold( mat_gray, dst, 100, 255, THRESH_BINARY );

/*RNG rng(12345);
Vector<Vector<Point> >hull=new Vector<Vector<Point>>( contours.size() );
for( int i = 0; i < contours.size(); i++ )
{ Imgproc.convexHull(new Mat((MatOfPoint2f)(contours.get(i))), hull.get(i), false ); }

/// 绘出轮廓及其凸包
Mat drawing = Mat.zeros( dst.size(), CV_8UC3 );
for( int i = 0; i< contours.size(); i++ )
{
Scalar color = Scalar( rng.uniform(0, 255), rng.uniform(0,255), rng.uniform(0,255) );
Imgproc.drawContours( drawing, contours, i, color, 1, 8, Vector<Vec4i>(), 0, Point() );
drawContours( drawing, hull, i, color, 1, 8, vector<Vec4i>(), 0, Point() );
}*/
//**********************************************************************
int index = 0;
double area = 0, maxArea=0;
for (int i=0;i < polyedges.size(); i++)
{
area = Imgproc.contourArea(polyedges.get(i));
if (area > maxArea)
{
maxArea = area;
index = i;
}
}
MatOfPoint couPoint = polyedges.get(index);
Point[] a=couPoint.toArray();
// List<Point> couPoint = contours.get(nContoursNum);
Vector<Point> fingerTips = new Vector<Point>();
Point tmp = new Point();
double max = 0;
int count = 0, notice = 0;
for (int i = 0; i < a.length; i++) {
tmp = a[i];
double dist = (tmp.x - center.x) * (tmp.x - center.x) + (tmp.y - center.y) * (tmp.y - center.y);
if (dist > max) {
max = dist;
notice = i;
}
// 计算最大值保持的点数,如果大于40(这个值需要设置,本来想根据max值来设置,
// 但是不成功,不知道为何),那么就认为这个是指尖
if (dist != max) {
max = 0;
boolean flag = false;
// 低于手心的点不算
if (center.y < a[notice].y)
continue;
// 离得太近的不算
for (int j = 0; j < fingerTips.size(); j++) {
if (abs(a[notice].x - fingerTips.get(j).x) < 40) {
flag = true;
break;
}
}
if (flag) continue;
fingerTips.add(a[notice]);
circle(dst, a[notice], 6, new Scalar(255, 255, 255), -1);
line(dst, center, a[notice], new Scalar(0, 255, 255), 5);

}
}
textView.setText(String.valueOf(fingerTips.size()));
//*****************************************************
Bitmap bmp_gray = Bitmap.createBitmap(mat_gray.cols(), mat_gray.rows(), Bitmap.Config.ARGB_8888);
Utils.matToBitmap(dst, bmp_gray);
picture.setImageBitmap(bmp_gray);

}catch (FileNotFoundException e){
e.printStackTrace();
}
}
break;
default:
break;
}
}

}

四、程序效果:

五、不足:

1.程序鲁棒性不足,容易收到背景环境的干扰,尤其是与肤色相近的环境。

2.处理速度慢,要等待数秒左右。

3.弯曲手指不彻底就会影响结果。

吸烟者问题

###一、问题描述

抽烟者问题。假设一个系统中有三个抽烟者进程,每个抽烟者不断地卷烟并抽烟。抽烟者卷起并抽掉一颗烟需要有三种材料:烟草、纸和胶水。一个抽烟者有烟草,一个有纸,另一个有胶水。系统中还有两个供应者进程,它们无限地供应所有三种材料,但每次仅轮流提供三种材料中的两种。得到缺失的两种材料的抽烟者在卷起并抽掉一颗烟后会发信号通知供应者,让它继续提供另外的两种材料。这一过程重复进行。 请用以上介绍的 IPC 同步机制编程,实现该问题要求的功能。

二、问题分析

这个问题主要涉及到操作系统中的进程见的同步与互斥的,是一个非常经典的问题。可以看做是生产者消费者这一类。

三个抽烟者相当于三个不同的消费者,他们每次只会有一个抽烟者可以抽到烟,其余两个则需要等待。而在这里默认空间大小只有一个单元,即供应者每次放下两种材料后都会停下来等待直到有消费者使用了这两种材料,他才会继续放另两种材料。相当于说缓冲区的大小为1。为了方便起见,我们把要放的两种材料捆绑到一起,看成一个单位,分别用A、B、C表示,三个吸烟着分别用1,2,3号表示。

###三、画出大致的操作流程和关键代码

img

设置五个信号量分别为三个抽烟者对应的glue、tobacco、paper和与供应者相应的同步信号量表示缓存区为空的empty信号量。最后还有一个保证临界资源安全访问的互斥信号量mutex。

供应者: 1号抽烟者: 2号抽烟者: 3号抽烟者:

while(1) while(1) while(1) whiel(1)

{ { { {

p(empty); p(glue); p(tobacco); p(paper);

p(mutex); p(mutex); p(mutex); p(mutex);

供应材料。 抽烟 抽烟 抽烟

v(mutex) v(mutex); v(mutex); v(mutex);

if(材料为A) v(empty); v(empty); v(empty);

v(glue) } } }

if(材料为B)

v(tobacco)

if(材料为C)

v(paper)

}

信号量的初始值:

empty=1;mutex=1;glue=0;paper=0;tobacco=0;

四、具体代码

ipc.h:

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
/*
* Filename
: ipc.h
* copyright
: (C) 2006 by zhonghonglie
* Function
: 澹版槑 IPC 鏈哄埗鐨勫嚱鏁板師鍨嬪拰鍏ㄥ眬鍙橀噺
*/
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/sem.h>
#include <sys/msg.h>
#define BUFSZ 256
//寤虹珛鎴栬幏鍙?ipc 鐨勪竴缁勫嚱鏁扮殑鍘熷瀷璇存槑
int get_ipc_id(char *proc_file,key_t key);
char *set_shm(key_t shm_key,int shm_num,int shm_flag);
int set_msq(key_t msq_key,int msq_flag);
int set_sem(key_t sem_key,int sem_val,int sem_flag);
int down(int sem_id);
int up(int sem_id);
/*淇″彿鐏帶鍒剁敤鐨勫叡鍚屼綋*/
typedef union semuns {
int val;
} Sem_uns;
/* 娑堟伅缁撴瀯浣?/
typedef struct msgbuf {
long mtype;
char mtext[1];
} Msg_buf;
//鐢熶骇娑堣垂鑰呭叡浜紦鍐插尯鍗冲叾鏈夊叧鐨勫彉閲?
key_t buff_key;
int buff_num;
char *buff_ptr;
//鐢熶骇鑰呮斁浜у搧浣嶇疆鐨勫叡浜寚閽?
key_t pput_key;
int pput_num;
int *pput_ptr;
//娑堣垂鑰呭彇浜у搧浣嶇疆鐨勫叡浜寚閽?
key_t cget_key;
int cget_num;
int *cget_ptr;
//鐢熶骇鑰呮湁鍏崇殑淇″彿閲?
key_t tobacco_key;
key_t glue_key;
key_t paper_key;
int tobacco_sem;
int glue_sem;
int paper_sem;
//娑堣垂鑰呮湁鍏崇殑淇″彿閲?
key_t empty_key;
key_t mutex_key;
int empty_sem;
int mutex_sem;
int sem_val;
int sem_flg;
int shm_flg;

ipc.c

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
/*
绗?41 椤靛疄楠屽洓銆佽繘绋嬪悓姝ュ疄楠?
* Filename
* copyright
* Function
: ipc.c
: (C) 2006 by zhonghonglie
: 涓€缁勫缓绔?IPC 鏈哄埗鐨勫嚱鏁?
*/
#include "ipc.h"
/*
* get_ipc_id() 浠?proc/sysvipc/鏂囦欢绯荤粺涓幏鍙?IPC 鐨?id 鍙?
* pfile: 瀵瑰簲/proc/sysvipc/鐩綍涓殑 IPC 鏂囦欢鍒嗗埆涓?
*
msg-娑堟伅闃熷垪,sem-淇″彿閲?shm-鍏变韩鍐呭瓨
* key: 瀵瑰簲瑕佽幏鍙栫殑 IPC 鐨?id 鍙风殑閿€?
*/
int get_ipc_id(char *proc_file,key_t key)
{
FILE *pf;
int i,j;
char line[BUFSZ],colum[BUFSZ];
if((pf = fopen(proc_file,"r")) == NULL){
perror("Proc file not open");
exit(EXIT_FAILURE);
}
fgets(line, BUFSZ,pf);
while(!feof(pf)){
i = j = 0;
fgets(line, BUFSZ,pf);
while(line[i] == ' ') i++;
while(line[i] !=' ') colum[j++] = line[i++];
colum[j] = '\0';
if(atoi(colum) != key) continue;
j=0;
while(line[i] == ' ') i++;
while(line[i] !=' ') colum[j++] = line[i++];
colum[j] = '\0';
i = atoi(colum);
fclose(pf);
return i;
}
fclose(pf);
return -1;
}
/*
* 淇″彿鐏笂鐨?down/up 鎿嶄綔
* semid:淇″彿鐏暟缁勬爣璇嗙
* semnum:淇″彿鐏暟缁勪笅鏍?
* buf:鎿嶄綔淇″彿鐏殑缁撴瀯
*/
int down(int sem_id)
{
struct sembuf buf;
buf.sem_op = -1;
buf.sem_num = 0;
buf.sem_flg = SEM_UNDO;
if((semop(sem_id,&buf,1)) <0) {
perror("down error ");
exit(EXIT_FAILURE);
}
return EXIT_SUCCESS;
}
int up(int sem_id)
{
struct sembuf buf;
buf.sem_op = 1;
buf.sem_num = 0;
buf.sem_flg = SEM_UNDO;
if((semop(sem_id,&buf,1)) <0) {
perror("up error ");
exit(EXIT_FAILURE);
}
return EXIT_SUCCESS;
}
/*
* set_sem 鍑芥暟寤虹珛涓€涓叿鏈?n 涓俊鍙风伅鐨勪俊鍙烽噺
*
濡傛灉寤虹珛鎴愬姛,杩斿洖 涓€涓俊鍙风伅鏁扮粍鐨勬爣璇嗙 sem_id
*
杈撳叆鍙傛暟:
* sem_key 淇″彿鐏暟缁勭殑閿€?
* sem_val 淇″彿鐏暟缁勪腑淇″彿鐏殑涓暟
* sem_flag 淇″彿绛夋暟缁勭殑瀛樺彇鏉冮檺
*/
int set_sem(key_t sem_key,int sem_val,int sem_flg)
{
int sem_id;
Sem_uns sem_arg;
//娴嬭瘯鐢?sem_key 鏍囪瘑鐨勪俊鍙风伅鏁扮粍鏄惁宸茬粡寤虹珛
if((sem_id = get_ipc_id("/proc/sysvipc/sem",sem_key)) < 0 )
{
//semget 鏂板缓涓€涓俊鍙风伅,鍏舵爣鍙疯繑鍥炲埌 sem_id
if((sem_id = semget(sem_key,1,sem_flg)) < 0)
{
perror("semaphore create error");
exit(EXIT_FAILURE);
}
//璁剧疆淇″彿鐏殑鍒濆€?
sem_arg.val = sem_val;
if(semctl(sem_id,0,SETVAL,sem_arg) <0)
{
perror("semaphore set error");
exit(EXIT_FAILURE);
}
}
return sem_id;
}
/*
* set_shm 鍑芥暟寤虹珛涓€涓叿鏈?n 涓瓧鑺?鐨勫叡浜唴瀛樺尯
*
濡傛灉寤虹珛鎴愬姛,杩斿洖 涓€涓寚鍚戣鍐呭瓨鍖洪鍦板潃鐨勬寚閽?shm_buf
*
杈撳叆鍙傛暟:
* shm_key 鍏变韩鍐呭瓨鐨勯敭鍊?
* shm_val 鍏变韩鍐呭瓨瀛楄妭鐨勯暱搴?
* shm_flag 鍏变韩鍐呭瓨鐨勫瓨鍙栨潈闄?
*/
char * set_shm(key_t shm_key,int shm_num,int shm_flg)
{
int i,shm_id;
char * shm_buf;
//娴嬭瘯鐢?shm_key 鏍囪瘑鐨勫叡浜唴瀛樺尯鏄惁宸茬粡寤虹珛
if((shm_id = get_ipc_id("/proc/sysvipc/shm",shm_key)) < 0 )
{
//shmget 鏂板缓 涓€涓暱搴︿负 shm_num 瀛楄妭鐨勫叡浜唴瀛?鍏舵爣鍙疯繑鍥炲埌 shm_id
if((shm_id = shmget(shm_key,shm_num,shm_flg)) <0)
{
perror("shareMemory set error");
exit(EXIT_FAILURE);
}
//shmat 灏嗙敱 shm_id 鏍囪瘑鐨勫叡浜唴瀛橀檮鍔犵粰鎸囬拡 shm_buf
if((shm_buf = (char *)shmat(shm_id,0,0)) < (char *)0)
{
perror("get shareMemory error");
exit(EXIT_FAILURE);
}
for(i=0; i<shm_num; i++) shm_buf[i] = 0; //鍒濆涓?0
}
//shm_key 鏍囪瘑鐨勫叡浜唴瀛樺尯宸茬粡寤虹珛,灏嗙敱 shm_id 鏍囪瘑鐨勫叡浜唴瀛橀檮鍔犵粰鎸囬拡 shm_buf
if((shm_buf = (char *)shmat(shm_id,0,0)) < (char *)0)
{
perror("get shareMemory error");
exit(EXIT_FAILURE);
}
return shm_buf;
}
/*
* set_msq 鍑芥暟寤虹珛涓€涓秷鎭槦鍒?
* 濡傛灉寤虹珛鎴愬姛,杩斿洖 涓€涓秷鎭槦鍒楃殑鏍囪瘑绗?msq_id
* 杈撳叆鍙傛暟:
* msq_key 娑堟伅闃熷垪鐨勯敭鍊?
* msq_flag 娑堟伅闃熷垪鐨勫瓨鍙栨潈闄?
*/
int set_msq(key_t msq_key,int msq_flg)
{
int msq_id;
//娴嬭瘯鐢?msq_key 鏍囪瘑鐨勬秷鎭槦鍒楁槸鍚﹀凡缁忓缓绔?
if((msq_id = get_ipc_id("/proc/sysvipc/msg",msq_key)) < 0 )
{
//msgget 鏂板缓涓€涓秷鎭槦鍒?鍏舵爣鍙疯繑鍥炲埌 msq_id
if((msq_id = msgget(msq_key,msq_flg)) < 0)
{
perror("messageQueue set error");
exit(EXIT_FAILURE);
}
}
return msq_id;
}

供应者:

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
/*
* Filename
: producer.c
* copyright
: (C) 2006 by zhonghonglie
* Function
: 寤虹珛骞舵ā鎷熺敓浜ц€呰繘绋?
*/
#include "ipc.h"
int main(int argc,char *argv[])
{
int rate;
//鍙湪鍦ㄥ懡浠よ绗竴鍙傛暟鎸囧畾涓€涓繘绋嬬潯鐪犵鏁?浠ヨ皟瑙h繘绋嬫墽琛岄€熷害
if(argv[1] != NULL) rate = atoi(argv[1]);
else rate = 3; //涓嶆寚瀹氫负 3 绉?
//鍏变韩鍐呭瓨浣跨敤鐨勫彉閲?
buff_key = 101;//缂撳啿鍖轰换缁欑殑閿€?
buff_num = 1;//缂撳啿鍖轰换缁欑殑闀垮害
pput_key = 102;//鐢熶骇鑰呮斁浜у搧鎸囬拡鐨勯敭鍊?
pput_num = 1; //鎸囬拡鏁?
shm_flg = IPC_CREAT | 0644;//鍏变韩鍐呭瓨璇诲啓鏉冮檺
//鑾峰彇缂撳啿鍖轰娇鐢ㄧ殑鍏变韩鍐呭瓨,buff_ptr 鎸囧悜缂撳啿鍖洪鍦板潃
buff_ptr = (char *)set_shm(buff_key,buff_num,shm_flg);
//鑾峰彇鐢熶骇鑰呮斁浜у搧浣嶇疆鎸囬拡 pput_ptr
pput_ptr = (int *)set_shm(pput_key,pput_num,shm_flg);
//淇″彿閲忎娇鐢ㄧ殑鍙橀噺
tobacco_key = 201; //鐢熶骇鑰呭悓姝ヤ俊鍙风伅閿€?
glue_key = 202; //鐢熶骇鑰呬簰鏂ヤ俊鍙风伅閿€?
paper_key=203; //鐢熶骇鑰?鐨勫悓姝ヤ俊鍙风伅閿€?
empty_key = 301; //娑堣垂鑰呭悓姝ヤ俊鍙风伅閿€?
mutex_key = 302; //娑堣垂鑰呬簰鏂ヤ俊鍙风伅閿€?
sem_flg = IPC_CREAT | 0644;
//鐢熶骇鑰呭悓姝ヤ俊鍙风伅鍒濆€艰涓虹紦鍐插尯鏈€澶у彲鐢ㄩ噺
sem_val = buff_num;
//鑾峰彇鐢熶骇鑰呭悓姝ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?prod_sem
empty_sem = set_sem(empty_key,sem_val,sem_flg);
//娑堣垂鑰呭垵濮嬫棤浜у搧鍙彇,鍚屾淇″彿鐏垵鍊艰涓?0
sem_val = 0;
//鑾峰彇娑堣垂鑰呭悓姝ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?cons_sem
paper_sem = set_sem(paper_key,sem_val,sem_flg);
glue_sem = set_sem(glue_key,sem_val,sem_flg);
tobacco_sem = set_sem(tobacco_key,sem_val,sem_flg);
//鐢熶骇鑰呬簰鏂ヤ俊鍙风伅鍒濆€间负 1
sem_val = 1;
//鑾峰彇鐢熶骇鑰呬簰鏂ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?pmtx_sem
mutex_sem = set_sem(mutex_key,sem_val,sem_flg);
int i=0;
//寰幆鎵ц妯℃嫙鐢熶骇鑰呬笉鏂斁浜у搧
while(1){
int d;
//濡傛灉缂撳啿鍖烘弧鍒欑敓浜ц€呴樆濉?
down(empty_sem);
//濡傛灉鍙︿竴鐢熶骇鑰呮鍦ㄦ斁浜у搧,鏈敓浜ц€呴樆濉?
down(mutex_sem);
//鐢ㄥ啓涓€瀛楃鐨勫舰寮忔ā鎷熺敓浜ц€呮斁浜у搧,鎶ュ憡鏈繘绋嬪彿鍜屾斁鍏ョ殑瀛楃鍙婂瓨鏀剧殑浣嶇疆
sleep(rate);
d=(i++)%3;
buff_ptr[*pput_ptr] = 'A'+ d;
printf("%d provider put: %c to Buffer[%d]\n",getpid(),buff_ptr[*pput_ptr],*pput_ptr);
//瀛樻斁浣嶇疆寰幆涓嬬Щ
*pput_ptr = (*pput_ptr+1) % buff_num;
//鍞ら啋闃诲鐨勭敓浜ц€?
up(mutex_sem);
//鍞ら啋闃诲鐨勬秷璐硅€?
if(d==0)
up(paper_sem);
if(d==1)
up(glue_sem);
if(d==2)
up(tobacco_sem);
}
return EXIT_SUCCESS;
}

三个抽烟者:

glue.c:

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
/*
Filename
: consumer.c
copyright
: (C) by zhanghonglie
Function
: 寤虹珛骞舵ā鎷熸秷璐硅€呰繘绋?
*/
#include "ipc.h"
int main(int argc,char *argv[])
{
int rate;
//鍙湪鍦ㄥ懡浠よ绗竴鍙傛暟鎸囧畾涓€涓繘绋嬬潯鐪犵鏁?浠ヨ皟瑙h繘绋嬫墽琛岄€熷害
if(argv[1] != NULL) rate = atoi(argv[1]);
else rate = 3; //涓嶆寚瀹氫负 3 绉?
//鍏变韩鍐呭瓨 浣跨敤鐨勫彉閲?
buff_key = 101; //缂撳啿鍖轰换缁欑殑閿€?
buff_num = 1; //缂撳啿鍖轰换缁欑殑闀垮害
cget_key = 103; //娑堣垂鑰呭彇浜у搧鎸囬拡鐨勯敭鍊?
cget_num = 1; //鎸囬拡鏁?
shm_flg = IPC_CREAT | 0644; //鍏变韩鍐呭瓨璇诲啓鏉冮檺
//鑾峰彇缂撳啿鍖轰娇鐢ㄧ殑鍏变韩鍐呭瓨,buff_ptr 鎸囧悜缂撳啿鍖洪鍦板潃
buff_ptr = (char *)set_shm(buff_key,buff_num,shm_flg);
//鑾峰彇娑堣垂鑰呭彇浜у搧鎸囬拡,cget_ptr 鎸囧悜绱㈠紩鍦板潃
cget_ptr = (int *)set_shm(cget_key,cget_num,shm_flg);
//淇″彿閲忎娇鐢ㄧ殑鍙橀噺
tobacco_key = 201; //鐢熶骇鑰呭悓姝ヤ俊鍙风伅閿€?
glue_key = 202; //鐢熶骇鑰呬簰鏂ヤ俊鍙风伅閿€?
paper_key=203; //鐢熶骇鑰?鐨勫悓姝ヤ俊鍙风伅閿€?
empty_key = 301; //娑堣垂鑰呭悓姝ヤ俊鍙风伅閿€?
mutex_key = 302; //娑堣垂鑰呬簰鏂ヤ俊鍙风伅閿€?
sem_flg = IPC_CREAT | 0644; //淇″彿鐏搷浣滄潈闄?
//鐢熶骇鑰呭悓姝ヤ俊鍙风伅鍒濆€艰涓虹紦鍐插尯鏈€澶у彲鐢ㄩ噺
sem_val = buff_num;
//鑾峰彇鐢熶骇鑰呭悓姝ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?prod_sem
empty_sem = set_sem(empty_key,sem_val,sem_flg);
//娑堣垂鑰呭垵濮嬫棤浜у搧鍙彇,鍚屾淇″彿鐏垵鍊艰涓?0
sem_val = 0;
//鑾峰彇娑堣垂鑰呭悓姝ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?cons_sem
glue_sem = set_sem(glue_key,sem_val,sem_flg);
sem_val = 1;
//鑾峰彇鐢熶骇鑰呬簰鏂ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?pmtx_sem
mutex_sem = set_sem(mutex_key,sem_val,sem_flg);
while(1){
//濡傛灉鏃犱骇鍝佹秷璐硅€呴樆濉?
down(glue_sem);
down(mutex_sem);
//鐢ㄨ涓€瀛楃鐨勫舰寮忔ā鎷熸秷璐硅€呭彇浜у搧,鎶ュ憡鏈繘绋嬪彿鍜?
sleep(rate);
printf("%d 1鍙峰惛鐑熻€?寰楀埌浜? %c鐑熻崏鍜岀焊 from Buffer[%d]\n",getpid(),buff_ptr[*cget_ptr],*cget_ptr);
//璇诲彇浣嶇疆寰幆涓嬬Щ
*cget_ptr = (*cget_ptr+1) % buff_num;
up(mutex_sem);
//鍞ら啋闃诲鐨勭敓浜ц€?
up(empty_sem);
}
return EXIT_SUCCESS;
}

tobacco.c:

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
/*
Filename
: consumer.c
copyright
: (C) by zhanghonglie
Function
: 寤虹珛骞舵ā鎷熸秷璐硅€呰繘绋?
*/
#include "ipc.h"
int main(int argc,char *argv[])
{
int rate;
//鍙湪鍦ㄥ懡浠よ绗竴鍙傛暟鎸囧畾涓€涓繘绋嬬潯鐪犵鏁?浠ヨ皟瑙h繘绋嬫墽琛岄€熷害
if(argv[1] != NULL) rate = atoi(argv[1]);
else rate = 3; //涓嶆寚瀹氫负 3 绉?
//鍏变韩鍐呭瓨 浣跨敤鐨勫彉閲?
buff_key = 101; //缂撳啿鍖轰换缁欑殑閿€?
buff_num = 1; //缂撳啿鍖轰换缁欑殑闀垮害
cget_key = 103; //娑堣垂鑰呭彇浜у搧鎸囬拡鐨勯敭鍊?
cget_num = 1; //鎸囬拡鏁?
shm_flg = IPC_CREAT | 0644; //鍏变韩鍐呭瓨璇诲啓鏉冮檺
//鑾峰彇缂撳啿鍖轰娇鐢ㄧ殑鍏变韩鍐呭瓨,buff_ptr 鎸囧悜缂撳啿鍖洪鍦板潃
buff_ptr = (char *)set_shm(buff_key,buff_num,shm_flg);
//鑾峰彇娑堣垂鑰呭彇浜у搧鎸囬拡,cget_ptr 鎸囧悜绱㈠紩鍦板潃
cget_ptr = (int *)set_shm(cget_key,cget_num,shm_flg);
//淇″彿閲忎娇鐢ㄧ殑鍙橀噺
tobacco_key = 201; //鐢熶骇鑰呭悓姝ヤ俊鍙风伅閿€?
glue_key = 202; //鐢熶骇鑰呬簰鏂ヤ俊鍙风伅閿€?
paper_key=203; //鐢熶骇鑰?鐨勫悓姝ヤ俊鍙风伅閿€?
empty_key = 301; //娑堣垂鑰呭悓姝ヤ俊鍙风伅閿€?
mutex_key = 302; //娑堣垂鑰呬簰鏂ヤ俊鍙风伅閿€?
sem_flg = IPC_CREAT | 0644; //淇″彿鐏搷浣滄潈闄?
//鐢熶骇鑰呭悓姝ヤ俊鍙风伅鍒濆€艰涓虹紦鍐插尯鏈€澶у彲鐢ㄩ噺
sem_val = buff_num;
//鑾峰彇鐢熶骇鑰呭悓姝ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?prod_sem
empty_sem = set_sem(empty_key,sem_val,sem_flg);
//娑堣垂鑰呭垵濮嬫棤浜у搧鍙彇,鍚屾淇″彿鐏垵鍊艰涓?0
sem_val = 0;
//鑾峰彇娑堣垂鑰呭悓姝ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?cons_sem
tobacco_sem = set_sem(tobacco_key,sem_val,sem_flg);
sem_val = 1;
//鑾峰彇鐢熶骇鑰呬簰鏂ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?pmtx_sem
mutex_sem = set_sem(mutex_key,sem_val,sem_flg);
while(1){
//濡傛灉鏃犱骇鍝佹秷璐硅€呴樆濉?
down(tobacco_sem);
down(mutex_sem);
//鐢ㄨ涓€瀛楃鐨勫舰寮忔ā鎷熸秷璐硅€呭彇浜у搧,鎶ュ憡鏈繘绋嬪彿鍜?
sleep(rate);
printf("%d 2鍙峰惛鐑熻€?寰楀埌浜? %c鑳舵按鍜岀焊 from Buffer[%d]\n",getpid(),buff_ptr[*cget_ptr],*cget_ptr);
//璇诲彇浣嶇疆寰幆涓嬬Щ
*cget_ptr = (*cget_ptr+1) % buff_num;
//鍞ら啋闃诲鐨勭敓浜ц€?
up(mutex_sem);
up(empty_sem);
}
return EXIT_SUCCESS;
}

paper.c:

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
/*
Filename
: consumer.c
copyright
: (C) by zhanghonglie
Function
: 寤虹珛骞舵ā鎷熸秷璐硅€呰繘绋?
*/
#include "ipc.h"
int main(int argc,char *argv[])
{
int rate;
//鍙湪鍦ㄥ懡浠よ绗竴鍙傛暟鎸囧畾涓€涓繘绋嬬潯鐪犵鏁?浠ヨ皟瑙h繘绋嬫墽琛岄€熷害
if(argv[1] != NULL) rate = atoi(argv[1]);
else rate = 3; //涓嶆寚瀹氫负 3 绉?
//鍏变韩鍐呭瓨 浣跨敤鐨勫彉閲?
buff_key = 101; //缂撳啿鍖轰换缁欑殑閿€?
buff_num = 1; //缂撳啿鍖轰换缁欑殑闀垮害
cget_key = 103; //娑堣垂鑰呭彇浜у搧鎸囬拡鐨勯敭鍊?
cget_num = 1; //鎸囬拡鏁?
shm_flg = IPC_CREAT | 0644; //鍏变韩鍐呭瓨璇诲啓鏉冮檺
//鑾峰彇缂撳啿鍖轰娇鐢ㄧ殑鍏变韩鍐呭瓨,buff_ptr 鎸囧悜缂撳啿鍖洪鍦板潃
buff_ptr = (char *)set_shm(buff_key,buff_num,shm_flg);
//鑾峰彇娑堣垂鑰呭彇浜у搧鎸囬拡,cget_ptr 鎸囧悜绱㈠紩鍦板潃
cget_ptr = (int *)set_shm(cget_key,cget_num,shm_flg);
//淇″彿閲忎娇鐢ㄧ殑鍙橀噺
tobacco_key = 201; //鐢熶骇鑰呭悓姝ヤ俊鍙风伅閿€?
glue_key = 202; //鐢熶骇鑰呬簰鏂ヤ俊鍙风伅閿€?
paper_key=203; //鐢熶骇鑰?鐨勫悓姝ヤ俊鍙风伅閿€?
empty_key = 301; //娑堣垂鑰呭悓姝ヤ俊鍙风伅閿€?
mutex_key = 302; //娑堣垂鑰呬簰鏂ヤ俊鍙风伅閿€?
sem_flg = IPC_CREAT | 0644; //淇″彿鐏搷浣滄潈闄?
//鐢熶骇鑰呭悓姝ヤ俊鍙风伅鍒濆€艰涓虹紦鍐插尯鏈€澶у彲鐢ㄩ噺
sem_val = buff_num;
//鑾峰彇鐢熶骇鑰呭悓姝ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?prod_sem
empty_sem = set_sem(empty_key,sem_val,sem_flg);
//娑堣垂鑰呭垵濮嬫棤浜у搧鍙彇,鍚屾淇″彿鐏垵鍊艰涓?0
sem_val = 0;
//鑾峰彇娑堣垂鑰呭悓姝ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?cons_sem
paper_sem = set_sem(paper_key,sem_val,sem_flg);
sem_val = 1;
//鑾峰彇鐢熶骇鑰呬簰鏂ヤ俊鍙风伅,寮曠敤鏍囪瘑瀛?pmtx_sem
mutex_sem = set_sem(mutex_key,sem_val,sem_flg);
while(1){
//濡傛灉鏃犱骇鍝佹秷璐硅€呴樆濉?
down(paper_sem);
//鐢ㄨ涓€瀛楃鐨勫舰寮忔ā鎷熸秷璐硅€呭彇浜у搧,鎶ュ憡鏈繘绋嬪彿鍜?
down(mutex_sem);
sleep(rate);
printf("%d 0鍙峰惛鐑熻€?寰楀埌浜? %c鐑熻崏鍜岃兌姘?from Buffer[%d]\n",getpid(),buff_ptr[*cget_ptr],*cget_ptr);
//璇诲彇浣嶇疆寰幆涓嬬Щ
*cget_ptr = (*cget_ptr+1) % buff_num;
up(mutex_sem);
//鍞ら啋闃诲鐨勭敓浜ц€?
up(empty_sem);
}
return EXIT_SUCCESS;
}

makefile:

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
hdrs = ipc.h
opts = -g -c
c_src = glue.c ipc.c
c_obj = glue.o ipc.o
d_src = paper.c ipc.c
d_obj = paper.o ipc.o
e_src = tobacco.c ipc.c
e_obj = tobacco.o ipc.o
f_src = provider.c ipc.c
f_obj = provider.o ipc.o
all: glue paper tobacco provider
glue: $(c_obj)
gcc $(c_obj) -o glue
glue.o: $(c_src) $(hdrs)
gcc $(opts) $(c_src)
paper: $(d_obj)
gcc $(d_obj) -o paper
paper.o: $(p_src) $(hdrs)
gcc $(opts) $(d_src)
tobacco: $(e_obj)
gcc $(e_obj) -o tobacco
tobacco.o: $(e_src) $(hdrs)
gcc $(opts) $(e_src)
provider: $(f_obj)
gcc $(f_obj) -o provider
provider.o: $(f_src) $(hdrs)
gcc $(opts) $(f_src)
clean:
rm glue provider paper tobaco *.o

eclipse连接Mysql

一、前期准备:

1.eclipse

2.Mysql workbench

3.jdbc

下载地址:下载地址

点击JDBC Driver for Mysql(Connector/j) 后面的下载

按箭头选择

之后会有登录或者注册oracle的按钮,登录就行了,没有账号注册就好了。然后下载完成。

二、搭建:

将下载好的jdbc放置到指定的文件夹下。

1.打开eclipse

​ 依次点击Window-preferences-java-Build Path-User Libraries

​ 如下图所示:

2.点击new按钮,出现如下界面:

3.在输入框中输入jdbc,选中下面的System library,点击ok

4.回到上一级界面,点击Add External JARs,打开到你的jdbc存放的目录,打开-ok

5.接下来是项目导入jar包,项目右键-Build Path-Configure Build Path

6.点击右侧Add Library… -User Library-Next。打上对勾点击finish

7.回到上一级界面就可以看到你添加的jdbc,点击Apply再点击ok。

8.这样在你的项目下就可以看到你导入的jdbc了

jdbc配置到这里就完成了。

然后是连接的测试代码了

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
package shiyanshi;

import java.sql.*;

public class test {

public static void main(String args[]) {

try {

Class.forName("com.mysql.cj.jdbc.Driver"); //加载MYSQL JDBC驱动程序

//Class.forName("org.gjt.mm.mysql.Driver");

System.out.println("Success loading Mysql Driver!");

}

catch (Exception e) {

System.out.print("Error loading Mysql Driver!");

e.printStackTrace();

}

try {

Connection connect = DriverManager.getConnection(

"jdbc:mysql://localhost:3306/test?useUnicode=true&characterEncoding=utf-8&useSSL=false&serverTimezone=GMT","root","xxxxxxx");

//连接URL为 jdbc:mysql//服务器地址/数据库名 ,后面的2个参数分别是登陆用户名和密码

}catch(SQLException e)

{

}

}

}

注意登录用户名一般都是root,密码要改成你自己设置的密码。当连接成功时,控制台会打印成功连接的信息。

之前参考的教程因为版本的原因出现了一些问题,现在我的代码是改好的,jdk和jdbc以及各软件都是比较新的版本,应该已经没多大问题了。

旋转Treap的简单实现

Treap=Tree+Heap

Treap是一棵二叉搜索树,它的左子树和右子树分别是一个Treap,和一般的二叉搜索树不同的是,Treap结构中每个节点x有两个域,一个是其关键字值key,一个是优先级数priority(他是一个独立选取的随机数),对于Treap结构,其关键字遵循二叉搜索树性质,其优先级遵循堆性质。但是这里要注意的是Treap和二叉堆有一点不同,就是二叉堆必须是完全二叉树,而Treap可以并不一定是。

在这里用的链表实现的旋转的Treap,简单实现是思路比较简单,但代码稍微有点繁琐。有点懒,不想整理了。

TreapNode结构如下:

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
template<class T>
struct treapNode
{
int key;//用于二叉搜索树的关键字
int pri;//用于堆性质的优先级数字
T element;//其中的元素
treapNode<T> *leftChild, //左子树
*rightChild,
*father; //右子树
treapNode() {leftChild = rightChild = father=NULL;}//构造函数
treapNode(const T& theElement):element(theElement)
{
leftChild = rightChild = father=NULL;
}
treapNode(const T& theElement,
treapNode *theLeftChild,
treapNode *theRightChild,
treapNode *theFather)
:element(theElement)
{
leftChild = theLeftChild;
rightChild = theRightChild;
father=theFather;
}
treapNode(int theKey,int thePri,T theElement)
{
key=theKey;
pri=thePri;
element=theElement;
leftChild = rightChild = father=NULL;
}
treapNode(int theKey,T theElement)
{
key=theKey;
pri=rand();
element = theElement;
leftChild=rightChild=father=NULL;
}
};

在节点中加入了父节点的指针,为了后面的旋转操作能够更简单一点,不加也是可以的,不过就要稍微复杂一点了。

插入操作:

不满足:当插入的节点为其父节点的左孩子时,应该右旋,否则左旋。

插入方法:

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
template<class T>
void treap<T>::insert(treapNode<T> *t)//插入方法,参数为一个treap节点。
{ t->leftChild=t->rightChild=t->father=NULL;
if(root==NULL)//当treap为空的时候情况
{
root=t;
treapSize++;
return ;
}
else//当treap不为空的时候,要找到要删除的位置
{
treapNode<T> *pp=root;
treapNode<T> *p=NULL;
while(pp!=NULL)
{ p=pp;
if(t->key<pp->key)//小于关键字时
pp=pp->leftChild;
else
{
if(t->key>pp->key)//大于关键字时
pp=pp->rightChild;
else//要插入的节点已经重复时
{
pp->element=t->element;
treapSize--;
return;
}
}
}
if(t->key>p->key)
{
p->rightChild=t;
t->father=p;
}
else
{
p->leftChild=t;
t->father=p;
}
}
treapNode<T> *q=t->father;//获取插入节点的父节点
//treapNode<T> *w=t->father;
int com;//判断是否循环继续的量
do//采用do-while结构,保证循环至少进行一次
{ com=0;
if(t->pri<q->pri&&t->key<q->key)//当优先级不满足堆的性质并且插入的节点在左孩子的位置时,此时应该右旋
{ if(t->rightChild!=NULL)//当插入节点的右孩子不为空的时候
{
q->leftChild=t->rightChild;//插入节点的右孩子变成其父节点的左孩子
t->rightChild->father=q;//插入节点的右孩子的父母指向插入节点的父母
t->rightChild=q;//父节点变为插入节点的右孩子
if(q->father!=NULL)//在这里分情况讨论,当其父节点的父节点不为空的时候
{
t->father=q->father;//插入节点的父节点为其父节点的父节点
if(q->father->leftChild==q)//判断父节点是否是父节点的父节点的左孩子
q->father->leftChild=t;//父节点的父节点左孩子变成插入节点
else
q->father->rightChild=t;
q->father=t; //父节点的父母变成插入节点
}
else//当其父节点的父节点为空时
{
t->father=NULL;//插入节点的父节点为空
root=t;
q->father=t;//父节点的父母变为插入节点
}
}
else//当插入节点的右孩子为空的时候
{ t->rightChild=q;
if(q->father!=NULL)//当其父节点的父节点不为空时
{
t->father=q->father;
if(q->father->leftChild==q) //判断父节点是否是父节点的父节点的左孩子
q->father->leftChild=t;
else
q->father->rightChild=t;
q->father=t;
q->leftChild=NULL;
}
else//当其父节点的父节点为空时
{
t->father=NULL;//父节点变为空
root=t;//此时根节点为当前插入的节点
t->rightChild=q;//插入节点的右孩子变为原来节点的父节点
q->father=t; //插入节点的父节点改成当前节点
q->leftChild=NULL;//插入节点的原来的父节点改为空值
}
} com=1;
}
if(t->pri<q->pri&&t->key>q->key)//当优先级不满足堆的性质并且插入的节点在右孩子的位置时,此时应该左旋
{ if(t->leftChild!=NULL)//当插入节点的左孩子不为空的时候
{
q->rightChild=t->leftChild;//插入节点的左孩子变成其父节点的右孩子
t->leftChild->father=q;//插入节点的左孩子的父母指向插入节点的父母
t->leftChild=q;//父节点变为插入节点的左孩子
if(q->father!=NULL)//在这里分情况讨论,当其父节点的父节点不为空的时候
{
t->father=q->father;//插入节点的父节点为其父节点的父节点
if(q->father->leftChild==q)//判断父节点是否是父节点的父节点的左孩子
q->father->leftChild=t;//父节点的父节点左孩子变成插入节点
else
q->father->rightChild=t;
q->father=t; //父节点的父母变成插入节点

}
else//当其父节点的父节点为空时
{
t->father=NULL;//插入节点的父节点为空
root=t;
q->father=t;//父节点的父母变为插入节点
q->leftChild=NULL;
}
}
else//当插入节点的左孩子为空的时候
{ t->leftChild=q;
if(q->father!=NULL)//当其父节点的父节点不为空时
{
t->father=q->father;
if(q->father->leftChild==q) //判断父节点是否是父节点的父节点的左孩子
q->father->leftChild=t;
else
q->father->rightChild=t;
q->father=t;
q->rightChild=NULL;
}
else//当其父节点的父节点为空时
{
t->father=NULL;
root=t;
t->leftChild=q;
q->father=t;
q->rightChild=NULL;
}
} com=1;
}
q=t->father;//更新插入节点的父节点
} while(q!=NULL&&com==1);//
treapSize++;
}

删除操作:

先找到要删除的节点的位置,然后判断要删除的节点的有几个孩子,然后再根据情况具体实现。

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
template<class T>
void treap<T>::erase(int key)
{
treapNode<T> *t=root;
while(t!=NULL)//首先找到要删除的节点
{
if(t->key<key)
t=t->rightChild;
else
{
if(t->key>key)
t=t->leftChild;
else//当相等时即找到要删除的节点了,跳出循环
break;
}
}
if(t==NULL)//treap中没有要删除的关键字的元素
{
cout<<"please put in correct data"<<key<<" ";
return ;
}
else//找到要删除的节点后
{
treapNode<T> *q=t->father;//找到要删除的节点的父节点
if(t->leftChild==NULL&&t->rightChild==NULL)//最简单的情况:当要删除的节点为叶节点时 ,并且此种情况下优先级的顺序不会改变
{
if(t==root)//其中的特殊情况:只有一个节点,即根节点
root=NULL;
else//不为根节点
{
if(key<q->key)//判断是左孩子还是右孩子
q->leftChild=NULL;
else
q->rightChild=NULL;
t->father=NULL;//让此节点的父节点为空
//t=NULL;//释放此节点
}
}
if((t->leftChild==NULL&&t->rightChild!=NULL)||(t->leftChild!=NULL&&t->rightChild==NULL))//当要删除的节点为有一个孩子时
{
if(q==NULL)//当要删除的节点为根节点时
{
if(t->leftChild!=NULL)//如果左孩子不为空
{ t->leftChild->father=NULL;
root=t->leftChild;
t->leftChild=NULL;
}
else//右孩子不为空
{
t->rightChild->father=NULL;
root=t->rightChild;
t->rightChild=NULL;
}
}
else//删除的节点不为根节点时
{
if(t->key<q->key)//当为其左孩子时
{
if(t->leftChild!=NULL)//当要删除的节点的左孩子不为空时
{
q->leftChild=t->leftChild;//删除节点的父节点的左孩子指向删除节点的左孩子
t->leftChild->father=q;//删除节点的左孩子的父亲指向删除节点的父亲
t->leftChild=NULL;//删除节点的左孩子指针指向空
t->father=NULL;//其父节点的指针指向空
}
else//当要删除的右孩子不为空时
{
q->leftChild=t->rightChild;
t->rightChild->father=q;
t->rightChild=NULL;
t->father=NULL;
}
}
else//当为其右孩子时
{
if(t->leftChild!=NULL)//当要删除的节点的左孩子不为空时
{
q->rightChild=t->leftChild;
t->leftChild->father=q;
t->leftChild=NULL;
t->father=NULL;
//t=NULL;
}
else//当删除的节点的右孩子不为空时
{
q->rightChild=t->rightChild;
t->rightChild->father=q;
t->rightChild=NULL;
t->father=NULL;
//t=NULL;
}
}
}
}
if(t->leftChild!=NULL&&t->rightChild!=NULL)//左右孩子均不为空的情况
{
if(t->leftChild->pri<t->rightChild->pri)//找出左右孩子中优先级较小的那个
{treapNode<T> *p=t->leftChild;//记录下当前节点的左孩子
if(p->rightChild==NULL)//当左孩子的右孩子为空时
{
if(q==NULL)//如果待删节点为根节点
{
p->rightChild=t->rightChild;
p->father=NULL;
t->rightChild->father=p;
t->leftChild=t->rightChild=NULL;
//t=NULL;
root=p;
}
else//待删节点不为根节点
{
p->rightChild=t->rightChild;
t->rightChild->father=p;
p->father=q;
if(q->leftChild==t)
q->leftChild=p;
else
q->rightChild=p;
t->father=t->leftChild=t->rightChild=NULL;
//t=NULL;
}

}
else//当左孩子的右孩子不为空时
{
t->father=p;
t->leftChild=p->rightChild;
p->rightChild->father=t;
p->rightChild=t;
if(q==NULL)
{
p->father=NULL;
root=p;
}
else
{
p->father=q;
if(q->leftChild==t)
q->leftChild=p;
else
q->rightChild=p;
}
erase(key);
}
}
else//找出左右孩子中优先级较小的那个
{treapNode<T> *p=t->rightChild;//记录下当前节点的右孩子
if(t->rightChild->leftChild==NULL)//当右孩子的左孩子为空时
{
if(q==NULL)//如果待删节点为根节点
{
p->leftChild=t->leftChild;
p->father=NULL;
t->leftChild->father=p;
t->leftChild=t->rightChild=NULL;
//t=NULL;
root=p;
}
else//待删节点不为根节点
{
p->leftChild=t->leftChild;
t->leftChild->father=p;
p->father=q;
if(q->leftChild==t)
q->leftChild=p;
else
q->rightChild=p;
t->father=t->leftChild=t->rightChild=NULL;
//t=NULL;
}

}
else//当右孩子的左孩子不为空时
{
t->father=p;
t->rightChild=p->leftChild;
p->leftChild->father=t;
p->leftChild=t;
if(q==NULL)
{
p->father=NULL;
root=p;
}
else
{
p->father=q;
if(q->leftChild==t)
q->leftChild=p;
else
q->rightChild=p;
}
erase(key);
}
}
}
treapSize--;
}
}