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

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

2、* * 2-廣 義 表 * * 0-返 回 * * 請選擇菜單號（0-2）：*/#include <stdio.h>#include <stdlib.h>#include <string.h>#define SPAMAX 100 /三元組非零元素的最大個數(shù)#define GLMAX 100typedef struct /定義三元組 int x, y, v; /三元組非零元素的行，列，值spnode;typedef struct /定義稀疏矩陣 int rows, cols, num; /稀疏矩陣中非零元素的行，列，個數(shù) spnode dataSPAMAX;s

3、pamatrix;typedef struct glnode /定義廣義表 int tag; /標志位：0為原子，1為子表 struct glnode *glNext; /指向下一個元素的指針 union glDatas /共用存儲空間 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,

4、 char x);spamatrix createSpamatrix();spamatrix 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) sy

5、stem("pause"); system("cls"); printf("n 稀疏矩陣和廣義表子系統(tǒng)n"); printf("*n"); printf("* 1-稀疏矩陣 *n"); printf("* 2-廣 義 表 *n"); printf("* 0-返 回 *n"); printf("*n"); printf("請選擇菜單號（0-2）："); fflush(stdin); scanf("%d&quo

6、t;, &ch); switch(ch) case 1: sparmatrix(); /稀疏矩陣的三元組存儲 break; case 2: vastlist(); /廣義表 break; case 0: k = 0; break; default: k = 1; break; /*Function: sparmatrix()Description: 稀疏矩陣的三元組存儲Calls: createSpamatrix() transpose() showSpamatrix() findSpamatrix()Input: NULLReturn: voidOthers: NULL*/void

7、sparmatrix() int cho, v, k = 1; spamatrix A, B; A.num = 0; while (k) system("pause"); system("cls"); printf("n 稀疏矩陣的三元組存儲n"); printf("*n"); printf("* 1-新 建 *n"); printf("* 2-轉(zhuǎn) 置 *n"); printf("* 3-查 找 *n"); printf("* 4-顯 示 *n&

8、quot;); printf("* 0-返 回 *n"); printf("*n"); printf("請選擇菜單號（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(&q

9、uot;轉(zhuǎn)置后的矩陣為："); showSpamatrix(B); /顯示矩陣 break; case 3: printf("請輸入要查找的元素："); 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:

10、k = 1; break; /*Function: createSpamatrix()Description: 創(chuàng)建稀疏矩陣的三元組存儲Calls: voidInput: NULLReturn: spamatrixOthers: NULL*/spamatrix createSpamatrix() spamatrix A; int i; /之后可以加入限制條件 printf("請輸入稀疏矩陣的行數(shù)："); scanf("%d", &A.rows); printf("請輸入稀疏矩陣的列數(shù)："); scanf("%d&qu

11、ot;, &A.cols); printf("請輸入稀疏矩陣中非零元素個數(shù)："); scanf("%d", &A.num); for (i = 0; i < A.num; i+) printf("請輸入第%d個元素的行數(shù)：", i+1); scanf("%d", &A.datai.x); printf("請輸入第%d個元素的列數(shù)：", i+1); scanf("%d", &A.datai.y); printf("請輸入第%d個元

12、素的值：", 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.num = A.num; /元素數(shù)不變 for (k = 0;

13、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; /按矩陣格式輸出，零元素自動補充 for (x = 0; x < A.rows; x+) for (

14、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：要查找的

15、元素Return: voidOthers: NULL*/void findSpamatrix(spamatrix A, int v) int i; for (i = 0; i < A.num; i+) if (A.datai.v = v) printf("該元素的位置為：行：%3d，列：%3d。n", A.datai.x+1, A.datai.y+1); i = -1; break; if (i != -1) printf("矩陣不存在該元素。n"); /*Function: vastlist()Description: 廣義表Calls: cre

16、ateGL() showGL() search()Input: NULLReturn: voidOthers: NULL*/void vastlist() int choice, k = 1; char sGLMAX, x; glnode *gHead = NULL; while (k) system("pause"); system("cls"); printf("n 廣 義 表n"); printf("*n"); printf("* 1-新 建 *n"); printf("* 2-

17、查 找 *n"); printf("* 3-顯 示 *n"); printf("* 0-返 回 *n"); printf("*n"); printf("請選擇菜單號（0-3）："); fflush(stdin); scanf("%d", &choice); switch(choice) case 1: printf("新建廣義表："); scanf("%s", s); gHead = createGL(s); /新建 break; cas

18、e 2: if (gHead = NULL) printf("廣義表為空。n"); else printf("請輸入要查找的廣義表的元素："); scanf("%s", &x); if (search(gHead, x) = 1) /查找成功返回值 printf("該元素在廣義表中。n"); else printf("該元素不在廣義表中。n"); break; case 3: if (gHead = NULL) printf("廣義表為空。n"); else prin

19、tf("廣義表為："); printf("("); showGL(gHead); /顯示 break; case 0: k = 0; break; default: k = 1; break; /*Function: createGL()Description: 新建廣義表Calls: change()Input: s：字符串Return: glnode *Others: NULL*/glnode *createGL(char s) glnode *gHead, *p, *q, *r; char strGLMAX, stpGLMAX; int len;

20、len = strlen(s); if (!strcmp(s, "()") /輸入的為空表 gHead = NULL; else if (len = 1) /輸入的只有一個元素 gHead = (glnode *)malloc(sizeof(glnode); gHead->tag = 0; /標志位顯示為原子 gHead->datas.data = *s; /值域賦值 gHead->glNext = NULL; /下一個為空 else /輸入的元素不唯一時 gHead = (glnode *)malloc(sizeof(glnode); gHead->

21、;tag = 1; /標志位顯示為子表 p = gHead; /保持指針 s+; strncpy(str, s, len-2); /去除前括號 strlen-2 = '0' do change(str, stp); /取表頭內(nèi)容 r = createGL(stp); /遞歸調(diào)用 p->datas.next = r; q = p; len = strlen(str); /計算表中剩余長度 if (len > 0) p = (glnode *)malloc(sizeof(glnode); p->tag = 1; q->glNext = p; while (l

22、en > 0); q->glNext = NULL; return gHead;/*Function: search()Description: 查找廣義表中的元素是否存在Calls: voidInput: gHead:：廣義表 x：字符Return: intOthers: NULL*/int search(glnode *gHead, char x) int i = 0; if (gHead != NULL) /廣義表不為空 if (!gHead->tag && gHead->datas.data = x) /元素為原子存在 return 1; els

23、e if (gHead->tag) i = search(gHead->datas.next, x); /查找元素為子表存在 if (i) return 1; else return search(gHead->glNext, x); /查找下一個元素 else return 0; /*Function: change()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 = '(') /字符串中是否含