双向链表的基本常用操作（创建、初始化、插入、删除、链表长度、查找指定元素的位置、链表的销毁） c语言 数据结构 超详细~~

/本程序中包含对双向链表的：：创建、初始化、插入、删除、链表长度、查找指定元素的位置以及双向链表的销毁/

#include<stdio.h>

#include<stdlib.h>

typedef int Elemtype;

typedef struct linknode

{

Elemtype data;

struct linknode* next;

}Linknode,Linklist;

//创建循环链表

Linknode create()

{

Linklist head = (Linklist)malloc(sizeof(Linknode));

if (!head)

{

printf(“分配内存空间失败\n”);

return 0;

}

head->next = head;

return head;

}

//初始化循环链表(头插法）（本质上是尾插法，但是每次都将最后一个结点

//作为第一个结点，就相当于头插法）

void initnode(Linknode* head)

{

int elem;

Linknode* target,p;

while (1)

{

printf(“请输入数据elem”);

scanf_s("%d", &elem);

if (elem == 0)

{/当我们输入0的时候，就代表数据已经输入完成了，就要通过break退出循环了/

printf(“输入完成\n”);

break;

}

for (target = head->next; target != head; target = target->next);

/上面for循环的作用是找到双向链表 的最后一个结点，那我们为什么要找该双向链表的最后一个结点呢？因为我们想要通过尾插法的形式进行链表的插入，并且当循环结束之后target就指向了双向链表中的最后一个结点了/

p = (Linknode)malloc(sizeof(Linknode));

/为插入的结点申请空间/

if (!p)

{/如果p等于NULL，那么申请内存空间失败，那么程序就应该返回，注意直接用return返回就可以了/

printf(“内存空间分配失败\n”);

return;

}

/如果内存申请成功，就将刚刚输入的elem的值赋值给刚刚申请内存空间的结点，准备插入/

p->data = elem;

Linknode* headnode = target->next;

//通过遍历得到的target已经是循环遍历的最后一个结点了，那么target->next就是该双向链表中头指针的地址

p->next = headnode;

/这句话可以和上一行的代码一次性的写成p->next=target-next,直接省略掉了headnode的步骤）

并且最后几行代码的含义就是先将刚刚准备插入的结点的next的指针指向头指针，然后再将原先链表的最后一个结点指向刚刚加入的结点/

target->next = p;

/注意p->next=target-next和 target->next = p这两句代码就不能交换；因为如果交换了的话， target->next = p，p->next=target-next=p,那么p->next就会等于p，而p->next在双向链表中应该指向头指针，因为它已经为最后一个元素了/

}

}

//循环链表的插入数据

void insertnode(Linknode* head, Elemtype x, int i)

{

//在位置i插入数据元素为x的结点

int j = 0;

Linknode* p = head,q;

for (j = 0; p->next != head && j < i-1; j++)

{/注意for循环中j<i-1就结束的原因是：

我们为了找到插入位置的前一个位置，因为我们需要用到插入位置的前一个位置的指针，需要将该指针的地址进行一个修改，从指向原来的结点到指向新插入的结点/

/现在我们来分析为什么是j等于i-1就结束了：：

因为刚开始p结点是指向头节点的，并且 j刚开始也初始化为0，所以当p指向第i-1个结点时，这个结点是我们需要的结点，循环就应该结束，这时j等于i-1，所以当j<i-1的时候，都可以一个一个往下找，当j=i-1的时候，循环就应该结束，即此时p已经指向了第i-1个结点了/

p = p->next;

}

/注意该for循环结束是已经找到了第i-1个结点p了/

if (p->next != head)

{//找到了合理的插入的位置

//并且p为插入位置的前一个结点

/那为什么插入位置合理的位置的条件是p->next != head呢？？现在我们来分析：：

由于该链表是一个双向链表，p为待插入结点的上一个结点，如果p->next即p的下一个结点如果不存在的话，那么就不可能在这个位置进行插入了，即插入失败！！那么说明时候为p的下一个结点不存在呢？？就是p->next等于head，因为该链表是双向链表，不是单链表，所以它的下一个结点不存在的判断条件不是p->next!=NULL/

q = (Linknode)malloc(sizeof(Linknode));

/如果插入位置合理的话，就为该结点申请内存空间/

if (!q)

{

printf(“分配内存空间失败\n”);

return;

/如果申请内存空间不成功，那么就返回，空即return掉/

}

q->data = x;/申请内存空间成功，那么就将值x赋给新增加的结点的data域，再将该节点插入即可/

q->next = p->next;

p->next = q;

printf("%d已经插入成功\n", x);

/注意插入应该从后往前插入，因为如果从前往后插入的话，即先执行p->next=q的话，那么p结点原先的下一个结点的指针就已经找不到了，就不能完成插入的相关操作，所以要先执行q->next=p->next;在执行p->next=q;如果先执行p->next=q的话，记得要先将p->next赋给一个变量/

}

else

{

printf(“插入失败\n”);

}

}

