最小生成樹問題

PAGEPAGE7中北大學數據結構與算法課程設計說明書

學院、系：軟件學院專業軟件工程學生姓名：xx學號：xxx設計題目：最小生成樹問題起迄日期:20年12月9日-20年12月20日指導教師:

20年12月20日需求分析設計內容：給定一個地區的n個城市間的距離網，用prim算法或kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價?；疽螅?（1）城市間的距離網采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價； （2）表示城市間距離網的鄰接矩陣（要求至少6個城市，10條邊）； （3）最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。2本設計所采用的數據結構本程序設計所采用的數據結構為圖。3設計思想普里姆算法4核心代碼intmain()//主函數{mgraphg;vertextypeu;intk;createUDN(&g);/*生成鄰接矩陣結構的圖*/printf("\nThegraphis:\n");print(g);/*輸出鄰接矩陣*/printf("inputthecityyouwanttostart:");scanf("%s",u);/*輸入最小生成樹的起點*/k=locatedvex(g,u);while(k==-1){printf("thenameofthecityiswrong!\n");printf("inputthecityyouwanttostartagain:");scanf("%s",u);k=locatedvex(g,u);}minispantree(g,u);/*普里姆算法求最小生成樹*/}4代碼#include"stdio.h"#include"string.h"#definemaxnum20/*圖的最大頂點數*/#defineINFINITY1000/*定義一個權值的最大值*/typedefcharvertextype[20];/*定義城市名稱*/typedefstructarccell{intadj;/*弧的權值*/int*info;/*弧上相關信息的指針*/}arccell;typedefstructarray{vertextypeadjvex;/*頂點的鄰接點*/intlowcost;/*某頂點與已構造好的部分生成樹的頂點之間的最小權值*/}array;typedefstruct{ vertextypevexs[maxnum];/*頂點向量*/ arccellarcs[maxnum][maxnum];/*鄰接矩陣*/ intvexnum,arcnum;/*圖的頂點個數和弧個數*/ arrayclosedge[maxnum];/*用普里姆算法求最小生成樹時的輔助數組*/}mgraph;voidcreateUDN(mgraph*g){/*用鄰接矩陣構造n個城市間的距離網g*/inti,j,m,n,k,a,b,c;vertextypex,y;printf("inputthenumberofcities(atleast6cities):");scanf("%d",&g->vexnum);/*輸入城市的個數（圖的頂點數）*/printf("inputthenumberofroads(atleast10roads):");scanf("%d",&g->arcnum);/*輸入道路的邊數（圖的邊數）*/printf("inputthenameof%dcities:",g->vexnum);for(i=0;i<g->vexnum;i++)scanf("%s",g->vexs[i]);/*輸入城市名稱（圖的頂點）*/for(m=0;m<g->vexnum;m++){for(n=0;n<g->vexnum;n++)g->arcs[m][n].adj=INFINITY;}/*初始化鄰接矩陣*/for(k=0;k<g->arcnum;k++){printf("inputthedistanceofaroad:");scanf("%s%s%d",x,y,&c);/*輸入城市間的距離（圖中邊的起點和終點及權值）*/a=locatedvex(*g,x);b=locatedvex(*g,y);while(a==-1||b==-1){printf("thenameofthecityiswrong!\n");printf("inputthedistanceofaroadagain:");scanf("%s%s%d",x,y,&c);a=locatedvex(*g,x);b=locatedvex(*g,y);}g->arcs[a][b].adj=c;g->arcs[b][a]=g->arcs[a][b];}} voidprint(mgraphg)/*輸出用鄰接矩陣構造的n個城市間距離網g*/{inti,j;for(i=0;i<g.vexnum;i++){for(j=0;j<g.vexnum;j++) printf("%-4d",g.arcs[i][j].adj);printf("\n");}}voidminispantree(mgraphg,vertextypex){/*從第k個頂點出發構造圖g的最小生成樹*/ inti,j,t,k,sum=0; k=locatedvex(g,x); for(j=0;j<g.vexnum;j++)/*輔助數組初始化*/ if(j!=k){g.closedge[j].lowcost=g.arcs[k][j].adj; strcpy(g.closedge[j].adjvex,x); } g.closedge[k].lowcost=0;/*初始，U={u}*/ for(i=1;i<g.vexnum;i++){/*選擇其余的G->vexnum-1個頂點*/ k=min(g);/*求出生成樹的下一個頂點*/ printf("(%s,%s)%d\n",g.closedge[k].adjvex,g.vexs[k],g.closedge[k].lowcost);/*輸出生成樹的邊和權值*/ sum+=g.closedge[k].lowcost;/*計算最小生成樹的代價*/g.closedge[k].lowcost=0;/*第k頂點并入U集*/for(t=0;t<g.vexnum;t++)/*新頂點并入U后，修改輔助數組*/ if(g.arcs[k][t].adj<g.closedge[t].lowcost){ strcpy(g.closedge[t].adjvex,g.vexs[k]); g.closedge[t].lowcost=g.arcs[k][t].adj; } } printf("Theshortestdistanceis%d\n",sum);/*輸出最小生成樹的代價*/}intmin(mgraphg){/*在輔助數組g.closedge[i]中選擇權值最小的頂點，并返回其位置*/ inti,a=0,min; min=maxnum; for(i=1;i<g.vexnum;i++) if(g.closedge[i].lowcost<min&&g.closedge[i].lowcost!=0){ a=i; min=g.closedge[i].lowcost; }returna; }intlocatedvex(mgraphg,vertextypeu){/*確定任一城市在距離網g中的位置*/ inti; for(i=0;i<g.vexnum;i++)if(strcmp(u,g.vexs[i])==0)returni;return-1;}intmain(){mgraphg;vertextypeu;intk;createUDN(&g);/*生成鄰接矩陣結構的圖*/printf("\nThegraphis:\n");print(g);/*輸出鄰接矩陣*/printf("inputthecityyouwanttostart:");scanf("%s",u);/*輸入最小生成樹的起點*/k=locatedvex(g,u);while(k==-1){printf("thenameofthecityiswrong!\n");printf("inputthecityyouwanttostartagain:");scanf("%s",u);k=locatedvex(g,u);}minispantree(g,u);/*普里姆算法求最小生成樹*/}5程序運行結果8心得體會本次課程設計我們經歷了最短時間最繁重的設計任務，作為兩人組的課程設計任務難度相對來說較大，我和我的合作伙伴盡了最大的努力來做到課程設計的要求，仍然不是很滿意最后的結果。但是，總的來說也讓我們體會到了一些軟件開發的辛苦，有時候你確實需要在有限的時間內來完成任務。最后本次課程任務教給我們很多，讓我們客觀的正視了自己一個學期的學習成果。我們相信自己通過這樣的任務能學到我們平時僅僅上課所學不到的知識，并發現、體會到了一種經過辛苦編程，糾正代碼后所獨有的快樂。也讓我們發現了自己對于編程所潛藏的熱愛。

