《C和指针学习笔记》之双链表操作

主要参考代码来自：http://blog.csdn.net/l52188821/archive/2009/02/24/3933743.aspx

#include<stdio.h> #include<stdlib.h> typedef struct node { struct node *pre; struct node *next; int data; char *name; }Node; #define LEN (sizeof(Node)) /****************************************************************************************** *函数名称：Node* create_double_link(int n) *函数功能：创建升序排列的双链表 *入口参数：链表节点个数 *返回值：指向节点(结构体)的指针 *******************************************************************************************/ Node* create_double_link(int n) { Node *current; Node *head; Node *new; int i; new = (Node*)malloc(LEN*n); if(NULL == new) { return NULL; } for(i = 0; i < n; i++) { new->data = (i+1)*2; /*如果是头结点，要赋值给head，用于返回*/ if(0 == i) { new->name = "head"; new->pre = NULL; head = new; /*头结点不用current->next = new;*/ current = new; new++; } /*如果是尾节点*/ else if((n-1) == i) { new->name = "tail"; new->pre = current; /*开始写成current->next = NULL，导致没有尾节点;*/ { current->next = new; new->next = NULL; } /*尾节点不用current = new;*/ /*尾节点不用new++;*/ } /*中间节点，实际上相当于在双链表的尾部插入新节点*/ else { new->name = "body"; new->pre = current; current->next = new; current = new; new++; } } /*头结点的前驱是空*/ head->pre = NULL; return head; } /****************************************************************************************** *函数名称：int insert_double_link(Node **linkp, int data, char *name) *函数功能：创建往升序排列的双链表中插入新的节点 *入口参数：linkp, 指向链表头节点的指针的指针; data, 新节点的数值字段; name, 新节点的名称字段 *返回值：-1, 内存申请失败; 1, 插入成功 *******************************************************************************************/ int insert_double_link(Node **linkp, int data, char *name) { Node *current; Node *new; while((current = *linkp) != NULL && current->data < data) { linkp = ¤t->next; } new = (Node*)malloc(LEN); /*如果申请内存失败，返回-1*/ if(new == NULL) { return -1; } new->data = data; new->name = name; /*不是尾节点*/ if(current != NULL) { new->pre = current->pre; current->pre = new; } new->next = current; *linkp = new; return 1; } /****************************************************************************************** *函数名称：int delete_double_link(Node**p, int data) *函数功能：删除升序排列的双链表中的节点 *入口参数：p, 指向链表头节点的指针的指针; data, 所删除节点的数值字段; *返回值：-1, 内存申请失败; 1, 插入成功 *******************************************************************************************/ int delete_double_link(Node**p, int data) { Node *q; q = *p; while(q->data != data )/*相当不解的是while((q->data != data) && (q != NULL))当data值不在链表中时就出错*/ { q = q->next; if (q == NULL) break; } /*所要删除的值不在链表中，返回0*/ if(q == NULL) { return 0; } #if 1 if(*p == q) { *p = (*p)->next ; (*p)->pre = NULL; } else if(q->next == NULL) { q->pre->next =NULL; //free(q); } else { q->pre->next = q->next; q->next->pre = q->pre ; } return 1; #endif } int main() { Node *p, *p2; p = create_double_link(3); insert_double_link(&p, 1, "body"); p2 = p; while(p != NULL) { printf("The node's name is %s, and data is %d/n", p->name, p->data); p = p->next; } delete_double_link(&p2, 1); while(p2 != NULL) { printf("The node's name is %s, and data is %d/n", p2->name, p2->data); p2 = p2->next; } return 0; }