0%

顺序表和单链表的使用

线性表的基本操作与使用

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 150             //定义顺序链表储存信息的最大值
typedef char ElementType;   //定义char为ElemenType方便改变需要储存的类型
typedef struct NodeOL       //定义NodeOL结构体
{
    ElementType data[MAX];  //定义结构体内储存信息类型
    int last;               //记录链表长度
} OList;                    //将struck NodeOL结构体定义为OList
typedef struct NodeL
{
    ElementType data;
    struct NodeL *next;
} List;
OList *OL;
List  *L;

/*建立顺序表开始*/

/*建立顺序表储存信息
/*数序表是链式结构
/*完成顺序表的基本操作*/

/*初始化顺序表*/
OList *MakeOList()
{

    OList *p;
    p=(OList *)malloc(sizeof(OList));   //为节点分配空间大小
    p->last=0;                          //初始化链表长度
    return p;
}
/*查找元素位置*/
int FindOL(char X,OList *OL)
{

    int i=0;
    while(OL->data[i]!=X)
    {
        i++;
        if(i>OL->last)
            return -1;
    }
    return i;
}
/*插入*/
OList *InsertOL(int n,ElementType X,OList *OL)      //输入想要插入的位置、内容和被插入的链表指针
{
    int i;
    if(OL->last==MAX-1)                             //做出必要的判断。判断是否已经栈满
    {
        printf("顺序表已满,请勿添加!\n");
        return NULL;
    }

    if(n<1||n>OL->last+2)                           //做出必要的判断。判断输入位置是否正确
    {
        printf("非法位置!\n");
        return NULL;
    }

    for( i=OL->last; i>=n-1; i-- )                  //循环改变顺序链表信息内容位置
    {
        OL->data[i+1]=OL->data[i];                  //特别注意此处一定为data[i+1]=data[i]
    }                                               //如果改成data[i]=data[i++]
    //否则将会出现所有改变的信息全部都变成了data[i]
    OL->data[n-1]=X;
    OL->last++;
    return OL;

}

/*删除*/
OList *DeleteOL(int n,OList *OL)
{

    int i;
    if(OL->last==0)                                 //做出必要的判断。判断输入位置是否正确
    {
        printf("顺序表为空!请重试!\n");
        return 0;
    }

    if(n<1||n>OL->last)                             //做出必要的判断。判断输入位置是否正确
    {
        printf("非法位置,请重试!\n");
        return NULL;
    }
    for(i=n-1; i<OL->last ; i++)
    {
        OL->data[i]=OL->data[i+1];                  //注意data[i]=data[i+1] 不可写成data[i+1]=data[i]
    }
    OL->last--;                                     //顺序表长度减一
    return OL;

}
/*逆转*/
OList *ReOList(OList *OL)
{

    char  a[MAX];
    int i=0;
    int temp=OL->last-1;
    for(; i<OL->last ; i++)
    {
        a[temp--]=OL->data[i];
    }
    for(i=0; i<OL->last ; i++)
    {
        OL->data[i]=a[i];
    }
    return OL;

}

/*输出*/
void PutOL(OList *OL)
{

    int i=0;
    for(; i<OL->last; i++)
        printf("%c ",OL->data[i]);
    printf("\n");
}
/*销毁*/
OList *DestoryOL(OList *OL)
{
    free(OL);
    return NULL;
}
/*置空表*/
OList *MakeEmptyOL(OList *OL)
{
    int i=OL->last;
    for(; i>=0 ; i--)
    {

        OL->data[i]='\0';

    }
    OL->last=0;

    return OL;
}
/*求表长*/
int LengthOL(OList *OL)
{
    return OL->last;
}

/*查找元素内容*/
ElementType FindOLCon(int n,OList *OL)
{
    if(n<1||n-1>OL->last)                           //做出必要的判断。判断输入位置是否正确
    {
        printf("非法位置,请重试!~\n");
    }
    return OL->data[n];
}
/*判线性表是否为空*/
int  is_EmptyListOL(OList *OL)
{

    if(OL==NULL)                                    //做出必要的判断。判断输入位置是否正确
    {
        printf("不存在的线性表,请重试!\n");
    }
    if(OL->last==0)
        return 0;
    else
        return 1;

}

