# 数据结构(C语言版)第二章:数组与结构 原

fzyz_sb

``````#include <stdio.h>

#define MAX_SIZE 100
float sum( float [], int );
int i;
int main( void )
{
for ( i = 0; i < MAX_SIZE; i++ ){
input[ i ] = (float)i;
}
answer = sum( input, MAX_SIZE );
printf("the sum is: %f\n", answer );

return 0;
}

float sum( float list[], int n )
{
int i;
float tempSum = 0;
for ( i = 0; i < n; i++ ){
tempSum += list[ i ];
}

return tempSum;
}``````

1. 当数组作为参数传递进去的时候,只是将其地址传进去,所以我们无法获知数组的长度,需要将长度当作一个参数传递进去.

2. 良好的程序风格应该具有良好的编码,对齐等风格.

``````#include <stdio.h>
#include <string.h>

int main( void )
{
int arr[ 5 ];
int i = 0;
memset( arr, 0, sizeof( int ) * 5 );

for ( i = 0; i < 5; i++ ){
printf("0x%u:%d\n", arr + i, *( arr + i ) );
}

return 0;
}``````

2.2 结构与共用体

``````#include <stdio.h>

typedef struct PERSON{
char	name[ 10 ];
int		age;
float	salary;
}Person;

int main( void )
{
Person person1 = { "voler", 24, 3500 };
Person person2 = person1;

printf("name:%s  age:%d  salary:%.2f\n", person2.name, person2.age, person2.salary );

return 0;
}``````

1.

``````#include <stdio.h>

typedef struct LIST{
char				data;
}List;

int main( void )
{
List item1, item2, item3;
List *list = &item1;
item1.data = 'a';
item2.data = 'b';
item3.data = 'c';

while ( NULL != list ){
printf("%c-->", list->data );
}
printf("NULL\n");

return 0;
}``````

2.

``````#include <stdio.h>

typedef struct LIST{
char				data;
}List;

int main( void )
{
List *item1 = ( List * )malloc( sizeof( List ) );
List *item2 = ( List * )malloc( sizeof( List ) );
List *item3 = ( List * )malloc( sizeof( List ) );
List *list = item1;
item1->data = 'a';
item2->data = 'b';
item3->data = 'c';

while ( NULL != list ){
printf("%c-->", list->data );
}
printf("NULL\n");

free( item1 );
free( item2 );
free( item3 );

return 0;
}``````

``````#include <stdio.h>
#include <string.h>

typedef struct POLYNOMIAL{
float		coef;
int			expon;
}Polynomial;

#define MAX_TERMS 100

void padd( Polynomial [], Polynomial [], Polynomial [] );

int main( void )
{
Polynomial p1[ MAX_TERMS ], p2[ MAX_TERMS ], p[ MAX_TERMS ];
int i = 0;
memset( p1, 0, sizeof( Polynomial ) * MAX_TERMS );
memset( p2, 0, sizeof( Polynomial ) * MAX_TERMS );
memset( p, 0, sizeof( Polynomial ) * MAX_TERMS );

p1[ 0 ].coef = 2;
p1[ 0 ].expon = 1000;
p1[ 1 ].coef = 5;
p1[ 1 ].expon = 2;
p1[ 2 ].coef = 1;
p1[ 2 ].expon = 0;		//2x^1000 + 5x^2 + 1

p2[ 0 ].coef = 1;
p2[ 0 ].expon = 4;
p2[ 1 ].coef = 10;
p2[ 1 ].expon = 3;
p2[ 2 ].coef = 3;
p2[ 2 ].expon = 2;
p2[ 3 ].coef = 1;
p2[ 3 ].expon = 0;		//x^4 + 10x^3+3x^2+1

for ( i = 0; i < MAX_TERMS; i++ ){
if ( 0 == p[ i ].coef && 0 == p[ i ].expon ){
break;
}
printf("%.2fx^%d + ", p[ i ].coef, p[ i ].expon );
}

return 0;
}

void padd( Polynomial p1[], Polynomial p2[], Polynomial p[] )
{
while ( ( 0 != ( *p1 ).expon || 0 != ( *p1 ).coef ) && ( 0 != ( *p2 ).expon || 0 != ( *p2 ).coef ) ){
if ( ( *p1 ).expon > ( *p2 ).expon ){
*p = *p1;
p1++;
p++;
}else if ( ( *p1 ).expon < ( *p2 ).expon ){
*p = *p2;
p2++;
p++;
}else{
( *p ).coef = ( *p1 ).coef + ( *p2 ).coef;
( *p ).expon = ( *p1 ).expon;
p1++;
p2++;
p++;
}
}
while ( 0 != ( *p1 ).expon || 0 != ( *p1 ).coef ){
*p++ = *p1++;
}
while ( 0 != ( *p2 ).expon || 0 != ( *p2 ).coef ){
*p++ = *p2++;
}
}``````

