天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

线性表基本操作

Posted on 2012-08-21 16:25 hoshelly 阅读(357) 评论(0)  编辑 收藏 引用 所属分类: DS && Algorithm
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int ElemType;
typedef int Status;
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) exit(OVERFLOW);
    (*L).length=0;
    (*L).listsize=LIST_INIT_SIZE;
    return OK;
}
int ListLength(SqList L)
{
    return L.length;
}

Status ListEmpty(SqList L)
{
    if(L.length == 0)
        return OK;
    else
        return ERROR;
}

Status ClearList(SqList *L)
{
    (*L).length=0;
    return OK;
}

Status DestroyList(SqList *L)
{
    free((*L).elem);
    (*L).elem=NULL;
    (*L).length=0;
    (*L).listsize=0;
    return OK;
}

Status GetElem(SqList L,int i,ElemType *e)
{
    if(i<1 || i>L.length)
        exit(ERROR);
    *e=*(L.elem+i-1);
    return OK;
}

Status ListInsert(SqList *L,int i,ElemType e)
{
    ElemType *newbase,*p,*q;
    if(i<1 || i>(*L).length+1)
        return ERROR;
    if((*L).length >= (*L).listsize)
    {
        newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
        if(!newbase) exit(OVERFLOW);
        (*L).elem=newbase;
        (*L).listsize +=LISTINCREMENT;
    }
    q=(*L).elem+i-1; //插入位置
    for(p=(*L).elem+(*L).length-1;p>=q;--p)
        *(p+1)=*p;
    *q=e;
    ++(*L).length;
    return OK;
}

Status Visit(ElemType *c)
{
    printf("%d ",*c);
    return OK;
}

Status ListTraverse(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        Visit(L.elem+i);
    printf("\n");
    return OK;
}

int LocateElem(SqList L,ElemType e)
{
    int i;
    for(i=0;i<L.length;i++)
    {
        if(*(L.elem+i) == e)
            break;
    }
    if(i>=L.length)
        return 0;
    return i+1;
}

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int k;
    if(L->length == 0)
        return ERROR;
    if(i<1 || i>=L->length)
        return ERROR;
    *e=*(L->elem+i-1);
    if(i<L->length)
    {
        for(k=i;k<L->length;k++)
            *(L->elem+k-1)=*(L->elem+k);
    }
    L->length--;
    return OK;
}

int main()
{
    int i,e;
    SqList mylist;
    int m = InitList_Sq(&mylist);
    if(m)
    {
        printf("线性表创建成功!\n");
        printf("当前表长: %d \n",ListLength(mylist));
    }
    else
        printf("线性表创建失败.");
    for(i=1;i<=10;i++)
        ListInsert(&mylist,i,i);
    ListTraverse(mylist);
    printf("当前表长:%d \n",ListLength(mylist));
    GetElem(mylist,5,&e);
    printf("第5个元素为:%d\n",e);
    ListDelete(&mylist,4,&e);
    printf("删除第4个元素后:");
    ListTraverse(mylist);
    printf("当前表长:%d \n",ListLength(mylist));
    i=ClearList(&mylist);
    printf("清空线性表后:表长为 %d\n",mylist.length);
    i=ListEmpty(mylist);
    printf("表是否为空:%d (1:空 0:否)\n",i);


    return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理