A. c語言 三元組 問題
//三元組表示稀疏矩陣
#include<stdio.h>
#define N 1000
typedef struct Elem
{
int i,j;
int e;
} ELEM; /* 表示一個元素的三元組結構 */
void main()
{
ELEM mat[N];
int row,col; /* 行列數 */
int i,j,k=0,n;
int x;
char fn[]="data.txt";
FILE *pf=fopen(fn,"r");
if(!pf){
printf("Error: Can't open the file: %s\n",fn);
return;
}
fscanf(pf,"%d%d",&row,&col); /* 讀取行列數 */
/* 讀取矩陣數據，並存入三元組 */
for(i=0; i<row; i++)
for(j=0; j<col; j++){
fscanf(pf,"%d",&x);
if(x!=0){
mat[k].e=x;
mat[k].i=i;
mat[k].j=j;
if(k%5==0) printf("\n");
k++;
printf("[%2d][%2d]=%3d ",i,j,x);
}
}
printf("\n");
fclose(pf);
n=k; k=0;
/* 將給定的一個三元組（就用前面得到的這個三元組），輸出稀疏矩陣 */
for(i=0; i<row; i++){
for(j=0; j<col; j++){
if(mat[k].i==i && mat[k].j==j){
printf("%3d ",mat[k].e);
k++;
}else
printf("%3d ",0);
}
printf("\n");
}
printf("\n");
}
/*
注意，為了便於測試，將一個稀疏矩陣保存於數據文件data.txt中（該文件放在源程序所在的目錄中），文件的內容如下：
第一行兩個數據（數據間用空格分隔）：r c（分別表示矩陣行數和列數）
接下來是矩陣的數據，共有r行，每行c個數據。例如：
10 10
0 0 0 0 0 1 0 0 0 1
2 0 0 0 1 0 0 0 0 0
0 3 0 0 0 0 0 1 0 0
0 0 0 0 0 0 4 0 0 0
0 0 5 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 1
2 0 0 0 1 0 0 0 0 0
0 3 0 0 0 0 0 1 0 0
0 0 0 0 0 0 4 0 0 0
0 0 5 0 0 0 0 0 1 0
*/
B. C語言課程設計：稀疏矩陣應用 要求：實現三元組，十字鏈表下的稀疏矩陣的加、轉、乘的實現。
我剛寫了一個稀疏矩陣的代碼，如下
#include <iostream>
#include <iomanip>
using namespace std;
template<class T>
//三元組
struct Trituple
{
int row;
int col;
T val;
};
//稀疏矩陣聲明
template<class T>
class SparseMatrix
{
public:
SparseMatrix(int maxt=100);
~SparseMatrix();
bool TransposeTo(SparseMatrix &);
bool AddTo(const SparseMatrix&);
bool TransposeTo_Faster(SparseMatrix&);
void Input();
void Output();
private:
Trituple<T>* data;
int rows,cols,terms;
int maxterms;
};
template<class T>
SparseMatrix<T>::SparseMatrix(int maxt)
{
maxterms=maxt;
data=new Trituple<T>[maxterms];
terms=rows=cols=0;
}
template<class T>
SparseMatrix<T>::~SparseMatrix()
{
if (data!=NULL)
{
delete[] data;
}
}
//普通轉置
template<class T>
bool SparseMatrix<T>::TransposeTo(SparseMatrix &B)
{
if (terms>B.maxterms)
{
return false;
}
B.rows=cols;
B.cols=rows;
B.terms=terms;
if (terms>0)
{
int p=0;
for (int j=1;j<=cols;j++)
{
for (int k=0;k<terms;k++)
{
if (data[k].col==j)
{
B.data[p].row=j;
B.data[p].col=data[k].row;
B.data[p].val=data[k].val;
p++;
}
}
}
}
return true;
}
//快速轉置
template<class T>
bool SparseMatrix<T>::TransposeTo_Faster(SparseMatrix& B)
{
if (terms>B.maxterms)
{
return false;
}
B.rows=cols;
B.cols=rows;
B.terms=terms;
if (terms>0)
{
int *num,*cpot;
num=new int[cols];
cpot=new int[cols];
for (int j=0;j<cols;j++)
{
num[j]=0;
}
for (int k=0;k<terms;k++)
{
num[data[k].col-1]++;
}
//求出B中每一行的起始下標cpot[]
cpot[0]=0;
for (int j=1;j<cols;j++)
{
cpot[j]=cpot[j-1]+num[j-1];
}
//執行轉置操作
for (int p,k=0;k<terms;k++)
{
p=cpot[data[k].col-1]++;
B.data[p].row=data[k].col;
B.data[p].col=data[k].row;
B.data[p].val=data[k].val;
}
delete[] num;
delete[] cpot;
}
return true;
}
template<class T>
void SparseMatrix<T>::Input()
{
cout<<"intput the matrix' row:";
int row1;
cin>>row1;
cout<<"intput the matrix' col:";
int col1;
cin>>col1;
cout<<"input "<<row1<<"*"<<col1<<" matrix"<<endl;
int number;
rows=row1;
cols=col1;
for (int i=0;i<rows;i++)
{
for (int j=0;j<cols;j++)
{
cin>>number;
if (number!=0)
{
data[terms].row=i+1;
data[terms].col=j+1;
data[terms].val=number;
terms++;
}
}
}
}
template<class T> //輸出好看，但是違背了最初的原則
void SparseMatrix<T>::Output()
{
T **tempArray=new T*[rows];
for (int i1=0;i1<rows;i1++)
{
tempArray[i1]=new int[cols];
}
for (int j=0;j<rows;j++)
{
for (int k=0;k<cols;k++)
{
tempArray[j][k]=0;
}
}
for (int i=0;i<terms;i++)
{
tempArray[data[i].row-1][data[i].col-1]=data[i].val;
}
for (int j=0;j<rows;j++)
{
for (int k=0;k<cols;k++)
{
cout<<setw(4)<<tempArray[j][k];
}
cout<<endl;
}
for (int l=0;l<rows;l++)
{
delete[] tempArray[l];
}
delete tempArray;
cout<<endl;
}
template<class T>
bool SparseMatrix<T>::AddTo(const SparseMatrix& B)
{
if (rows!=B.rows||cols!=B.cols)
{
return false;
}
bool flag=false;
int tempTerms=terms;
for (int i=0;i<B.terms;i++)
{
flag=false;
for (int j=0;j<tempTerms;j++)
{
if (data[j].col==B.data[i].col&&data[j].row==B.data[i].row)
{
data[j].val+=B.data[i].val;
flag=true;
}
}
if (flag==false)
{
data[++terms-1].col=B.data[i].col; //數組下標操作注意事項
data[terms-1].row=B.data[i].row;
data[terms-1].val=B.data[i].val;
}
}
return true;
}
int main()
{
cout<<"此程序演示稀疏矩陣的普通轉置和快速轉置操作"<<endl;
SparseMatrix<int> sm(50);
SparseMatrix<int> sm1(50);
SparseMatrix<int> sm2(50);
sm.Input();
cout<<"sm is"<<endl;
sm.Output();
sm.TransposeTo(sm1);
cout<<"Transposition of sm is "<<endl;
sm1.Output();
sm.TransposeTo_Faster(sm2);
cout<<"Transposition of sm is "<<endl;
sm2.Output();
SparseMatrix<int> sm3;
cout<<"input a new matrix"<<endl;
sm3.Input();
cout<<"sm3 is"<<endl;
sm3.Output();
if(sm.AddTo(sm3))
{
cout<<"after adding sm3 ,sm is"<<endl;
sm.Output();
}
else
cout<<"the two matrix can't add"<<endl;
cout<<"Good job!"<<endl;
system("pause");
return 0;
}
C. 誰能給我講講C語言中的三元運算符是怎麼回事
在C裡面只有一個三元運算符，型如a>b ？a：b 裡面有兩個符號，先是問號，再一個冒號，意思是，先判斷a>b，如果為真（值為1），則反回a,如果為假（值為0），既a<b,反回b.依你題目，char sex=getch();while(sex=='0' || sex=='1'){printf ("you are %s\n", (xb == '1')? "boy":"girl");}
D. c語言中三元運算符有哪些
c語言中只有一種三元運算符。
它就是「問號運算符」。
它的語法形式是：
表達式一？表達式二：表達式三
表達式一是一個數學表達式、關系表達式或邏輯表達式，它的邏輯值作為下一步運行的選擇：當邏輯值為真時，運行表達式二並返回表達式二的值；當邏輯值為假時，運行表達式三並返回表達式三的值。舉個例子：
x=3>2？8:100;
執行後，x=8。
E. c語言數據結構（考題，測試你的能力）－－編寫源代碼
P88 稀疏矩陣十字鏈表相加演算法如下：
/*假設ha為A稀疏矩陣十字鏈表的頭指針，hb為B稀疏矩陣十字鏈表的頭指針*/
#include<stdio.h>
#define maxsize 100
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext
{ int v;
struct linknode *next;} k;
};
struct linknode creatlindmat( ) /*建立十字鏈表*/
{ int x, m, n, t, s, i, j, k;
struct linknode *p , *q, *cp[maxsize],*hm;
printf("請輸入稀疏矩陣的行、列數及非零元個數\n");
scanf("%d%d%d",&m,&n,&t);
if (m>n) s=m; else s=n;
hm=(struct linknode*)malloc(sizeof(struct linknode)) ;
hm->i=m; hm->j=n;
cp[0]=hm;
for (i=1; i<=s;i++)
{ p=(struct linknode*)malloc(sizeof(struct linknode)) ;
p->i=0; p->j=0;
p->rptr=p; p->cptr=p;
cp[i]=p;
cp[i-1]->k.next=p;
}
cp[s]->k.next=hm;
for( x=1;x<=t;x++)
{ printf("請輸入一個三元組(i,j,v)\n");
scanf("%d%d%d",&i,&j,&k);
p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=i; p->j=j; p->k.v=k;
/*以下是將p插入到第i行鏈表中 */
q=cp[i];
while ((q->rptr!=cp[i]) &&( q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
/*以下是將P插入到第j列鏈表中*/
q=cp[j];
while((q->cptr!=cp[j]) &&( q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
}
return hm;
}
/* ha和hb表示的兩個稀疏矩陣相加，相加的結果放入ha中*/
struct linknode *matadd(struct linknode *ha, struct linknode *hb)
{ struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q;
struct linknode *hl[maxsize];
int i , j, n;
if((ha->i!=hb->i)||(ha->j!=hb->j))
printf("矩陣不匹配,不能相加\n");
else
{ p=ha->k.next; n=ha->j;
for (i=1;i<=n; i++)
{ hl[i]=p;
p=p->k.next;
}
ca=ha->k.next; cb=hb->k.next;
while(ca->i==0)
{pa=ca->rptr; pb=cb->rptr;
qa=ca;
while(pb->j!=0)
{ if((pa->j<pb->j)&&(pa->j!=0))
{ qa=pa; pa=pa->rptr;}
else if ((pa->j>pb->j)||(pa->j==0)) /*插入一個結點*/
{ p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=pb->i; p->j=pb->j;
p->k.v=pb->k.v;
qa->rptr=p; p->rptr=pa;
qa=p; pb=pb->rptr;
j=p->j; q=hl[j]->cptr;
while((q->i<p->i)&&(q->i!=0))
{ hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=p; p->cptr=q;
hl[j]=p;
}
else
{pa->k.v=pa->k.v+pb->k.v;
if(pa->k.v==0) /*刪除一個結點*/
{ qa->rptr=pa->rptr;
j=pa->j; q=hl[j]->cptr;
while (q->i<pa->i)
{hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=q->cptr;
pa=pa->rptr; pb=pb->rptr;
free(q);
}
else
{ qa=pa; pa=pa->rptr;
pb=pb->rptr;
}
}
}
ca=ca->k.next; cb=cb->k.next;
}
}
return ha;
}
void print(struct linknode *ha) /*輸出十字鏈表*/
{ struct linknode *p,*q;
p=ha->k.next;
while(p->k.next!=ha)
{ q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
p=p->k.next;
}
q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
}
void main()
{
struct linknode *ha=NULL,*hb=NULL,*hc=NULL;
ha=creatlindmat( ); /*生成一個十字鏈表ha*/
hb=creatlindmat( ); /*生成另一個十字鏈表hb*/
printf("A:\n"); /*輸出十字鏈表ha*/
print(ha);printf("\n");
printf("B:\n"); /*輸出十字鏈表hb*/
print(hb);printf("\n");
hc=matadd(ha,hb); /*十字鏈表相加*/
printf("A+B:\n"); /*輸出相加後的結果*/
print(hc);printf("\n");
}
P94 數據類型描述如下：
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
}
P95 數據類型描述如下：
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}
P96 求廣義表的深度depth(LS)
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
P96 廣義表的建立creat(LS)
void creat(struct node1 *LS)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node*)malloc(sizeof(struct node));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node*)malloc(sizeof(struct node));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
P97 輸出廣義表print(LS)
void print(struct node1 *LS)
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c ",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
P98 該演算法的時間復雜度為O(n)。整個完整程序如下：
#include<stdio.h>
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
};
void creat(struct node1 LS) /*建立廣義表的單鏈表*/
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
void print(struct node1 LS) /*輸出廣義單鏈表*/
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
int depth(struct node1 LS) /*求廣義表的深度*/
{
int max=0;
while(LS!=NULL)
{ if(LS->atom==0)
{ int dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
main()
{ int dep;
struct node1 *p=NULL;
creat(p); /*建立廣義表的單鏈表*/
print(p); /*輸出廣義單鏈表*/
dep=depth(p); /*求廣義表的深度*/
printf("%d\n",dep);
}
第六章 樹
P109 二叉鏈表的結點類型定義如下：
typedef struct btnode
{ anytype data;
struct btnode *Lch,*Rch;
}tnodetype;
P109 三叉鏈表的結點類型定義如下：
typedef struct btnode3
{ anytype data;
struct btnode *Lch,*Rch，*Parent ;
}tnodetype3;
P112 C語言的先序遍歷演算法：
void preorder (tnodetype *t)
/*先序遍歷二叉樹演算法，t為指向根結點的指針*/
{ if (t!=NULL)
{printf("%d ",t->data);
preorder(t->lch);
preorder(t->rch);
}
}
P113 C語言的中序遍歷演算法：
void inorder(tnodetype *t)
/*中序遍歷二叉樹演算法，t為指向根結點的指針*/
{
if(t!=NULL)
{inorder(t->lch);
printf("%d ",t->data);
inorder(t->rch);
}
}
P113 C語言的後序遍歷演算法：
void postorder(tnodetype *t)
/*後序遍歷二叉樹演算法，t為指向根結點的指針*/
{
if(t!=NULL)
{ postorder(t->lch);
postorder(t->rch);
printf("%d ",t->data);
}
}
P114 如果引入隊列作為輔助存儲工具，按層次遍歷二叉樹的演算法可描述如下：
void levelorder(tnodetype *t)
/*按層次遍歷二叉樹演算法，t為指向根結點的指針*/
{tnodetype q[20]; /*輔助隊列*/
front=0;
rear=0; /*置空隊列*/
if (t!=NULL)
{ rear++;
q[rear]=t; /*根結點入隊*/
}
while (front!=rear)
{ front++;
t=q [front];
printf ("%c\n",t->data);
if (t->lch!=NULL) /*t的左孩子不空，則入隊*/
{ rear++;
q [rear]=t->lch;
}
if (t->rch!=NULL) /*t的右孩子不空，則入隊*/
{ rear++;
q [rear]=t->rch;
}
}
}
P115 以中序遍歷的方法統計二叉樹中的結點數和葉子結點數，演算法描述為：
void inordercount (tnodetype *t)
/*中序遍歷二叉樹，統計樹中的結點數和葉子結點數*/
{ if (t!=NULL)
{ inordercount (t->lch); /*中序遍歷左子樹*/
printf ("%c\n",t->data); /*訪問根結點*/
countnode++; /*結點計數*/
if ((t->lch==NULL)&&(t->rch==NULL))
countleaf++; /*葉子結點計數*/
inordercount (t->rch); /*中序遍歷右子樹*/
}
}
P115 可按如下方法計算一棵二叉樹的深度：
void preorderdeep (tnodetype *t,int j)
/*先序遍歷二叉樹，並計算二叉樹的深度*/
{ if (t!=NULL)
{ printf ("%c\n",t->data); /*訪問根結點*/
j++;
if (k<j) k=j;
preorderdeep (t->lch,j); /*先序遍歷左子樹*/
preorderdeep (t->rch,j); /*先序遍歷右子樹*/
}
}
P117 線索二叉樹的結點類型定義如下：
struct nodexs
{anytype data;
struct nodexs *lch, *rch;
int ltag,rtag; /*左、右標志域*/
}
P117 中序次序線索化演算法
void inorderxs (struct nodexs *t)
/*中序遍歷t所指向的二叉樹，並為結點建立線索*/
{ if (t!=NULL)
{ inorderxs (t->lch);
printf ("%c\n",t->data);
if (t->lch!=NULL)
t->ltag=0;
else { t->ltag=1;
t->lch=pr;
} /*建立t所指向結點的左線索，令其指向前驅結點pr*/
if (pr!=NULL)
{ if (pr->rch!=NULL)
pr->rtag=0;
else { pr->rtag=1;
pr->rch=p;
}
} /*建立pr所指向結點的右線索，令其指向後繼結點p*/
pr=p;
inorderxs (t->rch);
}
}
P118 在中根線索樹上檢索某結點的前驅結點的演算法描述如下：
struct nodexs * inpre (struct nodexs *q)
/*在中根線索樹上檢索q所指向的結點的前驅結點*/
{ if (q->ltag==1)
p=q->lch;
else { r=q->lch;
while (r->rtag!=1)
r=r->rch;
p=r;
}
return (p);
}
P119 在中根線索樹上檢索某結點的後繼結點的演算法描述如下：
struct nodexs * insucc (struct nodexs *q)
/*在中根線索樹上檢索q所指向的結點的後繼結點*/
{ if (q->rtag==1)
p=q->rch;
else { r=q->rch;
while (r->ltag!=1)
r=r->lch;
p=r;
}
return (p);
}
P120 演算法程序用C語言描述如下：
void sortBT(BT *t,BT *s) /*將指針s所指的結點插入到以t為根指針的二叉樹中*/
{ if (t==NULL) t=s; /*若t所指為空樹，s所指結點為根*/
else if (s->data < t->data)
sortBT(t->lch,s); /*s結點插入到t的左子樹上去*/
else
sortBT(t->rch,s); /*s結點插入到t的右子樹上去*/
}
P121 二叉排序樹結點刪除演算法的C語言描述如下：
void delnode(bt,f,p)
/*bt為一棵二叉排序樹的根指針，p指向被刪除結點，f指向其雙親*/
/*當p=bt時f為NULL*/
{ fag=0; /*fag=0時需修改f指針信息，fag=1時不需修改*/
if (p->lch==NULL)
s=p->rch; /*被刪除結點為葉子或其左子樹為空*/
else if (p->rch==NULL)
s=p->lch;
else { q=p; /*被刪除結點的左、右子樹均非空*/
s=p->lch;
while (s->rch!=NULL)
{ q=s;
s=s->rch;
} /*尋找s結點*/
if (q=p)
q->lch=s->lch;
else q->rch=s->lch;
p->data=s->data; /*s所指向的結點代替被刪除結點*/
DISPOSE(s);
Fag=1;
}
if (fag=0) /*需要修改雙親指針*/
{ if (f=NULL)
bt=s; /*被刪除結點為根結點*/
else if (f->lch=p)
f->lch=s;
else f->rch=s;
DISPOSE(p); /*釋放被刪除結點*/
}
}
第七章 圖
P134 用鄰接矩陣表示法表示圖，除了存儲用於表示頂點間相鄰關系的鄰接矩陣外，通常還需要用一個順序表來存儲頂點信息。其形式說明如下：
# define n 6 /*圖的頂點數*/
# define e 8 /*圖的邊(弧)數*/
typedef char vextype; /*頂點的數據類型*/
typedef float adjtype; /*權值類型*/
typedef struct
{vextype vexs[n];
adjtype arcs[n][n];
}graph;
P135 建立一個無向網路的演算法。
CREATGRAPH(ga) /*建立無向網路*/
Graph * ga;
{
int i,j,k;
float w;
for(i＝0;i<n;i++ )
ga ->vexs[i]＝getchar(); /*讀入頂點信息，建立頂點表*/
for(i＝0;i<n;i++ )
for(j＝0;j<n;j++)
ga ->arcs[i][j]＝0; /*鄰接矩陣初始化*/
for(k＝0;k<e;k++) /*讀入e條邊*/
(scanf("％d％d％f",&I,&j,&w); /*讀入邊(vi,vj)上的權w */
ga ->arcs[i][j]＝w;
ga - >arcs[j][i]＝w;
}
} /*CREATGRAPH*/
P136 鄰接表的形式說明及其建立演算法：
typedef struct node
{int adjvex; /*鄰接點域*/
struct node * next; /*鏈域*/
}edgenode; /*邊表結點*/
typedef struct
{vextype vertex; /*頂點信息*/
edgenode link; /*邊表頭指針*/
}vexnode; /*頂點表結點*/
vexnode ga[n];
CREATADJLIST(ga) /*建立無向圖的鄰接表*/
Vexnode ga[ ];
{int i,j,k;
edgenode * s;
for(i=o;i<n;i++＝ /*讀入頂點信息*/
(ga[i].vertex＝getchar();
ga[i].1ink＝NULL; /*邊表頭指針初始化*/
}
for(k＝0;k<e;k++＝ /*建立邊表*/
{scanf("％d％d",&i,&j); /*讀入邊(vi , vj)的頂點對序號*/
s＝malloc(sizeof(edgenode)); /*生成鄰接點序號為j的表結點*s */
s-> adjvex＝j;
s- - >next：＝ga[i].Link;
ga[i].1ink＝s; /*將*s插入頂點vi的邊表頭部*/
s＝malloc(size0f(edgende)); /*生成鄰接點序號為i的邊表結點*s */
s ->adjvex＝i;
s ->next＝ga[j].1ink;
ga[j].1ink＝s; /*將*s插入頂點vj的邊表頭部*/
}
} /* CREATADJLIST */
P139 分別以鄰接矩陣和鄰接表作為圖的存儲結構給出具體演算法，演算法中g、g1和visited為全程量，visited的各分量初始值均為FALSE。
int visited[n] /*定義布爾向量visitd為全程量*/
Graph g; /*圖g為全程量*/
DFS(i) /*從Vi+1出發深度優先搜索圖g，g用鄰接矩陣表示*/
int i;
{ int j;
printf("node：％c＼n" , g.vexs[i]); /*訪問出發點vi+1 */
Visited[i]＝TRUE; /*標記vi+l已訪問過*/
for (j＝0;j<n;j++) /*依次搜索vi+1的鄰接點*/
if((g.arcs[i][j]＝＝1) ＆＆(! visited[j]))
DFS(j); /*若Vi+l的鄰接點vj+l未曾訪問過，則從vj+l出發進行深度優先搜索*/
} /*DFS*/
vexnode gl[n] /*鄰接表全程量*/
DFSL(i) /*從vi+l出發深度優先搜索圖g1，g1用鄰接表表示*/
int i;
{ int j;
edgenode * p;
printf("node：％C\n" ,g1[i].vertex);
vistited[i]＝TRUE;
p＝g1[i].1ink; /*取vi+1的邊表頭指針*/
while(p !＝NULL) /*依次搜索vi+l的鄰接點*/
{
if(! Vistited[p ->adjvex])
DFSL(p - >adjvex); /*從vi+1的未曾訪問過的鄰接點出發進行深度優先搜索*/
p＝p - >next; /*找vi+l的下一個鄰接點*/
}
} /* DFSL */
P142 以鄰接矩陣和鄰接表作為圖的存儲結構，分別給出寬度優先搜索演算法。
BFS(k) /＊從vk+l出發寬度優先搜索圖g，g用鄰接矩陣表示，visited為訪問標志向量*/
int k;
{ int i,j;
SETNULL(Q); /*置空隊Q */
printf("％c＼n"，g.vexs[k]); /*訪問出發點vk+l*x/
visited[k]＝TRUE; /*標記vk+l已訪問過*/
ENQUEUE(Q，K); /*已訪問過的頂點(序號)入隊列*/
While(!EMPTY(Q)) /*隊非空時執行*/
{i＝DEQUEUE(Q); /*隊頭元素序號出隊列*/
for(j＝0;j<n;j++)
if((g.arcs[i][j]＝＝1)＆＆(! visited[j]))
{printf("％c＼n" , g.vexs[j]); /*訪問vi+l的未曾訪問的鄰接點vj+l */
visited[j]＝TRUE;
ENQUEUE(Q,j); /*訪問過的頂點入隊*/
}
}
} /* BFS */
BFSL(k) /*從vk+l出發寬度優先搜索圖g1，g1用鄰接表表示*/
int k
{ int i;
edgenode * p;
SETNULL(Q);
printf("％c＼n" , g1[k].vertex);
visited[k]＝TRUE;
ENQUEUE(Q,k);
while(! EMPTY(Q));
{ i＝DEQUEUE(Q);
p＝g1[i].1ink /*取vi+l的邊表頭指針*/
while(p !＝NULL) /*依次搜索vi+l的鄰接點*/
{ if( ! visited[p - >adjvex]) /*訪問vi+l的未訪問的鄰接點*/
{ printf{"％c＼n" , g1[p - >adjvex].vertex};
visited[p - >adjvex]＝TRUE;
ENQUEUE(Q,p - >adjvex); /*訪問過的頂點入隊*/
}
p＝p - >next; /*找vi+l的下一個鄰接點*/
}
}
} /*BFSL*/
P148 在對演算法Prim求精之前，先確定有關的存儲結構如下：
typdef struct
{Int fromvex，endvex; /*邊的起點和終點*/
float length; /*邊的權值*/
} edge;
float dist[n][n]; /*連通網路的帶權鄰接矩陣*/
edgeT[n-1]; /*生成樹*/
P149 抽象語句(1)可求精為：
for(j=1;j<n;j++) /*對n-1個藍點構造候選紫邊集*/
{T[j-1].fromvex＝1}; /*紫邊的起點為紅點*/
T[j-1].endvex＝j+1; /*紫邊的終點為藍點*/
T[j-1].1ength＝dist[0][j]; /*紫邊長度*/
}
P149 抽象語句(3)所求的第k條最短紫邊可求精為：
min＝max; /*znax大於任何邊上的權值*/
for (j＝k;j<n-1;j++) /*掃描當前候選紫邊集T[k]到T[n-2]，找最短紫邊*/
if(T[j].1ength<min)
{min＝T[j].1ength;m＝j; /*記錄當前最短紫邊的位置*/
}
P149 抽象語句(4)的求精：
e＝T[m];T[m]＝T[k];T[k]＝e， /* T[k]和T[m]交換*/
v＝T[kl.Endvex]; /* v是剛被塗紅色的頂點*/
P149 抽象語句(5)可求精為：
for(j＝k+1;j<n-1;j++) /*調整候選紫邊集T[k+1]到T[n-2]*/
{d＝dist[v-1][T[j].endvex-1]; /*新紫邊的長度*/
if(d<T[j].1ength) /*新紫邊的長度小於原最短紫邊*/
{T[j].1ength＝d;
T[j].fromvex＝v; /*新紫邊取代原最短紫邊*/
}
}
P150 完整的演算法：
PRIM() /*從第一個頂點出發構造連通網路dist的最小生成樹，結果放在T中*/
{int j , k , m , v , min , max＝l0000;
float d;
edge e;
for(j=1;j<n;j++) /*構造初始候選紫邊集*/
{T[j-1].formvex＝1; /*頂點1是第一個加入樹中的紅點*/
T[j-1].endvex＝j+1;
T[j-1].length＝dist[o][j];
}
for(k＝0;k<n-1;k++) /*求第k條邊*/
{min＝max;
for(j＝k;j<n-1;j++) /*在候選紫邊集中找最短紫邊*/
if(T[j].1ength<min)
{min＝T[j].1ength;
m＝j;
} /*T[m]是當前最短紫邊*/
}
e＝T[m];T[m]＝T[k];T[k]＝e; /*T[k]和T[m]交換後，T[k]是第k條紅色樹邊*/
v＝T[k].endvex ; /* v是新紅點*/
for(j＝k+1;j<n-1;j++) /*調整候選紫邊集*/
{d＝dist[v-1][T[j].endvex-1];
if(d<T[j].1ength);
{T[j].1ength＝d;
T[j].fromvex＝v;
}
}
} /* PRIM */
P151 Kruskl演算法的粗略描述：
T＝(V,φ);
While(T中所含邊數<n-1)
{從E中選取當前最短邊(u,v);
從E中刪去邊(u,v);
if((u,v)並入T之後不產生迴路，將邊(u,v)並入T中;
}
P153 迪傑斯特拉演算法實現。演算法描述如下：
#define max 32767 /*max代表一個很大的數*/
void dijkstra (float cost[][n],int v)
/*求源點v到其餘頂點的最短路徑及其長度*/
{ v1=v-1;
for (i=0;i<n;i++)
{ dist[i]=cost[v1][i]; /*初始化dist*/
if (dist[i]<max)
pre[i]=v;
else pre[i]=0;
}
pre[v1]=0;
for (i=0;i<n;i++)
s[i]=0; /*s數組初始化為空*/
s[v1]=1; /*將源點v歸入s集合*/
for (i=0;i<n;i++)
{ min=max;
for (j=0;j<n;j++)
if (!s[j] && (dist[j]<min))
{ min=dist[j];
k=j;
} /*選擇dist值最小的頂點k+1*/
s[k]=1; /*將頂點k+1歸入s集合中*/
for (j=0;j<n;j++)
if (!s[j]&&(dist[j]>dist[k]+cost[k][j]))
{ dist[j]=dist[k]+cost[k][j]; /*修改 V-S集合中各頂點的dist值*/
pre[j]=k+1; /*k+1頂點是j+1頂點的前驅*/
}
} /*所有頂點均已加入到S集合中*/
for (j=0;j<n;j++) /*列印結果*/
{ printf("%f\n%d",dist[j],j+1;);
p=pre[j];
while (p!=0)
{ printf("%d",p);
p=pre[p-1];
}
}
}
P155 弗洛伊德演算法可以描述為：
A(0)[i][j]=cost[i][j]; //cost為圖的鄰接矩陣
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n
P155 弗洛伊德演算法實現。演算法描述如下：
int path[n][n]; /*路徑矩陣*/
void floyd (float A[][n],cost[][n])
{ for (i=0;i<n;i++) /*設置A和path的初值*/
for (j=0;j<n;j++)
{ if (cost[i][j]<max)
path[i][j]=j;
else { path[i][j]=0;
A[i][j]=cost[i][j];
}
}
for (k=0;k<n;k++)
/*做n次迭代，每次均試圖將頂點k擴充到當前求得的從i到j的最短路徑上*/
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (A[i][j]>(A[i][k]+A[k]
F. C語言 三元組分配，到底錯在哪嘛
#include<stdio.h>
#include<stdlib.h>
#defineERROR0
#define芹行談OK1
#defineOVERFLOW-2
typedefint嫌碰Status;
typedefintElemType;
typedefElemType*Triplet;
StatusInitTriplet(Triplet*T,ElemTypev1,ElemTypev2,ElemTypev3){//這里帶肆請不要用漢語的逗號
*T=(ElemType*)malloc(3*sizeof(ElemType));
if(!(*T))exit(OVERFLOW);
(*T)[0]=v1;
(*T)[1]=v2;
(*T)[2]=v3;
returnOK;
}
voidmain(){
}
請不要用漢語的逗號
！！！
G. 關於數據結構的問題，用C語言描述
數據結構復習重點歸納筆記[清華嚴蔚敏版]
數據結構復習重點歸納[適於清華嚴版教材]
一、數據結構的章節結構及重點構成
數據結構學科的章節劃分基本上為：概論，線性表，棧和隊列，串，多維數組和廣義表，樹和二叉樹，圖，查找，內排，外排，文件，動態存儲分配。
對於絕大多數的學校而言，「外排，文件，動態存儲分配」三章基本上是不考的，在大多數高校的計算機本科教學過程中，這三章也是基本上不作講授的。所以，大家在這三章上可以不必花費過多的精力，只要知道基本的概念即可。但是，對於報考名校特別是該校又有在試卷中對這三章進行過考核的歷史，那麼這部分朋友就要留意這三章了。
按照以上我們給出的章節以及對後三章的介紹，數據結構的章節比重大致為：
概論：內容很少，概念簡單，分數大多隻有幾分，有的學校甚至不考。
線性表：基礎章節，必考內容之一。考題多數為基本概念題，名校考題中，鮮有大型演算法設計題。如果有，也是與其它章節內容相結合。
棧和隊列：基礎章節，容易出基本概念題，必考內容之一。而棧常與其它章節配合考查，也常與遞歸等概念相聯系進行考查。
串 ：基礎章節，概念較為簡單。專門針對於此章的大型演算法設計題很少，較常見的是根據KMP進行演算法分析。
多維數組及廣義表
：基礎章節，基於數組的演算法題也是常見的，分數比例波動較大，是出題的「可選單元」或「侯補單元」。一般如果要出題，多數不會作為大題出。數組常與「查找，排序」等章節結合來作為大題考查。
樹和二叉樹
：重點難點章節，各校必考章節。各校在此章出題的不同之處在於，是否在本章中出一到兩道大的演算法設計題。通過對多所學校的試卷分析，絕大多數學校在本章都曾有過出大型演算法設計題的歷史。
圖 ：重點難點章節，名校尤愛考。如果作為重點來考，則多出現於分析與設計題型當中，可與樹一章共同構成演算法設計大題的題型設計。
查找
：重點難點章節，概念較多，聯系較為緊密，容易混淆。出題時可以作為分析型題目給出，在基本概念型題目中也較為常見。演算法設計型題中可以數組結合來考查，也可以與樹一章結合來考查。
排序
：與查找一章類似，本章同屬於重點難點章節，且概念更多，聯系更為緊密，概念之間更容易混淆。在基本概念的考查中，尤愛考各種排序演算法的優劣比較此類的題。演算法設計大題中，如果作為出題，那麼常與數組結合來考查。
二、數據結構各章節重點勾劃：
第0章 概述
本章主要起到總領作用，為讀者進行數據結構的學習進行了一些先期鋪墊。大家主要注意以下幾點：數據結構的基本概念，時間和空間復雜度的概念及度量方法，演算法設計時的注意事項。本章考點不多，只要稍加註意理解即可。
第一章 線性表
作為線性結構的開篇章節，線性表一章在線性結構的學習乃至整個數據結構學科的學習中，其作用都是不可低估的。在這一章，第一次系統性地引入鏈式存儲的概念，鏈式存儲概念將是整個數據結構學科的重中之重，無論哪一章都涉及到了這個概念。
總體來說，線性表一章可供考查的重要考點有以下幾個方面：
1.線性表的相關基本概念，如：前驅、後繼、表長、空表、首元結點，頭結點，頭指針等概念。
2.線性表的結構特點，主要是指：除第一及最後一個元素外，每個結點都只有一個前趨和只有一個後繼。
3.線性表的順序存儲方式及其在具體語言環境下的兩種不同實現：表空間的靜態分配和動態分配。靜態鏈表與順序表的相似及不同之處。
4.線性表的鏈式存儲方式及以下幾種常用鏈表的特點和運算：單鏈表、循環鏈表，雙向鏈表，雙向循環鏈表。其中，單鏈表的歸並演算法、循環鏈表的歸並演算法、雙向鏈表及雙向循環鏈表的插入和刪除演算法等都是較為常見的考查方式。此外，近年來在不少學校中還多次出現要求用遞歸演算法實現單鏈表輸出（可能是順序也可能是倒序）的問題。
在鏈表的小題型中，經常考到一些諸如：判表空的題。在不同的鏈表中，其判表空的方式是不一樣的，請大家注意。
5.線性表的順序存儲及鏈式存儲情況下，其不同的優缺點比較，即其各自適用的場合。單鏈表中設置頭指針、循環鏈表中設置尾指針而不設置頭指針以及索引存儲結構的各自好處。
第二章 棧與隊列
棧與隊列，是很多學習DS的同學遇到第一隻攔路虎，很多人從這一章開始坐暈車，一直暈到現在。所以，理解棧與隊列，是走向DS高手的一條必由之路，。
學習此章前，你可以問一下自己是不是已經知道了以下幾點：
1.棧、隊列的定義及其相關數據結構的概念，包括：順序棧，鏈棧，共享棧，循環隊列，鏈隊等。棧與隊列存取數據（請注意包括：存和取兩部分）的特點。
2.遞歸演算法。棧與遞歸的關系，以及藉助棧將遞歸轉向於非遞歸的經典演算法：n!階乘問題，fib數列問題，hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關系等。其中，涉及到樹與圖的問題，多半會在樹與圖的相關章節中進行考查。
3.棧的應用：數值表達式的求解，括弧的配對等的原理，只作原理性了解，具體要求考查此為題目的演算法設計題不多。
4.循環隊列中判隊空、隊滿條件，循環隊列中入隊與出隊演算法。
如果你已經對上面的幾點了如指掌，棧與隊列一章可以不看書了。注意，我說的是可以不看書，並不是可以不作題哦。
第三章 串
經歷了棧一章的痛苦煎熬後，終於迎來了串一章的柳暗花明。
串，在概念上是比較少的一個章節，也是最容易自學的章節之一，但正如每個過來人所了解的，KMP演算法是這一章的重要關隘，突破此關隘後，走過去又是一馬平川的大好DS山河了，呵呵。
串一章需要攻破的主要堡壘有：
1.串的基本概念，串與線性表的關系（串是其元素均為字元型數據的特殊線性表），空串與空格串的區別，串相等的條件
2.串的基本操作，以及這些基本函數的使用，包括：取子串，串連接，串替換，求串長等等。運用串的基本操作去完成特定的演算法是很多學校在基本操作上的考查重點。
3.順序串與鏈串及塊鏈串的區別和聯系，實現方式。
4.KMP演算法思想。KMP中next數組以及nextval數組的求法。明確傳統模式匹配演算法的不足，明確next數組需要改進之外。其中，理解演算法是核心，會求數組是得分點。不用我多說，這一節內容是本章的重中之重。可能進行的考查方式是：求next和nextval數組值，根據求得的next或nextval數組值給出運用KMP演算法進行匹配的匹配過程。
第四章 數組與廣義表
學過程序語言的朋友，數組的概念我們已經不是第一次見到了，應該已經「一回生，二回熟」了，所以，在概念上，不會存在太大障礙。但作為考研課程來說，本章的考查重點可能與大學里的程序語言所關注的不太一樣，下面會作介紹。
廣義表的概念，是數據結構里第一次出現的。它是線性表或表元素的有限序列，構成該結構的每個子表或元素也是線性結構的，所以，這一章也歸入線性結構中。
本章的考查重點有：
1.多維數組中某數組元素的position求解。一般是給出數組元素的首元素地址和每個元素佔用的地址空間並組給出多維數組的維數，然後要求你求出該數組中的某個元素所在的位置。
2.明確按行存儲和按列存儲的區別和聯系，並能夠按照這兩種不同的存儲方式求解1中類型的題。
3.將特殊矩陣中的元素按相應的換算方式存入數組中。這些矩陣包括：對稱矩陣，三角矩陣，具有某種特點的稀疏矩陣等。熟悉稀疏矩陣的三種不同存儲方式：三元組，帶輔助行向量的二元組，十字鏈表存儲。掌握將稀疏矩陣的三元組或二元組向十字鏈表進行轉換的演算法。
4.廣義表的概念，特別應該明確表頭與表尾的定義。這一點，是理解整個廣義表一節演算法的基礎。近來，在一些學校中，出現了這樣一種題目類型：給出對某個廣義表L若干個求了若干次的取頭和取尾操作後的串值，要求求出原廣義表L。大家要留意。
5.與廣義表有關的遞歸演算法。由於廣義表的定義就是遞歸的，所以，與廣義表有關的演算法也常是遞歸形式的。比如：求表深度，復制廣義表等。這種題目，可以根據不同角度廣義表的表現形式運用兩種不同的方式解答：一是把一個廣義表看作是表頭和表尾兩部分，分別對表頭和表尾進行操作；二是把一個廣義表看作是若干個子表，分別對每個子表進行操作。
第五章 樹與二叉樹
從對線性結構的研究過度到對樹形結構的研究，是數據結構課程學習的一次躍變，此次躍變完成的好壞，將直接關繫到你到實際的考試中是否可以拿到高分，而這所有的一切，將最終影響你的專業課總分。所以，樹這一章的重要性，已經不說自明了。
總體來說，樹一章的知識點包括：
二叉樹的概念、性質和存儲結構，二叉樹遍歷的三種演算法（遞歸與非遞歸），在三種基本遍歷演算法的基礎上實現二叉樹的其它演算法，線索二叉樹的概念和線索化演算法以及線索化後的查找演算法，最優二叉樹的概念、構成和應用，樹的概念和存儲形式，樹與森林的遍歷演算法及其與二叉樹遍歷演算法的聯系，樹與森林和二叉樹的轉換。
下面我們來看考試中對以上知識的主要考查方法：
1.二叉樹的概念、性質和存儲結構
考查方法可有：直接考查二叉樹的定義，讓你說明二叉樹與普通雙分支樹的區別；考查滿二叉樹和完全二叉樹的性質，普通二叉樹的五個性質：第i層的最多結點數，深度為k的二叉樹的最多結點數，n0=n2+1的性質，n個結點的完全二叉樹的深度，順序存儲二叉樹時孩子結點與父結點之間的換算關系（左為：2*i，右為：2*i+1）。
二叉樹的順序存儲和二叉鏈表存儲的各自優缺點及適用場合，二叉樹的三叉鏈表表示方法。
2.二叉樹的三種遍歷演算法
這一知識點掌握的好壞，將直接關繫到樹一章的演算法能否理解，進而關繫到樹一章的演算法設計題能否順利完成。二叉樹的遍歷演算法有三種：先序，中序和後序。其劃分的依據是視其每個演算法中對根結點數據的訪問順序而定。不僅要熟練掌握三種遍歷的遞歸演算法，理解其執行的實際步驟，並且應該熟練掌握三種遍歷的非遞歸演算法。由於二叉樹一章的很多演算法，可以直接根據三種遞歸演算法改造而來（比如：求葉子個數），所以，掌握了三種遍歷的非遞歸演算法後，對付諸如：「利用非遞歸演算法求二叉樹葉子個數」這樣的題目就下筆如有神了。我會在另一篇系列文章（）里給出三種遍歷的遞歸和非遞歸演算法的背記版，到時請大家一定熟記。
3.可在三種遍歷演算法的基礎上改造完成的其它二叉樹演算法：
求葉子個數，求二叉樹結點總數，求度為1或度為2的結點總數，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結點，刪除值為n的某個指定結點，諸如此類等等等等。如果你可以熟練掌握二叉樹的遞歸和非遞歸遍歷演算法，那麼解決以上問題就是小菜一碟了。
4.線索二叉樹：
線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。眾所周知，遞歸雖然形式上比較好理解，但是消耗了大量的內存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險，為了避免此類情況，線索二叉樹便堂而皇之地出現了。對於線索二叉樹，應該掌握：線索化的實質，三種線索化的演算法，線索化後二叉樹的遍歷演算法，基本線索二叉樹的其它演算法問題（如：查找某一類線索二叉樹中指定結點的前驅或後繼結點就是一類常考題）。
5.最優二叉樹（哈夫曼樹）：
最優二叉樹是為了解決特定問題引出的特殊二叉樹結構，它的前提是給二叉樹的每條邊賦予了權值，這樣形成的二叉樹按權相加之和是最小的。最優二叉樹一節，直接考查演算法源碼的很少，一般是給你一組數據，要求你建立基於這組數據的最優二叉樹，並求出其最小權值之和，此類題目不難，屬送分題。
6.樹與森林：
二叉樹是一種特殊的樹，這種特殊不僅僅在於其分支最多為2以及其它特徵，一個最重要的特殊之處是在於：二叉樹是有序的！即：二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之後的二叉樹與原二叉樹我們認為是不相同的兩棵二叉樹。但是，對於普通的雙分支樹而言，不具有這種性質。
樹與森林的遍歷，不像二叉樹那樣豐富，他們只有兩種遍歷演算法：先根與後根（對於森林而言稱作：先序與後序遍歷）。在難度比較大的考試中，也有基於此二種演算法的基礎上再進行擴展要求你利用這兩種演算法設計其它演算法的，但一般院校很少有這種考法，最多隻是要求你根據先根或後根寫出他們的遍歷序列。此二者的先根與後根遍歷與二叉樹中的遍歷演算法是有對應關系的：先根遍歷對應二叉樹的先序遍歷，而後根遍歷對應二叉樹的中序遍歷。這一點成為很多學校的考點，考查的方式不一而足，有的直接考此句話，有的是先讓你求解遍歷序列然後回答這個問題。二叉樹、樹與森林之所以能有以上的對應關系，全拜二叉鏈表所賜。二叉樹使用二叉鏈表分別存放他的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。
樹一章，處處是重點，道道是考題，大家務必個個過關。
第六章 圖
如果說，從線性結構向樹形結構研究的轉變，是數據結構學科對數據組織形式研究的一次升華，那麼從樹形結構的研究轉到圖形結構的研究，則進一步讓我們看到了數據結構對於解決實際問題的重大推動作用。
圖這一章的特點是：概念繁多，與離散數學中圖的概念聯系緊密，演算法復雜，極易被考到，且容易出大題，尤其是名校，作為考研課程，如果不考查樹與圖兩章的知識，幾乎是不可想像的。
下面我們看一下圖這一章的主要考點以及這些考點的考查方式：
1.考查有關圖的基本概念問題：
這些概念是進行圖一章學習的基礎，這一章的概念包括：圖的定義和特點，無向圖，有向圖，入度，出度，完全圖，生成子圖，路徑長度，迴路，（強）連通圖，（強）連通分量等概念。與這些概念相聯系的相關計算題也應該掌握。
2.考查圖的幾種存儲形式：
圖的存儲形式包括：鄰接矩陣，（逆）鄰接表，十字鏈表及鄰接多重表。在考查時，有的學校是給出一種存儲形式，要求考生用演算法或手寫出與給定的結構相對應的該圖的另一種存儲形式。
3.考查圖的兩種遍歷演算法：深度遍歷和廣度遍歷
深度遍歷和廣度遍歷是圖的兩種基本的遍歷演算法，這兩個演算法對圖一章的重要性等同於「先序、中序、後序遍歷」對於二叉樹一章的重要性。在考查時，圖一章的演算法設計題常常是基於這兩種基本的遍歷演算法而設計的，比如：「求最長的最短路徑問題」和「判斷兩頂點間是否存在長為K的簡單路徑問題」，就分別用到了廣度遍歷和深度遍歷演算法。
4.生成樹、最小生成樹的概念以及最小生成樹的構造：PRIM演算法和KRUSKAL演算法。
考查時，一般不要求寫出演算法源碼，而是要求根據這兩種最小生成樹的演算法思想寫出其構造過程及最終生成的最小生成樹。
5.拓撲排序問題：
拓撲排序有兩種方法，一是無前趨的頂點優先演算法，二是無後繼的頂點優先演算法。換句話說，一種是「從前向後」的排序，一種是「從後向前」排。當然，後一種排序出來的結果是「逆拓撲有序」的。
6.關鍵路徑問題：
這個問題是圖一章的難點問題。理解關鍵路徑的關鍵有三個方面：一是何謂關鍵路徑，二是最早時間是什麼意思、如何求，三是最晚時間是什麼意思、如何求。簡單地說，最早時間是通過「從前向後」的方法求的，而最晚時間是通過「從後向前」的方法求解的，並且，要想求最晚時間必須是在所有的最早時間都已經求出來之後才能進行。這個問題拿來直接考演算法源碼的不多，一般是要求按照書上的演算法描述求解的過程和步驟。
在實際設計關鍵路徑的演算法時，還應該注意以下這一點：採用鄰接表的存儲結構，求最早時間和最晚時間要採用不同的處理方法，即：在演算法初始時，應該首先將所有頂點的最早時間全部置為0。關鍵路徑問題是工程進度控制的重要方法，具有很強的實用性。
7.最短路徑問題：
與關鍵路徑問題並稱為圖一章的兩只攔路虎。概念理解是比較容易的，關鍵是演算法的理解。最短路徑問題分為兩種：一是求從某一點出發到其餘各點的最短路徑；二是求圖中每一對頂點之間的最短路徑。這個問題也具有非常實用的背景特色，一個典型的應該就是旅遊景點及旅遊路線的選擇問題。解決第一個問題用DIJSKTRA演算法，解決第二個問題用FLOYD演算法。注意區分。
第七章 查找
在不少數據結構的教材中，是把查找與排序放入高級數據結構中的。應該說，查找和排序兩章是前面我們所學的知識的綜合運用，用到了樹、也用到了鏈表等知識，對這些數據結構某一方面的運用就構成了查找和排序。
現實生活中，search幾乎無處不在，特別是現在的網路時代，萬事離不開search，小到文檔內文字的搜索，大到INTERNET上的搜索，search占據了我們上網的大部分時間。
在復習這一章的知識時，你需要先弄清楚以下幾個概念：
關鍵字、主關鍵字、次關鍵字的含義；靜態查找與動態查找的含義及區別；平均查找長度ASL的概念及在各種查找演算法中的計算方法和計算結果，特別是一些典型結構的ASL值，應該記住。
在DS的教材中，一般將search分為三類：1st，在順序表上的查找；2nd，在樹表上的查找；3rd，在哈希表上的查找。下面詳細介紹其考查知識點及考查方式：
1.線性表上的查找：
主要分為三種線性結構：順序表，有序順序表，索引順序表。對於第一種，我們採用傳統查找方法，逐個比較。對於及有序順序表我們採用二分查找法。對於第三種索引結構，我們採用索引查找演算法。考生需要注意這三種表下的ASL值以及三種演算法的實現。其中，二分查找還要特別注意適用條件以及其遞歸實現方法。
2.樹表上的查找：
這是本章的重點和難點。由於這一節介紹的內容是使用樹表進行的查找，所以很容易與樹一間的某些概念相混淆。本節內容與樹一章的內容有聯系，但也有很多不同，應注意規納。樹表主要分為以下幾種：二叉排序樹，平衡二叉樹，B樹，鍵樹。其中，尤以前兩種結構為重，也有部分名校偏愛考B樹的。由於二叉排序樹與平衡二叉樹是一種特殊的二叉樹，所以與二叉樹的聯系就更為緊密，二叉樹一章學好了，這里也就不難了。
二叉排序樹，簡言之，就是「左小右大」，它的中序遍歷結果是一個遞增的有序序列。平衡二叉樹是二叉排序樹的優化，其本質也是一種二叉排序樹，只不過，平衡二叉樹對左右子樹的深度有了限定：深度之差的絕對值不得大於1。對於二叉排序樹，「判斷某棵二叉樹是否二叉排序樹」這一演算法經常被考到，可用遞歸，也可以用非遞歸。平衡二叉樹的建立也是一個常考點，但該知識點歸根結底還是關注的平衡二叉樹的四種調整演算法，所以應該掌握平衡二叉樹的四種調整演算法，調整的一個參照是：調整前後的中序遍歷結果相同。
B樹是二叉排序樹的進一步改進，也可以把B樹理解為三叉、四叉....排序樹。除B樹的查找演算法外，應該特別注意一下B樹的插入和刪除演算法。因為這兩種演算法涉及到B樹結點的分裂和合並，是一個難點。B樹是報考名校的同學應該關注的焦點之一。
鍵樹也稱字元樹，特別適用於查找英文單詞的場合。一般不要求能完整描述演算法源碼，多是根據演算法思想建立鍵樹及描述其大致查找過程。
3.基本哈希表的查找演算法：
哈希一詞，是外來詞，譯自「hash」一詞，意為：散列或雜湊的意思。哈希表查找的基本思想是：根據當前待查找數據的特徵，以記錄關鍵字為自變數，設計一個function，該函數對關鍵字進行轉換後，其解釋結果為待查的地址。基於哈希表的考查點有：哈希函數的設計，沖突解決方法的選擇及沖突處理過程的描述。
第八章 內部排序
內排是DS課程中最後一個重要的章節，建立在此章之上的考題可以有多種類型：填空，選擇，判斷乃至大型演算法題。但是，歸結到一點，就是考查你對書本上的各種排序演算法及其思想以及其優缺點和性能指標（時間復雜度）能否了如指掌。
這一章，我們對重點的規納將跟以上各章不同。我們將從以下幾個側面來對排序一章進行不同的規納，以期能更全面的理解排序一章的總體結構及各種演算法。
從排序演算法的種類來分，本章主要闡述了以下幾種排序方法：插入、選擇、交換、歸並、計數等五種排序方法。
其中，在插入排序中又可分為：直接插入、折半插入、2路插入、希爾排序。這幾種插入排序演算法的最根本的不同點，說到底就是根據什麼規則尋找新元素的插入點。直接插入是依次尋找，折半插入是折半尋找。希爾排序，是通過控制每次參與排序的數的總范圍「由小到大」的增量來實現排序效率提高的目的。
交換排序，又稱冒泡排序，在交換排序的基礎上改進又可以得到快速排序。快速排序的思想，一語以敝之：用中間數將待排數據組一分為二。快速排序，在處理的「問題規模」這個概念上，與希爾有點相反，快速排序，是先處理一個較大規模，然後逐漸把處理的規模降低，最終達到排序的目的。
選擇排序，相對於前面幾種排序演算法來說，難度大一點。具體來說，它可以分為：簡單選擇、樹選擇、堆排。這三種方法的不同點是，根據什麼規則選取最小的數。簡單選擇，是通過簡單的數組遍歷方案確定最小數；樹選擇，是通過「錦標賽」類似的思想，讓兩數相比，不斷淘汰較大（小）者，最終選出最小（大）數；而堆排序，是利用堆這種數據結構的性質，通過堆元素的刪除、調整等一系列操作將最小數選出放在堆頂。堆排序中的堆建立、堆調整是重要考點。樹選擇排序，也曾經在一些學校中的大型演算法題中出現，請大家注意。
歸並排序，故名思義，是通過「歸並」這種操作完成排序的目的，既然是歸並就必須是兩者以上的數據集合才可能實現歸並。所以，在歸並排序中，關注最多的就是2路歸並。演算法思想比較簡單，有一點，要銘記在心：歸並排序是穩定排序。
基數排序，是一種很特別的排序方法，也正是由於它的特殊，所以，基數排序就比較適合於一些特別的場合，比如撲克牌排序問題等。基數排序，又分為兩種：多關鍵字的排序（撲克牌排序），鏈式排序（整數排序）。基數排序的核心思想也是利用「基數空間」這個概念將問題規模規范、變小，並且，在排序的過程中，只要按照基排的思想，是不用進行關鍵字比較的，這樣得出的最終序列就是一個有序序列。
本章各種排序演算法的思想以及偽代碼實現，及其時間復雜度都是必須掌握的，學習時要多注意規納、總結、對比。此外，對於教材中的10.7節，要求必須熟記，在理解的基礎上記憶，這一節幾乎成為很多學校每年的必考點。
至此，數據結構所有章節的章節重點問題，我們已經規納完畢，使用清華嚴版教材的同學，在復習的同時，可以參照本貼給出的重點進行復習。但是，由於作者本人水平有限，可能有很多考點沒有規納出來，也可能有些考點規納有誤，在此，作者本人誠懇希望諸位朋友直面提出，我會不斷完善和發布新的關於數據結構復習的總結以及筆記
嚴蔚敏數據結構為主的筆記二
第二章：線性表(包括習題與答案及要點)
--------------------------------------------------------------------------------
本章的重點是掌握順序表和單鏈表上實現的各種基本演算法及相關的時間性能分析，難點是使用本章所學的基本知識設計有效演算法解決與線性表相關的應用問題。
要求達到<識記>層次的內容有:線性表的邏輯結構特徵；線性表上定義的基本運算，並利用基本運算構造出較復雜的運算。
要求達到<綜合應用>層次的內容有：順序表的含義及特點，順序表上的插入、刪除操作及其平均時間性能分析，解決簡單應用問題。
鏈表如何表示線性表中元素之間的邏輯關系；單鏈表、雙鏈表、循環鏈表鏈接方式上的區別；單鏈表上實現的建表、查找、插入和刪除等基本演算法及其時間復雜度。循環鏈表上尾指針取代頭指針的作用，以及單循環鏈表上的演算法與單鏈表上相應演算法的異同點。雙鏈表的定義和相關演算法。利用鏈表設計演算法解決簡單應用問題。
要求達到<領會>層次的內容就是順序表和鏈表的比較，以及如何選擇其一作為其存儲結構才能取得較優的時空性能。
--------------------------------------------------------------------------------
線性表的邏輯結構特徵是很容易理解的，如其名，它的邏輯結構特徵就好象是一條線，上面打了一個個結，很形象的，如果這條線上面有結，那麼它就是非空表，只能有一個開始結點，有且只能有一個終端結點，其它的結前後所相鄰的也只能是一個結點(直接前趨和直接後繼)。
關於線性表上定義的基本運算，主要有構造空表、求表長、取結點、查找、插入、刪除等。
--------------------------------------------------------------------------------
線性表的邏輯結構和存儲結構之間的關系。在計算機中，如何把線性表的結點存放到存儲單元中，就有許多方法，最簡單的方法就是按順序存儲。就是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的。
在順序表中實現的基本運算主要討論了插入和刪除兩種運算。相關的演算法我們通過練習掌握。對於順序表的插入和刪除運算，其平均時間復雜度均為O(n)。
--------------------------------------------------------------------------------
線性表的鏈式存儲結構。它與順序表不同，鏈表是用一組任意的存儲單元來存放線性表的結點，這組存儲單元可以分布在內存中任何位置上。因此，鏈表中結點的邏輯次序和物理次序不一定相同。所以為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還存儲了其後繼結點的地址信息(即
H. C語言求解 畢達哥拉斯三元組
#include<iostream>
using namespace std;
void main()
{
int side1;
int side2;
int hypotenuse;
int sum1,sum2;
int count;
cout<<"Please enter the hypotenuse:"<<endl;
cout<<"Make sure that the length is above 0 and below 500!"<<endl;
cin>>count;
cout<岩鍵芹<"The length is "<< count <<"."亮仿<<endl;
for(side1=1;side1<count;side1++)
{
for(side2=side1+1;side2<count;side2++)
{
sum1=side1*side1+side2*side2;
for(hypotenuse=side2+1;hypotenuse<=count;hypotenuse++)
{
sum2=hypotenuse*hypotenuse;
if(sum2==sum1)
{
cout<<side1<<" "<<side2<<" "<<hypotenuse<<" "<<endl;
}
}
}
}
}
程序用vc6.0編譯通過。粗畢
I. C語言三元組輸入輸出的轉置矩陣
分類: 電腦/網路 >> 程序設計 >> 其他編程語言
解析:
用三元組存儲的稀疏矩陣的轉置運算
三元組採用行優先表示法,轉置後的矩陣的三元組同樣要採用行優先表示法
0 1 12
0 2 9
2 0 -3
3 5 14
3 2 24
4 1 18
5 0 15
5 3 -7
struct node
{
int i,j; 定義三元組的行、列號
int v; 三元組的值
};
struct sparmatrix
{
int rows,cols; 稀疏矩陣的行純指裂、列數
int terms; 稀疏矩陣的非零元個數
struct node data[maxsize]; 存放稀疏矩陣的三元組表
};
（1）按照A的列序進行轉置
由於A的列即為B的行，在a.data（原表）中，按列掃描，則得到的b.data（轉置表）必按行優先存放。
但為了找到A的每一列中所有的非零的元素，每次都必須從頭到尾掃描A的三元組表（有多少列，則掃描多少遍）
void transpose(struct sparmatrix a)
{
struct sparmatrix b; /*b為a的轉置*/
int ano,bno=0,col,i;
b.rows=a.cols; b.cols=a.rows;
b.terms=a.terms;
if (b.terms>0)
{
for ( col=0; col<a.cols; col++) /*按列號掃描*/
for( ano=0;ano<a.terms;ano++) /*對三元組掃描*/
if (a.data[ano].j==col) /*進行轉置*/
{ b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
b.data[bno].v=a.data[ano].v;
bno++;
}
}
…………….
（2）按照A的行序進行轉置
即按a.data中三元組的次序進行轉置，並將轉置後的三元組放入b中恰當的位置。
若能在轉置前求出矩陣A的每一列col（即B中每一行）的第一個非零元轉置後在b.data中的正確位置pot[col]（0≤col<a.cols），那麼在對a.data的三元組依次作轉置時，只要將三元組按列號col放置到b.data[pot[col]]中，之後將pot[col]內容加1，以指示第逗鉛col列的下一個非零做閉元的正確位置。
void fastrans(struct sparmatrix a)
{
struct sparmatrix b;
int pot[maxsize],col,ano,bno,t,i;
b.rows=a.cols; b.cols=a.rows;
b.terms=a.terms;
if(b.terms>0)
{
for(col=0;col<=a.cols;col++)
pot[col]=0;
for( t=0;t<a.terms;t++) /*求出每一列的非零元個數*/
{
col=a.data[t].j;
pot[col+1]=pot[col+1]+1;
}
pot[0]=0;
for(col=1;col<a.cols;col++) /*求出每一列的第一個非零元在轉置後的位置*/
pot[col]=pot[col-1]+pot[col];
for( ano=0;ano<a.terms;ano++) /*轉置*/
{ col=a.data[ano].j;
bno=pot[col];
b.data[bno].j=a.data[ano].i;
b.data[bno].i=a.data[ano].j;
b.data[bno].v=a.data[ano].v;
pot[col]=pot[col]+1;
}
}
J. 求一關於三元二次方程求解的C語言程序！！
#include<stdio.h>
#include<math.h>
void main()
{
int a,b,c,d;
float sum1,sum2;
printf("本程序功能為為計算一元二次方程式的根\n請按一下格式輸入：\n");
printf("型如ax2+bx+c=0：\na=");
scanf("襪滑%d",&a);
printf("b=");
scanf("%d",&b);
printf("搭好睜c=");
scanf("%d",&c);
if((b*b-4*a*c)>=0)
{
sum1=(float)((double)(-1)*b+(double)sqrt((double)(b*b-4*a*c)))/((float)(2*a));
sum2=(float)((double)(-1)*b-(double)sqrt((double)(b*b-4*a*c)))/((float)(2*a));
printf("所求的兩個根為x1=%.3f\tx2=%.3f\n",sum1,sum2);
}
else
{
printf("輸入錯誤：b*b-4ac<知歲0\n");
}
printf("運算結束，如有BUG，請禮貌上報[email protected]\n");
}