/*单链表开始*/
/*建立链表*/
List *MakeList()                                //建立头结点
{
    List *p;
    p=(List *)malloc(sizeof(List));             //分配结点资源
    p->next=NULL;
    p->data='\0';
    return p;
}
/*查找*/
/*整数查找*/
List *FindKth(int n, List *PtrL)                //因为有头结点可以简化下标和位置不同步的问题
{
    List *p=PtrL;
    List *s=p;
    int i=0;
    while(i<n && p!=NULL)                       //搜索结点
    {
        i++;
        p=p->next;
        if(p!=NULL)
        {
            s=p;
        }

    }
    if(i==n)
    {
        //     printf("%d\n",s);
        return s;
    }
    else
    {
        return NULL;
    }
}
/*字符查找*/
List *Find(char X, List *PtrL)
{
    List *p=PtrL;
    while(p!=NULL && p->data!=X)
    {
        p=p->next;
    }
    return p;
}
/*插入*/
List *Insert(int n,char X,List *PtrL)
{

    List *s,*p;
    p=FindKth(n-1,PtrL);
    if(p==NULL)
    {
        printf("参数存在错误!\n");                          //做出必要的判断。判断输入位置是否正确
        return NULL;
    }
    else
    {
        s=(List *)malloc(sizeof(List));                     //分配节点资源
        s->data=X;
        s->next=p->next;
        p->next=s;
        return PtrL;

    }

}
/*删除*/
List *Delect(int i,List *PtrL)
{
    List *s,*p;
    p = FindKth( i-1, PtrL );                                  /*查找第i-1个结点*/
    if ( p == NULL )
    {
        printf("第%d个结点不存在", i-1);
        return NULL;
    }
    else if ( p->next == NULL )
    {
        printf("第%d个结点不存在", i);
        return NULL;
    }
    else
    {
        s = p->next;                                         /*s指向第i个结点*/
        p->next = s->next;                                   /*从链表中删除*/
        free(s);                                             /*释放被删除结点 */
        return PtrL;

    }
}

/*输出*/
void PutList(List *POL)
{
    List *p=POL;
    int i=1;
    p=p->next;
    while(p!=NULL)
    {
        printf("%c ",p->data);
        p=p->next;
    }
    printf("\n");

}

/*其它基本操作*/
/*销毁链表*/
List *Destory(List *POL)
{
    List *p;
    if(POL!=NULL)
    {
        p=POL;
        POL=POL->next;
        free(p);
    }
    return NULL;
}

/*将链表置为空表*/
List *MakeEmpty(List *POL)
{
    List *p=POL->next;
    List *s=p;
    while(p!=NULL)
    {
        p=p->next;
        free(s);
        s=p;
    }
    return POL;
}

/*求链表的长度*/
int  Length(List *POL)
{
    List *p=POL;
    if(POL==NULL)
    {
        printf("不存在的链表!\n");                    //做出必要的判断。判断输入位置是否正确
        return NULL;
    }
    int i=0;
    while(p!=NULL)
    {
        p=p->next;
        i++;
        //  printf("1\n");
    }
    return i-1;
}
/*获取某位置结点的内容*/
ElementType *FindKthCon(int n, List *PtrL)
{
    List *p=PtrL;
    int i;
    for(i=0 ; i <=n ; i++)
    {
        if(p!=NULL)
        {
            p=p->next;
        }
        else
        {
            return NULL;
        }
    }

    return p->data;
}
/*搜索结点*/
List *FindKthNode(int n, List *PtrL)
{
    List *p=PtrL;
    int i;
    for(i=0 ; i <=n ; i++)
    {
        if(p!=NULL)
        {
            p=p->next;
        }
        else
        {
            return NULL;
        }
    }

    return p;
}

