【数据结构】线性表&&顺序表详解和代码实例

体贴的说话可扫码关注我们的群众号哦,更多美观尽在微信公众号【程序猿声】

图片 1

顺序表

01 预备知识

 
 1.顺序表定义:线性表的次第表示因的凡用相同组地方连续的存储单元依次存储线性表的数码元素。假使线性表的每个元素用占用L个

1.0 什么是线性表?

线性表(List)是零个或两只数据元素的星星点点系列.

  • 首先它是一个类别.里面的要素是发出各样的,假如出多独因素,除最先和尾声以外的素都起一个前任和一个后继.而开元素只有后继,结尾元素只有前驱.
  • 其次线性表是有限的,也就是是中间的因素个数是片的。

存储单元,并以所占有的率先单单元的储存地方作为数据元素的贮存地点。则线性表中第i+1独数据元素的囤地点LOC(ai+1)和第i单数据

1.1 线性表的基本操作(描述)

 1ADT 线性表(List)
 2Data
 3    线性表的数据对象集合为{a1, a2, a3, ......, an},每个元素类型为DataType。
 4Operation
 5    InitList(L);        //初始化线性表
 6    IsEmptyList(L);     //判断线性表是否为空
 7    ClearList(L);       //清空线性表
 8    GetElemList(L, i, *e); //获取第i个位置的数据
 9    SearchList(L, e); //查找与数据e相等的元素
10    InsertNodeList(L, i, e);//在第i个位置插入元素
11    DeleteNodeList(L, i, *e);//删除第i个位置的元素,e获取删除元素
12    GetLengthList(L);  //获取线性表的长度
13endADT

关于线性表的基本操作就地方几乎种,还有三只例如线性表的排序,合并,逆序等等操作。为了随笔篇幅,就下次更介绍了。

要素的存储地方LOC(ai)之间满足下列关系:LOC(ai+1)=LOC(ai)+L,一般的话,线性表的第i单数据元素ai的储存地点吗:LOC(ai)=LOC(a1)

1.2 什么是顺序存储结构?

线性表的顺序存储结构,就是指
于是平等段落地址连续的存储单元一不善存储线性表的数量元素。宪章过高等语言的恋人,相信对数组这戏意儿都未会面生吧。数组就是如出一辙栽顺序存储结构。

+(i-1)*L,式中LOC(ai)是线性表的首先单数据元素a1之贮存地方,通常如作线性表的前奏地点要基地址。

1.3 什么是链式存储结构?

链式存储结构即是可以为此同组随机的内存单元存储线性表中的因素。与顺序存储不同的凡,这组外存单老大能够是接连的,也然而不连续的。立便表示,元素得以储存于内存的即兴地点。正为这样,在链式结构被,每个元素不仅使抱它的音信,还得仓储它们后继元素的囤积地点。大家将仓储元素消息之域称为数据域,而把囤积后继元素地址的域称为指针域。由这有限组成部分共整合的数量元素ai,则可以称呼节点(Node)。
假使下边这几个图所示:

图片 2

 2.顺序表的数据结构

1.5 什么是链表?

链表就是链式存储的线性表。结点之间通过逻辑连接,形成链式存储结构。存储结点的内存单元,可以是连的呢堪是无总是的。逻辑连接和物理存储次序没有关联。

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

02 顺序表(Sequential List)

 

2.0 什么是顺序表?

使用顺序存储结构的线性表,就是顺序表。

   3. 于逐一表中有以下操作:

2.1 顺序表的囤积结构代码

此间大家统一用C语言来讲述。

1#define MAXSIZE 20   //存储空间的初始大小
2typedef int DataType //类型可根据实际情况而定
3typedef struct 
4{
5    DataType data[MAXSIZE]; //数组来存储数据
6    int length;              //实际长度
7}SqlList;

看得出,顺序表的几乎单第一特征:

  • 仓储空间的职务:数组data
  • 顺序表的无比老容量:数经理度MAXSIZE
  • 顺序表当前长:length
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);

2.2 顺序表的插操作

