数据库作业： 输入一组整数，建立带头结点的单链表，并实现线性表的求长度、插入和删除等操作。

Question

希望能来个没有什么错误的~只有20分了~

Answer 1

昨天闲着没事写了个C++的约瑟夫环问题的解决。。
是带头结点的循环单链表。。只要改一两处地方就可以改成普通单链表。。
求长度、插入、删除操作都有。。。

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;

template <class T>
class LinkedList{
typedef struct LNode{
T value;
LNode *next;
}LNode, *pNode;
private:
pNode headNode;
int size;
public:
LinkedList(){
headNode = new LNode;
headNode->value = NULL;
headNode->next = headNode;
size = 0;
}
~LinkedList(){

}

void add(T &t){
pNode node = new LNode;
node->value = t;
node->next = headNode;

pNode tmp = headNode;
while(tmp->next != headNode){
tmp = tmp->next;
}
tmp->next = node;
size ++;

}
bool remove(T t){
pNode pre, node;
pre = headNode;
node = headNode->next;
while(node!=headNode){

if(node->value == t){
pre->next = node->next;
size --;

//T rt = node->value;
delete node;
return true;
}
pre = node;
node = node->next;

}

return false;
}

T get(int index){
//assert( index < size);
if(index >= size){
throw 1;
}

pNode node = headNode->next;
int i=0;
for(;i<index;i++){
node = node->next;
}
return node->value;
}

int getSize(){
return size;
}

void printList(){
cout <<"list size: " << size << ", elements: " << endl;
for(pNode p = headNode->next; p!=headNode; p=p->next){
cout << p->value << " ";
}
cout << endl;
}
void resefu(){
int n = 9, k = 6, m = 5;

pNode cur = headNode;
for(int i=0; i<k; i++){
cur = cur->next;
}
while(size > 0){
for(int i=1; i<m ; i++){
cur = cur->next;
if(cur == headNode){
i--;
}

}
T tmp = cur->value;
cur = cur->next;
cout << "-------------remove " << tmp << endl;
remove(tmp);
printList();
}
}
};

/*
void main(){
LinkedList<int> list;
int n = 9, k = 1, m = 5;

for(int i=1; i<=n; i++){
list.add(i);
}
// list.printList();

list.resefu();

}*/