数据结构—带头结点的单链表
前言
链式结构中，除了存数据元素信息外，还要存储它的后继元素的存储地址。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。这两部分组成一个结点。n个结点链结成一个链表，即为线性表的链式存储结构。因为此链表的每个结点中只包含一个指针域，所以叫做单链表。
- 为了更加方便地对链表进行操作，会在单链表地第一个结点之前附设一个结点，称为头结点。
- 头结点地数据域可以不存储任何信息，指针域存储指向第一个结点地指针。
一、带头结点的单链表结构设计
typedef int ElemType;
//设计结点类型
typedef struct ListNode {ElemType val;struct ListNode* next;//后继 结点类型的指针
}ListNode;//链表
typedef struct LinkList {ListNode* head;//head是头指针，指向头节点int cursize;//有效结点个数
};
二、头文件设计(SingleLink.h)
#ifndef SINGLELINK_H
#define SINGLELINK_H//带头结点的单向链表设计
typedef int ElemType;
//设计结点类型
typedef struct ListNode {ElemType val;struct ListNode* next;//后继 结点类型的指针
}ListNode;//链表
typedef struct LinkList {ListNode* head;//head是头指针，指向头节点int cursize;//有效结点个数
};//接口声明……#endif // !SINGLELINK_H
接口函数设计
//1、初始化
void InitList(LinkList* plist);
//2、清空链表元素---将有效结点依次删除
void Clear(LinkList* plist);
//3、销毁----清空链表+删除头结点
void Destory(LinkList* plist);
//4、判空操作
bool IsEmpty(LinkList* plist);
//5、头插法
bool InsertHead(LinkList* plist,ElemType val);
//6、尾插法
bool InsertTail(LinkList* plist, ElemType val);
//7、指定位置插入---pos 第几个有效结点
bool InsertPosindex(LinkList* plist, int pos, ElemType val);
//8、头删法
bool DeleteHead(LinkList* plist);
//9、尾删法
bool DeleteTail(LinkList* plist);
//10、指定位置删除，返回删除结点的元素值
ElemType DeletePos(LinkList* plist, int pos);
//11、删除val元素对应的结点
bool DeleteVal(LinkList* plist, ElemType val);
//12、获取指定结点的前驱结点
ListNode* GetPrevNode(LinkList* plist, ElemType val);
//13、获取指定结点的后驱结点
ListNode* GetNextNode(LinkList* plist, ElemType val);
//14、删除指定结点的前驱结点
bool DeletePrevNode(LinkList* plist, ElemType val);
//15、删除指定结点的后驱结点
bool DeleteNextNode(LinkList* plist, ElemType val);
//16、打印链表
void Show(LinkList* plist);
三、接口函数实现(SingleLink.cpp)
#include "SingleLink.h"
#include 1、初始化
ListNode* Buynode(ElemType val,ListNode* next) {ListNode* p = (ListNode*)malloc(sizeof(ListNode));if (p == nullptr)return nullptr;//memset(p, 0, sizeof(ListNode));p->next = next;p->val = val;return p;
}
void InitList(LinkList* plist) { assert(plist != nullptr);plist->head = Buynode(0,nullptr);//带头结点plist->cursize = 0;
}
2、清空链表元素—将有效结点依次删除
void Clear(LinkList* plist) {assert(plist != NULL);ListNode* p;while (plist->head->next != nullptr) {//1.指针指向待删除结点地址p = plist->head->next;//2.贯穿plist->head->next = p->next;//3.释放p结点free(p);plist->cursize--;}/*while (!IsEmpty(plist)) {DeleteHead(plist); 空间开销大} */
}
3、销毁链表----清空链表+删除头节点
void Destory(LinkList* plist) {assert(plist != nullptr);Clear(plist);free(plist->head);plist->head = nullptr;
}
4、判空操作
bool IsEmpty(LinkList* plist){assert(plist != nullptr);//return plist->cursize == 0; 两种方式return plist->head->next == nullptr;
}
5、头插法
bool InsertHead(LinkList* plist, ElemType val) {assert(plist != nullptr);ListNode* p = Buynode(val,nullptr);//生成新结点p assert(p != nullptr);p->next = plist->head->next;plist->head->next = p;plist->cursize++;return true;
}
6、尾插法
bool InsertTail(LinkList* plist, ElemType val) {assert(plist != nullptr);ListNode* newnode = Buynode(val, nullptr);//生成新结点assert(newnode != nullptr);//找到尾结点 尾结点-> next=pListNode* s = plist->head;while (s->next != nullptr) {s = s->next;}s->next = newnode;plist->cursize++;return true;
}
7、指定位置插入 pos----第几个有效结点
bool InsertPosindex(LinkList* plist, int pos, ElemType val) {assert(plist != nullptr && pos >= 0 && pos <= plist->cursize+1);ListNode* newnode = Buynode(val, nullptr);//新节点assert(newnode != nullptr);ListNode* p = plist->head;for (int i = 0; i < pos - 1; i++) {//找该位置前一个结点 p = p->next;}newnode->next = p->next;//先牵右手p->next = newnode;//再牵左手plist->cursize++;return true;
}
8、头删法
bool DeleteHead(LinkList* plist) {assert(plist != NULL);if (IsEmpty(plist))return false;//空链表不需要删除//1.指针指向待删除结点地址ListNode* p = plist->head->next;//2.贯穿plist->head->next = p->next;//3.释放p结点free(p); plist->cursize--;return true;
}
9、尾删法
bool DeleteTail(LinkList* plist) {assert(plist != nullptr);if (IsEmpty(plist))return false;//空链表不需要删除ListNode* p = plist->head;while (p->next->next != nullptr) {//找到尾结点的前一个结点p p = p->next;}p->next = p->next->next;free(p->next);plist->cursize--;return true;
}
10、指定位置删除,返回删除结点的元素值
//pos 删除第几个有效结点
ElemType DeletePos(LinkList* plist, int pos) {assert(plist != nullptr && pos >= 1 && pos < plist->cursize);if (IsEmpty(plist))exit(EXIT_FAILURE);ListNode* pre = plist->head;int i = 0;while (i < pos-1) {pre = pre->next;//pre标记待删结点的前一个结点i++;}ListNode* p = pre->next;//p标记待删结点ElemType val = p->val;pre->next = p->next;//free(p);可以省略。p属于局部变量，不会出现野指针问题plist->cursize--;return val;
}
11、删除val元素对应的结点
bool DeleteVal(LinkList* plist, ElemType val) {assert(plist != nullptr);if (IsEmpty(plist))return false;ListNode* p = plist->head;//删除第一个出现的val结点while (p->next!=nullptr && p->next->val != val) {//待删结点的前一个结点p = p->next;}if (p->next == nullptr)return false;//没有找到val所在结点则直接返回ListNode* q = p->next;//待删结点p->next = p->next->next;free(q); plist->cursize--;return true;
}
注：
1、这里删除的是val元素对应的第一个结点。有待修改为删除为删除val元素对应的所有结点。
2、如果找到指定位置，再调用DeletePos(LinkList* plist, int pos) 会增加开销，因为DeletePos存在重复for循环
12、获取指定结点的前驱结点
ListNode* GetPrevNode(LinkList* plist, ElemType val) {assert(plist != nullptr);if (IsEmpty(plist))return nullptr;ListNode* q = nullptr;for (ListNode* p = plist->head; p->next != nullptr; p = p->next) {if (p->next->val == val) {q = p;break;}}return q;
}13、获取指定结点的后驱结点
ListNode* GetNextNode(LinkList* plist, ElemType val) {assert(plist != nullptr);ListNode* p = plist->head->next;for (; p != nullptr && p->val != val ; p = p->next) {;}return p != nullptr ? p->next : nullptr;
}
14、删除指定结点的前驱结点
bool DeletePrevNode(LinkList* plist, ElemType val) {assert(plist != nullptr);if (IsEmpty(plist))return false;//空链表不删除ListNode* q;for (ListNode* p = plist->head; p->next->next != nullptr; p = p->next) {if (p->next->next->val == val) {//p标记的是val所在结点的前前个结点q = p->next;p->next = p->next->next;free(q);break;}}plist->cursize--;return true;}
15、删除指定结点的后驱结点
bool DeleteNextNode(LinkList* plist, ElemType val) {assert(plist != nullptr);if (IsEmpty(plist))return false;//空链表不删除ListNode* q;for (ListNode* p = plist->head->next; p != nullptr; p = p->next) {if (p->val == val) {//p标记的是val所在结点if (p->next == nullptr)return false;//尾结点不删除q = p->next;p->next = p->next->next;free(q);break;}}plist->cursize--;return true;
}
16、打印链表
void Show(LinkList* plist) {//方式一for (ListNode* p = plist->head ; p->next!=nullptr ; p = p->next) {printf("%5d", p->next->val);}printf("\n");//方式二/*for (ListNode* p = plist->head->next; p != nullptr; p = p->next) {printf("%5d", p->val);}*/
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！