首页 > 代码库 > 数据结构之线性表

数据结构之线性表

对于线性表的线性存储结构,主要注意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;}

 

数据结构之线性表