數(shù)據(jù)結(jié)構(gòu)：稀疏矩陣和廣義表子系統(tǒng)

1、*題目：編寫稀疏矩陣三元組表的存儲(chǔ)程序。* 編寫稀疏矩陣三元組表創(chuàng)建、顯示、轉(zhuǎn)置和查找程序。* 稀疏矩陣二級(jí)菜單形式如下：* 稀疏矩陣的三元組存儲(chǔ)* * * 1-新 建 * * 2-轉(zhuǎn) 置 * * 3-查 找 * * 4-顯 示 * * 0-返 回 * * 請(qǐng)選擇菜單號(hào)（0-4）：*題目：編寫建立廣義表的程序。* 編寫廣義表的顯示和查找程序。* 廣義表二級(jí)菜單形式如下：* 廣 義 表* * * 1-新 建 * * 2-查 找 * * 3-顯 示 * * 0-返 回 * * 請(qǐng)選擇菜單號(hào)（0-3）：/*題目：設(shè)計(jì)選擇式菜單，其一級(jí)菜單形式如下：* 稀疏矩陣和廣義表子系統(tǒng)* * * 1-稀疏矩陣

2、* * 2-廣 義 表 * * 0-返 回 * * 請(qǐng)選擇菜單號(hào)（0-2）：*/#include #include #include #define SPAMAX 100 /三元組非零元素的最大個(gè)數(shù)#define GLMAX 100typedef struct /定義三元組 int x, y, v; /三元組非零元素的行，列，值spnode;typedef struct /定義稀疏矩陣 int rows, cols, num; /稀疏矩陣中非零元素的行，列，個(gè)數(shù) spnode dataSPAMAX;spamatrix;typedef struct glnode /定義廣義表 int tag;

3、/標(biāo)志位：0為原子，1為子表 struct glnode *glNext; /指向下一個(gè)元素的指針 union glDatas /共用存儲(chǔ)空間 char data; /值域 struct glnode *next; /指向子表的指針 datas;glnode;glnode *createGL(char s);void showGL(glnode *gHead);void change(char s, char str);void vastlist();int search(glnode *gHead, char x);spamatrix createSpamatrix();spamatrix

4、transpose(spamatrix A);void showSpamatrix(spamatrix A);void findSpamatrix(spamatrix A, int v);void sparmatrix();/*Function: main()Description: 主調(diào)函數(shù)Calls: vastlist() sparmatrix()Input: NULLReturn: voidOthers: NULL*/void main() int ch, k = 1; while (k) system(pause); system(cls); printf(n 稀疏矩陣和廣義表子系統(tǒng)n

5、); printf(*n); printf(* 1-稀疏矩陣 *n); printf(* 2-廣 義 表 *n); printf(* 0-返 回 *n); printf(*n); printf(請(qǐng)選擇菜單號(hào)（0-2）：); fflush(stdin); scanf(%d, &ch); switch(ch) case 1: sparmatrix(); /稀疏矩陣的三元組存儲(chǔ) break; case 2: vastlist(); /廣義表 break; case 0: k = 0; break; default: k = 1; break; /*Function: sparmatrix()Desc

6、ription: 稀疏矩陣的三元組存儲(chǔ)Calls: createSpamatrix() transpose() showSpamatrix() findSpamatrix()Input: NULLReturn: voidOthers: NULL*/void sparmatrix() int cho, v, k = 1; spamatrix A, B; A.num = 0; while (k) system(pause); system(cls); printf(n 稀疏矩陣的三元組存儲(chǔ)n); printf(*n); printf(* 1-新 建 *n); printf(* 2-轉(zhuǎn) 置 *n);

7、 printf(* 3-查 找 *n); printf(* 4-顯 示 *n); printf(* 0-返 回 *n); printf(*n); printf(請(qǐng)選擇菜單號(hào)（0-4）：); fflush(stdin); /清空輸入的緩存區(qū) scanf(%d, &cho); switch(cho) case 1: A = createSpamatrix(); /新建矩陣 break; case 2: if (A.num = 0) printf(三元組為空。n); else B = transpose(A); /轉(zhuǎn)置 printf(轉(zhuǎn)置后的矩陣為：); showSpamatrix(B); /顯示矩

