程序设计课程设计报告.doc

程序设计课程设计报告设计人：电气Q1142李艳平（11150038）日期：2012-11-29指导教师：桂超设计题目：链表操作 一、 设计任务1、 创建一个单链表，并返回头结点的地址head2、 编写函数circulachain，将上述单链表改为单循环链表3、 编写函数addnode，在数据为x的结点之后插入数据为y的结点4、 编写函数delenode，删除单链表中数据为x的结点5、 解决约瑟夫问题：有n个人，围坐一圈，对他们从1开始编号，即1，2，3，.，n，如果从某一个人开始报数，他报数1，按顺时针进行，紧挨的人报数2，再往下的人跟着报3.，一直报到k，凡报到k的人出列，再往下，继续从1 开始报数，2，3，.，一直报到k，凡报到k的人出列。试输出该问题中顺序出列的人的名字。二、 功能描述创建单链表函数：chain* crechain(char *ch) 创建单循环链表函数：chain* circulchain(char *ch) 销毁链表：void Destroy(chain *head)显示链表中每个结点的数据：void Show(chain *head)插入结点函数：void AddNode(chain *head, char x, char y)删除结点函数：void DeleNode(chain *head, char x) 三、 程序实现1、单链表的基本操作：#include using namespace std;struct chainchar data;chain *next;chain* crechain(char *ch) /创建单链表int i;chain *head = NULL, *p = NULL, *q = NULL;for (i = 0; chi != 0; i +)p = new chain;p-data = chi;if (head = NULL)head = p;elseq-next = p;q = p;q - next = NULL;return (head);void AddNode(chain *head, char x, char y) /* 插入结点 */ chain *r, *s;if (head = NULL) cout链表为空!data != x)r = r-next;else break;if (r = NULL)cout没有数据为x的节点!data = y;s-next = r-next;r-next = s;void DeleNode(chain *head, char x) /* 删除结点*/chain *p = head, *s;if (head = NULL)cout链表为空!data = x)head = p-next;delete p;else while (p-next != NULL)if (p-next-data != x)p = p-next;elses = p-next;p-next = s-next;delete s;break;void Show(chain *head) /输出链表 chain *p;p = head;while (p != NULL)coutdata;p = p-next;coutnext;delete p;int main()chain *head;head = crechain(abcd);Show(head);AddNode(head, b, f);Show(head);DeleNode(head, c);Show(head);Destroy(head);return 0;2、单循环链表：chain* circulchain(char *ch)int i;chain *head = NULL, *p = NULL, *q = NULL, *r;for(i = 0; chi != 0; i +)p = new chain; p-data = chi;if (head = NULL)head = p;elseq - next = p;q = p;q - next = head; return (head);3、约瑟夫问题：#include using namespace std;struct Josephchar ch;Joseph *next;Joseph *head, *tail; /Joseph结构指针，全局变量void create(int n)/给每个结点数据赋值int i;Joseph *p, *q;p = (Joseph*) malloc (sizeof(Joseph);p-ch = A;p-next = NULL;head = p;q = p;for(i = 1; i ch = A + i;q-next = p; /将p结点加到链表尾部q = p; /让q指向链表尾部结点p-next = NULL; /链表尾部指向空tail = q;tail-next = head;void Display(int m) /依次输出出列的人的名字int x = 0;Joseph *p, *q;q = tail;dop = q - next; /p赋值为q相邻的下一个结点x +;if (x % m = 0)cout出列的人为chnext = p-next;delete p;p = NULL;else q = p; /q指向相邻的下一结点pwhile(q != q - next); /剩余结点数