首页 > 代码库 > 数据结构——双链表

数据结构——双链表

2024-10-26 16:16:02   206人阅读

双链表的操作

利用链表的尾插法建立双链表：

 1 void CreateDlistR(DLNode *&L,int a[],int n){
 2     DLNode *s,*r;
 3     int i;
 4     L = (DLNode *)malloc(sizeof(DLNode));
 5     L -> prior = NULL;
 6     L -> next = NULL;                        //空的双向链表
 7     r = L;                                    //r指向L的头结点也是尾结点
 8     for(i = 0;i < n;i++){
 9         s = (DLNode *)malloc(sizeof(DLNode))    
10         s -> data =http://www.mamicode.com/ a[i];
11         r -> next = s;
12         s -> peror = r;                        //双链表的相互连接操作
13         r = s;
14     }
15     r -> next =NULL;
16 }

查找结点的算法实现：

1 DLNode* findNode(DLNode *C,int x){
2     DLNode *p = C -> next;
3     while(p!=NULL){
4         if(p -> data =http://www.mamicode.com/= x)
5             break;
6         p = p ->next;                //没查找一次向右移一次
7     }
8     return p;
9 }

插入算法的实现：

1 s -> next = p -> next;
2 s -> peror = p;
3 p -> next = s;
4 s -> next -> prior = s;

删除算法的实现：

1 q = p -> next;
2 p -> next = q -> next;        //相当于p -> next = p -> next -> next
3 q -> next -> peror = p;
4 free(q);循环链表的特点：

无论是循环单链表还是循环多链表，无非就是将链表的尾部终结点与头结点相连接；循环双链表就是头结点的前驱为终结点，终结点的后继为头结点；
判断一个循环链表是否走到了尾部，只需要语句：

p -> next == head

 

数据结构——双链表


联系
我们