Κοινή χρήση τεχνολογίας

Στοίβα δομών δεδομένων

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Τίτλος

Γεια σας φίλοι Ας μάθουμε τη δομή δεδομένων της στοίβας σήμερα!

1. Στοίβα

1.1 Βασικές έννοιες της στοίβας

Στοίβα: Μια ειδική γραμμική λίστα που επιτρέπει μόνο λειτουργίες εισαγωγής και διαγραφής σε σταθερό άκρο. Το άκρο που εισέρχεται στις λειτουργίες εισαγωγής και διαγραφής δεδομένων ονομάζεται κορυφή της στοίβας και το άλλο άκρο ονομάζεται κάτω μέρος της στοίβας.Τα στοιχεία δεδομένων στη στοίβα συμμορφώνονται μεLIFO Αρχή (Last In First Out). Μπορούμε να το φανταστούμε σαν να τρώμε κεμπάπ προβάτου,Βάλτο πρώταΤα κομμάτια του προβάτου πιέζονται μέσακάτω μέρος，το τελευταίοΤα κομμάτια του προβάτου είναι μέσαΣτην κορυφήτου.

Σπρώξιμο της στοίβας: Η λειτουργία εισαγωγής της στοίβας ονομάζεται push/push/push.Εισαγάγετε δεδομένα από την κορυφή της στοίβας。

Pop: Η λειτουργία διαγραφής της στοίβας ονομάζεται popping.Τα εξερχόμενα δεδομένα βρίσκονται επίσης στην κορυφή της στοίβας。

1.2 Υλοποίηση στοίβας

Η στοίβα μπορεί γενικά να υλοποιηθεί χρησιμοποιώντας έναν πίνακα για την υλοποίηση της στοίβας ή χρησιμοποιώντας μια συνδεδεμένη λίστα για την υλοποίηση της στοίβαςδομή πίνακαΗ εφαρμογή της στοίβας είναι απλούστερη και πιο αποτελεσματική.

Επειδή κατά την υλοποίηση της προσθήκης, διαγραφής, τροποποίησης και διεπαφής ερωτήματος του προηγούμενου πίνακα ακολουθιών (πίνακας ακολουθίας δομών δεδομένων) Είναι πολύ βολικό για εμάς να χρησιμοποιήσουμε τη δομή του πίνακα για εισαγωγή και διαγραφή από το τέλος, οπότε στην υλοποίηση της στοίβας ορίζουμε το άκρο του πίνακα ως το πάνω μέρος της στοίβας και το κεφάλι ως το κάτω μέρος του η στοίβα.

2. Εφαρμογή διασύνδεσης στοίβας

Η στοίβα, όπως και η λίστα ακολουθιών, μπορεί να σχεδιαστεί ως στατική στοίβα σταθερού μήκους ή ως δυναμικά αναπτυσσόμενη στοίβα.Επειδή η στοίβα σταθερού μήκους έχει μεγάλους περιορισμούς και δεν είναι πρακτική στην πράξη, εφαρμόζουμε κυρίως υποστήριξηΔυναμικά αναπτυσσόμενη στοίβα。

Όπως και στην προηγούμενη εφαρμογή διασύνδεσης λίστας ακολουθιών/συνδεδεμένης λίστας, δημιουργούμε πρώτα ένα αρχείο κεφαλίδας "Stack.h" και δύο αρχεία προέλευσης "Stack.c" και "Test.c".

Στοίβα.ηΟρισμός στοίβας, αναφορά αρχείου κεφαλίδας και δήλωση λειτουργίας διεπαφής
Στοίβα.γΥλοποίηση λειτουργιών διεπαφής
Δοκιμή.γΔοκιμάστε κάθε λειτουργία

Ας δείξουμε πρώτα τον πλήρη κώδικα του "Stack.h", μην ξεχάσετε να αναφέρετε το "Stack.h" στα 2 αρχεία πηγής

  1. #pragma once				//防止头文件被二次引用
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5.  
  6. typedef int ElemType;		//如果要修改存储的数据类型可直接在此修改
  7. typedef struct Stack {
  8. 	ElemType* arr;			//动态数组
  9. 	int top;				//栈顶
  10. 	int capacity;			//容量
  11. }Stack;
  12.  
  13.  
  14. void StackInit(Stack* ps);//初始化栈
  15.  
  16. void StackPush(Stack* ps, ElemType x);//入栈
  17.  
  18. void StackPop(Stack* ps);//出栈
  19.  
  20. ElemType StackTop(Stack* ps);//获取栈顶元素
  21.  
  22. int StackSize(Stack* ps);//获取栈中有效元素的个数
  23.  
  24. int StackEmpty(Stack* ps);//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  25.  
  26. void StackDestroy(Stack* ps);//销毁栈

