• Day1：数据结构&算法之顺序表

    目录

    一、基本概念以及相关思路、注意点

            1.注意细节：

            2.核心模块：增 删 改 查

                    ①增加（两种方法）：

                    ②删除(伪删除)

                    ③查找：由data获取并返回data的index

    二、C语言实现顺序表

    sqlist.h

     sqlist.c

     Main顺序表.c

    三、C++实现顺序表 

    sqlist.h

    sqlist.cpp

    Main顺序表.cpp 

    一、基本概念以及相关思路、注意点

            1.注意细节：

                    顺序表：取值时，优先判断是否为NULL，增加时要看是否满了(链表就无需担心)

                            null 、curSize、MaxSize

     

            2.核心模块：增 删 改 查

                    ①增加（两种方法）：

                            法一：直接把数据丢到末尾，然后依次swap至index指定位置

                            法二：现平移出位置，然后对空位进行赋值

                    优化：提供push_front()和push_back()两种接口

                    对于有序表：

                                    step1：先将data插入到表的最后面，

                                    step2：再依次和前面进行比较，找到比其小的位置(注意边界问题：不能越界&&记得不管是增还是删除，及时更新curSize!!!)

                    ②删除(向前移动覆盖->伪删除)

                                    ->真正的删除在curSize--

                     优化：提供pop_front()和pop_back()两种接口

                    ③查找：由data获取并返回data的index

    二、C语言实现顺序表

    sqlist.h

    1. #pragma once
    2. #include <stdio.h>
    3. #include <stdlib.h>
    4. #include <assert.h>
    5. #define MAX 10		//最大元素个数
    6. typedef int DataType;
    7. //结构体抽象---> 抽象长相
    8. enum INFO {OK=1,ERROR=-1};
    9. typedef struct 
    10. {
    11. 	DataType* dataMemory;			//一级指针动态内存申请变成一位数组
    12. 	int maxSize;					//最大元素个数-->容量
    13. 	int curSize;					//当前元素个数
    14. }Sqlist,*LPSqlist;
    15.  
    16. LPSqlist	createSqlist(int maxSize);	
    17. //万金油函数-->所有数据结构都可以有的
    18. int			size(LPSqlist sqlist);
    19. int			empty(LPSqlist sqlist);
    20. //增删改查
    21. DataType	getData(LPSqlist sqlist, int index);
    22. int			insertSqlist(LPSqlist sqlist, int index, DataType data);
    23. void		printSqlist(LPSqlist sqlist);
    24. int			deleteSqlist(LPSqlist sqlist, int index);
    25. void		push_front(LPSqlist sqlist,DataType data);    //头部插入
    26. void		pop_front(LPSqlist sqlist);
    27. void		push_back(LPSqlist sqlist, DataType data);
    28. void		pop_back(LPSqlist sqlist);
    29. int			searchSqlist(LPSqlist sqlist, DataType data);
    30. void		insert_sort(LPSqlist sqlist, DataType data);
    31. void		destroySqlist(LPSqlist* sqlist);

     sqlist.c

    1. #include "sqlist.h"
    2. LPSqlist createSqlist(int maxSize)
    3. {
    4.     //创建过程，就是初始化数据
    5.     LPSqlist sqlist = (LPSqlist)malloc(sizeof(Sqlist));
    6.     assert(sqlist);
    7.     sqlist->curSize = 0;
    8.     sqlist->maxSize = maxSize;
    9.     //指针变成一个数组
    10.     sqlist->dataMemory = (DataType*)malloc(sizeof(DataType)*maxSize);
    11.     assert(sqlist->dataMemory);
    12.     return sqlist;
    13. }
    14. int size(LPSqlist sqlist)
    15. {
    16.     if (sqlist == NULL)
    17.         return ERROR;
    18.     return sqlist->curSize;
    19. }
    20. int empty(LPSqlist sqlist)
    21. {
    22.     if (sqlist == NULL)
    23.         return ERROR;
    24.     return sqlist->curSize==0;
    25. }
    26.  
    27. DataType getData(LPSqlist sqlist, int index)
    28. {
    29.     if (sqlist == NULL||sqlist->curSize==0) 
    30.     {
    31.         printf("sqlist is empty,unable to get......\n");
    32.         return ERROR;
    33.     }
    34.     if ( sqlist->curSize < index) 
    35.     {
    36.         //invalid 无效
    37.         printf("index is invalid,unable to get......\n");
    38.         return ERROR;
    39.     }
    40.     //index是第几个元素
    41.     return sqlist->dataMemory[index-1];
    42. }
    43.  
    44. int insertSqlist(LPSqlist sqlist, int index, DataType data)
    45. {
    46.     //数组实现的数据结构：放进去需要考虑满
    47.     if (sqlist == NULL) 
    48.     {
    49.         printf("sqlist is empty,unable to insert......\n");
    50.         return ERROR;
    51.     }
    52.     if (sqlist->curSize == sqlist->maxSize) 
    53.     {
    54.         printf("sqlist is full,unbale to insert......\n");
    55.         return ERROR;
    56.     }
    57.     if (index == 0) 
    58.     {
    59.         sqlist->dataMemory[sqlist->curSize++] = data;
    60.         return OK;
    61.     }
    62.     if (sqlist->curSize < 1 || sqlist->curSize < index) 
    63.     {
    64.         printf("index is invalid,unable to insert......\n");
    65.         return ERROR;
    66.     }
    67. #if 0
    68.     int pos = sqlist->curSize;
    69.     sqlist->dataMemory[pos] = data;     //插在最后面
    70.     while (pos != index) 
    71.     {
    72.         DataType temp = sqlist->dataMemory[pos];
    73.         sqlist->dataMemory[pos] = sqlist->dataMemory[pos - 1];
    74.         sqlist->dataMemory[pos - 1] = temp;
    75.         pos--;
    76.     }
    77.     sqlist->curSize++;
    78. #endif
    79.     for (int k = sqlist->curSize; k >= index; k--) 
    80.     {
    81.         sqlist->dataMemory[k] = sqlist->dataMemory[k - 1];
    82.     }
    83.     sqlist->dataMemory[index - 1] = data;
    84.     sqlist->curSize++;
    85.     return OK;
    86. }
    87.  
    88. void printSqlist(LPSqlist sqlist)
    89. {
    90.     if (sqlist == NULL||sqlist->curSize==0)
    91.     {
    92.         printf("sqlist is empty,unable to print......\n");
    93.         return;
    94.     }
    95.     for (int i = 0; i < sqlist->curSize; i++) 
    96.     {
    97.         printf("%d\t", sqlist->dataMemory[i]);
    98.     }
    99.     printf("\n");
    100. }
    101. int deleteSqlist(LPSqlist sqlist, int index)
    102. {
    103.     if (sqlist == NULL || sqlist->curSize == 0) 
    104.     {
    105.         printf("sqlist is empty,unable to delete......\n");
    106.         return ERROR;
    107.     }
    108.     if (sqlist->curSize < index) 
    109.     {
    110.         printf("index is invalid,unbale to delete......\n");
    111.         return ERROR;
    112.     }
    113.     for (int k = index - 1; k < sqlist->curSize; k++) 
    114.     {
    115.         sqlist->dataMemory[k] = sqlist->dataMemory[k + 1];
    116.     }
    117.     sqlist->curSize--;              //伪删除
    118.     return OK;
    119. }
    120. void push_front(LPSqlist sqlist, DataType data)
    121. {
    122.     insertSqlist(sqlist, 1, data);
    123. }
    124. void pop_front(LPSqlist sqlist)
    125. {
    126.     deleteSqlist(sqlist, 1);
    127. }
    128. void push_back(LPSqlist sqlist, DataType data)
    129. {
    130.     if (sqlist == NULL)
    131.     {
    132.         printf("sqlist is empty,unable to pushback");
    133.         return;
    134.     }
    135.     if (sqlist->curSize == sqlist->maxSize) 
    136.     {
    137.         printf("sqlist is full,unable to pushback");
    138.         return;
    139.     }
    140.     sqlist->dataMemory[sqlist->curSize++] = data;
    141. }
    142. void pop_back(LPSqlist sqlist)
    143. {
    144.     deleteSqlist(sqlist, sqlist->curSize);
    145. }
    146. int searchSqlist(LPSqlist sqlist, DataType data)
    147. {
    148.     if (sqlist == NULL) 
    149.     {
    150.         printf("sqlist is empty,unable to search......\n");
    151.         return ERROR;
    152.     }
    153.     for (int i = 0; i < sqlist->curSize; i++) 
    154.     {
    155.         if (sqlist->dataMemory[i] == data) 
    156.         {
    157.             return i;
    158.         }
    159.     }
    160.     return ERROR;
    161. }
    162. void insert_sort(LPSqlist sqlist, DataType data)
    163. {
    164.     if (sqlist == NULL) 
    165.     {
    166.         printf("sqlist is empty,unable to insert......\n");
    167.         return;
    168.     }
    169.     if (sqlist->curSize == sqlist->maxSize) 
    170.     {
    171.         printf("sqlist is full,unable to insert......\n");
    172.         return;
    173.     }
    174.     if (sqlist->curSize == 0)
    175.     {
    176.         sqlist->dataMemory[sqlist->curSize++] = data;
    177.     }
    178.     sqlist->dataMemory[sqlist->curSize] = data;
    179.     int pos = sqlist->curSize;
    180.     for (int k = sqlist->curSize;k>0; k--)
    181.     {
    182.         if (sqlist->dataMemory[k] < sqlist->dataMemory[k - 1])
    183.         {
    184.             DataType temp = sqlist->dataMemory[k];
    185.             sqlist->dataMemory[k] = sqlist->dataMemory[k - 1];
    186.             sqlist->dataMemory[k - 1] = temp;
    187.         }
    188.         else 
    189.         {
    190.             break;
    191.         }
    192.     }
    193.     sqlist->curSize++;
    194. }
    195.  
    196. void destroySqlist(LPSqlist* sqlist)
    197. {
    198.     if (*sqlist == NULL) 
    199.     {
    200.         printf("sqlist is empty, unable to destory......\n");
    201.         return;
    202.     }
    203.     free((*sqlist)->dataMemory);
    204.     free(*sqlist);
    205.     *sqlist = NULL;
    206. }

     Main顺序表.c

    1. #include "sqlist.h"
    2. int main() 
    3. {
    4. 	LPSqlist sqlist = createSqlist(MAX);
    5. 	printf("test insert:\n");
    6. 	insertSqlist(sqlist, 0, 0);  //0
    7. 	insertSqlist(sqlist, 1, 1);  //1 0
    8. 	insertSqlist(sqlist, 1, 2);  //2 1 0
    9. 	insertSqlist(sqlist, 1, 3);  //3 2 1 0
    10. 	insertSqlist(sqlist, 4, 444);
    11. 	printSqlist(sqlist);
    12. 	printf("test delete:\n");
    13. 	deleteSqlist(sqlist, 4);
    14. 	printSqlist(sqlist);
    15. 	printf("test push and pop:\n");
    16. 	push_front(sqlist, 666);
    17. 	push_back(sqlist, 999);
    18. 	printSqlist(sqlist);
    19. 	pop_front(sqlist);
    20. 	pop_back(sqlist);
    21. 	printSqlist(sqlist);
    22. 	int pos = searchSqlist(sqlist, 3);
    23. 	printf("pos:%d\n", pos);	
    24. 	destroySqlist(&sqlist);
    25. 	LPSqlist sortSqlist = createSqlist(MAX);
    26. 	insert_sort(sortSqlist, 1);
    27. 	insert_sort(sortSqlist, 100);
    28. 	insert_sort(sortSqlist, 77);
    29. 	insert_sort(sortSqlist, -1);
    30. 	printSqlist(sortSqlist);
    31. 	destroySqlist(&sortSqlist);
    32. 	return 0;
    33. }

     输出：

    test insert:
    3       2       1       444     0
    test delete:
    3       2       1       0
    test push and pop:
    666     3       2       1       0       999
    3       2       1       0
    pos:0
    -1      1       1       77      100

    三、C++实现顺序表 

    sqlist.h

    1. #pragma once
    2. #pragma once
    3. #include <iostream>
    4. using namespace std;
    5. #define MAX 10		//最大元素个数
    6. typedef int DataType;
    7. //结构体抽象---> 抽象长相
    8. enum INFO { OK = 1, ERROR = -1 };
    9. class Sqlist 
    10. {
    11. public:
    12. 	Sqlist(int MaxSize);
    13. 	int			size() const;
    14. 	int			empty()const;
    15. 	DataType	getData(int index);
    16. 	int			insertSqlist(int index, DataType data);
    17. 	void		printSqlist();
    18. 	int			deleteSqlist( int index);
    19. 	void		push_front( DataType data);    //头部插入
    20. 	void		pop_front();
    21. 	void		push_back(DataType data);
    22. 	void		pop_back();
    23. 	int			searchSqlist( DataType data);
    24. 	void		insert_sort(DataType data);
    25. 	void		destroySqlist();
    26. protected:
    27. 	DataType* dataMemory;			
    28. 	int maxSize;					
    29. 	int curSize;				
    30. };

    sqlist.cpp

    1. #include "sqlist.h"
    2.  
    3. Sqlist::Sqlist(int MaxSize)
    4. {
    5.     //创建过程，就是初始化数据
    6.     curSize = 0;
    7.     maxSize = MaxSize;
    8.     //指针变成一个数组
    9.     dataMemory =new DataType[maxSize];
    10. }
    11.  
    12. int Sqlist::size() const
    13. {
    14.     if (dataMemory == NULL)
    15.         return ERROR;
    16.     return curSize;
    17. }
    18.  
    19. int Sqlist::empty() const
    20. {
    21.     if (dataMemory == NULL)
    22.         return ERROR;
    23.     return curSize==0;
    24. }
    25.  
    26. DataType Sqlist::getData(int index)
    27. {
    28.     if (curSize == 0)
    29.     {
    30.         cout<<"sqlist is empty,unable to get......"<<endl;
    31.         return ERROR;
    32.     }
    33.     if (curSize < index)
    34.     {
    35.         //invalid 无效
    36.         cout << "index is invalid,unable to get......" << endl;;
    37.         return ERROR;
    38.     }
    39.     //index是第几个元素
    40.     return dataMemory[index - 1];
    41. }
    42.  
    43. int Sqlist::insertSqlist(int index, DataType data)
    44. {
    45.     //数组实现的数据结构：放进去需要考虑满
    46.     if (curSize == maxSize)
    47.     {
    48.         printf("sqlist is full,unbale to insert......\n");
    49.         return ERROR;
    50.     }
    51.     if (index == 0)
    52.     {
    53.         dataMemory[curSize++] = data;
    54.         return OK;
    55.     }
    56.     if (curSize < 1 || curSize < index)
    57.     {
    58.         printf("index is invalid,unable to insert......\n");
    59.         return ERROR;
    60.     }
    61. #if 0
    62.     int pos = sqlist->curSize;
    63.     dataMemory[pos] = data;     //插在最后面
    64.     while (pos != index)
    65.     {
    66.         DataType temp = dataMemory[pos];
    67.         dataMemory[pos] = dataMemory[pos - 1];
    68.         dataMemory[pos - 1] = temp;
    69.         pos--;
    70.     }
    71.     curSize++;
    72. #endif
    73.     for (int k = curSize; k >= index; k--)
    74.     {
    75.         dataMemory[k] = dataMemory[k - 1];
    76.     }
    77.     dataMemory[index - 1] = data;
    78.     curSize++;
    79.     return OK;
    80. }
    81.  
    82. void Sqlist::printSqlist()
    83. {
    84.     if (curSize == 0)
    85.     {
    86.         cout << "sqlist is empty,unable to print......\n" << endl;
    87.         return;
    88.     }
    89.     for (int i = 0; i < curSize; i++)
    90.     {
    91.         printf("%d\t", dataMemory[i]);
    92.     }
    93.     printf("\n");
    94. }
    95.  
    96. int Sqlist::deleteSqlist(int index)
    97. {
    98.     if (curSize == 0)
    99.     {
    100.         cout<<"sqlist is empty,unable to delete......\n";
    101.         return ERROR;
    102.     }
    103.     if (curSize < index)
    104.     {
    105.         cout<<"index is invalid,unbale to delete......\n";
    106.         return ERROR;
    107.     }
    108.     for (int k = index - 1; k < curSize; k++)
    109.     {
    110.         dataMemory[k] = dataMemory[k + 1];
    111.     }
    112.     curSize--;              //伪删除
    113.     return OK;
    114. }
    115.  
    116. void Sqlist::push_front(DataType data)
    117. {
    118.     insertSqlist(1, data);
    119. }
    120.  
    121. void Sqlist::pop_front()
    122. {
    123.     deleteSqlist(1);
    124. }
    125.  
    126. void Sqlist::push_back(DataType data)
    127. {
    128.     if (curSize == maxSize)
    129.     {
    130.         printf("sqlist is full,unable to pushback");
    131.         return;
    132.     }
    133.     dataMemory[curSize++] = data;
    134. }
    135.  
    136. void Sqlist::pop_back()
    137. {
    138.     deleteSqlist(curSize);
    139. }
    140.  
    141. int Sqlist::searchSqlist(DataType data)
    142. {
    143.     for (int i = 0; i < curSize; i++)
    144.     {
    145.         if (dataMemory[i] == data)
    146.         {
    147.             return i;
    148.         }
    149.     }
    150.     return ERROR;
    151. }
    152.  
    153. void Sqlist::insert_sort(DataType data)
    154. {
    155.     if (curSize ==maxSize)
    156.     {
    157.         cout<<"sqlist is full,unable to insert......\n";
    158.         return;
    159.     }
    160.     if (curSize == 0)
    161.     {
    162.        dataMemory[curSize++] = data;
    163.     }
    164.     dataMemory[curSize] = data;
    165.     int pos = curSize;
    166.     for (int k = curSize; k > 0; k--)
    167.     {
    168.         if (dataMemory[k] < dataMemory[k - 1])
    169.         {
    170.             DataType temp = dataMemory[k];
    171.             dataMemory[k] = dataMemory[k - 1];
    172.             dataMemory[k - 1] = temp;
    173.         }
    174.         else
    175.         {
    176.             break;
    177.         }
    178.     }
    179.     curSize++;
    180. }
    181.  
    182. void Sqlist::destroySqlist()
    183. {
    184.     delete [] dataMemory;
    185.     dataMemory = nullptr;
    186. }

    Main顺序表.cpp 

    1. #include "sqlist.h"
    2. int main()
    3. {
    4. 	Sqlist *pSqlist=new Sqlist(MAX);
    5. 	printf("test insert:\n");
    6. 	pSqlist->insertSqlist( 0, 0);  //0
    7. 	pSqlist->insertSqlist( 1, 1);  //1 0
    8. 	pSqlist->insertSqlist( 1, 2);  //2 1 0
    9. 	pSqlist->insertSqlist( 1, 3);  //3 2 1 0
    10. 	pSqlist->insertSqlist( 4, 444);
    11. 	pSqlist->printSqlist();
    12. 	printf("test delete:\n");
    13. 	pSqlist->deleteSqlist( 4);
    14. 	pSqlist->printSqlist();
    15. 	printf("test push and pop:\n");
    16. 	pSqlist->push_front(666);
    17. 	pSqlist->push_back(999);
    18. 	pSqlist->printSqlist();
    19. 	pSqlist->pop_front();
    20. 	pSqlist->pop_back();
    21. 	pSqlist->printSqlist();
    22. 	int pos = pSqlist->searchSqlist(3);
    23. 	printf("pos:%d\n", pos);
    24. 	pSqlist->destroySqlist();
    25. 	delete pSqlist;
    26. 	pSqlist = nullptr;
    27. 	Sqlist sortSqlist(10);
    28. 	sortSqlist.insert_sort(1);
    29. 	sortSqlist.insert_sort(100);
    30. 	sortSqlist.insert_sort(77);
    31. 	sortSqlist.insert_sort(-1);
    32. 	sortSqlist.printSqlist();
    33. 	sortSqlist.destroySqlist();
    34. 	return 0;
    35. }

  • 相关阅读:
    巨好看的登录注册界面源码
    K8S精进之路-控制器Deployment-(1)
    Vue中的$attrs和inheritAttrs
    Intel汇编-Linux系统调用
    网络安全（黑客）—自学
    算法刷题2(C++)链表遍历算法
    java计算机毕业设计医院远程诊断系统源代码+系统+数据库+lw文档
    【Nano Framework ESP32 篇】刷入 nanoCLR 固件以及相关问题
    案例4-1.4 堆中的路径 + 基础实验4-2.5 关于堆的判断
    设计两个异常类，用于检查身高
  • 原文地址：https://blog.csdn.net/zjjaibc/article/details/125630084