Bài tập Cấu trúc dữ liệu | Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Hà Nội

DSA06 //Bai 1 //a) #include #include #include void revString(char str[]){ int len = strlen(str); for(int i=0;i char a=str[i]; str[i]=str[len - 1 - i]; str[len-i]=a; } } void printStr(char str[]){ int len=strlen(str);
for(int i=0;i printf("%c", str[i]); } } int main(){
char a[]="hsjkfbaibfauibfiavbaiufsfudbfaiudb"; printStr(a); printf("\n"); revString(a); printStr(a); } //b) #include #include #include #define Max 5 typedef struct Stack { int a[Max]; int top; } Stack; void initStack(Stack *s){ s->top = -1; } int isEmpty(Stack *s){
if(s->top == -1) return 1; return 0; } int isFull(Stack *s){
if(s->top == Max - 1) return 1; return 0; }
void push(Stack *s, int value){ if(isFull(s)){ printf("Stack full\n"); return; } s->top++; s->a[s->top] = value; } int pop(Stack *s){ if(isEmpty(s)){ return -1; }
int value = s->a[s->top]; s->top--; return value; } void printStack(Stack *s){ if(isEmpty(s)){ printf("Stack empty\n"); return; } printf("Stack: ");
for(int i=0; i<=s->top; i++){ printf("%d ", s->a[i]); } printf("\n"); } //Cau b: #include #include #include #define Max 1000 typedef struct Stack { int a[Max]; int top; } Stack; void initStack(Stack *s){ s->top = -1; } int isEmpty(Stack *s){
if(s->top == -1) return 1; return 0; } int isFull(Stack *s){
if(s->top == Max - 1) return 1; return 0; }
void push(Stack *s, int value){ if(isFull(s)){ printf("Stack full\n"); return; } s->top++; s->a[s->top] = value; } int pop(Stack *s){ if(isEmpty(s)){ return -1; }
int value = s->a[s->top]; s->top--; return value; } void printStack(Stack *s){ if(isEmpty(s)){ printf("Stack empty\n"); return; } printf("Stack: ");
for(int i=0; i<=s->top; i++){ printf("%d ", s->a[i]); } printf("\n"); } void printStr(char str[]){ int len=strlen(str);
for(int i=0;i printf("%c", str[i]); } } int main(){ Stack s; initStack(&s); char a[1000]; fgets(a, sizeof(a), stdin);
printf("Ur input string:\n"); printStr(a); int len=strlen(a);
for(int i=0;i push(&s,a[i]); }
for(int i=0;i a[i]=pop(&s); }
printf("The reverse string:"); printStr(a); } #include #include #include #define Max 1000 typedef struct Stack { int a[Max]; int top; } Stack; void initStack(Stack *s){ s->top = -1; } int isEmpty(Stack *s){
if(s->top == -1) return 1; return 0; } int isFull(Stack *s){
if(s->top == Max - 1) return 1; return 0; }
void push(Stack *s, int value){ if(isFull(s)){ printf("Stack full\n"); return; } s->top++; s->a[s->top] = value; } int pop(Stack *s){ if(isEmpty(s)){ return -1; }
int value = s->a[s->top]; s->top--; return value; } void printStr(char str[]){ int len = strlen(str);
for(int i=0; i printf("%c", str[i]); } printf("\n"); }
void checkParenthesis(char str[]){ Stack s; initStack(&s); int errors[Max]; int count = 0; int len = strlen(str);
if(len > 0 && str[len-1] == '\n'){ str[len-1] = '\0'; len--; }
for(int i=0; i char c = str[i];
if(c == '(' || c == '[' || c == '{'){ push(&s, c); }
else if(c == ')' || c == ']' || c == '}'){
char open = (char)pop(&s); char expect;
if(open == '(') expect = ')';
else if(open == '[') expect = ']';
else if(open == '{') expect = '}'; if(c != expect){ errors[count] = i; count++; str[i] = expect; } } } if(count == 0){ printf("No error.\n"); } else { printf("Error at");
for(int i=0; i if(i == 0) printf(" %d", errors[i]);
else printf(", %d", errors[i]); } printf("\n"); printStr(str); } } int main(){ char str[Max]; // printf("Input: ");
fgets(str, sizeof(str), stdin); checkParenthesis(str); return 0; } #include #include #include #include #define Max 100 typedef struct Stack { int a[Max]; int top; } Stack; void initStack(Stack *s){ s->top = -1; } int isEmpty(Stack *s){
if(s->top == -1) return 1; return 0; } int isFull(Stack *s){
if(s->top == Max - 1) return 1; return 0; }
void push(Stack *s, int value){ if(isFull(s)){ return; } s->top++; s->a[s->top] = value; } int pop(Stack *s){ if(isEmpty(s)){ return -1; }
int value = s->a[s->top]; s->top--; return value; } int getPriority(char c){
if(c == '*' || c == '/') return 2;
if(c == '+' || c == '-') return 1; return 0; } int main(){ char input[Max]; printf("Input: "); scanf("%s", input); Stack s; initStack(&s); char postfix[Max]; int k = 0; int len = strlen(input);
for(int i=0; i char c = input[i]; if(isdigit(c)){ postfix[k] = c; k++; }
else if(c == '+' || c == '-' || c == '*' || c == '/'){
while(!isEmpty(&s) && getPriority((char)s.a[s.top]) >= getPriority(c)){
postfix[k] = (char)pop(&s); k++; } push(&s, c); } } while(!isEmpty(&s)){
postfix[k] = (char)pop(&s); k++; } postfix[k] = '\0'; printf("%s\n", postfix); initStack(&s);
for(int i=0; i char c = postfix[i]; if(isdigit(c)){ push(&s, c - '0'); } else{ int val2 = pop(&s); int val1 = pop(&s); int res = 0;
if(c == '+') res = val1 + val2;
else if(c == '-') res = val1 - val2;
else if(c == '*') res = val1 * val2;
else if(c == '/') res = val1 / val2; push(&s, res); } }
printf("Result = %d\n", pop(&s)); } return 0; } #include #define Max 100 typedef struct { int head, tail; int a[Max]; } Queue; void init(Queue* q) { q->head = 0; q->tail = -1; } int isEmpty(Queue* q) {
if (q->head > q->tail) { return 1; } return 0; } int isFull(Queue* q) { if (q->tail == Max - 1) { return 1; } return 0; }
void put(Queue* q, int value) { if (isFull(q)) {
printf("Hang doi da day!\n"); return; } q->tail++; q->a[q->tail] = value; } int get(Queue* q) { if (isEmpty(q)) { return -1; }
int value = q->a[q->head]; q->head++; return value; } void displayQueue(Queue* q) {
printf("Danh sach dang ky: "); if (isEmpty(q)) { printf("Trong\n"); } else {
for (int i = q->head; i <= q->tail; i++) { printf("%d ", q->a[i]); } printf("\n"); } }
void cancelRegistration(Queue* q, int id) { if (isEmpty(q)) {
printf("Hang doi rong, khong the huy.\n"); return; } int index = -1;
for (int i = q->head; i <= q->tail; i++) { if (q->a[i] == id) { index = i; break; } } if (index != -1) {
for (int i = index; i < q->tail; i++) { q->a[i] = q->a[i + 1]; } q->tail--;
printf("Da huy dang ky ID %d\n", id); } else {
printf("Khong tim thay ID %d trong hang doi\n", id); } } int main() { Queue q; init(&q); int choice; int id; int run = 1; while (run) {
printf("1. Dang ky nguoi dung (put)\n");
printf("2. Xu ly nguoi dau hang (get)\n");
printf("3. Huy dang ky (cancelRegistration)\n");
printf("4. Hien thi danh sach (displayQueue)\n"); printf("5. Thoat\n"); printf("Nhap lua chon: "); scanf("%d", &choice); if (choice == 1) {
printf("Nhap ID nguoi dung: "); scanf("%d", &id); put(&q, id); } else if (choice == 2) { if (isEmpty(&q)) {
printf("Hang doi rong, khong co ai de xu ly.\n"); } else { id = get(&q);
printf("Thong tin nguoi duoc xu ly: ID %d\n", id);