[数据结构与算法]数据结构与算法（C语言）代码实现-线性表的相关操作代码实现（单链表）

c语言代码实现

C语言实现 线性表（单链表）的相关操作，实现了如下方法：

• 初始化单链表
  InitLinkList(LinkList &L);
• 销毁单链表
  DestroyLinkList(LinkList &L);
• 清空单链表
  ClearLinkList(LinkList &L);
• 在单链表指定位置插入元素
  LinkListInsert(LinkList &L, int i, ElemType e);
• 单链表头插法
  LinkListInsert_h(LinkList &L, ElemType e);
• 单链表尾插法
  LinkListInsert_r(LinkList &L, ElemType e);
• 获取单链表的长度
  LinkListLength(LinkList L);
• 在单链表中查找指定元素所在的位置
  LocateElem(LinkList L, ElemType e);
• 在单链表中查找指定元素是否存在，存在就把该节点作为函数返回值返回
  LocateElem_(LinkList L, ElemType e);
• 在单链表中获取指定位置的元素
  GetElem(LinkList L, int i, ElemType &e);
• 判断单链表是否为空
  IsEmpty(LinkList L);
• 删除单链表指定位置的元素
  LinkListDelete(LinkList &L, int i, ElemType &e);

写的匆忙，如有错误，请大家指正一下。

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

//###一些常量
//函数结果状态码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//单链表最大容量
#define MAXSIZE 100


//函数类型
typedef int Status;
//单链表的元素类型
typedef char ElemType;


//定义单链表的结构体
typedef struct node{
    //链表的数据域
    ElemType data;
    //链表的指针域
    struct node *next;
}LinkListNode, *LinkList;

//---------------------------------------------------------------
//初始化单链表
Status InitLinkList(LinkList &L);
//销毁单链表
void DestroyLinkList(LinkList &L);
//清空单链表
void ClearLinkList(LinkList &L);
//在单链表指定位置插入元素
Status LinkListInsert(LinkList &L, int i, ElemType e);
//单链表头插法
Status LinkListInsert_h(LinkList &L, ElemType e);
//单链表尾插法
Status LinkListInsert_r(LinkList &L, ElemType e);
//获取单链表的长度
int LinkListLength(LinkList L);
//在单链表中查找指定元素所在的位置
int LocateElem(LinkList L, ElemType e);
//在单链表中查找指定元素是否存在，存在就把该节点作为函数返回值返回
LinkListNode* LocateElem_(LinkList L, ElemType e);
//在单链表中获取指定位置的元素
Status GetElem(LinkList L, int i, ElemType &e);
//判断单链表是否为空
Status IsEmpty(LinkList L);
//删除单链表指定位置的元素
Status LinkListDelete(LinkList &L, int i, ElemType &e);
//---------------------------------------------------------------
int main(){
    /**
    * 对线性表的相关操作进行测试
    */
    //定义一个链表
    LinkList list;
    //初始化顺序表
    InitLinkList(list);
    //将元素插入到线性表中
    ElemType e1 = 'a';
    ElemType e2 = 'b';
    ElemType e3 = 'c';
    ElemType e4 = 'd';
    ElemType e5 = 'e';
    LinkListInsert(list, 1, e1);
    LinkListInsert(list, 2, e2);
    LinkListInsert(list, 3, e3);
    LinkListInsert(list, 4, e4);
    LinkListInsert(list, 5, e5);
    //打印线性表的元素，打印结果：a	b	c	d	e
    for(int i = 0; i < LinkListLength(list); i++){
        ElemType e;
        GetElem(list, i+1, e);
        printf("%c\t", e);
    }
    //查看线性表是否为空
    Status s = IsEmpty(list);
    printf("\n是否为空线性表：%d\n", s);//0
    //查看线性表的长度
    int length = LinkListLength(list);//返回
    printf("线性表的长度：%d\n", length);//5
    //删除一个元素
    ElemType e6;
    LinkListDelete(list, 2, e6);
    printf("被删除的元素：%c\n", e6);//b
    //打印线性表的元素，打印结果：a	c	d	e
    for(int i = 0; i < LinkListLength(list); i++){
        ElemType e;
        GetElem(list, i+1, e);
        printf("%c\t", e);
    }
    printf("\n");
    //查找元素c所在的序号
    ElemType c = 'c';
    int index = LocateElem(list, c);
    printf("元素c所在的序号是：%d\n", index);//2
    //头插法和尾插法
    ElemType e7 = '7';
    ElemType e8 = '8';
    LinkListInsert_h(list, e7);
    LinkListInsert_r(list, e8);
    //打印线性表的元素，打印结果：7	a	c	d	e	8
    for(int i = 0; i < LinkListLength(list); i++){
        ElemType e;
        GetElem(list, i+1, e);
        printf("%c\t", e);
    }
    printf("\n");
    //查找元素c所在的结点
    ElemType e9 = 'c';
    LinkListNode *locateNode = LocateElem_(list, e9);
    printf("查找到的结点的数据域：%c，下一个结点的地址：%p\n", locateNode->data, locateNode->next);//c
    //清空线性表
    ClearLinkList(list);
    //查看线性表是否为空
    s = IsEmpty(list);
    printf("是否为空线性表：%d\n", s);//1
    //销毁线性表
    DestroyLinkList(list);
    return 0;
}

