数据结构源代码(C语言描述)(4)

} slstrtype;

P66【算法4.2 在链式存储方式中求子串】 int substr(slstrtype s1,slstrtype *s2,int m,int n) {slstrtype *p,*q,*v; int length1,j; p=&s1;

for(lenght1=0;p->next!=NULL;p=p->next) length1++; /*求主串和串长*/ if(m<=0||m>length1||n<0) {s2=NULL;return FALSE;} /*参数错误*/ p=s1.next;

for(j=0;jnext; /*找到子串和起始位置*/

s2=(slstrtype *)malloc(sizeof(slstrtype)); /*分配子串和第一个结点*/ v=s2;q=v;

for(j=0;jnext!=NULL;j++) /*建立子串*/ { q->str=p->str; p=p->next;

q=(slstrtype *)malloc(sizeof(slstrtype)); v->next=q; v=q; }

q->str='\\0';q->next=NULL; /*置子串和尾结点*/ return TRUE; }

P67 堆存储结构用C语言定义为： typedet struct{ char *str; int length; } HSstrtype;

P67【算法4.3 共享法求子串】

int substr(HSstrtype s1,HSstrtype *s2,int m,int n) { int j,k; j=s1.length;

if(m<=0||m>j||n<0) {s2->length=0;return FALSE;} /*参数错误*/ k=strlen(s1.str+m); /*主串第m个位置开始之后的串长*/ if (n>k) s2->length=k;

else s2->length=n; /*置子串的串长*/ s2->str=s1.str+m; /*置子串的串首地址 return TRUE; }

P67【算法4.4 重新赋值法求子串】

int substr(HSstrtype s1,HSstrtype *s2,int m,int n)

{ int j,k; j=s1.length;

if(m<=0||m>j||n<0) {s2->length=0;return FALSE;} /*参数错误*/ k=strlen(s1.str+m); /*主串第m个位置开始之后的串长*/ if (n>k) s2->length=k;

else s2->length=n; /*置子串的串长*/ k=s2->length; for(j=0;j

s2->str[j]=s1.str[m++]; /*复制字符*/ s2->str[j]='\\0'; /*置结束符*/ return TRUE; }

P68 例 main() {int a,b,c;

scanf(〃%d,%d〃,&a,&b); c=a+b;

printf(\

数据结构源代码归纳(二)

2008年08月01日 星期五 23:46

第五章 多维数组和广义表 P77 三元组表

#define maxsize 100 /*定义非零元的最大数目*/ struct node /*定义一个三元组*/ {

int i , j; /*非零元行、列号*/ int v; /*非零元值*/ };

struct sparmatrix /*定义稀疏矩阵*/ {

int rows,cols ; /*稀疏矩阵行、列数*/ int terms; /*稀疏矩阵非零元个数*/ node data [maxsize]; /*三元组表*/ };

P79 十字链表的数据类型描述如下： struct linknode { int i, j;

struct linknode *cptr, *rptr;

union vnext /*定义一个共用体*/

{ int v; /*表结点使用V域,表示非零元值*/ struct linknode next; /*表头结点使用next域*/

} k; }

P81 （1）按照A的列序进行转置 #define maxsize 100 struct node {

int i,j; /*定义三元组的行、列号*/ int v; /*三元组的值*/ };

struct sparmatrix {

int rows,cols; /*稀疏矩阵的行、列数*/ int terms; /*稀疏矩阵的非零元个数*/

struct node data[maxsize]; /*存放稀疏矩阵的三元组表*/ };

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

for( i=0;i

void main() { int i;

struct sparmatrix a;

scanf(\输入稀疏矩阵的行、列数及非零元的个数*/

for( i=0;i

scanf(\输入转置前的稀疏矩阵的三元组*/

for(i=0;i

printf(\输出转置前的三元组结果*/

transpose( a); /*调用转置算法*/ }

P83 M稀疏矩阵的转置矩阵N的三元组表 #define maxsize 100 struct node { int i,j; int v; };

struct sparmatrix {

int rows,cols; int terms;

struct node data[maxsize]; };

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

col=a.data[t].j;

pot[col+1]=pot[col+1]+1; }

pot[0]=0;

for(col=1;col

for( ano=0;ano

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; } }

for( i=0;i

printf(\输出转置后的三元组*/ }

void main()

{ struct sparmatrix a; int i;

scanf(\输入稀疏矩阵的行、列数及非零元的个数*/

for( i=0;i

scanf(\输入转置前的三元组*/

for(i=0;i

printf(\输出转置前的三元组*/

fastrans(a); /*调用快速转置算法*/ }

P85第二步，生成表中结点。算法描述如下： #include #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(\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)) ;