/*扩展实验内容*/
/*查前驱元素*/
/*单向链表字符查找*/
List *FindLast(char X, List *PtrL)                      //查找上一节点的指针,返回指针地址
{
    List *p=PtrL;
    List *s=NULL;
    while(p!=NULL && p->data!=X)
    {
        s=p;
        p=p->next;
    }
    return s;
}
/*单向链表位置查找*/
List *FindLastKth(int n, List *PtrL)
{
    List *p=PtrL;
    p=FindKth(n-1,p);
    return p;
}
/*查后继元素*/
/*单向链表字符查找*/
List *FindNext(char X, List *PtrL)                      //查找下一节点的指针,返回指针地址
{
    List *p=PtrL;
    List *s=PtrL->next;
    while(p!=NULL && p->data!=X)
    {
        p=p->next;
        s=p->next;
    }
    return s;
}
/*单向链表位置查找*/
List *FindNextKth(int n, List *PtrL)
{
    List *p=PtrL;
    p=FindKth(n+1,p);
    return p;
}

/*顺序表合并*/
List *JoinOL(OList *p1,OList *p2)
{

    int len1,len2;
    int i;
    len1=LengthOL(p1);
    len2=LengthOL(p2);
    if(len1+len2>MAX)
    {
        printf("长度超出顺序表上线!");
        return NULL;

    }
    else
    {

        p1->last=len1+len2;
        for(i=0; i<len2 ; i++)
        {
            p1->data[len1+i]=p2->data[i];
        }

    }

    return p1;
}

/*两个有序单链表的合并操作*/

List *Join(List *p1,List *p2)
{
    List *p=p1;
    List *s=p1;
    while(p1!=NULL)
    {
        p=p1;
        p1=p1->next;
    }
    p->next=p2->next;

    return s;
}

/*单链表结束*/

int main()
{
    OList *OL1;
    OList *OL2;
    List  *L1;
    List  *L2;
    ElementType X;
    int n;
    int len;
    //测试顺序链表
    OL1=MakeOList();
    OL2=MakeOList();
    OL1=InsertOL(1,'a',OL1);
    OL1=InsertOL(2,'b',OL1);
    OL1=InsertOL(3,'c',OL1);
    OL1=InsertOL(4,'d',OL1);
    OL1=InsertOL(5,'e',OL1);
    OL2=InsertOL(1,'f',OL2);
    OL2=InsertOL(2,'g',OL2);
    OL2=InsertOL(3,'h',OL2);
    OL2=InsertOL(4,'i',OL2);
    OL2=InsertOL(5,'j',OL2);
    PutOL(OL1);
    PutOL(OL2);
    OL1=JoinOL(OL1,OL2);
    PutOL(OL1);
    OL1=ReOList(OL1);
    PutOL(OL1);
    n=FindOL('a',OL1);
    printf("n=%d\n",n);
    X=FindOLCon(9,OL1);
    printf("X=%c\n",X);
    len=LengthOL(OL1);
    printf("OLen=%d\n",len);
    DeleteOL(1,OL1);
    PutOL(OL1);
    MakeEmptyOL(OL2);
    if(is_EmptyListOL(OL2))
    {
        printf("此链表已经为空!\n");
    }
    else
    {
        printf("此链表未被置空!\n");
    }
    OL2=DestoryOL(OL2);
    if(OL2)
    {
        printf("此链表仍然存在!\n");
    }
    else
    {
        printf("此链表不存在!\n");
    }

    //测试单向链表
    L1=MakeList();
    L2=MakeList();
    L1=Insert(1,'a',L1);
    L1=Insert(2,'b',L1);
    L1=Insert(3,'c',L1);
    L1=Insert(4,'d',L1);
    L1=Insert(5,'e',L1);
    L2=Insert(1,'f',L2);
    L2=Insert(2,'g',L2);
    L2=Insert(3,'h',L2);
    L2=Insert(4,'i',L2);
    L2=Insert(5,'j',L2);
    PutList(L1);
    PutList(L2);
    L1=Join(L1,L2);
    PutList(L1);
    L2=FindKth(1,L1);
    printf("X=%c\n",L2->data);
    L1=Delect(1,L1);
    PutList(L1);
    len=Length(L1);
    printf("ListLen=%d\n",len);

    return 0;
}