LinkList.hLinkLlist.cppmain.cpp测试运行结果

LinkList.h

#pragma /*------------------------------------------------------------ // 链表结构的定义 ------------------------------------------------------------*/ typedef int ElemType; typedef struct _Node { ElemType data; // 元素数据 struct _Node* next; // 链表中结点元素的指针 }Node, * NodePtr; /*------------------------------------------------------------ // 链表的基本操作 ------------------------------------------------------------*/ void InitList(NodePtr head);//单链表初始化 void DestroyList(NodePtr head, ElemType * data);//销毁 bool IsListEmpty(NodePtr head);//判空 int ListLength(NodePtr head);//求链表长度 bool GetElem(NodePtr head, int pos,ElemType* data); //得到链表的第pos个元素 int LocateElem(NodePtr head, ElemType data);//得到链表指定元素的位置 Node* GetPosPrior(NodePtr head, int pos);//获得pos位置节点的前驱节点 Node* GetPosNext(NodePtr head, int pos);//获得pos位置节点的后继节点 void Show(NodePtr head); //打印单链表 bool ListInsert(NodePtr head, int pos, ElemType data);//在指定位置插入元素 void ListInsertHead(NodePtr head, ElemType data);//在链表的头部插入元素 void ListInsertTail(NodePtr head, ElemType data);//在链表的尾部插入元素 bool ListDeletePos(NodePtr head, int pos, ElemType* data);//删除指定位置的元素 void ListDeleteHead(NodePtr head, ElemType* data);//删除单链表的第一个元素 void ListDeleteTail(NodePtr head, ElemType* data);//删除单链表的最后一个元素 void ListDeleteData(NodePtr head, ElemType data);//删除与data相等数据的元素

LinkLlist.cpp

