首页 > 代码库 > 数据结构之线性表
数据结构之线性表
对于线性表的线性存储结构,主要注意malloc这个函数的使用,它是用来开辟空间的。声明头文件#include <stdlib.h>可以调用它。
#include<iostream>#include<stdio.h>#include<stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;using namespace std;#define LIST_INT_SIZE 100#define LISTINCREMENT 10typedef struct { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 //(以sizeof(ElemType)为单位)} SqList;//初始化线性表Lvoid InitList(SqList *L){ L->elem=(ElemType*)malloc(LIST_INT_SIZE *sizeof(ElemType)); //分配空间 if (L->elem==NULL) exit(ERROR); //若分配空间不成功 L->length=0; //将当前线性表长度置0 L->listsize=LIST_INT_SIZE;}//销毁线性表Lvoid DestroyList(SqList *L){if(L->elem) { if (L->elem) free(L->elem); //释放线性表占据的所有存储空间 L->length=0; L->listsize=0; L->elem=NULL; } else { cout<<"Sqlist is not exsit!\n";exit(ERROR); }}//清空线性表Lvoid ClearList(SqList *L){ if(L->elem) L->length=0; //将线性表的长度置为0 else { cout<<"Sqlist is not exsit!\n";exit(ERROR); }}//判断线性表L是否为空Status IsEmpty(SqList *L){ if(L->elem) if (L->length==0) return TRUE; else return FALSE; else { cout<<"Sqlist is not exsit!\n";exit(ERROR); }}//求线性表L的长度int ListLength(SqList *L){ if(!L->elem){ cout<<"Sqlist is not exsit!\n";exit(ERROR); } else return (L->length);}//获取线性表L中的某个数据元素的内容Status GetElem(SqList *L,int i,ElemType *e){ if(L->elem) { if (i<1||i>L->length) return ERROR; //判断i值是否合理,若不合理,返回ERROR *e=L->elem[i-1]; //数组中第i-1的单元存储着线性表中第i个数据元素的内容 return OK; } else { cout<<"Sqlist is not exsit!\n";exit(ERROR); }}//检索时选用的数据元素判定函数Status equal(ElemType e, ElemType q){ if(e==q) return TRUE; else return FALSE;}//在线性表L中检索值为e的数据元素int LocateElem(SqList *L,ElemType e,Status (*compare)(ElemType e,ElemType q)){ int i; if(L->elem) { for (i=0;i<L->length;i++) if(compare(e,L->elem[i]))return i+1; return 0; } else { cout<<"Sqlist is not exsit!\n";exit(ERROR); }}//在线性表L中第i个数据元素之前插入数据元素eStatus ListInsert(SqList *L,int i,ElemType e){ if(L->elem) { if (i<1||i>L->length+1) return ERROR; //检查i值是否合理 if (L->length==L->listsize) { ElemType *newp=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newp) exit(OVERFLOW); L->elem=newp; L->listsize+=LISTINCREMENT; } for (int j=L->length-1;j>=i-1;i++) //将线性表第i个元素之后的所有元素向后移动 L->elem[j+1]=L->elem[j]; L->elem[i-1]=e; //将新元素的内容放入线性表的第i个位置 L->length++; return OK; } else { cout<<"Sqlist is not exsit!\n";exit(ERROR); }}//将线性表L中第i个数据元素删除Status ListDelete(SqList *L,int i,ElemType *e){ if(L->elem) { if (IsEmpty(L)) return ERROR; //检测线性表是否为空 if (i<1||i>L->length) return ERROR; //检查i值是否合理 *e=L->elem[i-1]; //将欲删除的数据元素内容保留在e所指示的存储单元中 for (int j=i;j<=L->length-1;j++) //将线性表第i+1个元素之后的所有元素向前移动 L->elem[j-1]=L->elem[j]; L->length--; return OK; } else { cout<<"Sqlist is not exsit!\n";exit(ERROR); }}//遍历顺序表方式visit()函数void print(ElemType e){ cout<<e<<" ";}//以visit()方式遍历顺序表void ListTraverse(SqList *L,void (*visit)(ElemType e)){ if(L->elem) { for(int i=0;i<L->length;i++) visit(L->elem[i]); cout<<endl; } else { cout<<"Sqlist is not exsit!\n";exit(ERROR); }}void ListCreate(SqList *L){ int n; cout<<"Number of elements:"; while(1) { cin>>n; if(n<=L->listsize)break; } for(int i=0;i<n;i++)cin>>L->elem[i]; L->length=n;}void ListUnion(SqList *LA,SqList *LB){ ElemType e; int LALen=ListLength(LA); int LBLen=ListLength(LB); for(int i=1;i<=LBLen;i++) { GetElem(LB,i,&e); if(!LocateElem(LA,e,equal)) ListInsert(LA,++LALen,e); }}int main(){ SqList *L=(SqList *)malloc(sizeof(SqList));//创建一个线性表 SqList *Lb=(SqList *)malloc(sizeof(SqList));//创建另一个线性表 ElemType e; //int a=5; InitList(L); InitList(Lb); //ListTraverse(L,print); //ListTraverse(Lb,print); ListCreate(L); ListCreate(Lb); ListTraverse(L,print); ListTraverse(Lb,print); ListUnion(L,Lb); ListTraverse(L,print); //cout<<ListLength(L); //for(int i=1;i<=10;i++) //ListInsert(L,i,i); //DestroyList(L); //ListTraverse(L,print); //LocateElem(L,9,equal); //printf("%d\n",(LocateElem(L,7,equal))); //ListDelete(L,LocateElem(L,7,equal),&e); //ListTraverse(L,print); //if(IsEmpty(L)) cout<<"Empty\n"; //else cout<<" Not Empty\n"; //ClearList(L); //ListCreate(L); //ListTraverse(L,print); //ListTraverse(L,print); //DestroyList(L); //if(IsEmpty(L)) cout<<"Empty\n"; //else cout<<" Not Empty\n"; //cout<<ListLength(L); //ListTraverse(L,print); return 0;}
数据结构之线性表
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。