大數(shù)據(jù)結構線性表應用

1、實驗一線性表應用一.實驗目的1、掌握用Turbo C或VC+吐機調試線性表的基本方法；2、 掌握線性表的基本操作，如插入、刪除、查找，以及線性表合并等運算在順序存儲結構和 鏈式存儲結構上的運算；并能夠運用線性表基本操作解決問題，實現(xiàn)相應算法。二.實驗學時：課實驗學時：2學時課外實驗學時：4學時三備選實驗題目1. 單鏈表基本操作練習（實驗類型：驗證型）1）問題描述：在主程序中設計一個簡單的菜單，分別調用相應的函數(shù)功能:1 建立鏈表2 連接鏈表3 輸出鏈表0結束2）實驗要求：在程序中定義下述函數(shù)，并實現(xiàn)所要求的函數(shù)功能:CreateLinklist():從鍵盤輸入數(shù)據(jù)，創(chuàng)建一個單鏈表ContLin

2、klist():將前面建立的兩個單鏈表首尾相連OutputLi nklist():輸出顯示單鏈表3）實驗提示：單鏈表數(shù)據(jù)類型定義（C語言）# in elude <stdio.h>typedef int ElemType; / 元素類型typedef struct LNode ElemType data;struct LNode *n ext;LNode,*Li nkList;為了算法實現(xiàn)簡單，最好采用帶頭結點的單向鏈表。4）注意問題重點理解鏈式存儲的特點及指針的含義。 注意比較順序存儲與鏈式存儲的各自特點。注意比較帶頭結點、無頭結點鏈表實現(xiàn)插入、刪除算法時的區(qū)別。 單鏈表的操作是數(shù)

3、據(jù)結構的基礎，一定要注意對這部分的常見算法的理解。2. 順序表基本操作練習（實驗類型：驗證型）1）問題描述：從鍵盤輸入一組整型元素序列，建立順序表。實現(xiàn)該順序表的遍歷。在該順序表中進行順序查找某一元素，查找成功返回1,否則返回0。判斷該順序表中元素是否對稱，對稱返回1,否則返回0。2）實驗要求：對應問題描述，在程序中定義4個相應的函數(shù)，實現(xiàn)上面要求的函數(shù)功能：在主程序中設計一個簡單的菜單，調用上述4個函數(shù)3）實驗提示：順序表存儲數(shù)據(jù)類型定義（C語言）# define MAXSIZE 100 /表中元素的最大個數(shù)typedef int ElemType; / 元素類型typedef struct

4、 listElemType elemMAXSIZE; /靜態(tài)線性表in t le ngth; II表的實際長度SqList; II順序表的類型名4）注意問題：插入、刪除時元素的移動原因、方向及先后順序。理解不同的函數(shù)形參與實參的傳遞關系。3. 約瑟夫環(huán)問題（實驗類型：綜合型）1） 問題描述：有編號為1,2n的n個人按順時針方向圍坐一圈，每人持有一個正整數(shù)密碼。開始給定一個正整數(shù) m,從第一個人按順時針方向自 1開始報數(shù)，報到 m者出列，不再參加報 數(shù)，這時將出列者的密碼作為 m,從出列者順時針方向的下一人開始重新自1開始報數(shù)。如此下去,直到所有人都出列。試設計算法，輸出出列者的序列。2）實驗要

5、求：采用順序和鏈式兩種存儲結構實現(xiàn)3）實現(xiàn)提示：用順序表來存儲圍座者的序號和密碼（順序存儲結構）.用number和code分別表示圍座者的序號和密碼 .假設圍座者人數(shù)為j,當前使 用密碼為m,開始報數(shù)者位置為 s,那么下一出列者位置為 s=（s+m-1） mod j.當我們要在線性表的順序存儲結構上的第i個位置上插入一個元素時，必須先將線性表的第i個元素之后的所有元素依次后移一個位置，以便騰空一個位置，再把新元素插入到 該位置。若要刪除第i個元素時，也必須把第i個元素之后的所有元素前移一個位置。用鏈式存儲解決此問題時可以采用循環(huán)鏈表4）注意問題：順序存儲和鏈式存儲實現(xiàn)此算法時計算出列位置的不同