8、陣 break; case 3: printf(請(qǐng)輸入要查找的元素：); scanf(%d, &v); findSpamatrix(A, v); /查找 break; case 4: if (A.num = 0) printf(三元組為空。n); else printf(矩陣為：); showSpamatrix(A); /顯示矩陣 break; case 0: k = 0; break; default: k = 1; break; /*Function: createSpamatrix()Description: 創(chuàng)建稀疏矩陣的三元組存儲(chǔ)Calls: voidInput: NULLRetur

9、n: spamatrixOthers: NULL*/spamatrix createSpamatrix() spamatrix A; int i; /之后可以加入限制條件 printf(請(qǐng)輸入稀疏矩陣的行數(shù)：); scanf(%d, &A.rows); printf(請(qǐng)輸入稀疏矩陣的列數(shù)：); scanf(%d, &A.cols); printf(請(qǐng)輸入稀疏矩陣中非零元素個(gè)數(shù)：); scanf(%d, &A.num); for (i = 0; i A.num; i+) printf(請(qǐng)輸入第%d個(gè)元素的行數(shù)：, i+1); scanf(%d, &A.datai.x); printf(請(qǐng)輸入第%

10、d個(gè)元素的列數(shù)：, i+1); scanf(%d, &A.datai.y); printf(請(qǐng)輸入第%d個(gè)元素的值：, i+1); scanf(%d, &A.datai.v); return A;/*Function: transpose()Description: 轉(zhuǎn)置稀疏矩陣Calls: voidInput: A：spamatrix類型Return: spamatrixOthers: NULL*/spamatrix transpose(spamatrix A) spamatrix B; int k; B.rows = A.cols; /行數(shù)與列數(shù)交換 B.cols = A.rows; B.

11、num = A.num; /元素?cái)?shù)不變 for (k = 0; k B.num; k+) B.datak.x = A.datak.y; B.datak.y = A.datak.x; B.datak.v = A.datak.v; return B;/*Function: showSpamatrix()Description: 顯示稀疏矩陣Calls: voidInput: A：spamatrix類型Return: voidOthers: NULL*/void showSpamatrix(spamatrix A) int x, y, i, k; /按矩陣格式輸出，零元素自動(dòng)補(bǔ)充 for (x =

12、0; x A.rows; x+) for (y = 0; y A.cols; y+) k = 0; for (i = 0; i A.num; i+) if (A.datai.x = x & A.datai.y = y) printf(%3d, A.datai.v); k = 1; if (k = 0) printf(%3d, k); printf(n); /*Function: findSpamatrix()Description: 查找稀疏矩陣中的元素Calls: voidInput: A：spamatrix類型 v：要查找的元素Return: voidOthers: NULL*/void

13、findSpamatrix(spamatrix A, int v) int i; for (i = 0; i tag = 0; /標(biāo)志位顯示為原子 gHead-datas.data = *s; /值域賦值 gHead-glNext = NULL; /下一個(gè)為空 else /輸入的元素不唯一時(shí) gHead = (glnode *)malloc(sizeof(glnode); gHead-tag = 1; /標(biāo)志位顯示為子表 p = gHead; /保持指針 s+; strncpy(str, s, len-2); /去除前括號(hào) strlen-2 = 0; do change(str, stp);

14、/取表頭內(nèi)容 r = createGL(stp); /遞歸調(diào)用 p-datas.next = r; q = p; len = strlen(str); /計(jì)算表中剩余長度 if (len 0) p = (glnode *)malloc(sizeof(glnode); p-tag = 1; q-glNext = p; while (len 0); q-glNext = NULL; return gHead;/*Function: search()Description: 查找廣義表中的元素是否存在Calls: voidInput: gHead:：廣義表 x：字符Return: intOthers

15、: NULL*/int search(glnode *gHead, char x) int i = 0; if (gHead != NULL) /廣義表不為空 if (!gHead-tag & gHead-datas.data = x) /元素為原子存在 return 1; else if (gHead-tag) i = search(gHead-datas.next, x); /查找元素為子表存在 if (i) return 1; else return search(gHead-glNext, x); /查找下一個(gè)元素 else return 0; /*Function: change()

16、Description: 區(qū)分表頭及其他部分Calls: voidInput: s：字符串（輸入者，也是保存剩余內(nèi)容） str：字符串（表頭的內(nèi)容）Return: voidOthers: NULL*/void change(char s, char str) char stpGLMAX; int i, j, r, k; i = j = r = k = 0; while (si & (si != , | k) if (si = () /字符串中是否含有括號(hào) k+; else if (si = ) k-; if (si != , | (si = , & k) strj = si; /賦值 i+; j+; stri = 0; if (si = ,) i+; while (si) stpr = si; r+; i+; stpr = 0; strcpy(s, stp);/*Function: showGL()Description: 顯示廣義表內(nèi)容Calls: voidInput: gHead：廣義表Return: voidOthers: NULL*/void showGL(glnode *gHead) glnode *p, *q; if (gHead) /不為空 do p = gHead-da