Μεταξύ αυτών, η έννοια του "κορυφή" καθορίζεται από την αρχική τιμή, η οποία θα εξηγηθεί λεπτομερώς παρακάτω. Στη συνέχεια ξεκινάμε την υλοποίηση της διεπαφής.

(1) Στοίβα αρχικοποίησης
  1. //初始化栈
  2. void StackInit(Stack* ps) {
  3. 	assert(ps);		//断言,防止传入空指针
  4. 	ps->arr = NULL; //初始化数组,置空
  5. 	ps->capacity = 0;//top指向栈顶元素的下一个位置
  6. 	ps->top = 0;	 //初始化容量
  7. }

Για ευκολία κατανόησης, κατανοούμε κατά προσέγγιση την κορυφή στη δομή ως δείκτη του πίνακα.Εάν αρχικοποιήσουμε την κορυφή στο 0 κατά την προετοιμασία της στοίβας, δεν υπάρχουν δεδομένα στη στοίβα και η κορυφή δείχνει στην επόμενη θέση των κορυφαίων δεδομένων στη στοίβα.

Εάν αρχικοποιήσουμε το top σε -1, το top θα δείχνει τη θέση των κορυφαίων δεδομένων στη στοίβα. Είναι καλύτερο για εμάς να το αρχικοποιήσουμε στο 0 εδώ γιατί είναι βολικό να προσθέσουμε στοιχεία και να διαγράψουμε στοιχεία.

(2) Σπρώξτε στη στοίβα
  1. //入栈
  2. void StackPush(Stack* ps, ElemType x) {
  3. 	//扩容
  4. 	if (ps->capacity == ps->top) //容量已满,需要扩容
  5. 	{
  6. 		//如果容量为0,则扩容到4; 否则扩大2倍
  7. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
  8. 		//创建一个临时指针变量来存储新空间地址,防止开辟失败
  9. 		ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
  10. 		if (temp == NULL) //防止开辟失败出现空指针
  11. 		{
  12. 			perror("realloc fail!n");
  13. 			exit(1);
  14. 		}
  15. 		ps->arr = temp;	  //将临时指针变量中存放的新空间地址赋给arr
  16. 		ps->capacity = newCapacity;//空间容量更新
  17. 	}
  18. 	ps->arr[ps->top] = x;//将数据存放进栈顶元素的下一个位置
  19. 	ps->top++;//位置更新
  20. }

Επειδή υπάρχει διαφορά μεταξύ της στοίβας και του πίνακα ακολουθίας, δεν μπορούμε απευθείας να διασχίσουμε και να εκτυπώσουμε. Επομένως, εάν θέλουμε να εκτυπώσουμε τα στοιχεία στη στοίβα, πρέπει να χρησιμοποιήσουμε τη συνάρτηση StackEmpty και τη συνάρτηση StackPop, η οποία θα συζητηθεί αργότερα. .

(3) Πηγαίνετε έξω
  1. //出栈
  2. void StackPop(Stack* ps) {
  3. 	assert(ps);			//断言,防止传入空指针
  4. 	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
  5. 	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
  6. }
(4) Αποκτήστε το επάνω στοιχείο της στοίβας
  1. //获取栈顶元素
  2. ElemType StackTop(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	assert(ps->top);		//断言,防止栈为空
  5. 	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
  6. }
(5) Λάβετε τον αριθμό των έγκυρων στοιχείων στη στοίβα
  1. //获取栈中有效元素的个数
  2. int StackSize(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	return ps->top;			//top即为有效元素的个数
  5. }
(6) Ελέγξτε εάν η στοίβα είναι άδεια
  1. //检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  2. int StackEmpty(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	return ps->top == 0;	//如果top==0, 说明栈为空
  5. }

Αυτός είναι ο λόγος για τον οποίο το StackEmpty στον προηγούμενο ισχυρισμό πρέπει να προστεθείτελεστής λογικής άρνησηςΟ λόγος είναι ότι εάν η στοίβα είναι κενή, το StackEmpty επιστρέφει true και η άρνηση του false μπορεί να αποδείξει ότι υπάρχουν στοιχεία στη στοίβα.

(7) Καταστρέψτε τη στοίβα
  1. //销毁栈
  2. void StackDestroy(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	if (ps->arr)			//如果动态数组有效
  5. 	{
  6. 		free(ps->arr);		//释放arr
  7. 		ps->arr = NULL;		//将arr置空
  8. 	}
  9. 	ps->capacity = 0;		//数组的容量为0
  10. 	ps->top = 0;			//数组的栈顶top为0
  11.  
  12. }

Αφού ολοκληρωθούν όλες οι διεπαφές, ας δοκιμάσουμε τον κώδικα στο Test.c:

Ας το δοκιμάσουμε λίγο ακόμα:

