暂时未有相关云产品技术能力~
1. 删除所有存在缺失值的行语法:df.dropna(axis=0, how=‘any’, thresh=None, subset=None, inplace=False)参数:axis : {0 or ‘index’, 1 or ‘columns’}, default 00, or ‘index’:删除包含丢失值的行 1, or ‘columns’:删除包含丢失值的列默认为0how : {‘any’, ‘all’}, default ‘any’‘any’: 如果存在NA值,则删除该行或列‘all’: 如果所有值都是NA,则删除该行或列thresh: int,保留含有int个非空值的行subset: 对特定的列进行缺失值删除处理不同情况参数设置:删除所有有缺失值的行df.dropna()删除所有有缺失值的列df.dropna(axis=‘columns’)df.dropna(axis=1)删除所有值缺失的行df.dropna(how=‘all’)删除至少有两个非缺失值的行df.dropna(thresh=2)指定判断缺失值的列范围df.dropna(subset=[‘name’, ‘born’])使删除和的结果生效df.dropna(inplace=True)指定列的缺失值删除df.toy.dropna()2. 重置data的行号data = data.reset_index()3.设置日期为索引data = data.set_index('日期')4. 以5个数据作为一个数据滑动窗口,在这5个数据上取均值(收盘价)data['收盘价(元)'].rolling(5).mean()日期2016-01-04 NaN2016-01-05 NaN2016-01-06 NaN2016-01-07 NaN2016-01-08 15.695782016-01-11 15.563302016-01-12 15.473222016-01-13 15.347802016-01-14 15.420222016-01-15 15.436122016-01-18 15.547402016-01-19 15.603922016-01-20 15.579202016-01-21 15.342502016-01-22 15.243582016-01-25 15.128782016-01-26 14.932722016-01-27 14.832042016-01-28 14.832042016-01-29 14.810862016-02-01 14.717242016-02-02 14.734902016-02-03 14.722522016-02-04 14.849702016-02-05 15.111122016-02-15 15.455562016-03-11 15.492662016-03-14 15.536822016-03-15 15.487362016-03-16 15.42552 ... 2017-03-24 15.952002017-03-27 15.932002017-03-28 15.934002017-03-29 15.952002017-03-30 15.938002017-03-31 15.948002017-04-05 15.972002017-04-06 15.990002017-04-07 16.036002017-04-10 16.068002017-04-11 16.044002017-04-12 15.990002017-04-13 15.920002017-04-14 15.802002017-04-17 15.720002017-04-18 15.602002017-04-19 15.446002017-04-20 15.278002017-04-21 15.186002017-04-24 15.074002017-04-25 15.024002017-04-26 15.012002017-04-27 15.072002017-04-28 15.104002017-05-02 15.136002017-05-03 15.142002017-05-04 15.128002017-05-05 15.070002017-05-08 15.000002017-05-09 14.92000Name: 收盘价(元), Length: 309, dtype: float64将数据往后移动5天data.shift(5)index代码简称前收盘价(元)开盘价(元)最高价(元)最低价(元)收盘价(元)成交量(股)成交金额(元)涨跌(元)涨跌幅(%)均价(元)换手率(%)A股流通市值(元)总市值(元)A股流通股本(股)市盈率日期2016-01-04NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaN2016-01-05NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaN2016-01-06NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaN2016-01-07NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaN2016-01-08NaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaNNaN.........................................................309 rows × 18 columns作业import pandas as pd import numpy as np import matplotlib.pyplot as plt import matplotlib import seaborn as sns data = pd.read_excel('/home/mw/input/pandas1206855/600000.SH.xls') # 删除空值 data.dropna(axis=0, how='any', inplace=True) # 删除非数值行 tmp = [] for i in range(len(data)): if type(data.loc[i, '换手率(%)']) != float: tmp.append(i) data.drop(labels=tmp, inplace=True) # 重置索引,并设置新index data = data.reset_index() data = data.set_index('日期') # STEP1: 按照以下要求计算结果 # 1. 将数据往前移动5天 !注意此处!第25步往后移动5天! # data = data.shift(-5) # 第25步操作 # data = data.shift(-5) # 第一题操作 # 2. 使用expanding函数计算开盘价的移动窗口均值 meta_mean_sta = data['开盘价(元)'] exp_mean_sta = data['开盘价(元)'].expanding(min_periods=1, center=False, axis=0).mean() plot_df1_mean = pd.concat([meta_mean_sta, exp_mean_sta], axis=1, ignore_index=True) plot_df1_mean = plot_df1_mean.rename(columns={0: '原始数据', 1: '移动窗口均值'}) # 3. 绘制上一题的移动均值与原始数据折线图 # plt.rc('figure', figsize=(16, 6), dpi=150) # plt.plot(plot_df1_mean['原始数据']) # plt.plot(plot_df1_mean['移动窗口均值']) # plt.show() # 4. 计算布林指标 N = 20 # 布林线指标的参数最好设为20 # 第一步:计算MA 移动平均线 ma = data['收盘价(元)'].rolling(N).mean() # 第二步:计算标准差MD md = data['收盘价(元)'].rolling(N).std() # 第三步:计算MB、UP、DN线 分别对应 中轨线 上轨线 下轨线 mb = ma up = mb + (md * 2) dn = mb - (md * 2) # 5. 计算布林线并绘制 plt.rc('figure', figsize=(16, 6), dpi=150) plt.plot(ma, color='blue') plt.plot(up, color='red') plt.plot(dn, color='g') #plt.show() # STEP2: 为了简化最终提交的行数,所以这里只需要保留上轨线UP这一字段即可,并保存为 csv 文件 dic = {'上轨线': up} df = pd.DataFrame(dic).reset_index(drop=True) df = df.round(2) df.columns = ['answer'] df.dropna(axis=0, how='any', inplace=True) df['id'] = range(len(df)) df = df[['id', 'answer']] df.to_csv('answer_4.csv', index=False, encoding='utf-8-sig')
1.创建DataFramedata = {"col1":['Python', 'C', 'Java', 'R', 'SQL', 'PHP', 'Python', 'Java', 'C', 'Python'], "col2":[6, 2, 6, 4, 2, 5, 8, 10, 3, 4], "col3":[4, 2, 6, 2, 1, 2, 2, 3, 3, 6]} df = pd.DataFrame(data) dfcol1col2col30Python641C222Java663R424SQL215PHP526Python827Java1038C339Python462. 设置索引df['new_index'] = range(1,11) df.set_index('new_index')col1col2col3new_index1Python642C223Java664R425SQL216PHP527Python828Java1039C3310Python463.更改列名#方法二:(使用rename()函数:修改指定修改某列或某几列名字) df.rename(columns={'col1':'grammer', 'col2':'score', 'col3':'cycle','new_index':'id'}, inplace=True) df.head()grammerscorecycleid0Python6411C2222Java6633R4244SQL2154.更改全部列顺序order = df.columns[[0, 3, 1, 2]] # 或者order = ['xx', 'xx',...] 具体列名 df = df[order] dfscoreidgrammercycle061Python4122C2263Java6344R2425SQL1556PHP2687Python27108Java3839C39410Python65.提取第一列位置在1,10,15上的值# 方法一: df.iloc[[1,10,15], 0] # 方法二: df['createTime'][[1,10,15]] # 方法三: df['createTime'].take([1,10,15]) out:1 2020-03-16 10:58:4810 2020-03-16 10:34:1915 2020-03-16 10:52:14Name: createTime, dtype: datetime64[ns]6.判断数据框中所有行是否存在重复df.duplicated()7. 判断education列和salary列数据是否重复(多列组合查询)df.duplicated(subset = ['education','salary'])8.提取value列元素值大于60小于70的行df[(df['value'] > 60) & (df['value'] < 70)]9.提取salary列包含字符串(‘–’)的行# 方法一:isin() df[df['salary'].isin(['--'])] # 方法二:contains() df[df["salary"].str.contains("--")]10.提取value列和value1列出现频率最高的数字# 先将两列使用append()按行合并,再用计数函数: temp = df['value'].append(df['value1']) temp.value_counts(ascending=False)#不加index,返回的是一个Series temp.value_counts(ascending=False).index[:5] #返回一个数组作业import pandas as pd import numpy as np import re data = pd.read_excel(r'pandas120.xlsx') df = pd.DataFrame(data) # 提取学历为本科,工资在25k-35k的数据 df1 = df.loc[df['education'].isin(['本科']) & df['salary'].isin(['25k-35k']), :] # 提取salary列中以'40k'结尾的数据 df2 = df[df['salary'].str.endswith('40k')] # 提取薪资区间中最低薪资与最高薪资的平均值大于30k的行,只需提取原始字段('createTime', 'education', 'salary')即可 salary = df tmp = salary['salary'].str.extract(r'(\d+).*?(\d+)') # 正则匹配,分割字符串 salary['avg'] = ((tmp[0].astype('int') + tmp[1].astype('int')) / 2) # 切记 相加记得加小括号 df3 = salary[salary['avg'] > 30] df3 = df3.drop(columns=['avg']) # 将以上三题提取出来的行按照相同列进行合并,汇总到一个数据框中 answer_2 = pd.concat([df1, df2, df3], axis=0) # 将三列数据合并成一列,并设置列名为answer,最后保留id(数据行数、answer) data = pd.concat([answer_2.iloc[:, 0], answer_2.iloc[:, 1], answer_2.iloc[:, 2]]) df = pd.DataFrame(data, columns=['answer']) df['id'] = range(len(df)) df = df[['id', 'answer']] # 将结果保存为 csv 文件 df.to_csv(r'answer_2.csv', index=False, encoding='utf-8-sig')收获 inplace = True表示在原DataFrame上进行操作 · pf.columns[索引]返回的是一个Index列表,可以用来作为.iloc[]的参数· Pandas的insert()函数允许用户在指定的位置插入行和列。下面是insert()函数的语法:DataFrame.insert(loc, column, value, allow_duplicates=False)参数说明:• loc:表示要插入的数据的位置,以整数形式表示。• column:要插入的列名(如果未指定值,则必须传递列名)• value:要插入的值。可以是单个值或一组值。• allow_duplicates:如果设为True时,允许在同一位置上重复列名。ps:已经存在的列的列名不能重复添加· DataFrame对象take函数是一个用于返回指定的行的函数。语法:DataFrame.take(indices, axis=0, convert=None):参数:• indices:行的索引值(int或者list of ints)。• axis:可选参数,默认值为0。• convert: 可选参数,默认值为None。是否将索引转换为相应的列标签。返回:Ndarray或者其他可迭代对象中存储的行元素。·df.[] 里面也能对type为Series,数据为bool进行df数据筛选
重要的一些步骤1.将下面的字典创建为DataFrame¶data = {"grammer":['Python', 'C', 'Java', 'GO', np.NaN, 'SQL', 'PHP', 'Python'], "score":[1.0, 2.0, np.NaN, 4.0, 5.0, 6.0, 7.0, 10.0]} df = pd.DataFrame(data) dfgrammerscore0Python1.01C2.02JavaNaN3GO4.04NaN5.05SQL6.06PHP7.07Python10.02.交换两列位置#方法2 cols = df.columns[[1,0]] df = df[cols] dfpopularitygrammer01.0Python12.0C23.0Java34.0GO45.0NaN56.0SQL67.0PHP710.0Python3.提取popularity列最大值所在行df[df['popularity'] == df['popularity'].max()]popularitygrammer710.0Python4. 随机生成20个0-100的随机整数:Numpy.random.randint()np.random.randint(0, 100, 20)array([72, 68, 6, 41, 22, 63, 27, 43, 55, 26, 60, 89, 29, 83, 23, 68, 37,70, 42, 31])5.生成20个0-100固定步长的数:Numpy.arange()np.arange()函数分为一/两/三个参数三种情况:一个参数时,参数值为终点,起点取默认值0,步长取默认值1。两个参数时,第一个参数为起点,第二个参数为终点,步长取默认值1。三个参数时,第一个参数为起点,第二个参数为终点,第三个参数为步长。其中步长支持小数np.arange(0, 100, 5)array([ 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80,85, 90, 95])6. 生成20个指定分布(如标准正态分布)的数:Numpy.random.normal()np.random.normal(0, 1, 20)array([-0.20191223, 0.71407157, -0.9127828 , -0.65248936, 1.06513536,0.31551879, -0.71842129, -0.75766808, 0.488825 , -1.15330714,-0.50300377, -0.4937517 , -1.11488371, -0.70628642, -1.86134249,-0.03509479, 0.20524998, 0.04379019, 0.39735111, -1.58616105])7. 查看两列值相等的行号:Numpy.where()np.where()用法:np.where(condition, x, y): #满足条件(condition),输出x,不满足输出ynp.where(condition):只有条件(condition),没有x和y,则输出满足条件 (即非0) 元素的坐标(等价于numpy.nonzero)。当条件成立时,where返回的是每个符合condition条件元素的坐标,返回的是以元组的形式。df['cycle'] = [2.0, 3.0, 6.0, 3.0, 5.0, 2.0, 7.0, 5.0] #方法一:值相等 df[df['score'] == df['cycle']].index #方法二:np.where() np.where(df.score == df.cycle)(array([2, 4, 6]),)8.查找第一列的局部最大值位置:Numpy.sign()#思路:查找比它前一个和后一个数字都大数字 data = {"grammer":['Python', 'C', 'Java', 'GO', 'css', 'SQL', 'PHP', 'Python'], "score":[1.0, 2.0, 6.0, 4.0, 5.0, 6.0, 7.0, 10.0]} tem = np.diff(np.sign(np.diff(df['score']))) np.where(tem == -2)[0] + 1array([2])9. 计算两列欧式距离:Numpy.linalg.norm()#方法一:公式法 import math as mt mt.sqrt(sum((df['score']-df['cycle'])**2)) #方法二:numpy函数 np.linalg.norm(df['score'] - df['cycle']) 6.633249580710810. numpy其他一些统计基础函数np.min([1,2,3]) # 最小值 np.mean([1,2,3]) # 均值 np.median([1,2,3]) # 中位数 np.var([1,2,3]) # 方差 np.max([1,2,3]) # 最大值 np.ptp([1,2,3]) # 极差 np.std([1,2,3]) # 标准差 np.cov([1,2,3]) # 协方差 np.log1p([1,2,3]) # log(x + 1) np.log2([1,2,3]) # 以2为底的对数 np.expm1([1,2,3]) # e的x次幂-1 np.exp([1,2,3]) # e的次数幂 np.log([1,2,3]) # 取对数 np.sqrt([1,2,3]) # 开根号 np.exp2([1,2,3]) # 平方 array([2., 4., 8.])作业STEP1: 按照下列要求创建数据框已知10位同学的学号以及语数英三科成绩如下:(都是数值型数据)Id: [202001, 202002, 202003, 202004, 202005, 202006, 202007, 202008, 202009, 202010] Chinese: [98, 67, 84, 88, 78, 90, 93, 75, 82, 87] Math: [92, 80, 73, 76, 88, 78, 90, 82, 77, 69] English: [88, 79, 90, 73, 79, 83, 81, 91, 71, 78]要求:计算出每位同学的总成绩(SumScore)、平均成绩(MeanScore),最高成绩(MaxScore)、最低成绩(MinScore)、最高成绩与最低成绩的极差(PtpScore)、成绩方差(VarScore);并将所有数据保存到score数据框中;将多列数据(包括学生的ID)合并到一列中,列名设置为answer,最终只保留索引id(从0到100)和answer两列,统一保留整数;别人写的,挺好的import pandas as pd import numpy as np data = {'Id': ['202001','202002','202003','202004','202005','202006','202007','202008','202009','202010'], 'Chinese': ['98','67','84','88','78','90','93','75','82','87'], 'Math': ['92','80','73','76','88','78','90','82','77','69'], 'English': ['88','79','90','73','79','83','81','91','71','78']} df = pd.DataFrame(data) # 字典转换为DF df = df.astype('int') # object等格式转换为int #运算 a = df[['Chinese', 'Math', 'English']].apply(np.sum, axis=1) b = df[['Chinese', 'Math', 'English']].apply(np.mean, axis=1) c = df[['Chinese', 'Math', 'English']].apply(np.max, axis=1) d = df[['Chinese', 'Math', 'English']].apply(np.min, axis=1) e = df[['Chinese', 'Math', 'English']].apply(np.ptp, axis=1) f = df[['Chinese', 'Math', 'English']].var(axis='columns') # 查阅资料后得知,pandas df方差计算方法与numpy方差计算方法不一致 # 拼接共10列 df_concat = pd.concat([df['Id'], df['Chinese'], df['Math'], df['English'],a,b,c,d,e,f]) # 拼接列,series df_concat = df_concat.astype('int') print(df_concat) df2 = pd.DataFrame() # 新建df2 df2['answer'] = df_concat # 新增列,数据来自拼接列 df2['id'] = range(len(df_concat)) # 新增列,并按照answer数量添加id我写的,挺慢的import numpy as np import pandas as pd data = {"Id": [202001, 202002, 202003, 202004, 202005, 202006, 202007, 202008, 202009, 202010], "Chinese": [98, 67, 84, 88, 78, 90, 93, 75, 82, 87], "Math": [92, 80, 73, 76, 88, 78, 90, 82, 77, 69], "English": [88, 79, 90, 73, 79, 83, 81, 91, 71, 78]} mydata = pd.DataFrame(data) mydata['SumScore'] = mydata.loc[:,mydata.columns[1:4]].sum(axis=1) mydata['MeanScore'] = mydata.loc[:,mydata.columns[1:4]].sum(axis=1)/3 mydata['MaxScore'] = mydata.loc[:,mydata.columns[1:4]].max(axis=1) mydata['MinScore'] = mydata.loc[:,mydata.columns[1:4]].min(axis=1) mydata['PtpScore'] = np.ptp(mydata.loc[:,mydata.columns[1:4]],axis=1) mydata['VarScore'] = mydata.loc[:,mydata.columns[1:4]].var(axis=1) answer = pd.concat([mydata[c] for c in mydata.columns]) answer = answer.astype('int') mydata1 = pd.DataFrame() mydata1['answer'] = answer mydata1['id'] = range(len(answer)) mydata1 = mydata1[['id','answer']] print(mydata1) mydata1.to_csv('answer_1.csv',index=False,encoding='utf-8-sig') 收获在 Pandas 中,有三种方法可以用来索引和选择数据:[]、.iloc 和 .loc。[] 是最基本的索引和选择数据的方法,它通常用于选择单个列或多个列。使用 [] 选择多个列时,需要将列名以列表的形式传递。import pandas as pd df = pd.DataFrame({ 'A': [1, 2, 3], 'B': [4, 5, 6], 'C': [7, 8, 9] }) # 选择单个列 df['A'] # 输出:0 1 # 1 2 # 2 3 # Name: A, dtype: int64 # 选择多个列 df[['A', 'B']] # 输出: A B # 0 1 4 # 1 2 5 # 2 3 6 .iloc 是按照整数位置(从 0 开始)进行索引和选择数据的方法。使用 .iloc 可以选择单个元素、行、列或者一个区域。选择行和列时可以用整数位置或者切片。import pandas as pd df = pd.DataFrame({ 'A': [1, 2, 3], 'B': [4, 5, 6], 'C': [7, 8, 9] }) # 选择单个元素 df.iloc[0, 0] # 输出:1 # 选择单个行 df.iloc[0] # 输出:A 1 # B 4 # C 7 # Name: 0, dtype: int64 # 选择单个列 df.iloc[:, 0] # 输出:0 1 # 1 2 # 2 3 # Name: A, dtype: int64 # 选择一个区域 df.iloc[0:2, 0:2] # 输出: A B # 0 1 4 # 1 2 5.loc 是按照标签进行索引和选择数据的方法。使用 .loc 可以选择单个元素、行、列或者一个区域。选择行和列时必须使用标签。import pandas as pd df = pd.DataFrame({ 'A': [1, 2, 3], 'B': [4, 5, 6], 'C': [7, 8, 9] }) # 选择单个元素 df.loc[0, 'A'] # 输出:1 # 选择单个行 df.loc[0] # 输出:A 1 # B 4 # C 7 # Name: 0, dtype: int64 # 选择单个列 df.loc[:, 'A'] # 输出:0 1 # 1 2 # 2 3 # Name: A, dtype: int64 # 选择一个区域 df.loc[0:1, ['A', 'B']] # 输出: A B # 0
计算机网络:知识点总结(带问号是考题,不带的是知识点)文章目录计算机网络:知识点总结(带问号是考题,不带的是知识点)1.互联网的产生?2.三网融合?3.互连网和互联网?Internet与internet4.互联网的两个基本特点5.WWW?6.ISP、IXP?RFC?7.互联网的组成?8.端系统的两种通信方式9.集线器、路由器、以及交换机的区别?10.计算机网络性能指标11.分层网络体系结构及各层作用12.SDU与PDU?13.上面的服务用户只能看见服务,无法看见下面的协议;对上面的服务用户是透明的。透明怎么理解?14.数据链路层为啥要加首部和尾部?15.什么是物理层?16.信道 三种通信方式17.基带调制(也称编码)、带通调制18.自同步能力19.信道传输速率影响因素?奈氏准则和香农公式20.物理层下面的传输媒体分类?21.信道复用技术22.局域网中的中间设备(交换机)包含哪几层23.以太网24.数据链路层的信道类型?25.什么是链路?什么是数据链路?26.字节填充与零比特填充27.CRC计算冗余码?28.CRC与FCS区别?29.无比特差错与无传输差错30.PPP协议??组成?31.并行传输与串行传输、同步通信与异步通信(转载)32.PPP协议格式33.网络层的概述?34.虚电路和数据报服务的对比?35. 直接交付和间接交付?36.IP地址的表示方法37.IP地址的分类38.CIDR39.子网掩码怎么计算网络地址?40.按位与、或、异或操作?41. IP地址与MAC地址的区别?42.超网?43.路由聚合和划分?44.有mac地址为什么还需要ip地址?45.ARP如何获取IP地址与MAC地址的映射?46.首部校验和的计算?(与CRC区别开)47.IP数据报首部的可变部分?48.路由器的转发表如何进行转发?以及转发表匹配具体过程?49.二叉线索查找转发表?50.ICMP报文51.IPV6?52.静态路由和动态路由52. RIP例题53. 运输层的位置?54.运输层的作用?55.UDP与TCP的区别?56.不同进程如何进行识别?57.端口?58.停止等待协议?59.TCP报文首部格式?60.滑动窗口?61.RTO计算?(百度的 看不懂)62.TCP的流量控制?63.糊涂窗口综合征?64.TCP的拥塞控制?65.TCP的三次握手和4次挥手?66.应用层作用?67.DNS?域名结构?区和域的区别?68.域名服务器类型?递归查询与迭代查询?69.FTP、TFTP、NFS以及TELNET?70.HTTP?71.简述用户在浏览器中输入http://acm.sdtbu.edu.cn并回车到浏览器显示出页面的主要流程?1.互联网的产生?•1969 – 1990从单个网络 ARPANET 向互联网发展。•1985 – 1993建成了三级结构的互联网 。•1993 – 现在全球范围的多层次ISP结构的互联网。2.三网融合?电信网络:提供电话、电报以及传真等服务。有线电视网络:向用户传送各种电视节目。计算机网络:使用户能在计算机之间传送数据文件。发展最快的并起核心作用的是计算机网络“三网融合”:是指电信网络、有限电视网络融入计算机网络3.互连网和互联网?Internet与internet互联网:目前流行最广,事实上的标准译名。互连网:局部范围互连起来的计算机网络互联网 ≠ 互连网。Internet:全球最大、最重要的计算机网络。它采用TCP/IP协议族作为通讯的规则,且前身是美国的ARPANET。internet:是一个通用名词,它泛指由许多个计算机网络互连而成的计算机网络。它不一定采用TCP/IP协议族作为通讯的规则4.互联网的两个基本特点•连通性(connectivity)使上网用户之间可以非常便捷、非常经济地交换各种信息好像这些用户终端都彼此直接连通一样。•资源共享(•Sharing)实现信息共享、软件共享、硬件共享。由于网络的存在,这些资源好像就在用户身边一样地方便使用5.WWW?请百度万维网。。6.ISP、IXP?RFC?•互联网服务提供者ISP(Internet Service Provider): 在许多情况下,互联网服务提供者ISP就是一个进行商业活动的公司,例如,中国电信、联通、移动、腾讯、网易、3guu 提供接入到互联网的服务。 需要收取一定的费用•互联网交换点IXP(Internet eXchange Point): 世界上较大的 IXP 的峰值吞吐量都在 Tbit/s 量级。 允许两个网络直接相连并快速交换分组。 常采用工作在数据链路层的网络交换机。•标准发表:以RFC的形式(Request For Comments ):所有的 RFC 文档都可从互联网上免费下载。任何人都可以用电子邮件随时发表对某个文档的意见或建议。但并非所有的 RFC 文档都是互联网标准。只有很少部分的 RFC 文档最后才能变成互联网标准。RFC 文档按发表时间的先后编上序号(即 RFCxxxx,xxxx 是阿拉伯数字)。7.互联网的组成?从互联网的工作方式上看,可以划分为两大块:边缘部分: 由所有连接在互联网上的主机组成,由用户直接使用,用来进行通信(传送数据、音频或视频)和资源共享。核心部分: 由大量网络和连接这些网络的路由器组成,为边缘部分提供服务(提供连通性和交换)。8.端系统的两种通信方式客户/服务器方式: Client / Server 方式 简称为 C/S 方式对等方式: Peer to Peer 方式 简称为 P2P 方式9.集线器、路由器、以及交换机的区别?了解三者工作方式(比喻法,具体官方解释请百度):一、区分集线器、交换机、路由器(比喻法)某一天,你到你女友小芳(暂定这个名字吧)就读的学校去找她,那么你的做法是什么呢:一、集线器的工作方式:你站到学校中庭,大喊一声“小芳,我来你找你了!” (广播)如果这个时候正好有别人也在大喊大叫,你就必须等他喊完了再喊。(排队)如果你喊的时候不巧碰上另一个人跟你同时喊,那么你和他喊的内容都不能被听见。(冲突)你喊的时候,是听不见别人说什么的,只有喊完了才开始竖起耳朵听。(半双工工作方式、监听)果然,对面楼里传来了你女友的声音“你去死吧!” (响应)二、交换机的工作方式:你女友事先通知了你她的手机号码(Mac地址)。你拨通了她的手机。(建立连接)对她说“我来找你了,因为我想你想得要死,我的甜心,我的宝贝……”。(独享信道)你的女友听得不耐烦,没等你说完就回了一句“肉麻死了”! (全双工方式)三、路由器的工作方式:你事先把你所有女友所在的XX系XX级XX班XX号座位的信息记录在你的粉红色笔记本上(建立路由表)你找到了小芳的地址(IP地址),并且确定了如何才能找到她的途径 (路由选择) 。你到学校门房问到了XX系所在的楼,又到XX系问到了XX班的教室,又到XX教室问到了XX号座位的位置……经过N次询问(N跳),你终于来到了小芳的面前。知乎https://www.zhihu.com/question/21690010具体区别:路由器交换机集线器工作层次网络层数据链路层物理层转发依据IP地址Mac地址Mac地址功能连接不同的网络连接局域网中的主机连接局域网中的主机宽带影响共享宽带独享宽带共享宽带传输模式-全双工或半双工半双工注:10.计算机网络性能指标速率:吞吐量:时延:时延带宽积:往返时间:利用率:11.分层网络体系结构及各层作用应用层:运输层:网络层:数据链路层:物理层:12.SDU与PDU?SDU: OSI 把层与层之间交换的数据的单位称为服务数据单元 SDU (Service Data Unit)。PDU: OSI 参考模型把对等层次之间传送的数据单位称为该层的协议数据单元 PDU (Protocol Data Unit)。任何两个同样的层次把 PDU (即数据单元加上控制信息)通过水平虚线直接传递给对方。这就是所谓的“对等层”之间的通信SDU 可以与 PDU 不一样。 例如:可以是多个 SDU 合成为一个 PDU,也可以是一个 SDU 划分为几个 PDU。13.上面的服务用户只能看见服务,无法看见下面的协议;对上面的服务用户是透明的。透明怎么理解?可以理解为 下层提供给上层服务,上层不需要懂其下层原理,实现了上下层的“分离”。既下层是对上层来说,是透明的。14.数据链路层为啥要加首部和尾部?利用首部和尾部进行帧定界(既确定帧的边界)时钟同步,差错检验首部是前同步码,可以使接收方和发送方的时钟同步。尾部信息含有CRC校验码,可以用来检验信息在传输来的过程中是否出错。15.什么是物理层?基本概念: 物理层考虑的是怎么样才能在连接各种计算机的传输媒介上传输比特流,并且尽可能屏蔽掉不同传输媒介和通讯手段的差异,而不是指具体的传输媒介。16.信道 三种通信方式信道: 一般是用来表示向某一方向传送信息的媒体,一条信道往往包含一条发送信道和一条接收信道从通信的双方信息交互的方式,可以有下面三种方式:单向通信(单工通信): 只能由一个方向的通信而没有反方向的交互。无线电广播或有线电视广播就属于这种类型双向交替通信(半双工通信): 通信双方都可以发送信息,但不能双方同时发送(当然也不能同时接收)。这种通信方式是一方发送另一方接收,过段时间后可以反过来。双向同时通信(全双工通信): 通信的双方可以同时发送和接收信息
(9)函数名:void preservation(double money)函数功能:更新用户信息输 入:已用金额输 出:算法描述:(10)函数名:void manage()函数功能:管理员登录输 入:输 出:算法描述:(11)函数名:void inforSheet()函数功能:会员信息查看输 入:无输 出:无算法描述:(12)函数名:void recharge()函数功能:充值输 入:无输 出:无算法描述:(13)函数名:void Begin()函数功能:过场动画输 入:无输 出:无算法描述:(14)函数名:void menu()函数功能:输 入:输 出:算法描述:三、UI设计效果1.启动界面:一个简单的进场动画。2.开始界面:几个功能展示。3.用户界面:有会员的基本信息。4.信息打印界面:5.项目到目前为止存在的不足及改正措施:(1)界面显示不够美观。(2)数据打印不够整齐。(3)没能完成在计时的同时进行游戏(在里面添加c语言小游戏)功能实现(大二的我现在也解决不了,大一本心是想把用c写的一些小游戏,用上去)四、代码实现(记得添加一个Account library.txt 文本文档)tips:管理员系统进入方法:在用户菜单下输入“管理员登录”。账号默认为(账号:admin 密码:1111)验证码查看方法:打开c文件—>打开vercode.txt用户注册:账号是身份证号,初始密码:123456(可修改)#include <stdio.h> #include <string.h> #include <windows.h> #include<time.h> #include<stdint.h> #include <stdlib.h> #define MAX 19 #define MIN 16 #define MIN_INPUT 0x20 #define MAX_INPUT 0x7e time_t timer; struct tm *tblock; int userPrint;//用于用户输入验证码 typedef struct { char vipAccount[MAX]; //会员账号(身份证号) char vipPassword[MIN]; //会员密码 char vipID[17]; //未知错误(1) char vipPhoneNum[11]; //会员绑定手机号 double vipAmount; //会员剩余金额 } VIP; VIP user;//便于操作 typedef struct clock { int hour; //小时 int minute; //分钟 int second; //秒 } Clock; Clock startime;//用于存储上机开始时间 Clock endtime;//用于存储下机时间 Clock temptime;//用于存储临时时间 void vipMenu()//会员界面ui { system("cls"); printf("_________________________________________\n"); printf("|*会员信息 |\n"); printf("|*账号:%c%c%c%c%c%c%c%c%c%c%c%c%c%c**** |\n",user.vipAccount[0],user.vipAccount[1],user.vipAccount[2],user.vipAccount[3],user.vipAccount[4],user.vipAccount[5],user.vipAccount[6],user.vipAccount[7],user.vipAccount[8],user.vipAccount[9],user.vipAccount[10],user.vipAccount[11],user.vipAccount[12],user.vipAccount[13]); printf("|*手机号:%c%c%c****%c%c%c%c |\n",user.vipPhoneNum[0],user.vipPhoneNum[1],user.vipPhoneNum[2],user.vipPhoneNum[7],user.vipPhoneNum[8],user.vipPhoneNum[9],user.vipPhoneNum[10]); printf("|*余额:%lf |\n",user.vipAmount); printf("| |\n"); printf("|===========会员界面====================|\n"); printf("|=======================================|\n"); printf("|======上机===========下机==============|\n"); printf("|======使用帮助=======密码修改==========|\n"); printf("|_______________________________________|\n"); if(user.vipAmount<0) { printf("余额不足,请充值"); system("pause"); menu(); } else { userChoices(); } } void GetPassword(char* pszPw)//密码回显“*” { char ch; int i=0; int flag=1; while( ( ch = (char)getch() ) ) { flag=1; if ( ch == 13) { pszPw[i++]=0; break; } else if ( ch >= MIN_INPUT && ch <= MAX_INPUT) /*所有可打印字符*/ { pszPw[i++]=ch; } else if ( ch == 8 && i> 0 ) //退格键 { pszPw[i--] = 0; flag = 0; putchar( ch ); putchar( ' ' ); putchar( ch ); } else flag= 0; if(flag) putchar('*'); } pszPw[i]=0; } void manage()//管理员登录 { char userAccount[5]; char userPass[5]; printf("账号:"); scanf("%s",userAccount); printf("密码:"); scanf("%s",userPass); if(strcmp(userAccount,"admin")==0 && strcmp(userPass,"1111")==0) { maMenu(); } } void maMenu()//管理员界面 { system("cls"); printf("_________________________________________\n"); printf("|===========管理员界面==================|\n"); printf("|=======================================|\n"); printf("|======会员信息总览========会员充值=====|\n"); printf("|======使用帮助=========================|\n"); printf("|_______________________________________|\n"); maChoice(); } void maChoice()//管理员选择 { char choice[20]; scanf("%s",choice); if(strcmp(choice,"会员信息总览")==0) { memberInfor(); } else if(strcmp(choice,"会员充值")==0) { memberRecharge(); } } void memberInfor()//会员信息总览 { int i = 0; VIP mangePass; FILE *fpp = fopen("Account library.txt","r+"); printf("|NO| |account number| |password| |Binding| |balance|\n"); printf("------------------------------------------------------------------------------\n"); while(!feof(fpp)) { i++; fscanf(fpp,"%s",mangePass.vipAccount); printf("%04d %s ",i,mangePass.vipAccount); fscanf(fpp,"%s",mangePass.vipPassword); printf("%s ",mangePass.vipPassword); fscanf(fpp,"%s",mangePass.vipPhoneNum); printf("%s ",mangePass.vipPhoneNum); fscanf(fpp,"%s",mangePass.vipID); printf("%s\n",mangePass.vipID); } maChoice(); } void memberRecharge()//会员充值 { int i = 3; int condiTime = 0; int flag = 0; char key[MAX];//用于转移数据 char account[MAX];//充值账户 double reMoney; while(1) { rename("Account library.txt","Accountlibrary.txt"); FILE *fp = fopen("Accountlibrary.txt","r+"); FILE *fpp = fopen("Account library.txt","wt+"); printf("输入充值账号:"); scanf("%s",account); printf("输入充值金额:"); scanf("%lf",&reMoney); while(fscanf(fp,"%s",key)!=EOF) { fprintf(fpp,"%s",key); condiTime++; if(condiTime%4!=0) { fprintf(fpp," "); } else { fprintf(fpp,"\n"); } if(strcmp(account,key)==0) { flag = 1; double balance; fscanf(fp,"%s",key); fprintf(fpp,"%s ",key); fscanf(fp,"%s",key); fprintf(fpp,"%s ",key); fscanf(fp,"%lf",&balance); balance = balance + reMoney; fprintf(fpp,"%lf\n",balance); condiTime = 0; } } fclose(fpp); fclose(fp); system("del Accountlibrary.txt"); if(!flag) { printf("账户不存在,请重新输入:"); } else { printf("账户信息已更新\n"); while(i>1) { printf("返回用户界面中.......%ds",i--); printf("\r"); Sleep(1000); } system("pause"); maMenu(); } } } void enroll()//注册 { char choice; int flag ;//用于判断是否重复手机号的标志 VIP user; printf("正在注册...\n"); while(1) { char account[MAX]; char phoneNum[12]; printf("身份证号:"); scanf("%s",user.vipAccount); //身份证号查重 FILE *pf = fopen("Account library.txt","r+"); while(fscanf(pf,"%s",account)!=EOF) { if(strcmp(account,user.vipAccount)==0) { printf("账号已被注册,请重新输入:"); enroll(); } } fclose(pf); if(strlen(user.vipAccount)!=18) { continue; } else if(strlen(user.vipAccount)==18) { unsigned long curTime; time(&timer); tblock = gmtime(&timer); curTime = (tblock->tm_year+1900)*10000+(tblock->tm_mon+1)*100+tblock->tm_mday; //printf("%ld",curTime); unsigned long tempTime; tempTime = (user.vipAccount[6]-'0')*10000000+(user.vipAccount[7]-'0')*1000000+(user.vipAccount[8]-'0')*100000+(user.vipAccount[9]-'0')*10000+(user.vipAccount[10]-'0')*1000+(user.vipID[11]-'0')*100+(user.vipID[12]-'0')*10+(user.vipID[13]-'0'); //printf("%ld",tempTime); if(curTime-tempTime>180000) { int flag = 0;//用于判断 //printf("通过"); while(1) { flag = 0; printf("输入手机号:"); scanf("%s",user.vipPhoneNum); //手机号查重 FILE *pf = fopen("Account library.txt","r+"); while(fscanf(pf,"%s",phoneNum)!=EOF) { if(strcmp(phoneNum,user.vipPhoneNum)==0) { printf("手机号已被注册,请重新输入:"); flag = 1; break; } } fclose(pf); if(flag) { continue; } if(strlen(user.vipPhoneNum)!=11) { printf("输入有误,重新输入\n"); continue; } else { int j; //读取文件中验证码 while(1) { int i = 3; j = verCode(); printf("请输入验证码:"); scanf("%d",&userPrint); if(userPrint==j) { FILE *fp = fopen("Account library.txt","a+"); fprintf(fp,"%s 123456 %s 0.000000\n",user.vipAccount,user.vipPhoneNum); fclose(fp); printf("成功注册,请记住你的账号(身份证号)和密码(默认:123456)\n"); printf("》》》请求发送中》》》》》\n"); while(i>1) { printf(".......%d",i--); printf("\r"); Sleep(1000); } system("pause"); signUp(); } else { printf("验证码错误,是否重新输入手机号(Y/N):"); scanf("\n"); scanf("%c",&choice); if(choice == 'Y') { break; } else { printf("已经重新发送验证码,"); continue; } } } } } } else { printf("未成年人禁止上网\n"); continue; } } } } void signUp()//登录 { int flag = 0;//账号正确的标志 int count = 0; FILE *fp; char userAccount[18]; char userPass[16]; while(1) { printf("账号:"); scanf("%s",userAccount); fp = fopen("Account library.txt","r"); while(!feof(fp)) { fscanf(fp,"%s",user.vipAccount); if(strcmp(userAccount,user.vipAccount)==0) { flag = 1; fscanf(fp,"%s",user.vipPassword); fscanf(fp,"%s",user.vipPhoneNum); fscanf(fp,"%lf",&user.vipAmount); while(count<3) { printf("密码:"); GetPassword(userPass); if(strcmp(userPass,user.vipPassword)==0) { fclose(fp); //printf("登录成功"); vipMenu(); } else if(count<3) { printf("密码有误请重新输入:"); count++; } } while(1) { int j = verCode(); int userVerify; printf("验证码:%d\n请输入以上验证码:",j); scanf("%d",&userVerify); if(userVerify==j) { printf("重新输入密码:"); GetPassword(userPass); if(strcmp(userPass,user.vipPassword)==0) { fclose(fp); // printf("登录成功"); vipMenu(); } } } } else { fscanf(fp,"%s",user.vipPassword); fscanf(fp,"%s",user.vipPhoneNum); fscanf(fp,"%lf",&user.vipAmount); } } if(!flag) { fseek(fp,0L,0); printf("账号不存在,请重新输入\n"); fclose(fp); } } } int verCode()//发送验证码 { int i; int j; srand((int)time(0));//初始化时间 j = rand()%9999; FILE *fp = fopen("vercode.txt","w+"); //printf("%d",j);//需要写入文件 fprintf(fp,"%d",j); fclose(fp); return j; } void Begin()//开始ui { printf("正在启动网吧管理系统 请您遵守网吧管理规定,看好随身物品。\n"); char str[100] = ">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"; int i,j; for(i = 0; i<strlen(str); i++) { printf("%c",str[i]); Sleep(10); } printf("\n加载完成\n"); system("pause"); system("cls"); } void menu()//菜单界面ui { system("cls"); printf("==================================\n"); printf("===========网吧管理系统===========\n"); printf("==================================\n"); printf("======会员登录=======成为会员=====\n"); printf("======使用帮助=======找回密码=====\n"); printf("==================================\n"); userChoice(); } void userChoice()//用户选择1 { while(1) { char userchoice[20]; scanf("%s",userchoice); if(strcmp(userchoice,"会员登录")==0) { // printf("登录"); signUp(); } else if(strcmp(userchoice,"成为会员")==0) { printf("注册"); enroll(); } else if(strcmp(userchoice,"使用帮助")==0) { printf("帮助"); //userMal(); } else if(strcmp(userchoice,"管理员登录")==0) { manage(); } else if(strcmp(userchoice,"找回密码")==0) { getPassBack(); } else { printf("输入有误,请重新输入"); } } } void getPassBack() { int j,i; int flag = 0; //是否有对应账号的标签 char key[11]; while(1) { printf("输入绑定手机号:"); scanf("%s",key); if(strlen(key)!=11) { printf("输入有误,重新输入\n"); continue; } VIP mangePass; FILE *fpp = fopen("Account library.txt","r+"); while(!feof(fpp)) { fscanf(fpp,"%s",mangePass.vipAccount); fscanf(fpp,"%s",mangePass.vipPassword); fscanf(fpp,"%s",mangePass.vipPhoneNum); fscanf(fpp,"%s",mangePass.vipID); if(strcmp(key,mangePass.vipPhoneNum)==0) { flag = 1; break; } } if(flag) { printf("已经发送验证码,请输入:"); j = verCode(); while(1) { scanf("%d",&userPrint); if(userPrint==j) { printf("|NO| |account number| |password| |Binding| |balance|\n"); printf("------------------------------------------------------------------------------\n"); printf("%04d %s ",i,mangePass.vipAccount); printf("%s ",mangePass.vipPassword); printf("%s ",mangePass.vipPhoneNum); printf("%s\n",mangePass.vipID); } else { printf("输入有误!!重新输入"); } } } } } void userChoices()//用户选择2 { char userchoice[10]; while(1) { scanf("%s",userchoice); if(strcmp(userchoice,"上机")==0) { getOn(); } else if(strcmp(userchoice,"下机")==0) { printf("尚未上机"); } else if(strcmp(userchoice,"使用帮助")==0) { } else if(strcmp(userchoice,"密码修改")==0) { changePass(); } } } void getOn()//上机 { int endWhile = 0;//用于下机结束循环 int vipChoice;//区域选项 int upOdown;//是否下机的选项 double money;//单价 while(1) { Clock a; printf("选择区域:1.VIP区\n2.游戏区\n3.普通区"); scanf("%d",&vipChoice); switch(vipChoice) { case 1: money = 0.25; break; case 2: money = 0.16; break; case 3: money = 0.05; break; default: getOn(); } while(!kbhit()) { printf("\r"); if(endWhile == 0) { timestar(); endWhile = 1; } timeend(); Sleep(1000); a.second = temptime.second - startime.second; if(a.second<0) { a.second = a.second + 60; temptime.minute--; } a.minute = temptime.minute - startime.minute; if(a.minute<0) { a.minute = a.minute + 60; temptime.hour--; } a.hour = temptime.hour - startime.hour; printf("%02d:%02d:%02d", a.hour, a.minute,a.second); if(a.minute%15==0 && a.minute!=0 && a.second==0) { //自动保存 money = money*15; preservation(money); } } printf("是否下机?(1/0)"); scanf("%d",&upOdown); if(upOdown==1) { if(vipChoice == 1) { //自动保存 money = money *((a.hour*60+a.minute)%15); preservation(money); break; } else if(vipChoice == 2) { //自动保存 money = money *((a.hour*60+a.minute)%15); preservation(money); break; } else if(vipChoice == 3) { //自动保存 money = money *((a.hour*60+a.minute)%15); preservation(money); break; } } else { printf("重新"); } } } void preservation(double money)//更新用户信息 { int i = 3; int condiTime = 0; double balance; char key[19];//用于文件数据的转移 rename("Account library.txt","Accountlibrary1.txt"); FILE *fp = fopen("Accountlibrary1.txt","r+"); FILE *fpp = fopen("Account library.txt","wt+"); while(fscanf(fp,"%s",key)!=EOF) { fprintf(fpp,"%s",key); condiTime++; if(condiTime%4!=0) { fprintf(fpp," "); } else { fprintf(fpp,"\n"); } if(strcmp(user.vipPhoneNum,key)==0) { double balance; fscanf(fp,"%lf",&balance); balance = balance - money; fprintf(fpp,"%lf\n",balance); condiTime++; } } fclose(fpp); fclose(fp); system("del Accountlibrary1.txt"); printf("账户信息已更新\n"); while(i>1) { printf("返回用户界面中.......%ds",i--); printf("\r"); Sleep(1000); } system("pause"); } void changePass()//密码修改 { int i = 3; int j; char phone[11]; while(1) { printf("输入绑定手机号:"); scanf("%s",phone); if(strcmp(phone,user.vipPhoneNum)==0) { printf("已经发送验证码,请输入:"); j = verCode(); while(1) { scanf("%d",&userPrint); if(userPrint==j) { int condiTime = 0; char key[19];//用于文件数据的转移 printf("输入新密码:"); scanf("%s",user.vipPassword); rename("Account library.txt","Accountlibrary1.txt"); FILE *fp = fopen("Accountlibrary1.txt","r+"); FILE *fpp = fopen("Account library.txt","wt+"); while(fscanf(fp,"%s",key)!=EOF) { condiTime++; if(strcmp(key,user.vipAccount)!=0) { fprintf(fpp,"%s ",key); } else { fprintf(fpp,"%s ",key); fprintf(fpp,"%s ",user.vipPassword); fscanf(fp,"%s",key); condiTime++; } if(condiTime%4==0) { fprintf(fpp,"\n"); } } fclose(fpp); fclose(fp); system("del Accountlibrary1.txt"); printf("成功修改密码,请记住你的账号(身份证号)和新密码\n"); printf("》》》请求发送中》》》》》\n"); while(i>1) { printf(".......%d",i--); printf("\r"); Sleep(1000); } system("pause"); vipMenu(); } else { printf("验证码错误,重新输入:"); } } } else { printf("手机号输入错误"); } } } void timestar()//记录开始时间 { time_t now ; struct tm *p ; time(&now) ; p = localtime(&now) ; startime.hour = p->tm_hour; startime.minute = p->tm_min; startime.second = p->tm_sec; } void timeend()//记录结束时间 { time_t now ; struct tm *p ; time(&now) ; p = localtime(&now) ; temptime.hour = p->tm_hour; temptime.minute = p->tm_min; temptime.second = p->tm_sec; } int main() { Begin(); menu(); return 0; }
拓扑排序:按照有向图给出的次序关系,将图中顶点排成一个线性序列,对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关系,由此所得顶点的线性序列称之为拓扑有序序列。显然对于有回路的有向图得不到拓扑有序序列,因为有回路的话,顶点的先后次序就不确定了。例如:例如,下图,我们可以人为限定次序:A B C D 或 A C B D解释:该输出顺序特点就是后面的顶点输出必然后于该顶点的前驱顶点算法:从有向图中选取一个没有前驱(没有在它之前活动)的顶点,输出之;从有向图中删去此顶点以及所有以它为尾的弧;重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。没有被打印输出的顶点构成回路了。那么、如何找到一个没有前驱的顶点呢?通过解释看出,没有前驱的顶点的入度为零。我们每次重复第一个操作就是找到图中入度为零的点并且输出。当然问题来了,如果图中有多个入度为零的顶点,如何判断谁先输出。或者怎么依次输出它们?答:这里可以利用栈(队列),暂时将其入栈(入队),每次输出栈顶(队头)元素。因为每次都是输出的入度为零的节点,不同的存储方式可能造成输出顺序的不同,但是他们都遵循拓扑排序。都是拓扑排序的一种情况。注意:ingress[]:用来存每个顶点的入度图的存储结构:邻接表(不懂可以看我的上一篇随笔)获取各顶点入度的函数:void FindID(AdjList G, int indegree[MAX_VERTEX_NUM]){ int i; ArcNode *p; for(i=0;i<G.vexnum;i++) /*--初始化度数组----*/ indegree[i]=0; for(i=0;i<G.vexnum;i++){ p=G.vertexes[i].firstarc; //找邻接点 while(p!=NULL){ indegree[p->adjvex]++; p=p->nextarc; } } }入栈方法输出拓扑排序bool TopologicalSort(ALGraph G) { SeqStack *s; s = (SeqStack*)malloc(sizeof(SeqStack)); InitStack(s); /*---初始化栈---*/ int count,indegree[G.vexnum]; /*--count:用来计数---*/ ArcNode *p; FindIndegree(G, indegree); /*---获取各顶点入度的函数---*/ int j; for(j = 0;j<G.vexnum;j++) { if(indegree[j]==0) push(s,j); /*--找到一个度为零的入栈----*/ } count = 0; while(!IsEmpty(s)) /*---栈非空---*/ { int i = 0; Pop(s,&i); /*---度为零的出栈并输出---*/ printf("%d ",i); count++; for( p = G.adjlist[i].firstarc;p;p = p->nextarc) { /*---将出栈的顶点尾部的弧’删除‘(其实是将所尾部连接的顶点的度减一)---*/ indegree[p->adjvex]--; if(!indegree[p->adjvex]) push(s,p->adjvex); } } if(count == G.vexnum) /*---出栈顶点数目等于图的顶点数说明图中无回路,否则有回路---*/ { return true; } return false; }入对方法输出拓扑排序int TopoSort(AdjList G){ Queue Q; /*队列存储入度为0*/ int indegree[MAX_VERTEX_NUM]; //存放每个顶点的入度值 int i,count,k; //count计数,然后和有向图中顶点总数比较 ArcNode*p; FindID(G,indegree); InitStack(&S); //初始化队列 for(i=0;i<G.vexnum;i++) if(indegree[i]==0) EnterQueue(&Q,i); //入队 count=0; while(!StackEmpty(S)){ DeleteQueue(&Q,&i); //一个入度为0的点出队 printf("%c",G.vertex[i].data); count++; p=G.vertexes[i].firstarc; while(p!=NULL){ k=p->adjvex; indegree[k]--; if(indegree[k]==0) EnterQueue(&S,k); p=p->nextarc; } } if(count<G.vexnum) return(Error); //有向图中有回路 else return(Ok); } 时间复杂度如果AOV网络有n个顶点,e条边,在拓扑排序的过程中,搜索入度为零的顶点所需的时间是O(n)。在正常情况下,每个顶点进一次栈,出一次栈,所需时间O(n)。每个顶点入度减1的运算共执行了e次。所以总的时间复杂为O(n+e)。oj题目要求:(入栈)拓扑排序
目标①:了解集合和数组的区别在Java中,集合位于java.util包下。从定义看区别:集合定义:集合是一个不定量存放对象的引用的容器。数组定义:数组是一个定量存放“相同类型”变量的容器。那么从定义的角度上看,数组和集合的区别:数组和集合都是Java中的容器数组的长度是固定的,集合的长度是可变的(数组是静态的,一个数组实例具有固定的大小,一旦创建了就无法改变容量了。而集合是可以动态扩展容量,可以根据需要动态改变大小,集合提供更多的成员方法,能满足更多的需求)数组只能存储相同数据类型的数据,这里的数据类型可以是基本数据类型,也可以是引用类型集合可以存储不同数据类型的对象的引用(但一般情况下,我们会使用泛型来约定只使用1种数据类型),但不能存储基本数据类型从存储结构看联系集合存储:(集合以接口和类的形式存在,不同的实现有着不同的存储结构)看下图注:粉色代表接口,绿色代表实现类;数组、哈希表:顺序存储哈希表、红黑树:链式存储数组存储:链式存储那么,数组是java语言中内置的数据类型,是线性排列的,执行效率或者类型检查都是最快的。集合以接口和类的形式存在,具有封装,继承和多态等类的特性,通过简单的方法和属性调用即可实现各种复杂的操作,大大提高软件的开发效率。目标②:认识集合(自上而下)Map和Collection 接口左右两个集合:Collection、Map 都是接口(不能构建实例对象) 各自都有自己的实现类,以迭代器Iterator将其联系起来经常使用的方法:构建方法:Collection/Map 对象 = new 实现类;注意:Map 没有继承 Collection 接口, Map 提供 key 到 value 的映射,你可以通过“key”查找“value”。一个 Map 中不能包含相同的 key ,每个 key 只能映射一个 valueps:Map集合必须保证保证key唯一,作为key,必须重写hashCode方法和equals方法,以保证key唯一。List和Set 接口以及它的实现类注:绿色为实现类(内包含Collection的基本方法)。据结构为数组的特点:查询快、增删慢。结构为数组链表特点:查询慢、增删快。List 接口:它利用索引(index),定义了一些特殊方法:get(int index,E e) 获取指定位置的元素;remove(int index)移除指定位置的元素;add(int index,E e) 将元素添加到指定位置;set(int index,E e) 用元素替换指定位置的元素;Set接口:特点:元素不可重复;元素无序,存储及取出时顺序不一致;没有索引,因此不能使用普通For循环遍历;Set与Collection 接口中的方法基本一致,没有进行功能上的扩充;Map接口以及实现方法特点:元素包含两个值(key,value)即键值对, key不允许重复,value可以重复, key与value是一一对应的。元素无序;Map接口是双列集合的最顶层接口,定义了一些通用的方法。put(key , value) 添加元素; remove(key) 删除key对应元素;containsKey(key) 判断是否存在key对应元素;get(key) 获取key对应元素;KeySet() 获取所有的key,存到Set集合中;entrySet() 获取所有的元素,存到Set集合中;ps:Map集合必须保证保证key唯一,作为key,必须重写hashCode方法和equals方法,以保证key唯一。使用集合进行操作(此内容来自csdn:java集合基础习题代码部分改动)一.生成10个1到20之间的不重复的随机数分析过程:需要生成随机数,那么需要Random类需要存储10个不能重复的数,需要HashSet集合(当前TreeSet还没学习到)判断,当HashSet的Size小于10就往里存储随机数,等于就停止添加存储元素通过Random的nextInt()方法获取随机数并加入到HashSet里遍历HashSet,打印出10个随机数 package hashset; import java.util.HashSet; import java.util.Random; public class Test1_HashSet { public static void main(String[] args) { //1.创建Random对象 Random r = new Random(); //2.创建HashSet对象 HashSet<Integer> hs = new HashSet<>(); //注意是包装类不是int //3.判断并添加元素 while(hs.size()< 10) { //4.通过Random中随机方法nextInt()获取1到20范围内随机数 hs.add(r.nextInt(20) + 1); //如果不加1,随机范围是0到19 } //5.遍历HashSet for (Integer integer : hs) { System.out.println(integer); } } 二、从键盘获取一行输入字符串,要求去除重复字符。分析过程:需要使用Scanner类输入的是一行字符串,需要转换成字符数组创建HashSet集合对象(利用HashSet无法储存相同元素的特性达到去除重复字符的目的)字符数组遍历元素,并添加进入HashSet集合变量集合元素package hashset; import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; import javax.swing.plaf.synth.SynthSpinnerUI; public class Test2_HashSet { public static void main(String[] args) { //1.创建键盘输入对象 Scanner sc = new Scanner(System.in); System.out.println("请输入一行字符串:"); String line = sc.nextLine(); //2.字符串转换成字符数组 char[] c = line.toCharArray(); //3.字符数组转换成集合对象,创建HashSet HashSet<Character> hs = new HashSet<>(); //4.遍历数组,元素依次添加进集合 for (int i = 0; i < c.length; i++) { hs.add(c[i]); } //5.遍历HashSet集合 for (Character character : hs) { System.out.println(character); } } }三、假设顺序列表ArrayList中存储的元素是整型数字1~5,遍历每个元素,将每个元素顺序输出。(list集合遍历方法总结) import java.util.ArrayList; import java.util.Iterator; import java.util.List; //假设顺序列表ArrayList中存储的元素是整型数字1~5,遍历每个元素,将每个元素顺序输出。 [必做题] public class MyArray { public static void main(String[] args) { List<Integer> list = new ArrayList<Integer>(); list.add(1); list.add(2); list.add(3); list.add(4); list.add(5); Iterator<Integer> it = list.iterator(); // 迭代器遍历 while(it.hasNext()){ System.out.println(it.next()); } // for循环遍历 for(int i = 0;i<list.size();i++){ System.out.println(list.get(i)); } // 增强for循环 for(Integer i :list){ System.out.println(i); } } 四、在一个列表中存储以下元素:apple,grape,banana,pear• 3.1 返回集合中的最大的和最小的元素• 3.2 将集合进行排序,并将排序后的结果打印在控制台上package txtt; import java.util.*; //3、在一个列表中存储以下元素:apple,grape,banana,pear //• 3.1 返回集合中的最大的和最小的元素 //• 3.2 将集合进行排序,并将排序后的结果打印在控制台上 public class test4 { public static void main(String[] args) { HashSet<String> set = new HashSet<>(); set.add("apple"); set.add("grape"); set.add("banana"); set.add("pear"); String max = Collections.max(set); System.out.println(max); String min = Collections.min(set); System.out.println(min); for(Object o:set) { System.out.print(o+" "); } } } 五、编写程序,获取命令行参数中的字符串列表,输出其中重复的字符、不重复的字符以及消除重复以后的字符列表。ublic static void main(String[] args) { String str = "abcdeafblmbnopawc"; System.out.println("原字符串:"+str); Set<Character> set1 = new HashSet<Character>();//消除重复后的字符 Set<Character> set2 = new HashSet<Character>();//重复的字符 Set<Character> set3 = new HashSet<Character>();//不重复的字符 //把字符串转为字符数组 char[] cs = str.toCharArray(); for (char c : cs) { boolean b = set1.add(c); if(!b){ set2.add(c); } } //把消除重复后的字符赋给set3 set3.addAll(set1); //把消除重复后的字符 - 重复的字符 = 不重复的字符 set3.removeAll(set2); System.out.println("====消除重复后的字符========"); for (char c : set1) { System.out.print(c+" "); } System.out.println("\n====重复的字符========"); for (char c : set2) { System.out.print(c+" "); } System.out.println("\n====不重复的字符========"); for (char c : set3) { System.out.print(c+" "); } }六、使用Scanner从控制台读取一个字符串,统计字符串中每个字符出现的次数,要求使用学习过的知识完成以上要求实现思路根据Set、List、Map集合的特性完成。 public static void main(String[] args) { String str = "abcdeblmbac"; System.out.println("原字符串:"+str); Map<Character,Integer> map = new HashMap<Character,Integer>(); char[] cs = str.toCharArray(); for (char c : cs) { if(map.containsKey(c)){ Integer value = map.get(c); value++; map.put(c, value); }else{ map.put(c, 1); } } //遍历map Set<Character> set = map.keySet(); for (Character c : set) { System.out.println(c+"出现了"+map.get(c)+"次"); } }七、 写一个Student类, 包含属性id[1-30), grade[1-6], score[0-100], 所有属性都是随机生成// 创建一个Set集合, 保存20个对象, 如果两个对象的id是一样的,则不允许添加.// 使用迭代器遍历集合,打印输出对象的信息, 并找出分数最高的同学和分数最低的同学, 最后打印输出最高分和最低分同学信息.package txtt; import java.util.*; public class Test13 { public static void main(String[] args) { Set<Student> set = new TreeSet<Student>(); for (; set.size() != 20;) { int id = (int) (Math.random() * 29 + 1); int grade = (int) (Math.random() * 6 + 1); double score = (int) (Math.random() * 1001) / 10.0; set.add(new Student(id, grade, score)); } for (Student student : set) { System.out.println(student); } System.out.println("---------------------------"); Object[] array = set.toArray(); System.out.println("max:"+array[0]); System.out.println("min:"+array[array.length-1]); } } class Student implements Comparable<Student> { private int id; private int grade; private double score; public Student() { } public Student(int id, int grade, double score) { super(); this.id = id; this.grade = grade; this.score = score; } public int getId() { return id; } public void setId(int id) { this.id = id; } public int getGrade() { return grade; } public void setGrade(int grade) { this.grade = grade; } public double getScore() { return score; } public void setScore(double score) { this.score = score; } @Override public String toString() { return "Student [id=" + id + ", grade=" + grade + ", score=" + score + "]"; } public int compareTo(Student o) { return (int) (this.score - o.score); } } 附:选择部分图来自网络,习题来自https://blog.csdn.net/Andrelia20171760/article/details/85268422
共享栈共享栈:两个栈共享同一片存储空间,这片存储空间不单独属于任何一个栈,某个栈需要的多一点,它就可能得到更多的存储空间;两个栈的栈底在这片存储空间的两端,当元素入栈时,两个栈的栈顶指针相向而行。基本概念栈是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的,对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时,称之为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。栈是一种特殊的线性表,是一种只允许在表的一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。栈顶的当前位置是动态的,对栈顶当前位置的标记称为栈顶指针。当栈中没有数据元素时,称之为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。共享栈示意图第一个栈从数组头开始存储,第二个栈从数组尾开始,两个栈向中间拓展。当top1+1 == top2或者top1 == top2-1时,即staock overflow!.与普通栈一样,共享栈出栈入栈的时间复杂度仍为O(1).实验报告当一个应用程序中需要使用多少个栈时,为了提高空间的使用效率,要让多个栈共享空间,这样既能减少预分配的空间过多造成的浪费,又能降低发生栈上溢产生错误中断的可能性,如上图所示,仅当两个栈相遇才会发生上溢一、问题描述(标题黑体小四)实现共享栈二、实验目的实现共享栈三、实验设计1.逻辑结构逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。它与数据的存储无关,是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构,线性表是典型的线性结构;集合、树和图是典型的非线性结构。数据的逻辑结构分类见图1-1。集合结构中的数据元素之间除了 “同属于一个集合”的关系外,别无其他关系。线性结构结构中的数据元素之间只存在一对一的关系。树形结构结构中的数据元素之间存在一对多的关系。图状结构或网状结构结构中的数据元素之间存在多对多的关系。栈是特殊的线性表,它的逻辑结构和线性表相同,只是起操作规则受到了限制,因此,又称它是操作受限的线性表。共享栈也是栈,故逻辑结构为线性结构。2.存储结构存储结构是指数据结构在计算机中的表示(又称映像),也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。数据的存储结构主要有:顺序存储、链式存储、索引存储和散列存储。顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里,元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取,每个元素占用最少的存储空间;缺点是只能使用相邻的一整块存储单元,因此可能产生较多的外部碎片。链接存储:不要求逻辑上相邻的元素在物理位置上也相邻,借助指示元素存储地址的指针表示元素之间的逻辑关系。其优点是不会出现碎片现象,充分利用所有存储单元;缺点是每个元素因存储指针而占用额外的存储空间,并且只能实现顺序存取。索引存储:在存储元素信息的同时,还建立附加的索引表。索引表中的每一项称为索引项,索引项的一般形式是:(关键字,地址)。其优点是检索速度快;缺点是增加了附加的索引表,会占用较多的存储空间。另外,在增加和删除数据时要修改索引表,因而会花费较多的时间。散列存储:根据元素的关键字直接计算出该元素的存储地址,又称为Hash存储。其优点是检索、增加和删除结点的操作都很快;缺点是如果散列函数不好可能出现元素存储单元的冲突,而解决冲突会增加时间和空间开销。可以采用顺序表,也可以采用链式表。本次实验用顺序表实现。故本次为顺序存储。/—变量的定义—/typedef int Selemtype; #define Maxsize 100 //定义共享栈中元素的最大个数 #define TURE 1; #define FALSE 0;/—栈的顺序存储结构—/typedef struct { Selemtype data[Maxsize]; //栈的大小 int top1; //第一个栈的栈顶 int top2; //第二个栈的栈顶 }ShareStack;3.算法设计思想两个栈共享一个存储空间,top1栈在指向空间的左端,依次向右入栈同时top1++,top2栈在指定空间的右端,依次向左入栈同时top2–,栈满,既S1入栈:指针右移一个位置,即stack[++top[0]]=x;S2入栈:指针左移一个位置,即stack[–top[0]]=x;当top1-1 = top2时 栈满4.输入、输出设计输入:入栈(数字+栈序)结束入栈操作(F)输出:出栈(栈内存储变量值)四、主要代码/—初始化—/int InitStack(ShareStack *s) { s->top1 = 0; s->top2 = Maxsize-1; return TURE; } /—判断共享栈是否为空—/int IsEmpty(ShareStack *s) { if(s->top1==0 && s->top2==Maxsize-1) { return TURE; } return FALSE; } /—入栈操作—/int pushSStack(ShareStack *s,Selemtype x,int stackNum) { if(s->top1 == s->top2+1) { return FALSE; } switch(stackNum) { case 1:s->data[s->top1++] = x;break; case 2:s->data[s->top2--] = x;break; } return TURE; } /—出栈操作—/int PopSStack(ShareStack *s,Selemtype *x,int stackNum) { switch(stackNum) { case 1: { if(s->top1 == 0) return FALSE; *x = s->data[--s->top1]; };break; case 2: { if(s->top2==Maxsize-1) return FALSE; *x = s->data[++s->top2]; };break; } return TURE; } 五、程序运行结果截图六、遇到的问题和解决方法问题:栈空输出临界重复输出数值解决方法:利用if语句进行先判断后打印操作完整代码点击查看代码#include <stdio.h> #include <stdlib.h> #include "SStack.h" //自定义头文件 内部有共享栈的定义初始化 出入栈 判断栈空等函数 int main(){ ShareStack *s; s = (ShareStack *)malloc(sizeof(ShareStack)); InitStack(s); int n; int SStackNum; char c; /*---判断栈空---*/ if(IsEmpty(s)) printf("栈空\n"); else printf("栈不空\n"); printf("入栈\n"); while(!(c = getchar() == 'F') ) { printf("输入入栈数字和栈序(末尾加F:退出):"); scanf("%d %d",&n,&SStackNum); pushSStack(s,n,SStackNum); } printf("出栈\n"); while(!(c = getchar() == 'F') ) { printf("输入出栈序(末尾加F:退出):"); scanf("%d",&SStackNum); if(PopSStack(s,&n,SStackNum)) printf("%d\n",n); else break; } /*---判断栈空---*/ if(IsEmpty(s)) printf("栈空"); else printf("栈不空"); }
2023年05月