字符串、稀疏矩陣實驗(實驗四).doc

實驗 四 字符串、稀疏矩陣實驗一 實驗目的及要求（1） 熟悉字符串類型的實現(xiàn)方法，并完成串的一些基本操作；（2） 掌握稀疏矩陣的三元組順序表存儲表示，并實現(xiàn)矩陣的轉(zhuǎn)置運算。二.實驗內(nèi)容：（1） 編程實現(xiàn)兩個串S1和S2的比較。（要求自己設(shè)計串的存儲結(jié)構(gòu)，并編寫比較函數(shù)，不要調(diào)用系統(tǒng)提供的函數(shù)）（2） 編程實現(xiàn)稀疏矩陣的三元組順序表示方法及基本操作的實現(xiàn)（建立、輸出、轉(zhuǎn)置等）。（3）編程實現(xiàn)稀疏矩陣的十字鏈表存儲表示及基本操作的實現(xiàn)（建立、輸出等）。三.實驗主要流程、基本操作或核心代碼、算法片段（該部分如不夠填寫，請另加附頁）（1）編程實現(xiàn)兩個串S1和S2的比較。（要求自己設(shè)計串的存儲結(jié)構(gòu)，并編寫比較函數(shù)，不要調(diào)用系統(tǒng)提供的函數(shù)） 程序代碼：頭文件#define OK 1#define ERROR 0#define OVERFLOW -1#define dayu 1#define xiaoyu -2#define dengyu 0typedef int Status;typedef struct char *ch;int length;HString;Status StrAssign(HString &S);Status StrCompare(HString S,HString T);主函數(shù)：#includestdio.h#includestdlib.h#include1.hint main() char c;/用于讀取換行符，便于StrAssign函數(shù)中g(shù)ets讀取串的操作 HString S,T; printf(請確定第一個字符串的長度n); scanf(%d,&S.length); c=getchar(); StrAssign(S);/初始化S的ch部分 printf(請確定第二個字符串的長度n); scanf(%d,&T.length); c=getchar(); StrAssign(T);/初始化T的ch部分 printf(兩字符串的比較結(jié)果為：n); int a;/承載比較結(jié)果 a=StrCompare(S,T);/字符串比較函數(shù) if(a=-2) printf(第一個字符串小于第二個字符串n); else if(a=0) printf(第一個字符串等于第二個字符串n); else if(a=1) printf(第一個字符串大于第二個字符串n); else printf(比較程序出錯n); return ERROR; return OK;功能函數(shù)：#includestdio.h#includestdlib.h#include1.h/初設(shè)S，TStatus StrAssign(HString &S) S.ch=(char *)malloc(sizeof(char)*(S.length+1); if(!S.ch) exit(OVERFLOW); printf(請輸入相應長度的字符串n); gets(S.ch); return OK;/比較函數(shù)Status StrCompare(HString S,HString T) int i=0; while(i=S.length&i=T.length) if(S.chiT.chi) return dayu; if(S.length=T.length) return dengyu; if(S.lengthT.length) return dayu; if(S.lengthT.length) return xiaoyu; return OK; 運行結(jié)果：（2）編程實現(xiàn)稀疏矩陣的三元組順序表示方法及基本操作的實現(xiàn)（建立、輸出、轉(zhuǎn)置等）。程序代碼部分：頭文件：#define OK 1#define ERROR 0#define OVERFLOW -2#define maxsize 30typedef int Status;typedef int ElemType;typedef struct int i,j; ElemType e;Triple;typedef struct Triple datamaxsize; int mu,nu,tu;TSMatrix;Status Init(TSMatrix &trip);void visit(TSMatrix trip);void Transpose(TSMatrix trip,TSMatrix &trip1);主函數(shù)：#includestdio.h#includestdlib.h#include1.hvoid main() TSMatrix trip; printf(請輸入矩陣規(guī)模（行和列數(shù)，空格隔開）n); scanf(%d%d,&trip.mu,&trip.nu); Init(trip); printf(n-n); printf(n原矩陣為n); visit(trip); TSMatrix trip1; Transpose(trip,trip1); printf(n轉(zhuǎn)置矩陣為n); visit(trip1);功能函數(shù)：#includestdio.h#includestdlib.h#include1.h/原矩陣存儲Status Init(TSMatrix &trip) printf(請輸入矩陣元素n); ElemType e; trip.tu=0; for(int i=1;itrip.mu+1;i+) for(int j=1;jtrip.nu+1;j+) scanf(%d,&e); if(e!=0) +trip.tu; trip.datatrip.tu.i=i; trip.datatrip.tu.j=j; trip.datatrip.tu.e=e; return OK;/矩陣的輸出void visit(TSMatrix trip) int n=1; for(int i=1;i=trip.mu;i+) for(int j=1;j=trip.nu;j+) if(trip.datan.i=i&trip.datan.j=j&n=trip.tu) printf(%d ,trip.datan.e); n+; else printf(0 ); printf(n); printf(n);/矩陣的轉(zhuǎn)置void Transpose(TSMatrix trip,TSMatrix &trip1) trip1.nu=trip.mu; trip1.mu=trip.nu; trip1.tu=trip.tu; /形成num-cpot表格 int col=0,t=0; int nummaxsize,cpotmaxsize; for(col=1;col=trip.nu;col+) numcol=0; for(t=1;t=trip.tu;t+) +numtrip.datat.j; cpot1=1; for(col=2;col=trip.nu;col+) cpotcol=cpotcol-1+numcol-1;/注意col從2開始 /實施轉(zhuǎn)置 int p; for(t=1;t=trip.tu;t+) col=trip.datat.j;/第一步：取原矩陣存儲每一個非零元列數(shù) p=cpotcol;/第二步：由列數(shù)得到該元素在轉(zhuǎn)置矩陣存儲中的存放位置/第三步：存放數(shù)據(jù)trip1.datap.i=trip.datat.j;trip1.datap.j=trip.datat.i;trip1.datap.e=trip.datat.e;/第四步：更新每一列下一個非零元在轉(zhuǎn)置矩陣存儲中的存放位置cpotcol+; 運行結(jié)果：（3）編程實現(xiàn)稀疏矩陣的十字鏈表存儲表示及基本操作的實現(xiàn)（建立、輸出等）。程序代碼：頭文件:#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct OLNode int i,j; ElemType e; struct OLNode *right,*down;OLNode,*OLink;typedef struct int mu,nu,tu; OLink *rhead,*chead;CrossList;Status Create(CrossList &T);void print(CrossList T);void Add(CrossList &A,CrossList B);主函數(shù)：#includestdio.h#includestdlib.h#include1.hint main() CrossList A,B; printf(請輸入矩陣A的行數(shù)、列數(shù)、非零元個數(shù)（空格格開）n); scanf(%d %d %d,&A.mu,&A.nu,&A.tu); printf(請輸入矩陣A的非零元對應的行數(shù)、列數(shù)及非零元本身數(shù)值（空格格開，輸入0 0 0表示非零元輸入結(jié)束）n); Create(A); printf(請輸入矩陣B的行數(shù)、列數(shù)、非零元個數(shù)（空格格開）n); scanf(%d %d %d,&B.mu,&B.nu,&B.tu); printf(請輸入矩陣B的非零元對應的行數(shù)、列數(shù)及非零元本身數(shù)值（空格格開，輸入0 0 0表示非零元輸入結(jié)束）n); Create(B); printf(-n); printf(原矩陣A為：n); print(A); printf(原矩陣B為：n); print(B); printf(-n); printf(矩陣A加B為：n); if(A.mu=B.mu&A.nu=B.nu) Add(A,B); print(A); else printf(兩矩陣規(guī)模不同，不能進行加法n); return 0; 功能函數(shù)：#includestdio.h#includestdlib.h#include1.hStatus Create(CrossList &T) if(!(T.rhead=(OLink *)malloc(sizeof(OLink)*(T.mu+1) exit(OVERFLOW); if(!(T.chead=(OLink *)malloc(sizeof(OLink)*(T.nu+1) exit(OVERFLOW); for(int i=1;i=T.mu;i+) T.rheadi=NULL; for(int j=1;ji=i;p-j=j;p-e=e; if(T.rheadi=NULL|T.rheadi-jj) p-right=T.rheadi;T.rheadi=p; else for(q=T.rheadi;(q-right)&q-right-jright); p-right=q-right;q-right=p; if(T.cheadj=NULL|T.cheadj-ii) p-down=T.cheadj;T.cheadj=p; else for(q=T.cheadj;(q-down)&q-down-idown) p-down=q-down;q-down=p; return OK;void print(CrossList T) int t=T.tu; OLNode *p; for(int i=1;i=T.mu;i+) p=T.rheadi; for(int j=1;ji=i&p-j=j) t-;printf(%d ,p-e);p=p-right; elseprintf(0 ); printf(n); printf(n);void Add(CrossList &A,CrossList B)/pre,hl為行、列前驅(qū)，hl特殊（對于每一列的第一個非零元，沒有列前驅(qū)，即此時的hl就是這些非零元，對于同列的其他非零元，hl是前驅(qū)） OLNode *pa,*pb,*pre; OLink *hl; if(!(hl=(OLink *)malloc(sizeof(OLink)*(A.nu+1) exit(OVERFLOW); for(int i=1;i=A.nu;i+) hli=A.cheadi; for(i=1;ijpb-j) A.tu+;OLNode *p; if(!(p=(OLNode *)malloc(sizeof(OLNode) exit(OVERFLOW);p-i=pb-i;p-j=pb-j;p-e=pb-e; if(pre=NULL) A.rheadp-i=p;elsepre-right=p;p-right=pa;pre=p;/為了使下一次處理該情況時，元素有行前驅(qū)，所以讓pre指向p（if和else的共同步驟）;if(A.cheadp-j=NULL|A.cheadp-j-ip-i)p-down=A.cheadp-j;A.cheadp-j=p;elsep-down=hlp-j-down;hlp-j-down=p; hlp-j=p;/為了使下一次處理該情況時，元素有列前驅(qū)，所以讓hl指向p（if和else的共同步驟）;pb=pb-right;/第一種情況和第三種情況處理完后，pb都應改變 else if(pa!=NULL&pa-jj) pre=pa; pa=pa-right;/在第二種和第三種情況下改變 else if(pa-j=pb-j) pa-e+=pb-e;if(pa-e=0) A.tu-; OLNode *p; p=pa;