基于C/C++语言数据结构之线性表（一）

青旅半醒 2022-07-16 09:56 159阅读 0赞

### 数据结构学习笔记： ###

数据结构的重要性：数据结构我感觉很重要，不仅仅是考试很重要，而且在以后程序员事业上都是尤为重要的，知乎上有网友评价数据结构是最重要的编程基本能力，没有之一。我感觉这个说法很对，并且大家都知道，数据结构与算法这种说法常常被大家使用，就是因为数据结构是算法的基本前提，不懂数据结构，算法肯定学的很毛糙，根本就没有真正的高效可言，那也自然称不上是算法啦。所以大家要重视数据结构，虽然刚开始可能会不理解，从不理解到理解，才是真正的学习过程，如果你看一个会一个，你就根本就不用学习，因为已经是天才啦，这正如我们锻炼，锻炼的时候真正起作用的不是你轻轻松松完成几个俯卧撑，跑了几圈，而是你最累，最不想继续运动的阶段。总之学习也是欲速则不达吧，坚持学习，一定会从不理解到掌握。

### 线性表： ###

线性表安装存储结构分为：顺序表和链式表

顺序表在计算机中以数组的形式保存是指地址连续的存储单元一次存储数据元素的线性结构

线性表中所有元素的数据类型都是相同的

线性表中的元素具有逻辑上的顺序性。

受存储空间限制，线性表只能有限存储。

线性表中所有元素的数据类型都是相同的。

在顺序表中，元素都是一个挨一个存储，元素都集中在一段区间内，相对存储密度大

顺序表在访问元素时，可以通过表头元素的地址和元素的编号（下标）在 \\mathcal\{O\}(1)O(1) 时间内访问到它。

### 顺序表的创建： ###

#include <iostream>
    #include <cstring>
     
    class Vector {
    private:
       int size,length;
       int *data;
       
    public:
       Vector(int input_size) {
           size=input_size;
           length=0;
           data=new int [size];
          
        }
       ~Vector() {
           delete[] data;
        }
    };
    int main() {
       Vector a(100);
       return 0;
    }

### c++中delete data和delete\[ \] data的区别是什么？ ###

主要差别是  是否调用析构函数  
  
delete data\[\] 会自动调用data数组每个元素的析构函数  
delete data则不会

delete data是清除data的内存单元，而delete\[\]data的内存单元。  
data 为一个指针，而delete\[\] date中的data为一个指针数组的首指针

### using std::cout;using std::endl; 用法？说明 ###

使用std命名空间中的cout和endl。如果不这样的话，每次使用cout和endl都要加上std::  
例如：  
std::cout<< "Hello World"<<std::endl;

用了名字空间 std 你也可以在入口函数前面 写 using namespace std;来代替。而在后面 就只要直接用 cout 和endl；

### C语言中system("pause")是什么作用和意思？ ###

system就是调用从程序中调用系统命令（和shell命令）。    
  system("pause")就是从程序里调用“pause”命令；    
  而“pause”这个系统命令的功能很简单，就是在命令行上输出一行类似于

“Press  any   key   to  exit”

请按任意键继续. . .

的字，等待用户按一个键，然后返回。

插入：

![20161015193259381][]

删除：

![20161015193313694][]

### 顺序表构造、插入、扩容、查找、删除、遍历： ###

#include <iostream>
    #include <cstring>
    using std::cout;
    using std::endl;
    class Vector {
           private:
                  intsize, length;
                  int* data;
           public:
                  Vector(intinput_size) {//构造函数
                         cout<<"调用了构造函数"<<endl;
                         size= input_size;
                         length= 0;
                         data= new int[size];
                  }
                  ~Vector(){//析构函数
                         cout<<"调用了析构函数"<<endl;
                         delete[]data;
                  }
                  boolinsert(int loc, int value) {//插入元素
                         cout<<"调用了插入元素函数"<<endl;
                         if(loc < 0 || loc > length) {
                                returnfalse;
                         }
                         if(length >= size) {
                                returnfalse;
                         }
                         for(int i = length; i > loc; --i) {
                                data[i]= data[i - 1];
                         }
                         data[loc]= value;
                         length++;
                         returntrue;
                  }
                  intsearch(int value) {//查找元素
                         cout<<"调用了查找元素函数"<<endl;
                         for(int i = 0; i < length; ++i) {
                                if(data[i] == value) {
                                       returni;
                                }
                         }
                         return-1;
                  }
                  boolremove(int index) {//删除元素
                         cout<<"调用了删除元素函数"<<endl;
                         if(index < 0 || index >= length) {
                                returnfalse;
                         }
                         for(int i = index + 1; i < length; ++i) {
                                data[i- 1] = data[i];
                         }
                         length= length - 1;
                         returntrue;
                  }
                  voidprint() {//打印元素
                         cout<<"调用了打印元素函数"<<endl;
                         for(inti=0; i<length; i++) {
                                if(i>0){
                                       cout<<"";
                                }
                                cout<<data[i];
     
                         }
                         cout<<endl;
                  }
                  //请在下面实现扩容方法expand
                  voidexpand() {//扩容函数
                         cout<<"调用了扩容函数"<<endl;
                         int* old_data=data;
                         size=size*2;
                         data=newint[size];
                         for(inti=0; i<length; ++i) {
                                data[i]=old_data[i];
                         }
                         delete[]old_data;
                  }
    };
    int main() {
           Vectora(2);
           cout<< a.insert(0, 1) << endl;
           cout<< a.insert(0, 2) << endl;
           a.print();
           cout<< a.remove(1) << endl;
           a.print();
           cout<< a.search(0) << endl;
           cout<< a.search(1) << endl;
           a.expand();
     
           return0;
           system("pause");//如果在返回值之前执行此句，则不能正常执行析构函数，释放空间
    }