6、方法，人員出列后所做操作的區(qū)別。4. 一元稀疏多項式簡單的計算器（實驗類型：綜合型）1）問題描述：用線性表表示一元稀疏多項式，設計一個一元多項式運算器2）實驗要求：采用單鏈表存儲結構一元稀疏多項式輸入并建立多項式輸出多項式實現(xiàn)多項式加、減運算3）實現(xiàn)提示：以兩個多項式相加為例結果多項式另存掃描兩個相加多項式，若都未檢測完：若當前被檢測項指數(shù)相等，系數(shù)相加，若結果未變成0,則將結果插入到結果多項式。若當前被檢測項指數(shù)不等，則將指數(shù)較小者插入到結果多項式。若有一個多項式已檢測完，則將另一個多項式剩余部分直接連接到結果多項式。5. 長整數(shù)（任意長度）四則運算演示程序（實驗類型：綜合型）1）問題描述：

7、設計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序2）實驗要求：利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，給各結點含一個整型變量。任何整型變量的的圍是-（215-1 ） （215-1 ）。輸入和輸出形式：按照中國對長整數(shù)的表示習慣，每四位一組，組間用逗號隔開。3）實現(xiàn)提示：每個結點中可以存放的最大整數(shù)為215-1=32767,才能保證兩數(shù)相加不會溢出。但若這樣存，即相當于按 32768進制數(shù)存，在十進制數(shù)與 32768進制數(shù)之間的轉換十分不方便。故可以在 每個結點中僅存十進制數(shù)的4位，即不超過9999的非負整數(shù)，整個鏈表視為萬進制數(shù)?？梢岳妙^結點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結點的樹木

8、。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結構的一種方法。4）注意問題：不能給常整數(shù)位數(shù)規(guī)定上限。程序設計源代碼如下:第一題：#in elude <stdio.h>#in elude <stdlib.h>#in elude<iostream.h>typedef int ElemType;Illi元素類型typedef struct LNodeElemType data;struct LNode *n ext;LNode;typedef LNode *Lin kList;Lin kList head;Lin kList L;

