本文共 6667 字，大约阅读时间需要 22 分钟。
#ifndef LINKLIST_H_INCLUDED#define LINKLIST_H_INCLUDED/*********************************************************************** * Project:数据结构第二章案例 * Function：链表抽象数据类型的定义和实现 * Description：每个节点都有后继结点，链表的优点是存储空间利用高效 * Author：chillinght * *********************************************************************** * Copyright：2019 by chillinght *********************************************************************** */ #include#include #include "DataElement.h" #include /** 定义链表的结点，包含数据域和指针域 */ typedef struct Node{ ElementType data; //数据域 struct Node* next; //指针域,指向下个结点 }Node; //注意这里定义了链表的结点结构 //但是没有头结点，有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，谁叫它是第一个呢，有这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针/** * 下面的结构是用来存储指向第一个非头结点指针和链表长度的 * 头结点 * 也叫首元结点，最后一个结点也叫尾元结点， * 习惯性的定义头结点，以便统一结点的插入和删除 */ typedef struct LinkList{ Node* next ; //指针域 也就是头指针(如果有头结点，next指向头结点，没有就指向第一个结点） int length; //数据域 }LinkList; /** 初始化链表 */ void InitLinkList(LinkList * linkList,ElementType* dataArray,int length); /** 插入方法 */ void InsertLinkList(LinkList* linklist,ElementType element,int pos); /** 打印方法 */void PrintLinkList(LinkList* linkList);/** 判断是否为空 */int IsLinkListEmpty(LinkList* linklist);/** 查询返回pos位置的元素 */ElementType GetLinkListElement(LinkList* linklist,int pos);/** 删除pos位置的元素 返回元素内容 */ElementType DeleteLinkListElement(LinkList* linkList,int pos);/** 清空链表 */void ClearLinkList(LinkList* linklist);#endif // LINKLIST_H_INCLUDED
#include "LinkList.h" /** 初始化链表 */void InitLinkList(LinkList * linkList,ElementType* dataArray,int length){ for(int i= 1;i <= length;i++){ InsertLinkList(linkList,dataArray[i-1],i); } return;}/** 插入方法 在pos前面插入*//** * 向链表插入元素 * @param linklist 指向头结点的指针-》头指针（头指针指 指向第一个元素的指针，这里第一个元素是头结点） * @param element 插入元素 这里的元素是Node结点数据类型中的数据域内容 * @param pos 插入位置 */ void InsertLinkList(LinkList* linklist,ElementType element,int pos) { //1. 创建空间存储新节点信息 Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = element; new_node->next = NULL; //2. 找到要插入的位置 if(pos == 1){ //如果插入的是第一个元素，由于linklist和node数据结构不一样 需要单独写一下 new_node->next = linklist->next; linklist->next = new_node; linklist->length ++; //printf("%d\n",linklist->length); return; } // 下面正式开始找位置（pos之前元素的位置） Node* p = linklist->next; //p指向第一个元素 for(int i = 1;p &&i < pos - 1;i++){ p = p->next; } //3.如果能够插入，开始定义结点空间并改变指针域进行连接 if(!p){ //如果pos位置的结点不存在 printf("该位置不存在\n"); return; } else{ new_node->next = p->next; p->next = new_node; //现在p已经没用了，已经连上了~ 可以删了p了 别忘了总长度 p = NULL; linklist->length++; //printf("%d\n",linklist->length); return; } }void PrintLinkList(LinkList * linkList){ Node* p = linkList->next; if(!p){ printf("链表为空\n"); linkList->length = 0; return; } //printf("%d\n",linkList->length); while(p) { printf("%d\t%s\n",p->data.id,p->data.name); p = p->next; } //p = NULL; return;}int IsLinkListEmpty(LinkList* linklist){ return linklist->length == 0 ? true : false;}ElementType GetLinkListElement(LinkList* linklist,int pos){ Node* p = linklist->next; for(int i = 1;p && i < pos;i++){ p = p->next; } return p->data;}ElementType DeleteLinkListElement(LinkList* linkList,int pos){ //删除其实很简单 //1.判断pos是否合法 不合法直接gg //2.指定两个结点指针，分别指向要删除的结点和它上一个结点：这里注意如果是第一个元素，就没有前一个结点（头结点不算） //3.如果不是第一个元素，那就按照正常逻辑删除就ok printf("删除元素中\n"); if(pos > linkList->length){ printf("pos不合法，该位置元素无法删除\n"); return; } else{ //合法 Node* pre_node; Node* del_node = linkList->next; if(pos == 1){ linkList->next = del_node->next; free(del_node); linkList->length--; } else{ for(int i = 1;i < pos;i++) { //把指针位置弄好 pre_node = del_node; del_node = del_node->next; } ElementType ret_element; del_node->data = ret_element; pre_node->next = del_node->next; free(del_node); linkList->length--; return ret_element; } }}void ClearLinkList(LinkList* linklist){ printf("开始删除整个单链表\n"); Node* p; Node* q; p = linklist->next; while(p){ q = p->next; free(p); p = q; } linklist->next = NULL; linklist->length = 0; printf("删除完成\n"); return;} #include#include #include "SequenceList.h"#include "DataElement.h"#include "LinkList.h"//测试一下~void TestSequenceList();void TestLinkList();int main(){ //TestSequenceList(); TestLinkList(); return 0;}void TestSequenceList(){ ElementType dataArray[] = { { 1,"海绵宝宝"}, { 2,"派大星"}, { 3,"章鱼哥"}, { 4,"蟹老板"}, { 5,"痞老板"} }; SeqList seqlist; InitList(&seqlist,dataArray,sizeof(dataArray) / sizeof(dataArray[0])); PrintList(&seqlist); //下面进行删除操作测试 int del = -1,get = -1; printf("下面进行删除操作测试\n请输入删除元素的索引值："); scanf("%d",&del); ElementType* del_element = DeleteElement(&seqlist,del); printf("删除之后的结果为：\n"); PrintList(&seqlist); printf("所删除的元素是：%d\t%s\n",del_element->id,del_element->name); printf("请输入要查找的元素的索引："); scanf("%d",&get); ElementType* get_element = GetElement(&seqlist,get); printf("您所查找的元素为：%d\t%s:",get_element->id,get_element->name); free(del_element);}void TestLinkList(){ ElementType dataArray[] = { { 1,"海绵宝宝"}, { 2,"派大星"}, { 3,"章鱼哥"}, { 4,"蟹老板"}, { 5,"痞老板"} }; LinkList linklist; linklist.length = 0; linklist.next = NULL; //printf("%d\n",sizeof(dataArray)/sizeof(dataArray[0])); InitLinkList(&linklist,dataArray,sizeof(dataArray)/sizeof(dataArray[0])); PrintLinkList(&linklist); printf("\n"); ElementType new_node_element; new_node_element.id = 6; new_node_element.name = "xxxxx"; InsertLinkList(&linklist,new_node_element,2); PrintLinkList(&linklist); printf("是否为空？\t%d\n",IsLinkListEmpty(&linklist)); printf("第3位元素为%d\t%s\n",GetLinkListElement(&linklist,3)); ElementType del_data; del_data = DeleteLinkListElement(&linklist,3); printf("删除的元素为%d\t%s\n",del_data.id,del_data.name); PrintLinkList(&linklist); ClearLinkList(&linklist); PrintLinkList(&linklist); return;}
转载地址：http://sjzwi.baihongyu.com/