数据结构持续总结ing
//初始化、判空、在p结点之后插入s结点、删除p结点的后继结点、销毁双链表 //尾插法建立双链表、头插法建立双链表、输出 #include <stdio.h> #include <stdlib.h>//malloc,free函数库 typedef int ElemType;//int另命名 typedef struct DNode{ ElemType data; struct DNode *prior,*next;//前驱和后继指针 }DNode,*DLinkList; bool InitDLinkList(DLinkList &L){//初始化 L=(DNode *)malloc(sizeof(DNode));//分配一个头结点 if(L==NULL) return false; L->prior=NULL;//头结点的prior永远指向NULL L->next=NULL;//头结点之后暂时还没有结点 return true; } bool Empty(DLinkList L){//判空（带头结点） if(L->next==NULL) return false; else return true; } bool InsertNextNode(DNode *p,DNode *s){//在p结点之后插入s结点 if(p==NULL || s==NULL)//非法参数 return false; s->next=p->next;//s的next指针指向p的下一个结点 if(p->next !=NULL)//如果p结点有后继结点 p->next->prior=s;//p的下一个结点的prior指针指向s s->prior=p;//s的prior指针指向p结点 p->next=s;//p的next指针指向s结点 return true; } bool DeleteNextDNode(DNode *p){//删除p结点的后继结点 if(p==NULL)//非法参数 return false; DNode *q=p->next;//找到p的后继结点q if(q==NULL)//p没有后继 return false; p->next=q->next;//p的next指针指向q的下一个结点 if(q->next !=NULL)//q结点不是最后一个结点 q->next->prior=p;//q的下一个结点的prior指针指向p free(q);//释放结点空间 return true; } void DestoryList(DLinkList &L){//销毁双链表 while(L->next !=NULL)//循环释放各个数据结点 DeleteNextDNode(L); free(L);//释放头结点 注意：销毁表时才能删除头结点 L=NULL;//头指针指向NULL } //1、后向遍历 //while(p!=NULL) // p=p->next; //2、前向遍历 //while(p!=NULL) // p=p->prior; //3、前向遍历（跳过头结点） //while(p->prior!=NULL) // p=p->prior; DLinkList List_TailInsert(DLinkList &L){//尾插法建立双链表（带头结点） int x; L=(DLinkList)malloc(sizeof(DNode));//建立头结点,注意此处返回的是DLinkList，初始化空表 DNode *s; DNode *r=L;//r为表尾指针 scanf("%d",&x);//输入结点的值 while(x!=999){ s=(DNode *)malloc(sizeof(DNode));//创建新结点（此时s结点已在循环体外声明） s->data=x; r->next=s; s->prior=r; r=s;//r指向新的表尾结点 scanf("%d",&x); } r->next=NULL;//尾结点指针置空 return L; } DLinkList List_HeadInsert(DLinkList &L){//头插法建立双链表（带头结点） DNode *s; int x; L=(DLinkList)malloc(sizeof(DNode));//创建头结点 L->next=NULL;//初始化为空链表，养成好习惯，只要是初始化链表，都应该先把头指针指向NULL L->prior=NULL;//初始化 scanf("%d",&x); while(x!=9999){ s=(DNode *)malloc(sizeof(DNode));//创建新结点（此时s结点已在循环体外声明） s->data=x; s->next=L->next; if(L->next!=NULL)//双链表不为空，L的下一个结点的prior指针指向s L->next->prior=s; L->next=s;//将新结点插入表中，L为头指针 s->prior=L;//s的prior指针指向L scanf("%d",&x); } return L; } void DispList(DLinkList L){//输出 int i=1; DNode *p=L->next;//定义一个结点指针p指向头结点的下一个结点 while(p!=NULL){ //如果p不为空则循环 printf("第%d个元素为%d\n",i,p->data); p=p->next;//移动指针p遍历链表 i++; } } int main(){ DLinkList L; List_HeadInsert(L); DispList(L); }