Thêm 1 sinh viên vào cuối danh sách

QUẢN LÝ SINH VIÊN

LỜI NÓI ĐẦU
Công nghệ thông tin là một trong những ngành phát triển vượt bậc trong những năm gần đây.
Ngày nay với sự phát triển nhanh chóng của xã hội thì công nghệ thông tin được ứng dụng rộng rãi ở
hầu hết tất cả các lĩnh vực và ngày càng đóng vai trò quan trọng, trở thành một phần thiết yếu trong
đời sống hằng ngày. Công nghệ thông tin là một ngành đòi hỏi ở người học một nền tảng kiến thức
vững chắc, sự tư duy logic cao, hiểu biết sâu rộng trên nhiều lĩnh vực. Với chúng em hiện đang là
những sinh viên công nghệ thông tin cần phải có sự đầu tư, không ngừng học hỏi để nâng cao kiến
thức. Do đó để củng cố lại kiến thức đã học, đề tài mà em chọn để thực hiện đồ án là: Bài toán Quản
lí sinh viên bằng danh sách đặc.
Quản lý sinh viên là một đề tài không còn mới mẻ với các bài toán quản lý. Việc đưa tin học
vào ứng dụng để quản lý là rất hữu ích, vì chúng ta bỏ ra rất ít thời gian mà lại thu được hiệu quả
cao, rất chính xác và tiện lợi nhanh chóng.
Thông qua quá trình thực hiện đồ án, chúng em đã nắm bắt được những kỹ thuật quan trọng
của việc xây dựng cấu trúc dữ liệu và phân tích, thiết kế giải thuật sao cho tối ưu nhất. Bài toán Quản
lý sinh viên mà nhóm chúng em nghiên cứu và trình bày trong báo cáo sau đây là một ví dụ. Chúng
em xin chân thành cảm ơn cô Đỗ Thị Tuyết Hoa đã bổ sung ý tưởng và tận tình giúp đỡ chúng em thực
hiện đồ án này.
Trong quá trình thực hiện, không tránh khỏi sai xót. Chúng em rất mong nhận được sự góp ý từ
phía thầy cô để bài làm của chúng em được hoàn thiện hơn.
Đà Nẵng, ngày 02 tháng 06 năm 2017

1


QUẢN LÝ SINH VIÊN

MỤC LỤC
LỜI NÓI ĐẦU.01
MỤC LỤC 02

I

Cơ sở lý thuyết
1
2

II

Định nghĩa danh sách đặc .. 03
Biểu diễn danh sách đặc .03

Ứng dụng danh sách đặc vào quản lý sinh viên
1
2
3
4

Đặc tả hệ thống ....05
Yêu cầu hệ thống 05
Phân tích và thiết kế chương trình . 05
Thuật toán, độ phức tạp và cài đặt chương trình 08
4.1: Hiển thị danh sách sinh viên .. 10
4.2: Thêm một sinh viên vào danh sách 11
4.3: Tìm thông tin sinh viên theo họ và tên ... 12
4.4: Tìm thông tin sinh viên theo mã sinh viên .. 12
4.5: Xóa một sinh viên khỏi danh sách . 12
4.6: Tính điểm trung bình và xét học bổng ... 13
4.7: Xóa sinh viên nữ khóa 08 ... 13
4.8: Sắp xếp theo họ và tên 14
4.9: Chèn một sinh viên không thay đổi thứ tự sắp xếp 16

4.10: Thống kê số lượng học sinh và học bổng . 16
4.11: Hàm kiểm tra giới tính . 17
4.12: Hàm kiểm tra ngày tháng . 17
4.13: Hàm kiểm tra tên .. 17
4.14: Ghi kết quả ra file . 17

5. Kết quả chương trình . 18
6. Kết luận 23

2


QUẢN LÝ SINH VIÊN

CHƯƠNG 1: CƠ SỞ LÍ THUYẾT
I.
ĐỊNH NGHĨA DANH SÁCH ĐẶC
Danh sách đặc là danh sách mà không gian bộ nhớ lưu trữ các phần tử được đặt liên
tiếp nhau trong bộ nhớ
II.
BIỂU DIỄN DANH SÁCH ĐẶC

