C语言学习之链表的实现详解
Fug_Lee 人气:0一、链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
二、链表的结构
（1）单链表
（2）带头结点的单链表
（3）双向链表
（4）循环单链表
（5）双向循环链表
注释：
（1）无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
（2）带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。
三、顺序表和链表的区别和联系
（1）顺序表：
优点： 空间连续，支持随机访问。
缺点： 中间或前面部分的插入删除时间复杂度为O（n），并且增容代价比较大。
（2）链表
优点： 任意位置插入删除时间复杂度为O(1) 2.没有增容问题，插入一个开辟一个空间。
缺点： 以节点为单位存储，不支持随机访问。
四、链表的实现
（1）单链表的增删查找等操作
#pragma once
#include"common.h"
typedef struct SListNode
{
ElemType data;
struct SListNode* next;
}SListNode;
typedef struct SList
{
SListNode* head;
}SList;
///
///
//单链表的函数接口声明
void SListInit(SList* plist);
static SListNode* _Buynode(ElemType x);
void SListPushBack(SList* plist, ElemType item);//1
void SListPushFront(SList* plist, ElemType item);//2
void SListShow(SList* plist);//3
void SListPopBack(SList* plist);//4
void SListPopFront(SList* plist);//5
void SListInsertVal(SList* plist, ElemType val);//7
void SqListDeleteByVal(SList* plist, ElemType val);//9
SListNode* SListFind(SList* plist, ElemType key);//10
size_t SListLength(SList* plist);//11
void SListSort(SList* plist);//13
void SListReverse(SList* plist);//14
void SListClear(SList* plist);//15
void SListDestroy(SList* plist);
///
///
//单链表的函数接口实现
void SListInit(SList* plist)
{
plist->head = NULL;
}
static SListNode* _Buynode(ElemType x)
{
SListNode* s = (SListNode*)malloc(sizeof(SListNode));
assert(s != NULL);
s->data = x;
s->next = NULL;
return s;
}
//1
void SListPushBack(SList* plist, ElemType item)
{
assert(plist != NULL);
SListNode* s = _Buynode(item);
//插入的节点为第一个节点
if (plist->head == NULL)
{
plist->head = s;
return;
}
//O(n)
SListNode* p = plist->head;
//查找链表的尾部节点
while (p->next != NULL)
{
p = p->next;
}
p->next = s;
}
//2
void SListPushFront(SList* plist, ElemType item)
{
assert(plist != NULL);
SListNode* s = _Buynode(item);
s->next = plist->head;
plist->head = s;
}
//3
void SListShow(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head;
while (p != NULL)
{
printf("%d-->", p->data);
p = p->next;
}
printf("Over.\n");
}
//4
void SListPopBack(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head;
if (plist->head == NULL)
{
printf("单链表为空，输出失败!\n");
return;
}
if (p->next == NULL)
{
plist->head = NULL;
return;
}
SListNode* prev = NULL;
while (p->next != NULL)
{
prev = p;
p = p->next;
}
prev->next = NULL;
free(p);
}
//5
void SListPopFront(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head;
if (plist->head == NULL)
{
printf("单链表为空，输出失败!\n");
return;
}
plist->head = p->next;
free(p);
}
//6
//7
void SListInsertVal(SList* plist, ElemType val)
{
assert(plist != NULL);
SListNode* prev = NULL;
SListNode* p = plist->head;
SListNode* s = _Buynode(val);
while (p != NULL && val > p->data)
{
prev = p;
p = p->next;
}
if (prev == NULL)
{
s->next = p;
plist->head = s;
}
else
{
s->next = prev->next;
prev->next = s;
}
}
//10
SListNode* SListFind(SList* plist, ElemType key)
{
assert(plist != NULL);
SListNode* p = plist->head;
while (p != NULL && p->data != key)
p = p->next;
return p;
}
//9
void SqListDeleteByVal(SList* plist, ElemType val)
{
assert(plist != NULL);
SListNode* prev = NULL;
SListNode* p = SListFind(plist, val);
if (p == NULL)
{
printf("要删除的节点不存在.\n");
return;
}
if (p == plist->head)
plist->head = p->next;
else
{
prev = plist->head;
while (prev->next != p)
prev = prev->next;
//删除
prev->next = p->next;
}
free(p);
}
//11
size_t SListLength(SList* plist)
{
assert(plist != NULL);
size_t len = 0;
SListNode* p = plist->head;
while (p != NULL)
{
len++;
p = p->next;
}
return len;
}
//13
void SListSort(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head->next;
SListNode* q, * t, * prev = NULL;
plist->head->next = NULL; //断开链表
t = plist->head;
while (p != NULL)
{
q = p->next;
while (t != NULL && p->data > t->data)
{
prev = t;
t = t->next;
}
if (prev == NULL)
{
p->next = plist->head;
plist->head = p;
}
else //if(prev->next!=NULL)
{
p->next = prev->next;
prev->next = p;
}
p = q;
t = plist->head;
}
}
//14
void SListReverse(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head->next;
SListNode* q;
if (p->next == NULL)
return;
//断开第一个节点
plist->head->next = NULL;
while (p != NULL)
{
q = p->next;
p->next = plist->head;
plist->head = p;
p = q;
}
}
//15
void SListClear(SList* plist)
{
assert(plist != NULL);
SListNode* p = plist->head;
while (p != NULL)
{
plist->head = p->next;
free(p);
p = plist->head;
}
}
void SListDestroy(SList* plist)
{
SListClear(plist);
plist->head = NULL;
}
```c
（2）带头的双循环链表的实现
#pragma once
#include"common.h"
/
//带头的双循环链表
typedef struct DCListNode
{
ElemType data;
struct DCListNode* next;
struct DCListNode* prev;
}DCListNode;
typedef struct DCList
{
DCListNode* head;
}DCList;
static DCListNode* _Buydnode(ElemType x);
void DCListInit(DCList* plist);
void DCListDestroy(DCList* plist);
void DCListPushBack(DCList* plist, ElemType x);//1
void DCListPushFront(DCList* plist, ElemType x);//2
void DCListShow(DCList* plist);//3
void DCListPopBack(DCList* plist);//4
void DCListPopFront(DCList* plist);//5
void DCListInsertByVal(DCList* plist, ElemType val);//7
void DCListDeleteByVal(DCList* plist, ElemType val);//9
size_t DCListLength(DCList* plist);//11
void DCListSort(DCList* plist);//13
void DCListReverse(DCList* plist);//14
void DCListClear(DCList* plist);//15
DCListNode* DCListFind(DCList* plist, ElemType key);//10
static DCListNode* _Buydnode(ElemType x)
{
DCListNode* s = (DCListNode*)malloc(sizeof(DCListNode));
assert(s != NULL);
s->data = x;
s->next = s->prev = s;
return s;
}
void DCListInit(DCList* plist)
{
plist->head = _Buydnode(0);
}
//1
void DCListPushBack(DCList* plist, ElemType x)
{
assert(plist != NULL);
DCListNode* s = _Buydnode(x);
s->prev = plist->head->prev;
s->prev->next = s;
s->next = plist->head;
plist->head->prev = s;
}
//2
void DCListPushFront(DCList* plist, ElemType x)
{
assert(plist != NULL);
DCListNode* s = _Buydnode(x);
s->next = plist->head->next;
s->next->prev = s;
plist->head->next = s;
s->prev = plist->head;
}
//3
void DCListShow(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
while (p != plist->head)
{
printf("%d->", p->data);
p = p->next;
}
printf("Over.\n");
}
//4
void DCListPopBack(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->prev;
if (plist->head->next == plist->head)
//if(p == plist->head)
{
printf("循环双链表只有头结点,操作失败.\n");
return;
}
plist->head->prev = p->prev;
p->prev->next = plist->head;
free(p);
}
//5
void DCListPopFront(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
if (p == plist->head)
{
printf("循环双链表只有头结点,操作失败.\n");
return;
}
plist->head->next = p->next;
p->next->prev = plist->head;
free(p);
}
//7
void DCListInsertByVal(DCList* plist, ElemType val)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
while (p != plist->head && p->data < val)
{
p = p->next;
}
DCListNode* s = _Buydnode(val);
s->next = p;
s->prev = p->prev;
p->prev->next = s;
p->prev = s;
}
//9
void DCListDeleteByVal(DCList* plist, ElemType val)
{
assert(plist != NULL);
DCListNode* p = DCListFind(plist, val);
if (p == NULL)
return;
p->next->prev = p->prev;
p->prev->next = p->next;
free(p);
}
//10
DCListNode* DCListFind(DCList* plist, ElemType key)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
if (p == plist->head)
{
printf("双循环链表只有头结点，查找失败.\n");
return 0;
}
while (p != plist->head && p->data != key)
{
p = p->next;
}
if (p != plist->head)
return p;
return NULL;
}
//11
size_t DCListLength(DCList* plist)
{
assert(plist != NULL);
size_t len = 0;
DCListNode* p = plist->head->next;
while (p != plist->head)
{
len++;
p = p->next;
}
return len;
}
//13
void DCListSort(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
DCListNode* q = p->next;
//断开链表
p->next = plist->head;
plist->head->prev = p;
while (q != plist->head)
{
p = q;
q = q->next;
//寻找p插入的位置
DCListNode* t = plist->head->next;
while (t != plist->head && t->data < p->data)
t = t->next;
p->next = t;
p->prev = t->prev;
p->next->prev = p;
p->prev->next = p;
p = q;
}
}
//14
void DCListReverse(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
DCListNode* q = p->next;
//断开链表
p->next = plist->head;
plist->head->prev = p;
while (q != plist->head)
{
p = q;
q = q->next;
p->next = plist->head->next;
p->prev = plist->head;
p->next->prev = p;
p->prev->next = p; //plist->head->next = p;
}
}
//15
void DCListClear(DCList* plist)
{
assert(plist != NULL);
DCListNode* p = plist->head->next;
while (p != plist->head)
{
p->next->prev = p->prev;
p->prev->next = p->next;
free(p);
p = plist->head->next;
}
}
void DCListDestroy(DCList* plist)
{
DCListClear(plist);
free(plist->head);
plist->head = NULL;
}
加载全部内容