【数据结构】单链表的基本运算实现


【数据结构】单链表的基本运算实现

关于数据结构中线性表的链接表示的基本运算的实现,把书上单链表的代码敲了一遍,加了些注释。

/*
  author:Ab4nd0n
  Time:2021-3-11
*/

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;

typedef struct node     //节点的结构体
{
    ElemType element;
    struct node *link;
}Node;

typedef struct singleList //单链表的结构体
{
    Node *first;  //first 头指针,用来存放头结点a0的地址
    int n;        //表示单链表中元素的个数
}SingleList;


//单链表的初始化
Status Init(SingleList *L)
{
    L->first=NULL;
    L->n=0;
    return OK;
}

//单链表的查找
/*
判断下标i是否越界 0~n-1
若未越界,则从头结点开始顺着单链表逐个结点查找
通过循环让p指向结点ai
将ai的值通过x返回(传值与传址,这边传进来的是地址,操作完会改变实参x的值)
*/
Status Find(SingleList *L,int i,ElemType *x)
{
    int j;
    Node *p;
    if(i<0||i>L->n-1)   return ERROR;
      
    p=L->first;          //p指向a0
    for(j=0;j<i;j++)
    {
        p=p->link;       //执行1次后p指向a1,反复指向下一个结点
    }
    *x=p->element;
    return OK;
}

//单链表的插入
/*
判断i是否越界 (-1~n-1)
查找ai,指针p指向此节点
生成一个新的结点q,将新结点的数据域置为x,指针q指向此结点
考虑i的取值:若i=-1,表明新结点q插在头结点a0之前,成为新的头结点
            若i>-1,将q所指向的结点插入p所指的结点之后(注意不要断链)
单链表元素个数+1
*/
Status Insert(SingleList  *L,int i,ElemType x)
{
    Node *p,*q;
    int j;
    if(i<-1||i>L->n-1)
    {
        return  ERROR;
    }
    p=L->first;          //p指向头指针
    for(j=0;j<i;j++)     //从头开始查找ai
    {
        p=p->link;
    }
    q=(Node*)malloc(sizeof(Node));      //生成新节点q
    q->element=x;

    if(i>-1)            //讨论i=-1和i>-1的情况
    {
        q->link=p->link;
        p->link=q;
    }
    else
    {
        q->link=L->first; //新节点插在头节点a0之前,成为新的头节点
        L->first=q;
    }
    L->n++;
    return OK;
}

//单链表的删除
/*
判断i是否越界(0~n-1)、单链表是否为空
查找元素ai的直接前驱ai-1,并令指针q指向它
考虑i的取值:若i=0,则从单链表中删除头结点
            若i>0,则使p指向ai所在的结点,并删除ai
释放p所指结点的存储空间
单链表元素个数-1
*/
Status Delete(SingleList *L,int i)
{
    int j;
    Node *p,*q;
    if(!L->n)  
      return ERROR;
    if(i<0||i>L->n-1)
      return ERROR;
    q=L->first;
    p=L->first;
    for(j=0;j<i-1;j++)
      q=q->link;
    if(i==0)
      L->first=L->first->link;    //删除的是头节点
    else
    {
        p=q->link;               //p指向ai
        q->link=p->link;          //ai+1的地址存到ai-1的指针域中
    }
    free(p);   //释放p所指结点的存储空间
    L->n--;
    return OK;

}

//单链表的输出
Status Output(SingleList *L)
{
    Node *p;
    if(!L->n)
        return ERROR;
    p=L->first;
    while(p)
    {
        printf("%d ",p->element);
        p=p->link;
    }
    printf("\n\n");
    return OK;
}

//单链表的销毁
void Destroy(SingleList *L)
{
    Node *p;
    while (L->first)
    {
        p=L->first->link;  //保存后继结点地址,防止断链
        free(L->first);   //释放first所指结点的存储空间
        L->first=p;
    }
}


int main()
{
    int i;
    int x;
    SingleList List;
    i=Init(&List);
    printf("%d\n\n",i);     // 1
    for(i=0;i<10;i++)
    {
        Insert(&List,i-1,i);
    }
    Output(&List);    //0 1 2 3 4 5 6 7 8 9
    Find(&List,1,&x);
    printf("The value is : %d\n\n",x);  //1
    Delete(&List,3);
    Output(&List);  //0 1 2 4 5 6 7 8 9
    Destroy(&List);

}



文章作者: Ab4nd0n
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Ab4nd0n !
评论
  目录