链表new1# include <stdio.h># include <malloc.h># include <stdlib.h>struct node{int data; //存放数据本身struct node *next;};struct node *CreateList( void ){struct node *pH = NULL;int len; //存放节点的个数int i;int temp; //存放用户暂时存入的节点的值域的值struct node *pNew = NULL;//存放临时分配好的节点本身的内容struct node *pTail = NULL;//pTail永远指向链表的尾节点//创建一个头节点pH = ( struct node * )malloc( sizeof( struct node ) );if( NULL == pH ){puts( "动态内存分配失败" );exit( -1 );}pH ->next = NULL;pTail = pH;printf( " 请输入节点的个数:len = " );scanf( " %d ", &len );for( i = 0; i < len; ++ i ){printf( " 请输入第%d 节点的值: ", i + 1 );scanf( " %d ", &temp );//临时构造一个节点pNew = ( struct node * )malloc( sizeof( struct node ) );if( NULL == pNew )//如果p所指向的节点存在{}}}int main ( void ){struct node *pH = NULL;pH = CreateList();//通过CreateList()函数创建一个链表,j将该链表的首地址发松给pH TraverseList( ph );//遍历整个单链表return 0;}跨函数使用内存malloc//2012年9月9日晚上# include <stdio.h># include <malloc.h>struct Student{int sid;int age;};struct Student *CreateStudent( void );void ShowStudent( struct Student * );int main( void ){struct Student *ps;ps = CreateStudent();ShowStudent( ps );return 0;}struct Student *CreateStudent( void ){struct Student *p = ( struct Student * )malloc( sizeof( struct Student ) );p->sid = 99;p->age = 88;return p;void ShowStudent( struct Student *pst ){printf( " %d %d\n ", pst->sid, pst->age );}快速排序# include <stdio.h>void QuickSort( int *a, int low, int high );int FindPos( int *a, int low, int high );int main( void ){int a[6] = { 2, 1, 0, 5, 4, 3 };int i;QuickSort( a, 0, 5 );//第二个参数表示第一个元素的下标,第三个参数表示最后一个元素的下标for( i = 0; i < 6; ++ i )printf( "%d ", a[i] );printf( "\n" );return 0;}void QuickSort( int *a, int low, int high ){int pos;if( low < high ){pos = FindPos( a, low, high );QuickSort( a, low, pos - 1 );QuickSort( a, pos + 1, high );}}int FindPos( int *a, int low, int high ){int val = a[low];while( low < high ){while( low < high && a[high] > val )-- high;a[low] = a[high];while( low < high && a[low] <= val )++ low;a[high] = a[low];}//终止while循环之后low和high一定相等的a[low] = val;return low;//或者return high;}连续存储数组的算法1//2012年9月10日晚上# include <stdio.h># include <malloc.h># include <stdlib.h>//使用exit( -1 );需要定义的头文件//定义了一个数据类型,没有定义变量struct Arr{int *pBase;//存储的是数组第一个元素的地址int len;//数组所能容纳的最大元素的个数int cnt;//当前所在有效的个数};void init_arr( struct Arr *pArr, int length );//分号不能省bool append_arr();//追加bool insert_arr();bool delete_arr();int get();bool is_empty( struct Arr *pArr );bool is_full();bool sort_arr();void sort_arr();void show_arr( struct Arr *pArr );void inversion_arr();int main( void ){struct Arr arr;init_arr( &arr, 6 );//地址只占四个字节show_arr( &arr );//printf( " %d\n ", arr.len );return 0;}void init_arr( struct Arr *pArr, int length ){pArr->pBase = ( int * )malloc( sizeof( int )*length );//pArr->len = 99;if( NULL == pArr->pBase ){printf( "动态内存分配失败!\n" );exit( -1 );//终止整个程序}else{pArr->len = length;pArr->cnt = 0;}return;}bool is_empty( struct Arr *pArr ){if( 0 == pArr->cnt ){return true;}elsereturn false;}void show_arr( struct Arr *pArr ){/*if( 数组为空)提示用户数组为空else输出数组有效内容*/if( is_empty( pArr ) )printf( "数组为空!\n" );}else{for( int i = 0; i < pArr->cnt; ++i )printf( " %d ", pArr->pBase[i] );printf( "\n" );}}连续存储数组的算法2//2012年9月11日早上# include <stdio.h># include <malloc.h># include <stdlib.h>//使用exit( -1 );需要定义的头文件//定义了一个数据类型,没有定义变量struct Arr{int *pBase;//存储的是数组第一个元素的地址int len;//数组所能容纳的最大元素的个数int cnt;//当前所在有效的个数};void init_arr( struct Arr *pArr, int length );//分号不能省bool append_arr( struct Arr *pArr, int val );//追加bool insert_arr( struct Arr *pArr, int pos, int val );//pos的值从1开始bool delete_arr( struct Arr *pArr, int pos, int *pVal );int get();bool is_empty( struct Arr *pArr );bool is_full( struct Arr *pArr );void sort_arr( struct Arr *pArr );void show_arr( struct Arr *pArr );void inversion_arr( struct Arr *pArr );//倒置int main( void ){struct Arr arr;int val;init_arr( &arr, 6 );//地址只占四个字节show_arr( &arr );append_arr( &arr, 1 );append_arr( &arr, 2 );append_arr( &arr, 3 );append_arr( &arr, 4 );if ( delete_arr( &arr, 1, &val ) ){printf("删除成功\n");printf("你删除的元素是:%d\n", val);}elseprintf("删除失败\n");/*append_arr( &arr, 2 );append_arr( &arr, 3 );append_arr( &arr, 4 );append_arr( &arr, 5 );insert_arr( &arr, 6, 99 );append_arr( &arr, 6 );append_arr( &arr, 7 );//这个也是追加不成功的,因为是只是分配了6个数if( append_arr( &arr, 8 ) ){printf( "追加成功\n" );}else{printf( "追加失败\n" );}*/show_arr( &arr );inversion_arr( &arr );printf("倒置之后的内容是:\n");show_arr( &arr );sort_arr( &arr ); //呜呜,这里哪里是出错了呢??printf("排列\n");show_arr( &arr );//printf( " %d\n ", arr.len );return 0;}void init_arr( struct Arr *pArr, int length ){pArr->pBase = ( int * )malloc( sizeof( int )*length );//pArr->len = 99;if( NULL == pArr->pBase ){printf( "动态内存分配失败!\n" );exit( -1 );//终止整个程序}else{pArr->len = length;pArr->cnt = 0;}return;}bool is_empty( struct Arr *pArr ){if( 0 == pArr->cnt ){return true;}elsereturn false;}bool is_full( struct Arr *pArr ){if( pArr->cnt == pArr->len )return true;elsereturn false;}void show_arr( struct Arr *pArr ){/*if( 数组为空)提示用户数组为空else输出数组有效内容*/if( is_empty( pArr ) ){printf( "数组为空!\n" );}else{for( int i = 0; i < pArr->cnt; ++i )printf( " %d ", pArr->pBase[i] );printf( "\n" );}}bool append_arr( struct Arr *pArr, int val ){//满时返回falseif( is_full( pArr ) )return false;//不满时追加elsepArr->pBase[pArr->cnt] = val;( pArr->cnt ) ++;return true;}bool insert_arr( struct Arr *pArr, int pos, int val ){int i;//第一中情况,数组里面全满时if( is_full( pArr ) )return false;//第二种情况,数组里面不为满时if( pos < 1 || pos > pArr->cnt + 1 )return false;//把原来的第pos的位置和之后的数都向前移动for( i = pArr->cnt - 1; i >= pos - 1; --i ){pArr->pBase[i + 1] = pArr->pBase[i];}//把第pos位置插入新的值pArr->pBase[pos - 1] = val;( pArr->cnt ) ++;//个数加一return true;}bool delete_arr( struct Arr *pArr, int pos, int *pVal ){int i;if( is_empty( pArr ) )return false;if( pos < 1 || pos > pArr->cnt )return false;*pVal = pArr->pBase[pos - 1];for( i = pos; i < pArr->cnt; ++i ) //cnt表示数组有效的个数{pArr->pBase[i - 1] = pArr->pBase[i]; //这里要前移一个数,所以上面的可以i <= pArr->cnt - 1}pArr->cnt --; //删除了一个数组个数,所以有效个数要相应的减一return true;}void inversion_arr( struct Arr *pArr ){int i = 0;int j = pArr->cnt - 1;int t;while( i < j ){t = pArr->pBase[i];pArr->pBase[i] = pArr->pBase[j];pArr->pBase[j] = t;++ i;-- j;}return;}void sort_arr( struct Arr *pArr ){int i, j, t;for( i = 0; i < pArr->cnt; ++i ){for( j = j + 1; j < pArr->cnt; ++ j ){if( pArr->pBase[i] > pArr->pBase[j] ){t = pArr->pBase[i];pArr->pBase[i] = pArr->pBase[j];pArr->pBase[j] = t;}}}}链表//2012年9月12日早上离散存储[链表]定义:n个节点离散分配彼此通过指针相连每个节点只有一个前驱节点,每个节点只有后续节点首节点没有前驱节点,尾节点没有后续节点术语:首节点:第一个有效的节点尾节点:最后一个有效的节点头节点:头节点额数据类型和首节点类型一样首节点前一个没有存放有效数据加头节点的目的主要是为了方便链表的操作头指针:指向头节点的指针变量尾指针:指向尾节点的指针如果希望通过一个函数来对链表进行处理,我们至少需要接受链表的哪些参数因为我们通过头指针可以推算出链表的其他信息分类:单链表双链表:每一个节点有两个指针域循环链表:能通过任何一个节点找到所有的节点非循环链表算法:遍历查找清空销毁求长度排序删除节点插入节点typedef struct node{int data;struct node *pNext;}NODE, *PNODE;PNODE p = ( PNODE )malloc( sizeof( NODE ) );free( p );//删除p指向节点所占的内存,不是删除p本身所占的内存p->pNext;//p所指向结构体变量中的pNext成员本身删除p所节点的后面节点先临时定义一个指向p后面节点的指针rr = p->pNext;//r所指向后面的那个节点p->pNext = r->pNext;free(r);链表创建和链表遍历算法的演示//2012年9月12日早上# include <stdio.h># include <malloc.h># include <stdlib.h>typedef struct Node{int data;struct Node *pNext;}NODE, *PNODE;//函数的声明PNODE create_list(void);void traverse_list( PNODE pHead );int main( void ){PNODE pHead = NULL;//等价于struct Node *pHead = NULL;pHead = create_list();//创建一个非循环单链表,并将该链表的头节点的头结点的地址赋给pHeadtraverse_list( pHead );return 0;}PNODE create_list(void){int len;//用来存放节点有效节点的个数int i;int val;//用来临时存放用户输入的节点的值//分配了一个不存放有效数据的头节点PNODE pHead = ( PNODE )malloc( sizeof( NODE ) );if( NULL == pHead ){printf( " 分配失败,程序终止" );exit( -1 );}PNODE pTail = pHead;//pTail指向链表的尾指针,刚开始时尾指针后头指针指向的相同pTail->pNext = NULL;printf( " 请输入你需要生成的链表节点的个数:len = " );//scanf( " %d ", &len ); //注意了,这里要先打一个空格,在输入一个数字,因为%d前面有个空格,所以......scanf( "%d", &len );for( i = 0; i < len; ++i ){printf(" 请输入第%d个节点的值: ", i + 1);scanf( "%d", &val );PNODE pNew = ( PNODE )malloc( sizeof( NODE ) );if( NULL == pNew ){printf( " 分配失败,程序终止" );exit( -1 );}//把新生成的节点挂在尾节点的后面pNew->data = val;pTail->pNext = pNew;pNew->pNext = NULL;pTail = pNew;//}return pHead;}void traverse_list( PNODE pHead ){PNODE p = pHead->pNext;while( NULL != p ){printf( " %d ", p->data );p = p->pNext;}printf( " \n " );return;//意思是告诉别人程序已经结束}每一个链表节点的数据类型该如何处理的问题//2012年9月11日晚上# include <stdio.h>typedef struct Node{int data;//数据域struct Node *pNext;//指针域}NODE, *PNODE;int main( void ){return 0;}排序:冒泡出入选择快速排序归并排序排序和查找的关系排序是查找的前提排序重点Typedef的用法1# include <stdio.h>//typedef int lisi; //为int再重新多取一个名字,lisi等价于inttypedef struct Student{int sid;char name[100];char sex;}ST;int main( void ){struct Student st; //等价于ST st;struct Student *ps = &st; //等价于ST *PS;ST st2;st2.sid = 200;printf("%d\n", st2.sid);return 0;}Typedef的用法2# include <stdio.h>typedef struct Student{int sid;char name[100];char sex;}*PST; //PST等价于struct Student *int main( void ){struct Student st;PST ps = &st;ps->sid = 99;printf( "%d\n", ps->sid );return 0;}Typedef的用法3# include <stdio.h>typedef struct Student{int sid;char name[100];char sex;}*PSTU, STU;//等价于STU代表struct Student, PSTU代表了struct Student *int main( void ){STU st;//struct Studtn st;PSTU ps = &st;//struct Student *ps = &st;ps->sid = 99;printf( "%d\n", ps->sid );return 0;}1到100相加# include <stdio.h>long sum( int n ){//用递归实现if( 1 == n )return 1;elsereturn sum( n - 1 ) + n;/*//用循环实现long s = 0;int i;for( i = 1; i <= n; ++i )s += i;return s;*/}int main( void ){printf( "%d\n", sum(100) );return 0;}//2012年9月17日早上到2012年9月18日早上递归定义:一个函数自己直接或间接调用自己举例:1)1 + 2 + 3 + ...100的和2)求阶乘3)汉诺塔4)走迷宫递归满足三个条件1)递归必须得有一个明确的中止条件2)该函数所处理的数据规模必须在递减3)这个转化必须是可解的递归和循环递归:1)易于理解2)速度慢3)存储空间大循环:1)不易理解2)速度快3)存储空间小递归的应用数和森林就是以递归的方式定义的数和图很多算法都是以递归来实现的很多数学公式就是以递归的方式定义的菲波拉契//2012年9月18日早上# include <stdio.h>void hannuota( int n, char A, char B, char C ){/*如果是1个盘子直接将A柱子上的盘子从A移动到C否则先将A柱子上的n-1个盘子借助于C移动到B直接将A柱子上的盘子从A移到C最后将B柱子上的n-1借助A移动到C*/if( 1 == n ){printf( "将编号为%d的盘子直接从%c柱子%c柱子\n", n, A, C );}else{hannuota( n-1, A, C, B );printf( "将编号为%d的盘子直接从%c柱子%c柱子\n", n, A, C );hannuota( n-1, B, A, C );}}int main( void ){char ch1 = 'A';char ch2 = 'B';char ch3 = 'C';int n;printf( "请输入要移动的盘子个数:" );scanf( "%d", &n );hannuota( n, 'A', 'B', 'C' );}阶乘的递归实现# include <stdio.h>//假定是1或大于1的值long f( long n ){if( 1 == n )return 1;elsereturn f( n - 1 ) * n;}int main( void ){printf( "%d\n", f(3) );return 0;} 阶乘的循环使用//程序实现不了功能噢# include <stdio.h>int main( void ){int val;int i, mult;printf( "请输入一个数字:" );printf( "val = " );scanf( "%d", &val );for( i = 1; i <= val; ++i )mult = mult * i;printf( "%d的阶乘是:%d\n", val, mult );return 0;}队和列//2012年9月14日早上到2012年9月17日早上队列定义:一种可以实现"先进先出"的存储结构分类链式队列用链表实现静态队列用数组实现静态队列通常都必须是循环队列循环队列1.静态队列为什么必须是循环队列2.循环队列需要几个参数确定及其含义两个参数来确定(front和rear)2个参数不同场合有不同的含义建议初学者先记住,然后慢慢体会1)队列初始化front和rear的值都是零2)队列非空front代表的是队列的第一个因素rear代表的是队列的最后一个有效元素的下一个元素3)队列空front和reard的值相等,单不是零3.循环队列各个参数含义建议初学者先记住,然后慢慢体会1)队列初始化front和rear的值都是零2)队列非空front代表的是队列的第一个因素rear代表的是队列的最后一个有效元素的下一个元素3)队列空front和reard的值相等,单不是零4.循环队列入队伪算法讲解两部完成:1)将值存入r所代表的位置2)rear = ( rear+1 ) % 数组的长度5.循环队列出队伪算法讲解front = ( front+1 ) % 数组的长度6.如何判断循环队列是否为空如果front与rear的值相等则该队列就一定为空7.如何判断循环队列是否已满预备知识:( front和rear没有任何关系)front的值可能比rear大也完全有可能比rear小当然也可能相等两种方式:1)多增加一个标志参数2)少用一个元素[通常使用第二种方式]用c伪算法表示就是:如果r和f的值紧挨着,则队列已满if( (r + 1)%数组长度== f )已满else不满队列算法入队出队队列的具体应用所有和时间有关的操作都与队列有关循环队列程序的演示/2012年9月17日早上# include <stdio.h># include <malloc.h>typedef struct Queue{int *pBase;int front;int rear;}QUEUE;void init( QUEUE * );bool en_queue( QUEUE *, int val );//入队void traverse_queue( QUEUE * );bool full_queue( QUEUE * );bool out_queue( QUEUE *, int * );//出队bool empty_queue( QUEUE * );int main( void ){QUEUE Q;int val;init( &Q );en_queue( &Q, 1 );en_queue( &Q, 2 );en_queue( &Q, 3 );en_queue( &Q, 4 );en_queue( &Q, 5 );en_queue( &Q, 6 );en_queue( &Q, 7 );en_queue( &Q, 8 );en_queue( &Q, 9 );traverse_queue( &Q );if ( out_queue( &Q, &val ) ){printf( "出队成功,队列出队的元素是%d\n", val );}else{printf( "出队失败!\n" );}traverse_queue( &Q );return 0;}void init( QUEUE *pQ ){pQ->pBase = ( int * )malloc( sizeof( int )*6 );pQ->front = 0;pQ->rear = 0;}bool full_queue( QUEUE *pQ ){if( ( pQ->rear + 1 ) % 6 == pQ->front ){return true;}elsereturn false;}bool en_queue( QUEUE *pQ, int val ){if( full_queue( pQ ) ){return false;}else{pQ->pBase[pQ->rear] = val;pQ->rear = ( pQ->rear + 1 ) % 6;return true;}}void traverse_queue( QUEUE *pQ ){int i = pQ->front;while( i != pQ->rear ){printf( "%d ", pQ->pBase[i] );i = ( i + 1 ) % 6;}printf("\n");return;}bool empty_queue( QUEUE *pQ ){if( pQ->front == pQ->rear )return true;elsereturn false;}bool out_queue( QUEUE *pQ, int *pVal ) {if( empty_queue( pQ ) ){return false;}else{*pVal = pQ->pBase[pQ->front];pQ->front = (pQ->front + 1) % 6;return true;}树测试# include <stdio.h># include <stdlib.h>int main ( void ){int i;charchar *ptr1[4]={"china","chengdu","sichuang","chongqin"};for( i = 0; i < 4; i ++ ){printf( "%s\n", ptr1[i] );}}树非线性结构数树定义专业定义:1)有且只有一个称为根的节点2)有若干个互不相交的子树,这些子树本身也是一课树通俗的定义:1)树是由节点和边组成2)每个节点只有一个父节点但可以有多个子节点3)但有一个节点例外,该节点没有放节点,此节点称为根节点专业术语节点父节点子节点子孙堂兄弟深度:从根节点到底层节点的层数称之为深度根节点是第一层叶子节点:没有子节点的节点非终端节点:实际就是非叶子节点(有子节点的节点)度:子节点的个数称为度树分类一般树任意一个子节点的个数都不受限制二叉树任意一个节点的子节点的个数最多两个,且子节点的个数不可以更改分类:一般二叉树满二叉树在不增加树的层数的前提下,无法再添加一个节点的二叉树就是满二叉树完全二叉树如果只是删除满二叉树最底层最右边的连续若干个节点,这样形成的二叉树就是完全二叉树森林n个互不相交的树的集合树的存储森林的存储二叉树的存储连续存储[完全二叉树](只能是这样子存储)优点:查找某个节点的父节点和子节点(也包括有没有子节点)很快缺点:耗用内存空间过大链式存储一般树的存储双亲表示法求父节点方遍孩子表示法求子节点方便双亲孩子表示法求父节点和子节点都很方便二叉树表示法把一个普通的树转化成二叉树来存储具体的转化方法:设法保证任意一个节点的左指针域指向它的第一个孩子右指针域指向他的下一个兄弟只要能满足此条件,就可以把一个普通树转化成二叉树一个普通树转化成的二叉树一定没有右子树森林的存储先把森林转化成二叉树,在存储二叉树操作遍历先序遍历[先访问根节点]先访问根节点再先序访问左子树再先序访问右子树中序遍历[中间访问根节点]中序遍历左子树再访问根节点再中序遍历右子树后续遍历[最后访问根节点]中序遍历左子树中序遍历右子树再访问根节点已知二中遍历序列求原始二叉树通过先序和中序或者中序和后序我们可以还原原始的二叉树但是通过先序和后序是无法还原原始的二叉树的换种说法:只有通过先序和中序,或者中序和后序我们才可以唯一的确定的二叉树应用树是数据库中数据组织一种重要形式操作系统子父进程的关系本身就是一颗树面向对象语言中类的继承关系本身就是一棵树赫夫曼树数操作链式二叉树遍历具体程序演示# include <stdio.h># include <malloc.h>struct BTNode{int data;struct BTNode *pLchild;//p是指针L是左child是孩子struct BTNode *pRchild;};void PreTraverseBTree( struct BTNode * pT );void InTraverseBTree( struct BTNode * pT );void PostTraverseBTree( struct BTNode * pT );struct BTNode *CreateBTree( void );int main( void ){struct BTNode *pT = CreateBTree();printf( "先序\n" );PreTraverseBTree( pT );//先序printf( "中序\n" );InTraverseBTree( pT );//中序printf( "后序\n" );PostTraverseBTree( pT );//后序return 0;}void PreTraverseBTree( struct BTNode * pT ) {/*伪算法先访问根节点再先序访问左子树再先序访问右子树*/if( pT != NULL ){printf( "%c\n", pT->data );if( NULL != pT->pLchild ){PreTraverseBTree( pT->pLchild );}if( NULL != pT->pRchild ){PreTraverseBTree( pT->pRchild );//pT->pLchild可以代表整个左子树}}}void InTraverseBTree( struct BTNode * pT ){if( pT != NULL ){if( NULL != pT->pLchild ){InTraverseBTree( pT->pLchild );}printf( "%c\n", pT->data );if( NULL != pT->pRchild ){InTraverseBTree( pT->pRchild );//pT->pLchild可以代表整个左子树}}}void PostTraverseBTree( struct BTNode * pT ) {if( pT != NULL ){if( NULL != pT->pLchild ){InTraverseBTree( pT->pLchild );}if( NULL != pT->pRchild ){InTraverseBTree( pT->pRchild );//pT->pLchild可以代表整个左子树}printf( "%c\n", pT->data );}}struct BTNode *CreateBTree( void ){struct BTNode *pA = ( struct BTNode * )malloc( sizeof( struct BTNode ) );struct BTNode *pB = ( struct BTNode * )malloc( sizeof( struct BTNode ) );struct BTNode *pC = ( struct BTNode * )malloc( sizeof( struct BTNode ) );struct BTNode *pD = ( struct BTNode * )malloc( sizeof( struct BTNode ) );struct BTNode *pE = ( struct BTNode * )malloc( sizeof( struct BTNode ) );pA->data = 'A';pB->data = 'B';pC->data = 'C';pD->data = 'D';pE->data = 'E';pA->pLchild = pB;pA->pRchild = pC;pB->pLchild = pB->pRchild = NULL;pC->pLchild = pD;pC->pRchild = NULL;pD->pLchild = NULL;pD->pRchild = pE;pE->pLchild = pE->pRchild = NULL;return pA;}线性结构和非线性结构逻辑结构线性数组链表栈和队列是一种特殊线性结构非线性树图物理结构快速排序图表链式二叉树二叉树表示方法后序遍历普通二叉树转化为二叉树普通二叉树转化为完全二叉树(正方形为要删除的)森林转化成二叉树先序遍历先序遍历2已知先序和中序求后序已知先序和中序求后序2已知中序和后序求先序中序遍历中序遍历2栈定义一种可以实现"先进后出"的存储结构栈类似于箱子分类静态栈动态栈算法出栈压栈应用函数调用中断表达式求值内存分配缓冲处理迷宫凡是静态分配的的都是栈里面分配(有操作系统帮你分配的)凡是动态分配的都是堆里面分配(由程序员手动分配的)//编译器编译成功,但是运行不是程序所需要的功能?# include <stdio.h># include <malloc.h># include <stdlib.h>typedef struct Node{int data;struct Node *pNext;}NODE, *PNODE;typedef struct Stack{PNODE pTop;PNODE pBottom;//pBottem是指向栈底下一个没有实际意义的元素}STACK, *PSTACK;void init( PSTACK );void push( PSTACK, int );void traverse( PSTACK );bool pop( PSTACK, int * );bool empty( PSTACK pS );int main( void ){STACK S;//STACK等价于struct Stackint val;init( &S );//目的是造出一个空栈push( &S, 1 );//压栈push( &S, 2 );push( &S, 3 );push( &S, 4 );push( &S, 5 );push( &S, 6 );push( &S, 7 );traverse( &S );//遍历输出clear( &S ); //清空数据traverse( &S );//遍历输出if( pop( &S, &val ) )printf( "出栈成功,出栈的元素是&d\n", val );}else{printf( "出栈失败" );}traverse( &S );//遍历输出return 0;}void init( PSTACK pS ){pS->pTop = ( PNODE )malloc( sizeof( NODE ) );if( NULL == pS->pTop ){printf( "动态内存分配失败!\n" );exit( -1 );}else{pS->pBottom = pS->pTop;pS->pTop = NULL;//或是pS->pBottom = NULL;}}void push( PSTACK pS, int val ){PNODE pNew = ( PNODE )malloc( sizeof( NODE ) );pNew->data = val;pNew->pNext = pS->pTop;//pS->Top不能改为pS->pBottom pS->pTop = pNew;return;}void traverse( PSTACK pS ){PNODE p = pS->pTop;while( p != pS->pBottom ){printf( "%d ", p->data );p = p->pNext;printf( "\n" );return;}bool empty( PSTACK pS ){if( pS->pTop == pS->pBottom )return true;elsereturn false;}//把pS所指向的栈出栈一次,并把出栈的元素存入pVal形参所指向的变量中,如果出栈失败,则返回false,否则truebool pop( PSTACK pS, int *pVal){if( empty( pS ) )//pS本身存放的就是S的地址{return false;}else{PNODE r = pS->pTop;*pVal = r->data;pS->pTop = r->pNext;free( r );r = NULL; //为什么要把r赋给NULL呢??return true;}}//clear清空void clear( PSTACK pS ){if( empty( pS ) ){return ;}else{PNODE p = pS->pTop;PNODE q = p->pNext;while( p != pS->pBottom ){q = p->pNext;free( p );p = q;}pS->pTop = pS->pBottom;}}。
![[郝斌]数据 结构c语言-前导知识](https://img.taocdn.com/s1/m/9cc808d2c9d376eeaeaad1f34693daef5ff7137c.png)