數(shù)據(jù)結(jié)構(gòu)_實(shí)驗(yàn)四_字符串、稀疏矩陣實(shí)驗(yàn)

1、實(shí)驗(yàn)編號(hào)：4 四川師大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告2016 年 11 月 12日實(shí)驗(yàn)四 字符串、稀疏矩陣實(shí)驗(yàn)（1） 熟悉字符串類型的實(shí)現(xiàn)方法，并完成串的一些基本操作；（2） 掌握稀疏矩陣的三元組順序表存儲(chǔ)表示，并實(shí)現(xiàn)矩陣的轉(zhuǎn)置運(yùn)算。（1） 編程實(shí)現(xiàn)兩個(gè)串S1和S2的比較。 （要求自己設(shè)計(jì)串的存儲(chǔ)結(jié)構(gòu)，并編寫比較函數(shù)，不要調(diào)用系統(tǒng)提供的函數(shù)）（2） 編程實(shí)現(xiàn)稀疏矩陣的三元組順序表示方法及基本操作的實(shí)現(xiàn)（建立、輸出、轉(zhuǎn)置等） 。（3） 編程實(shí)現(xiàn)稀疏矩陣的十字鏈表存儲(chǔ)表示及基本操作的實(shí)現(xiàn)（建立、輸出等）。注： （ 2）必做，（ 1 ） （ 3）選做。（ 1） PC機(jī)（ 2） Dev C+ ,Visual C+,

2、 VS2010 等（ 1）編程實(shí)現(xiàn)兩個(gè)串S1 和 S2的比較。 （要求自己設(shè)計(jì)串的存儲(chǔ)結(jié)構(gòu)，并編寫比較函數(shù)，不要調(diào)用系統(tǒng)提供的函數(shù)）代碼部分：/Main.cpp:#include"SString.h int main()SString T1,T2;int i,n;T10=T20=0;cout<<"input T1 size:"cin>>n;T10=n;cout<<"input T1 data:"for(i=1;i<=n;i+)cin>>T1i;cout<<"input

3、T2 size:"cin>>n;T20=n;cout<<"input T2 data:"for(i=1;i<=n;i+)cin>>T2i;cout<<"T1"<<Compare(T1,T2)<<"T2"<<endl;return 0;/SString.cpp:#include"SString.h"char Compare(SString T1,SString T2)if(T10>T20)return '

4、>'else if(T10<T20)return '<'elsefor(int i=1;i<=T10;i+)if(T1i>T2i)return '>'else if(T1i<T2i)return '<'return '='/SString.h:#include<iostream> using namespace std;const int MAX=255;typedef unsigned char SStringMAX+1;char Compare(SString

5、 T1,SString T2);2)編程實(shí)現(xiàn)稀疏矩陣的三元組順序表示方法及基本操作的實(shí)現(xiàn)輸出、 轉(zhuǎn)置等) 。代碼部分：/Main.cpp#include"TSMatrix.h" int main()TSMatrix T,M;int count;cout<<"輸入矩陣的行數(shù)，列數(shù)，非零元個(gè)數(shù)："cin>>M.mu>>M.nu>>M.tu;for (count=1;count<=M.tu;count+)cout<<" 請輸入第"<<count<<&q

6、uot; 個(gè)非零元的行數(shù),列數(shù),數(shù)據(jù)"<<endl;cin>>M.datacount.i>>M.datacount.j>>M.datacount.e;TransposeSMatrix(M,T);cout<<"i j e"<<endl;for (count=1;count<=T.tu;count+)cout<<T.datacount.i<<" "<<T.datacount.j<<" "<<T

7、.datacount.e<<endl;return 0;/TSMatrix.cpp#include"TSMatrix.h"Status TransposeSMatrix(TSMatrix M,TSMatrix &T)int col,p,q;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(col=1;col<=M.nu;+col)for(p=1;p<=M.tu;+p)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M

8、.datap.e;+q;return OK;/TSMatrix.h#include<iostream>using namespace std;const int MAXSIZE=12500;const int OK=1;const int ERROR=0;typedef int ElemType;typedef int Status;typedef structint i,j;ElemType e;Triple;typedef struct Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;Status TransposeSMatrix(TSMa