#include "LinkList.h" #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <memory.h> #include <assert.h> #define ERROR_JUDGEMENT assert(NULL != head);\ if (NULL == head)\ {\ printf("%s %d error\n", __FUNCTION__, __LINE__);\ exit(-1);\ } /*------------------------------------------------------------ 操作目的： 初始化单链表 初始条件： 单链表不存在 操作结果： 创建一个空的单链表 函数参数： NodePtr head 待初始化单链表的头节点 返回值： void 无返回值 ------------------------------------------------------------*/ void InitList(NodePtr head) { ERROR_JUDGEMENT head->next = NULL; head->data = 0; } /*------------------------------------------------------------ 操作目的： 销毁单链表 初始条件： 单链表head已存在 操作结果： 单链表不存在 函数参数： NodePtr head 待销毁的单链表头结点 返回值： void 无 ------------------------------------------------------------*/ void DestroyList(NodePtr head, ElemType* data) { ERROR_JUDGEMENT while (head->next) ListDeleteHead(head,data); } /*------------------------------------------------------------ 操作目的： 判断单链表是否为空 初始条件： 线性表head已存在 操作结果： 若单链表head为空表，则返回true，否则返回false 函数参数： NodePtr head 待判断的单链表 返回值： bool 返回 true 表示单链表为空 返回 false 表示单链表不为空 ------------------------------------------------------------*/ bool IsListEmpty(NodePtr head) { ERROR_JUDGEMENT return head->next == NULL ? true : false; } /*------------------------------------------------------------ 操作目的： 得到单链表的长度 初始条件： 单链表head已存在 操作结果： 返回L中数据元素的个数 函数参数： NodePtr head 单链表的head头节点 返回值： int 单链表数据元素的个数 ------------------------------------------------------------*/ int ListLength(NodePtr head) { ERROR_JUDGEMENT return head->data; } /*------------------------------------------------------------ 操作目的： 得到单链表的pos位置元素 初始条件： 单链表L已存在，1<=i<=ListLength(head) 操作结果： 返回查找到的元素 函数参数： NodePtr head 单链表的head头节点 int pos 数据元素的位置 ElemType *data 存储查找到的元素数据 返回值： bool 查找到返回为true 没有找到返回为false ------------------------------------------------------------*/ bool GetElem(NodePtr head, int pos,ElemType *data) { ERROR_JUDGEMENT Node* tmp = head->next; int j = 1; while (tmp && j < pos) { tmp = tmp->next; j++; } if (!tmp || j > pos) return false; else { *data = tmp->data; return true; } } /*------------------------------------------------------------ 操作目的： 得到单链表指定元素的位置 初始条件： 单链表head已存在 操作结果： 返回单链表中查找到的和指定 data 相等的元素的下标 若这样的元素不存在则返回0。 函数参数： NodePtr head 线性表head ElemType data 查找的元素 返回值： int 返回元素的位置 如果元素不存在则返回 0 ------------------------------------------------------------*/ int LocateElem(NodePtr head, ElemType data) { ERROR_JUDGEMENT Node* tmp = head -> next; unsigned count = 0; while (tmp) { count++; if (data == tmp->data) return count; else { tmp = tmp->next; } } return 0; } /*------------------------------------------------------------ 操作目的： 返回单链表中pos位置的前驱节点 初始条件： 单链表head已存在 操作结果： 返回单链表中pos位置的前驱节点的地址 函数参数： NodePtr head 线性表head int pos 链表位置 返回值： Node* 返回前驱节点的指针 ------------------------------------------------------------*/ Node* GetPosPrior(NodePtr head, int pos) { ERROR_JUDGEMENT if (pos<1 || pos>head->data) { printf("pos error"); exit(0); } Node* tmp =head; while (tmp && pos > 1) { tmp = tmp->next; pos--; } return tmp; } /*------------------------------------------------------------ 操作目的： 返回单链表中pos位置的后继节点 初始条件： 单链表head已存在 操作结果： 返回单链表中pos位置的后继节点的地址 函数参数： NodePtr head 线性表head int pos 链表位置 返回值： 返回pos位置的后继节点 ------------------------------------------------------------*/ Node* GetPosNext(NodePtr head, int pos) { ERROR_JUDGEMENT if (pos<1 || pos>head->data) { printf("pos error"); exit(0); } Node* tmp = head; while (tmp && pos > 0) { tmp = tmp->next; pos--; } return tmp->next; } /*------------------------------------------------------------ 操作目的： 打印单链表 初始条件： 单链表head已存在 操作结果： 依次打印链表中所有元素的数据域 函数参数： NodePtr head 线性表head 返回值： void ------------------------------------------------------------*/ void Show(NodePtr head) { ERROR_JUDGEMENT Node* tmp = head->next; while (tmp) { printf("%d\t", tmp->data); tmp = tmp->next; } printf("\n"); } /*------------------------------------------------------------ 操作目的： 在单链表的指定位置插入结点，插入位置i表示在第i个 元素之前插入 初始条件： 线性表head已存在，0<=i<=ListLength(head) 操作结果： 在head中第pos个位置插入新的数据元素data，head的长度加1 函数参数： NodePtr head 线性表head int pos 插入位置 ElemType data 待插入的数据元素 返回值： void ------------------------------------------------------------*/ bool ListInsert(NodePtr head, int pos, ElemType data) { ERROR_JUDGEMENT if (pos<1 || pos>head->data + 1) { printf("pos error"); exit(0); } NodePtr p = head; int j = 0; while (p && j < pos - 1) { p = p->next; ++j; } if (p && j > pos - 1) { return false; } NodePtr tmp = (NodePtr)malloc(sizeof(Node)); tmp->data = data; tmp->next = p->next; p->next = tmp; head->data++; return true; } /*------------------------------------------------------------ 操作目的： 在单链表的头部插入元素 初始条件： 单链表L已存在 操作结果： 在单链表的头部插入元素，head的长度加1 函数参数： NodePtr head 线性表head ElemType data 待插入的数据元素 返回值： bool 操作是否成功 ------------------------------------------------------------*/ void ListInsertHead(NodePtr head, ElemType data) { ERROR_JUDGEMENT ListInsert(head, 1, data); } /*------------------------------------------------------------ 操作目的： 在单链表的尾部位置插入节点 初始条件： 单链表head已存在 操作结果： 在L中尾部插入节点，head的长度加1 函数参数： NodePtr head 线性表head ElemType data 待插入的数据元素 返回值： 无 ------------------------------------------------------------*/ void ListInsertTail(NodePtr head, ElemType data) { ERROR_JUDGEMENT ListInsert(head, head->data + 1, data); } /*------------------------------------------------------------ 操作目的： 删除单链表的第i个结点 初始条件： 单链表存在 操作结果： 删除head的第i个数据元素 函数参数： NodePtr head 线性表head int pos 删除位置 返回值： 无返回值 ------------------------------------------------------------*/ bool ListDeletePos(NodePtr head, int pos,ElemType * data) { ERROR_JUDGEMENT if (pos<1 || pos>head->data) exit(0); NodePtr p = head, q; int j = 0; while (p->next && j < pos - 1) { p = p->next; ++j; } if (!(p->next) || j > pos - 1) return false; q = p->next; p->next = q->next; *data = q->data; free(q); head->data--; return true; } /*------------------------------------------------------------ 操作目的： 删除单链表的头节点 初始条件： 单链表head已存在且非空 操作结果： 删除head的头节点 函数参数： NodePtr head 线性表head 返回值： 无返回值 ------------------------------------------------------------*/ void ListDeleteHead(NodePtr head,ElemType *data) { ERROR_JUDGEMENT ListDeletePos(head, 1, data); } /*------------------------------------------------------------ 操作目的： 删除单链表的尾节点 初始条件： 单链表head已存在且非空 操作结果： 删除head的尾节点 函数参数： LinkList head 线性表head 返回值： 无返回值 ------------------------------------------------------------*/ void ListDeleteTail(NodePtr head, ElemType* data) { ERROR_JUDGEMENT ListDeletePos(head, head->data,data); } /*------------------------------------------------------------ 操作目的： 删除链表数据域为data的节点 初始条件： 线性表head已存在且非空 操作结果： 删除链表数据域为data的节点 函数参数： NodePtr head 线性表head ElemType data 被删除的数据元素值 返回值： 无返回值 ------------------------------------------------------------*/ void ListDeleteData(NodePtr head, ElemType data) //删除与data相等数据的元素 { ERROR_JUDGEMENT Node* tmp = head->next; int count = 1; while (tmp) { if (tmp->data == data) { Node* PosPrior = GetPosPrior(head, count); Node* PosNode = PosPrior->next; PosPrior->next = PosNode->next; free(PosNode); return; } else { tmp = tmp->next; count++; } } }

