数据结构—顺序表的基本操作与元素的插入（C语言详细解读版2/3）

53 阅读 0 评论 35 点赞

我是靠谱客的博主想人陪灯泡，最近开发中收集的这篇文章主要介绍数据结构—顺序表的基本操作与元素的插入（C语言详细解读版2/3），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本部分操作：关于顺序表的清除、求长度、判空、新元素插入、遍历。

/* [Daily Coding] Fall in love coding! */
/*
顺序表 (SqList, Sequence List)，即顺序线性表。
*/
// 顺序表的初始化
#include"stdio.h"

#include"malloc.h"
// malloc
#include"stdlib.h"
// exit
#define List_InitSize 100
#define List_Increment 10
typedef struct{
int *elem;
// 存储空间基址
int length;
// 当前长度
int listsize; // 当前分配的存储容量(以sizeof(int)为单位)
}SqList;
// 【C段代码】调用示例：
// SqList l; 
// Init_SqList03(&l);
void Init_SqList03(SqList *L)
{
L->elem = (int*)malloc(List_InitSize * sizeof(int));
if (!L->elem)
{
exit(-2);
}
L->length = 0;
L->listsize = List_InitSize;
}
void DestroyList_Sq(SqList *L)
{
free(L->elem);
// free((*L).elem);
L->elem = NULL;
// (*L).elem = NULL;
// 置空防止野指针 
L->length = 0;
// (*L).length = 0; 
L->listsize = 0;	// (*L).listsize = 0; 
}
// 清除 
int ClearList_Sq(SqList *L)
{
// 直接把L->length置为0即可，这样在下一次插入操作的时候，之前的元素就被覆盖了。（其实，在计算机内部，当你申请了一段内存用于存放元素的时候，这个内存中已经存放了一些随机数。这些随机数会在插入操作时被覆盖。）
L->length = 0;
return 0;
}
/*
// 清除顺序表：无返回值版
void ClearList(SqList *L)
{
L->length = 0;
}
*/
// 求长度 
int ListLength_Sq(SqList *L)
{
// 直接返回顺序表中元素的长度即可。注意，顺序表的长度和顺序表的容量是两个概念。顺序表的容量是表示这个表能存放多少元素。顺序表的长度表示这个顺序表中已经存在了多少元素。
return L->length;
}
// 判空 
int ListIsEmpty_Sq(SqList *L)
{
if(L->length == 0)
return 1;
else
return 0;
}
// 画个图，形象地说一下这个问题。 
int ListInsert_Sq(SqList *L, int i, int e)
{
// 这里的i，要想清楚它的含义。这里的i是指，在第i位之前（i从1开始）。比如，在第0号位插入，就是在第1号位之前插入，即，i=1。 
// * 假设顺序表初始长度为10，目前里面已经有了1个元素。我们可以插入的位置，用计算机语言描述插入位置的下标可以是（0号位，1号位。不能插入2号位，因为是顺序存储，不能跳）
// * 那么，用大众的思维，我们如果要插入0号位。那就是说，在第1个位置之前插入，即i=1。对应的，该位置的地址可以利用语句 [(*L).elem + i - 1]表示。
// * 并且，如果我们要插入在第1号位，在本例中，1号位就是顺序表的最后1个位置的后面。那就是说，在第2个位置插入。那么，2怎么来的呢？
// ** 2应该是当前顺序表内元素的个数+1.换句话说，在最后一位插入，就是在当前顺序表的length + 1位插入。 
// ** 比如，现在顺序表中有3个元素。我想在最后1位之后插入。那就是获取L的length(也就是3),在这个位置后面插入就行了，即i要再增加1位，变为4，因为对应的代码应该延续上面的，有一个减1的操作。 [(*L).elem + 4 - 1]
// * 所以，这里我们要判断的是，待插入位置，不能小于1（大众思维）；不能大于length+1（比如已存3个元素，我们最多在第4个位置插入） 
if((i < 1) || i > L->length + 1)
return 0;
if (L->length >= L->listsize)
{
int *newbase = (int*)realloc(L->elem, (L->listsize + List_Increment) * sizeof(int));
if (!newbase)
{
exit(-2);
}
L->elem = newbase;
L->listsize = L->listsize + List_Increment;
}
int *q = L->elem + i - 1;
// q指向待插入的位置
int *p;
for (p = L->elem + L->length - 1; p >= q; p--)
{
*(p + 1) = *(p);
}
// 腾出位置后，在q位置插入元素e
*q = e;
// 插入元素后，长度别忘记加啦~ 
L->length++;
return 0;
}
void ListTraverse_Sq(SqList *L)
{
int i;
for (i = 0; i < L->length; i++)
{
printf("%d ", *(L->elem + i));
// L->elem指向的是元素数组的首地址
}
printf("n");
}
int main()
{
SqList Lc;
// 操作符为 "." 
Init_SqList03(&Lc);
printf("Lc.length=%d, Lc.listsize=%dn", Lc.length, Lc.listsize);
ListInsert_Sq(&Lc, 1, 3);
printf("Lc.length=%d, Lc.listsize=%dn", Lc.length, Lc.listsize);
ListTraverse_Sq(&Lc);
ListInsert_Sq(&Lc, 1, 4);
printf("Lc.length=%d, Lc.listsize=%dn", Lc.length, Lc.listsize);
ListTraverse_Sq(&Lc);
return 0;
}