深信不疑我们在排队的早晚都有了给插的感受吧。当一个栽到您眼前时,那么些时刻你内心os
mmp外加素质三连的又,也只能向后动一个岗位。于是乎这就是够呛了,你前面的为只要于后挪,你后边的末尾呢是……然后队伍容貌里顷刻间尽管乱起……
这,这么些顺序表的插入其实也大都的。由于地方是接连存储的,那么当某地点插入后,其后的元素不得不于后活动一个职务。

图片 3

插算法描述:

  • 挺处理(插入地点不成立、顺序表已经载等等)。抛来很。
  • 自最后一个元素于前头遍历到第i个职务,依次将她们还于后移动一个岗位。
  • 就要插入的元素放入地点i处。
  • 变化忘了说明长度length++。

由于数组下标是从0初叶的,大家习惯要抹的职第i远在又是起1方始算从的。本文就满门合改为,都从0初叶吧。比如要在第5单地方插入一个要素,这虽然是a[5]。不然真的会混杂的。

实际代码如下:

 1//功能:在顺序表L第i个位置之前插入元素e
 2int InsertSqlList(SqlList *L, int i, DataType data)
 3{
 4    int k;
 5    if(L->length==MAXSIZE || i<0 || i>L->length) //记住,都是从0开始的哦
 6        return 0;//异常处理
 7    if(i == L->length)
 8        L->data[length++] = data;//尾插一步到位
 9    if(i < L->length)  //中间插,要挪人啦
10    {
11        for(k = L->length-1; k >= i;k--) //再次强调哈,都是从0开始的。
12            L->data[k+1]=L->data[k];//后移
13        L->data[i] = data;//新元素插入
14        L->length++;
15    }
16    return 1;
17}

   
以上操作包括(1)开首化一个梯次表来布局一个拖欠的顺序表.(2)体现顺序表.(3)尾插法.(3)头插法.(4)求顺序表的长度.

2.2 顺序表的去操作

