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

数据结构——单链表

2024-10-26 04:51:39   206人阅读

1.对于一个有数据的单链表，如果要对其初始化，使用下列操作:

技术分享 
1 void initList(sqlist &L){    #对于需要改变的变量或链表，使用引用型
2 L.length==0;
3 } 　　　　//单链表长度重置为0
View Code

2.单链表有4中操作：归并，插入，删除，查找

归并的实现：(链表A,B是有序的，且归并后的C也是有序的)如下：

技术分享 
 1 void merge(LNode *A,LNode *B,LNode *&C){        //将A B两个链表归并为一个新的单链表(链表C采用引用型)
 2         LNode *p = A -> next;                        //指向头结点后的数据，若A表示递增序列，则指向A的最小值
 3         LNode *q = B -> next;
 4         LNode *r;
 5         C = A;                                        
 6         C -> next = NULL;                            //从A中取下头结点作为C的头结点
 7         free(B);                                    //释放B的头结点（A的头结点已经给C用，B无用故释放，反之释放A）
 8         r = C;                                        //r指向C的头结点
 9 
10         while(p!=NULL&&q!=NULL){                    //为了归并后的C是有序的这里表示递增，两个链表数据均未遍历完执行循环
11             if(p -> data <= q -> data){                
12                 r -> next = p;                        
13                 p = p -> next;
14                 r = r -> next;                        //判断p小(即A链表中的数值小),p放在C头结点后，链表A,C数据均右移
15             }
16             else{
17                 r -> next = q;
18                 q = q -> next;
19                 r = r -> next;                        //q小，同上
20             }
21 
22         }
23         r -> next = NULL;                            //指向C终结点
24 
25         if(p!=NULL)                                    
26             r -> next = p;
27         if(q!=NULL)
28             r -> next = q;                            //若A,B链表有一方遍历完则执行这两句判断语句，那个链表没有遍历完，那个链表的余下数据直接按顺序连在C的终结点上即可
29         
30     }
View Code

单链表插入有两种，尾插法和头插法

假设有n个元素已经存储在数组a中。

头插法：

技术分享 
 1 void createlistF(LNode *&C,int a[],int n){
 2     LNode *s,*r;
 3     int i;
 4     C = (LNode *)malloc(sizeof(LNode));
 5     C -> next = NULL;
 6     r = C;
 7     for(i = 0;i < n;++i){
 8         s=(LNode *)malloc(sizeof(LNode));
 9         s -> data =http://www.mamicode.com/ a[i];
10         s -> next = C -> next;            //s所指新结点的指针域指向C的开始结点
11         C -> next = s;                    //头结点指针域指向s,使s再次成为开始结点
12     }
13     r -> next = NULL;            //指针域为空，就表示链表建立完成
14 }
View Code

尾插法：

技术分享 
 1 void createlistR(LNode *&C,int a[],int n){
 2     LNode *s,*r;
 3     int i;
 4     C = (LNode *)malloc(sizeof(LNode));                    //申请头结点空间
 5     C -> next = NULL;
 6     r = C;
 7     for(i = 0;i < n;++i){
 8         s=(LNode *)malloc(sizeof(LNode));                //s指向新申请的结点
 9         s -> data =http://www.mamicode.com/ a[i];                                    
10         r -> next = s;                                    //s取得的值赋给r的数据结点
11         r = r -> next;                                    //r始终指向终结点，保证了下次的数据存储始终是在尾部
12     }
13     r -> next = NULL;            //指针域为空，就表示链表建立完成
14 }
View Code

头插法的特征就是有序链表按顺序归并为新链表时会变成倒序，即递增变递减，递减变递增。
头插法的关键步骤：

1 s -> next = C -> next;
2 C -> next = s;

两个顺序不可颠倒，若颠倒则当C -> next指向s之后，之前的C -> next地址将丢失而无法被找到！

单链表插入类似这样:

技术分享

3.单链表删除：

1 q = p -> next;                //指向要删除的结点
2 p -> next = p -> next -> next;
3 free(q);                //释放指针q所指的结点时数据也会消失。这是完整的删除过程

4：单链表查找操作：

 1 int findData(LNode *C,int x){
 2     LNode *p ;
 3     p = C;
 4     while(p -> next != NULL){
 5         if(p -> next -> data =http://www.mamicode.com/= x)
 6             break;            //找到匹配项，跳出循环
 7         p = p -> next;
 8     }
 9     if(p -> next == NULL)
10         return False
11 }

 

数据结构——单链表


联系
我们