``````#include <stdio.h>
#include <string.h>

#define MAX_TERMS 101
typedef struct TERM{
int		col;
int		row;
int		value;
}Term;

void transpose( Term [], Term [] );

void sortpose( Term [] );

int main( void )
{
Term a[ MAX_TERMS ], b[ MAX_TERMS ];
int i = 0;
memset( a, 0, sizeof( Term ) * MAX_TERMS );
memset( b, 0, sizeof( Term ) * MAX_TERMS );

a[ 0 ].col = 6;
a[ 0 ].row = 6;
a[ 0 ].value = 8;
a[ 1 ].col = 0;
a[ 1 ].row = 0;
a[ 1 ].value = 15;
a[ 2 ].col = 0;
a[ 2 ].row = 3;
a[ 2 ].value = 22;
a[ 3 ].col = 0;
a[ 3 ].row = 5;
a[ 3 ].value = -15;
a[ 4 ].col = 1;
a[ 4 ].row = 1;
a[ 4 ].value = 11;
a[ 5 ].col = 1;
a[ 5 ].row = 2;
a[ 5 ].value = 3;
a[ 6 ].col = 2;
a[ 6 ].row = 3;
a[ 6 ].value = -6;
a[ 7 ].col = 4;
a[ 7 ].row = 0;
a[ 7 ].value = 91;
a[ 8 ].col = 5;
a[ 8 ].row = 2;
a[ 8 ].value = 28;

transpose( a, b );
sortpose( b );

for ( i = 1; i <= b[ 0 ].value; i++ ){
printf("(%d,%d):%d\n", b[ i ].col, b[ i ].row, b[ i ].value );
}

return 0;
}

void transpose( Term a[], Term b[] )
{
int i = 0;
b[ 0 ].col = a[ 0 ].row;
b[ 0 ].row = a[ 0 ].col;
b[ 0 ].value = a[ 0 ].value;

for ( i = 1; i <= a[ 0 ].value; i++ ){
b[ i ].col = a[ i ].row;
b[ i ].row = a[ i ].col;
b[ i ].value = a[ i ].value;
}
}

void swap( Term *a, Term *b )
{
Term temp;
temp = *a;
*a = *b;
*b = temp;
}

void sortpose( Term b[] )
{
int i = 0;
int j = 0;
for ( i = 1; i < b[ 0 ].value; i++ ){
for ( j = i + 1; j <= b[ 0 ].value; j++ ){
if ( b[ i ].col > b[ j ].col ){
swap( &b[ i ], &b[ j ] );
}
}
}
}``````

1. 程序块的功能越简单越好.我封装的两个函数,一个用来倒置,一个用来排序.

2. 这样更容易扩展,如果程序要求以value的顺序排序,我只要修改一行代码即可(if那条判断比较语句)

``````#include <stdio.h>
#include <string.h>

#define MAX_TERMS 101
typedef struct TERM{
int		col;
int		row;
int		value;
}Term;

void fast_transpose( Term [], Term [] );

int main( void )
{
Term a[ MAX_TERMS ], b[ MAX_TERMS ];
int i = 0;
memset( a, 0, sizeof( Term ) * MAX_TERMS );
memset( b, 0, sizeof( Term ) * MAX_TERMS );

a[ 0 ].col = 6;
a[ 0 ].row = 6;
a[ 0 ].value = 8;
a[ 1 ].col = 0;
a[ 1 ].row = 0;
a[ 1 ].value = 15;
a[ 2 ].col = 0;
a[ 2 ].row = 3;
a[ 2 ].value = 22;
a[ 3 ].col = 0;
a[ 3 ].row = 5;
a[ 3 ].value = -15;
a[ 4 ].col = 1;
a[ 4 ].row = 1;
a[ 4 ].value = 11;
a[ 5 ].col = 1;
a[ 5 ].row = 2;
a[ 5 ].value = 3;
a[ 6 ].col = 2;
a[ 6 ].row = 3;
a[ 6 ].value = -6;
a[ 7 ].col = 4;
a[ 7 ].row = 0;
a[ 7 ].value = 91;
a[ 8 ].col = 5;
a[ 8 ].row = 2;
a[ 8 ].value = 28;

fast_transpose( a, b );

for ( i = 1; i <= b[ 0 ].value; i++ ){
printf("(%d,%d):%d\n", b[ i ].col, b[ i ].row, b[ i ].value );
}

return 0;
}

