今晚最快开奖现场直播 > 关于计算机 > 数据结构，数据结构之线性表

数据结构，数据结构之线性表

日期:2019-11-15编辑作者：关于计算机

C++数据结构 顺序表的达成(模板类的完毕)

接收模板类实现顺序表的操作

兑现的功效:

1.尾插，2.头插，3.显得，4.尾删，5.头删，6.按职分，7.插按值插，8.按职责删，9.按值删，10.按值查，11.求表长，12.排除数据，13.摧毁该顺序表，14.反转，15.排序(冒泡排序，快速排序)。

头文件源代码:

 

#pragma once        // 防止重复编译

#include
using namespace std;

template
class SeqList
{
public:
 SeqList(size_t sz=INIT_SIZE);
public:
 bool isfull()const
 {return size>=capacity;}
 bool isempty()const
 {return size==0;}
public:
 void push_back(const Type &x);   //尾插
 void push_front(const Type &x);  //头插
 void show_list();                //显示
 void pop_back();                 //尾删
 void pop_front();                //头删
 void insert_pos(int pos,const Type &x);//按位置插
 void insert_val(const Type &x);        //按值插
 void delete_pos(int pos);              //按位置删
 void delete_val(const Type &x);        //按值删
 int  find(const Type &key);            //按值查
 int  length()const;                    //求表长
 void clear();                          //清除数据
 void destroy();                        //摧毁该顺序表
 void reserv();                         //反转
 void sort(/*int low,int high*/);       //排序
private:
 enum{INIT_SIZE=8};
 Type *base;
 size_t capacity;
 size_t size;
};


template
SeqList::SeqList(size_t sz)
{
 capacity = sz > INIT_SIZE ? sz : INIT_SIZE;
 base = new Type[capacity];
 size = 0;
}