main.cpp

#include "LinkList.h" #include <stdio.h> int main() { Node Head; ElemType data = 0; int pos = 1; InitList(&Head);//初始化 for (int i = 1; i <= 10; i++)//调用头插法 { ListInsertHead(&Head, i * 10); } Show(&Head); data = 999; pos = 4; printf("在单链表的第%d位置插入数据:%d\n",pos, data); ListInsert(&Head, pos, data); Show(&Head); data = 666; printf("在单链表的尾部插入数据%d:\n", data); ListInsertTail(&Head,data); Show(&Head); data = 119; printf("在单链表的头部插入数据%d:\n", data); ListInsertHead(&Head, data); Show(&Head); pos = 4; printf("删除单链表的%d位置元素:\n",pos); ListDeletePos(&Head, pos, &data); Show(&Head); printf("删除单链表头部位置的元素:\n"); ListDeleteHead(&Head, &data); Show(&Head); printf("删除单链表头尾位置的元素:\n"); ListDeleteTail(&Head, &data); Show(&Head); printf("获得单链表长度:\n"); printf("%d\n", ListLength(&Head)); pos = 3; printf("%d\n", GetElem(&Head, pos, &data)); printf("获得单链表的第%d个位置的数据元素为%d\n",pos,data); data = 70; printf("数据元素%d所在的位置为%d\n", data, LocateElem(&Head, data)); pos = 7; printf("获得第%d个数据元素的前驱结点数据：\n",pos); Node* PosPrior = GetPosPrior(&Head, pos); printf("pos %d prior node data : %d\n", pos, (*PosPrior).data); pos = 7; printf("获得第%d个数据元素的后继结点数据：\n", pos); PosPrior = GetPosNext(&Head, pos); printf("pos %d next node data : %d\n", pos, (*PosPrior).data); if (IsListEmpty(&Head)) printf("单链表为空\n"); else printf("单链表不为空\n"); printf("销毁单链表\n"); DestroyList(&Head, &data); if (!Head.next) printf("单链表销毁成功"); return 0; }

测试运行结果