void fast_transpose( Term a[], Term b[] )
{
int		row_terms[ MAX_TERMS ], starting_post[ MAX_TERMS ];
int		i, j, num_cols = a[ 0 ].col, num_terms = a[ 0 ].value;
b[ 0 ].row = num_cols;
b[ 0 ].col = a[ 0 ].row;
b[ 0 ].value = num_terms;

if ( num_terms > 0 ){
for ( i = 0; i < num_cols; i++ ){
row_terms[ i ] = 0;
}
for ( i = 1; i <= num_terms; i++ ){
row_terms[ a[ i ].col ]++;
}
starting_post[ 0 ] = 1;
for ( i = 1; i < num_cols; i++ ){
starting_post[ i ] = starting_post[ i - 1 ] + row_terms[ i - 1 ];
}
for ( i = 1; i <= num_terms; i++ ){
j = starting_post[ a[ i ].col ]++;
b[ j ].row = a[ i ].col;
b[ j ].col = a[ i ].row;
b[ j ].value = a[ i ].value;
}
}
}``````

2.5 多维数组

``````#include <stdio.h>

int main( void )
{
int a[ 20 ];
int *b = NULL;
int i = 0;
for ( i = 0; i < 20; i++ ){
a[ i ] = i;
}
b = a + 10;
for ( i = -10; i < 10; i++ ){
printf("%d ", *( b + i ) );
if ( 0 == ( ( i + 11 ) % 5 ) ){
printf("\n");
}
}

return 0;
}``````

``````#include <stdio.h>

int main( void )
{
char *s1 = "hello world";
char s2[] = { "hello world" };

s2[ 1 ] = 'a';
s1[ 1 ] = 'a';

printf("%s\n", s1 );
printf("%s\n", s2 );

return 0;
}``````

``````#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE 100
void strnins( char *s, char *t, int i );

int main( void )
{
char str1[MAX_SIZE] = "amobile";
char str2[MAX_SIZE] = "uto";
strnins( str2, str1, 1 );

printf("%s\n", str1 );

return 0;
}

void strnins( char *s, char *t, int i )
{
char *begint = ( char * )malloc( sizeof( char ) * MAX_SIZE );
char *result = t;
strcpy( begint, t );
while ( i-- ){
result++;
begint++;
}
while ( *s ){
*result++ = *s++;
}
while ( *begint ){
*result++ = *begint++;
}
*result = '\0';
}``````

``char str[ MAX_SIZE ], *temp = str;``

2.6.2 模式匹配

``````#include <stdio.h>
#include <string.h>

int main( void )
{
char *str1 = "hello world";
char *str2 = "wor";
char *str3 = "worr";

if ( strstr( str1, str2 ) ){
printf("str2 in str1\n");
}
else{
printf("str2 not in str1\n");
}

if ( strstr( str1, str3 ) ){
printf("str3 in str1\n");
}
else{
printf("str3 not in str1\n");
}

return 0;
}``````

``````#include <stdio.h>
#include <string.h>

int nfind( char *string, char *pat );
int main( void )
{
char *str1 = "hello world";
char *str2 = "wor";
char *str3 = "worr";

if ( nfind( str1, str2 ) ){
printf("str2 in str1\n");
}
else{
printf("str2 not in str1\n");
}

if ( nfind( str1, str3 ) ){
printf("str3 in str1\n");
}
else{
printf("str3 not in str1\n");
}

return 0;
}

int nfind( char *string, char *pat )
{
char *tempString = string;
char *tempPat = pat;
int lenPat = strlen( pat );
while ( *( string + lenPat ) ){
while ( *string == *pat && *pat ){
string++;
pat++;
}
if ( !*pat ){
return string - tempString;
}
else{
pat = tempPat;
}
string++;
}

return 0;
}``````

``````void fail( char *pat )
{
int i = 0;
int j = 0;
int n = strlen( pat );
failure[ 0 ] = -1;
for ( j = 1; j < n; j++ ){
i = failure[ j - 1 ];
while ( ( pat[ j ] != pat[ i + 1 ] ) && ( i >= 0 ) )
i = failure[ i ];
if ( pat[ j ] == pat[ i + 1 ] )
failure[ j ] = i + 1;
else
failure[ j ] = -1;
}
}``````

``````#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100
int failure[ MAX_SIZE ];

void fail( char *pat );
int pmatch( char *string, char *pat );

