文章目录
1.带头节点的单链表
list头文件
#pragma once
//带头节点的单链表
//头节点:不用于存储数据,只是起标记作用
//单链表:尾节点的next为空
typedef struct Node
{
int data;//数据域
struct Node* next;//后继指针
}Node, * List; //List == Node *
//初始化
void InitList(List plist);
//头插
bool Insert_head(List plist, int val);
//尾插
bool Insert_tail(List plist, int val);
//插入数据,在plist顺序表的pos下标插入val
bool Insert(List plist, int pos, int val);
//判空
bool IsEmpty(List plist);
//获取数据节点个数
int GetLength(List plist);
//在plist中查找第一个key,找到返回节点地址,没有找到返回NULL
Node* Search(List plist, int key);
//删除pos位置的值
bool DelPos(List plist, int pos);
//删除第一个val值
bool DelVal(List plist, int val);
//返回key的前驱地址,如果不存在前驱则返回NULL
Node* GetPrio(List plist, int key);
//返回key的后继地址,如果不存在后继则返回NULL
Node* GetNext(List plist, int key);
//输出
void Show(List plist);
//清空数据
void Clear(List plist);
//销毁整个内存
void Destroy(List plist);
list.cpp文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "list.h"
//初始化
void InitList(List plist)
{
assert(plist != NULL);
if (plist == NULL)
return;
//plist->data;//头结点的data不使用
plist->next = NULL;//单链表的尾节点next为空
}
//头插
bool Insert_head(List plist, int val)
{
//动态申请一个新节点
Node* p = (Node*)malloc(sizeof(Node));
assert(p != NULL);
//将val放到新节点
p->data = val;
//插入新节点
p->next = plist->next;
plist->next = p;
return true;
}
//尾插
bool Insert_tail(List plist, int val)
{
assert(plist != NULL);
if (plist == NULL)
return false;//exit(1);//在工作中不允许使用
Node* p = (Node*)malloc(sizeof(Node));
p->data = val;
//找尾部
Node* q;
for (q = plist; q->next != NULL; q = q->next)
{
;
}
//插入新节点
p->next = q->next;
q->next = p;
//maxsize++;这种设计不好,不要使用全局变量(不安全)
return true;
}
//插入数据,在plist顺序表的pos下标插入val
bool Insert(List plist, int pos, int val)
{
if (pos<0 || pos>GetLength(plist))
{
return false;
}
Node* p = (Node*)malloc(sizeof(Node));//List == Node * 不建议使用List p;
p->data = val;
//找位置
Node* q;
int i;
for (q = plist, i = 0; i < pos; i++, q = q->next);
//p插入在q的后面
p->next = q->next;
q->next = p;
return true;
}
//判空
bool IsEmpty(List plist)
{
return plist->next == NULL;
}
//获取数据节点个数
int GetLength(List plist)
{
int count = 0;
for (Node* p = plist->next; p != NULL; p = p->next)
{
count++;
}
return count;
}
//在plist中查找第一个key,找到返回节点地址,没有找到返回NULL
Node* Search(List plist, int key)
{
for (Node* p = plist->next; p != NULL; p = p->next)
{
if (p->data == key)
return p;
}
return NULL;
}
//删除pos位置的值
bool DelPos(List plist, int pos)
{
if (pos < 0 || pos >= GetLength(plist))
{
return false;
}
Node* p;
int i;
for (p = plist, i = 0; i < pos; i++, p = p->next);
//删除p后面的节点
Node* q = p->next;
p->next = q->next;
free(q);
return true;
}
//删除第一个val值
bool DelVal(List plist, int val)
{
Node* p = GetPrio(plist, val);
if (p == NULL)
return false;
Node* q = p->next;//将要删除的节点
//将q从链表中剔除
p->next = q->next;//p->next = p->next->next;
//释放q
free(q);
return true;
}
//返回key的前驱地址,如果不存在前驱则返回NULL
Node* GetPrio(List plist, int key)
{
for (Node* p = plist; p->next != NULL; p = p->next)
{
if (p->next->data == key)//p是前驱地址
return p;
}
return NULL;
}
//返回key的后继地址,如果不存在后继则返回NULL
Node* GetNext(List plist, int key)
{
Node* p = Search(plist, key);
if (p == NULL)
return NULL;
return p->next;
}
//输出
void Show(List plist)
{
//通过节点指针,遍历所有的数据节点(注意头结点不能访问data)
for (Node* p = plist->next; p != NULL; p = p->next)
{
printf("%d ", p->data);
}
printf("\n");
}
//清空数据
void Clear(List plist)
{
Destroy(plist);
}
//销毁整个内存,释放所有的数据节点
void Destroy(List plist)
{
Node* p;
while (plist->next != NULL)//总是删除第一个数据节点
{
p = plist->next;
plist->next = p->next;
free(p);
}
}
void Destroy1(List plist)//太复杂
{
if (plist == NULL || plist->next == NULL)
return;
Node* p = plist->next;
Node* q;
plist->next = NULL;
while (p != NULL)
{
q = p->next;
free(p);
p = q;
}
}
2.带头结点的双向链表
dlist头文件
#pragma once
//双向链表
//带头结点的双向链表,不循环.尾节点的后继为空,头结点的前驱为空
typedef struct DNode
{
int data;
struct DNode* next;//后继指针
struct DNode* prio;//前驱指针
}DNode, * DList;
//初始化
void InitList(DList plist);
//头插
bool Insert_head(DList plist, int val);
//尾插
bool Insert_tail(DList plist, int val);
//插入数据,在plist顺序表的pos下标插入val
bool Insert(DList plist, int pos, int val);
//判空
bool IsEmpty(DList plist);
//获取数据节点个数
int GetLength(DList plist);
//在plist中查找第一个key,找到返回节点地址,没有找到返回NULL
DNode* Search(DList plist, int key);
//删除pos位置的值
bool DelPos(DList plist, int pos);
//删除第一个val值
bool DelVal(DList plist, int val);
//返回key的前驱地址,如果不存在前驱则返回NULL
DNode* GetPrio(DList plist, int key);
//返回key的后继地址,如果不存在后继则返回NULL
DNode* GetNext(DList plist, int key);
//输出
void Show(DList plist);
//清空数据
void Clear(DList plist);
//销毁整个内存
void Destroy(DList plist);
dlist.cpp文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "dlist.h"
//初始化
void InitList(DList plist)
{
assert(plist != NULL);
if (plist == NULL)
return;
//plist->data数据域不使用
plist->next = NULL;
plist->prio = NULL;
}
static DNode* BuyNode(int val)
{
DNode* p = (DNode*)malloc(sizeof(DNode));
p->data = val;
return p;
}
//头插
//考试的重点
bool Insert_head(DList plist, int val)
{
//创建新节点
DNode* p = (DNode*)malloc(sizeof(DNode));
p->data = val;
//DNode *p = BuyNode(val);
//插入新节点
p->next = plist->next;//首先将后面的数据节点绑好
plist->next = p;
p->prio = plist;
if (p->next != NULL)//判断很重要
{
p->next->prio = p;
}
return true;
}
//尾插
//考试的重点
bool Insert_tail(DList plist, int val)
{
DNode* p = (DNode*)malloc(sizeof(DNode));
p->data = val;
DNode* q = plist;
//找尾巴
for(;q->next != NULL;q = q->next)
{
;
}
//插入新节点
p->next = q->next;
q->next = p;
p->prio = q;
return true;
}
//插入数据,在plist顺序表的pos下标插入val
bool Insert(DList plist, int pos, int val)
{
if (pos < 0 || pos > GetLength(plist))
return false;
DNode* q = plist;
for (int i = 0; i < pos; i++)
{
q = q->next;
}
DNode* p = (DNode*)malloc(sizeof(DNode));
p->data = val;
p->next = q->next;
q->next = p;
p->prio = q;
if (p->next != NULL)
{
p->next->prio = p;
}
return true;
}
//判空
bool IsEmpty(DList plist)
{
return plist->next == NULL;
}
//获取数据节点个数
int GetLength(DList plist)
{
int count = 0;
for (DNode* p = plist->next; p != NULL; p = p->next)
{
count++;
}
return count;
}
//在plist中查找第一个key,找到返回节点地址,没有找到返回NULL
DNode* Search(DList plist, int key)
{
for (DNode* p = plist->next; p != NULL; p = p->next)
{
if (p->data == key)
return p;
}
return NULL;
}
//删除pos位置的值
bool DelPos(DList plist, int pos)
{
if (pos < 0 || pos > GetLength(plist))
return false;
DNode* q = plist->next;//
for (int i = 0; i < pos; i++)
{
q = q->next;
}
q->prio->next = q->next;
if (q->next != NULL)
{
q->next->prio = q->prio;
}
free(q);
return true;
}
//删除第一个val值 //考试的重点
bool DelVal(DList plist, int val)
{
DNode* p = Search(plist, val);
if (p == NULL)
return false;
//将p从链表中剔除
p->prio->next = p->next;
if (p->next != NULL)
{
p->next->prio = p->prio;
}
//释放节点p
free(p);
return true;
}
//返回key的前驱地址,如果不存在前驱则返回NULL
DNode* GetPrio(DList plist, int key)
{
DNode* p = Search(plist, key);
/*if(p == NULL)
return NULL;
return p->prio;*/
return p == NULL ? NULL : p->prio;
}
//返回key的后继地址,如果不存在后继则返回NULL
DNode* GetNext(DList plist, int key)
{
DNode* p = Search(plist, key);
return p == NULL ? NULL : p->next;
}
//输出
void Show(DList plist)
{
for (DNode* p = plist->next; p != NULL; p = p->next)
{
printf("%d ", p->data);
}
printf("\n");
}
//清空数据
void Clear(DList plist)
{
Destroy(plist);
}
//销毁整个内存
void Destroy(DList plist)
{
/*int a = GetLength(plist);
for (int i = 0;i< a; i++)
{
DelPos(plist, 0);
}*/
while (plist->next != NULL)
{
DelPos(plist, 0);
}
}
3.带头结点的循环链表
clist头文件
#pragma once
//循环链表:尾部节点的next指向头结点,形成一个环形
//带头结点
typedef struct CNode
{
int data;
struct CNode* next;
}CNode, * CList;
//初始化
void InitList(CList plist);
//头插
bool Insert_head(CList plist, int val);
//尾插
bool Insert_tail(CList plist, int val);
//插入数据,在plist顺序表的pos下标插入val
bool Insert(CList plist, int pos, int val);
//判空
bool IsEmpty(CList plist);
//获取数据节点个数
int GetLength(CList plist);
//在plist中查找第一个key,找到返回节点地址,没有找到返回NULL
CNode* Search(CList plist, int key);
//删除pos位置的值
bool DelPos(CList plist, int pos);
//删除第一个val值
bool DelVal(CList plist, int val);
//返回key的前驱地址,如果不存在前驱则返回NULL
CNode* GetPrio(CList plist, int key);
//返回key的后继地址,如果不存在后继则返回NULL
CNode* GetNext(CList plist, int key);
//输出
void Show(CList plist);
//清空数据
void Clear(CList plist);
//销毁整个内存
void Destroy(CList plist);
clist.cpp文件
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "clist.h"
//初始化
void InitList(CList plist)
{
assert(plist != NULL);
if (plist == NULL)
return;
plist->next = plist;//环形
}
//头插
bool Insert_head(CList plist, int val)
{
CNode* p = (CNode*)malloc(sizeof(CNode));
assert(p != NULL);
if (p == NULL)
return false;
p->data = val;
//头插
//CNode* q = plist;
p->next = plist->next;
plist->next = p;
return true;
}
//尾插
bool Insert_tail(CList plist, int val)
{
//创建新节点
CNode* p = (CNode*)malloc(sizeof(CNode));
assert(p != NULL);//以前要判断,现在一般不判断
if (p == NULL)
return false;
p->data = val;
//找尾巴
CNode* q;
for (q = plist; q->next != plist; q = q->next);
//插入新节点,p插入在q的后面
p->next = q->next;//p->next = plist;
q->next = p;
return true;
}
//插入数据,在plist顺序表的pos下标插入val
bool Insert(CList plist, int pos, int val)
{
if (pos < 0 || pos > GetLength(plist))
return false;
CNode* q = plist;
for (int i = 0; i < pos; i++)
{
q = q->next;
}
CNode* p = (CNode *)malloc(sizeof(CNode));
p->data = val;
p->next = q->next;
q->next = p;
return true;
}
//判空
bool IsEmpty(CList plist)
{
return plist->next == plist;
}
//获取数据节点个数
int GetLength(CList plist)
{
int count = 0;
for (CNode* p = plist->next; p != plist; p = p->next)
{
count++;
}
return count;
}
//在plist中查找第一个key,找到返回节点地址,没有找到返回NULL
CNode* Search(CList plist, int key)
{
assert(plist != NULL);
for (CNode* q = plist->next; q->next != plist;q = q->next)
{
if (q->data == key)
return q;
}
return NULL;
}
//删除pos位置的值
bool DelPos(CList plist, int pos)
{
if (pos < 0 || pos > GetLength(plist))
return false;
CNode* q = plist;
for (int i = 0; i < pos - 1; i++)
{
q = q->next;
}
CNode* p = q->next;
q->next = p->next;
free(p);
return true;
}
//删除第一个val值
bool DelVal(CList plist, int val)
{
CNode* p = GetPrio(plist, val);
if (p == NULL)
return false;
CNode* q = p->next;//将要删除的节点
//将q从链表中剔除
p->next = q->next;//p->next = p->next->next;
//释放q
free(q);
return true;
}
//返回key的前驱地址,如果不存在前驱则返回NULL
CNode* GetPrio(CList plist, int key)
{
assert(plist != NULL);
for (CNode* q = plist->next; q->next != plist; q = q->next)
{
if (q->next->data == key)
return q;
}
return NULL;
}
//返回key的后继地址,如果不存在后继则返回NULL
CNode* GetNext(CList plist, int key)
{
assert(plist != NULL);
for (CNode* q = plist->next; q->next != plist; q = q->next)
{
if (q->data == key)
return q->next;
}
return NULL;
}
//输出
void Show(CList plist)
{
for (CNode* p = plist->next; p != plist; p = p->next)
{
printf("%d ", p->data);
}
printf("\n");
}
//清空数据
void Clear(CList plist)
{
Destroy(plist);
}
//销毁整个内存
void Destroy(CList plist)
{
CNode* p;
while (plist->next != plist)//总是删除第一个数据节点
{
p = plist->next;
plist->next = p->next;
free(p);
}
}