main.cpp

一个我的数据结构解题集合

#include <iostream>
#include <string>
#include <assert.h>
#include <stdlib.h>
#include "IoUtils.h"

using namespace std;

/* 按照步长k删除元素，元素共n个
 * 删除元素依次输出到cout, 利用链表实现
 */
void remove(int n, int k) {
    struct node {
	    node(int i) {dat=i;}
        int dat;
        node *next;
	};
    typedef node *link;

	assert(n > 0);
	assert(k > 0);

	link head, p;
	p = head = new node(1);
	for (int i = 2; i <= n; ++i, p=p->next)
		p->next = new node(i);
	p->next = head;	//循环链表至此已经生成

	while (p->next != p) {
		link dying = p->next;
		p->next = dying->next;
		cout << dying->dat <<" ";
		delete dying;

		for (int j=0; j<k-1; j++) //只走k-1步的原因：
			p = p->next;      //因为这个循环的任务是从刚刚被删除的结点的前一个结点
		                      //走到将要被删除的结点的前一个结点
	}
	cout << p->dat << endl;
	delete p;
} // remove(int, int)

int main() {
	cout << "输入2个正整数n和k，按照步长k删除这n个元素" << endl;

	cout << "请输入n: ";
	int n = getPositiveInteger();

	cout << "请输入k: ";
	int k = getPositiveInteger();

	remove(n, k);

	system("pause");

	return 0;
} // main()