首页 > > 程序设计 > C/C++ >

数据结构之线性表（顺序表）

2018-06-17 21:23:41来源：未知 阅读 ()

新老客户大回馈,云服务器低至5折

顺序表

   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）尾插法.（4）头插法.（5）求顺序表的长度.

（6）按位置将一个数据元素插入顺序表中.（7）尾部删除元素.（8）头部删除元素.（9）按值的大小插入顺序表中.（10）按位置删

 除顺序表中的元素.（11）按值删除顺序表中的元素.（12）按值查找顺序表中的元素.（13）将顺序表逆置.（14）将顺序表的元素

 进行排序.（15）清除顺序表.（16）销毁顺序表.

 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);方法的实现过程是让该顺序表可以随着数据的插入增长顺序表的长度也随之增长，然后

再进行头插法或者尾插法的时候就不用担心顺序表的空间满了不能插入的问题了。

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：C++中 模板Template的使用

下一篇：LOJ #115. 无源汇有上下界可行流

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签