线性表-单链表c语言实现

一、基本介绍

        回顾单链表的知识

二、单链表

#include<stdio.h> 
#include<cstdlib>

typedef int ElemType;
typedef int Status; 

#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define NULL 0

// 定义单链表中结点类型 
typedef struct LNode{
    ElemType data;//数据域 
    struct LNode *next;//指针域 
}LNode,*LinkList;
 

 //查找单链表中第i个元素 
Status GetElem_L(LinkList L,int i,ElemType *e){
    LNode *p ;
    int j;
    p = L->next; j=1;
    //判断条件 p 相当于 p!=NUll 
    //顺时针查找 直到p找到第i个 或 p 为空 
    while(p && j<i){
        p = p ->next; ++j;//TODO
    }
    if(!p || j > i){
        return ERROR;// 第i个元素不存在 
    }
    *e = p->data;//取值
    return OK;         
}

//在带头结点的单链表L的第i个位置插入元素e 
Status ListInsert_L(LinkList L,int i,ElemType e){
    LNode *p, *s; 
    p=L; 
    int j=0;//p为指向单链表头指针，j为计数器 
    while(p && j < i-1){ //找到插入位置, i 结点的前驱 
        p = p->next;
        ++j;
    }
    if (!p || j > i-1) {
        return ERROR; //位置不合法 
    }
    s = (LinkList)malloc(sizeof(LNode));//创建一个新结点，LinkList相当于LNode* 
    if(!s) exit(OVERFLOW);                 //溢出错误，退出程序    
    s->data = e;                         //新结点赋值 
    s->next = p->next;                    //新结点插入单链表 
    p->next =s;                            
    return OK; 
} 

//单链表L中，删除第i个元素，并由e 返回其值
Status ListDelete_L(LinkList L,int i,ElemType *e){
    LNode *p,*q;//指向数据结点的指针
    int j;//j 计数器
    p=L;j=0;
    while(p->next && j<i-1){//找到删除元素的位置 ,条件p->next保证被删结点存在 
        p = p->next;
        ++j;
    }
    if(!(p->next) || j > i-1){//删除位置不合法 
        return ERROR;
    } 
    q = p->next; p->next = q->next;//q 指向被删除结点 
    *e = q->data; free(q); //释放q 所指向的内存空间 
    return OK;
}

//逆位序输入n个元素的值，建立单链表
void CreateList_L(LinkList L,int n){
    LNode *p;
    int i; //循环控制变量 

    printf("请逆位序输入%d个数据元素的值\n",n); 
    for (i=n;i>0;--i){
        p = (LinkList)malloc(sizeof(LNode));
        if (!p) exit(OVERFLOW);
        scanf("%d",&p->data);//数据域的首地址 
        p->next = L->next;//新结点p 指向单链表第一个数据结点 
        L->next = p;
    } 
}//CreateList_L

//单链表遍历操作
Status VisitList_L(LinkList L){
    LNode *p;//指向待访问数据结点的指针 
    if(!L->next) {
        printf("该单链表为空表");
        return ERROR; 
    }
    p= L->next;//p 指向单链表第一个数据结点 
    printf("单链表中数据结点为:");
    while(p){//条件 p为非空结点 
        printf("%d ->",p->data);
        p= p->next;
    }
    printf("NULL\n");
    return OK; 
} //VisitList_L

//清空单链表
void ClearList(LinkList L) {
    LNode *p;//指向待删除结点 
    while(L->next){//条件 L->next 保证单链表非空 
        p= L->next;//P 指向单链表第一个结点 
        L->next = p->next;// 逻辑删除p所指结点
        free(p);//释放p 
    }
}

三、测试

//函数声明  略

int main(){
     int n,i,j;
     ElemType e;
     LinkList L = (LinkList)malloc(sizeof(LNode));
     L->next =NULL;
     printf("请输入创建单链表中结点个数：");
    scanf("%d",&n); 
    CreateList_L(L,n);
    //测试遍历 
    VisitList_L(L);
    //测试取元素
    printf("请输入待取元素为序：");
    scanf("%d",&i); 
    if(GetElem_L(L,i,&e))
        printf("第%d个数据元素为%d\n",i,e);
    else
        printf("第%d个数据元素不存在！",i);
    //测试删除元素 
    printf("请输入删除元素的位序：");
    scanf("%d",&j);
    if(ListDelete_L(L,j, &e))
        printf("删除第%d个数据元素为%d",j,e);
    else 
        printf("删除失败"); 
    
    ClearList(L);
    free(L);
    return 0;
          
 }

四、心得

        eeeeeee
       函数ListDelete_L(LinkList L,int i,ElemType *e)，调用时ListDelete_L(L, i,&e)