『壹』 用十字鏈表表示稀疏矩陣，並實現稀疏矩陣加法
呵呵 和樓主還真是有緣喲 我恰好前兩天編了這個程序，給樓主看看哈，希望可以幫上樓主的忙喲，我這個程序還包含了用石子鏈表實現稀疏矩陣的加法，三元組實現矩陣的乘法，如果樓主不需要可以刪掉哈，更多相關質料可以參見喲，呵呵、
#include <iostream>
#include <iomanip>
using namespace std;
const int MAXSIZE=100; // 定義非零元素的對多個數
const int MAXROW=10; // 定義數組的行數的最大值
typedef struct { // 定義三元組的元素
int i,j;
int e;
}Triple;
typedef struct { // 定義普通三元組對象
Triple data[MAXSIZE+1];
int mu,nu,tu;
}TSMatrix;
typedef struct { // 定義帶鏈接信息的三元組對象
Triple data[MAXSIZE+2];
int rpos[MAXROW+1];
int mu,nu,tu;
}RLSMatrix;
template <class P>
bool InPutTSMatrix(P & T,int y){ //輸入矩陣，按三元組格式輸入
cout<<"輸入矩陣的行，列和非零元素個數:"<<endl;
cin>>T.mu>>T.nu>>T.tu;
cout<<"請輸出非零元素的位置和值:"<<endl;
int k=1;
for(;k<=T.tu;k++)
cin>>T.data[k].i>>T.data[k].j>>T.data[k].e;
return true;
}
template <class P>
bool OutPutSMatrix(P T){ // 輸出矩陣，按標准格式輸出
int m,n,k=1;
for(m=0;m<T.mu;m++){
for(n=0;n<T.nu;n++){
if((T.data[k].i-1)==m&&(T.data[k].j-1)==n){
cout.width(4);
cout<<T.data[k++].e;}
else{
cout.width(4); cout<<"0"; }
}
cout<<endl;
}
return true;
}
// 求矩陣的轉置矩陣
bool TransposeSMatrix( ){
TSMatrix M,T; //定義預轉置的矩陣
InPutTSMatrix(M, 0); //輸入矩陣
int num[MAXROW+1];
int cpot[MAXROW+1]; // 構建輔助數組
int q,p,t;
T.tu=M.tu; T.mu=M.nu; T.nu=M.mu;
if(T.tu){
for(int col=1;col<=M.nu;col++) num[col]=0;
for(t=1;t<=M.tu;t++) ++num[M.data[t].j];
cpot[1]=1;
for(int i=2;i<=M.nu;i++) cpot[i]=cpot[i-1]+num[i-1]; // 求出每一列中非零元素在三元組中出現的位置
for(p=1;p<=M.tu;p++){
col=M.data[p].j; q=cpot[col];
T.data[q].i=col; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++cpot[col];
}
}
cout<<"輸入矩陣的轉置矩陣為"<<endl;
OutPutSMatrix(T);
return true;
}
bool Count(RLSMatrix &T)
{
int num[MAXROW+1];
for(int col=1;col<=T.mu;col++) num[col]=0;
for(col=1;col<=T.tu;col++) ++num[T.data[col].i];
T.rpos[1]=1;
for(int i=2;i<=T.mu;i++) T.rpos[i]=T.rpos[i-1]+num[i-1]; // 求取每一行中非零元素在三元組中出現的位置
return true;
}
// 兩個矩陣相乘
bool MultSMatrix ( ){
RLSMatrix M,N,Q; // 構建三個帶「鏈接信息」的三元組表示的數組
InPutTSMatrix(M,1); // 用普通三元組形式輸入數組
InPutTSMatrix(N,1);
Count(M); Count(N);
if(M.nu!=N.mu) return false;
Q.mu=M.mu; Q.nu=N.nu; Q.tu=0; // Q初始化
int ctemp[MAXROW+1]; // 輔助數組
int arow,tp,p,brow,t,q,ccol;
if(M.tu*N.tu){ // Q是非零矩陣
for( arow=1;arow<=M.mu;arow++){
///memset(ctemp,0,N.nu);
for(int x=1;x<=N.nu;x++) // 當前行各元素累加器清零
ctemp[x]=0;
Q.rpos[arow]=Q.tu+1; // 當前行的首個非零元素在三元組中的位置為此行前所有非零元素+1
if(arow<M.mu) tp=M.rpos[arow+1];
else tp=M.tu+1;
for(p=M.rpos[arow];p<tp;p++){ // 對當前行每個非零元素進行操作
brow=M.data[p].j; // 在N中找到i值也操作元素的j值相等的行
if(brow<N.mu) t=N.rpos[brow+1];
else t=N.tu+1;
for(q=N.rpos[brow];q<t;q++){ // 對找出的行當每個非零元素進行操作
ccol=N.data[q].j;
ctemp[ccol] += M.data[p].e*N.data[q].e; // 將乘得到對應值放在相應的元素累加器裡面
}
}
for(ccol=1;ccol<=Q.nu;ccol++) // 對已經求出的累加器中的值壓縮到Q中
if(ctemp[ccol]){
if(++Q.tu>MAXSIZE) return false;
Q.data[Q.tu].e=ctemp[ccol];
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
}
}
}
OutPutSMatrix(Q);
return true;
}
typedef struct OLNode{ // 定義十字鏈表元素
int i,j;
int e;
struct OLNode *right,*down; // 該非零元所在行表和列表的後繼元素
}OLNode,*OLink;
typedef struct{ // 定義十字鏈表對象結構體
OLink *rhead,*chead;
int mu,nu,tu; // 系數矩陣的行數，列數，和非零元素個數
}CrossList;
bool CreateSMatrix_OL(CrossList & M){ // 創建十字鏈表
int x,y,m;
cout<<"請輸入矩陣的行，列，及非零元素個數"<<endl;
cin>>M.mu>>M.nu>>M.tu;
if(!(M.rhead=(OLink*)malloc((M.mu+1)*sizeof(OLink)))) exit(0);
if(!(M.chead=(OLink*)malloc((M.nu+1)*sizeof(OLink)))) exit(0);
for(x=0;x<=M.mu;x++)
M.rhead[x]=NULL; // 初始化各行，列頭指針，分別為NULL
for(x=0;x<=M.nu;x++)
M.chead[x]=NULL;
cout<<"請按三元組的格式輸入數組："<<endl;
for(int i=1;i<=M.tu;i++){
cin>>x>>y>>m; // 按任意順序輸入非零元，（普通三元組形式輸入）
OLink p,q;
if(!(p=(OLink)malloc(sizeof(OLNode)))) exit(0); // 開辟新節點，用來存儲輸入的新元素
p->i=x; p->j=y; p->e=m;
if(M.rhead[x]==NULL||M.rhead[x]->j>y){
p->right=M.rhead[x]; M.rhead[x]=p;
}
else{
for(q=M.rhead[x];(q->right)&&(q->right->j<y);q=q->right); // 查找節點在行表中的插入位置
p->right=q->right; q->right=p; // 完成行插入
}
if(M.chead[y]==NULL||M.chead[y]->i>x){
p->down=M.chead[y]; M.chead[y]=p;
}
else{
for(q=M.chead[y];(q->down)&&(q->down->i<x);q=q->down); // 查找節點在列表中的插入位置
p->down=q->down; q->down=p; // 完成列插入
}
}
return true;
}
bool OutPutSMatrix_OL(CrossList T){ // 輸出十字鏈表，用普通數組形式輸出
for(int i=1;i<=T.mu;i++){
OLink p=T.rhead[i];
for(int j=1;j<=T.nu;j++){
if((p)&&(j==p->j)){
cout<<setw(3)<<p->e; p=p->right;
}
else
cout<<setw(3)<<"0";
}
cout<<endl;
}
return true;
}
//矩陣的加法
bool AddSMatrix(){
CrossList M,N; // 創建兩個十字鏈表對象，並初始化
CreateSMatrix_OL(M);
CreateSMatrix_OL(N);
cout<<"輸入的兩矩陣的和矩陣為："<<endl;
OLink pa,pb,pre ,hl[MAXROW+1]; //定義輔助指針，pa，pb分別為M,N當前比較的元素，pre為pa的前驅元素
for(int x=1;x<=M.nu;x++) hl[x]=M.chead[x];
for(int k=1;k<=M.mu;k++){ // 對M的每一行進行操作
pa=M.rhead[k]; pb=N.rhead[k]; pre=NULL;
while(pb){ // 把N中此行的每個元素取出，
OLink p;
if(!(p=(OLink)malloc(sizeof(OLNode)))) exit(0); // 開辟新節點，存儲N中取出的元素
p->e=pb->e; p->i=pb->i; p->j=pb->j;
if(NULL==pa||pa->j>pb->j){ // 當M此行已經檢查完或者pb因該放在pa前面
if(NULL==pre)
M.rhead[p->i]=p;
else
pre->right=p;
p->right=pa; pre=p;
if(NULL==M.chead[p->j]){ // 進行列插入
M.chead[p->j]=p; p->down=NULL;
}
else{
p->down=hl[p->j]->down; hl[p->j]->down=p;
}
hl[p->j]=p;
pb=pb->right;
}
else
if((NULL!=pa)&&pa->j<pb->j){ // 如果此時的pb元素因該放在pa後面，則取以後的pa再來比較
pre=pa; pa=pa->right;
}
else
if(pa->j==pb->j){ // 如果pa，pb位於同一個位置上，則將值相加
pa->e += pb->e;
if(!pa->e){ // 如果相加後的和為0，則刪除此節點，同時改變此元素坐在行，列的前驅元素的相應值
if(NULL==pre) // 修改行前驅元素值
M.rhead[pa->i]=pa->right;
else
pre->right=pa->right;
p=pa; pa=pa->right;
if(M.chead[p->j]==p) M.chead[p->j]=hl[p->j]=p->down; // 修改列前驅元素值
else
hl[p->j]->down=p->down;
free(p); pb=pb->right;
}
else{
pa=pa->right; pb=pb->right;
}
}
}
}
OutPutSMatrix_OL(M);
return true;
}
int main(){
cout.fill('*');
cout<<setw(80)<<'*';
cout.fill(' ');
// system("color 0C");
cout<<setw(50)<<"***歡迎使用矩陣運算程序***"<<endl; //輸出頭菜單
cout.fill('*');
cout<<setw(80)<<'*';
cout.fill(' ');
cout<<"請選擇要進行的操作："<<endl;
cout<<"1:矩陣的轉置。"<<endl;
cout<<"2:矩陣的加（減）法。"<<endl;
cout<<"3:矩陣的乘法。"<<endl;
cout<<"4:推出程序。"<<endl;
char c=getchar();
if(c=='1')
TransposeSMatrix( ); //調用矩陣轉置函數
else
if(c=='2')
AddSMatrix(); //調用矩陣相加函數
else
if(c=='3')
MultSMatrix (); //調用矩陣相乘函數
else
exit(0); //退出
return 0;
}
『貳』 十字鏈表是什麼
十字鏈表是有向圖的另一種鏈式存儲結構，是將有向圖的正鄰接表和逆鄰接表結合起來得到的一種鏈表。
十字鏈表在這種結構中，每條弧的弧頭結點和弧尾結點都存放在鏈表中，並將弧結點分別組織到以弧尾結點為頭結點和以弧頭結點為頭結點的鏈表中。由此可見，圖中的每條弧存在於兩個鏈表中，一個是弧頭相同的鏈表，一個是弧尾相同的鏈表，兩個鏈表在該弧處交叉形成「十」字，因此稱作十字鏈表。十字鏈表的結點結構如圖7－14所示。頂點結點由2個域組成，其中data域存儲和頂點相關的信息，如頂點的名稱等；firstin和firstout為兩個指針域，分別指向以該頂點為弧頭和弧尾的第一個弧結點。弧結點有5個域，其中尾域tailve*和頭域headve*分別指向弧尾和弧頭這兩個頂點在圖中的位置，指針域hlink指向弧頭相同的下一條弧，而指針域tlink指向弧尾相同的下一條弧，Info域指向該弧的相關信息。
十字鏈表的結點結構
『叄』 用十字鏈表作為存儲結構建立有向圖
http://hi..com/yedeqixian/item/58b9c4f6d0db17c5521c2665 裡面的很詳細。
『肆』 十字鏈表的介紹
十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。該結構可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的。用十字鏈表來存儲有向圖，可以達到高效的存取效果。同時，代碼的可讀性也會得到提升。
『伍』 用十字鏈表存儲結稀疏矩陣，並進行矩陣的轉置。 要C的，c++的我看不懂。。。。~
這個吧 功能比你要的還多：http://wenku..com/view/3d744dd950e2524de5187e68.html
建立稀疏矩陣A 的十字鏈表首先輸入的信息是：m（A 的行數），n（A 的列數），r（非零項的數目），緊跟著輸入的是r 個形如（i,j,aij）的三元組。
演算法的設計思想是：首先建立每行（每列）只有頭結點的空鏈表，並建立起這些頭結點拉成的循環鏈表；然後每輸入一個三元組（i，j，aij），則將其結點按其列號的大小插入到第i 個行鏈表中去，同時也按其行號的大小將該結點插入到第j 個列鏈表中去。在演算法中將利用一個輔助數組MNode *hd[s+1]; 其中s=max(m , n) , hd [i]指向第i 行(第i 列)鏈表的頭結點。這樣做可以在建立鏈表時隨機的訪問任何一行（列），為建表帶來方便。
演算法如下：
MLink CreatMLink( ) /* 返回十字鏈表的頭指針*/
｛
MLink H;
Mnode *p,*q,*hd[s+1];
int i,j,m,n,t;
datatype v;
scanf(「%d,%,%d」,&m,&n,&t);
H=malloc(sizeof(MNode)); /*申請總頭結點*/
H->row=m; H->col=n;
hd[0]=H;
for(i=1; i<S; i++)
{ p=malloc(sizeof(MNode)); /*申請第i 個頭結點*/
p->row=0; p->col=0;
p->right=p; p->down=p;
hd[i]=p;
hd[i-1]->v_next.next=p;
}
hd[S]->v_next.next=H; /*將頭結點們形成循環鏈表*/
for (k=1;k<=t;k++)
{ scanf (「%d,%d,%d」,&i,&j,&v); /*輸入一個三元組，設值為int*/
p=malloc(sizeof(MNode));
p->row=i ; p->col=j; p->v_next.v=v
/*以下是將*p 插入到第i 行鏈表中去，且按列號有序*/
q=hd[i];
while ( q->right!=hd[i] && (q->right->col)<j ) /*按列號找位置*/
q=q->right;
p->right=q->right; /*插入*/
q->right=p;
/*以下是將*p 插入到第j 行鏈表中去，且按行號有序*/
q=hd[i];
while ( q->down!=hd[j] && (q->down->row)<i ) /*按行號找位置*/
q=q->down;
p-> down =q-> down; /*插入*/
q-> down =p;
} /*for k*/
return H;
} /* CreatMLink */
『陸』 用十字鏈表的存儲結構構造一個圖，並分別進行深度優先和廣度優先遍歷。。。要完整的程序
我們也是這個作業。。。。。。。。。。。。。。。。。。
『柒』 將下圖所示稀疏矩陣A用十字鏈表存儲法表示。
消去c得：
6a²+a+b²-16b-2=0
6a²+a+（b-8）²=66
∵6a²+a≤66
∴a≤3
∴a=1,2,3
逐一試驗可知
a=3，b-8=±3
即a=3，b=11，c=8b-3a²=61
或a=3，b=5，c=13
∴abc的最大值是3×11×61=2013
『捌』 設計利用十字鏈表為存儲結構對有向圖進行遍歷的操作
哥們你這個的答案還有么 我的和你的一樣能交流一下么
『玖』 十字鏈表的十字鏈表
十字鏈表（Orthogonal List)是有向圖的另一種鏈式存儲結構。可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的一種鏈表。在十字鏈表中，對應於有向圖中每一條弧都有一個結點，對應於每個定頂點也有一個結點。
十字鏈表之於有向圖，類似於鄰接表之於無向圖。
也可以理解為 將行的單鏈表和列的單鏈表結合起來存儲稀疏矩陣稱為十字鏈表， 每個節點表示一個非零元素。
『拾』 跪求C語言達人！！！！！關於圖的十字鏈表的
十字鏈表就是用來表示有向圖的，我給你個存儲結構表示形式：
//弧結點：
typedef struct arcnode
{ int tailvex, headvex; //弧尾、弧頭在表頭數組中位置
struct arcnode *hlink；//指向弧頭相同的下一條弧
struct arcnode *tlink; //指向弧尾相同的下一條弧
int *info; //該弧相關信息指針
}AD;
//頂點結點：
typedef struct dnode
{ int data; //存與頂點有關信息
struct arcnode *firstin；//指向以該頂點為弧頭的第一個弧結點
struct arcnode *firstout; //指向以該頂點為弧尾的第一個弧結點
}DD;
DD g[M]; //DD g[M]就是有向圖的十字鏈表存儲表示的數據結構，g[0]不用
只要輸入n個頂點信息和e條弧信息，就可以建立了！幾個for循環加scanf的問題，學習一下struct的初始化吧