/**
 * 初始化单链表，将L指向头结点，并将头结点的next指针域设置为空
 * @param L 单链表
 * @return
 */
Status InitLinkList(LinkList &L){
    //C语言写法，创建一个头结点，L指向这个头结点
    //L = (LinkList)malloc(sizeof(LinkListNode));
    // c++写法
    L = new LinkListNode;
    //判断是否创建头结点成功
    if (!L){
        printf("单链表初始化失败！");
        return OVERFLOW;
    }
    //初始化头结点，指针域设置为空
    L->next = NULL;
    return OK;
}
/**
 * 判断单链表是否为空，如果单链表的头结点的next指针域为空，说明单链表为空
 * @param L 单链表
 * @return
 */
Status IsEmpty(LinkList L){
    //三目运算符
    return L->next? FALSE: TRUE;
}
/**
 * 销毁单链表，从头结点开始，依次销毁每个结点
 * @param L
 */
void DestroyLinkList(LinkList &L){
    for(LinkListNode *p = L; p; p = L->next){
        //记录当前结点指向的下一节点
        L = p->next;
        //销毁当前结点
        delete p;
        //p指向下一节点
    }
}
/**
 * 清空单链表，头结点的next指针域设为空，后面的元素都进行销毁
 * @param L
 */
void ClearLinkList(LinkList &L){
    //方法一：
    //把头结点的next指针传入DestroyLinkList函数进行销毁
    DestroyLinkList(L->next);


    //方法二：
    //从首元节点开始，每个结点都进行销毁
    LinkListNode *p1 = L->next, *p2;
    //p1为空，说明没有要删除的元素了，退出循环
    while(p1){
        //p1指向当前要删除的结点，p2指向当前节点的下一个结点
        p2 = p1->next;
        //销毁当前元素
        delete p1;
        //p1指向下一个要删除的元素，即p2
        p1 = p2;
    }
    //将头结点的next指针域设置为空
    L->next = NULL;
}
/**
 * 获取单链表的长度
 * @param L 单链表
 * @return
 */
int LinkListLength(LinkList L){
    int count = 0;
    //从首元节点开始计算
    //循环计数
    for(LinkListNode *p = L->next; p; (p = p->next), count++);
    return count;
}
/**
 * 获取单链表中指定位置的元素
 * @param L 单链表
 * @param i 第几个位置
 * @param e 用来接收找到的元素
 * @return
 */
Status GetElem(LinkList L, int i, ElemType &e){
    LinkListNode *p = L;
    for(int k = 1; k <= i && p; k++){
        //指向下一个结点
        p = p->next;
        //不是要找的位置，跳过本次循环
        if (k != i) continue;
        //已经到第i个了，将e指向这个结点
        e = p->data;
        return OK;
    }
    //没有找到
    return ERROR;
}
/**
 * 在单链表中查找指定元素所在的位置
 * @param L 单链表
 * @param e 要查找的元素
 * @return
 */
