疎行列の3つの記憶方式
20150 ワード
一、関連概念
1つの特殊な行列:行列には多くの数値が同じ要素、または非0要素が存在し、行列中の分布には一定の法則がある.
1.対称行列:行列中の要素が満足する
aij=aji 1≤i,j≤n
⒉三角行列:上(下)三角行列は、行列の下(上)三角(対角線を含まない)の要素が定数cまたは0のn次行列を指す.
3.対角行列(帯状行列):行列内のすべての非0要素が主対角線を中心とした領域に集中する.
二疎行列:非0元素が少なく(≦5%)、分布が不規則である.
二、ストレージ構造
1、対称行列
ストレージ割り当てポリシー:対称要素のペアに1つのストレージユニットのみが割り当てられます.すなわち、下三角(対角線を含む)の要素のみが格納されます.必要な空間数はn(n+1)/2です.
ストレージ割り当て方法:1次元配列sa[n(n+1)/2]をストレージ構造とする.
2、三角行列
n次方程式でもあり,上三角行列と下三角行列がある.下(上)三角行列は、主対角線以上(下)の要素がいずれもゼロのn次行列である.1次元配列sb[0..n(n+1)/2]をn次三角行列Bの記憶構造として、行別記憶方式を採用すると、Bのいずれかの要素bi,j,sb[k]の間には、上記のような対応関係が残っているが、さらに1つの記憶定数cの記憶空間を加える必要がある.下三角行列ではn(n+1)/2の位置で定数を格納する
特殊マトリクスの圧縮ストレージは実質的に2次元マトリクスの一部の要素をあるスキームに従って1次元配列に並べ、異なる配列スキームも異なるストレージスキームに対応する.
3、疎行列
よく見られるのは、三元群表現法、補助行ベクトル付き二元群表現法(すなわち、行論理チェーンテーブルの順序テーブル)、十字チェーンテーブル表現法などである.
三、ストレージ構造及びC言語の説明
1、三元グループ表示法
クイックシフト:a.dataの3元グループの順序でシフトし、シフト後の3元グループをb.dataの適切な位置に配置します.
適切な位置の決定:まず、M行列の各列(すなわち、Tの各行)における非0元の個数を計算し、次に、b.dataにおけるM行列の各列の最初の非0元の位置を求める.
トリプルグループ表示コード:
2行論理接続の順序表
上で論じたのは疎行列の回転であり,今では疎行列の乗算,加算,減算について論じた.疎行列ではないことがあらかじめ分かっていれば,2次元配列で乗算すればよい.もしそうであれば、マトリクスを格納するために使用される構造を行論理接続のシーケンステーブルと呼び、疎マトリクス内の各行の非ゼロ要素の三元グループテーブルの開始位置を記録するために行テーブルを追加します.
行論理リンク付きシーケンステーブル実装コード:
3,クロスチェーン表記
疎行列の三元群記憶方式の実現は簡単であり,各要素にはi,j,eの3つのドメインがあることを知った.ゼロ以外の行番号、列番号、および値を表します.では、クロスチェーンテーブルの格納方式では、まずこの3つのドメインが欠かせません.そうしないと、多くの操作を行うときに自分でカウンタを使うので、面倒です.クロスチェーンテーブルの形式は、各行がチェーンテーブルであり、各列がチェーンテーブルであることを理解することができます.図に示すように、
上記の図から,各ノードはi,j,eだけを格納する必要はないことが分かる.また、横方向の次のノードのアドレスと縦方向の次のノードのアドレスも格納されます.十字形のチェーンテーブルのような構造を形成します.各ノードの構造体定義も呼び出されます
これにより、ノードの挿入と削除に対して2つのポインタドメインを変更します.ノードの操作を容易にするために、ヘッダポインタまたはヘッダノードを作成します.ヘッドポインタを選択するか、ヘッドノードを選択するかは、引き続き見てください.
ヘッドポインタやヘッドノードを作成する方法を考えてみましょうOLNode構造のノードを作成して、ある行または列のノードを指す連続したアドレス空間を形成することができます.(これは私の最初の考えです)またはポインタ配列を作成します.配列要素に格納されているアドレスは、ある行または列の最初のノードのアドレスです.2つの方法の1つ目の方法を分析すると、ポインタ変数の空間は4バイトなので、比較的2つ目の節約空間が無駄になります.
2つ目は、ヘッドポインタの作成であることは間違いありません.では、2つ目は何で実現しますか?配列ですか、ダイナミックメモリ割り当てですか.配列を使用して行と列の最大値を事前に定義する場合は、これは良いアイデアではありませんが、動的メモリ割り当ての方法では、ユーザーが行数と列数を入力した後に、対応するアドレス連続の空間を割り当てることができます.より柔軟なので、動的メモリ割り当てを選択します.
注意RheadとCheadのタイプは、ポインタを指すポインタ、すなわち、我々が定義したOLNode構造のノードを指すポインタのポインタである.この話は少し回りくどいが、Cがよく勉強したと信じている友达はみな知っているはずだ.もし分からないならばこの招待状を见てくださいhttp://topic.csdn.net/u/20110829/01/506b33e3-ebc9-4905-bf8d-d0c877f85c08.html
構造体が定義されているので、次に何をすべきか考えてみましょう.まず,ユーザは,疎行列の行数と列数,および非ゼロ要素の個数を入力する必要がある.では、これらの値を格納するためにCrossListの構造体変数を定義する必要があります.
CreatSMatrix関数は、疎行列を作成し、クロスチェーンテーブルを使用して行列を格納するために今日作成する関数です.この関数の原型はint CreateSMatrix(CrossList*M)である.
Mを作成したらユーザー入力が必要になるので、ユーザーの入力をチェックして、要求に合っているかどうかを確認します.まずmu,nu,tuは0より小さくてはいけません.mu,nuは0に等しくありません(ここでは、行番号と列番号が1から始まると仮定しますので、0に等しくありません).tuの値は0とmu*nuの間でなければなりません.
ユーザーが正しい値を入力したら、ヘッダポインタの配列を作成します.
ここでm+1とn+1は、後の操作を容易にするために、それらの下付き文字を1から開始する.作成時の強制変換のタイプに注意してください.OLink*、まずポインタタイプです.m+1個を連続的に作成し、それぞれがOLinkタイプの変数を指すので、OLNodeタイプのポインタを指すアドレスが格納されているはずです.
作成後に初期化する必要があります.後の挿入は、NULLの値、すなわち行または列にノードがないことを判断するためです.
ノードの入力を行うことができます.入力するノードの数がt変数に格納されていることが明らかになりました.では、tノードを作成します.これが大きなサイクルです
ノードを作成するたびに、2つのポインタドメインとチェーンテーブルヘッダ配列を変更します.では、2回に分けて変更し、行のポインタドメインを1回目に変更し、列のポインタドメインを2回目に変更することができます.
ユーザーが正しい値を入力し、OLNodeタイプのノードも作成した後、ローに挿入することについて説明します.まず、どの行に挿入するかを確認します.私たちが入力したときに行番号iを入力しました.では、自然にi行に挿入します.では、どのように挿入すればいいですか.二つの状況に分ける
1、この行にノードがない場合は、直接挿入します.
2、この行にノードがある場合は正しい位置に挿入します
1つずつ分析:
どのようにして1行にノードがあるかどうかを判定しますか?私たちの前のRheadの初期化を覚えていますか?すべての要素の値はNULLなので、私たちの判断条件はNULL==M->Rhead[i]です.
2つ目の問題を解決しましょう
挿入する正しい位置をどうやって見つけますか.行にノードがある場合、私たちはあるノードの前または後に挿入することにほかならない.では、前に戻って、Rheadを定義したときに、ある行のヘッダーポインタがその行の最初のノードのアドレスを指していると言いました.行にノードがあると仮定してAノードと呼びますAノードの前に挿入すると、Aノードの列番号は必ず私たちが入力したノードより大きいです.(Pノードと呼びます)の列番号です.挿入操作は、ヘッダポインタとpノードのrightドメインを変更します.チェーンテーブルの挿入のように.行にノードがない場合はどうやって挿入しますか?ヘッダポインタを変更してPノードを指し、Pノードのrightドメインを変更します.if文を使用して、この2つの条件を実現できます.の判断を下す.では、次のコードがあります!
今、あるノードの後ろに挿入する方法を考えてみましょう.新しく作成したPノードを既存のAノードの後ろに挿入すると、Pの列番号は必ずAより大きい列番号になります.では、Pより大きい列番号の最初のノードBを見つけて、Bノードの前に挿入します.既存のノードにPノードより大きいカラム番号がない場合は、最後のノードの後に挿入する必要があります.まず条件に合った場所を探して挿入します
これで挿入が完了し、カラムのポインタドメインの変更はこれと似ています.すべてのコードを貼り付けます
転載先:https://www.cnblogs.com/buyizhiyou/p/5587888.html
1つの特殊な行列:行列には多くの数値が同じ要素、または非0要素が存在し、行列中の分布には一定の法則がある.
1.対称行列:行列中の要素が満足する
aij=aji 1≤i,j≤n
⒉三角行列:上(下)三角行列は、行列の下(上)三角(対角線を含まない)の要素が定数cまたは0のn次行列を指す.
3.対角行列(帯状行列):行列内のすべての非0要素が主対角線を中心とした領域に集中する.
二疎行列:非0元素が少なく(≦5%)、分布が不規則である.
二、ストレージ構造
1、対称行列
ストレージ割り当てポリシー:対称要素のペアに1つのストレージユニットのみが割り当てられます.すなわち、下三角(対角線を含む)の要素のみが格納されます.必要な空間数はn(n+1)/2です.
ストレージ割り当て方法:1次元配列sa[n(n+1)/2]をストレージ構造とする.
2、三角行列
n次方程式でもあり,上三角行列と下三角行列がある.下(上)三角行列は、主対角線以上(下)の要素がいずれもゼロのn次行列である.1次元配列sb[0..n(n+1)/2]をn次三角行列Bの記憶構造として、行別記憶方式を採用すると、Bのいずれかの要素bi,j,sb[k]の間には、上記のような対応関係が残っているが、さらに1つの記憶定数cの記憶空間を加える必要がある.下三角行列ではn(n+1)/2の位置で定数を格納する
特殊マトリクスの圧縮ストレージは実質的に2次元マトリクスの一部の要素をあるスキームに従って1次元配列に並べ、異なる配列スキームも異なるストレージスキームに対応する.
3、疎行列
よく見られるのは、三元群表現法、補助行ベクトル付き二元群表現法(すなわち、行論理チェーンテーブルの順序テーブル)、十字チェーンテーブル表現法などである.
三、ストレージ構造及びC言語の説明
1、三元グループ表示法
クイックシフト:a.dataの3元グループの順序でシフトし、シフト後の3元グループをb.dataの適切な位置に配置します.
適切な位置の決定:まず、M行列の各列(すなわち、Tの各行)における非0元の個数を計算し、次に、b.dataにおけるM行列の各列の最初の非0元の位置を求める.
トリプルグループ表示コード:
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 12500
#define OK 1
typedef int ElemType;
typedef struct
{
int i,j;
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int mu,nu,tu; // , 0
}TSMatrix;
int cpot[MAXSIZE+1],num[MAXSIZE+1];
int TransposeSMatrix(TSMatrix M,TSMatrix &T)
{
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
{
int q=1;
for(int col=1;col<=M.nu;++col)
for(int p=1;p<=M.tu;++p)
if(M.data[p].j==col)
{
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++q;
}//if
}//if
return OK;
}//TransposeSMatrix
int InPutM(TSMatrix &M)
{
printf("input nu mu tu(With a space interval)of a Matrix:
");
scanf("%d %d %d",&M.nu,&M.mu,&M.tu); //row,colume,and tu
printf("Please input the data of Matrix:
");
for(int c=1;c<=M.tu;c++)
{
scanf("%d",&M.data[c].i);
scanf("%d",&M.data[c].j);
scanf("%d",&M.data[c].e);
}//for
return 1;
}//InPut
int PrintM(TSMatrix T)
{
printf("Matrix after transpose is:
");
for(int c=1;c<=T.tu;c++)
{
printf("%d %d %d
",T.data[c].i,T.data[c].j,T.data[c].e);
}//for
return 1;
}//InPut
int FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{
T.mu=M.nu;
T.nu=M.mu;
T.tu=M.tu;
if(T.tu)
{
for(int col=1;col<=M.mu;++col) num[col]=0;
for(int t=1;t<=M.tu;++t) ++num[M.data[t].j]; // M.data[t].j
// 0
cpot[1]=1;
// col b.data(T)
for(int col=2;col<=M.mu;++col)
cpot[col]=cpot[col-1]+num[col-1];
for(int p=1;p<=M.tu;++p)
{
int col=M.data[p].j;
int q=cpot[col];
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++cpot[col];
}//for
}//if
return OK;
}//FastTransposeSMatrix
int main()
{
TSMatrix M,T;
InPutM(M);
//TransposeSMatrix(M,T);
FastTransposeSMatrix(M,T);
PrintM(T);
return OK;
}
2行論理接続の順序表
上で論じたのは疎行列の回転であり,今では疎行列の乗算,加算,減算について論じた.疎行列ではないことがあらかじめ分かっていれば,2次元配列で乗算すればよい.もしそうであれば、マトリクスを格納するために使用される構造を行論理接続のシーケンステーブルと呼び、疎マトリクス内の各行の非ゼロ要素の三元グループテーブルの開始位置を記録するために行テーブルを追加します.
行論理リンク付きシーケンステーブル実装コード:
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 12500
#define MAXRC 100
#define OK 1
#define ERROR -1
typedef int ElemType;
typedef int Status;
typedef struct
{
int i,j;
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1];
int rpos[MAXRC+1];//
int mu,nu,tu; // , 0
}RLSMatrix;
int cpot[MAXSIZE+1],num[MAXSIZE+1];
Status CreateSMatrix(RLSMatrix &M)
{ // M
int i;
Triple T;
Status k;
printf(" , , :(Separated by commas)
");
scanf("%d,%d,%d",&M.mu,&M.nu,&M.tu);
M.data[0].i=0; //
for(i=1;i<=M.tu;i++)
{
do
{
printf(" %d (1~%d), (1~%d), :",i,M.mu,M.nu);
printf("the 3 num Separated by commas
");
scanf("%d,%d,%d",&T.i,&T.j,&T.e);
k=0;
if(T.i<1||T.i>M.mu||T.j<1||T.j>M.nu) // 、
k=1;
if(T.iM.data[i-1].i)
for(T.i=0;T.iMAXSIZE)
return ERROR;
Q.data[Q.tu].i=arow;
Q.data[Q.tu].j=ccol;
Q.data[Q.tu].e=ctemp[ccol];
}//if
}//for
}//if
return OK;
}//MultSMatrix
int main()
{
RLSMatrix M,N,Q;
CreateSMatrix(M);
CreateSMatrix(N);
MultSMatrix(M,N,Q);
PrintSMatrix(Q);
DestroySMatrix(M);
DestroySMatrix(N);
DestroySMatrix(Q);
return OK;
}
3,クロスチェーン表記
疎行列の三元群記憶方式の実現は簡単であり,各要素にはi,j,eの3つのドメインがあることを知った.ゼロ以外の行番号、列番号、および値を表します.では、クロスチェーンテーブルの格納方式では、まずこの3つのドメインが欠かせません.そうしないと、多くの操作を行うときに自分でカウンタを使うので、面倒です.クロスチェーンテーブルの形式は、各行がチェーンテーブルであり、各列がチェーンテーブルであることを理解することができます.図に示すように、
上記の図から,各ノードはi,j,eだけを格納する必要はないことが分かる.また、横方向の次のノードのアドレスと縦方向の次のノードのアドレスも格納されます.十字形のチェーンテーブルのような構造を形成します.各ノードの構造体定義も呼び出されます
1 typedef struct OLNode {
2 int i, j; //
3 ElemType e; //
4 struct OLNode *right, *down; //
5 }OLNode, *OList;
これにより、ノードの挿入と削除に対して2つのポインタドメインを変更します.ノードの操作を容易にするために、ヘッダポインタまたはヘッダノードを作成します.ヘッドポインタを選択するか、ヘッドノードを選択するかは、引き続き見てください.
ヘッドポインタやヘッドノードを作成する方法を考えてみましょうOLNode構造のノードを作成して、ある行または列のノードを指す連続したアドレス空間を形成することができます.(これは私の最初の考えです)またはポインタ配列を作成します.配列要素に格納されているアドレスは、ある行または列の最初のノードのアドレスです.2つの方法の1つ目の方法を分析すると、ポインタ変数の空間は4バイトなので、比較的2つ目の節約空間が無駄になります.
2つ目は、ヘッドポインタの作成であることは間違いありません.では、2つ目は何で実現しますか?配列ですか、ダイナミックメモリ割り当てですか.配列を使用して行と列の最大値を事前に定義する場合は、これは良いアイデアではありませんが、動的メモリ割り当ての方法では、ユーザーが行数と列数を入力した後に、対応するアドレス連続の空間を割り当てることができます.より柔軟なので、動的メモリ割り当てを選択します.
typedef struct {
OLink *Rhead, *Chead;
int mu, nu, tu; // 、
}CrossList;
注意RheadとCheadのタイプは、ポインタを指すポインタ、すなわち、我々が定義したOLNode構造のノードを指すポインタのポインタである.この話は少し回りくどいが、Cがよく勉強したと信じている友达はみな知っているはずだ.もし分からないならばこの招待状を见てくださいhttp://topic.csdn.net/u/20110829/01/506b33e3-ebc9-4905-bf8d-d0c877f85c08.html
構造体が定義されているので、次に何をすべきか考えてみましょう.まず,ユーザは,疎行列の行数と列数,および非ゼロ要素の個数を入力する必要がある.では、これらの値を格納するためにCrossListの構造体変数を定義する必要があります.
int main(void)
{
CrossList M;
CreateSMatrix(&M);
}
CreatSMatrix関数は、疎行列を作成し、クロスチェーンテーブルを使用して行列を格納するために今日作成する関数です.この関数の原型はint CreateSMatrix(CrossList*M)である.
Mを作成したらユーザー入力が必要になるので、ユーザーの入力をチェックして、要求に合っているかどうかを確認します.まずmu,nu,tuは0より小さくてはいけません.mu,nuは0に等しくありません(ここでは、行番号と列番号が1から始まると仮定しますので、0に等しくありません).tuの値は0とmu*nuの間でなければなりません.
int CreateSMatrix(CrossList *M)
{
int i, j, m, n, t;
int k, flag;
ElemType e;
OLNode *p, *q;
if (M->Rhead)
DestroySMatrix(M);
do {
flag = 1;
printf(" 、 ");
scanf("%d%d%d", &m, &n, &t);
if (m<0 || n<0 || t<0 || t>m*n)
flag = 0;
}while (!flag);
M->mu = m;
M->nu = n;
M->tu = t;
...................................
return 1;
}
ユーザーが正しい値を入力したら、ヘッダポインタの配列を作成します.
//
M->Rhead = (OLink *)malloc((m+1) * sizeof(OLink));
if(!M->Rhead)
exit(-1);
//
M->Chead = (OLink *)malloc((n+1) * sizeof(OLink));
if(!(M->Chead))
exit(-1);
ここでm+1とn+1は、後の操作を容易にするために、それらの下付き文字を1から開始する.作成時の強制変換のタイプに注意してください.OLink*、まずポインタタイプです.m+1個を連続的に作成し、それぞれがOLinkタイプの変数を指すので、OLNodeタイプのポインタを指すアドレスが格納されているはずです.
作成後に初期化する必要があります.後の挿入は、NULLの値、すなわち行または列にノードがないことを判断するためです.
for(k=1;k<=m;k++) // ;
M->Rhead[k]=NULL;
for(k=1;k<=n;k++) // ;
M->Chead[k]=NULL;
ノードの入力を行うことができます.入力するノードの数がt変数に格納されていることが明らかになりました.では、tノードを作成します.これが大きなサイクルです
ノードを作成するたびに、2つのポインタドメインとチェーンテーブルヘッダ配列を変更します.では、2回に分けて変更し、行のポインタドメインを1回目に変更し、列のポインタドメインを2回目に変更することができます.
do {
flag = 1;
printf(" %d 、 ", k);
scanf("%d%d%d", &i, &j, &e);
if (i<=0 || j<=0)
flag = 0;
}while (!flag);
p = (OLink) malloc (sizeof(OLNode));
if (NULL == p)
exit(-1);
p->i = i;
p->j = j;
p->e = e;
ユーザーが正しい値を入力し、OLNodeタイプのノードも作成した後、ローに挿入することについて説明します.まず、どの行に挿入するかを確認します.私たちが入力したときに行番号iを入力しました.では、自然にi行に挿入します.では、どのように挿入すればいいですか.二つの状況に分ける
1、この行にノードがない場合は、直接挿入します.
2、この行にノードがある場合は正しい位置に挿入します
1つずつ分析:
どのようにして1行にノードがあるかどうかを判定しますか?私たちの前のRheadの初期化を覚えていますか?すべての要素の値はNULLなので、私たちの判断条件はNULL==M->Rhead[i]です.
2つ目の問題を解決しましょう
挿入する正しい位置をどうやって見つけますか.行にノードがある場合、私たちはあるノードの前または後に挿入することにほかならない.では、前に戻って、Rheadを定義したときに、ある行のヘッダーポインタがその行の最初のノードのアドレスを指していると言いました.行にノードがあると仮定してAノードと呼びますAノードの前に挿入すると、Aノードの列番号は必ず私たちが入力したノードより大きいです.(Pノードと呼びます)の列番号です.挿入操作は、ヘッダポインタとpノードのrightドメインを変更します.チェーンテーブルの挿入のように.行にノードがない場合はどうやって挿入しますか?ヘッダポインタを変更してPノードを指し、Pノードのrightドメインを変更します.if文を使用して、この2つの条件を実現できます.の判断を下す.では、次のコードがあります!
if(NULL==M->Rhead[i] || M->Rhead[i]->j>j)
{
// p
// M->Rhead[i] p->right = M->Rhead[i];
M->Rhead[i] = p;
}
今、あるノードの後ろに挿入する方法を考えてみましょう.新しく作成したPノードを既存のAノードの後ろに挿入すると、Pの列番号は必ずAより大きい列番号になります.では、Pより大きい列番号の最初のノードBを見つけて、Bノードの前に挿入します.既存のノードにPノードより大きいカラム番号がない場合は、最後のノードの後に挿入する必要があります.まず条件に合った場所を探して挿入します
for(q=M->Rhead[i]; q->right && q->right->j < j; q=q->right)
;
p->right=q->right; //
q->right=p;
これで挿入が完了し、カラムのポインタドメインの変更はこれと似ています.すべてのコードを貼り付けます
int CreateSMatrix(CrossList *M)
{
int i, j, m, n, t;
int k, flag;
ElemType e;
OLNode *p, *q;
if (M->Rhead)
DestroySMatrix(M); do {
flag = 1;
printf(" 、 ");
scanf("%d%d%d", &m, &n, &t);
if (m<0 || n<0 || t<0 || t>m*n)
flag = 0;
}while (!flag);
M->mu = m;
M->nu = n;
M->tu = t;
//
M->Rhead = (OLink *)malloc((m+1) * sizeof(OLink));
if(!M->Rhead)
exit(-1);
//
M->Chead = (OLink *)malloc((n+1) * sizeof(OLink));
if(!(M->Chead))
exit(-1);
for(k=1;k<=m;k++) // ;
M->Rhead[k]=NULL;
for(k=1;k<=n;k++) // ;
M->Chead[k]=NULL;
//
for (k=1; k<=t; ++k)
{
do {
flag = 1;
printf(" %d 、 ", k);
scanf("%d%d%d", &i, &j, &e);
if (i<=0 || j<=0)
flag = 0;
}while (!flag); p = (OLink) malloc (sizeof(OLNode));
if (NULL == p)
exit(-1);
p->i = i;
p->j = j;
p->e = e;
if(NULL==M->Rhead[i] || M->Rhead[i]->j>j)
{
// p
// M->Rhead[i]
p->right = M->Rhead[i];
M->Rhead[i] = p;
}
else //
{
// ,
for(q=M->Rhead[i]; q->right && q->right->j < j; q=q->right)
;
p->right=q->right; //
q->right=p;
} if(NULL==M->Chead[j] || M->Chead[j]->i>i)
{
p->down = M->Chead[j];
M->Chead[j] = p;
}
else //
{
// ,
for(q=M->Chead[j]; q->down && q->down->i < i; q=q->down)
;
p->down=q->down; //
q->down=p;
}
} return 1;
}
転載先:https://www.cnblogs.com/buyizhiyou/p/5587888.html