C语言实现数据结构和双向链表操作

数据结构  双向链表的实现

双向链表中的每一个结点都含有两个指针域，一个指针域存放其后继结点的存储地址，另一个指针域则存放其前驱结点的存储地址。

双向链表结点的类型描述：

//双向链表的类型描述 
typedef int ElemType; 
typedef struct node{ 
 ElemType data; 
 struct node *prior,*next; 
}DuLNode,*DuLinkList; 

 其中，prior域存放的是其前驱结点的存储地址，next域存放的是其后继结点的存储地址。

双向链表有两个特点：

一是可以从两个方向搜索某个结点，这使得链表的某些操作（如插入和删除）变得比较简单； 二是无论利用前链还是后链都可以遍历整个双向链表。

        双向链表的操作基本和单链表的操作相同；

        1. 头插法创建带头结点的双向链表Create_DLinkListF(int n)

//头插法创建带头结点的双向链表 
DuLinkList Create_DLinkListF(int n){ 
 DuLinkList L,p; 
 int i = n - 1; 
 ElemType x; 
 //新建头结点 
 L = (DuLinkList)malloc(sizeof(DuLNode)); 
 L->prior = NULL; 
 L->next = NULL; 
 
 //添加第一个结点 
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 L->next = p; 
 p->prior = L; 
 p->next = NULL; 
 
 //加入其他结点 
 while(i > 0){ 
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 
 p->next = L->next; 
 L->next->prior = p; 
 p->prior = L; 
 L->next = p; 
 
 i--; 
 } 
 return L; 
} 

         2. 尾插法创建带头结点的双向链表Create_DLinkListR(int n)

//尾插法创建带头结点的双向链表 
DuLinkList Create_DLinkListR(int n){ 
 DuLinkList L,p,lastNode; 
 int i = n - 1; 
 ElemType x; 
 //新建头结点 
 L = (DuLinkList)malloc(sizeof(DuLNode)); 
 L->prior = NULL; 
 L->next = NULL; 
 
 //添加第一个结点 
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 L->next = p; 
 p->prior = L; 
 p->next = NULL; 
 
 lastNode = p; 
 //加入其他结点 
 while(i > 0){ 
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 
 lastNode->next = p; 
 p->prior = lastNode; 
 p->next = NULL; 
 
 lastNode = p; 
 i--; 
 
 } 
 return L; 
 
} 

3. 在指定结点之前插入新结点Insert_DLinkListBefore(DuLinkList p,ElemType x)

//在指定结点之前插入新结点 
void Insert_DLinkListBefore(DuLinkList p,ElemType x){ 
 DuLinkList newNode; 
 //判断结点p之前的结点的合法性： 
 if(p->prior == NULL) 
 printf("结点不合法，不能在该结点之前插入结点\n"); 
 else{ 
 newNode = (DuLinkList)malloc(sizeof(DuLNode)); 
 newNode->data = x; 
 
 newNode->next = p; 
 p->prior->next = newNode; 
 newNode->prior = p->prior; 
 p->prior = newNode; 
 } 
} 

4. 在指定结点之后插入新结点Insert_DLinkListAfter(DuLinkList p,ElemType x)

//在指定结点之后插入新结点 
void Insert_DLinkListAfter(DuLinkList p,ElemType x){ 
 
 DuLinkList newNode; 
 newNode = (DuLinkList)malloc(sizeof(DuLNode)); 
 newNode->data = x; 
 
 //当插入位置是最后一个结点之后时 
 if(p->next == NULL){ 
 p->next = newNode; 
 newNode->prior = p; 
 newNode->next = NULL; 
 } 
 else{ 
 newNode->next = p->next; 
 p->next->prior = newNode; 
 p->next = newNode; 
 newNode->prior = p; 
 } 
} 

5. 删除指定结点Delete_DLinkList(DuLinkList p)

//删除指定结点 
void Delete_DLinkList(DuLinkList p){ 
 //如果删除的是最后一个元素 
 if(p->next == NULL) 
 p->prior->next = NULL; 
 
 else{ 
 p->prior->next = p->next; 
 p->next->prior = p->prior; 
 
 } 
 free(p); 
} 

6. 后链输出双向链表Print_DLinkListN(DuLinkList L)

//后链输出双向链表 
void Print_DLinkListN(DuLinkList p){ 
 
 while(p != NULL){ 
 printf("%d\t",p->data); 
 p = p->next; 
 } 
 printf("\n"); 
 
} 

  7.前链输出双向链表Print_DLinkListP(DuLinkList p)

//前链输出双向链表 
void Print_DLinkListP(DuLinkList p){ 
 
 while(p != NULL){ 
 printf("%d\t",p->data); 
 p = p-prior; 
 } 
 printf("\n"); 
} 
 

至于双向链表的其他操作，如定位，和单链表的操作类同，不再赘述。

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！