- 首页 > it技术 > >
Data|[转载] 线性表的数组实现
dataAlgorithmsANDstructure
/*对于线性结构，有两种保存的方法，一种是使用C语言中内置的数组，这样的结构成为顺序表；另一种使用指针，这样的结构成为链表。对于线性结构，有12种基本的操作，分别是：初始化、删除、清空、判断是否为空、遍历、求表的长度、求某个元素在表中的位置、返回特定序号的元素、求某个元素的前一个元素、求某个元素的后一个元素、插入一个元素、删除一个元素。这一小节介绍如何利用数组实现线性表。*//*再插入元素时，如果线性表已满，需要重新分配内存空间，新分配的内存空间设定为原来的2倍。这个倍数也不是我随便给出的，我是参考C++中STL里面的vector给出的。相信那些专家，肯定考虑了倍数过小而导致多次分配内存与内存分配太大的折中*/#include
#include typedef int Elementtype;
typedef struct arraylist
{
Elementtype *Array;
//实际存放元素的数组
int length;
//数组中已经使用了多少元素
int size;
//数组的容量
} ;
//初始化顺序表：给出初始化长度
bool InitialArray(arraylist *arrayList,int len)
{
arrayList->length = 0;
arrayList->size = len;
arrayList->Array = (Elementtype*)malloc(len*sizeof(Elementtype));
if(NULL == arrayList->Array)
return false;
else
return true;
}//删除顺序表
void DeleteArray(arraylist *arrayList)
{
arrayList->length = 0;
arrayList->size = 0;
free(arrayList->Array);
arrayList->Array = NULL;
}//清空顺序表
void ClearArray(arraylist *arrayList)
{
arrayList->length = 0;
}//判断是否为空
bool Empty(arraylist *arrayList)
{if(0 == arrayList->length)
{
printf("the arrayList is empty!\n");
return true;
}
else
{
printf("the arrayList is not empty!\n");
return false;
}
}//求有多少个元素
int ArrayLength(arraylist *arrayList)
{
return arrayList->length;
}//取出某个元素
bool GetElement(arraylist *arrayList,int index,Elementtype *element)//元素取出用指针
{
if(index < 0 || index > ArrayLength(arrayList)-1) //数组越界
return false;
else
{
*element = arrayList->Array[index];
return true;
}}//遍历顺序表，并打印
void PrintArray(arraylist *arrayList)
{
printf("array elements are: ");
for(int i = 0;
i < ArrayLength(arrayList);
++i)
{
printf("%d\t",arrayList->Array[i]);
}
printf("\n");
}//判断某个元素的位置
int LocateElement(arraylist *arrayList,Elementtype element)
{
for(int i = 0;
i < ArrayLength(arrayList);
++i)
{
if(element == arrayList->Array[i])
return i;
}
return -1;
}//求某个元素的前驱：如果没找到返回-2；如果是第一个元素。返回-1；否则返回前驱元素的下标
int PreElement(arraylist *arrayList,Elementtype element,Elementtype *preElement)
{
for(int i = 0 ;
i < ArrayLength(arrayList);
++i)
{
//如果找到了
if(element == arrayList->Array[i])
{
//如果是第一个元素
if(0 == i)
{
return -1;
}
else
{
*preElement = arrayList->Array[i-1];
return i-1;
}
}
}
return -2;
}//求某个元素的后继：如果没找到，返回-2,如果是最后一个元素，返回-1；否则返回后继元素的下标
int NextElement(arraylist *arrayList,Elementtype element,Elementtype *nextElement)
{
for(int i = 0;
i < ArrayLength(arrayList);
++i)
{
if(element == arrayList->Array[i])
{
if(ArrayLength(arrayList) -1 == i)
{
return -1;
}
else
{
*nextElement = arrayList->Array[i+1];
return i+1;
}
}
}
return -2;
}//将元素插入到指定位置
bool InsertElem(arraylist *arrayList,int index ,Elementtype element )
{
//先判断插入位置是否合法
if(0 > index ||ArrayLength(arrayList) < index)
return false;
//先判断当前的指针是否有足够的连续空间，如果有，扩大mem_address指向的地址，并且将mem_address返回，如果空间不够，先按照 newsize指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来mem_address所指内存区域（注意：原来指针是自动 释放，不需要使用free），同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。
//如果顺序表存储空间已满，则需要重新分配内存
if(arrayList->length == arrayList->size)
{
arrayList->Array = (Elementtype*)realloc(arrayList->Array,2*arrayList->size*sizeof(Elementtype));
if(NULL == arrayList->Array)
//分配失败，程序退出
return false;
else
//分配成功，扩容
arrayList->size *= 2;
}
//将插入点之后的元素后移
for(int i = ArrayLength(arrayList);
i > index;
--i)
arrayList->Array[i] = arrayList->Array[i-1];
//插入元素
arrayList->Array[index] = element;
//顺序表长度自增
++arrayList->length;
return true;
}//删除指定位置的元素
bool DeleteElem(arraylist *arrayList,int index ,Elementtype *element)
{
if(index < 0 || index > ArrayLength(arrayList)-1)
return false;
*element = arrayList->Array[index];
//将删除点的元素依次左移
for(int i = index;
i < ArrayLength(arrayList);
++i)
{
arrayList->Array[i] = arrayList->Array[i+1];
}
--arrayList->length;
;
return true;
}/*我们可以看出，利用数组来表示线性结构，最大的优点在于由于数组是连续储存的，所以随机访问速度非常快，只需要用数组的首地址+下标*sizeof(结构体)就能计算指定元素的地址了。而它的缺点也很明显：就是插入、删除时效率很低，因为要移动大量的元素，甚至需要重新分配内存。*/
推荐阅读