Để biểu diễn danh sách đặc chúng ta sử dụng một dãy [mảng] các phần tử có kiểu dữ liệu là
kiểu dữ liệu của các phần tử trong danh sách. Do vậy, chúng ta cần biết trước số phần tử tối đa của
mảng cũng chính là chiều dài tối đa của danh sách thông qua một hằng số nguyên. Ngoài ra, do
chiều dài của danh sách luôn luôn biến động cho nên chúng ta cũng cần quản lý chiều dài thực của
danh sách thông qua một biến nguyên.
Giả sử chúng ta quy ước chiều dài tối đa của danh sách đặc là 10000, khi đó cấu trúc dữ liệu để
biểu diễn danh sách đặc như sau:
const int MaxLen = 10000; // hoặc: #define MaxLen 10000

int Length;
T CD_LIST[MaxLen]; // hoặc: T * CD_LIST = new T[MaxLen];

Nếu chúng ta sử dụng cơ chế cấp phát động để cấp phát bộ nhớ cho danh sách đặc thì cần kiểm
tra sự thành công của việc cấp phát động.
a. Các thao tác cơ bản trên danh sách đặc
a. Khởi tạo danh sách [Initialize].
b. Tạo mới danh sách/ Nhập danh sách.
c. Thêm một phần tử vào danh sách.
d. Tìm kiếm một phần tử trong danh sách.
e. Loại bỏ bớt một phần tử ra khỏi danh sách.
f. Cập nhật giá trị cho một phần tử trong danh sách.
g. Sắp xếp thứ tự các phần tử trong danh sách.
h. Tách một danh sách thành nhiều danh sách.
i. Nhập nhiều danh sách thành một danh sách.
j. Sao chép một danh sách.
k. Hủy danh sách.
b. Ưu điểm và nhược điểm của danh sách đặc
Do các phần tử được lưu trữ liên tiếp nhau trong bộ nhớ, do vậy danh sách đặc có các
ưu nhược điểm sau đây:
Ưu điểm:
- Mật độ sử dụng bộ nhớ của danh sách đặc là tối ưu tuyệt đối [100%]
- Việc truy xuất và tìm kiếm các phần tử của danh sách đặc là dễ dàng vì các phần tử đứng
liền nhau nên chúng ta chỉ cần sử dụng chỉ số để định vị vị trí các phần tử trong danh sách
[định vị địa chỉ các phần tử]
3


QUẢN LÝ SINH VIÊN


Nhược điểm:
- Việc thêm, bớt các phần tử trong danh sách đặc có nhiều khó khăn do chúng ta phải di dời
các phần tử khác đi qua chỗ khác.
c. Ứng dụng của danh sách đặc
Danh sách đặc được ứng dụng nhiều trong các cấu trúc dữ liệu mảng: mảng 1 chiều,
mảng nhiều chiều; Mảng cấp phát tĩnh, mảng cấp phát động; mà chúng ta đã nghiên cứu và
thao tác khá nhiều trong quá trình lập trình trên nhiều ngôn ngữ lập trình khác nhau.

4


QUẢN LÝ SINH VIÊN

