数据结构: 双向链表

双向链表

 / /结构体定义
typedef struct Node
{int num;struct Node* pNext;struct Node* pPer;
}NODE;

创建一个节点

 / / 创建一个节点信息/ / 只是创建了一个独立节点,没有和原链表产生任何关系!void creatNode(){NODE* new_node = (NODE*)malloc(sizeof(NODE))  / / 因为&n的值无法带回有效值 故NODE n 错误/ / 使用局部变量节省内存if(NULL == new_node) /  / 判空操作{perror("creatNode malloc fill!\n") / /标准库返回错误信息return NULL;}new_node -> num = value;new_node ->pNext = NULL;new_node ->pPer = NULL;return new_node;}

头插法

NODE* inserthead(NODE* head,int value)
{NODE* new_node = createNode(value); / / 新节点创建失败!if(NULL == new_node)return head;if (head == NULL) / / 原链表空!{return new_node;}new_node ->pNext = head;head ->pPer = new_node;return new_node;}

打印链表

void display(NODE* head)
{while(head != NULL){printf("%d",head -> num);head = head -> pNext;}printf("\n");
}

尾插法

NODE* inserttill(NODE* head,int value)
{NODE* new_node = createNode(value); if(NULL == new_node)return head;if (head == NULL) {return new_node;}NODE* p =head;while(p != NULL){p = p -> pNext;}new_node = p -> pNext;new_node -> pNext = NULL;new_node -> pPer = p;return head;
}

中间插入

NODE* insertmid(NODE* head, int value, int pos) {NODE* new_node = createNode(value);if (new_node == NULL) return head;  // 内存分配失败int len = getLength(head);// 处理空链表（直接返回新节点）if (head == NULL) {return (pos == 1) ? new_node : head;}// 头插（pos=1）if (pos == 1) {new_node->pNext = head;head->pPer = new_node;return new_node;  // 新节点成为头节点}// 尾插（pos等于长度+1时也视为尾插）if (pos == len + 1) {return insertTail(head, value);}// 中间插入（需检查pos是否合法）if (pos < 2 || pos > len) {// pos超出范围，插入失败（可根据需求调整处理方式）free(new_node);return head;}// 找到插入位置的前一个节点（pos-1的前驱）NODE* prev = head;for (int i = 1; i < pos - 1; i++) {  // 移动到pos-2的位置prev = prev->pNext;}// 插入新节点NODE* curr = prev->pNext;  // pos位置的原节点prev->pNext = new_node;new_node->pPer = prev;new_node->pNext = curr;if (curr != NULL) {curr->pPer = new_node;}return head;  // 返回头节点（头节点未改变）
}

中间插入

// pos = 0 时为头插法
// 当前函数不处理头插和尾插的情况
NODE* insertMid(NODE* head, int value, int pos)
{NODE* new_node = createNode(value);if (NULL == new_node){// 新节点创建失败return head;}if (head == NULL){// 原链表为空return new_node;}// 获取pos位置的节点指针NODE* cur = currentPosNode(head, pos);// 将新节点与其插入位置之后的节点进行连接new_node->pNext = cur->pNext;cur->pNext->pPer = new_node;// 将新节点与其插入位置之前节点进行连接cur->pNext = new_node;new_node->pPer = cur;return head;
}

NODE* deleteNode(NODE* head,)
{if(NNULL == head){printf("无节点!\n");return NULL;}while(head != NULL && head ->num == value){NODE* pBef = head -> pPer; / / 记录前后两个节点NODE* pAft = head -> pNext;/ / 首节点删除if(pBef == NULL){head = p1 -> pNext;}pBer ->pNext = pAft;     / / 链接两个指针pAft ->pPer = pBeef;free(p1);p1 = pAft;}if(head -> pNext == NULL){free(head);//head = NULL;return NULL;}}

尾插法

NODE* insertTail(NODE* head, int value)
{NODE* new_node = createNode(value);if (NULL == new_node){// 新节点创建失败return head;}if (head == NULL){// 原链表为空return new_node;}// 获取尾节点NODE* tail = getListTail(head);tail->pNext = new_node;new_node->pPer = tail;return head;
}