### 例题：循环左移或右移 ###

要求：在前面的课程中，我们学习了顺序表的构造、插入、扩容、查找、删除、遍历这 6 种操作。然而并不满足于实现这些基本的操作，于是蒜头君想到了一种新的操作：循环左移。

对于顺序表 L=(a\_0,a\_1, ..., a\_\{n-1\})L=(a0,a1,...,an−1)，循环左移 kk 位意味着将顺序表变为 L^k=(a\_k, a\_\{k+1\}, ..., a\_\{n-1\}, a\_0, a\_1, ...,a\_\{k-1\})Lk=(ak,ak+1,...,an−1,a0,a1,...,ak−1)。

比如：长度为 88 的顺序表 (1, 2, 3, 4, 5, 6, 7,8)(1,2,3,4,5,6,7,8)，循环左移 33 位后的结果为 (4, 5, 6, 7, 8, 1, 2, 3)(4,5,6,7,8,1,2,3)。

输入格式

第一行输入两个整数 n(1\\leq n \\leq 100)n(1≤n≤100) 和 k(0 \\leq k \\leq n)k(0≤k≤n)，分别表示顺序表的元素个数和循环左移的位移量。

第二行一共 nn 个整数 a\_i(0 \\leq a\_i \\leq10000)ai(0≤ai≤10000)，表示顺序表中元素的值。

输出格式

输出只有一行，输出 nn 个整数，顺序输出循环左移后顺序表中每个元素的值，每个元素之间用一个空格分隔。行末不要有多余空格。

样例输入

8 3

1 2 3 4 5 6 7 8

样例输出

4 5 6 7 8 1 2 3

代码：

#include<iostream>
    using std::cout;
    using std::cin;
    using std::endl;
    class ver{
       private:
       int length,size;
       int * data;
       public:
       ver(int input){
           size=input;
           length=0;
           data=new int[size];
        }
       ~ver(){
           delete[] data;       
        }
       void expand()
        {
           int * old_data=data;
           size=size*2;
           data=new int[size];
           for(int i=0;i<length;i++)
           {
               data[i]=old_data[i];
           }
        }
       int insert(int n)
        {
           for(int i=0;i<n;i++)
           {
               cin>>data[i];
           }
        }
       void print(int n)
        {
           
           for(int i=0;i<n;i++)
           {
               if(i>0){
                    cout<<" ";
               }
               cout<<data[i];
           }
        }
       void RigntMove(int n,int k)
        {
           int temp;
           for(int j=0;j<k;j++)
           {
               temp=data[n-1];
            for(int i=n-1;i>=1;i--)
           {
               data[i]=data[i-1];
           }
           data[0]=temp;
          }
        }
           void LeftMove(int n,int k)
        {
           int temp;
           for(int j=0;j<k;j++)
           {
               temp=data[0];
           for(int i=1;i<n;i++)
           {
               data[i-1]=data[i];
           }
           data[n-1]=temp;
          }
           
        }
       
    };
    int main()
    {
       int n,k;
       cin>>n;
       cin>>k;
       ver a(n);
       a.insert(n);
       a.LeftMove(n,k);
       a.print(n);
       return 0;
    }

版权说明

发表日期：2016年10月14日   
本文链接：[http://blog.csdn.net/qq\_26816591/article/details/52814488][http_blog.csdn.net_qq_26816591_article_details_52814488]

来源：CSDN   
更多内容：[关于][Link 1]visual studio 2010 直接复制粘贴会出现乱码的解决方法

编译运行环境：dev-c++

[20161015193259381]: /images/20220716/39a322836c0641dda1522bf7ce6238d4.png
[20161015193313694]: /images/20220716/12aac674cedd432e87ee916e68dad5d8.png
[http_blog.csdn.net_qq_26816591_article_details_52814488]: http://blog.csdn.net/qq_26816591/article/details/52814488
[Link 1]: http://blog.csdn.net/qq_26816591/article/details/52548927