CHƯƠNG 2: ỨNG DỤNG DANH SÁCH ĐẶC VÀO QUẢN LÍ SINH VIÊN
I. ĐẶC TẢ BÀI TOÁN
Quản lý sinh viên là công việc hằng ngày của phòng quản lý học sinh- sinh viên. Công việc
quản lý sinh viên đòi hỏi tính tỉ mỉ, cẩn thận trong từng khâu ghi chép các thông tin cá nhân của sinh
viên: mã số sinh viên, tên sinh viên, ngày tháng năm sinh, lớp.cũng như công việc thống kê kết quả
học tập cần rõ ràng và chính xác. Trước đây công nghệ thông tin chưa phát triển mạnh mẽ, các công
việc được xử lý thủ công, chủ yếu là ghi chép bằng bút, sổ sách chính vì vậy rất tốn công sức và khá
nhiều thời gian. Ngày nay khi mà khoa học kỹ thuật phát triển, đặc biệt là sự bùng nổ công nghệ
thông tin thì việc quản lý sinh viên sẽ dễ dàng hơn nhiều. Xuất phát từ nhu cầu đó mà bài toán Quản
lý sinh viên ra đời. Yêu cầu của bài toán là tạo ra chương trình có thể thực hiện các thao tác quản lý
sinh viên một cách dễ dàng, tiện lợi dựa trên sự trợ giúp của máy tính. Mọi công việc phải được thao
tác trên một vùng dữ liệu chung để đảm bảo việc đồng bộ với nhau trong khâu quản lý
II. YÊU CẦU HỆ THỐNG
Quản lý điểm sinh viên là chương trình quản lý hồ sơ, điểm học tập của sinh viên trong quá
trình theo học tại trường. Chương trình có thể thực hiện các công việc thêm mới sinh viên, tìm kiếm
sinh viên theo một điều kiện nào đó, xóa sinh viên, liệt kê danh sách sinh viên.
Chương trình được viết bằng ngôn ngữ C và dựa trên cấu trúc lưu trữ của danh sách đặc

Hiện nay các trường đại học của Việt Nam, cũng như các doanh nghiệp đang trong tiến trình
ứng dụng mạnh mẽ sự phát triển của công nghệ thông tin vào quản lý. Mới đầu chỉ là những máy tính
cá nhân đơn giản và cho đến nay là các mạng thông tin phức tạp. Tuy nhiên do đặc điểm công nghệ
thông tin của Việt Nam mới trong quá trình phát triển nên mặc dù đã quan tâm đến việc ứng dụng
công nghệ thông tin vào quản lý nhưng các phần mềm hệ thống, các phần mềm trợ giúp hoặc phần
mềm quản lý có thể thay thế hoàn toàn công việc thủ công chưa được quan tâm. Với chương trình
quản lý sinh viên này hy vọng sẽ giúp cho công tác quản lý sinh viên diễn ra đơn giản và tiết kiệm
thời gian hơn
III. PHÂN TÍCH VÀ THIẾT KẾ CHƯƠNG TRÌNH
a. Cấu trúc dữ liệu chương trình
Để giúp cho việc quản lý được chặc chẽ, dễ dàng, chương trình quản lí sinh viên sẽ có các
trường hợp sau:

5


QUẢN LÝ SINH VIÊN

-

msv [mã sinh viên] có kiểu dữ liệu char, với độ dài 100 kí tự, mỗi sinh viên có một mã số
riêng, không trùng lặp
fullname [họ và tên] có kiểu dữ liệu char, với độ dài 100 kí tự, họ tên sinh viên có thể trùng
nhau
date [ngày sinh] có kiểu dữ liệu char, với độ dài 100 kí tự, ngày sinh có thể trùng nhau
gender [giới tính] có kiểu dữ liệu char, với độ dài 100 kí tự,
classs [lớp] có kiểu dữ liệu char, với độ dài 100 kí tự
math [điểm toán] có kiểu dữ liệu float
physics [điểm lý] có kiểu dữ liệu float
it [điểm tin] có kiểu dữ liệu float

dtb [điểm trung bình] có kiểu dữ liệu float, điểm trung bình được tính bằng cách lấy trung
bình cộng điểm thi các môn học của sinh viên
hb [học bổng]
typedef char infor1[100];
typedef float infor2;
struct element {
infor1 msv;
infor1 fullname;
infor1 date;
infor1 gender;
infor1 classs;
infor2 math;
infor2 physics;
infor2 it;
infor2 dtb;
infor2 hb;
};

b. Các chức năng của chương trình
1. Hiển thị danh sách sinh viên
- Duyệt danh sách sinh viên trong file
- In thông tin sinh viên ra màn hình
2. Thêm một sinh viên vào danh sách
- Nhập thông tin chi tiết cho một sinh viên.
- Chèn sinh viên vào danh sách ở vị trí đầu tiên.
3. Tìm thông tin sinh viên theo họ và tên
6


QUẢN LÝ SINH VIÊN