int LocateElem(LinkList L, ElemType e){
    //指向首元节点
    LinkListNode *p = L->next;
    for(int i = 1; p; i++){
        //找到相同的元素，返回位置
        if(p->data == e) return i;
        //指向下一个元素
        p = p->next;
    }
    //没有找到
    return 0;
}
/**
 * 在单链表中查找指定元素是否存在，存在就把该节点返回
 * @param L 单链表
 * @param e 要查找的元素
 * @return
 */
LinkListNode* LocateElem_(LinkList L, ElemType e){
    //指向首元节点
    LinkListNode *p = L->next;
    while(p){
        //找到相同的元素，返回该结点
        if(p->data == e) return p;
        //指向下一个元素
        p = p->next;
    }
    //没有找到，返回空
    return NULL;
}
/**
 *在单链表的指定位置插入元素
 * @param L 单链表
 * @param i 位置
 * @param e 要插入的元素
 * @return
 */
Status LinkListInsert(LinkList &L, int i, ElemType e){
    LinkListNode *p = L;
    //p为空时结束循环
    for(int k = 1; k <= i && p; k++, p = p->next){
        //没到指定位置，跳过本次循环
        if(k != i) continue;
        //进行插入相关操作
        //新建一个结点
        LinkListNode *newNode = (LinkListNode*)malloc(sizeof(LinkListNode));
        //把元素放入新建的结点的数据域中
        newNode->data = e;
        //插入，新结点的next指针域指向当前结点的next指针域
        newNode->next = p->next;
        //当前结点的next指针域指向新结点，完成插入
        p->next = newNode;
        //插入完成
        return OK;
    }
    //插入失败
    printf("插入失败！\n");
    return ERROR;
}
/**
 * 删除单链表指定位置的元素
 * @param L 单链表
 * @param i 要删除的位置
 * @param e 接收删除的节点的元素
 * @return
 */
Status LinkListDelete(LinkList &L, int i, ElemType &e){
    //指向首元节点
    LinkListNode *p = L->next;
    //计算出删除元素的前一个元素的位置
    int deletePreIndex = i - 1;
    for(int k = 1; k <= deletePreIndex; k++, p = p->next){
        //没有到指定位置，跳过本次循环
        if(k != deletePreIndex) continue;
        //删除相关操作
        //把e指向要删除的结点的元素
        e = p->next->data;
        //记录要删除的结点
        LinkListNode *delNode = p->next;
        //把当前结点指向下一节点(要删除的结点)的下一节点，完成删除
        p->next = delNode->next;
        //销毁要删除的结点
        delete delNode;
        //完成删除
        return OK;
    }
    //没有删除
    return ERROR;
}
/**
 * 在单链表的头结点后插入一个元素
 * @param L 单链表
 * @param e 要插入的元素
 * @return
 */
Status LinkListInsert_h(LinkList &L, ElemType e){
    //创建一个新结点，并将数据域指向e
    LinkListNode *newNode = new LinkListNode;
    newNode->data = e;

    //将新结点的next指针域指向头结点的next
    newNode->next = L->next;
    //将头结点的next指针域指向新结点，完成插入
    L->next = newNode;
    return OK;

}
/**
 * 在单链表的最后一个结点插入元素
 * @param L 单链表
 * @param e 要插入的元素
 * @return
 */
Status LinkListInsert_r(LinkList &L, ElemType e){
    //将p指向单链表最后一个结点
    LinkListNode *p = L;
    for(; p->next; p = p->next);
    //创建一个新结点，并将数据域指向e，指针域设置为空
    LinkListNode *newNode = new LinkListNode;
    newNode->data = e;
    newNode->next = NULL;
    //最后一个结点的指针域指向新结点，完成插入
    p->next = newNode;
    return OK;
}