Κανένα πρόβλημα Συγχαρητήρια για την ολοκλήρωση της εφαρμογής της στοίβας.

  1. #include"Stack.h"
  2.  
  3. //初始化栈
  4. void StackInit(Stack* ps) {
  5. 	assert(ps);		//断言,防止传入空指针
  6. 	ps->arr = NULL; //初始化数组,置空
  7. 	ps->capacity = 0;//top指向栈顶元素的下一个位置
  8. 	ps->top = 0;	 //初始化容量
  9. }
  10.  
  11. //入栈
  12. void StackPush(Stack* ps, ElemType x) {
  13. 	//扩容
  14. 	if (ps->capacity == ps->top) //容量已满,需要扩容
  15. 	{
  16. 		//如果容量为0,则扩容到4; 否则扩大2倍
  17. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
  18. 		//创建一个临时指针变量来存储新空间地址,防止开辟失败
  19. 		ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
  20. 		if (temp == NULL) //防止开辟失败出现空指针
  21. 		{
  22. 			perror("realloc fail!n");
  23. 			exit(1);
  24. 		}
  25. 		ps->arr = temp;	  //将临时指针变量中存放的新空间地址赋给arr
  26. 		ps->capacity = newCapacity;//空间容量更新
  27. 	}
  28. 	ps->arr[ps->top] = x;//将数据存放进栈顶元素的下一个位置
  29. 	ps->top++;//位置更新
  30. }
  31.  
  32. //出栈
  33. void StackPop(Stack* ps) {
  34. 	assert(ps);			//断言,防止传入空指针
  35. 	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
  36. 	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
  37. }
  38.  
  39. //获取栈顶元素
  40. ElemType StackTop(Stack* ps) {
  41. 	assert(ps);				//断言,防止传入空指针
  42. 	assert(ps->top);		//断言,防止栈为空
  43. 	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
  44. }
  45.  
  46. //获取栈中有效元素的个数
  47. int StackSize(Stack* ps) {
  48. 	assert(ps);				//断言,防止传入空指针
  49. 	return ps->top;			//top即为有效元素的个数
  50. }
  51.  
  52. //检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  53. int StackEmpty(Stack* ps) {
  54. 	assert(ps);				//断言,防止传入空指针
  55. 	return ps->top == 0;	//如果top==0, 说明栈为空
  56. }
  57.  
  58. //销毁栈
  59. void StackDestroy(Stack* ps) {
  60. 	assert(ps);				//断言,防止传入空指针
  61. 	if (ps->arr)			//如果动态数组有效
  62. 	{
  63. 		free(ps->arr);		//释放arr
  64. 		ps->arr = NULL;		//将arr置空
  65. 	}
  66. 	ps->capacity = 0;		//数组的容量为0
  67. 	ps->top = 0;			//数组的栈顶top为0
  68.  
  69. }

Τμήμα ασκήσεων

1. Ποια από τις παρακάτω προτάσεις σχετικά με τις στοίβες είναι σωστή ( )

Α. Η στοίβα είναι μια δομή δεδομένων "first in first out".

Β. Η στοίβα μπορεί να υλοποιηθεί χρησιμοποιώντας μια συνδεδεμένη λίστα ή μια διαδοχική λίστα

Γ. Η στοίβα μπορεί να εισάγει δεδομένα μόνο στο κάτω μέρος της στοίβας

Δ. Η στοίβα δεν μπορεί να διαγράψει δεδομένα

σωστή απάντηση: σι

Σφάλμα: Η στοίβα είναι μια δομή δεδομένων last-in-first-out και η ουρά είναι first-in, first-out.

Το B είναι σωστό: Και οι λίστες ακολουθιών και οι συνδεδεμένες λίστες μπορούν να χρησιμοποιηθούν για την υλοποίηση στοίβων, αλλά οι λίστες ακολουθιών χρησιμοποιούνται γενικά επειδή η στοίβα θεωρείται ως ευνουχισμένη έκδοση της λίστας ακολουθιών χρησιμοποιείται και η εισαγωγή της ουράς του πίνακα ακολουθίας χρησιμοποιείται.

Σφάλμα C: Η στοίβα μπορεί να εκτελέσει λειτουργίες εισαγωγής και διαγραφής εισόδου μόνο στο επάνω μέρος της στοίβας

Σφάλμα D: Η στοίβα έχει λειτουργίες push and pop είναι να διαγράψετε ένα στοιχείο από τη στοίβα.

2. Η ακολουθία ώθησης μιας στοίβας είναι ABCDE και η αδύνατη ακολουθία pop είναι ( )

A.ABCDE

B.EDCBA

C.DCEBA

D.ECDBA

σωστή απάντηση: ρε

Εάν το E βγει πρώτο, σημαίνει ότι το ABCDE έχει ωθηθεί στη στοίβα. Αφού το E βγει από τη στοίβα, το επάνω στοιχείο της στοίβας είναι D. Εάν βγει ξανά, θα πρέπει να είναι D, όχι C. .