9、trix M,TSMatrix &T);運(yùn)行結(jié)果：3)編程實(shí)現(xiàn)隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)中的基本操作(隊(duì)列的初始化、判隊(duì)列空、入隊(duì)列、。代碼部分：A: 鏈?zhǔn)絻?chǔ)存：/Main.cpp:#include"QNode.h"int main()LinkQueue Q;InitQueue(Q);Menu(Q);DestroyQueue(Q);return 0;/QNode.cpp:#include"QNode.h"Status InitQueue(LinkQueue &Q)/構(gòu)造空隊(duì)列Q.front=Q.rear=(QueuePrt)malloc(size

10、of(QNode);if(!Q.front) exit (ERROR);Q.front->next=NULL;return OK;Status DestroyQueue(LinkQueue &Q)/銷毀隊(duì)列Qwhile(Q.front)Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;return OK;Status EnQueue (LinkQueue &Q,QElemType e)/插入元素a 為 Q 的新的隊(duì)尾元素QNode *p;p=(QueuePrt)malloc(sizeof(QNode);if(!p)

11、exit(ERROR);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return OK;Status DeQueue (LinkQueue &Q,QElemType &e)/刪除Q 的隊(duì)頭元素，用e 返回其值QNode *p;if(Q.front=Q.rear) return ERROR;p = Q.front->next;e=p->data;Q.front->next=p->next;if (Q.rear=p) Q.rear=Q.front;free(p);return OK;Stat

12、us QueueEmpty(LinkQueue Q)/判斷對是否為空if(Q.front=Q.rear)return ERROR;return OK;void Menu(LinkQueue &Q)/輸出選擇界面int select=1;QElemType e;while(select)cout<<""<<endl;cout<<" 請選擇以下功能："<<endl;cout<<"1, 入隊(duì) "<<endl;cout<<"2, 出隊(duì) &qu

13、ot;<<endl;cout<<"3, 判斷隊(duì)空"<<endl;cout<<"0, 退出程序"<<endl;cout<<" 請輸入你的選擇"cin>>select;switch (select)case 0:break;case 1:cout<<" 輸入入隊(duì)數(shù)據(jù)"<<endl;cin>>e;if(EnQueue(Q,e)cout<<" 入隊(duì)成功"<<en

14、dl;break;case 2:if(DeQueue(Q,e) cout<<e<<" 出隊(duì) "<<endl;break;case 3:if(QueueEmpty(Q) cout<<" 此隊(duì)不為空"<<endl;else cout<<"此隊(duì)為空"<<endl;break;/QNode.h#ifndef QNODE_H #define QNODE_H#include<iostream>#include<stdlib.h>using

15、namespace std;const int OK=1;const int ERROR=0;typedef int QElemType;typedef int Status;typedef struct QNodeQElemType data;struct QNode * next;QNode,*QueuePrt;typedef struct QueuePrt front;QueuePrt rear;LinkQueue;Status InitQueue(LinkQueue &Q);/ 構(gòu)造空隊(duì)列Status DestroyQueue(LinkQueue &Q);/ 銷毀隊(duì)列Q

16、Status EnQueue (LinkQueue &Q,QElemType e);/ 插入元素a為 Q 的新的隊(duì)尾元素Status DeQueue (LinkQueue &Q,QElemType &e);/ 刪除 Q 的隊(duì)頭元素，用e 返回其值Status QueueEmpty(LinkQueue Q);/ 判斷對是否為空void Menu(LinkQueue &Q);/ 輸出選擇界面#endif運(yùn)行結(jié)果：B 順序存儲(chǔ):代碼部分：/main.cpp:#include"SqQueue.h"int main()SqQueue Q;if(Init

17、Queue(Q)cout<<" 創(chuàng)建隊(duì)成功"<<endl;Menu(Q);DestroyQueue(Q);return 0;/SqQueue.cpp:#include"SqQueue.h"Status InitQueue(SqQueue &Q)/創(chuàng)建空隊(duì)列Q.base=(QElemType *)malloc(MAXSIZE * sizeof(QElemType);if (!Q.base) exit(ERROR);Q.front=Q.rear=0;return OK;Status EnQueue(SqQueue &Q

18、,QElemType e)/插入元素e 為 Q 的新隊(duì)尾元素if(Q.rear+1)% MAXSIZE) = Q.front) return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;Status DeQueue(SqQueue &Q,QElemType &e)/刪除Q 的對頭元素，用e 返回其值。if(Q.front = Q.rear) return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;return OK;Status SqQueueEmpt

19、y(SqQueue Q)/判斷Q 是否為空if(Q.front=Q.rear) return ERROR;return OK;Status DestroyQueue(SqQueue &Q)/銷毀棧Q.front=Q.rear=0;free(Q.base);return OK;void Menu(SqQueue &Q)/輸出選擇菜單int select=1;QElemType e;while (select)cout<<""<<endl;cout<<" 請選擇一下功能:"<<endl;cout

20、«"cout«"cout«"cout«"cout«"你的選擇是：" cin»select;switch (select)case O:break;case 1:1,入隊(duì)"«endl;2,出隊(duì)"«endl;3,判斷是否為空"<<endl;0,退出程序"«endl;cout«"輸入插入的數(shù)據(jù):"cin»e;if(EnQueue(Q,e)cout<<

21、"入隊(duì)成功"«endl;)else cout«"隊(duì)滿"«endl;break;case 2:if(DeQueue(Q,e)cout«e«"出隊(duì) "<<er)dl;)else cout«"隊(duì)空"«endl;break;case 3:if(SqQueueEmpty(Q)cout«"隊(duì)未空"«endl;)else cout«"隊(duì)空"«endl;break;/Sq

