End-顺序表的基本操作

方法一：初始化顺序表

sList* initList()
{
    sList* pList =(sList*)malloc(sizeof(sList)); //定义动态内存分配的指针
    memset(pList->data,MAX_SIZE,0);//将某一块内存中的全部设置为指定的值.将数据全部初始为0
    pList->length=0; //设置默认长度为0
    return pList;
}
1
2
3
4
5
6
7

方法二：初始化顺序表

void InitList(SqList * &L)
{
    L=(SqList *)malloc(sizeof(SqList));//分配存放线性表的空间
    L->length=0;
}
1
2
3
4
5

---

方法一：创建顺序表

sList* createList(sList* pList,int* pArray,int len)
{
   sList* pNativeList=pList;
   if (len>=MAX_SIZE)
   {
       return NULL;
   }
   for(int i=0;i<len;i++)
   {
       pList->data[i]=pArray[i];
   }
   pList->length=len;
   return pNativeList;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法二：创建顺序表

void CreateList(SqList * &L,ElemType a[],int n)
{
    L=(SqList *)malloc(sizeof(SqList));
   /*  L一个指针，指向SqList这样一个结构这个语句是一个赋值语句，
    malloc(sizeof(SqList))是分配一块大小为sizeof(SqList)的内存，并返回首地址
    (SqList*)表示把这个指针转型为SqList结构的指针 */
    for (int i = 0; i < n; i++)
    {
        L->data[i]=a[i];
    }
    L->length=n;   
}
1
2
3
4
5
6
7
8
9
10
11
12

⭐方法一：插入元素

sList* insertList(sList* pList,int pos,int iNewVal)
{
    // sList* pNativeList=pList;
    // cout<<"这是本地执行前的顺序表"<
    // printList(pNativeList);

    if (pos<0 || pos>MAX_SIZE)
    {
       cout<<"越界访问,无法继续进行！"<<endl;
    }else if(pos == pList->length-1){
        pList->data[pos]=iNewVal;//在顺序表最后面插入
        pList->length++;
    }else{
        //不是在顺序表最后插入的插入操作
        for (int i = pList->length-1; i >= pos; i--)
        {
            pList->data[i+1]=pList->data[i]; //后移操作
        }
        pList->data[pos]=iNewVal; //将插入的值赋值给要插入的下标位置
        pList->length++;
        
    }
    // cout<<"这是本地执行后的顺序表"<
    // printList(pNativeList);
    return pList;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

⭐方法二：插入元素

bool ListInsert(SqList * &L,int i,ElemType e)
{
    int j;
    if (i<1 || i>L->length+1 || L->length==MaxSize)
    {
       return false;
    }
    i--; //将顺序表的位序转换为data的下标
    for ( j = L->length; j >i; j--)
    {
       L->data[j]=L->data[j-1]; //将data[i]中的数据的元素后移一个位置
    }
       L->data[i]=e;
       L->length++;
       return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

⭐方法一：删除元素

sList* deleteList(sList* pList,int pos)
{
    if (pos<0 || pList->length>MAX_SIZE)
    {
        cout<<"越界访问,无法继续进行！"<<endl;
    }else if (pos ==pList->length-1)
    {
        //pList->data[pos]=-9999;
        pList->length--;
    }else{
        for (int i = pos; i <=pList->length-1; i++)
        {
           pList->data[i]=pList->data[i+1];
        }
        pList->length--;
    }
    return pList;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

⭐方法二：删除元素

bool ListDele(SqList * &L,int i,ElemType &e)
{
    int j;
    if (i<1 || i>L->length)
    {
        return false;
    }
    i--; //将顺序表的位序转换为data的下标
    e=L->data[i];//将要删掉的i个元素的数据赋值给e（char）
    for (j= i ; j < L->length; j++)
    {
        /* 将data[i]之后的元素前移一个位置*/
        L->data[j]=L->data[j+1];
    }
    L->length--;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法一的总代码：

#include
#include
using namespace std;
const int MAX_SIZE =50;

//定义结构体
typedef struct sqList
{
    int data[MAX_SIZE];
    int length;
}sList;
//初始化顺序表
sList* initList()
{
    sList* pList =(sList*)malloc(sizeof(sList)); //定义动态内存分配的指针
    memset(pList->data,MAX_SIZE,0);//将某一块内存中的全部设置为指定的值.将数据全部初始为0
    pList->length=0; //设置默认长度为0
    return pList;
}
//数据的创建
sList* createList(sList* pList,int* pArray,int len)
{
   sList* pNativeList=pList;
   if (len>=MAX_SIZE)
   {
       return NULL;
   }
   for(int i=0;i<len;i++)
   {
       pList->data[i]=pArray[i];
   }
   pList->length=len;
   return pNativeList;

}
//数据的打印
int printList(sList* pList)
{
    for (int i = 0; i < pList->length; i++)
    {
        cout<< pList->data[i]<<"\t";
    }
    cout<<endl;
    return 0;
}
//判断顺序表是否为空
bool isListEmpty(sList* pList)
{
    if (pList->length == 0)
    {
        return true;
    }else{
        return false;
    }
    
}
//根据下标获取数组中的值
int getElem(sList* pList,int pos)
{
    if (pos<0 || pos>=pList->length)
    {
        cout<<"越界，非法访问"<<endl;
        return 0;
    }else{
        //第pos个元素
        return pList->data[pos];
    }
    
}
//通过元素找下标
int getElemPos(sList* pList,int elemvalue)
{
    for (int i = 0; i < elemvalue; i++)
    {
        if (elemvalue == pList->data[i])
        {
            cout<<"value="<<elemvalue<<",则i="<<i<<endl;
            return i;
        }
    }
    cout<<"value="<<elemvalue<<" 在顺序表中不存在！"<<endl;
    return 0;
}
//求顺序表长度
int getListLen(sList* pList)
{
    return pList->length;
}
//插入一个元素
sList* insertList(sList* pList,int pos,int iNewVal)
{
    // sList* pNativeList=pList;
    // cout<<"这是本地执行前的顺序表"<
    // printList(pNativeList);

    if (pos<0 || pos>pList->length)
    {
       cout<<"越界访问,无法继续进行！"<<endl;
    }
    //不应该存在，老师出错了
    // else if(pos == pList->length-1){
    //     pList->data[pos]=iNewVal;//在顺序表最后面插入
    //     pList->length++;
    // }
    else{
        //不是在顺序表最后插入的插入操作
        for (int i = pList->length-1; i >= pos; i--)
        {
            pList->data[i+1]=pList->data[i]; //后移操作
        }
        pList->data[pos]=iNewVal; //将插入的值赋值给要插入的下标位置
        pList->length++;
        
    }
    // cout<<"这是本地执行后的顺序表"<
    // printList(pNativeList);
    return pList;
}

//删除一个元素
sList* deleteList(sList* pList,int pos)
{
    if (pos<0 || pList->length>MAX_SIZE)
    {
        cout<<"越界访问,无法继续进行！"<<endl;
    }else if (pos ==pList->length-1)
    {
        //pList->data[pos]=-9999;
        pList->length--;
    }else{
        for (int i = pos; i <=pList->length-1; i++)
        {
           pList->data[i]=pList->data[i+1];
        }
        pList->length--;
    }
    return pList;
    
}
//释放链表
bool freeList(sList* pList)
{
    if (pList!=NULL)
    {
        free(pList);
    }
    pList=NULL;
    return true;
}
int main()
{
    const int iArraySize=5;
    int iArray[iArraySize]={5,10,15,20,25};
    sList* pList=initList();//初始化顺序表
    pList=createList(pList,iArray,iArraySize);//创建顺序表
    printList(pList);//打印顺序表

    //判断是否为空
    bool bEmptyFlag =isListEmpty(pList);
    if (bEmptyFlag)
    {
        cout<<"\n当前顺序表为空!"<<endl;
    }else{
        cout<<"\n当前顺序表非空!"<<endl;
    }
    //获取下标的值
    cout<<"下标为3的值为："<<getElem(pList,3)<<endl;

    //获取下标
    getElemPos(pList,15);
    getElemPos(pList,40);

    //求顺序表的长度
    cout<<"此时顺序表的长度="<<getListLen(pList)<<endl;

    //插入顺序表数据的操作
    cout<<"插入7之后打印的顺序表："<<endl;
    pList=insertList(pList,4,7);
    printList(pList);
    cout<<"此时顺序表的长度="<<getListLen(pList)<<endl;

    cout<<"插入77之后打印的顺序表："<<endl;
    pList=insertList(pList,6,77);
    printList(pList);
    cout<<"此时顺序表的长度="<<getListLen(pList)<<endl;

    cout<<"插入777之后打印的顺序表："<<endl;
    pList=insertList(pList,51,777);

    //删除顺序表中数据的操作
    cout<<"删除下标为2的数据之后打印的顺序表："<<endl;
    pList=deleteList(pList,2);
    printList(pList);
    cout<<"此时顺序表的长度="<<getListLen(pList)<<endl;

    //结束，释放表
    // freeList(pList);
    if (freeList(pList))
    {
        cout<<"表已经释放！"<<endl;
    }else{
        cout<<"表未释放！"<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205

方法二的总代码：

/* 题目：编写一个程序实现顺序表的各种基本运算和整体建表算法
    （假设顺序表的元素类型是ElemType为char），并在此基础上设计一个程序
    完成以下功能。
    1、初始化顺序表L
    2、依次插入元素a、b、c、d、e。
    3、输出顺序表L
    4、输出顺序表L的长度。
    5、判断顺序表L是否为空。
    6、输出顺序表L的第3个元素。
    7、输出元素a的位置
    8、在第4个元素的位置上插入元素f。
    9、输出顺序表L
    10、删除顺序表L的第3个元素
    11、输出顺序表L
    12、释放顺序表L */
#include
#include
#define MaxSize 50
typedef char ElemType;//定义一种新的类型名称ElemType,该类型名同char效果一样
typedef struct 
{
    ElemType data[MaxSize];
    int length;
}SqList;
//创建顺序表
void CreateList(SqList * &L,ElemType a[],int n)
{
    L=(SqList *)malloc(sizeof(SqList));
   /*  L一个指针，指向SqList这样一个结构这个语句是一个赋值语句，
    malloc(sizeof(SqList))是分配一块大小为sizeof(SqList)的内存，并返回首地址
    (SqList*)表示把这个指针转型为SqList结构的指针 */
    for (int i = 0; i < n; i++)
    {
        L->data[i]=a[i];
    }
    L->length=n;   
}

//初始化线性表
void InitList(SqList * &L)
{
    L=(SqList *)malloc(sizeof(SqList));//分配存放线性表的空间
    L->length=0;
}
//销毁线性表
void DestroyList(SqList * &L)
{
    free(L);
}
//判断线性表是否为空表
bool ListEmpty(SqList * L)
{
    return(L->length==0);
}
//求线性表的长度
int ListLength(SqList *L)
{
    return(L->length);
}

//输出线性表
void DispList(SqList * L)
{
    for (int i = 0; i < L->length; i++)
    {
        printf(" %c ",L->data[i]);
    }
    printf("\n");   
}
//求线性表中第i个元素的值
bool GetElem(SqList *L,int i,ElemType &e)
{
    if (i<1 || i>L->length)
    {
        return false;
    }
    e=L->data[i-1];
    return true;
}
//查找第一个值域为e的元素的序号
int LocateElem(SqList *L,ElemType e)
{
    int i=0;
    while (i<L->length && L->data[i]!=e)
    {
        i++;
    }
    if (i>L->length)
    {
        return 0;
    }
    else
        return i+1;
    
}
//插入第i个元素
bool ListInsert(SqList * &L,int i,ElemType e)
{
    int j;
    if (i<1 || i>L->length+1 || L->length==MaxSize)
    {
       return false;
    }
    i--; //将顺序表的位序转换为data的下标
    for ( j = L->length; j >i; j--)
    {
       L->data[j]=L->data[j-1]; //将data[i]中的数据的元素后移一个位置
    }
       L->data[i]=e;
       L->length++;
       return true;
}

//删除第i个元素
bool ListDele(SqList * &L,int i,ElemType &e)
{
    int j;
    if (i<1 || i>L->length)
    {
        return false;
    }
    i--; //将顺序表的位序转换为data的下标
    e=L->data[i];//将要删掉的i个元素的数据赋值给e（char）
    for (j= i ; j < L->length; j++)
    {
        /* 将data[i]之后的元素前移一个位置*/
        L->data[j]=L->data[j+1];
    }
    L->length--;
    return true;
}
int main()
{
    SqList *L;
    ElemType e;
    printf("顺序表的基本运算如下：\n");
    printf("\t（1）初始化顺序表L\n");
    InitList(L);
    

    printf("\t（2）依次插入元素a,b,c,d,e\n");
    ListInsert(L,1,'a');
    ListInsert(L,2,'b');
    ListInsert(L,3,'c');
    ListInsert(L,4,'d');
    ListInsert(L,5,'e');


    printf("\t（3）输出顺序表L：\n\t\t");
    DispList(L);

    printf("\t（4）顺序表L长度：%d\n",ListLength(L));

    printf("\t（5）顺序表L为%s\n",(ListEmpty(L)?"空":"非空"));
    
    GetElem(L,3,e);
    printf("\t（6）顺序表L的第3个元素：%c\n",e);

    printf("\t（7）元素a的位置：%d\n",LocateElem(L,'a'));
    
    printf("\t（8）在第4个元素位置上插入元素f\n");
    ListInsert(L,4,'f');

    printf("\t（9）输出顺序表L：\n\t\t");
    DispList(L);

    printf("\t（10)删除L的第3个元素\n");
    ListDele(L,3,e);

    printf("\t（11）输出顺序表L：\n\t\t");
    DispList(L);

    printf("\t（12）释放顺序表L\n");
    DestroyList(L);
    if (L)
    {
        return 1;
    }else{
        printf("未释放顺序表");
    }
    
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183