9、Illi定義單鏈表頭指針 LLin kList L1;Lin kList L2;Lin kList L12;尾插入法建立單鏈表Lin kList Creatlist_L()llliiliLin kList L,p,r;int x;r=L=(L in kList)malloc(sizeof(LNode);L-> next=NULL;cin> >x;while(x!=O)p=(L in kList)malloc(sizeof(LNode);p_>data=x;p-> next=NULL;r->n ext=p;r=p;cin> >x;return L;

10、LinkList Show_L(LinkList L)Lin kList p2;p2=L;while(p2-> next!=NULL)cout<<p2->n ext->data<<"" p2=p2->n ext;return L;Lin kList Con tlist_L(Li nkList A,Li nkList B)Li nkList C,a,b,e,f;a=A->n ext;b=B->n ext;C=A;/C表的頭節(jié)點f=C=(Li nkList)malloc(sizeof(LNode);C-> nex

11、t=NULL;/建立空鏈表while(a)e=(L in kList)malloc(sizeof(LNode); e->data=a->data;e-> next=NULL;f->n ext=e;f=e;a=a->n ext;while(b)e=(L in kList)malloc(sizeof(LNode); e->data=b->data;e-> next=NULL;f->n ext=e;f=e;b=b->n ext;return C; void mai n()int choice;for(;)cout<<"

12、+ 進入菜單 +："<<e ndl; cout<<"1.建立單鏈表:"<<endl;cout<<"2.連接單鏈表:"<<endl;cout<<"3.輸出單鏈表:"<<endl;cout<<"0.程序結束:"<<endl;cout<<e ndl;cout<<"請選擇操作序號:"<<endl;cin> >choice;if(choice

13、=0)cout<<"成績結束，任意鍵退出！"<<endl;break;switch(choice)case 1:int choice1;cout<<"開始建立單鏈表 1:"<<endl;L仁 Creatlist_L();cout<<e ndl;cout<<"表 1 建立完畢!"<<endl;"<<e ndl;cout<<"是否繼續(xù)建立單鏈表2 ? "<<"n 1. 繼續(xù) 2.

14、返回cin> >choice1;if(choice1=1)cout<<"開始建立單鏈表 2"<<endl;L2=Creatlist_L();cout<<e ndl;cout<<"表 2 建立完畢!"<<endl;cout<<e ndl;cout<<"單鏈表建立完畢！!"<<endl;break;case 2:cout<<" 開始連接單鏈表 1, 2!"<<endl;L12=Co ntl

15、ist_L(L1 ,L 2);cout<<"asfsdfsagshdfhgdfhjdfhhdfhasdf'<<e ndl;break;case 3:int choice1;cout<<"請選擇輸出哪個表："<<endl;cout<<"1.表 12. 表 23.聯(lián)立后的表 12 "<<endl;cin> >choice1;switch(choice1)case 1:cout<<"單鏈表 1 為："<<endl;S

16、how_L(L1);cout<<e ndl;break;case 2:cout<<"單鏈表 2 為："<<endl;Show_L(L2);cout<<e ndl;break;case 3:cout<<"聯(lián)立后的表12為:"<<endl;Show_L(L12);cout<<e ndl;break; break;第二題:#in clude <stdio.h>#in clude <stdlib.h>#in clude<iostream.h>#

17、defi ne Maxsize 100/表中元素的最大個數(shù)typedef int ElemType; /typedef struct listElemType dataMaxsize; / in t le ngth;/SqList;/int m=0;元素類型靜態(tài)線性表表的實際長度順序表的類型名SqList *creat_SqList(SqList *L) /L=(SqList *)malloc(sizeof(SqList); cout<<"請輸入線性表數(shù)據(jù):"<<endl;建立線性表，并輸入線性表元素for(m;m+)ElemType x;cin&g

18、t; >x;if(x=O) break;L->datam=x; L->le ngth=m; return L;SqList *all_SqList(SqList *L)cout<<"已建立的線性表為:"<<endl;for(i nt i=0;i<L->le ngth;i+)cout<<L->datai<<""cout<<e ndl;return L;查詢元素函數(shù)"<<j+1<<"位!"<<e n

19、dl;int serch_SqList(SqList *L,i nt y) Illifor(i nt j=O;j<L->le ngth;j+)if(L->dataj=y)cout<<"表中含有此數(shù)據(jù)，位于表中第return 1;break;else if(j=L->le ngth-1)cout<<"表中沒有此數(shù)據(jù)!"<<endl;break;elsecon ti nue;void judje_SqList(SqList *L)Illi判斷是否對稱函數(shù)if(m%2=0)lllll線性表元素個數(shù)為偶數(shù)個cou

20、t<<"中心元素為"<<L->datam/2<<endl;for(i nt k=0;k<=m/2+1;k+)if(k=m/2+1)cout<<"*該線性表對稱!*"<<endl;break;else if(L->datak=L->datam-1-k)con ti nue;elsecout<<" *該線性表不是對稱的!*"<<e ndl;break;else lllllllllllll線性表元素個數(shù)為奇數(shù)個cout<<

21、"中心元素為"<<L->dataml2<<endl;for(i nt t=0;t<=ml2+1;t+)if(t=ml2+1)cout<<"*該線性表對稱!*"<<endl;break;else if(L->datat=L->datam-1-t)con ti nue;elsecout<<" *該線性表不是對稱的!*"<<e ndl;break;int mai n()SqList *L1;int choice;for(;)cout<<

22、;"+ 主菜單 +"<<e ndl;cout<<"1.新建線性表;"<<endl;cout<<"2.遍歷線性表;"<<endl;cout<<"3.查找表中元素;"<<endl;cout<<"4.判斷是否對稱;"<<endl;cout<<"0.退出程序;"<<endl;cout<<e ndl;cout<<"請輸入操

23、作序號："<<endl;cin> >choice;if(choice=0) break;switch(choice)case 1:L1=creat_SqList(L1);cout<<"線性表長度為:"<<m<<endl;break;case 2:cout<<"開始遍歷線性表："<<endl;all_SqList(L1);break;case 3:int y;cout<<"請輸入要查找的元素："<<endl;cin

24、87;y;serch_SqList(L1,y);break;case 4:cout<<"正在檢測是否對稱!"<<endl;judje_SqList(L1);break;return 0;第三題：#in clude <stdio.h>#in clude <stdlib.h>#in clude<iostream.h># define Maxsize 50 /元素最大容量typedef int ElemType; /元素類型typedef struct listElemType num Maxsize;ElemType

25、codeMaxsize; in t le ngth;/表的實際長度順序表的類型名Juserfu L;/定義一個順序表Lint j=0;/圍坐的總人數(shù)Juserfu *creat_Juserfu(Juserfu *L)/L=(Juserfu *)malloc(sizeof(Juserfu);cout<<"請分別輸入每個人的序號和密碼:"<<endl;for(j;j+)建立線性表，并輸入線性表元素ElemType m,s; /定義密碼cin> >s»m;if(m=0) break;L_>nu mj=s;L->codej=

26、m;L->le ngth=j;return L;Juserfu *output_Juserfu(Juserfu *L)/int x_num=O;int x_code;cout<<"請輸入初始密碼："<<endl;cin>> x_code;for(j;j>0;j-)輸出出列者的序列Juserfu;/x_nu m=(x_ nu m+x_code-1)%j;"<<e ndl;cout<<x_num<<"出歹U者為"<<L->numx_num<&

27、lt;"號!x_code=L->codex_ nu m;for(x_ num;x_nu m<j;x_ nu m+)L->numx_num =L->numx_nu m+1;L->codex_ nu m=L->codex_ nu m+1;return L;void mai n()int s;Juserfu *L1;cout<<"請輸入每位圍坐者的密碼!"<<endl;L1=creat_Juserfu(L1);cout<<"共圍坐人數(shù)為："<<L1->lengt

28、h<<endl;cout<<"密碼分別為："<<endl;for(i nt i=0;i<j;i+)cout<<L1->numi<<" "<<L1->codei<<""output_Juserfu(L1);第四題：#in clude <stdio.h>#in clude <stdlib.h> #in clude<iostream.h>typedef struct PolyNode系數(shù)float coe

29、f;/float exp; /指數(shù)PolyNode *n ext;/指針域PolyNode;typedef PolyNode *Po lyn omial;Polynomial A;/定義多項式APolyno mial creat_Poly()Pol yno mial L,p,r;float x_coef;float x_exp;r=L=(Po lyno mial)malloc(sizeof(PolyNode);L-> next=NULL;cout<<"請依次輸入多項式的系數(shù)和指數(shù)(0,0為輸入結束)："<<endl;cin>> x_

30、coef»x_exp;while(x_coef!=0 && x_exp!=0)p=(Po lyno mial)malloc(sizeof(PolyNode);p->coef=x_coef;p->exp=x_exp;p-> next=NULL;r->n ext=p;r=p;cin>> x_coef>>x_exp;return L;Polyno mial show_Poly(Po lyno mial L)Polyno mial p1;p1=L;while(p1-> next!=NULL)cout<<p1-

31、>n ext->coef<<"X"<<p1- >n ext->exp<<" +" p1=p1- >n ext;cout<<e ndl;return L;Poly nomial add_Poly(Poly nomial A,Poly nomial B)Pol yno mial C,D;Poly nomial p1,p2,p3;float sum;p1=A->n ext;p2=B->n ext;C=(Poly nomial)malloc(sizeof(PolyNode)

32、;p3=C;p3-> next=NULL;while(p1 &&p2)if(p1_>exp=p2_>exp)sum=p1->coef+p2->coef;if(sum!=0)D=(Poly nomial)malloc(sizeof(PolyNode);D->coef=sum;D->exp=p1->exp;D-> next=NULL;p3-> next=D;p3=D;p1=p1- >n ext;p2=p2->n ext;else if(p1->exp<p2->exp)D=(Poly nomia

33、l)malloc(sizeof(PolyNode);D->coef=p1->coef;D_>exp=p1_>exp;D-> next=NULL;p3-> next=D;p3=D;p1=p1- >n ext;elseD=(Poly nomial)malloc(sizeof(PolyNode);D->coef=p2->coef;D_>exp=p2_>exp;D-> next=NULL;p3-> next=D;p3=D;p2=p2->n ext;while(p1) / 多項式A沒有處理完D=(Poly nomial)

34、malloc(sizeof(PolyNode);D->coef=p1->coef;D->exp=p1->exp;D-> next=NULL;p3-> next=D;p3=D;p1=p1- >n ext; while(p2) / 多項式B沒有處理完D=(Poly no mial)malloc(sizeof(PolyNode);D->coef=p2->coef;D_>exp=p2_>exp;D-> next=NULL;p3-> next=D;p3=D;p2=p2->n ext;return C;void mai n

35、()Poly no mial A;Polyno mial B;Poly nomial C;cout<<"開始建立多項式 A:"<<endl;A=creat_Poly();cout<<"多項式 A 為:"<<endl;show_Poly(A);cout<<"開始建立多項式 B:"<<endl;B=creat_Poly();cout<<"多項式 B 為:"<<endl;show_Poly(B);C=add_Poly(A,B);cout<<"相加之后得到的多項式C為:"<<endl;show_Poly(C);第五題：#in clude<stdio.h>#in clude<stdlib.h>#in clude<iostream.h> typedef struct Nodeint data;Node* next;Node* front;Node;typedef Node *Operati on;Operatio n creat()Operati on L;Operati on p1,p2;L=(