int main( void )
{
int count = 0;

count = pmatch( "hello world", "wor" );
printf("%d\n", count );
count = pmatch( "hello world", "worr" );
printf("%d\n", count );
count = pmatch( "aaabb", "aabb" );
printf("%d\n", count);

return 0;
}

int pmatch( char *string, char *pat )
{
int i = 0, j = 0;
int lens = strlen( string );
int lenp = strlen( pat );
fail( pat );
while ( i < lens && j < lenp ){
if ( string[ i ] == pat[ j ] ){
i++;
j++;
}
else if ( 0 == j ){
i++;
}
else{
j = failure[ j - 1 ] + 1;
}
}

return (  ( j == lenp ) ? ( i - lenp ) : -1 );
}
void fail( char *pat )
{
int i = 0;
int j = 0;
int n = strlen( pat );
failure[ 0 ] = -1;
for ( j = 1; j < n; j++ ){
i = failure[ j - 1 ];
while ( ( pat[ j ] != pat[ i + 1 ] ) && ( i >= 0 ) )
i = failure[ i ];
if ( pat[ j ] == pat[ i + 1 ] )
failure[ j ] = i + 1;
else
failure[ j ] = -1;
}
}``````

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*

*/
void frequency( char *s, int *arr );
int main( void )
{
int arr[ 26 ];
int i = 0;
int ch = 'a';
memset( arr, 0, sizeof( int ) * 26 );

frequency( "hello world", arr );
for ( i = 0; i < 26; i++ ){
printf("%c-->%d  ", ch, arr[ i ] );
ch++;
if ( ( i + 1 ) % 5 == 0 ){
printf("\n");
}
}

}

void frequency( char *s, int *arr )
{
while ( *s ){
arr[ *s - 'a' ]++;
s++;
}
}``````

2. 删除子字符串

``````#include <stdio.h>
#include <string.h>

void strndel( char *str, int start, int length );
int main( void )
{
char str[] = "hello world";
strndel( str, 2, 3 );

printf("%s\n", str );

return 0;
}

void strndel( char *str, int start, int length )
{
char *tempStr = str;
while ( start-- ){
tempStr++;
str++;
}
while ( length-- && *str ){
str++;
}
while ( *str ){
*tempStr++ = *str++;
}
*tempStr = '\0';
}``````

3. 删除特定字符后面的字符串

``````#include <stdio.h>
#include <string.h>

char *strdel( char *s, char ch );

int main( void )
{
char *str = "hello world";
printf("%s\n", strdel( str, 'l' ) );

return 0;
}

char *strdel( char *s, char ch )
{
while ( *s != ch && *s ){
s++;
}

return s;
}``````

4. 字符首次出现位置的索引:

``````#include <stdio.h>
#include <string.h>

int strpos1( char *str, char ch );

int main( void )
{
char *str = "hello world";
printf("%d\n", strpos1( str, 'l' ) );
printf("%d\n", strpos1( str, 'm' ) );

return 0;
}

int strpos1( char *str, char ch )
{
char *tempStr = str;
while ( *str != ch && *str ){
str++;
}

if ( *str ){
return str - tempStr;
}

return -1;
}``````

### fzyz_sb

Linux C编程如何使用联机帮助来解决编程问题?

1.背景 多次学习C语言一直无法踏入C语言的大门，每次都是在学习C语言中的那些系统调用库函数等望而却只，linux下的系统调用需要我们去记忆一些没有规律的结构体和一些大写的宏定义并且还有一...

Jeff_Linux
2014/07/06
0
0

2017/11/07
0
0

20111564
2014/10/16
0
0

2015/10/16
28
0

2016/02/04
107
2

ps -ef | grep keyword | grep -v grep | awk '{print \$2}' | xargs kill -9 逐个分析: 1, ps -ef | grep keyword: 查出进程名含有 keyword 的所有进程; 2, grep -v grep: 从这些结果里面，把......

vinci321
24分钟前
0
0
nginx的简单使用：负载均衡

nginx：反向代理的服务器；用户发送请求到nginx，nginx把请求发送给真正的服务器，等待服务器处理完数据并返回，再把数据发送给用户。 nginx作为一个反向代理服务器，能缓存我们项目的静态文...

osliang
40分钟前
2
0

42分钟前
1
0
JDK版本与major.minor version的对照关系

44分钟前
1
0
C++基础教程面向对象学习笔记及心得感悟[图]

C++基础教程面向对象学习笔记及心得感悟[图] 使用友元函数重载算术运算符： C ++中一些最常用的运算符是算术运算符 - 即加号运算符（+），减运算符（ - ），乘法运算符（*）和除法运算符（/...

53分钟前
1
0