- Nhập họ và tên sinh viên từ bàn phím.
- Duyệt qua danh sách sinh viên.
- Tìm kiếm sinh viên theo họ tên mà người dùng yêu cầu.
- Hiển thị thông tin sinh viên cần tìm ra màn hình.
4. Tìm sinh viên theo mã số sinh viên
- Nhập mã số sinh viên từ bàn phím .
- Duyệt qua danh sách sinh viên.
- Tìm kiếm sinh viên theo họ tên mà người dùng yêu cầu.
- Hiển thị thông tin sinh viên cần tìm ra màn hình.
5. Xóa một sinh viên khỏi danh sách
- Nhập số thự tự cần xóa khỏi danh sách.
- Duyệt qua danh sách sinh viên.
- Tìm kiếm sinh viên theo số thứ tự mà người dùng yêu cầu.
- Xóa sinh viên vừa tìm được.
6. Tính điểm trung bình và xét học bổng
- Duyệt danh sách sinh viên
- Thực hiện tính điểm trung bình và xét học bổng của từng sinh viên
- Hiển thị danh sách sinh viên sau khi đã tính điểm trung bình và xét học bổng
7. Xóa các sinh viên nữ khóa 08
- Duyệt danh sách sinh viên
- Tìm kiếm sinh viên là nữ khóa 08
- Xóa các sinh viên vừa tìm được
8. Sắp xếp theo họ tên
7


QUẢN LÝ SINH VIÊN

- Duyệt danh sách sinh viên

- Sắp xếp danh sách sinh viên theo họ tên
- Hiển thị danh sách đã sắp xếp
9. Chèn một sinh viên không thay đổi thứ tự sắp xếp.
- Nhập thông tin sinh viên từ bàn phím.
- Duyệt danh sách sinh viên
- Hiển thị danh sách đã sắp xếp
10. Thống kê số lượng học sinh từng lớp và học bổng.
- Duyệt điểm trung bình và học bổng của từng sinh viên
- Hiển thị bảng tổng số sinh viên và tổng số học bổng của từng lớp
11. Hàm kiểm tra giới tính nhập từ bàn phím. [Nam/ Nữ]
- Trả về kết quả 1 nếu nhập đúng.
12. Hàm kiểm tra ngày tháng nhập từ bàn phím. [xx/xx/xx]
- Trả về kết quả 8 nếu nhập đúng.
13. Hàm kiểm tra tên nhập từ bàn phím . [[A-Z]xxx [A-Z]xxx [A-Z]xxx [A-Z]xxx]
- Trả về kết quả 1 nếu nhập đúng.
14. Ghi kết quả ra file
- Ghi kết quả ra file, thông tin mỗi sinh viên trên một hàng.
IV. THUẬT TOÁN, ĐỘ PHỨC TẠP VÀ CÀI ĐẶT CHƯƠNG TRÌNH
a. Định nghĩa cấu trúc cho chương trình quản lí sinh viên
- void insert[DS &A, int &n, int t,infor1 msv,infor1 fullname,infor1
gender,infor1 classs,infor2 math,infor2 physics,infor2 it]
- char *rtrim[char *s]
- void getlist[DS &A, int &n]
8

date,infor1


QUẢN LÝ SINH VIÊN


- void display[DS &A, int n]
- void gotoxy[int x, int y]
- void menu[]
- void Displayone [DS A,int i]
- void searchname [DS A,infor1 fullname]
- void searchid [DS A,infor1 fullname]
- void diemtrungbinh [DS &A,int &n]
- int check08[DS &A,int i]
- void dele[DS &A, int &n, int t]
- void delenu[DS &A, int &n]
- void OutputHB[DS A,int n]
- ChiTiet_Ten Tach_HovaTen[char *pTemp]
- int SoSanh[char *x, char *y]
- void SapXep[DS A, int n]
- void chenvao[DS &A, int &n, int t,infor1 msv,infor1 fullname,infor1
gender,infor1 classs,infor2 math,infor2 physics,infor2 it]
- void ghifile[DS A,int n]
- void ThongKe[DS A, int n]
- int checkdate[infor1 date]
- int checkgender[infor1 gender]
- int checkname[infor1 name]
- int main[]

