双向链表的c语言实现

概述

链表是很多数据结构的基础，它本身也是一种基本数据结构（线性表）的一种常见实现。但是很多教程上链表的c语言实现在我看来不够模块化。而较为模块化的实现，往往是通过c++或java等面向对象语言实现的，对于新手不够友好。

建表

首先，建立节点与链表的结构体

struct ListNode {
   //节点 int data;//数据 ListNode* Next;//指向前一个节点 ListNode* Last;//指向后一个节点};

struct List {
   //双向链表 ListNode* header;//头哨兵 ListNode* trailer;//尾哨兵 int _size;//链表规模};

这里我在链表的结构体内封装了_size变量作为链表的规模，这个变量可以简化之后对于链表的操作。

接下来开始对于表的初始化，建立一个_size为0，头哨兵与尾哨兵相连的链表

void CreateList(List* l)//建表{
    l->_size = 0; l->header = (ListNode*)malloc(sizeof(ListNode)); l->trailer = (ListNode*)malloc(sizeof(ListNode)); l->header->Next = l->trailer; l->header->Last = NULL; l->trailer->Last = l->header; l->trailer->Next = NULL;}

注意，头哨兵与尾哨兵并不存储数据，它们的存在，是为了之后对于链表的修改能较为方便地进行。

插入与删除

首先，实现一下在第i项前，插入存储值为e的函数

void InsertBefore(int i, int e,List* l)//在第i项前插入e{
    ListNode* p = l->header->Next; for (int j = 0; j < i; j++)  p = p->Next;                              //定位第i项 ListNode* np = (ListNode*)malloc(sizeof(ListNode)); np->data = e; np->Next = p; np->Last = p->Last; p->Last->Next = np; p->Last = np;                        //注意指针连接的顺序，此处易错 l->_size++;}

由于是双向链表，在第i项后插入就没有必要实现了。

值得一提的是，在空表中逐一插入节点，等同于依次在尾哨兵前插入节点，其实现直接把上面函数的参数i改为_size+1即可，也可以单独实现如下：

void InsertList(List* l,int e)//在尾节点前插入{
    ListNode* np = (ListNode*)malloc(sizeof(ListNode)); np->data = e; np->Next = l->trailer; np->Last = l->trailer->Last; l->trailer->Last->Next = np; l->trailer->Last = np;         //注意指针连接的顺序 l->_size++;}

下面是删除某一项的代码

int DeleteElem(int r, List* l)//删除第r项{
    ListNode* now = l->header->Next; for (int i = 0; i < r; i++)  now = now->Next; int old = now->data; now->Last->Next = now->Next; now->Next->Last = now->Last;//注意指针重新连接的顺序 free(now);                  //有alloc就有free，防止内存泄漏 l->_size--; return old;                //返回被删除项存储的值}

测试及其结果

测试代码如下,选取了114与514两个~~刻在DNA里的~~数字：

int main(){
    List l1; CreateList(&l1); for (int i = 0; i < 514; i++)  InsertList(&l1, i + 1); DeleteElem(114, &l1); printf("%d\n", DeleteElem(114,&l1)); printf("%d\n", l1._size); return 0;}

输出如下，符合预期：

116

512

Press any key to continue . . .

转载地址：http://dzwai.baihongyu.com/

你可能感兴趣的文章