# 数据结构-线性表的顺序实现(顺序表)

## Array based list

Posted by xuepro on November 9, 2017

## ——C版本的顺序表实现————

#include <stdio.h>

#include <malloc.h>

#define OK 0

#define ERROR 1

typedef int EType;

typedef struct{
EType *data;
int capacity,n;
}SqList;

int initSqList(SqList *L,int cap){
L->data = (EType *)malloc(cap*sizeof(EType));
if(!L->data) return ERROR;
L->capacity = cap;
L->n = 0 ;
return OK;
}

int insertSqList(SqList *L,int i,EType e){
EType *p,*q;
if(i<1 || i>L->n+1) return ERROR;
if(L->n == L->capacity){
EType *p = realloc(L->data, 2*L->capacity*sizeof(EType));
if(!p) return ERROR;
free(L->data);
L->data = p;
}
//[i,n]后移
q = &(L->data[i-1]);
p = &(L->data[L->n-1]);
for(;p>=q;p--)
*(p+1) = *p;
*q = e;
L->n++;
return OK;
}

int deleteSqList(SqList *L,int i){
EType *p,*q;
if(i<1 || i>L->n) return ERROR;
//[i,n]后移
p = &(L->data[i]);
q = &(L->data[L->n-1]);
for(;p<=q;p++)
*(p-1) = *p;
L->n--;
return OK;
}

int getSqList(SqList L,int i,EType *e){
if(i<1 || i>L.n) return ERROR;
*e = L.data[i-1];
return OK;
}
int setSqList(SqList *L,int i,EType e){
if(i<1 || i>L->n) return ERROR;
L->data[i-1] = e;
return OK;
}

int sizeSqList(SqList L){
return L.n;
}

int push_back(SqList *L,EType e){
if(L->n == L->capacity){
printf("apply for more memory!\n ");
EType *p = realloc(L->data, 2*L->capacity*sizeof(EType));
if(!p) return ERROR;
free(L->data);
L->data = p;
}

L->data[L->n] = e;
L->n++;
return OK;
}

int main(){
SqList list;
EType e;
initSqList(&list,10);
for(int i = 0; i<11; i++)
push_back(&list,i+1);

for(int i = 1 ;i<=list.n;i++){
getSqList(list,i,&e);
printf("%d\t",e);
}
printf("\n");

insertSqList(&list,2,20);
deleteSqList(&list,4);

for(int i = 1 ;i<=list.n;i++){
getSqList(list,i,&e);
printf("%d\t",e);
}
printf("\n");
}


## ——C++(引用)版本的顺序表实现————

SqList.h

// SqList.h: interface for the SqList class.
//
//////////////////////////////////////////////////////////////////////

#include <string>
using std::string;

#define LIST_INIT_SIZE 100
#define LISTINCREMENT  10
#define OVERFLOW 1
#define ERROR 2
#define OK 0
typedef int Status;

//typedef double ElemType;

struct student{
string name;
double score;
};
typedef student ElemType;

struct SqList{
ElemType *elem;
int length;
int listsize;
};

int InitList(SqList &L);
int ListInsert(SqList& L, int i, ElemType e);
int ListGet(const SqList L, int i, ElemType &e);
int ListSet(SqList& L, int i, ElemType e);
void DestoryList(SqList& L);
//int ListLength(SqList L){return L.length;};



SqList.cpp

// SqList.cpp: implementation of the SqList class.
//
//////////////////////////////////////////////////////////////////////

#include "SqList.h"
#include <malloc.h>

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
//void exit(int r){}

int InitList(SqList &L){
/*  L.elem = (ElemType*)malloc
(LIST_INIT_SIZE*
sizeof(ElemType));*/
L.elem = new ElemType[LIST_INIT_SIZE];
if(!L.elem) return 1;
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return 0;
}

int ListInsert(SqList &L, int i, ElemType e)
{
// 判断i是否合法
if(i < 1 || i > L.length + 1)
return ERROR;
// 若线性表空间不足，再分配一些空间
if(L.length >= L.listsize)
{
ElemType *newbase = new ElemType[L.listsize+LISTINCREMENT];
if(!newbase)    exit(OVERFLOW);
for(int i = 0;i<L.length;i++){
newbase[i] = L.elem[i];
}
delete[] L.elem;
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
/*
// q指向插入的位置
ElemType *q = &(L.elem[i-1]);
// p指向最后一个元素，
// 从p到q的所有元素后移一个单元
for(ElemType *p = &(L.elem[L.length - 1]);
p >= q; --p)
*(p+1) = *p;
*q = e;         // 写进待插入的元素e
*/
for(int j = L.length;j>=i)
++ L.length;    // 表长加1
return OK;
}

int ListGet(const SqList L, int i, ElemType &e){
if(i < 1 || i > L.length)
return ERROR;
e=L.elem[i-1];
return OK;
}
int ListSet(SqList& L, int i, ElemType e){
if(i < 1 || i > L.length)
return ERROR;
L.elem[i-1]=e;
return OK;
}

void DestoryList(SqList& L){
delete[] L.elem;
L.elem = 0;
L.listsize = 0;
}


main.cpp

#include "SqList.h"
#include <iostream>
using std::cout;

int main(){
SqList L;
InitList(L);
ElemType e;

e.name  = "Li"; e.score = 77;
ListInsert(L,1,e);

e.name  = "Wang"; e.score = 87;
ListInsert(L,2,e);

e.name  = "Zhang"; e.score = 27;
ListInsert(L,3,e);

e.name  = "KKKKK";
ListSet(L,2,e);

for(int i = 1;i<=L.length;i++){
ListGet(L,i,e);
cout<<e.name<<" "<<e.score<<"\n";
}
cout<<"\n";

DestoryList(L);
return 0;
}