22、Queue.h:#ifndef SQQUEUE_H#define SQQUEUE_H#include<iostream>#include<stdlib.h>using namespace std;const int MAXSIZE=100;const int MORE=100;const int OK=1;const int ERROR=0;typedef int QElemType;typedef int Status;typedef structQElemType *base;int front ;int rear;SqQueue;Status InitQueue(

23、SqQueue &Q);/ 創(chuàng)建空隊(duì)列Status EnQueue(SqQueue &Q,QElemType e);/ 插入元素e 為 Q 的新隊(duì)尾元素Status DeQueue(SqQueue &Q,QElemType &e);/ 刪除 Q 的對頭元素，用e 返回其值。Status SqQueueEmpty(SqQueue Q);/判斷Q 是否為空Status DestroyQueue(SqQueue &Q);/ 銷毀棧void Menu(SqQueue &Q);/ 輸出選擇菜單#endif運(yùn)行結(jié)果：（ 3） 編程實(shí)現(xiàn)稀疏矩陣的十字鏈表存儲(chǔ)表

24、示及基本操作的實(shí)現(xiàn)（建立、輸出等）代碼部分：/ CrossList.#include<stdio.h>#include<stdlib.h>#define OK 1;#define ERROR 1;typedef int ElemType;typedef int Status;typedef struct OLNodeint i,j;ElemType e;struct OLNode *right,*down;OLNode,*OLink;typedef structOLink *rhead,*chead;int mu,nu,tu;CrossList;Status Creat

25、eSMatrix_OL (CrossList &M);/ CrossList.cpp#include"CrossList.hStatus CreateSMatrix_OL (CrossList &M)int m,n,t,i,j,e,k;OLNode *p,*q;/ if(M) free(M);printf("mu,nu,tu :");scanf("%d %d %d",&m,&n,&t);M.mu=m;M.nu=n;M.tu=t;M.rhead=(OLink*)malloc(m+1)*sizeof(OLin

26、k);if(!M.rhead)return ERROR;if (!(M.chead=(OLink*)malloc(n+1)*sizeof(OLink) return ERROR;for(k=1;k<=M.mu;k+) M.rheadk=NULL;for(k=1;k<=M.nu;k+) M.cheadk=NULL;printf("input i j e:");for(scanf("%d%d%d",&i,&j,&e);i!=0;scanf("%d%d%d",&i,&j,&e)p=(OLNode *)malloc(sizeof(OLi