《[高等教育]《软件开发技术基础》第二章C语言版算法整理.doc》由会员分享，可在线阅读，更多相关《[高等教育]《软件开发技术基础》第二章C语言版算法整理.doc（32页珍藏版）》请在三一文库上搜索。
1、线性结构一、 线性表、顺序表1、顺序表类型描述 struct SeqList ElemType *data; / 顺序表存储数组的地址 int maxsize; / 顺序表最大允许长度 int length; / 顺序表当前长度 SeqList； / 定义一个线性表SeqList （1）ElemType代表数组的类型。（2）数组data需要在初始化函数中利用malloc操作动态申请，maxsize为其长度。数组的下标从0开始。（3）length表示线性表当前长度，初始长度为0（空表），最大不超过maxsize。顺序表的主要算法 2、顺序表的主要算法（1）顺序表的初始化顺序表的初始化主要是为El
2、emType类型的数组申请空间，下面的初始化函数为顺序表申请了长度为size的空间。void Init( struct Seqlist *L, int size )if ( size 0 )L-maxsize = size;L-length = 0;L-data = ( ElemType *)malloc( size*sizeof( ElemType ) ); else printf( 线性表初始化长度错误!n );（2）在顺序表中第i个位置插入新元素x void InsertList( struct Seqlist *L, int i, ElemType x)int j;if ( i L-l
3、ength+1 | L-length = L-maxsize )printf( 插入位置错误或表满!n );else for( j = L-length-1 ; j = i-1 ; j-) L-dataj+1= L-dataj; /元素依次后移L-datai-1= x; /向第 i 个位置存入新元素 xL-length+; /表长度加一（3）在顺序表中删除第i个元素 void Delete( SeqList *L, int i ) int j; if(i L-length ) print(表中没有第%d个元素, i );else for(j = i; j length-1; j+ ) L-da
4、taj-1 = L-dataj; L-length -; （4）在顺序表中查找某个元素 （按内容查找）int LocateLise( SeqList *L, ElemType x ) int i;for(i = 0; i length; i+ ) if( L-datai = x ) return i+1; /查找成功，返回元素位置return 0; /查找失败，返回 03、顺序表的举例应用/例2-1一元多项式相加#include #include typedef struct double coef; int exp;multi;struct Seqlist multi *data;int m
5、axsize;int length;L1,L2,L3;void Init( struct Seqlist *L, int size )if ( size 0 )L-maxsize = size;L-length =0;L-data = ( multi *)malloc( size*sizeof( multi) ); else printf( the size of Seqlist is an error!n );void Insert( struct Seqlist *L, int i, double coef, int exp )int j;if ( i L-length+1 | L-len
6、gth=L-maxsize ) printf( the place you insert is an error!n );else for ( j = L-length-1 ; j = i-1 ; j-)L-dataj+1.coef = L-dataj.coef; L-dataj+1.exp = L-dataj.exp;L-datai-1.coef = coef;L-datai-1.exp = exp;L-length+;void display( struct Seqlist *L)int i;for( i=0; i length-1; i+)printf( %f,L-datai.coef
7、);if( L-datai.exp 0 )printf( x%d,L-datai.exp ); if( i length-1 )printf( + );printf(n);void main ()int i=1,j=1,k=1,t; double c;Init( &L1,3 );Init( &L2,3 );Init( &L3,10) ;Insert( &L1, 1, 3.5, 0 );Insert( &L1, 2, 4, 2 );Insert( &L1, 3, 2.5, 4 );Insert( &L2, 1, 1.5, 1 );Insert( &L2, 2, 2.6, 2 );Insert(
8、&L2, 3, 1.6, 3 );printf( L1(x)= ); display( &L1 );printf( L2(x)= );display( &L2 ); while( i = L1.length & j = L2.length ) if( L1.datai-1.exp L2.dataj-1.exp ) Insert( &L3, k, L2.dataj-1.coef, L2.dataj-1.exp ); j+;else if( L1.datai-1.exp = L2.dataj-1.exp ) c = L1.datai-1.coef + L2.dataj-1.coef; t = L1
9、.datai-1.exp; if( c!=0 ) Insert( &L3, k, c, t );i+;j+; k+;while( i = L1.length )Insert( &L3, k, L1.datai-1.coef, L1.datai-1.exp );i+;k+;while( j next = NULL.2、单链表的基本算法(带头结点的单链表)（1）求单链表的长度为了保持头指针不变，使用了指针p在链表中移动。int Length( LinkList head )ListNode *p = head-next ; /p指向第一个元素所在结点int len=0 while( p != NU
10、LL ) /逐个检测p结点存在与否 len+;p = p-next; /指针后移return len; (2)返回单链表中指定序号的结点的指针ListNode *Get( LinkList head ,int pos ) /得到位于pos处的结点指针if( pos next;while( p != NULL & k next;k+; if( p != NULL & k = pos ) return p; else return NULL; （3）从单链表中删除第i个结点void Delete( LinkList head, int i )if ( i 0 ) printf( 不存在第%d个元素
11、！n,i );else ListNode *p = head; /p指向头结点(第0个结点)ListNode *q; /q和p最终分别指向第i-1和第i个结点int k = 0;while( p != NULL & k next;k+;if( p = NULL ) printf( %d超出链表长度！n );elseq-next = p-next; free( p ); /从链表中删除该结点，并释放结点p（4）在第i个位置插入新结点xvoid Insert( LinkList head, int i, ElemType x )if ( i 1 ) printf( 不存在第%d个位置！n, i )
12、;else ListNode *p = head; /p最终将指向第i-1个结点int k = 0; /p目前指向第0个结点(头结点)while( p != NULL & k next;k+;if ( p = NULL ) printf( %d超出链表的最大位置！n, i );elseListNode *s = ( ListNode * )malloc( sizeof( ListNode ) );s-data = x;s-next = p-next;p-next = s;（5）在单链表中查找数据值为x的结点ListNode *Find( LinkList head, ElemType x )
13、ListNode *p = head-next; /p指向第一个元素所在结点 while( p != NULL & p-data != x ) p = p-next; return p; 3、单链表的举例应用/例2-2约瑟夫环#include #include #include typedef struct LNodeint data;struct LNode *next;LNode;void Insert( LNode *head, int i, int x )if ( i1 )printf( 不存在第%d个位置！n,i );else LNode *p = head;int k = 0;wh
14、ile( p != NULL & knext; k+;if ( p = NULL ) printf( %d超出链表的最大位置！n,i );elseLNode *s = ( LNode * )malloc( sizeof( LNode ) );s-data = x;s-next = p-next; p-next = s;void Delete( LNode *head, int i )if ( i 0 ) printf( 不存在第%d个元素！n,i );else LNode *p = head;LNode *q; int k = 0;while( p != NULL & k next;k+;if
15、( p = NULL ) printf( %d超出链表长度！n );else q-next = p-next; free( p );int main()LNode *head,*p,*t;int n,s,m;int i,j;head = ( LNode *)malloc( sizeof( LNode ) );head-next = head;printf( 请输入元素的总数、开始计数的整数以及间隔数:n );scanf( %d%d%d,&n,&s,&m );for( i = 1; i 0 & s = n )for( i = 0; i next;elseprintf( 起始计数位置错误！n );
16、printf( 出列顺序为:n );for( i = 1; i = n; i+ )for( j = 1; j next;if( p = head ) p = p-next;t = p-next;if( t = head )p = t;t = t-next;printf( %d ,t-data ); p-next = t-next;free( t );printf( n ); return 0;二、栈、顺序栈1、顺序栈的类型描述typedef struct ElemType *data; /存储元素的数组int top; /栈顶指针，存储栈顶元素下标int stacksize; /最大可用空间数
17、量 SeqStack;一般将数组的0下标单元作为栈底，将栈顶元素的下标存储在栈顶指针top中，它随着元素进栈出栈而变化。top为-1表示空栈，top等于stacksize-1则表示栈满。2、顺序栈的基本算法（1）顺序栈初始化堆栈的初始化主要是为存储元素的数组申请空间，下面的初始化函数申请了长度为size的空间。void InitStack( SeqStack *s, int size)if( size 0 ) s-stacksize = size; s-top = -1;s-data = (ElemType *)malloc( size * sizeof(ElemType) ); elsepr
18、intf( 堆栈初始化长度错误!n ); （3） 进栈操作 若栈不满，则在栈顶插入元素x作为新的栈顶void PushStack( SeqStack *s, ElemType x)if( s-top stacksize - 1) s-top+;s-datas-top = x;else printf( 栈满!n );（4） 出栈操作 若栈不空，则删除s的栈顶元素，用e返回其值void PopStack( SeqStack *s, ElemType *e) if ( s-top -1) *e = s-data s-top ;s-top-;else printf(栈空!n);（4）取栈顶元素 若栈不
19、空，则用e返回s的栈顶元素void GetTop( SeqStack *s, ElemType *e)if( s-top -1) *e = s-data s-top ;else printf( 栈空!n );链式栈1、链式栈的类型描述typedef struct nodeElemType data; /数据域struct node *next; /指针域 SNode, *LinkStack;LinkStack top； /定义栈顶指针（1）SNode用来定义结点，LinkStack用来定义栈顶指针。 （2）链栈通过链表实现，链表的第一个结点为栈顶,最后一个结点为栈底。2、链式栈的基本算法（1）
20、进栈操作 若栈不满，则在栈顶插入元素x作为新的栈顶。void PushStack( LinkStack top, ElemType x)SNode *p=( SNode *)malloc( sizeof(SNode) ); if( p != NULL)p-data = x ;p-next = top ;top = p ;（2）出栈操作 若栈不空，则删除栈顶元素，用e返回其值。void PopStack( LinkStack top, ElemType *e);SNode *p ;if( top != NULL)*e = top-data ;p = top ;top = top-next ;fr
21、ee( p );3、栈的举例应用/例2-3 表达式求值#include #include #include struct SqStackdouble *data;/存储元素的数组int top; /栈顶指针，存储栈顶元素的下标int stacksize; /堆栈最大可分配空间数量，以元素为单位;void InitStack(SqStack &s, int size ) / 初始化if( size 0 ) s.stacksize = size; s.top = -1;s.data = ( double *)malloc( sizeof(double) );/ 申请空间else printf(堆栈
22、初始化长度错误!n); void Push(SqStack &s, double x) / 入栈if( s.top -1) e= s.datas.top;s.top-;else printf(栈空);int main()SqStack T;/定义一个堆栈double a,b,c,d;int i;char exp20;/存储表达式的数组，最长20个字符double num1,num2;printf(依次输入a、b、c、d的值：);scanf( %f%f%f%f,&a,&b,&c,&d);/输入a,b,c,d的数值printf(输入表达式：);scanf( %s,&exp );/输入a,b,c,d
23、组成的表达式InitStack(T, 20);/堆栈初始化/ 处理字符数组，计算后缀表达式for( i=0; expi!=0; i+) switch ( expi ) case + :case - : case * :case / :Pop(T,num2);Pop(T,num1);if(expi=+)Push(T,num1+num2);if(expi=-)Push(T,num1-num2);if(expi=*)Push(T,num1*num2);if(expi=/)Push(T,num1/num2);break; default : if(expi=a)Push(T,a);if(expi=b)
24、Push(T,b);if(expi=c)Push(T,c);if(expi=d)Push(T,d);Pop(T,num1);printf(结果为：%fn,num1);return 0;四、 队列循环队列1、循环队列类型描述struct SeqQueueElemType *data; / 存放元素的数组int length; / 数组空间总长度 int front; / 队头指针int rear; / 队尾指针;SeqQueue q; / 定义队列q（1）front和rear指针取值均为所指数组单元的下标。（2）由于队头指针所指单元总是空的，length比实际能存储的元素多一。 （3）队空条件为
25、front = rear，队满条件为(rear+1)%length = front2、循环队列的主要算法（1）循环队列初始化建立数组空间并将队头、队尾指针设定到0号单元。void InitQueue( SeqQueue *Q, int size ) Q-length = size+1; Q-front = Q-rear = 0; Q-data = ( ElemType *)malloc( Q-length * sizeof(ElemType) ); （2）入队操作若队列不满，则在队尾插入元素x作为新的队尾。void EnQueue( SeqQueue *Q , ElemType x ) if(
26、 (Q-rear+1)%Q-length = Q-front ) printf( 队列已满!n );else Q-rear = ( Q-rear+1 )%Q-length;Q-data Q-rear = x;（3）出队操作若队列不空，则删除队头元素并用e取回该元素的值。void DeQueue( SeqQueue *Q, ElemType *e ) if( Q-rear = Q-front ) printf(队列已空!n);else *e = Q-data Q-front ; Q-front = ( Q-front +1 )%Q-length;（4）取队头元素 若队列不空，则用e取回队头元素的
27、值。void GetHead( SeqQueue *Q, ElemType *e)int i ;if( Q-rear = Q-front ) printf(队列已空!n);else i = ( Q-front +1 )%Q-length;*e = Q-datai;链队列1、链队列结点可定义：struct QNode ElemType data;struct QNode *next;另外，链队列有两个指针，可以分别定义，也可采用下面定义。struct LinkQueue QNode *front;/ 队头指针QNode *rear; / 队尾指针;2、链队列的主要算法（1）链队列初始化 建立一个
28、含有头结点的空的链队列。void InitQueue( LinkQueue *Q )Q-front = ( QNode * )malloc( sizeof( QNode ) ); /建立头结点Q-front-next = NULL;Q-rear = Q-front; /尾指针也指向头结点（2）求队列的长度返 回队列的元素个数，即队列的长度。int QueueLength( LinkQueue *Q ) QNode *p = Q-front;int len = 0;while( p != Q-rear )len+;p = p-next;return len; （3）入队列操作 插入元素x为队列新
29、的队尾元素。void EnQueue( LinkQueue *Q, ElemType x ) QNode *s = ( QNode * )malloc( sizeof( QNode ) ); /建立新结点ss-data = x;s-next = NULL;Q-rear-next = s;/在队尾插入结点sQ-rear = s; /修改队尾指针（4）出队列操作 若队列不空，则删除队头元素，用e返回其值。void DeleteQueue( LinkQueue *Q, ElemType *e ) QNode *p;if( Q-front = Q-rear )printf(队列已空!n);else p
30、 = Q-front-next;*e = p-data;Q-front-next = p-next;if( Q-rear = p ) Q-rear = Q-front; /修改尾指针，使其指向头结点。free( p );（5）取队头元素 若队列不空，则用e返回队头元素void GetHead( LinkQueue *Q, ElemType *e ) QNode *p;if( Q-front = Q-rear ) printf(队列已空!n);else p = Q-front-next;*e = p-data;3、队列的举例应用/例2-4 利用循环队列求k阶斐波那切数列某一式的值#include
31、 #include #include struct SqQueueint *data;/ 存放元素的数组int length;/ 数组空间总长度 int front; / 队头指针int rear; / 队尾指针;void InitQueue(SqQueue &Q, int sz ) / 队列初始化 Q.length = sz+1; Q.front = Q.rear = 0; Q.data = (int *)malloc( sizeof( int ) ); void EnQueue(SqQueue &Q , int x) / 入队列if(Q.rear+1)% Q.length= Q.front
32、) printf(队列已满);else Q.rear = (Q.rear+1)%Q.length;Q.dataQ.rear=x;void DeQueue(SqQueue &Q, int &e) / 出队列if(Q.rear=Q.front) printf(队列已空);else Q.front = (Q.front +1)% Q.length;e= Q.dataQ.front;int main()SqQueue Q;int k,m,r,tmp,i,j;printf(输入斐波那切数列的阶数及需要计算哪一项的值：);scanf( %d%d,&k,&m );while(k=m) printf( 要求阶
33、数k小于待计算项的位置m ! );scanf( %d%d,&k,&m );InitQueue(Q, k); for(i=0;ik-1;i+) EnQueue(Q,0);/前k-1项为0EnQueue(Q,1);/第k项为1for(i=0;im-k;i+) r=0;for(j=0;jleftChild ); /遍历左子树 PreOrder( t-rightChild ); /遍历右子树 非递归算法void PreOrder( BinTreeNode *t )BinTree stackMaxsize ; /定义一个栈，用于存放结点指针int top ;BinTreeNode *p ; /定义一个结点指针top = 0 ;p = t ;while( p !=