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

——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.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_SQLIST_H__D5972AA1_A6AD_4DEB_8DCC_9520F1D0304A__INCLUDED_)
#define AFX_SQLIST_H__D5972AA1_A6AD_4DEB_8DCC_9520F1D0304A__INCLUDED_

#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;};


#endif // !defined(AFX_SQLIST_H__D5972AA1_A6AD_4DEB_8DCC_9520F1D0304A__INCLUDED_)

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;
}

赏

支付宝打赏

微信打赏

您的打赏是对我最大的鼓励！

Array based list

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

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

CATALOG

FEATURED TAGS

FRIENDS