template
void SeqList::push_back(const Type &x)
{
 if(isfull())
 {
  cout<<"顺序表已满,不能插入!"<
void SeqList::push_front(const Type &x)
{
 if(isfull())
 {
  cout<<"顺序表已满,不能插入!"<0; --i)
 {
  base[i] = base[i-1];
 }
 base[0] = x;
 size++;
}

template
void SeqList::show_list()
{
 for(int i=0; i%3Cbase%5Bi%5D%3C%3C%22%20%22%3B%0A%09%7D%0A%09cout%3C%3Cendl%3B%0A%7D%0A%0Atemplate%3Cclass%20Type%3E
void SeqList::pop_back()
{
    if(isempty())
    {
        cout<<"顺序表已满"<
void SeqList::pop_front()
{
    int i;
    for(i = 0;i
void SeqList::insert_pos(int pos,const Type &x)
{
 if(pos<0 || pos>size)
 {
  cout<<"要插入的位置非法!"<pos; --i)
 {
  base[i] = base[i-1];
 }
 base[pos] = x;
 size++;
}

template
void SeqList::insert_val(const Type &x)
{
    int pos;
    pos = find(x);
    insert_pos(pos,x);
}

template
void SeqList::delete_pos(int pos)
{
    int i;
    for(i = pos;i
void SeqList::delete_val(const Type &x)
{
 int pos = find(x);
 if(pos == -1)
 {
  return;
 }

 for(int i=pos; i
int SeqList::find(const Type &key)
{
 for(int i=0; i
int SeqList::length()const
{
    cout<<"表长是:"<<
void SeqList::clear()
{
    while(size)
    {
        base[size--] = NULL;
    }
}

template
void SeqList::destroy()
{
    int i;
    delete base;
    base = NULL;
    capacity = 0;
    size = 0;
}

template
void SeqList::reserv()
{
    int i = 0;
    int m = size - 1;
    for(;i<=((size-1)/2);++i)
        {
            int tmp = base[i];
            base[i] = base[m];
            base[m] = tmp;
            m--;
        }
}

template
void SeqList::sort()//排序
{


 for (int i=0;i<=size;i++)
  for (int j=i+1;j<=size-1;j++)
  {
   if(base[i]>base[j])
   {
    int tmp = base[j];
    base[j]=base[i];
    base[i]=tmp;
   }
  }
}
/*
template     ///快速排序
void SeqList::sort(int low,int high)
{
    if(low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = base[first];             //用字表的第一个记录作为枢轴
    while(first < last)
    {
        while(first < last && base[last] >= key)
        {
            last--;
        }
        base[first] = base[last];//将比第一个小的移到低端
        while(first < last && base[first] <= key)
        {
            first++;
        }
            base[last] = base[first];//将比第一个大的移到高端
    }
            base[first] = key;//枢轴记录到位
            sort(low, first-1);
            sort(first+1, high);
}
*/
<

 

 

主函数:

 

#include"SeqList.h"

int main()
{
 SeqList mylist;
 int select = 1;
 int Item;
 int pos;
 while(select)
 {
  cout<<"**************************************"<";
  cin>>select;
  switch(select)
  {
  case 1:
   cout<<"请输入要插入的值(-1结束):>";
   while(cin>>Item, Item!=-1)
   {
    mylist.push_back(Item);
   }
   break;
  case 2:
   cout<<"请输入要插入的值(-1结束):>";
   while(cin>>Item, Item!=-1)
   {
    mylist.push_front(Item);
   }
   break;
  case 3:
   mylist.show_list();
   break;
        case 4:
            mylist.pop_back();
            break;
        case 5:
            mylist.pop_front();
            break;
  case 6:
   cout<<"请输入要插入的位置:>";
   cin>>pos;
   cout<<"请输入要插入的值:>";
   cin>>Item;
   mylist.insert_pos(pos,Item);
   break;
        case 7:
            cout<<"请输入要插入的值:>";
            cin>>Item;
            mylist.insert_val(Item);
        case 8:
            cout<<"请输入要删除的位置:>";
            cin>>pos;
            mylist.delete_pos(pos);
            break;
  case 9:
   cout<<"请输入要删除的值:>";
   cin>>Item;
   mylist.delete_val(Item);
   break;
  case 10:
   cout<<"请输入要查找的值:>";
   cin>>Item;
   int pos;
   pos = mylist.find(Item);
   break;
        case 11:
            mylist.length();
            break;
        case 12:
            mylist.clear();
            break;
        case 13:
            mylist.destroy();
            break;
        case 14:
            mylist.reserv();
            break;
        case 15:
            //int a;
           //a = mylist.length();
            mylist.sort(/*0,a-1*/);
            break;
  default:
   break;
  }
 }
}

 

顺序表的贯彻(模板类的达成) 利用模板类实现顺序表的操作 达成的效果: 1.尾插，2.头插，3.来得，4.尾删，5.头删，6.按岗位，...

顺序表

   1.顺序表定义：线性表的各类表示指的是用后生可畏组地方一而再的存款和储蓄单元依次存款和储蓄线性表的数码成分。要是线性表的各样元素需占用L个

存款和储蓄单元，并以所占的率先个单元的存放地方作为数据成分的寄放地方。则线性表中第i+1个数据成分的囤积地方LOC(ai+1)和第i个数据

要素的储存地方LOC(ai)之间满意下列关系：LOC(ai+1)=LOC(ai)+L，平日的话，线性表的第i个数据成分ai的囤积地点为：LOC(ai)=LOC(a1)

+(i-1)*L，式中LOC(ai)是线性表的率先个数据成分a1的存放地方，日常称作线性表的开局地方或营地址。

 2.顺序表的数据结构

typedef struct SeqList
{
    ElemType *base; 
    size_t    capacity;
    size_t    len;
}SeqList;

 

   3. 在依次表中有以下操作： 

void InitSeqList(SeqList *list);
void ShowSeqList(SeqList *list);
bool push_back(SeqList *list, ElemType x);
bool push_front(SeqList *list, ElemType x);
size_t Length(SeqList *list);
bool insert_pos(SeqList *list, int pos, ElemType x);
bool pop_back(SeqList *list);
bool pop_front(SeqList *list);
bool insert_val(SeqList *list, ElemType x);
bool delete_pos(SeqList *list, int pos);
bool delete_val(SeqList *list, ElemType key);
int  find_key(SeqList *list, ElemType key);
void reverse_list(SeqList *list);
void sort_list(SeqList *list);
void clear_list(SeqList *list);
void destroy_list(SeqList *list);

    以上操作包含(1)起始化三个相继表来组织一个空的各种表.（2卡塔尔体现顺序表.（3卡塔 尔（英语：State of Qatar）尾插法.（3卡塔 尔（英语：State of Qatar）头插法.（4卡塔尔国求顺序表的长度.

（5卡塔 尔（阿拉伯语：قطر‎按岗位将一个数量成分插入顺序表中.（6卡塔 尔（英语：State of Qatar）尾巴部分删除元素.（7卡塔 尔（阿拉伯语：قطر‎尾部删除成分.（8卡塔 尔（阿拉伯语：قطر‎按值的朗朗上口插入顺序表中.（9卡塔 尔（阿拉伯语：قطر‎按任务删

 除顺序表中的成分.（10卡塔 尔（阿拉伯语：قطر‎按值删除顺序表中的元素.（11卡塔 尔（英语：State of Qatar）按值查找顺序表中的成分.（12卡塔 尔（阿拉伯语：قطر‎将各种表逆置.（13卡塔尔将顺序表的因素

 实行排序.（14卡塔尔清除顺序表.（15卡塔 尔（阿拉伯语：قطر‎销毁顺序表.

 4.底下将上边所注明的议程在SeqList.h的头文件中展开落到实处如下：

#ifndef _SEQLIST_H
#define _SEQLIST_H

  #include<iostream>
  #include<assert.h>
  using namespace std;

  #define ElemType int

  #define SEQLIST_DEFAULT_SIZE 8

  #define SEQLIST_INC_SIZE 3

typedef struct SeqList
{
    ElemType *base;
    size_t    capacity;
    size_t    len;
}SeqList;

void InitSeqList(SeqList *list);
void ShowSeqList(SeqList *list);
bool push_back(SeqList *list, ElemType x);
bool push_front(SeqList *list, ElemType x);
size_t Length(SeqList *list);
bool insert_pos(SeqList *list, int pos, ElemType x);
bool pop_back(SeqList *list);
bool pop_front(SeqList *list);
bool insert_val(SeqList *list, ElemType x);
bool delete_pos(SeqList *list, int pos);
bool delete_val(SeqList *list, ElemType key);
int  find_key(SeqList *list, ElemType key);
void reverse_list(SeqList *list);
void sort_list(SeqList *list);
void clear_list(SeqList *list);
void destroy_list(SeqList *list);

bool IsFull(SeqList *list)
{
    return list->len >= list->capacity;
}
bool IsEmpty(SeqList *list)
{
    return list->len == 0;
}
void Swap(ElemType &a, ElemType &b)
{
    ElemType tmp = a;
    a = b;
    b = tmp;
}

//异常安全 
bool Inc(SeqList *list)
{
    size_t new_capacity = list->capacity+SEQLIST_INC_SIZE;
    ElemType *new_base = (ElemType*)realloc(list->base, sizeof(ElemType)*new_capacity);
    if(new_base == NULL)
        return false;
    list->capacity = new_capacity;
    list->base = new_base;
    return true;
}

void InitSeqList(SeqList *list)
{
    list->base = (ElemType*)malloc(sizeof(ElemType)*SEQLIST_DEFAULT_SIZE);
    assert(list->base != NULL);
    list->capacity = SEQLIST_DEFAULT_SIZE;
    list->len = 0;
}

void ShowSeqList(SeqList *list)
{
    for(int i=0; i<list->len; ++i)
    {
        cout<<list->base[i]<<" ";
    }
    cout<<endl;
}

bool push_back(SeqList *list, ElemType x)
{
    if(list->len>=list->capacity && !Inc(list))
    //if(!Inc(list) && list->len>=list->capacity)
    {
        cout<<"空间已满，"<<x<<"不能尾部插入."<<endl;
        return false;
    }
    list->base[list->len++] = x;
    //list->len++;
    return true;
}

bool push_front(SeqList *list, ElemType x)
{
    if(list->len >= list->capacity)
    {
        cout<<"空间已满，"<<x<<"不能头部插入."<<endl;
        return false;
    }
    for(int i=list->len; i>0; --i)
    {
        list->base[i] = list->base[i-1];
    }
    list->base[0] = x;
    list->len++;
    return true;
}

size_t Length(SeqList *list)
{
    return list->len;
}

bool insert_pos(SeqList *list, int pos, ElemType x)
{
    if(list->len >= list->capacity)
    {
        cout<<"空间已满，"<<x<<"不能插入."<<endl;
        return false;
    }
    if(pos<0 || pos>list->len)
    {
        cout<<"插入的位置非法."<<endl;
        return false;
    }
    for(int i=list->len; i>pos; --i)
    {
        list->base[i] = list->base[i-1];
    }
    list->base[pos] = x;
    list->len++;
    return true;
}

bool pop_back(SeqList *list)
{
    if(list->len == 0)
    {
        cout<<"顺序表已空，不能删除."<<endl;
        return false;
    }
    list->len--;
    return true;
}

bool pop_front(SeqList *list)
{
    if(list->len == 0)
    {
        cout<<"顺序表已空，不能删除."<<endl;
        return false;
    }
    for(int i=0; i<list->len-1; ++i)
    {
        list->base[i] = list->base[i+1];
    }
    list->len--;
    return true;
}
bool insert_val(SeqList *list, ElemType x)
{
    if(list->len >= list->capacity)
    {
        cout<<"空间已满，"<<x<<"不能插入."<<endl;
        return false;
    }
    for(int i=0; i<list->len; ++i)
    {
        if(x < list->base[i])
        {
            for(int j=list->len; j>i; --j)
            {
                list->base[j] = list->base[j-1];
            }
            break;
        }
    }
    list->base[i] = x;
    list->len++;
    return true;
}

bool delete_pos(SeqList *list, int pos)
{
    if(list->len == 0)
    {
        cout<<"顺序表已空，不能删除."<<endl;
        return false;
    }
    if(pos<0 || pos>=list->len)
    {
        cout<<"删除的位置非法,不能删除元素."<<endl;
        return false;
    }
    for(int i=pos; i<list->len-1; ++i)
    {
        list->base[i] = list->base[i+1];
    }
    list->len--;
    return true;
}

bool delete_val(SeqList *list, ElemType key)
{
    if(list->len == 0)
    {
        cout<<"顺序表已空，不能删除."<<endl;
        return false;
    }
    int del_pos = find_key(list, key);
    if(del_pos == -1)
    {
        cout<<"要删除的数据:"<<key<<"不存在."<<endl;
        return false;
    }
    return delete_pos(list, del_pos);
}

int  find_key(SeqList *list, ElemType key)
{
    for(int i=0; i<list->len; ++i)
    {
        if(key == list->base[i])
            return i;
    }
    return -1;
}

void reverse_list(SeqList *list)
{
    if(list->len > 1)
    {
        int low = 0;
        int high = list->len-1;
        while(low < high)
        {
            Swap(list->base[low], list->base[high]);
            low++;
            high--;
        }
    }
}

void sort_list(SeqList *list)
{
    if(list->len > 1)
    {
        for(int i=0; i<list->len-1; ++i)
        {
            for(int j=0; j<list->len-i-1; ++j)
            {
                if(list->base[j] > list->base[j+1])
                {
                    Swap(list->base[j], list->base[j+1]);
                }
            }
        }
    }
}

void clear_list(SeqList *list)
{
    list->len = 0;
}

void destroy_list(SeqList *list)
{
    free(list->base);
    list->base = NULL;    // 预防野指针
    list->capacity = list->len = 0;
}

#endif

 5.将地点达成的格局在主函数中调用如下：

#include <iostream>
#incldue "SeqList.h"
using namespace std;
int main()
{
    SeqList mylist;
    InitList(&mylist);
    ElemType item;
    int pos;
    int select = 1;
    while(select)
    {
        cout<<"******************************************"<<endl;
        cout<<"*[1] push_back       [2] push_front      *"<<endl;
        cout<<"*[3] show_list       [0] quit_system     *"<<endl;
        cout<<"*[4] pop_back        [5] pop_front       *"<<endl;
        cout<<"*[6] insert_pos      [7] insert_val      *"<<endl;
        cout<<"*[8] delete_pos      [9] delete_val      *"<<endl;
        cout<<"*[10] find_key       [11] length         *"<<endl;
        cout<<"*[12] reverse_list   [13] sort           *"<<endl;
        cout<<"*[14] clear_list                         *"<<endl;
        cout<<"******************************************"<<endl;
        cout<<"请选择:>";
        cin>>select;
        switch(select)
        {
        case 1:
            cout<<"请输入要插入的数据(-1结束):>";
            while(cin>>item, item!=-1) 
            {
                push_back(&mylist, item);
            }
            break;
        case 2:
            cout<<"请输入要插入的数据(-1结束):>";
            while(cin>>item, item!=-1) 
            {
                push_front(&mylist, item);
            }
            break;
        case 3:
            ShowList(&mylist);
            break;
        case 4:
            pop_back(&mylist);
            break;
        case 5:
            pop_front(&mylist);
            break;
        case 6:
            cout<<"请输入要插入的位置:>";
            cin>>pos;
            cout<<"请输入要插入的值:>";
            cin>>item;
            insert_pos(&mylist, pos, item);
            break;
        case 7:
            cout<<"请输入要插入的值:>";
            cin>>item;
            insert_val(&mylist, item);
            break;
        case 8:
            cout<<"请输入要删除的位置:>";
            cin>>pos;
            delete_pos(&mylist, pos);
            break;
        case 9:
            cout<<"请输入要删除的值:>";
            cin>>item;
            delete_val(&mylist, item);
            break;
        case 10:
            cout<<"请输入要查找的值:>";
            cin>>item;
            p = find_key(&mylist, item);
            if(p == NULL)
            {
                cout<<"要查找的值:"<<item<<"不存在!"<<endl;
            }
            break;
        case 11:
            cout<<"SeqList Length = "<<Length(&mylist)<<endl;
            break;
        case 12:
            reverse_list(&mylist);
            break;
        case 13:
            sort_list(&mylist);
            break;
        case 14:
            clear_list(&mylist);
            break;
        }
        system("pause");
        system("cls");
    }
    destroy_list(&mylist);
    return 0;
}

    在上述代码的贯彻中bool Inc(SeqList *list);方法的落实进度是让该顺序表能够随着数据的插入拉长顺序表的尺寸也随着提升，然后

再拓宽头插法抑或尾插法的时候就绝置之不顾忌顺序表的半空中满了不能够插入的标题了。**

 

本文由今晚最快开奖现场直播发布于关于计算机,转载请注明出处：数据结构，数据结构之线性表

关键词：

启发式搜索A，多单位寻路算法

多单位寻路算法，找寻最优解，算法最优 对于单个单位的寻路可以使用A*算法。可是在实际应用中一重现身多个单位...

详细>>

结对编制程序

结对编程（黄金点游戏），结对编程黄金点游戏 我扮演的角色是驾驶员 一、结对伙伴 领航员：赵峻 作业地址见我的...

详细>>

模板增强

C++11/14学习（五）模板增强，14模板 外部模板 传统 C++ 中，模板只有在使用时才会被编译器实例化。 换句话说，只要...

详细>>

Shell脚本监察和控制网址页面平常打开状态，巧用

Nginx静态文件管理技能是超级屌的，我们能或不可能越发优化呢？静态文件的读取，会消耗IO财富。能够设想把静态文...

详细>>