10 trang 7 lượt tải

Danh sách liên kết Môn Câu trúc dữ liệu giải thuật | Trường Đại học Công nghiệp Thành phố Hồ Chí Minh

13

#include <stdio.h>#include <stdlib.h>// dinh nghia cau truc danh sach lien ketstruct ttNode{int data;struct ttNode *pNext;};typedef struct ttNode Node;struct ttList{Node *pHead, *pTail;};typedef struct ttList List;//khai bao cac nguyen mau hamvoid init(List *l);. Tài liệu gồm 10 trang, giúp các bạn tham khảo, ôn tập và đạt kết quả cao. Mình bạn đọc đón xem!

Môn: Câu trúc dữ liệu giải thuật (422000161) 12 tài liệu

Trường: Đại học Công nghiệp Thành phố Hồ Chí Minh 515 tài liệu

Tác giả:

Profile

Hân Hân

2 tuần trước
Danh sách Quiz
/10
1
DS LIÊN KẾT
#include <stdio.h>
#include <stdlib.h>
// dinh nghia cau truc danh sach lien ket
struct ttNode{
int data;
struct ttNode *pNext;
};
typedef struct ttNode Node;
struct ttList{
Node *pHead, *pTail;
};
typedef struct ttList List;
//khai bao cac nguyen mau ham
void init(List *l);
int isEmpty(List *l);
void addHead(List *l,Node *pNew);
void addTail(List *l,Node *pNew);
Node * createNode(int x);
…
//cai dat ham main
int main(int argc, char *argv[]) {
List ds;
init(&ds);
input(&ds);
printf("Danh sach sau khi nhap :\n");
output(ds);
//Cau 3
printf("\nPhan tu mang gia tri chan la :");
XuatChan(&ds);
//cau 4
Node *maxNode= TimMax(&ds);
if(maxNode!=NULL){
printf ("\nGia tri lon nhat la: %d\n",
maxNode->data);
scanf ("%d",&X);
ThemXTruocChanDau(&ds,X);
printf ("\nDanh sach sau khi them vao truoc pt
chan : ");
output(ds);
//Cau 7
printf ("\nNhap gia tri can them vao sau pt le:
");
scanf ("%d",&X);
ThemXSauLeCuoi(&ds,X);
printf ("\nDanh sach sau khi them vao sau pt le
: ");
output(ds);
//Cau 8
Node *minNode= TimMin(&ds);
if(minNode!=NULL){
printf ("\nGia tri nho nhat la: %d\n",
minNode->data);
} else printf("\nDanh sach rong");
SapXep(&ds);
printf("\nDanh sach sau khi sx tang la: ");
output(ds);
// Xóa phan tu dau
XoaDau(&ds);
printf("\nDs sau khi xoa phan tu dau:\n");
output(ds);
// Xóa phan tu cuoi
XoaCuoi(&ds);
printf("\nDanh sach sau khi xoa phan tu cuoi:\n");
output(ds);
// Xóa phan tu giua
XoaGiua(&ds);
printf("\nDanh sách sau khi xóa giua la: ");
output(ds);
} else printf("\nDanh sach rong");
//Cau 5
int demSNT= DemSNT(&ds);
printf ("\nSo luong so nguyen to la: %d\
n",demSNT);
n");
//Xoa Min
XoaMin(&ds);
printf("\nDanh sach sau khi xoa min %d la:\
//Cau 6
int X;
printf ("Nhap gia tri can them vao truoc pt
chan: ");
output(ds);
// Nhap X va xoa truoc sau X
printf("Nhap gia tri X de xoa truoc va sau X: ");
scanf("%d", &X);
XoaTruocSauX(&ds, X);
printf("Danh sach sau khi xoa truoc va sau X:\n");
output(ds);
// // Tach danh sach thanh 2 danh sach
// Tach(ds, &dsNguyenTo, &dsConLai);
// printf("Danh sach cac so nguyen to:\n");
// output(dsNguyenTo);
// printf("Danh sach cac phan tu con lai:\n");
// output(dsConLai);
Node * createNode(int x){
Node *p;
p = (Node *)malloc(sizeof(Node));
if(p == NULL){
printf("Khong du bo nho cap phat.\n");
}else{
p->data = x;
p->pNext = NULL;
}
return p;
printf("Nhap gia tri X de xoa cac phan tu co gia tri
bang X: ");
scanf("%d", &X);
XoaX(&ds, X);
printf("Danh sach sau khi xoa cac phan tu bang
%d:\n", X);
output(ds);
return 0;
}
//cai dat cac thao tac cua DSLK
void init(List *l){
l->pHead = l->pTail = NULL;
}
int isEmpty(List *l){
return ((l->pHead == NULL) && (l->pTail ==
NULL)) ? 1 : 0;
}
void addHead(List *l,Node *pNew){
if(isEmpty(l)){
l->pHead = l->pTail = pNew;
}else{
pNew->pNext = l->pHead;
l->pHead = pNew;
}
}
void addTail(List *l,Node *pNew){
if(isEmpty(l)){
l->pHead = l->pTail = pNew;
}else{
l->pTail->pNext = pNew;
l->pTail = pNew;
}
}
}
void input(List *l){
init(l);
int x;
Node *pNew;
do{
printf("Hay nhap pt :");
scanf("%d",&x);
if(x == 0)
break;
pNew = createNode(x);
if(pNew != NULL){
addTail(l,pNew);
}
}while(1);
}
void output(List l){
Node *p = l.pHead;
while(p!=NULL){
printf("%d\t",p->data);
p = p->pNext;
}
printf("\n");
}
//Cau 3
void XuatChan(List *l){
Node *p= l -> pHead;
while(p){
if(p->data %2 ==0)
printf (" %d\t", p->data);
p= p->pNext;
}
}
//Cau 4
2
3
Node * TimMax(List *l){
Node *pmax= l->pHead;
Node *p= l->pHead->pNext;
for(;p;p=p->pNext){
if(p->data > pmax->data)
pmax=p;
}
prev=q;
break;
}
}
if(prev!=NULL){
prev->pNext=k;
k->pNext=p;
return pmax; }
} }
//Cau 5
int LaSNT(int x){
if(x<2) return 0;
int i;
for(i=2;i*i<=x;i++){
if(x%i==0) return 0;
}
return 1;
}
int DemSNT(List *l){
int dem=0;
Node *p= l->pHead;
for(;p!= NULL; p=p->pNext){
if(LaSNT(p->data))
dem++;
}
return dem;
}
//Cau 6
Node * TimChanDau(List *l){
Node *p=l->pHead;
for(;p!=NULL;p=p->pNext){
if(p->data %2==0){
return p;
}
}
return NULL;
}
void ThemkTruocp(List *l, Node *p, Node *k){
if(l->pHead==NULL) return;
if(p==l->pHead){
k->pNext=l->pHead;
l->pHead=k;
return;
}
Node *prev=NULL;
Node *q= l->pHead;
for(;q;q=q->pNext){
if(q->pNext==p){
void ThemXTruocChanDau(List *l, int X){
Node *k = createNode(X);
Node *p= TimChanDau(l);
if(p==NULL){
addHead(l,k);
}
else
ThemkTruocp(l,p,k);
}
//Cau 7
Node * TimLeCuoi(List *l){
Node *p=l->pHead;
Node * pLeCuoi=NULL;
while(p!=NULL){
if(p->data %2!=0){
pLeCuoi=p;
}
p=p->pNext;
}
return pLeCuoi;
}
void ThemkSaup(List *l, Node *p, Node *k){
k-> pNext= p->pNext;
p->pNext=k;
}
void ThemXSauLeCuoi(List *l, int X){
Node *k= createNode(X);
Node *p= TimLeCuoi(l);
if(p==NULL){
addTail(l,k);
}
else ThemkSaup(l,p,k);
}
//Cau 8
Node * TimMin(List *l){
if(l->pHead==NULL) return NULL;
Node * pMin= l->pHead;
Node *p= l->pHead->pNext;
for(;p;p=p->pNext){
if(p->data < pMin->data){
pMin=p;
void XoaMin(List *l) {
if (isEmpty(l)) {
printf("Danh sach rong, khong the xoa!\n");
return;
}
}
}
return pMin;
}
// Ham xoa phan tu dau tien trong danh sach
void XoaDau(List *l) {
if (isEmpty(l)) {
printf("Danh sach rong, khong the xoa!\n");
return;
}
Node* temp = l->pHead;
l->pHead = l->pHead->pNext;
free(temp);
// N?u danh sách tr? nên r?ng
if (l->pHead == NULL) {
l->pTail = NULL;
}
}
// Ham xoa phan tu cuoi cung trong danh sach
void XoaCuoi(List *l) {
if (l->pHead == NULL) return; // Danh sách r?ng
if (l->pHead->pNext == NULL) { // Ch? có 1 ph?n
t?
free(l->pHead);
l->pHead = NULL;
} else {
Node *prev = NULL;
Node *p = l->pHead;
while (p->pNext != NULL) {
prev = p;
p = p->pNext;
}
free(p);
prev->pNext = NULL;
}
}
Node *minNode = TimMin(l);
if (minNode == l->pHead) {
XoaDau(l); // N?u ph?n t? nh? nh?t là ph?n t? d?
u tiên
return;
}
Node *prev = NULL;
Node *p = l->pHead;
// Duy?t d?n khi tìm th?y ph?n t? minNode
while (p != NULL && p != minNode) {
prev = p;
p = p->pNext;
}
if (prev != NULL) {
prev->pNext = minNode->pNext;
}
if (minNode == l->pTail) {
l->pTail = prev; // C?p nh?t pTail n?u minNode
là ph?n t? cu?i
}
free(minNode);
}
void XoaGiua(List *l) {
if (isEmpty(l)) {
printf("Danh sach rong, khong the xoa!\n");
return;
}
// Neu danh sach chi co 1 phan tu thi chi can xoa
dau
if (l->pHead == l->pTail) {
XoaDau(l);
return;
}
// Buoc 1: Tim do dai cua danh sach
int length = 0;
Node *p = l->pHead;
while (p != NULL) {
length++;
p = p->pNext;
// Ham xoa phan tu co gia tri nho nhat
}
4
5
// Buoc 2: Tim vi tri phan tu o giua
int midPos = length / 2;
// Buoc 3: Duyet den vi tri giua va xoa phan tu
Node *prev = NULL;
p = l->pHead;
int i;
for ( i = 0; i < midPos; i++) {
prev = p;
p = p->pNext;
}
// Neu `prev` khong NULL, nghia la phan tu can
xoa khong phai phan tu dau tien
if (prev != NULL) {
prev->pNext = p->pNext;
}
// Cap nhat `pTail` neu can
if (p == l->pTail) {
l->pTail = prev;
}
// Giai phong bo nho cho phan tu giua
free(p);
}
// Ham xoa tat ca cac so chan trong danh sach
void XoaSoChan(List *l) {
if (isEmpty(l)) return;
// Xoa phan tu dau tien neu la so chan
while (l->pHead != NULL && l->pHead->data %
2 == 0) {
XoaDau(l);
}
Node *prev = l->pHead;
Node *p = (l->pHead != NULL) ? l->pHead-
>pNext : NULL;
while (p != NULL) {
if (p->data % 2 == 0) {
prev->pNext = p->pNext;
if (p == l->pTail) {
l->pTail = prev;
} else {
prev = p;
p = p->pNext;
}
}
}
// Ham xoa tat ca cac so le trong danh sach
// Ham xoa tat ca cac so nguyen to trong danh sach
void XoaSoNguyenTo(List *l) {
if (isEmpty(l)) return;
// Xoa phan tu dau tien neu la so nguyen to
while (l->pHead != NULL && LaSNT(l->pHead-
>data)) {
XoaDau(l);
}
Node *prev = l->pHead;
Node *p = (l->pHead != NULL) ? l->pHead-
>pNext : NULL;
while (p != NULL) {
if (LaSNT(p->data)) {
prev->pNext = p->pNext;
if (p == l->pTail) {
l->pTail = prev;
}
free(p);
p = prev->pNext;
} else {
prev = p;
p = p->pNext;
}
}
}
void Xoap(List *l, Node *p) {
if (isEmpty(l) || p == NULL) return;
// N?u node p là node d?u tiên
if (p == l->pHead) {
XoaDau(l);
return;
}
}
free(p);
p = prev->pNext;
// N?u node p là node cu?i
if (p == l->pTail) {
Node *prev = l->pHead;
while (prev->pNext != p) {
prev = prev->pNext;
}
prev->pNext = NULL;
l->pTail = prev;
free(p);
return;
}
// Xóa node p ? gi?a
Node *prev = l->pHead;
while (prev->pNext != p) {
prev = prev->pNext;
}
prev->pNext = p->pNext;
free(p);
}
Node *TimX(List l, int X) {
Node *p = l.pHead;
while (p != NULL) {
if (p->data == X) return p;
p = p->pNext;
}
return NULL; // Không tìm th?y
}
void XoakTruocp(List *l, Node *p) {
if (p == l->pHead || isEmpty(l)) {
printf("Khong co node truoc hoac danh sach
rong!\n");
return; // Không có node nào tru?c p ho?c danh
sách r?ng
}
Node *prev = NULL;
Node *cur = l->pHead;
// Tìm node tru?c node p
while (cur->pNext != p && cur != NULL) {
prev = cur;
cur = cur->pNext;
}
// Xóa node cur (node tru?c node p)
if (cur == NULL) {
printf("Khong the xoa node truoc!\n");
return;
if (prev == NULL) { // cur là node d?u tiên
l->pHead = p;
} else {
prev->pNext = p;
}
free(cur);
}
void XoakSaup(List *l, Node *p) {
if (p == NULL || p->pNext == NULL) {
printf("Khong co node sau hoac node sau khong
ton tai!\n");
return; // Không có node nào sau p ho?c p là ph?
n t? cu?i cùng
}
Node *q = p->pNext;
p->pNext = q->pNext; // Liên k?t p v?i node sau
node q
if (q == l->pTail) {
l->pTail = p; // C?p nh?t node cu?i n?u q là ph?n
t? cu?i
}
free(q); // Gi?i phóng node q
}
void XoaTruocSauX(List *l, int X) {
Node *pX = TimX(*l, X);
if (pX == NULL) {
printf("Khong tim thay phan tu %d trong danh
sach\n", X);
return;
}
// Xóa ph?n t? tru?c pX
XoakTruocp(l, pX);
// Xóa ph?n t? sau pX
XoakSaup(l, pX);
}
void XoaX(List *l, int X) {
if (isEmpty(l)) return;
Node *p = l->pHead;
Node *prev = NULL;
}
// Duy?t qua danh sách liên k?t
6
7
while (p != NULL) {
if (p->data == X) {
// N?u node c?n xóa là node d?u
if (p == l->pHead) {
l->pHead = p->pNext; // C?p nh?t l?i node
d?u
free(p);
p = l->pHead; // Ti?p t?c duy?t t? node d?u
m?i
}
// N?u node c?n xóa là node gi?a ho?c cu?i
else {
prev->pNext = p->pNext;
if (p == l->pTail) { // N?u p là node cu?i
l->pTail = prev;
}
free(p);
p = prev->pNext; // Ti?p t?c duy?t t? node
ti?p theo
}
}
else {
prev = p;
p = p->pNext; // Chuy?n sang node ti?p theo
}
}
}
void Tach(List l, List *l1, List *l2) {
init(l1);
init(l2);
Node *p = l.pHead;
while (p != NULL) {
int k = p->data;
Node *pAdd = createNode(k);
if (LaSNT(k)) {
addHead(l1, pAdd); // Thêm vào danh sách s?
nguyên t?
} else {
addHead(l2, pAdd); // Thêm vào danh sách
còn l?i
}
p = p->pNext;
}
}
void SapXep(List *l) {
Node *p = l->pHead;
Node *q = p->pNext;
for (; p != NULL; p = p->pNext) {
for (; q != NULL; q = q->pNext) {
if (p->data > q->data) {
// Hoán d?i giá tr? c?a 2 node
int temp = p->data;
p->data = q->data;
q->data = temp;
}
}
}
}
Bài về SV
// Cấu trúc sinh viên
typedef struct {
char MSSV[10];
char HoTen[50];
char GioiTinh[10];
char DiaChi[100];
float DiemTB;
} SinhVien;
// Node chứa thông tin sinh viên
typedef struct NODE {
SinhVien data;
struct NODE *pNext;
} NODE;
// Danh sách liên kết chứa các sinh viên
typedef struct {
NODE *pHead;
} LIST;
// Tạo node mới cho danh sách sinh viên
NODE* TaoNode(SinhVien sv) {
NODE *newNode = (NODE*)
malloc(sizeof(NODE));
if (newNode == NULL) return NULL;
newNode->data = sv;
newNode->pNext = NULL;
return newNode;
}
// Thêm sinh viên vào cuối danh sách
void ThemCuoi(LIST &l, NODE *p) {
if (l.pHead == NULL) {
l.pHead = p;
} else {
NODE *tail = l.pHead;
while (tail->pNext != NULL) {
tail = tail->pNext;
}
tail->pNext = p;
}
}
// Hàm thêm một sinh viên vào danh sách
void ThemSinhVien(LIST &l) {
SinhVien sv;
printf("Nhap MSSV: ");
scanf("%s", sv.MSSV);
printf("Nhap ho va ten: ");
scanf(" %[^\n]", sv.HoTen);
printf("Nhap gioi tinh: ");
scanf("%s", sv.GioiTinh);
printf("Nhap dia chi: ");
scanf(" %[^\n]", sv.DiaChi);
printf("Nhap diem trung binh: ");
scanf("%f", &sv.DiemTB);
return;
}
prev = p;
p = p->pNext;
}
printf("Khong tim thay sinh vien voi MSSV: %s\n",
MSSV);
}
// Hàm sắp xếp danh sách sinh viên theo điểm trung
bình
void SapXepTheoDiemTB(LIST &l) {
for (NODE *p = l.pHead; p != NULL; p = p-
>pNext) {
for (NODE *q = p->pNext; q != NULL; q = q-
>pNext) {
if (p->data.DiemTB > q->data.DiemTB) {
SinhVien temp = p->data;
p->data = q->data;
q->data = temp;
}
}
NODE *newNode = TaoNode(sv); }
ThemCuoi(l, newNode); }
}
// Hàm in danh sách sinh viên
void InDanhSachSinhVien(LIST l) {
NODE *p = l.pHead;
while (p != NULL) {
printf("MSSV: %s, Ho va ten: %s, Gioi tinh: %s,
Dia chi: %s, Diem TB: %.2f\n",
p->data.MSSV, p->data.HoTen, p-
>data.GioiTinh, p->data.DiaChi, p->data.DiemTB);
p = p->pNext;
}
}
// Hàm xóa một sinh viên theo MSSV
void XoaSinhVien(LIST &l, char *MSSV) {
NODE *prev = NULL, *p = l.pHead;
while (p != NULL) {
if (strcmp(p->data.MSSV, MSSV) == 0) {
if (prev == NULL) {
l.pHead = p->pNext;
} else {
prev->pNext = p->pNext;
}
free(p);
// Hàm liệt kê các sinh viên có điểm trung bình >= 5.0
void LietKeSinhVienDiemTB(LIST l) {
NODE *p = l.pHead;
while (p != NULL) {
if (p->data.DiemTB >= 5.0) {
printf("MSSV: %s, Ho va ten: %s, Gioi tinh:
%s, Dia chi: %s, Diem TB: %.2f\n",
p->data.MSSV, p->data.HoTen, p-
>data.GioiTinh, p->data.DiaChi, p->data.DiemTB);
}
p = p->pNext;
}
}
// Hàm đếm số lượng sinh viên nam
int DemSoLuongNam(LIST l) {
int count = 0;
NODE *p = l.pHead;
while (p != NULL) {
if (strcmp(p->data.GioiTinh, "Nam") == 0) {
count++;
}
p = p->pNext;
}
8
9
return count;
}
// Hàm cập nhật điểm trung bình của một sinh viên
thông qua MSSV
void CapNhatDiemTB(LIST &l, char *MSSV, float
newDiemTB) {
NODE *p = l.pHead;
while (p != NULL) {
if (strcmp(p->data.MSSV, MSSV) == 0) {
p->data.DiemTB = newDiemTB;
return;
}
p = p->pNext;
}
printf("Khong tim thay sinh vien voi MSSV: %s\n",
MSSV);
}
Có them thuộc tính đếm và phát
sinh ngẫu nhiên
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct ttNode {
char key; // Ký tự từ 'A' đến 'Z'
int demi; // Số lần xuất hiện của ký tự
struct ttNode *pNext; // Con trỏ đến node tiếp
theo
} Node;
typedef struct {
Node *pHead;
Node *pTail;
} List;
// Khởi tạo danh sách rỗng
void InitList(List *l) {
l->pHead = NULL;
l->pTail = NULL;
}
newNode->key = key;
newNode->demi = 1;
newNode->pNext = NULL;
return newNode;
}
// Thêm một node vào cuối danh sách
void ThemCuoi(List *l, Node *p) {
if (l->pHead == NULL) {
l->pHead = p;
l->pTail = p;
} else {
l->pTail->pNext = p;
l->pTail = p;
}
}
// Tìm node chứa ký tự `key` trong danh sách, nếu tìm
thấy trả về con trỏ đến node đó, nếu không thì trả về
NULL
Node* TimKiem(List *l, char key) {
Node *p = l->pHead;
while (p != NULL) {
if (p->key == key) {
return p;
}
p = p->pNext;
}
return NULL;
}
Phát sinh ngẫu nhiên chữ từ A-Z
void PhatSinhNgauNhienKyTu(List *l) {
srand(time(0));
for (int i = 0; i < 100; i++) {
char randomChar = 'A' + rand() % 26; // Sinh ký
tự ngẫu nhiên từ 'A' đến 'Z'
Node *p = TimKiem(l, randomChar); // Kiểm
tra xem ký tự đã xuất hiện trong danh sách chưa
if (p != NULL) {
p->demi++; // Nếu đã có thì tăng số lần xuất
hiện
} else {
Node *newNode = TaoNode(randomChar);
ThemCuoi(l, newNode);
}
// Tạo một node mới với ký tự và số lần xuất hiện là 1 }
Node* TaoNode(char key) { }
Node *newNode = (Node*) malloc(sizeof(Node));
if (newNode == NULL) return NULL;
Phát sinh ngẫu nhiên số tù 0-100
void PhatSinhNgauNhienSo(List *l) {
srand(time(0));
for (int i = 0; i < 100; i++) {
int randomNum = rand() % 101; // Sinh số ngẫu
nhiên từ 0 đến 100
// int Ran= rand() % (1000-1+1)+1; (số từ 1-1000
ngẫu nhiên)
Node *p = TimKiem(l, randomNum); // Kiểm
tra xem số đã xuất hiện trong danh sách chưa
if (p != NULL) {
p->demi++; // Nếu đã có thì tăng số lần xuất
hiện
} else {
Node *newNode = TaoNode(randomNum);
ThemCuoi(l, newNode);
}
}
}
void HienThiDanhSach(List l) {
Node *p = l.pHead;
while (p != NULL) {
printf("Ky tu: %c, So lan xuat hien: %d\n", p-
>key, p->demi);
p = p->pNext;
curr = next; // Tiến curr lên vị trí của next
}
l->pHead = prev; // Đặt pHead thành prev (vì prev
sẽ là nút cuối cùng đã duyệt qua)
}
int main() {
List ds;
InitList(&ds);
// a. Phát sinh ngẫu nhiên 100 ký tự từ A->Z
PhatSinhNgauNhienKyTu(&ds);
// b.1. Hiển thị danh sách với số lần xuất hiện của
mỗi ký tự
printf("Danh sach cac ky tu va so lan xuat hien:\
n");
HienThiDanhSach(ds);
// b.2. Tìm phần tử xuất hiện nhiều nhất
Node *maxNode = TimMax(ds);
printf("\nKy tu xuat hien nhieu nhat: %c voi %d
lan\n", maxNode->key, maxNode->demi);
}
} // b.3. Đảo ngược danh sách
Node* TimMax(List l) {
Node *pMax = l.pHead;
Node *p = l.pHead->pNext;
while (p != NULL) {
if (p->demi > pMax->demi) {
pMax = p;
DaoNguocDanhSach(&ds);
printf("\nDanh sach sau khi dao nguoc:\n");
HienThiDanhSach(ds);
return 0;
}
}
p = p->pNext;
}
return pMax;
}
void DaoNguocDanhSach(List *l) {
Node *prev = NULL;
Node *curr = l->pHead;
Node *next = NULL;
l->pTail = l->pHead; // Đầu tiên đặt pTail là pHead
(vì nó sẽ là nút cuối sau khi đảo)
while (curr != NULL) {
next = curr->pNext; // Lưu lại nút tiếp theo
curr->pNext = prev; // Đảo con trỏ pNext của
nút hiện tại để trỏ về nút trước đó
prev = curr; // Tiến prev lên vị trí của curr
10

Tài liệu khác của Đại học Công nghiệp Thành phố Hồ Chí Minh

Preview text:

DS LIÊN KẾT scanf ("%d",&X); #include ThemXTruocChanDau(&ds,X); #include
printf ("\nDanh sach sau khi them vao truoc pt chan : ");
// dinh nghia cau truc danh sach lien ket output(ds); struct ttNode{ //Cau 7 int data;
printf ("\nNhap gia tri can them vao sau pt le: struct ttNode *pNext; "); }; scanf ("%d",&X); typedef struct ttNode Node; ThemXSauLeCuoi(&ds,X); struct ttList{
printf ("\nDanh sach sau khi them vao sau pt le Node *pHead, *pTail; : "); }; output(ds); typedef struct ttList List; //Cau 8
Node *minNode= TimMin(&ds); //khai bao cac nguyen mau ham if(minNode!=NULL){ void init(List *l);
printf ("\nGia tri nho nhat la: %d\n", int isEmpty(List *l); minNode->data);
void addHead(List *l,Node *pNew);
void addTail(List *l,Node *pNew);
} else printf("\nDanh sach rong"); Node * createNode(int x); SapXep(&ds); …
printf("\nDanh sach sau khi sx tang la: "); output(ds); //cai dat ham main // Xóa phan tu dau
int main(int argc, char *argv[]) { XoaDau(&ds); List ds;
printf("\nDs sau khi xoa phan tu dau:\n"); init(&ds); output(ds); input(&ds);
printf("Danh sach sau khi nhap :\n"); // Xóa phan tu cuoi output(ds); XoaCuoi(&ds); //Cau 3
printf("\nDanh sach sau khi xoa phan tu cuoi:\n");
printf("\nPhan tu mang gia tri chan la :"); output(ds); XuatChan(&ds); //cau 4 // Xóa phan tu giua
Node *maxNode= TimMax(&ds); if(maxNode!=NULL){ XoaGiua(&ds);
printf ("\nGia tri lon nhat la: %d\n",
printf("\nDanh sách sau khi xóa giua la: "); maxNode->data); output(ds);
} else printf("\nDanh sach rong"); //Cau 5 //Xoa Min int demSNT= DemSNT(&ds); XoaMin(&ds);
printf ("\nSo luong so nguyen to la: %d\
printf("\nDanh sach sau khi xoa min %d la:\ n",demSNT); n"); output(ds); //Cau 6 // Nhap X va xoa truoc sau X int X;
printf ("Nhap gia tri can them vao truoc pt
printf("Nhap gia tri X de xoa truoc va sau X: "); chan: "); scanf("%d", &X); 1 XoaTruocSauX(&ds, X);
printf("Danh sach sau khi xoa truoc va sau X:\n"); Node * createNode(int x){ output(ds); Node *p;
p = (Node *)malloc(sizeof(Node));
// // Tach danh sach thanh 2 danh sach if(p == NULL){
// Tach(ds, &dsNguyenTo, &dsConLai);
printf("Khong du bo nho cap phat.\n");
// printf("Danh sach cac so nguyen to:\n"); }else{ // output(dsNguyenTo); p->data = x;
// printf("Danh sach cac phan tu con lai:\n"); p->pNext = NULL; // output(dsConLai); } return p;
printf("Nhap gia tri X de xoa cac phan tu co gia tri } bang X: "); scanf("%d", &X); void input(List *l){ XoaX(&ds, X); init(l);
printf("Danh sach sau khi xoa cac phan tu bang int x; %d:\n", X); Node *pNew; output(ds); do{ printf("Hay nhap pt :"); return 0; scanf("%d",&x); } if(x == 0) break;
//cai dat cac thao tac cua DSLK pNew = createNode(x); void init(List *l){ if(pNew != NULL){
l->pHead = l->pTail = NULL; addTail(l,pNew); } } }while(1); int isEmpty(List *l){ }
return ((l->pHead == NULL) && (l->pTail == NULL)) ? 1 : 0; } void output(List l){ Node *p = l.pHead;
void addHead(List *l,Node *pNew){ while(p!=NULL){ if(isEmpty(l)){ printf("%d\t",p->data);
l->pHead = l->pTail = pNew; p = p->pNext; }else{ } pNew->pNext = l->pHead; printf("\n"); l->pHead = pNew; } } //Cau 3 } void XuatChan(List *l){ Node *p= l -> pHead;
void addTail(List *l,Node *pNew){ while(p){ if(isEmpty(l)){ if(p->data %2 ==0)
l->pHead = l->pTail = pNew; printf (" %d\t", p->data); }else{ p= p->pNext; l->pTail->pNext = pNew; } l->pTail = pNew; } } } //Cau 4 2 Node * TimMax(List *l){ prev=q; Node *pmax= l->pHead; break;
Node *p= l->pHead->pNext; } for(;p;p=p->pNext){ }
if(p->data > pmax->data) if(prev!=NULL){ pmax=p; prev->pNext=k; } k->pNext=p; return pmax; } } }
void ThemXTruocChanDau(List *l, int X){ //Cau 5 Node *k = createNode(X); int LaSNT(int x){ Node *p= TimChanDau(l); if(x<2) return 0; if(p==NULL){ int i; addHead(l,k); for(i=2;i*i<=x;i++){ } if(x%i==0) return 0; else } ThemkTruocp(l,p,k); return 1; } } //Cau 7 int DemSNT(List *l){ Node * TimLeCuoi(List *l){ int dem=0; Node *p= l->pHead; Node *p=l->pHead;
for(;p!= NULL; p=p->pNext){ Node * pLeCuoi=NULL; if(LaSNT(p->data)) while(p!=NULL){ dem++; if(p->data %2!=0){ } pLeCuoi=p; return dem; } } p=p->pNext; //Cau 6 } Node * TimChanDau(List *l){ return pLeCuoi; Node *p=l->pHead; } for(;p!=NULL;p=p->pNext){
void ThemkSaup(List *l, Node *p, Node *k){ if(p->data %2==0){ k-> pNext= p->pNext; return p; p->pNext=k; } } }
void ThemXSauLeCuoi(List *l, int X){ return NULL; Node *k= createNode(X); } Node *p= TimLeCuoi(l);
void ThemkTruocp(List *l, Node *p, Node *k){ if(p==NULL){ if(l->pHead==NULL) return; addTail(l,k); if(p==l->pHead){ k->pNext=l->pHead; } l->pHead=k; else ThemkSaup(l,p,k); return; } } //Cau 8 Node *prev=NULL; Node * TimMin(List *l){ Node *q= l->pHead;
if(l->pHead==NULL) return NULL; for(;q;q=q->pNext){ Node * pMin= l->pHead; if(q->pNext==p){
Node *p= l->pHead->pNext; 3 for(;p;p=p->pNext){ void XoaMin(List *l) {
if(p->data < pMin->data){ if (isEmpty(l)) { pMin=p;
printf("Danh sach rong, khong the xoa!\n"); return; } } } return pMin; Node *minNode = TimMin(l); } if (minNode == l->pHead) {
XoaDau(l); // N?u ph?n t? nh? nh?t là ph?n t? d? u tiên
// Ham xoa phan tu dau tien trong danh sach return; void XoaDau(List *l) { } if (isEmpty(l)) {
printf("Danh sach rong, khong the xoa!\n"); Node *prev = NULL; return; Node *p = l->pHead; }
// Duy?t d?n khi tìm th?y ph?n t? minNode
while (p != NULL && p != minNode) { Node* temp = l->pHead; prev = p;
l->pHead = l->pHead->pNext; p = p->pNext; free(temp); } if (prev != NULL) {
// N?u danh sách tr? nên r?ng
prev->pNext = minNode->pNext; if (l->pHead == NULL) { } l->pTail = NULL; if (minNode == l->pTail) { }
l->pTail = prev; // C?p nh?t pTail n?u minNode } là ph?n t? cu?i }
// Ham xoa phan tu cuoi cung trong danh sach free(minNode); void XoaCuoi(List *l) { }
if (l->pHead == NULL) return; // Danh sách r?ng void XoaGiua(List *l) {
if (l->pHead->pNext == NULL) { // Ch? có 1 ph?n if (isEmpty(l)) { t?
printf("Danh sach rong, khong the xoa!\n"); free(l->pHead); return; l->pHead = NULL; } } else { Node *prev = NULL;
// Neu danh sach chi co 1 phan tu thi chi can xoa Node *p = l->pHead; dau while (p->pNext != NULL) {
if (l->pHead == l->pTail) { prev = p; XoaDau(l); p = p->pNext; return; } } free(p); prev->pNext = NULL;
// Buoc 1: Tim do dai cua danh sach } int length = 0; } Node *p = l->pHead; while (p != NULL) { length++; p = p->pNext;
// Ham xoa phan tu co gia tri nho nhat } 4 } else {
// Buoc 2: Tim vi tri phan tu o giua prev = p; int midPos = length / 2; p = p->pNext; }
// Buoc 3: Duyet den vi tri giua va xoa phan tu } Node *prev = NULL; } p = l->pHead; int i;
// Ham xoa tat ca cac so le trong danh sach
for ( i = 0; i < midPos; i++) { prev = p; p = p->pNext;
// Ham xoa tat ca cac so nguyen to trong danh sach } void XoaSoNguyenTo(List *l) { if (isEmpty(l)) return;
// Neu `prev` khong NULL, nghia la phan tu can
xoa khong phai phan tu dau tien
// Xoa phan tu dau tien neu la so nguyen to if (prev != NULL) {
while (l->pHead != NULL && LaSNT(l->pHead- prev->pNext = p->pNext; >data)) { } XoaDau(l); } // Cap nhat `pTail` neu can if (p == l->pTail) { Node *prev = l->pHead; l->pTail = prev;
Node *p = (l->pHead != NULL) ? l->pHead- } >pNext : NULL;
// Giai phong bo nho cho phan tu giua while (p != NULL) { free(p); if (LaSNT(p->data)) { } prev->pNext = p->pNext;
// Ham xoa tat ca cac so chan trong danh sach if (p == l->pTail) { void XoaSoChan(List *l) { l->pTail = prev; if (isEmpty(l)) return; } free(p);
// Xoa phan tu dau tien neu la so chan p = prev->pNext;
while (l->pHead != NULL && l->pHead->data % } else { 2 == 0) { prev = p; XoaDau(l); p = p->pNext; } } } Node *prev = l->pHead; }
Node *p = (l->pHead != NULL) ? l->pHead- void Xoap(List *l, Node *p) { >pNext : NULL;
if (isEmpty(l) || p == NULL) return; while (p != NULL) {
// N?u node p là node d?u tiên if (p->data % 2 == 0) { if (p == l->pHead) { prev->pNext = p->pNext; XoaDau(l); if (p == l->pTail) { return; l->pTail = prev; } } free(p); // N?u node p là node cu?i p = prev->pNext; if (p == l->pTail) { 5 Node *prev = l->pHead;
if (prev == NULL) { // cur là node d?u tiên while (prev->pNext != p) { l->pHead = p; prev = prev->pNext; } else { } prev->pNext = p; prev->pNext = NULL; } l->pTail = prev; free(cur); free(p); } return; }
void XoakSaup(List *l, Node *p) {
if (p == NULL | p->pNext == NULL) { // Xóa node p ? gi?a
printf("Khong co node sau hoac node sau khong Node *prev = l->pHead; ton tai!\n"); while (prev->pNext != p) {
return; // Không có node nào sau p ho?c p là ph? prev = prev->pNext; n t? cu?i cùng } } prev->pNext = p->pNext; free(p); Node *q = p->pNext; }
p->pNext = q->pNext; // Liên k?t p v?i node sau Node *TimX(List l, int X) { node q Node *p = l.pHead; while (p != NULL) { if (q == l->pTail) {
if (p->data == X) return p;
l->pTail = p; // C?p nh?t node cu?i n?u q là ph?n p = p->pNext; t? cu?i } }
return NULL; // Không tìm th?y }
free(q); // Gi?i phóng node q
void XoakTruocp(List *l, Node *p) { }
if (p == l->pHead || isEmpty(l)) {
printf("Khong co node truoc hoac danh sach
void XoaTruocSauX(List *l, int X) { rong!\n"); Node *pX = TimX(*l, X);
return; // Không có node nào tru?c p ho?c danh if (pX == NULL) { sách r?ng
printf("Khong tim thay phan tu %d trong danh } sach\n", X); return; Node *prev = NULL; } Node *cur = l->pHead; // Xóa ph?n t? tru?c pX // Tìm node tru?c node p XoakTruocp(l, pX);
while (cur->pNext != p && cur != NULL) { prev = cur; // Xóa ph?n t? sau pX cur = cur->pNext; XoakSaup(l, pX); } } void XoaX(List *l, int X) {
// Xóa node cur (node tru?c node p) if (isEmpty(l)) return; if (cur == NULL) {
printf("Khong the xoa node truoc!\n"); Node *p = l->pHead; return; Node *prev = NULL; }
// Duy?t qua danh sách liên k?t 6 while (p != NULL) { Node *q = p->pNext; if (p->data == X) {
for (; p != NULL; p = p->pNext) {
// N?u node c?n xóa là node d?u
for (; q != NULL; q = q->pNext) { if (p == l->pHead) {
if (p->data > q->data) {
l->pHead = p->pNext; // C?p nh?t l?i node
// Hoán d?i giá tr? c?a 2 node d?u int temp = p->data; free(p); p->data = q->data;
p = l->pHead; // Ti?p t?c duy?t t? node d?u q->data = temp; m?i } } }
// N?u node c?n xóa là node gi?a ho?c cu?i } else { } prev->pNext = p->pNext;
Bài về SV
if (p == l->pTail) { // N?u p là node cu?i // Cấu trúc sinh viên l->pTail = prev; typedef struct { } char MSSV[10]; free(p); char HoTen[50];
p = prev->pNext; // Ti?p t?c duy?t t? node char GioiTinh[10]; ti?p theo char DiaChi[100]; } float DiemTB; } } SinhVien; else { prev = p;
// Node chứa thông tin sinh viên
p = p->pNext; // Chuy?n sang node ti?p theo typedef struct NODE { } SinhVien data; } struct NODE *pNext; } } NODE;
void Tach(List l, List *l1, List *l2) {
// Danh sách liên kết chứa các sinh viên init(l1); typedef struct { init(l2); NODE *pHead; } LIST; Node *p = l.pHead; while (p != NULL) {
// Tạo node mới cho danh sách sinh viên int k = p->data; NODE* TaoNode(SinhVien sv) { Node *pAdd = createNode(k); NODE *newNode = (NODE*) malloc(sizeof(NODE)); if (LaSNT(k)) {
if (newNode == NULL) return NULL;
addHead(l1, pAdd); // Thêm vào danh sách s? newNode->data = sv; nguyên t? newNode->pNext = NULL; } else { return newNode;
addHead(l2, pAdd); // Thêm vào danh sách } còn l?i }
// Thêm sinh viên vào cuối danh sách p = p->pNext;
void ThemCuoi(LIST &l, NODE *p) { } if (l.pHead == NULL) { } l.pHead = p; void SapXep(List *l) { } else { Node *p = l->pHead; 7 NODE *tail = l.pHead; return;
while (tail->pNext != NULL) { } tail = tail->pNext; prev = p; } p = p->pNext; tail->pNext = p; } }
printf("Khong tim thay sinh vien voi MSSV: %s\n", } MSSV); }
// Hàm thêm một sinh viên vào danh sách
void ThemSinhVien(LIST &l) {
// Hàm sắp xếp danh sách sinh viên theo điểm trung SinhVien sv; bình printf("Nhap MSSV: ");
void SapXepTheoDiemTB(LIST &l) { scanf("%s", sv.MSSV);
for (NODE *p = l.pHead; p != NULL; p = p- printf("Nhap ho va ten: "); >pNext) { scanf(" %[^\n]", sv.HoTen);
for (NODE *q = p->pNext; q != NULL; q = q- printf("Nhap gioi tinh: "); >pNext) { scanf("%s", sv.GioiTinh);
if (p->data.DiemTB > q->data.DiemTB) { printf("Nhap dia chi: "); SinhVien temp = p->data; scanf(" %[^\n]", sv.DiaChi); p->data = q->data;
printf("Nhap diem trung binh: "); q->data = temp; scanf("%f", &sv.DiemTB); } } NODE *newNode = TaoNode(sv); } ThemCuoi(l, newNode); } }
// Hàm liệt kê các sinh viên có điểm trung bình >= 5.0
// Hàm in danh sách sinh viên
void LietKeSinhVienDiemTB(LIST l) {
void InDanhSachSinhVien(LIST l) { NODE *p = l.pHead; NODE *p = l.pHead; while (p != NULL) { while (p != NULL) {
if (p->data.DiemTB >= 5.0) {
printf("MSSV: %s, Ho va ten: %s, Gioi tinh: %s,
printf("MSSV: %s, Ho va ten: %s, Gioi tinh:
Dia chi: %s, Diem TB: %.2f\n",
%s, Dia chi: %s, Diem TB: %.2f\n",
p->data.MSSV, p->data.HoTen, p-
p->data.MSSV, p->data.HoTen, p-
>data.GioiTinh, p->data.DiaChi, p->data.DiemTB);
>data.GioiTinh, p->data.DiaChi, p->data.DiemTB); p = p->pNext; } } p = p->pNext; } } }
// Hàm xóa một sinh viên theo MSSV
void XoaSinhVien(LIST &l, char *MSSV) {
// Hàm đếm số lượng sinh viên nam
NODE *prev = NULL, *p = l.pHead; int DemSoLuongNam(LIST l) { while (p != NULL) { int count = 0;
if (strcmp(p->data.MSSV, MSSV) == 0) { NODE *p = l.pHead; if (prev == NULL) { while (p != NULL) { l.pHead = p->pNext;
if (strcmp(p->data.GioiTinh, "Nam") == 0) { } else { count++; prev->pNext = p->pNext; } } p = p->pNext; free(p); } 8 return count; newNode->key = key; } newNode->demi = 1; newNode->pNext = NULL;
// Hàm cập nhật điểm trung bình của một sinh viên return newNode; thông qua MSSV }
void CapNhatDiemTB(LIST &l, char *MSSV, float newDiemTB) {
// Thêm một node vào cuối danh sách NODE *p = l.pHead;
void ThemCuoi(List *l, Node *p) { while (p != NULL) { if (l->pHead == NULL) {
if (strcmp(p->data.MSSV, MSSV) == 0) { l->pHead = p;
p->data.DiemTB = newDiemTB; l->pTail = p; return; } else { } l->pTail->pNext = p; p = p->pNext; l->pTail = p; } }
printf("Khong tim thay sinh vien voi MSSV: %s\n", } MSSV); }
// Tìm node chứa ký tự `key` trong danh sách, nếu tìm
thấy trả về con trỏ đến node đó, nếu không thì trả về
Có them thuộc tính đếm và phát NULL
Node* TimKiem(List *l, char key) {
sinh ngẫu nhiên Node *p = l->pHead; while (p != NULL) { #include if (p->key == key) { #include return p; #include } p = p->pNext; typedef struct ttNode { } char key;
// Ký tự từ 'A' đến 'Z' return NULL; int demi;
// Số lần xuất hiện của ký tự }
struct ttNode *pNext; // Con trỏ đến node tiếp
Phát sinh ngẫu nhiên chữ từ A-Z theo
void PhatSinhNgauNhienKyTu(List *l) { } Node; srand(time(0));
for (int i = 0; i < 100; i++) { typedef struct {
char randomChar = 'A' + rand() % 26; // Sinh ký Node *pHead;
tự ngẫu nhiên từ 'A' đến 'Z' Node *pTail;
Node *p = TimKiem(l, randomChar); // Kiểm } List;
tra xem ký tự đã xuất hiện trong danh sách chưa if (p != NULL) {
// Khởi tạo danh sách rỗng
p->demi++; // Nếu đã có thì tăng số lần xuất void InitList(List *l) { hiện l->pHead = NULL; } else { l->pTail = NULL;
Node *newNode = TaoNode(randomChar); } ThemCuoi(l, newNode); }
// Tạo một node mới với ký tự và số lần xuất hiện là 1 } Node* TaoNode(char key) { }
Node *newNode = (Node*) malloc(sizeof(Node));
Phát sinh ngẫu nhiên số tù 0-100
if (newNode == NULL) return NULL;
void PhatSinhNgauNhienSo(List *l) { 9 srand(time(0)); curr = next;
// Tiến curr lên vị trí của next
for (int i = 0; i < 100; i++) { }
int randomNum = rand() % 101; // Sinh số ngẫu nhiên từ 0 đến 100
l->pHead = prev; // Đặt pHead thành prev (vì prev
// int Ran= rand() % (1000-1+1)+1; (số từ 1-1000
sẽ là nút cuối cùng đã duyệt qua) ngẫu nhiên) }
Node *p = TimKiem(l, randomNum); // Kiểm int main() {
tra xem số đã xuất hiện trong danh sách chưa List ds; if (p != NULL) { InitList(&ds);
p->demi++; // Nếu đã có thì tăng số lần xuất hiện
// a. Phát sinh ngẫu nhiên 100 ký tự từ A->Z } else {
PhatSinhNgauNhienKyTu(&ds);
Node *newNode = TaoNode(randomNum); ThemCuoi(l, newNode);
// b.1. Hiển thị danh sách với số lần xuất hiện của } mỗi ký tự }
printf("Danh sach cac ky tu va so lan xuat hien:\ } n");
void HienThiDanhSach(List l) { HienThiDanhSach(ds); Node *p = l.pHead; while (p != NULL) {
// b.2. Tìm phần tử xuất hiện nhiều nhất
printf("Ky tu: %c, So lan xuat hien: %d\n", p- Node *maxNode = TimMax(ds); >key, p->demi);
printf("\nKy tu xuat hien nhieu nhat: %c voi %d p = p->pNext;
lan\n", maxNode->key, maxNode->demi); } }
// b.3. Đảo ngược danh sách Node* TimMax(List l) { DaoNguocDanhSach(&ds); Node *pMax = l.pHead;
printf("\nDanh sach sau khi dao nguoc:\n"); Node *p = l.pHead->pNext; HienThiDanhSach(ds); while (p != NULL) {
if (p->demi > pMax->demi) { return 0; pMax = p; } } p = p->pNext; } return pMax; }
void DaoNguocDanhSach(List *l) { Node *prev = NULL; Node *curr = l->pHead; Node *next = NULL;
l->pTail = l->pHead; // Đầu tiên đặt pTail là pHead
(vì nó sẽ là nút cuối sau khi đảo) while (curr != NULL) {
next = curr->pNext; // Lưu lại nút tiếp theo
curr->pNext = prev; // Đảo con trỏ pNext của
nút hiện tại để trỏ về nút trước đó prev = curr;
// Tiến prev lên vị trí của curr 10

Tài liệu liên quan: