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

Δομή Δεδομένων (Μέρος 2)--Γραμμικός Πίνακας

2024-07-12

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

Πίνακας περιεχομένων

1. Βασικές έννοιες

2. Βασικές πράξεις γραμμικών πινάκων

3. Πίνακας ακολουθιών

(1).Στατική κατανομή

(2).Δυναμική κατανομή

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

(4) Αναζήτηση κατά σειρά bit, αναζήτηση κατά τιμή

4. Συνδεδεμένη λίστα

(1).Μοναδικά συνδεδεμένη λίστα

i Ορισμός της μεμονωμένης συνδεδεμένης λίστας (οδηγός κόμβος)

1. Βασικές έννοιες

Γραμμικός πίνακας:

(1) Κάθε στοιχείο σε αυτό,Ίδιος τύπος δεδομένων。

(2) Μεταξύ στοιχείων,Για να。

(3).στοιχείο κεφαλίδαςκαιστοιχείο ουράς。

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

2. Βασικές πράξεις γραμμικών πινάκων

τραπέζιΑπό την αρχή

InitList(&L):αρχικοποίησηένας γραμμικός πίνακας

DestroyList(&L):καταστρέφω

。

ListInsert(&L, i, e)：εισάγετε, εισάγετε το στοιχείο e στην i-η θέση στον πίνακα L

ListDelete(&L, i, &e)：διαγράφω, διαγράψτε το i-ο στοιχείο του πίνακα L και χρησιμοποιήστε το e για να επιστρέψετε το διαγραμμένο στοιχείο

。

LocateElem(L, e): ΠατήστεαξίαΑναζητήστε, βρείτε το στοιχείο της συγκεκριμένης λέξης κλειδιού e στον πίνακα, επιστρέψτε τη σειρά του e, όχι τον δείκτη

GetElem(L, i): πατήστεΚομμάτιΑναζήτηση για να λάβετε την τιμή του i-ου στοιχείου στον πίνακα

。

Άλλες γενικές λειτουργίες:

Μήκος(L): ΕύρεσητραπεζοκαθηγητήςΔαπανήσει

PrintList(L):παραγωγήτραπέζιόλαστοιχείο

Empty(L): Πίνακας κρίσηςΕίναι άδειο, επιστρέφει true ή false

Εξαιρετικά συνοπτικά, δηλαδή δημιουργία πωλήσεων και προσθήκη, διαγραφή, τροποποίηση και έλεγχος

3. Πίνακας ακολουθιών

μεδιαδοχική αποθήκευσηγραμμικός πίνακας δεδομένων

(1).Στατική κατανομή

  1. #define MAX 10
  2. //顺序表（静态分配）
  3. class SqList
  4. {
  5. public:
  6.     int data[MAX];
  7.     int length;
  8. };
  9. //初始化
  10. void InitList(SqList &l)
  11. {
  12.     for(int i = 0 ;i < 10 ;i++)
  13.     {
  14.         l.data[i] = 0;
  15.     }
  16.     l.length = 0;
  17. }
  18. //打印所有元素
  19. void PrintList(SqList &l)
  20. {
  21.     for (int i = 0; i < 10; i++)
  22.         cout << "第" << i << "个数：" << l.data[i] << endl;
  23. }
  24.  
  25. //测验
  26. void test01()
  27. {
  28.     SqList l;
  29.     InitList(l);
  30.     PrintList(l);
  31. }

(2).Δυναμική κατανομή

  1. #define InitSize 10
  2. //顺序表（动态分配）
  3. class SqList
  4. {
  5. public:
  6. 	int* data;		//指示动态分配数组的指针
  7. 	int MaxSize;	//指示最大容量
  8. 	int length;		//指示当前长度
  9. };
  10. //初始化顺序表
  11. void InitList(SqList& l)
  12. {
  13. 	l.data = new int[InitSize];
  14. 	l.MaxSize = InitSize;
  15. 	l.length = 0;
  16. 	for (int i = 0; i < l.MaxSize; i++)
  17. 	{
  18. 		l.data[i] = 0;
  19. 	}
  20. }
  21. //增长数组空间
  22. void IncreaseSize(SqList& l, int len)
  23. {
  24. 	int* p = l.data;					//暂存原数组中的数据
  25. 	l.data = new int[10 + len];			//扩展新的数组
  26. 	for (int i = 0; i < l.length; i++)	//将原数据拷贝进新数组中
  27. 	{
  28. 		l.data[i] = p[i];
  29. 	}
  30. 	l.MaxSize = InitSize + len;			//修改数组的状态数据
  31. 	delete p;							//将p释放
  32. }
  33. //打印所有元素
  34. void PrintList(SqList& l)
  35. {
  36. 	for (int i = 0; i < 10; i++)
  37. 		cout << "第" << i << "个数：" << l.data[i] << endl;
  38. }
  39.  
  40. void test01()
  41. {
  42. 	SqList l;
  43. 	InitList(l);
  44. 	PrintList(l);
  45. }

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

//εισάγετε

bool ListInsert(SqList& l, int d, int e)
{
if (l.length &gt;= MAX) //Πρώτα, καθορίστε εάν ο πίνακας είναι γεμάτος και εάν η εισαγωγή είναι νόμιμη.
    {
cout &lt;&lt; "Η εισαγωγή απέτυχε, το ανώτατο όριο έχει φτάσει" &lt;&lt; endl;
επιστροφή ψευδής?
    }
        
αν (d &lt; 1 || d &gt; l.μήκος + 1)
    {
cout &lt;&lt; "Η εισαγωγή απέτυχε, δεν υπάρχει άμεσος προκάτοχος" &lt;&lt; endl;
επιστροφή ψευδής?
    }
for (int j = l.length; j &gt;= d; j--) //Μετακίνηση του στοιχείου μετά το σημείο εισαγωγής προς τα πίσω
l.data[j] = l.data[j - 1];
l.data[d - 1] = e;
l.μήκος++;
επιστροφή αληθινή?
}

//διαγράφω
bool ListDelete(SqList& l, int d, int &e)
{
if (d &lt; 1 || d &gt;l.length) //Προσδιορίστε εάν η διαγραμμένη θέση είναι νόμιμη
επιστροφή ψευδής?
e = l.data[d - 1] //Προσωρινή αποθήκευση διαγραμμένων στοιχείων
for (int j = d; j &lt; l.length; j++) //Μετακίνηση του στοιχείου μετά το διαγραμμένο στοιχείο προς τα εμπρός
l.data[j - 1] = l.data[j] //Εδώ, πρέπει να είναι j = d, j-1 καλύπτεται από j, αν j = d-1, η ακόλουθη κάλυψη θα γίνει j καλύπτεται; Το j+1 καλύπτει και το j+1 μπορεί να υπερβεί τη μέγιστη χωρητικότητα του πίνακα στο τέλος
λ.μήκος--;
επιστροφή αληθινή?
}

Δείγμα κώδικα

  1. #define MAX 10
  2. //顺序表（静态分配）
  3. class SqList
  4. {
  5. public:
  6.     int data[MAX];
  7.     int length;
  8. };
  9. //初始化
  10. void InitList(SqList& l)
  11. {
  12.     for (int i = 0; i < 10; i++)
  13.     {
  14.         l.data[i] = 0;
  15.     }
  16.     l.length = 0;
  17. }
  18. //打印所有元素
  19. void PrintList(SqList& l)
  20. {
  21.     for (int i = 0; i < 10; i++)
  22.         cout << "第" << i << "个数：" << l.data[i] << endl;
  23. }
  24. //存入数据
  25. void InputElem(SqList& l, int e)
  26. {
  27.     int i = 0;
  28.     while (i < MAX)
  29.     {
  30.         if (l.data[i] == 0)
  31.         {
  32.             l.data[i] = e;
  33.             l.length++;
  34.             break;
  35.         }
  36.         i++;
  37.     }
  38. }
  39. //获取顺序表长度
  40. int GetLength(SqList l)
  41. {
  42.     //cout << l.length << endl;
  43.     return l.length;
  44. }
  45. //插入
  46. bool ListInsert(SqList& l, int d, int e)
  47. {
  48.     if (l.length >= MAX)                        //首先要判断表是否已满、插入是否合法
  49.     {
  50.         cout << "插入失败，已达上限" << endl;
  51.         return false;
  52.     }
  53.         
  54.     if (d < 1 || d > l.length + 1)
  55.     {
  56.         cout << "插入失败,无直接前驱" << endl;
  57.         return false;
  58.     }
  59.     for (int j = l.length; j >= d; j--)         //将插入点之后的元素后移
  60.         l.data[j] = l.data[j - 1];
  61.     l.data[d - 1] = e;                          //插入，因为d指的是第几个数，在数组的换算中要减一
  62.     l.length++;
  63.     return true;
  64. }
  65. //删除
  66. bool ListDelete(SqList& l, int d, int &e)
  67. {
  68.     if (d < 1 || d >l.length)                   //判断删除的位置是否合法
  69.         return false;
  70.     e = l.data[d - 1];                          //暂存删除掉的元素
  71.     for (int j = d; j < l.length; j++)          //将被删除元素之后的元素前移
  72.         l.data[j - 1] = l.data[j];              //此处，必须是j = d，j-1被j覆盖，若j = d-1，则下文的覆盖会变为j 被j+1 覆盖，而j+1在最后有可能会超过数组的最大容量
  73.     l.length--;
  74.     return true;
  75. }
  76.  
  77. //查看情况
  78. void CheckList(SqList& l)
  79. {
  80.     PrintList(l);
  81.     cout << "当前长度为" << GetLength(l) << endl;
  82. }
  83.  
  84. //测验
  85. void test01()
  86. {
  87. 	SqList l;
  88. 	InitList(l);
  89.     
  90.     //输入部分数据
  91.     InputElem(l, 1);
  92.     InputElem(l, 2);
  93.     InputElem(l, 3);
  94.     InputElem(l, 4);
  95.     CheckList(l);
  96.  
  97.     //开始插入
  98.     if(ListInsert(l, 3, 6))
  99.         CheckList(l);
  100.  
  101.     //开始删除
  102.     int a = -1;
  103.     if (ListDelete(l, 2, a))
  104.         CheckList(l);
  105. }

(4) Αναζήτηση κατά σειρά bit, αναζήτηση κατά τιμή

Πολύ απλό, δεν χρειάζεται να μπω σε λεπτομέρειες

  1. //判断d的合法性
  2. bool JugdeD(SqList l, int d)
  3. {
  4.     if (d < 1 || d > l.length)
  5.         return false;
  6.     return true;
  7. }
  8.  
  9. //按位序查找
  10. int GetElem(SqList l, int d)
  11. {
  12.     if (JugdeD(l, d))
  13.         return l.data[d - 1];
  14.     return 0;
  15. }
  16.  
  17. //按值查找
  18. int LocateElem(SqList l, int e)
  19. {
  20.     for (int i = 0; i < l.length; i++)
  21.     {
  22.         if (l.data[i] == e)       //数组储存的数据，若是类等复杂的数据类型，则需要对等号进行重载
  23.             return i + 1;
  24.     }
  25.     return 0;
  26. }
  27. //其余代码与上文相同
  28. //其中，JugdeD函数可以替换上文插入与删除中对位序合法性的判别————封装

4. Συνδεδεμένη λίστα

μεαποθήκευση αλυσίδαςγραμμικός πίνακας δεδομένων

(1).Μοναδικά συνδεδεμένη λίστα

i Ορισμός της μεμονωμένης συνδεδεμένης λίστας (οδηγός κόμβος)

  1. //单链表
  2. class LNode
  3. {
  4. public:
  5.     int data;           //数据域，存放数据
  6.     LNode* next;        //指针域，指向下一个节点
  7. };
  8. //用using关键字给类起别名，用LinkList指代的是头结点，代表的是整个链表
  9. using LinkList = LNode*;
  10.  
  11. //初始化
  12. bool InitList(LinkList& L)
  13. {
  14.     L = new LNode();
  15.     if (L == nullptr)   //如果成立，则说明内存不足，分配失败
  16.         return false;
  17.     L->next = nullptr;
  18.     return true;
  19. }

ii. Εισαγωγή και διαγραφή (οδηγός κόμβος)

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

Εισαγωγή (κανονική έκδοση)

  1. //插入
  2. bool ListInsert(LinkList& L, int i, int e)
  3. {
  4.     if (i < 1)                          //判断插入位点是否合法[1]——i值的合法性
  5.     {
  6.         cout << "i为负数" << endl;
  7.         return false;
  8.     }    
  9.     LNode* p = L;                       //让p与L指向相同的位点，L是指示头指针的，所以L是不能改变的
  10.     LNode* s = new LNode();             //新的数据储存
  11.     s->data = e;
  12.     while (p != nullptr && i != 1)      //由头结点起始，开始遍历寻找对应位点
  13.     {
  14.         p = p->next;
  15.         i--;
  16.     }
  17.     if (p == nullptr)                   //判断插入的位点是否合法[2]——i值对应的节点的合法性
  18.     {
  19.         cout << "插入位点超出实际长度" << endl;
  20.         return false;
  21.     }                     
  22.     s->next = p->next;                  //开始接轨，顺序不能乱
  23.     p->next = s;
  24.     return true;
  25. }

Εισαγωγή (συσκευασμένη έκδοση)

  1. //特定节点的后插操作
  2. bool InsertNextNode(LNode* p, int e)
  3. {
  4.     if (p == nullptr)                   
  5.     {
  6.         cout << "插入位点超出实际长度" << endl;
  7.         return false;
  8.     }
  9.     LNode* s = new LNode();
  10.     s->data = e;
  11.     s->next = p->next;
  12.     p->next = s;
  13.     return true;
  14. }
  15. //插入
  16. bool ListInsert(LinkList& L, int i, int e)
  17. {
  18.     if (i < 1)                          //判断插入位点是否合法[1]——i值的合法性
  19.     {
  20.         cout << "i为负数" << endl;
  21.         return false;
  22.     }    
  23.     LNode* p = L;                       //让p与L指向相同的位点，L是指示头指针的，所以L是不能改变的
  24.     while (p != nullptr && i != 1)      //由头结点起始，开始遍历寻找对应位点
  25.     {
  26.         p = p->next;
  27.         i--;
  28.     }
  29.     return InsertNextNode(p, e);        //被封装了的部分
  30. }

 

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

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

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

Ταχυδρομείο