danh sách sinh viên (ds liên kết đơn)

(tạo menu nhập vào danh sách sinh viên.
-> chèn vào đầu danh sách
->chèn vào cuối danh sách
-> chèn vào 1 vị trí bất kỳ

-> xóa sinh viên ở đâu
-> xóa sinh viên ở cuối
-> xóa sinh viên ở 1 vị trí bất kỳ

-> sắp xếp sinh viên theo tên)


#include<iostream>
#include <string>
using namespace std;

struct sinhvien{
 string ten;
};
struct Node{
 sinhvien *data;
 Node *next;
};

Node * dau;
Node * cuoi;

void khoitao(){
 dau = cuoi = NULL;
}

void themcuoi(Node * node){
 if(dau == NULL){
  dau = cuoi = node;
 }
 else{
  cuoi -> next = node;
  cuoi = node;
 }
}

Node *getNode(string x){
 Node *p = new Node();
 p -> data = new sinhvien();
 p -> data -> ten = x;
 p -> next = NULL;
 return p;
}

void input(){
 int n;
 cout << "nhap so sinhvien ";
 cin >> n;
 cin.ignore();
 khoitao();
 for(int i = 1; i <= n; i++){
  string x;
  cout << "nhap vao ten sinh vien: [" << i << "] = ";
  getline(cin, x);
  Node *p = getNode(x);
  themcuoi(p);
 }
}

void in(){
 Node *p = dau;
 cout << endl;
 while( p != NULL){
  cout << p -> data -> ten << " " << endl;
  p = p -> next;
 }
}

// dau = 1 -> 2 -> 3
//dau = 2 -> 3
void xoadau(){
 Node *p = dau;
 dau = dau ->next;
 p = NULL;
}

void xoacuoi(){
 for(Node *i = dau; i != cuoi; i = i -> next){
  if(i -> next == cuoi){
   cuoi = i;
   i -> next = NULL;
   break;
  }
 }
}


//1 2 -> 3 -> 4 5 6
//1 -> 2 -> 4 -> 5 -> 6
void xoa(int k){
 int index = 1;
 for(Node *i = dau; i != cuoi; i = i -> next){
  if(index == k){
   i -> next =  i -> next -> next;
   break;
  }
  index ++;
 }
}

void chendau(){
 string x;
 cout << "nhap vao ten sinh vien chen vao dau: ";
 cin.ignore();
 getline(cin, x);
 Node *p = getNode(x);
 if(dau == NULL){
  dau = cuoi = p;
 }
 else{
  p -> next = dau;
  dau = p;
 }
}
//1 ->2 -> 4 ->5
//3
//1 ->2 ->3 -> 4 ->5
void chenbatky(int k){
 string x;
 cout << "nhap vao ten sinh vien chen vao bat ky: ";
 cin.ignore();
 getline(cin, x);
 Node *p = getNode(x);
 int index = 1;
 Node *q = dau;
 for(Node * i = dau; i != cuoi; i= i->next){
  if(index == k){
   Node *tmp = q -> next;
   q -> next = p;
   p -> next = tmp;
   break;
  }
  q = q -> next;
  index ++;
 }
}

void chencuoi(){
 string x;
 cout <<"nhap vao ten sinh vien chen vao cuoi: "<< endl;
 cin.ignore();
 getline(cin,x);
 Node *p = getNode(x);
 themcuoi(p);
}

void hoanvi(Node *a, Node *b){
 sinhvien *tmp = b -> data;
 b->data = a->data;
 a->data = tmp;
}

void sapxep(){
 for(Node *i = dau; i != cuoi; i = i -> next){
  for(Node *j = i -> next; j != NULL; j = j -> next){
   if( i -> data -> ten.compare(j -> data -> ten) > 0){
    hoanvi(i , j);
   }
  }
 }
}

int main(){

 input();
 in();
 while(true){
  system("cls");
  cout << "0. exit " << endl;
  cout<<"1. them vao dau danh sach "<< endl;
  cout <<"2. them vao cuoi danh sach "<< endl;
  cout << "3. them vao vi tri bat ky "<< endl;
  cout << "4. xoa dau danh sach "<<endl;
  cout << "5. xoa cuoi danh sach "<<endl;
  cout << "6. xoa vi tri bat ky "<< endl;
  cout << "7. sap xep theo ten "<< endl;
  int x;
  cin >> x;
  switch(x){
   case 0: return 0;
   case 1: chendau();
     in();
     break;
   case 2: chencuoi();
     in();
     break;
   case  3: int k;
     cout << "nhap vi tri chen: "<< endl;
     cin >> k;
     chenbatky(k);
     in();
     break;
   case 4: xoadau();
     in();
     break;
   case 5: xoacuoi();
     in();
     break;
   case 6: int l;
     cout << "nhap vao vi tri xoa " << endl;
     cin >> l;
     xoa(l);
     in();
     break;
   case 7: sapxep();
     in();
     break;
  }
  system("pause");
 }

}