首页 > 代码库 > 线性表

线性表

1、线性表的顺序存储

#include <stdio.h>
#include <malloc.h>
typedef int ElementType;
#define MAXSIZE 10

struct listStr
{
    int data[MAXSIZE];
    int last;
};
typedef struct listStr List;

List* makeEmptyTest();//初始化,建立空表
int findElementTest( ElementType X, List* ptrL);//查找元素X,返回对应数组下标
void insertElementTest(ElementType X, int i, List *ptrL);//在第i个位置(对应a[i-1])插入元素X
void deleteElementTest(int i,List *ptrL);//删除第i个元素,即a[i-1]
void printListTest(List* ptrL);




int main()
{
    List *ptrL=NULL;//表的长度L.last+1 or ptrL->last+1
    
    ptrL=makeEmptyTest();
    insertElementTest(1,1,ptrL);
    insertElementTest(2,2,ptrL);
    insertElementTest(3,3,ptrL);
    printListTest(ptrL);

    printf("findElementTest: %d\n",findElementTest(2,ptrL));
    deleteElementTest(1,ptrL);
    printListTest(ptrL);
}

List* makeEmptyTest()//初始化,建立空表
{
    List* ptrL=(List*)malloc(sizeof(List));
    ptrL->last = -1;//数组下标从0开始
    return ptrL;
}

int findElementTest( ElementType X, List* ptrL)//查找元素X,返回对应数组下标
{
    int i=0;
    while(i <= ptrL->last && ptrL->data[i] != X)
    {
        i++;
    }
    if(i>ptrL->last)
    {
        return -1;//没找到   
    }
    else
    {
        return i;
    }
}

void insertElementTest(ElementType X, int i, List *ptrL)//在第i个位置(对应a[i-1])插入元素X
{
    int j;
    if(ptrL->last == (MAXSIZE-1))
    {
        printf("list is full...\n");
        return;
    }
    if(i<1 || i>ptrL->last+2)
    {
        printf("location error...\n");
        return;
    }
    for(j=ptrL->last;j>=i-1;j--)//将a[last]一直到a[i-1]往后移动一位,空出a[i-1],即第i个位置
    {
        ptrL->data[j+1]=ptrL->data[j];
    }
    ptrL->data[i-1]=X;
    ptrL->last++;
    return;
}

void deleteElementTest(int i,List *ptrL)//删除第i个元素,即a[i-1]
{
    int j;
    if( i<1 || i>(ptrL->last+1) )
    {
        printf("not exist %d element...\n",i);
        return;
    }

    for(j=i;j<=ptrL->last;j++)
    {
        ptrL->data[j-1]=ptrL->data[j];
    }
    ptrL->last--;
    return;
}

void printListTest(List* ptrL)
{
    int j;
    for(j=0;j<=ptrL->last;j++)
    {
        printf("%d,",ptrL->data[j]);
    }
   return;
}

 

2、线性表的链式存储

#include <stdio.h>
#include <malloc.h>
typedef int ElementType;


typedef struct Node
{
    ElementType data;
    struct Node *next;
} List;

int lengthList(List *ptrL);
List* findKth( int K, List* ptrL);
List* findValue( int X, List* ptrL);
List* insertElementTest(ElementType X, int i, List *ptrL);
List* deleteElementTest(int i,List *ptrL);
void printListTest(List* ptrL);

int main()
{
    List *ptrL=NULL;
    ptrL=insertElementTest(1,1,ptrL);
    ptrL=insertElementTest(2,2,ptrL);
    ptrL=insertElementTest(3,3,ptrL);
    printListTest(ptrL);

    deleteElementTest(2,ptrL);
    printListTest(ptrL);
}

int lengthList(List *ptrL)
{
    List*pTmp=ptrL;
    int j=0;
    while(pTmp)
    {
        pTmp=pTmp->next;
        j++;
    }
    return j;
}

List* findKth( int K, List* ptrL)
{
    List *pTmp=ptrL;
    int i=1;
    while(pTmp!=NULL && i<K)
    {
        pTmp=pTmp->next;
        i++;
    }
    if(i==K)
    {
        return pTmp;
    }
    else
    {
        return NULL;
    }
}

List* findValue( int X, List* ptrL)
{
    List *pTmp=ptrL;
    while(pTmp!=NULL && pTmp->data!=X)
    {
        pTmp=pTmp->next;
    }
    return pTmp;
}


List* insertElementTest(ElementType X, int i, List *ptrL)
{
   List *p, *s;
   if(i==1)
   {
        s=(List*)malloc(sizeof(List));
        s->data=http://www.mamicode.com/X;
        s->next=ptrL;
        return s;
   }
   p=findKth(i-1,ptrL);
   if(p==NULL)
   {
    printf("i error...\n");
    return NULL;
   }
   else
   {
        s=(List*)malloc(sizeof(List));
        s->data=http://www.mamicode.com/X;
        s->next=p->next;
        p->next=s;
        return ptrL;
   }

}

List* deleteElementTest(int i,List *ptrL)
{
    List *p,*s;
    if(i==1)
    {
        s=ptrL;
        if(ptrL!=NULL)
        {
            ptrL=ptrL->next;
        }
        else
        {
            return NULL;
        }
        free(s);
        return ptrL;
    }
    else
    {
        p=findKth(i-1,ptrL);
        if(p==NULL)
        {
            printf("%d node not exist...\n",i-1);
            return NULL;
        }
        else if(p->next==NULL)
        {
            printf("%d node not exist...\n",i);
            return NULL;
        }
        else
        {
            s=p->next;
            p->next=s->next;
            free(s);
            return ptrL;
        }
    }
}

void printListTest(List* ptrL)
{
    List* pTmp;
    for(pTmp=ptrL;pTmp!=NULL;pTmp=pTmp->next)
    {
        printf("%d,",pTmp->data);
    }
   return;
}

 

线性表