#include #include #include #include #include //定义结构体，链表中的节点 typedef struct student { int data; struct student* next;//双向链表，指向后一个节点 struct student* pre;//指向前一个节点 }dnode; typedef struct student* pnode; //创建节点，返回节点指针 //输入：节点的值 //输出：节点的指针 pnode createNode(int n) { pnode p=NULL; p=(pnode)malloc(sizeof(dnode)); p->next =NULL; p->pre = NULL; p->data =n; return p; } //在链表中按 data 升序插入节点 //输入：链表头指针，节点指针 //输出：链表头指针 pnode insert(pnode head,pnode temp) { pnode p=NULL; pnode k=NULL;// if(NULL==temp)//如果插入空节点，直接退出返回头节点指针 { return head; } if(NULL==head)//如果头指针为空， { head = temp;//节点就作头 }else { if(head->data > temp->data) {//如果头指针的值大于插入节点的值 //节点插入到最前面作为头节点 temp->next = head; head->pre = temp; head = temp; }else { p = head->next;//从第二个节点开始比较 k = head; while(NULL!=p) {//如果插入节点值比当前节点值小，那插入到当前节点前面 //如果比当前节点值大，那么与下一节点值比较 if(temp->data < p->data) { k = p->pre;//记住当前节点的前一节点 temp->next = p;//新插入节点的后节点是当前节点 p->pre = temp;//当前节点的前一节点是新插入节点 k->next = temp; temp->pre =k; break;//节点插入，退出比较 }else { p = p->next;//下一节点 k=p; } } if(NULL==p)//此条件成立,插入节点值比最后一个节点值大，节点插入到最后面 {//此时 k 是最后面节点 k->next =temp; temp->pre =k; } } } return head;//返回头节点指针 } //创建双链表 //返回链表头指针 pnode create() { pnode head=NULL,p=NULL; int x,cycle=1; while(cycle) { printf("\n 输入整数值(输入0 结束链表的创建):"); scanf("%d",&x); if(x!=0) { p=createNode(x);//创建一个节点 head = insert(head,p);//在链表中加入一个节点。按照升序的方式加入 }else { cycle=0;//此条件退出 while 循环 } } return head;//返回新建链表的头指针 } //得到双链表的深度，双链表中有多少个节点 //输入参数：双链表的头指针 //输出：双链表的节点个数 int length(pnode head) { int n=0; pnode p=head; while(NULL!=p) { p=p->next; n++; } return n; } //输出双链表 //输入参数：双链表头指针 void print(pnode head) { pnode p=head; int n=0; n=length(head); if(0==n) { printf("\n 链表里面没有节点"); return; }else { printf("\n 共有%d 个节点：",n); while(NULL!=p) { printf("\n%d",p->data); p=p->next; } } } //主函数 int main(int argc, char* argv[]) { pnode head=NULL; int n=0; head = create();//创建链表 print(head);//显示链表 system("pause"); return 0; }
