数据结构作业与实验1.ppt

计算机与电子信息学院 秦亮曦 数 据 结 构 作业与实验 广西大学计算机与电子信息学院 秦亮曦 e-mail: qin_lx@126.com 第二章 线性表 习题2.11 2.11 设线性表va中的数据元素递增有序。试写一算法，将x插入到顺序表中的适当位置上，以保持该表的有序性。 习题2.11 算法 习题2.22 2.22 试写一算法，对单链表实现就地逆置。 习题2.11 算法 实习1 线性表及其应用 1.2 约瑟夫环(Joseph)问题 编号为1, 2, …, n的n个人按照顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他顺时针方向上的下一个人开始，重新从1开始报数，如此下去直至所有人全部出列为止。试设计一个程序求出出列顺序。 Joseph.cpp * GUANGXI UNIVERSITY e1 e2 … ei-1 ei … en va.elem 表的长度增加 e1 e2 … ei-1 x ei … en Status InsertOrderList(SqList va, ElemType x) { if (va.length == va.listsize) // 当前存储空间已满，增加空间 { newbase=(ElemType*)realloc(va.elem, (va.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!newbase) exit(OVERFLOW); // 存储空间分配失败 va.elem=newbase; va.listsize += LISTINCREMENT; } for (i=va.length-1; i=0 va.elem[i]x; i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; va.length ++; return OK; } a1 a2 a3 … an ^ 头结点 a1 ^ a2 a3 ... an 逆置后： L 头结点 头指针 L p q r p-next Status LinkList_reverse(LinkList L) { p=L-next; //p指向首元结点（第一个元素结点） q=p-next; //q指向第二个元素结点 p-next=NULL; //首元结点变成尾结点 while (q) // 当q不为NULL { r=q-next; // 先使得r指向q的下一个结点 q-next=p; // 修改q的指针域，使之指向原来的前驱 p=q; q=r; // 修改指针，为下一轮循环作准备 } L-next=p; //头结点的指针指向尾结点，使之变成首元结点 return OK; } 1 c1 2 c2 3 c3 n cn … last num cipher next 链表结点的结构： 序号 密码 #include stdafx.h #include stdlib.h #define OK 1 #define ERROR 0 typedef bool Status; typedef struct LNode { int num; int cipher; LNode *next; } *Link; Status MakeNode(Link p, int n1, int c1) { p=(Link)malloc(sizeof(LNode)); if (!p) return ERROR; p-num=n1; p-cipher=c1; p-next=NULL; return OK; } void FreeNode(Link p) { free(p); p=NULL; } 建立结点 释放结点 * GUANGXI UNIVERSITY