//循环链表删除数据

void deletenode(Linknode* head, int i)

{

//删除位置为i的结点

int j;

Linknode* p = head,target;

for (j = 1; p->next!=head&&j < i; j++)

{//该for循环的目的是找到删除结点的上一个结点p

p = p->next;/必须要找到插入位置的前一个结点，因为你一旦找到了准备删除的结点，就找不到该节点的前驱结点了，就无法完成删除的相关操作了/

}

if (p->next != head)//找到了合理的删除的位置

{

target = p->next;

int elem = target->data;

p->next = target->next;

free(target);

printf("%d已经删除成功\n", elem);

}

else

{

printf(“删除失败\n”);

}

}

//统计循环链表的长度

void calculate(Linknode head)

{

Linknode* p = head;//将双向链表的头指针赋给一个指针变量p，因为我们不可以随意对原先双向链表的头指针进行随意的改动*/

int count = 0;//计算器

while (p->next!= head)

{/当p->next指向头指针的时候，双向链表也就所有的元素都遍历一遍了/

count++;

p = p->next;

}

printf(“该链表的长度为%d\n”, count);

}

//销毁循环链表

void destorynode(Linknode* head)

{

Linknode* p=head->next, * q;

while (p!= head)

{

q = p;

p = p->next;

free(q);

q = NULL;

}

head = NULL;

printf(“双向链表已经销毁完毕\n”);

}

//查找双向链表中指定数据的位置

void searchnode(Linknode* head, Elemtype x)

{

Linknode* p = head;

int count = 0;//计数器

for (; p!= head && p->data != x; p = p->next,count++);

/该for循环的意思是在双向链表内如果找到有结点的值等于x的，就退出循环；

所以我们如果在链表中找到了某个结点的值是等于x的，那么p一定不等于head；反之如果我们没有找到，那么p一定是等于head的，意思是一直到最后一个结点都没有找到，所以我们可以通过该判断条件来判断是否找到了指定了元素，若找到了指定的元素，就返回它的位置，该count就是用来存储该指定的元素在双向链表的位置的/

if (p != head)

{

printf(“找到了，位置为%d\n”, count);

}

else

{

printf(“没有找到\n”);

}

}

void print(Linknode* head)

{

Linknode* p = head->next;

/注意打印是从第一个有数据的结点开始，所以应该是head->next开始/

while (p != head)

{/一直打印到最后一个结点结束/

printf("%d\t", p->data);

p = p->next;

}

}

void test01()

{

int choice=0;

Linknode*L=NULL;

L = create();

initnode(L);

print(L);

printf("\n");

deletenode(L, 2);

print(L);

printf("\n");

insertnode(L, 100, 2);

print(L);

printf("\n");

deletenode(L, 1);

print(L);

printf("\n");

calculate(L);

printf("\n");

destorynode(L);

printf("\n");

}

int main(void)

{

test01();

system(“pause”);

return 0;

}

代码运行结果如图所示