b. Thuật toán và độ phức tạp :
1: Hiển thị danh sách sinh viên:
- Duyệt danh sách sinh viên trong file:
9

date,infor1



QUẢN LÝ SINH VIÊN

+Input : Dữ liệu từ một file .txt do người dùng định nghĩa.
+Output : Dữ liệu đã được nạp vào danh sách trong chương trình.
. Đọc dữ liệu từ tệp. Dữ liệu tệp là file .txt chứa danh sách sinh viên,mỗi hàng là thông tin của
một sinh viên bao gồm mã sinh viên, tên sinh viên ,ngày sinh, giới tính, lớp, điểm môn toán, lý, tin.
. Danh sách A, gồm các trường như trên.
.Đọc dữ liệu từ tệp:
Bước 1: Đọc từng hàng của tệp, lưu vào mảng ký tự A[i].
Bước 2: Thực hiện cắt chuỗi, gặp dấu ; thì sẽ cắt phần ở trước lưu vào biến
tương ứng, ví như gặp mã sinh viên thì sẽ cắt mã sinh viên lưu vào biến msv.
Bước 3: Các điểm toán, lý, tin sẽ chuyển từ kiểu ký tự sang số rồi lưu vào biến
điểm tương ứng [math, physics,it]
Bước 4: Sau khi đã hoàn thành việc chuyển các ký tự trên một hàng vào các biến
tương ứng, thực hiện ghi vào danh sách A bằng hàm insert [trình bày ở mục 2.4.2.2]
Bước 5: Thực hiện tương tự đến khi kết thúc file.
+Độ phức tạp thuật toán : trong trường hợp xấu nhất vòng while thực hiện n lần thì độ phức tạp
thuật toán là : T[n] = O[n].

.Tệp demo như sau :

- In thông tin sinh viên ra màn hình:
1. Hàm display dùng để in thông tin sinh viên ra màn hình.

10


QUẢN LÝ SINH VIÊN


