高级语言程序设计 2007.3 2007.7云南师大计信学院 解敏 xmin7186yahoo.com.cn cic.ynnu.edu.cn第第1010章章 结构体与共用体结构体与共用体 位运算位运算本章要点本章要点结构体类型的定义，结构体类型变量的定义、引用、初始化结构体数组的定义及初始化任务10.1 按书名查找图书指向结构体类型数据的指针用链表处理信息：链表建立、输出，结点删除、插入任务10.2 插入、删除图书用typedef为类型起别名循环链表: 任务10.3 猴子选大王（Joseph 问题） 共用体、枚举位运算符和位运算: 任务10.4 加密与解密小结任务任务10.1.1 按书名查找图书 按书名查找图书数组：每个元素都是同一类型的数据结构体：可以表示一组不同类型，但有内在联系的数据 nonameauthpubyea rpric ecount0 311 1C程序设计谭浩 强清华大学出 版社200 526.0 81 311 2从问题到程序裘宗 燕机械工业出 版社200 536.0 32 311 3C程序设计语 言徐宝 文机械工业出 版社200 630.0 43 311 4C语言程序设 计教程徐士 良人民邮电出 版社200 323.5 24 311 5程序设计基础吴文 虎清华大学出 版社200 428.0 5结构上的 合法操作程序实现使用结构体定义结构体类型格式 struct 结构体类型名 类型名 1 成员名 1； . . .类型名 n 成员名 n； ;定义类型，不分配内存空间，不可初始化定义结构体变量的格式：struct 结构体类型名 变量名；引用结构体变量成员的格式：结构体变量名 . 成员名（结构体指针变量名）. 成员名结构体变量名 - 成员名结构体的操作要点: 1. 定义结构体类型 2. 定义结构体变量 3. 引用结构体变量的成员例/1.定义结义结 构体类类型 struct book int no; char name50; char auth10; char pub20; int year; double price; int count; c1;abookno3111 name“C程序设计“ auth“谭浩强“ pub“清华大学出版社“ year2005 price26.0 count8/2.定义结义结 构体变变量 struct book *p, lib5; struct book abook=3111,“C程序设计设计 “,“谭谭浩强“, “清华华大学出版社“,2005,26.0,8;3.3.访问结构体变量的成员访问结构体变量的成员1.abook.no=3111;3./借书 abookuif(abook.count0)abook.count-; 4./按书名查找图书 lib5u for(i=0;i count=3;5./输入输出结构体变量可在结构上执行的合法操作可在结构上执行的合法操作struct abc char c; int x; ;struct xyz int x,y; ;struct abc a,b,*p; struct xyz x; int len;1.p=2.a.c=A;3.p-x=5;4.b=a;5.x=a;6.len=sizeof(struct abc);7.if(a=b)printf(“相等”)；任务任务10.2.2 插入、删除图书插入、删除图书2从问题到程 序1C程序设计3C程序设计 语言4C语言程序 设计教程5程序设计基 础链表用途：需要一次存储大量数据，但预 先不知道预计接收多少数据需要随意重排数据结点结构 创建链表顺序插入 结点删除结点程序实现输出链表删除所有 结点结点结构结点结构结点结构 (自引用结构)数据域：结构中的各种实际数据成员指针域：一个或几个指向本类结构的指针数据域指针域struct book int no; char name50; char auth10; char pub20; int year; double price; int count; ;struct node /链表结点 struct book data; /数据域 struct node * next; /指针域 ;struct node b1,b2,*p=b1.data.no=1;p-next=p-next-data.no=2;p=p-next;p-data.no=3;链表的建立过程链表的建立过程书nnextHeadNULL书2next书3next书1nextpnewNULLu头指针Head：指向链表的第一个结点，代表整个链表u尾结点：链表的最后一个结点，prear-next=NULLu尾插法创建链表u头指针Head在函数间的传递u思考：指针变量pnew 、prear的作用和指向prear链表创建思路链表创建思路: :尾插法尾插法1.定义结点结构 2.定义头指针：struct node*Head=NULL;3.生成新结点：分配存储空间pnew=(*struct node)malloc(sizeof(struct node)为数据域赋值4.在原链表尾(prear之后)插入新结点：若链表为空(Head=NULL)，则 Head=pnew;否则 prear-next=pnew;pnew成为新的尾结点: prear=pnew;5.尾结点处理: prear-next=NULLstruct node 类型数据域；struct node* next; 头指针头指针HeadHead在函数间的传递在函数间的传递思考：链表创建，插入、删除结点时，是否会改变头指针 Head的指向？全局变量 struct node * Head=NULL; int main() 局部变量 int main() struct node * Head=NULL; 1.传递头指针，返回改变指向的头指针 函数声明：struct node * create(struct node *Head ); 调用：Head=cerate(Head);1.传递头指针的地址 函数声明： void create(struct node * *Head ); 调用：cerate( 输出链表输出链表void brows(struct node *Head) /浏览struct node *p;p=Head;while( p!=NULL )Print(p); /输出一本书的信息p=p-next; 书15NU LLHead书6书5书12书8p链表结点的顺序插入链表结点的顺序插入1: 1: head=NULL head=NULL Head书6 pnewu当head=NULL 时Head = pnew;pnew-next = NULL;原则： u插入操作不应破坏原链接关系 u插入的结点前，应该有一个插入位置的查找子过程NULLNULL2 pnew-data.no data.no 3一般位置 PAD图链表结点的顺序插入链表结点的顺序插入2: 2: pnewpnew-data.nodata.no data.nodata.no书15NU LLHead书6书5书12书8书4 pnew当pnew-data.nodata.num时： ( 新结点将成为头结点 ) pnew-next = Head; Head = pnew;链表结点的顺序插入链表结点的顺序插入3 3书15NU LLHead书6书10书5pnew书12书8presucu循环：查找插入位置 u当suc-data.no data.no时 pnew-next =suc; pre-next = pnew;u思考：指针pre、suc 的作用，指向u在尾结点之后插入的 情况是否需要单独考虑“链表结点顺序插入链表结点顺序插入”的的PADPAD图图pre=Head; suc=Head-next;pnew-next=suc; pre-next=pnew;Head= NULLHead=pnew1.空链表pnew-next=Head Head=pnewpnew-data.no data.no2.插到头结点之前while suc!=NULL 1.当Head-data.no=no时p=Head; Head=(Head)-next; free(p);书12NU LL书6书5pHeadHeadNULL3、4一般位置 PAD图链表结点的删除链表结点的删除3 3书15NU LLHead书6书5书12书8u循环：查找删除位置 3. 找到：pre-next = p-next;free( p); 4. 找不到prepu思考：指针pre、p的作用，指向“链表结点删除链表结点删除”的的PADPAD图图pre=Head; p=pre-next;pre-next=p-next free(p)Head= NULLreturn1.空链表p=Head; Head=Head-next free(p) Head- data.no =no2.删除头结点while p!=NULL 3. p=*Head;4. while( p!=NULL )5. suc=p-next;6. free(p);7. p=suc;8. 9. *Head=NULL;10.任务任务10.3.3 猴子选大王（ 猴子选大王（Joseph Joseph 问题问题 ）n只猴子围成一圈，顺时针方向从1到n编号。之后从1号 开始沿顺时针方向让猴子从1，2，m依次报数，凡报 到m的猴子，都让其出圈，取消候选资格。然后不停地按 顺时针方向逐一让报出m者出圈，最后剩下一个就是猴王 。建立循环 链表模拟报数 过程程序实现n=8,m=3演 示反Joseph 问题起始位置猴 王123456783615284猴子被淘汰的顺序演示：n=8, m=3变量说明思路猴子选大王猴子选大王 思路思路链表结点数据域为猴子编号(需要建立链表)围成圈：出列：剩下一个：循环链表，尾结点tail-next=head删除结点p pre-next =pre结点结构struct node int num; / 整数，表示猴子的编号 struct node *next; / 指针，指向相邻的下一只猴子 ;typedef struct node monkey;全局变量: monkey* Head,*tail; /链表的头指针,尾指针int n; /猴子数(圈)int m; /间隔(报数)用typedef为 类型起别名用用typedeftypedef为类型起别名为类型起别名用新类型名代表原类型名typedef 原类型名 新类型名；例：typedef int Int;typedef char String20;typedef struct timeint h; int m; int s; Time;Int i,j=0;String s1,s2=“hello”;Time t=10,30,0尾插法建立循环链表尾插法建立循环链表tail1Head25prearpnew34678PAD图void void create( create( intint n n ) )“ “尾插法建立尾插法建立n n个个结结结结点的循点的循环链环链环链环链 表表” ” 的的PADPAD图图图图i=1 inum=i; pnew-next=NULLprear-next=pnew 循环：尾插法插入结点prear=pnewtail=prear tail-next=Head