线性表——循环双向链表定义、初始化、插入、删除

#include <stdio.h> #include <crtdbg.h> #include <corecrt_malloc.h> typedef int DataType;

1.定义链表

typedef struct Node { DataType data; struct Node* prior; struct Node* next; }DListNode,*DLinkList;

2.初始化循环链表（双向链表）

int ds_init(DListNode * *PNode) { int item; DListNode* temp, * target; printf("输入结点的值，输入0完成初始化\n"); while (1) { scanf("%d",&item); fflush(stdin);//清除缓存区 if (item == 0) { //如果输入0，结束退出 return 0; } if ((*PNode) == NULL)//PNode的地址是NULL 说明此表为空 {//循环表中只有一个结点 *PNode = (DListNode*)malloc(sizeof(DListNode));//分配空间 if (!(*PNode)) //如果分配空间，就错误退出 { return 0; } (*PNode)->data = item; //将新输入的数据传输PNode (*PNode)->next = *PNode; //因其假设为第一结点 } else { //找到next指向第一个结点的结点 也就是尾部 for (target = (*PNode); target->next != (*PNode); target = target->next); temp= (DListNode*)malloc(sizeof(DListNode)); if (!temp) { return 0; } temp->data = item; temp->next = *PNode; target->next = temp; } } }

3.插入双向链表

//参数：链表的第一个结点，插入位置 int ds_insert(DListNode **PNode,int i) { DListNode* temp, * target, * p; int item; int j = 1; printf("输入要插入结点的值："); scanf("%d",&item); if (i == 1) { temp = (DListNode*)malloc(sizeof(DListNode));//分配空间 if (!temp) { return 0; } temp->data = item; //寻找到最后一个结点 for (target = (*PNode); target->next != (*PNode); target = target->next); temp->next=(*PNode);//指向原来的第一个结点 target->next = temp;//指向新插入第一个结点的地址 } else { //假设我插入第三个结点 target = *PNode; //指向第一个结点的指针 for (; j < i-1; ++j) //i-1=2 { //——》第2个元素 target = target->next; //——》第3个元素 }//当target结束循环时，target指向第3个元素 temp = (DListNode*)malloc(sizeof(DListNode));//分配空间 if (!temp) { return 0; } temp->data = item; //给新空间赋值 p = target->next; //此时target-》next指向第三个元素 target->next = temp; temp->next = p; } }

4.删除双向链表

int ds_delete(DListNode** PNode, int i) { DListNode* temp, * target; int j = 1; if (i == 1) { //找到最后一个结点 for (target = (*PNode); target->next != (*PNode); target = target->next); target = *PNode; *PNode = (*PNode)->next; target->next = *PNode; free(temp); } else { target = *PNode; for (; j < i - 1; ++j) { target = target->next; } temp= target->next; target->next = temp->next; free(temp); } }

5.返回结点所在位置

int ds_select (DListNode* PNode, int elem) { DListNode *target; int i = 1; //找到最后一个结点 找到元素没找到结束 找一圈没找到结束 for (target = PNode; target->data != elem && target->next != PNode;++i); { target = target->next; } if(target->next==PNode) { return 0; } else { return 1; } }