2022年2022年郝斌老师数据结构上课代码 .pdf

《2022年2022年郝斌老师数据结构上课代码 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年郝斌老师数据结构上课代码 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一部分typedefine 的用法# include typedef struct Studentint sid;char name100;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( %dn, ps-sid );return 0;第二部分链表部分的全部代码#include #include

2、#include struct nodeint data;struct node * next;/创建一个链表，返回pheadstruct node * creat_list()/函数返回类型为structnode* 类型struct node * phead=NULL;struct node * ptail=NULL;struct node * pnew=NULL;int i;int len;int val;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 -

3、- - - - - - - - phead=(struct node *) malloc(sizeof (struct node);if (phead=NULL)printf( 动态分配失败n);exit(-1);phead-next=NULL;ptail=phead;printf( 请输入链表的长度len:n);scanf(%d,&len);for(i=0;idata=val;pnew-next=NULL;ptail-next=pnew;ptail=pnew;return phead;/输出链表void show_list(struct node * phead)struct node *

4、p;p=phead-next ;while (p!=NULL)printf(%5d,p-data);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - p=p-next ;printf(n);/判断链表是否为空bool is_empty(struct node * phead)if (phead-next=NULL)return true ;elsereturn false ;/求链表的长度int length_list(stru

5、ct node* phead)int len=0;struct node * p;p=phead-next;while (p!=NULL)+len;p=p-next;return len;/对链表进行排序void sort_list(struct node * phead)int l;int i,j,t;struct node * p, * q;l=length_list(phead);for(i=0,p=phead-next;inext)for(j=i+1,q=p-next;jnext)if (p-dataq-data)名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

6、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - t=p-data;p-data=q-data;q-data=t;/在链表中插入数据void insert_list(struct node * phead,int pos, int val)int i;struct node * p=phead-next;struct node * pnew;if (p=NULL)printf( 程序出错 !n);exit(-1);for(i=0;inext;+i;/让 p 指向插入位置的前面一个节点pnew=(st

7、ruct node *)malloc(sizeof(structnode);pnew-data=val;pnew-next=p-next;p-next=pnew;return ;/删除链表中某一位置的节点void delete_list(struct node * phead,int pos)int i;struct node * p=phead-next;struct node * q;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - -

8、 - - if (p=NULL)printf( 程序出错 !n);exit(-1);for(i=0;inext;+i;q=p-next;p-next=q-next;return ;/主函数int main ()int l;struct node * phead ;/ 创建头结点phead=creat_list();/ 创建一个链表，头指针返回给pheadshow_list(phead);/ 输出刚才创建的链表l=length_list(phead);/ 求链表的长度printf(len=%dn,l);/ 输出链表的长度l/ sort_list(phead);/ 对链表进行排序/ show_li

9、st(phead);/ 对排序完之后的链表进行输出insert_list(phead,4,44);show_list(phead);delete_list(phead,3);show_list(phead);return 0;第三部分栈的全部代码# include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - # include # include typedef struct Nodeint data;struct Nod

10、e *pNext;NODE, *PNODE;typedef struct StackPNODE 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 );/目的是造出一

11、个空栈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( 出栈成功 ,出栈的元素是&dn, val );else名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6

12、页，共 14 页 - - - - - - - - - printf( 出栈失败 );traverse( &S );/遍历输出return 0;void init( PSTACK pS )pS-pTop = ( PNODE )malloc( sizeof( NODE ) );if( NULL = pS-pTop )printf( 动态内存分配失败!n );exit( -1 );elsepS-pBottom = pS-pTop;pS-pTop = NULL;/ 或是 pS-pBottom = NULL;void push( PSTACK pS, int val )PNODE pNew = ( PN

13、ODE )malloc( sizeof( NODE ) );pNew-data = val;pNew-pNext = pS-pTop;/pS-Top 不能改为pS-pBottompS-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;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

14、- - - - - 第 7 页，共 14 页 - - - - - - - - - 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;elsePNODE r = pS-pTop;*pVal = r-data;pS-p

15、Top = r-pNext;free( r );r = NULL;/为什么要把r 赋给 NULL 呢?return true;/clear 清空void clear( PSTACK pS )if( empty( pS ) )return ;elsePNODE p = pS-pTop;PNODE q = p-pNext;while( p != pS-pBottom )名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - q = p-p

16、Next;free( p);p = q;pS-pTop = pS-pBottom;第四部分循环队列的代码# include # include typedef struct Queueint *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( QUE

17、UE * );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 );名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

18、 第 9 页，共 14 页 - - - - - - - - - if ( out_queue( &Q, &val ) )printf( 出队成功 ,队列出队的元素是%dn, val );elseprintf( 出队失败 !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

19、)return true;elsereturn false;bool en_queue( QUEUE *pQ, int val )if( full_queue( pQ ) )return false;elsepQ-pBasepQ-rear = val;pQ-rear = ( pQ-rear + 1 ) % 6;return true;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - void traverse_queue(QU

20、EUE *pQ )int i = pQ-front;while( i != pQ-rear )printf( %d , pQ-pBasei );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-pBasepQ-front;pQ-front

21、 = (pQ-front + 1) % 6;return true;第五部分递归1,1 到 100相加名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - # include 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;ret

22、urn s;*/int main( void )printf( %dn, sum(100) );return 0;2求阶乘# include /假定是 1 或大于 1 的值long f( long n )if( 1 = n )return 1;elsereturn f( n - 1 ) * n;int main( void )printf( %dn, f(3) );名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - return

23、 0;3汉诺塔# include void hannuota( int n, charA, 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 );elsehannuota( n-1, A, C, B );printf( 将编号为 %d 的盘子直接从%c 柱子 %c 柱子 n, n, A, C )

24、;hannuota( n-1, B, A, C );int main( void )char ch1 = A;char ch2 = B;char ch3 = C;int n;printf( 请输入要移动的盘子个数: );scanf( %d, &n );名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - hannuota( n, A, B, C );第六部分树1，指针数组和数组指针# include # include int main ( void )int i;char *ptr14=china,chengdu,sichuang,chongqin;for( i = 0; i 4; i + )printf( %sn, ptr1i );return 0;2，树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -