链表和模拟链表

一. 采用指针和动态分配函数实现的单链表

1.头指针，头结点，单链表

（1）头指针：由于线性表的第一个结点无直接前驱，所以设立一个头指针指向第一个结点；线性表的最后一个结点没有直接后继，应指向空“NULL”

（2）头结点：为了操作的统一和方便，在单链表的第一个结点之前，附设一个头结点，头结点的数据域可以存储单链表的长度等信息，也可以为空

（3）“带头结点的空单链表”和“带头结点的单链表”

2.单链表及其插入操作（暂时照搬）

 1 #include
 2 #include    //结构体需要此文件 
 3 struct node{
 4     int data;                    
 5     struct node *next;            //下一个结点也是结构体结点 
 6 }; 
 7 
 8 int main(){
 9     struct node *p, *q, *t, *head;
10     int i, n, a;
11     scanf("%d",&n);                 
12     
13     head = NULL;    //头指针为空 
14     //初始化链表 
15     printf("输入%d个数据：",n);
16     for(int i = 1; i <= n; i++){
17         scanf("%d",&a);
18         p = (struct node *)malloc(sizeof(struct node));         
19         p->data = a;
20         p->next = NULL;
21         //判断p是否是头结点，头指针->头结点 
22         if(head == NULL)
23             head = p;
24         else
25             q->next = p;
26         
27         q = p;
28     }
29     //插入操作 
30     printf("输入插入的数字：");
31     scanf("%d",&a);
32     t = head;
33     while(t != NULL){            //从前往后遍历单链表 
34         if(t->next == NULL||t->next->data > a){
35             p = (struct node *)malloc(sizeof(struct node));
36         
37             p->data = a;
38             p->next = t->next;
39             t->next = p;
40             break;
41         }
42         t = t->next;            //将下个结点的地址信息赋给t，继续遍历链表 
43     }
44     //输出链表 
45     printf("插入后的链表：");
46     t = head;
47     while(t != NULL){
48         printf("%d ",t->data);
49         t = t->next;
50     }
51     return 0;
52 }

二. 用数组模拟的单链表

1.两个数组模拟

（1）data数组：存放序列中的具体数字

（2）right数组：存放当前序列中每一个元素右边的元素在data数组中的位置。

2.代码实现（暂时照搬）

 1 #include
 2 int main(){
 3     int data[101], right[101];
 4     int n, t, len;
 5     printf("输入长度："); 
 6     scanf("%d",&n);
 7     len = n;
 8     printf("输入%d个数字：",n);
 9     for(int i = 1; i <= n; i++){
10         scanf("%d",&data[i]);
11     }
12     
13     //right数组存储的是data数据右边的元素序号 
14     for(int i = 1; i <= n; i++){
15         if(i != n){
16             right[i] = i + 1;
17         }
18         else
19             right[i] = 0;     //data数组的最后一个元素的右边元素为空，所以为0 
20     }
21     
22     printf("输入插入的数："); 
23     scanf("%d",&data[++len]);        //len = len + 1，已经不是n了，变为了n+1 
24     //遍历并插入，是整个模拟链表最关键的地方 
25     t = 1;
26     while(t != 0){
27         if(data[right[t]] > data[len]){            //判断当前结点的下一个结点是否大于待插入数 
28             right[len] = right[t];                //新插入数的下一个结点的标号 = 当前结点的下一个结点的编号 
29             right[t] = len;                        //将当前结点的下一个结点的编号就是新插入数的编号 
30             break;
31         }
32         t = right[t];                            //当前结点的下一个结点编号赋值给t 
33     } 
34     
35     printf("插入新数后的链表："); 
36     t = 1;
37     while(t != 0){
38         printf("%d ",data[t]);
39         t = right[t];
40     } 
41     return 0;
42 }

啊哈算法

链表和模拟链表

相关

标签