Επομένως, θα πρέπει να επιλεγεί το D

3. Σε σύγκριση με τη διαδοχική στοίβα, τα προφανή πλεονεκτήματα της στοίβας αλυσίδας είναι ( )

Α. Η λειτουργία εισαγωγής είναι πιο βολική

Β. Η λειτουργία διαγραφής είναι πιο βολική

Γ. Δεν απαιτείται επέκταση κατά την ώθηση στη στοίβα

σωστή απάντηση: ντο

Σφάλμα A. Εάν είναι μια συνδεδεμένη στοίβα, απαιτεί γενικά λειτουργίες εισαγωγής κεφαλής ή διαγραφής κεφαλής, ενώ μια διαδοχική στοίβα εκτελεί γενικά λειτουργίες εισαγωγής και διαγραφής ουράς Η λειτουργία μιας συνδεδεμένης λίστας είναι πιο περίπλοκη από έναν διαδοχικό πίνακα απλούστερη η χρήση μιας διαδοχικής δομής για την υλοποίηση μιας στοίβας.

Το Β είναι λάθος, ανατρέξτε στο Α για τον λόγο.

Το C είναι σωστό Όταν η στοίβα υλοποιείται σε μια δομή αλυσίδας, κάθε ώθηση στη στοίβα ισοδυναμεί με την εισαγωγή ενός κόμβου στην κεφαλή της συνδεδεμένης λίστας.

4. Ποια από τις παρακάτω προτάσεις σχετικά με τη χρήση στοίβων για την υλοποίηση ουρών είναι λανθασμένη ( )

Α. Η χρήση της προσομοίωσης στοίβας για την υλοποίηση μιας ουράς μπορεί να χρησιμοποιήσει δύο στοίβες, μια στοίβα προσομοιώνει την είσοδο στην ουρά και μια στοίβα προσομοιώνει την έξοδο από την ουρά.

Β. Κάθε φορά που κάνετε dequeue, θα πρέπει να εισάγετε όλα τα στοιχεία μιας στοίβας σε μια άλλη στοίβα και στη συνέχεια να την αναδυάσετε.

Γ. Κατά την είσοδο στην ουρά, απλώς αποθηκεύστε τα στοιχεία απευθείας στη στοίβα που προσομοιώνει την είσοδο στην ουρά.

Δ. Η χρονική πολυπλοκότητα της λειτουργίας ουράς είναι O(1)

σωστή απάντηση: σι

Στην επιλογή Β, η μία στοίβα προσομοιώνει την είσοδο στην ουρά και η μία στοίβα προσομοιώνει την αφαίρεση ουράς, το επάνω στοιχείο της προσομοιωμένης στοίβας αναμονής εμφανίζεται απευθείας όταν η στοίβα είναι κενή, εισάγονται όλα τα στοιχεία της προσομοιωμένης στοίβας Είναι απαραίτητο να εισάγετε στοιχεία κάθε φορά, επομένως είναι λάθος.

Στην επιλογή Α, τα χαρακτηριστικά των στοίβων και των ουρών είναι αντίθετα Μια στοίβα δεν μπορεί να υλοποιήσει μια ουρά.

Στην επιλογή Γ, μια στοίβα προσομοιώνει την είσοδο στην ουρά και μια στοίβα προσομοιώνει την έξοδο από την ουρά Κατά την είσοδο στην ουρά, τα στοιχεία αποθηκεύονται απευθείας στη στοίβα που προσομοιώνει την είσοδο στην ουρά.

Στην επιλογή Δ, η ουρά σημαίνει την τοποθέτηση στοιχείων στη στοίβα, οπότε η χρονική πολυπλοκότητα είναι O(1)

Κατάληξη

Σήμερα μάθαμε για τη δομή δεδομένων μιας στοίβας Δεν είναι πολύ πιο απλή από μια συνδεδεμένη λίστα, ελπίζω αυτό το άρθρο να είναι χρήσιμο για τους φίλους μου.

ικετεύωΚάντε like, αγαπημένο και follow!!!

σας ευχαριστώ όλους! ! !

Προσωπικό προφίλ

Έχει αφοσιωθεί στην έρευνα της τεχνολογίας για περισσότερα από 30 χρόνια και είναι ικανός σε διάφορες γλώσσες όπως java, linux, javascript, php, css κ.λπ. Έχει κάνει πολλές συνεισφορές στον τομέα του ανοιχτού κώδικα σταθμός τεκμηρίωσης προγραμματιστή για να μοιραστείτε ορισμένα ζητήματα στην ανάπτυξη τεχνολογίας για μελλοντική αναφορά

τα στοιχεία επικοινωνίας μου

Ταχυδρομείο