2. Cho một biến i chạy từ 0 n-1 : Với mỗi biến i thì in dữ liệu trong danh sách ứng với vị trí
A[i] ra. Vị trí A[i] gồm các trường mã sinh viên[A[i].msv, họ tênA[i].fullname, ngày sinh A[i].date,
giới tính A[i].gender, lớp A[i].classs, điểm toán A[i].math, điểm lý A[i].physics , điểm tin A[i].it .
2: Thêm một sinh viên vào danh sách:
+ Input: Nhập thông tin sinh viên từ bàn phím [mã sinh viên, họ tên, ngày sinh, giới tính, lớp,
điểm toán, điểm lý, điểm tin]
+ Output: Danh sách sau khi đã thêm sinh viên
Bước 1: Đọc dữ liệu từ bàn phím, lưu vào các biến tương ứng đã được định nghĩa.
Dữ liệu ở đây bao gồm mã sinh viên [msv], họ và tên sinh viên [fullname], ngày sinh
[date], giới tính [gender], lớp [classs], điểm toán [math], điểm lý [physics], điểm tin [it].
Bước 2: Dùng hàm Insert, chèn dữ liệu của sinh viên đã nhập vào bảng.
* Hàm Insert có các giá trị truyền vào hàm [A, n, t, msv, fullname, date, gender, classs, math,
physics, it] trong đó:
A
: tên danh sách.
n
: số các phần tử đã khởi tạo.
t
: vị trí chèn vào
msv
: mã sinh viên
fullname : họ và tên
date
: ngày sinh
gender : giới tính
classs
: lớp
math
: điểm toán
physics : điểm lý

it
: điểm tin
Bước 3: Khởi tạo biến i, biến i là biến đệm dùng để duyệt danh sách trong chương
trình.
Bước 4 : Nếu t có giá trị từ 0 n-1 thì dịch dữ liệu danh sách lên 1 đơn vị kể từ vị
trí t, sao chép dữ liệu đã nhập vào vị trí i=t. Cụ thể :
Bước 4.1: Cho biến i chạy từ n-1 đến t :
Bước 4.2: Với mỗi i gán A[i+1] =A[i] [Dịch dữ liệu lên 1 đơn vị ]
Bước 4.3: Sao chép dữ liệu đã nhập vào các trường A[t].
Bước 4.4: Sau khi thực hiện xong công việc, tăng n lên 1 đơn vị vì độ dài danh
sách đã tăng lên 1.
Trong trường hợp chèn dữ liệu đã nhập vào bảng, mặc định của t=0 để chèn dữ liệu vào
vị trí đầu tiên.

11


QUẢN LÝ SINH VIÊN

Trong trường hợp xấu nhất vòng for lặp lại n lần : O[n]
Vậy độ phức thuật toán là T[n] = = O[n²].
3: Tìm thông tin sinh viên theo họ và tên:
+ Input : Họ và tên sinh viên nhập từ bàn phím, danh sách đã nạp dữ liệu.
+ Output : Thông tin sinh viên tìm được, nếu tìm không có thì báo không tìm thấy
Bước 1: Nhập tên sinh viên vào từ bàn phím, lưu vào biến fullname.
Bước 2: Duyệt chương trình từ đầu đến cuối danh sách [0 n-1] :
Bước 3: Khởi tạo một biến k để kiểm tra trong danh sách có sinh viên cần tìm hay
không, nếu kết thúc chương trình k=0 thì không có sinh viên trong danh sách, ngược
lại thì có.
Bước 4: Nếu so sánh trường A[i].fullname = fullname thì thực hiện đồng thời việc

hiển thị thông tin sinh viên đó ra với hàm Displayone, tăng k lên 1 đơn vị.
Bước 5: Nếu k=0 thông báo tìm không có sinh viên trong danh sách.
Hàm Displayone để hiển thị thông tin 1 sinh viên, tương tự như hàm Display nhưng
Displayone chỉ duyệt 1 phần tử trong danh sách để hiển thị.
+ Độ phức tạp thuật toán : Trong trường hợp xấu nhất lặp lại n lần thì T[n] = O[n].
4 : Tìm thông tin sinh viên theo mã số sinh viên:
+ Input : Mã số sinh viên nhập từ bàn phím , danh sách đã nạp dữ liệu.
+ Output : Thông tin sinh viên tìm được, nếu tìm không có thì báo không tìm thấy.
Tương tự như tìm theo họ và tên, chỉ khác tìm theo mã số sinh viên sẽ so sánh với trường
A[i].msv.
+ Độ phức tạp thuật toán : Trong trường hợp xấu nhất lặp lại n lần thì T[n] = O[n].
5 : Xóa một sinh viên khỏi danh sách
+ Input : Nhập vào vị trí cần xóa , danh sách đã nạp dữ liệu.
+ Output : Danh sách sinh viên sau khi đã xóa một sinh viên.
12


QUẢN LÝ SINH VIÊN

Hàm dele[A,n,t] trong đó A: danh sách, n: số các đối tượng đã khởi tạo, t: vị trí.
Bước 1: Nhập vào vị trí cần xóa [ví trí từ 0 n-1], vị trí cần xóa tương ứng với t, nếu
vị trí cần xóa ngoài tầm thì thông báo lỗi.
Bước 2: Nếu vị trí trong tầm thì dịch danh sách lên 1 đoạn là 1 kể từ vị trí t, tức là
cho một biến i tạm chạy từ t n-1 gán A[i-1]=A[i].
Bước 3: Nếu xóa được thì giảm n đi một đơn vị.
+ Độ phức tạp thuật toán : T[n] = O[n].
6 : Tính điểm trung bình và xét học bổng
+ Input : Danh sách sinh viên đã nạp dữ liệu.
+ Output :Danh sách đã tính điểm trung bình và xét học bổng.
. Tính điểm trung bình và học bổng : hàm diemtrungbinh[A,i].

Bước 1: Duyệt danh sách từ đầu đến cuối
Bước 2: Ứng với mỗi phần tử tính trường điểm trung bình bằng trung bình cộng của
3 trường điểm toán, lý, tin.
Bước 3: Kiểm tra nếu điểm trung bình >=8 thì học bổng =200, nếu điểm trung bình
>=7 và