数据结构顺序表
Were equations, pictures or diagrams not properly rendered, please refresh the page. If the problem persists, you can contact me.
数据结构顺序表算法C语言实现
准备-函数结果状态码
#include <stdlib.h>
#include <malloc.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define LIST_INIT_SIZE 10//线性表储存空间的初始分配量
#define LISTADD 5//线性表储存空间的分配增量
typedef int ElemType;//定义顺序表元素的类型为int(一般用于返回所取元素)
typedef int Status;//Status是函数的类型，其值是函数结果状态代码 ，如OK等
typedef int Boolean;//Boolea是布尔类型
typedef struct {
ElemType *elem;//储存空间基地址
int length;//当前长度
int listsize;//当前分配的储存总容量（sizeof(ElemType）为单位
}Sqlist;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
顺序表示的线性表的基本操作（12个包括了书中有关操作的算法）
#include <stdio.h>
// 1, InitList(&L) 操作结果：构造一个空的顺序表L。书中算法2.3
Status InitList(Sqlist *L){
(*L).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));/*L.elem作为指针指向内
存，malloc用于分配内存，而内存为LIST_INIT_SIZE*sizeof(ElemType)这么大*/
if(!(*L).elem) exit(OVERFLOW);//exit(-1) 存储空间失败
(*L).length = 0;//初始化列表长度为0
(*L).listsize = LIST_INIT_SIZE;//初始化空表的储存总容量
return OK;//返回状态码 1
}
// 2, DestroyList(&L) 初始条件：顺序表L已存在。 操作结果：销毁顺序表L。
Status DestroyList(Sqlist *L){
free((*L).elem);//释放L.elem这个指针指向的内存
(*L).elem = NULL;//指向空
(*L).length = 0;//将长度赋值为0
(*L).listsize = 0;//将当前分配的储存总容量变为0
return OK;
}
//3, ClearList(&L) 初始条件：顺序表已经存在。操作结果：将L重置为空表。
Status ClearList(Sqlist *L){
(*L).length = 0;//清空当前长度
return OK;
}
//4. ListEmpty(L) 初始条件：顺序表L已存在。操作结果：判断若顺序表L为空返回TRUE，否则返回FLASE。
Status ListEmpty(Sqlist L){
if(L.length ==0){
return TRUE;
}else{
return FALSE;
}
}
//5, Listlength(L) 初始条件：顺序表已存在。操作结果：返回L中的数据元素的个数
Status ListLength(Sqlist L){
return L.length;
}
//6, GetElem(L,i,&e) 初始条件：顺序表已存在（l<=i<=ListLength(L)）. 操作结果：用e返回L中第i个数据元素的值。
Status GetElem(Sqlist L,int i,ElemType *e){
if(i<1||i>L.length){
exit(ERROR);
}
*e = L.elem[i-1];//*e = *(L.elem+i-1）
return OK;
}
//7, LocateElem(L,e,compare()) 初始条件：顺序表L已存在，compare()的数据元素判定函数。
// 操作结果：返回L中第1个与e的满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回0.
// 书中算法2.6(进行两个元素之间的比较) 时间复杂度为O(L.length)
int LocateElem(Sqlist L,ElemType e,Status (*compare)(ElemType,ElemType)){//compare()形参是函数指针
/*
*/
int i =1; //i的初值为第一个元素的位序
ElemType *p=L.elem; //p的初值为第一个元素的存储位置
while(i<=L.length && !(*compare)((*p++),e)){
++i;
}
if(i<=L.length) return i;
else
return 0;
}
//8, PriorElem(L,cur_e,&pre_e) 初始条件：顺序表L已存在。
//操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
Status PriorElem(Sqlist L,ElemType cur_e,ElemType *pre_e){
ElemType *p = L.elem+1;//指针变量p指向第二个数据元素
int i=2;
while(i<=L.length &&(*p)!=cur_e){
p++;
++i;
}
if(i>=L.length){
return ERROR;
}else{
*pre_e=(*--p); //p先自减，pre_e就指向该数据元素的前驱结点
return OK;
}
}
//9, NextElem(L,cur_e,&next_e) 初始条件：顺序表L已存在。
//操作结果：若cur_e是L的数据元素，且不是第一个，则用next_e返回它的前驱，否则操作失败，next_e无定义。
Status NextElem(Sqlist L,ElemType cur_e,ElemType *next_e){
ElemType *p =L.elem;
int i=1;
while(i<L.length && (*p)!=cur_e){
p++;
++i;
}
if(i>=L.length){
return ERROR;
}else{
*next_e =(*++p); //next_e指向该数据元素的后继结点
return OK;
}
}
此处是方法中的插入与删除，重点讲解
//10, ListTraverse(L,visit())
/* 初始条件：顺序线性表L已存在。
操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败 */
Status ListTraverse(Sqlist L,void (*visit)(ElemType*)){ //visit()的形参加&，意味着visit()可以修改L.elem中数据元素的值
int i=1;
ElemType *p=L.elem;
for(i=1;i<=L.length;i++)
(*visit)(p++);
printf("\n");
return OK;
}
//11, ListInsert(Sqlist *L,i,e) 初始条件：顺序表L已存在，1<=i<=ListLength(L)+1。
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
/*
书中算法2.4
算法语言描述：
1，检查插入位置i的有效性，插入位置i的有效范围是1<=i<=ListLength(L)+1（注意：顺序表尾也能执行插入操作）。
2，在插入之前先检查顺序表是否已满(判断顺序表的length是否等于listsize)，在顺序表满的时候不能进行插入运算,需要申请内存空间。
3，后移i位置以后的数据元素，为新数据元素让去第i个位置。
4，将新元素e插入第i个位置。
5，将当前的顺序表length加1.
*/
Status ListInsert(Sqlist *L,int i,ElemType e){
ElemType *p,*q,*newbase = NULL;
//第一步
if(i<1||i>(*L).length+1){判断i的大小是否符合，否则报错
return ERROR;//i的值不合法
}
//第二步
if((*L).length >=(*L).listsize){//由于当前储存空间已经满了增加分配
newbase = (ElemType *)realloc((*L).elem,((*L).listsize+LISTADD)*sizeof(ElemType));
//之前定义了一个结构体，名为ElemType, 现在使用realloc()函数重新分配一块内存。
//这个内存的大小为(L.lestsize+LISTADD)个 ElemType结构体.
if(!newbase) exit(OVERFLOW);
(*L).elem = newbase;//L.elem这个指针指向新的地址
(*L).listsize +=LISTADD; //增加存储容量
}
//第三步
q =&((*L).elem[i-1]); //q指针指向插入位置(或q =(*L).elem+i-1。)
for(p =&((*L).elem[(*L).length-1]);p >=q;--p){ //或p =((*L).elem+(*L).length-1)
*(p+1) =*p;//此处的for循环将所有在q插入位置之后的元素后羿
}
/*或
int j;
for(j =(*L).length;j >=i;--j){
(*L).elem[j] =(*L).elem[j-1]; //或 *((*L).elem+j) =((*L).elem+j-1)
}
(*L).elem[j-1]=e;*/
//第四步
*q =e; //插入数据元素
//第五步
++(*L).length;
return OK;
}
//12, ListDelete(Sqlist &L,int i,ElemType &e) 初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
/*
书中算法2.5
算法语言描述：
1，检查插入位置i的有效性，删除位置i的有效范围是1<=i<=ListLength(L)。
2，在插入之前先检查顺序表是否为空（length！=0）。
3，前移i+1位置以后的数据元素（注意：从i+1的位置开始，要覆盖第i个位置）。
4，将当前的顺序表length减1.
*/
Status ListDelete(Sqlist *L,int i,ElemType e){
ElemType *p,*q,*newbase;
//第一步，i的值不合法
if(i<1||i>(*L).length+1){
return ERROR;
}
//第二步，当储存空间已经满了时增加空间分配
if((*L).length >= (*L).listsize){
newbase = (ElemType *)realloc((*L).elem,((*L).listsize+LISTADD)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW);
(*L).elem = newbase;
(*L).listsize += LISTADD;
}
//第三步
q = &((*L).elem[i-1]);
for(p =&((*L).elem[(*L).length-1]);p >=q;--p){ //或p =((*L).elem+(*L).length-1)
*(p+1) =*p;
}
//第四步
*q = e;
++(*L).length;
return OK;
}
那么以上就是数据结构顺序表的全部内容了，希望能够对大家有所帮助。
作者：剑魄未改
GITHUB地址
ps:相关代码及算法引用CSDN和大话数据结构,并加入自己的修改，有错误请留言，(^__^)
Comments
😅 Commenting is disabled on this post.