社會實踐報告系別：班級：學號：姓名：作為祖國未來的事業的繼承人，我們這些大學生應該及早樹立自己的歷史責任感，提高自己的社會適應能力。假期的社會實踐就是很好的鍛煉自己的機會。當下，掙錢早已不是打工的唯一目的，更多的人將其視為參加社會實踐、提高自身能力的機會。許多學校也積極鼓勵大學生多接觸社會、了解社會，一方面可以把學到的理論知識應用到實踐中去，提高各方面的能力；另一方面可以積累工作經驗對日后的就業大有裨益。進行社會實踐，最理想的就是找到與本專業對口單位進行實習，從而提高自己的實戰水平，同時可以將課本知識在實踐中得到運用，從而更好的指導自己今后的學習。但是作為一名尚未畢業的大學生，由于本身具備的專業知識還十分的有限，所以我選擇了打散工作為第一次社會實踐的方式。目的在于熟悉社會。就職業本身而言，并無高低貴賤之分，存在即為合理。通過短短幾天的打工經歷可以讓長期處于校園的我們對社會有一種更直觀的認識。實踐過程：自從走進了大學，就業問題就似乎總是圍繞在我們的身邊，成了說不完的話題。在現今社會，招聘會上的大字報都總寫著“有經驗者優先”，可還在校園里面的我們這班學子社會經驗又會擁有多少呢？為了拓展自身的知識面，擴大與社會的接觸面，增加個人在社會競爭中的經驗，鍛煉和提高自己的能力，以便在以后畢業后能真正真正走入社會，能夠適應國內外的經濟形勢的變化，并且能夠在生活和工作中很好地處理各方面的問題，我開始了我這個假期的社會實踐-走進天源休閑餐廳。實踐，就是把我們在學校所學的理論知識，運用到客觀實際中去，使自己所學的理論知識有用武之地。只學不實踐，那么所學的就等于零。理論應該與實踐相結合。另一方面，實踐可為以后找工作打基礎。通過這段時間的實習，學到一些在學校里學不到的東西。因為環境的不同，接觸的人與事不同，從中所學的東西自然就不一樣了。要學會從實踐中學習，從學習中實踐。而且在中國的經濟飛速發展，又加入了世貿，國內外經濟日趨變化，每天都不斷有新的東西涌現，在擁有了越來越多的機會的同時，也有了更多的挑戰，前天才剛學到的知識可能在今天就已經被淘汰掉了，中國的經濟越和外面接軌，對于人才的要求就會越來越高，我們不只要學好學校里所學到的知識，還要不斷從生活中，實踐中學其他知識，不斷地從各方面武裝自已，才能在競爭中突出自已，表現自已。在餐廳里,別人一眼就能把我人出是一名正在讀書的學生,我問他們為什么,他們總說從我的臉上就能看出來,也許沒有經歷過社會的人都有我這種不知名遭遇吧!我并沒有因為我在他們面前沒有經驗而退后,我相信我也能做的像他們一樣好.我的工作是在那做傳菜生,每天9點鐘-下午2點再從下午的4點-晚上8:30分上班,雖然時間長了點但,熱情而年輕的我并沒有絲毫的感到過累,我覺得這是一種激勵,明白了人生,感悟了生活,接觸了社會,了解了未來.在餐廳里雖然我是以傳菜為主,但我不時還要做一些工作以外的事情，有時要做一些清潔的工作，在學校里也許有老師分配說今天做些什么，明天做些什么，但在這里，不一定有人會告訴你這些，你必須自覺地去做，而且要盡自已的努力做到最好，一件工作的效率就會得到別人不同的評價。在學校，只有學習的氛圍，畢竟學校是學習的場所，每一個學生都在為取得更高的成績而努力。而這里是工作的場所，每個人都會為了獲得更多的報酬而努力，無論是學習還是工作，都存在著競爭，在競爭中就要不斷學習別人先進的地方，也要不斷學習別人怎樣做人，以提高自已的能力！記得老師曾經說過大學是一個小社會，但我總覺得校園里總少不了那份純真，那份真誠，盡管是大學高校，學生還終歸保持著學生的身份。而走進企業，接觸各種各樣的客戶、同事、上司等等，關系復雜，但我得去面對我從未面對過的一切。記得在我校舉行的招聘會上所反映出來的其中一個問題是，學生的實際操作能力與在校理論學習有一定的差距。在這次實踐中，這一點我感受很深。在學校，理論的學習很多，而且是多方面的，幾乎是面面俱到；而在實際工作中，可能會遇到書本上沒學到的，又可能是書本上的知識一點都用不上的情況?；蛟S工作中運用到的只是很簡單的問題，只要套公式似的就能完成一項任務。有時候我會埋怨，實際操作這么簡單，但為什么書本上的知識讓人學得這么吃力呢？這是社會與學校脫軌了嗎？也許老師是正確的，雖然大學生生活不像踏入社會，但是總算是社會的一個部分，這是不可否認的事實。但是有時也要感謝老師孜孜不倦地教導，有些問題有了有課堂上地認真消化，有平時作業作補充，我比一部人具有更高的起點，有了更多的知識層面去應付各種工作上的問題，作為一名大學生，應該懂得與社會上各方面的人交往，處理社會上所發生的各方面的事情，這就意味著大學生要注意到社會實踐，社會實踐必不可少。畢竟，很快我就不再是一名大學生，而是社會中的一分子，要與社會交流，為社會做貢獻。只懂得紙上談兵是遠遠不及的，以后的人生旅途是漫長的，為了鍛煉自己成為一名合格的、對社會有用的人才.很多在學校讀書的人都說寧愿出去工作，不愿在校讀書；而已在社會的人都寧愿回校讀書。我們上學，學習先進的科學知識，為的都是將來走進社會，獻出自己的一份力量，我們應該在今天努力掌握專業知識，明天才能更好地為社會服務。實踐心得：雖然這次的實踐只有短短的幾天，而且從事的是比較簡單的服務工作，但是通過與各種各樣的人接觸，還是讓我學會了很多道理。首先是明白了守時的重要性。工作和上學是兩種完全不同的概念，上學是不遲到很多時候是因為懼怕老師的責怪，而當你走上了工作崗位，這里更多的是由于自己內心的一種責任。這種責任是我學會客服自己的惰性，準時走上自己的崗位。這對我以后的學習生活也是一種鞭策，時刻牢記自己的責任，并努力加強自己的時間觀念。其次讓我真實的體會到了合作的重要性。雖然我工作的只是小小的一家餐廳，但是從點單到制作到遞送到結帳這一環環的工作都是有分工的，只有這樣才能使整家店的工作效率都大大的提高。以前雖然在書上看見過很多的團隊合作的例子，但這一次是深刻的體會到了，正所謂“眾人拾柴火焰高”，“團結就是力量”。在以后的學習和工作中，一定會要牢記這一點，將自己融入到集體中，和大家一起攜手走向輝煌。再次，這次打工的經歷也讓我的心理更加趨于成熟。在餐廳里每天面對形形色色的客人，重復著單調的工作。讓從未涉世的我還是有那么一點點不適應的，但是堅持就是勝利。打工畢竟和在家是完全不同的概念，我們學會需要忍耐，需要學會承受，需要學會堅持。將自己這短短的一月的實踐同理論相聯系，我了解到當代大學生與以往的大學生相比較，求學經歷、生活條件、所處社會大環境都相對優越，也沒有經過必要的挫折教育，因此，意志往往比較脆弱，克服困難的能力也較差，常常是對社會的要求較高，對自我的要求較低。大學生的責任意識日益成為社會關注的熱點問題，責任意識和誠信意識成為不少地方采用人才的兩個新標準。大學生參與社會實踐是促進大學生素質教育,加強和改進青年學生思想政治工作，引導學生健康成長和成才的重要舉措，是學生接觸社會、了解社會、服務社會，培養創新精神、實踐能力和動手操作能力的重要途徑。對于當代大學生來說，應當刻苦學習專業知識，不斷提高綜合素質和運用知識的技能。從大學生活的開始到走進社會的大圈子中，就只有短短的幾年時間，誰不想在將來的社會中能有一席之地呢？所以大家認為大學生必須投身校園內外的各類實踐活動，有助于鍛煉品質，提高能力?？梢娖鋵Υ髮W生綜合素質的提高有不可抵觸的重要性。不能否認有過打工經歷的同學，看起來要比其它同學更成熟、社會適應力更強，但對于學生，社會適應力只是一方面的衡量指標，大學期間主要的任務是學業結構的搭建，即知識結構、專業結構的搭建，為了打工影響甚至放棄了專業知識的學習，結果是得不償失的。實踐出真知，社會實踐活動是大學生活的重要組成部份，培養當代大學生的歷史使命感、社會責任感和積極向上的精神風貌，充分發揮實踐育人的作用，提高大學生的綜合素質，也是檢驗所學理論知識的標準，社會實踐不但為大學生提供了一個發揮自我才能，展現自我風采的舞臺，也是培養和鍛煉同學們綜合能力的一個階梯，更是一個大學生進入社會，走上工作崗位前的演練場地。社會實踐活動，從而確定比較正確的人生前進方向。河南理工大學計算機科學與技術學院實習報告20—20學年第學期實習名稱生產實習實習地點實習日期學生姓名學號專業班級指導教師20**年**月**日一、實習基本情況20**年**月通過網絡招聘，我應聘到河南中方紡業有限公司進行實習，該公司位于周口市，主要承擔棉紡制造與銷售工作，進入公司后我被分配到信息管理部門，主要從事的工作是對公司的網絡進行管理與維護，同時對公司網站的管理與維護進行學習，三個月的實習讓學會了從不同的角度去看待問題和解決問題，對網絡工程師的工作有了全面的認識，為以后的就業積累了經驗。二、實習內容1.單位情況河南中方實業（集團）有限公司是以棉花種植、收購、加工、經營、倉儲、紡織及棉花與紡織品進出口為產業鏈條，集研發、生產、經營、投資、管理于一體的現代產業化集團企業。旗下擁有多家從事棉花、紡織等生產、經營的全資、控股子公司。經過多年的發展，公司已形成了以“棉花經營、棉花物流、棉紡織、紡織品出口”為主干業務，以“國內、國際”為兩大市場的經營格局。棉花經營涵蓋進口棉、新疆棉、地產棉三大系列多個品種；棉花物流業務以地產棉交易為主，填補了河南無地產棉交易市場的空白，并融入了全國棉花物流體系；棉紗產品從精梳40s到精梳120s、氣流紡紗16s到21s等兩大系列；外貿出口涵蓋棉紗、面料、服裝等三大系列、400多個品種。公司營銷網絡覆蓋國內眾多棉花生產、經營、紡織企業，大型專業公司及國際棉花、紡織工貿公司，并與之建立了長期穩固的互助合作關系，業務范圍遍及河南、河北、湖北、新疆、甘肅、浙江、江蘇、山東、廣東、福建、香港、新加坡、印度、澳大利亞、美國等區域。2.技術培訓初到公司后，公司進行了一系列的公司工作相關培訓，如企業文化、企業制度等，我所在的信息管理部門也進行了一些技術培訓，主要內容有辦公軟件的使用、公司網絡的日常維護工作等，這些培訓讓我對網絡專業有了更進一步的了解，對網絡工程師應該干什么有了一個整體的了解。3.工作內容在實習期間我先后主動了解了公司職能范圍、機構設置、人員編制等基本情況，并對人事教育、網絡管理重點以及現場維護等工作深入學習，先后研讀了TCP/IP協議詳解一、二卷等書籍，同時我還理論聯系實際，實習期間主動要求跟老工程師到現場去實踐鍛煉、了解學習，努力從多方面開拓自己的眼界。我的主要工作是，在日常工作中通過對老員工的學習，不斷的增加自己的實踐知識儲備，積極參加部門的技能培訓，及時總結學習內容，同時對公司需要的文件進行修改、打印以及分發到各個部門。在實習期間，我遇到了很多問題如對設備不熟悉、所學知識不能學以致用等問題，通過自己的溝通協調和監督管理，這些問題都得以解決。三、實習感想從學生到實習工程師，短短幾個月的工作過程使我受益匪淺。不僅是在專業知識方面，最主要是在為人處事方面。社會在加速度地發生變化，對人才的要求也越來越高，要用發展的眼光看問題，得不斷提高思想認識，完善自己。作為一名it從業者，所受的社會壓力將比其他行業更加沉重，要學會創新求變，以適應社會的需要。在單位里，小到計算機的組裝維修，大到服務器的維護與測試，都需要一個人獨立完成?？梢哉f，近幾個月的工作使我成長了不少，從中有不少感悟，下面就是我的一點心得：

第一是要真誠：你可以偽裝你的面孔你的心，但絕不可以忽略真誠的力量。第一天去網絡中心實習，心里不可避免的有些疑惑：不知道老師怎么樣，應該去怎么做啊，要去干些什么呢等等吧！踏進辦公室，只見幾個陌生的臉孔。我微笑著和他們打招呼。從那天起，我養成了一個習慣，每天早上見到他們都要微笑的說聲：“您早啊”，那是我心底真誠的問候。我總覺得，經常有一些細微的東西容易被我們忽略，比如輕輕的一聲問候，但它卻表達了對同事對朋友的尊重關心，也讓他人感覺到被重視與被關心。僅僅幾天的時間，我就和領導同事們打成一片，很好的跟他們交流溝通學習，我想，應該是我的真誠，換得了領導和同事的信任。他們把我當朋友也愿意指導我，愿意分配給我任務。

第二是溝通：要想在短暫的實習時間內，盡可能多的學一些東西，這就需要跟領導和同事有很好的溝通，加深彼此的了解，剛到網絡中心，老師并不了解你的工