读书笔记-《大话数据结构》第三章 线性表之顺序存储结构
【摘要】
线性表的机内表示法(又称存储结构)有2种
顺序存储结构 链式存储结构
顺序存储结构
是在内存中开辟一个连续的空间用来存储数据,因此对于内存的需求和苛刻,必须是连续的空间.在数据查找(特别是不按照规律排列的数据),时间复杂度教少.效率高.
大概看了一眼书，觉得书上的内容不够实用，在网上找个顺...
线性表的机内表示法(又称存储结构)有2种
- 顺序存储结构
- 链式存储结构
顺序存储结构
是在内存中开辟一个连续的空间用来存储数据,因此对于内存的需求和苛刻,必须是连续的空间.在数据查找(特别是不按照规律排列的数据),时间复杂度教少.效率高.
大概看了一眼书，觉得书上的内容不够实用，在网上找个顺序结构的小demo，以便于理解顺序存储结构
-
#include <stdio.h>
-
#include <stdlib.h>
-
-
#define TRUE 1
-
#define FALSE 0
-
#define ERROR -1
-
-
typedef int Status;
-
typedef int ElemType;
-
-
//------顺序存储结构---------
-
#define LIST_INIT_SIZE 100 //SqList的初始分配大小
-
#define LIST_INCREMENT 10 //SqList的增量分配大小
-
-
typedef struct{
-
ElemType *elem;
-
int length;
-
int listsize;
-
} SqList;
-
-
//线性表初始化
-
Status InitList_Sq(SqList *L){
-
//构造空的线性表,开辟对应内存
-
L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
-
if(!L->elem)
-
return ERROR;
-
-
L->length=0;
-
L->listsize=LIST_INIT_SIZE;
-
return TRUE;
-
}//InitList_Sq
-
-
//线性表销毁
-
void DestoryList_Sq(SqList *L){
-
//销毁已存在的线性表
-
if(L->elem) free(L->elem);
-
L->length=0;
-
}//DestoryList_Sq
-
-
//线性表清空
-
void ClearList_Sq(SqList *L){
-
//清空线性表
-
L->length=0;
-
}//ClearList_Sq
-
-
Status ListEmpty_Sq(SqList L){
-
//线性表为空返回TRUE，否则返回FALSE
-
if(!L.elem) return ERROR;
-
if(L.length!=0) return TRUE;
-
return FALSE;
-
}//ListEmpty_Sq
-
-
Status ListLength_Sq(SqList L){
-
//返回线性表的长度
-
if(!L.elem) return ERROR;
-
return L.length;
-
}//ListLength_Sq
-
-
Status GetElem_Sq(SqList L,int i,ElemType *e){
-
//用e返回L的第i个元素值
-
if(i>L.length||i<1) return ERROR;
-
*e=L.elem[i-1];
-
return TRUE;
-
}//GetElem_Sq
-
-
int LocateElem_Sq(SqList L,ElemType e,int (*cmp)(ElemType el,ElemType e)){
-
//返回L中第一个与e满足cmp函数的数据元素位序，若不存在则返回0
-
int i=0;
-
for(i=0;i<L.length;i++){
-
if(cmp(L.elem[i],e))
-
return i;
-
}
-
return 0;
-
}//LocateElem_Sq
-
-
Status PriorElem_Sq(SqList L,ElemType cur_e,ElemType *e){
-
//若cur_e为L中的元素，则返回其前驱
-
int loc=0;
-
int compareEqual(ElemType a,ElemType b);
-
-
loc=LocateElem_Sq(L,cur_e,compareEqual);
-
if(loc>0) {
-
*e=L.elem[loc-1];
-
return TRUE;
-
}
-
else
-
return FALSE;
-
}//PriorElem_Sq
-
-
Status NextElem_Sq(SqList L,ElemType cur_e,ElemType *e){
-
//若cur_e为L中的元素，返回其后继
-
int loc;
-
int compareEqual(ElemType a,ElemType b);
-
-
loc=LocateElem_Sq(L,cur_e,compareEqual);
-
if(loc<L.length-1){
-
*e=L.elem[loc+1];
-
return TRUE;
-
}
-
else
-
return FALSE;
-
}
-
-
//@Func: 插入
-
//@Param 线性表地址 ,插入位置,插入的数据
-
Status ListInsert_Sq(SqList *L,int i,ElemType e){
-
//在L的每i个元素之前插入e
-
int j=0;
-
-
if((i>L->length && L->length!=0) || i<1)
-
return ERROR;//位置不合法
-
-
if(L->length>=L->listsize)
-
{
-
L->elem=(ElemType*)realloc(L->elem,(LIST_INIT_SIZE+LIST_INCREMENT)*sizeof(ElemType));
-
if(!L->elem) return ERROR;//分配失败
-
L->listsize+=LIST_INCREMENT;
-
}
-
-
for(j=L->length;j>=i;j--){
-
L->elem[j]=L->elem[j-1];
-
}
-
L->elem[j]=e;
-
L->length++;
-
return TRUE;
-
}//ListInsert_Sq
-
-
Status ListDelete_Sq(SqList *L,int i,ElemType *e){
-
//删除L中第i元素，并用e返回
-
int j=0;
-
-
if(L->length==0||i<1||i>L->length) return ERROR;
-
*e=L->elem[i-1];
-
for(j=i-1;j<L->length-1;j++)
-
L->elem[j]=L->elem[j+1];
-
L->length--;
-
return TRUE;
-
}//ListDelete_Sq
-
-
void ListTraverse_Sq(SqList L,void (*visit)(ElemType e)){
-
//遍历L
-
int i;
-
for(i=0;i<L.length;i++)
-
visit(L.elem[i]);
-
}//ListTraverse_Sq
-
-
int compareEqual(ElemType a,ElemType b){
-
//比较元素，相等返回1
-
if(a==b) return TRUE;
-
else
-
return FALSE;
-
}
-
-
void visit(ElemType e){
-
//输出e
-
printf("%d ",e);
-
}
-
-
-
-
//主函数
-
int main(){
-
-
//生命顺序存储结构
-
SqList L;
-
ElemType e;
-
-
InitList_Sq(&L);
-
-
ListInsert_Sq(&L,1,1);
-
ListInsert_Sq(&L,1,2);
-
ListInsert_Sq(&L,1,3);
-
ListInsert_Sq(&L,1,4);
-
ListTraverse_Sq(L,visit);
-
printf("\n");
-
if(PriorElem_Sq(L,2,&e))
-
//ListDelete_Sq(&L,1,&e);
-
printf("e=%d\n",e);
-
//ListTraverse_Sq(L,visit);
-
printf("\n");
-
return 0;
-
}
文章来源: yujiang.blog.csdn.net，作者：鱼酱2333，版权归原作者所有，如需转载，请联系作者。
原文链接：yujiang.blog.csdn.net/article/details/52149834
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）