算法描述:

  • 怪处理(删除地点不客观、顺序表为空等等)
  • 尾删,间接沾取然后length–。
  • 中间删,从i起始以后遍历,依次将诸因素于前头挪。e获取要删元素,length–即可。

 1//功能:在顺序表L中删除第i个数据元素,用e获取被删除值
 2int DeleteElemList(SqlList *L, int i, DataType *e)
 3{
 4    int k;
 5    if(L->length==0 || i<0 || i>L->length-1) //记住,都是从0开始的哦
 6        return 0;//异常处理   
 7    if(i == L->length-1) //尾删,easy
 8    {
 9        *e = L->data[i];//获取要删除元素
10        L->length--; //删除元素
11    }        
12    if(i < L->length)  //中间删,要挪人啦
13    {
14        *e = L->data[i];//获取要删除元素
15        for(k = i; k < L->length-1;k++) //再次强调哈,都是从0开始的。
16            L->data[k]=L->data[k+1];//前移
17        L->length--;
18        return 1;
19    }

(5)按岗位将一个多少元素插入顺序表中.(6)尾部删除元素.(7)头部删除元素.(8)按值的高低插入顺序表中.(9)按职务去

3 顺序表的完全代码

  1#include <stdio.h>
  2#include <stdlib.h>
  3#define MAXSIZE 20
  4#define ERROR 0
  5#define OK 1
  6#define NO 0
  7#define YES 1
  8
  9typedef int DataType;
 10typedef int Status;
 11
 12typedef struct List
 13{
 14    int data[MAXSIZE];
 15    int length;
 16}SqlList;
 17
 18void InitList(SqlList * L);                      //初始化顺序表
 19Status IsEmptyList(SqlList *L);               //判断顺序表是否为空
 20void ClearList(SqlList *L);                      //清空线性表
 21Status GetElemList(SqlList *L,int i,DataType *e); //获取第i个位置的数据
 22int SearchList(SqlList *L, DataType e);         //查找与数据e相等的元素
 23Status InsertNodeList(SqlList *L, int i,DataType e);//在第i个位置插入元素
 24Status DeleteNodeList(SqlList *L, int i, DataType *e);//删除第i个位置的元素,e获取删除元素
 25int GetLengthList(SqlList *L);                        //获取线性表的长度
 26void PrintList(SqlList *L);                         //遍历顺序表,此函数测试使用,根据实际类型编写
 27
 28int main()
 29{
 30    int e;
 31    SqlList *pL = (SqlList*)malloc(sizeof(SqlList));
 32    InitList(pL);
 33    InsertNodeList(pL, 0, 1);
 34    InsertNodeList(pL, 1, 2);
 35    InsertNodeList(pL, 2, 3);
 36    InsertNodeList(pL, 3, 4);
 37    InsertNodeList(pL, 4, 5);
 38    InsertNodeList(pL, 5, 6);
 39
 40    PrintList(pL);
 41
 42    DeleteNodeList(pL, 2, &e);
 43    DeleteNodeList(pL, 4, &e);
 44
 45    PrintList(pL);
 46
 47
 48    return 0;
 49}
 50
 51void InitList(SqlList * L)
 52{
 53    for(int i = 0; i < MAXSIZE; i++)
 54        L->data[i] = 0;
 55    L->length = 0; //将表设为空
 56}
 57
 58Status IsEmptyList(SqlList *L)
 59{
 60    if(L->length == 0)
 61        return YES;//表为空
 62    else
 63        return NO;
 64}
 65
 66void ClearList(SqlList *L)
 67{
 68    InitList(L);//此操作跟初始化一样。
 69}
 70//这里的第i个位置,为了统一我们也是从0算起的
 71Status GetElemList(SqlList *L,int i,DataType *e)
 72{
 73    if(i < 0 || i >= L->length || L->length == 0)
 74        return ERROR;//异常处理
 75    *e = L->data[i];
 76
 77    return OK;
 78}
 79//找到与数据e相同的节点,返回下标。-1表示没找到,ERROR表示表为空
 80int SearchList(SqlList *L, DataType e)
 81{
 82    if(L->length == 0)
 83        return ERROR;
 84    for(int i = 0; i < L->length; i++)
 85    {
 86        if(L->data[i] == e)
 87            return i;
 88    }
 89
 90    return -1;
 91}
 92//获取顺序表的长度
 93int GetLengthList(SqlList *L)
 94{
 95    return L->length;
 96}
 97//在位置i插入元素,再次强调,从0开始
 98Status InsertNodeList(SqlList *L, int i,DataType e)
 99{
100    if(i < 0 || i > L->length || L->length == MAXSIZE)
101        return ERROR;//异常处理
102    for(int k = L->length; k > i; k--)
103    {
104        L->data[k] = L->data[k-1]; //往后挪
105    }
106    L->data[i] = e;//插入数据,
107    L->length++;   //长度也要加1
108
109    return OK;
110}
111
112Status DeleteNodeList(SqlList *L, int i, DataType *e)
113{
114    if(i < 0 || i > L->length || L->length == 0)
115        return ERROR;//异常处理
116    *e = L->data[i];//获取数据
117    for(int k = i; k < L->length -1; k++)
118        L->data[k] = L->data[k+1];//往前挪
119    L->length--; //长度减1
120    return OK;
121}
122
123void PrintList(SqlList *L)
124{
125    if(L->length == 0)
126    {
127        printf("顺序表为空\n");
128    }
129    printf("============遍历顺序表如下=============\n");
130    for(int i = 0; i < L->length; i++)
131    {
132        printf("\tdata[%d] = %d\n", i, L->data[i]);
133    }
134    printf("============共计%d个元素=============\n", L->length);
135
136}

简单易行测试了转。假使在问题,欢迎指正,谢谢我们。

图片 4

 除顺序表中的元素.(10)按值删除顺序表中的元素.(11)按值查找顺序表中的元素.(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);方法的兑现过程是给该顺序表可以就数据的插入增长顺序表的长短为跟着提升,然后

重复开展头插法要尾插法的时段便不要担心顺序表的空中满了不可能插入的题目了。**

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图