顺序表和链表

 1 /*
 2   问题描述：
 3   给定一个键值为整数的单链表 L， 将键值的绝对值有重复的结点删除： 
 4   即对任意键值 K， 只有键值或其绝对值等于 K 的第一个结点被保留在 L 中。 
 5   例如， 下面单链表 L 包含键值 21、-15、 15、 7、 -15， 去重后的链表 L 包含键值 21、 -15、 7
 6   
 7   输入说明：
 8   输入的第一行包含两个整数， 分别表示链表第一个结点的地址和结点个数 n（1≤n≤100）。 
 9   结点地址是一个非负的 5 位整数， NULL 指针用-1 表示。
10   随后 n 行， 每行含 3 个整数， 按下列格式给出一个结点的信息：
11   Address Key Next
12   其中 Address 是结点的地址， Key 是绝对值不超过 10000 的整数， Next 是下一个结点的地址。
13   
14   输出说明：
15   输出的第一行为去重后链表 L 的长度， 换行； 接下来按顺序输出 L 的所有结点， 每个结点
16   占一行， 按照 Address Key Next 的格式输出， 间隔 1 个空格
17   
18   测试样例：
19   输入样例 1
20   00100 5
21   99999 7 87654
22   23854 -15 00000
23   87654 -15 -1
24   00000 15 99999
25   00100 21 23854
26   输出样例 1
27   3 
28   00100 21 23854
29   23854 -15 99999
30   99999 7 -1
31   
32     参考了CSDN后考虑数组模拟链表的方法,也就是静态链表法，其实课本上也有，没注意看到，，，；静态链表法同样有基本操作的实现；可以看到整个代码的实现是非常简洁的
33  */
34 #include<stdio.h>
35 #include<stdlib.h>
36 #include<math.h>
37 
38 struct
39 {
40     int key;
41     int next;
42 }Initarr[100000];//建立数组结构体，结构体内存键值和下一个结点的地址，而数组下标用来代替首地址
43 
44 int first_address,i,n,finalarr[100000],repeat[100000];//建立两个数组，一个是输出的final数组，一个是判断重复键值的repeat数组
45 
46 int main()
47 {
48     int len=0;
49     scanf("%d %d",&first_address,&n);
50     for(i=0;i<n;i++)
51     {
52         int a,b,c;
53         scanf("%d %d %d",&a,&b,&c);
54         Initarr[a].key=b;
55         Initarr[a].next=c;//将三个量存进去，这里用数组模拟链表，也就是数组实现静态链表，其实访问数组某元素也是访问他的内存头地址，类似的道理
56         
57     }
58     for(i=first_address;i>-1;i=Initarr[i].next)//for循环实现一个连续的遍历，从first_addrest到Initarr[].next存的地址（数组下标）最后到-1终止
59     {
60         int key=abs(Initarr[i].key);//取绝对值
61         if(repeat[key]==0)//这里用0,1标识是否重复，由于比较的是相同key（取绝对值了）,所以repeat数组下标用key来指定唯一位置
62         {
63             repeat[key]=1;
64             finalarr[len++]=i;//不重复就把首地址存到final数组中，输出用
65         }
66         //不满足条件的话就会继续循环，当然也可以把剔除的存到另一个数组，用else分支写
67     }
68     printf("%d\n",len);
69     for(i=0;i<len;i++)
70     {
71         printf("%05d %d ",finalarr[i],Initarr[finalarr[i]].key);//先按格式输出首地址和键值；首地址按顺序存在final数组中，键值直接访问Init即可
72         if(i==len-1)
73             printf("-1\n");
74         else
75             printf("%05d\n",finalarr[i+1]);//显然next结点地址在i+1里
76         
77     }
78     
79     return 0;
80 }

  4 // Created by Administrator on 2023/10/27/027.
  5 //
  6 
  7 /*试题名称    反转链表
  8 时间限制:    2 秒
  9 内存限制:    256KB
 10 
 11 问题描述
 12 输入一个链表，反转链表后，输出链表的所有元素。
 13 
 14 输入说明
 15 输入第一行为整数n（n>=1),代表测试链表数。
 16 从第二行开始每行表示一个链表，其中第一个数据表示链表中数据个数，其余数据表示要测试的链表中的数据，均为整数。
 17 
 18 输出说明
 19 每一行对应一个链表反转后的元素。
 20 
 21 输入样例
 22 3
 23 5 1 2 3 4 5
 24 3 2 4 5
 25 1 3
 26 
 27 输出样例
 28 5 4 3 2 1
 29 5 4 2
 30 3
 31 
 32 
 33 这个方法选取的是：
 34  直接用头插法建立单链表然后从头指针往后读取即可
 35  直接输出的话有个问题就是他会更新单链表，所以需要一个存储链表头指针的数组-》这个适用于你想要输入完全部再统一输出的情况，事实上直接输入一遍后输出一边oj不会管
 36  第二个问题是在oj里超时了
 37 
 38  提交成功后加了一些printf语句打印方便观看，用于oj可以注释掉

 39 */
 40 
 41 #include <stdio.h>
 42 #include <stdlib.h>
 43 
 44 typedef struct node
 45 {
 46     int data;
 47     struct node *next;
 48 }Linklist;
 49 
 50 Linklist* headCreate(int  len)
 51 {
 52     Linklist *head,*newData;
 53     int my_data,i=0;
 54     head=(Linklist*)malloc(sizeof(Linklist));
 55     head->next=NULL;
 56     head->data=len;
 57     for(i=0;i<len;i++)
 58     {
 59         newData=(Linklist*) malloc(sizeof(Linklist));
 60         scanf("%d",&my_data);
 61         newData->data=my_data;
 62         newData->next=head->next;
 63         head->next=newData;
 64        //要注意到头插法的特点是先进的在队尾，新的元素不断接在头结点的后面称为第一结点
 65     }
 66     return head;
 67 }
 68 
 69 void Visit_Linklist(Linklist *head)
 70 {
 71     Linklist *find;
 72     find=head->next;
 73     while(find!=NULL)
 74     {
 75         printf("%d\t",find->data);
 76         find=find->next;
 77     }
 78     printf("\n");
 79 }
 80 
 81 int main()
 82 {
 83     int sum,cnt,singleLen;
 84     printf("请输入总的链表数：\n");
 85     scanf("%d",&sum);
 86 
 87     Linklist ** lists = (Linklist **)malloc(sum * sizeof(Linklist *));//新建一个数组来存取每次的头指针，并用下标给定他唯一的标识符
 88     //注意这个写法
 89     printf("请输入每个链表的元素数和元素：\n");
 90     for(cnt=0;cnt<sum;cnt++)
 91     {
 92         scanf("%d",&singleLen);
 93         lists[cnt]=headCreate(singleLen);
 94     }
 95 
 96     printf("反转后的链表是：\n");
 97     for(cnt=0;cnt<sum;cnt++)
 98     {
 99         Visit_Linklist(lists[cnt]);
100     }
101 
102     //或者写成下面的输出也行：
103     /* 把list那个注释掉
104      * for(cnt=0;cnt<sum;cnt++)
105     {
106         scanf("%d",&singleLen);
107         Linklist *head=headCreate(singleLen);
108         Vist_Linklist(head);
109     }
110     */
111 
112 
113     /*
114      1.在函数headCreate()中，使用了一个循环来读取输入数据并创建链表节点。
115        但是在每次循环时都调用getchar()来读取字符直到遇到换行符，这可能会导致程序在等待输入时耗费大量时间。（这个有可能是主要原因）
116        建议改为使用scanf函数读取整数，并在输入结束后清空缓冲区。
117 
118        尝试改进后重新试下oj超时的问题
119 
120        事实上验证了确实是这个getchar的问题，本来用的课本的例程代码，不过显然没考虑具体题目的时间限制情况
121      */
122 
123     return 0;
124 
125 
126 }

 1 //
 2 // Created by Administrator on 2023/10/27/027.
 3 //这个方法考虑的是尾插创建单链表再头插建新链表输出，实现倒序，可以看出尾插类似队列，头插类似栈
 4 #include <stdio.h>
 5 #include <stdlib.h>
 6 
 7 typedef struct node
 8 {
 9     int data;
10     struct node *next;
11 }Linklist;
12 
13 Linklist* reverseLinklist(Linklist *head)//反转链表，换为头插法
14 {
15     Linklist *new_head,*current;
16     new_head=NULL;
17     current=head;
18     while (current != NULL) {
19         Linklist * nextNode = current->next;//更新，将nextnode指针指向现指针指向位置的下一个结点（存储下一个结点的信息）
20         current->next = new_head;//将现指针的后继指针指向新链表的头指针，如一开始是指向NULL，下一次是指向上一个填入的结点
21         new_head = current;//更新头指针，新链表头指针指向现指针指向的结点，即赋值插入元素，由于上一步已经有current->next=newhead，实际完成了链接！
22         current = nextNode;//移动现指针到指向原链表的下一结点
23     }
24 
25     return new_head; // 返回新的头结点
26 }
27 
28 void Visit_Linklist(Linklist *head)
29 {
30     Linklist *find;
31     find=head;
32     while(find!=NULL)
33     {
34         printf("%d\t",find->data);
35         find=find->next;
36     }
37     printf("\n");
38 }
39 
40 int main()
41 {
42     int n; // 测试链表数
43     scanf("%d", &n);
44     int i,j;
45     for (i = 0; i < n; i++)
46     {
47         int len; // 链表长度
48         scanf("%d", &len);
49         Linklist *head,*tail;
50         head=NULL;
51         tail=NULL;
52         for (j = 0; j < len; j++)
53         {
54             int my_data;//尾插法存数据
55             Linklist *newData;
56             newData=(Linklist*) malloc(sizeof(Linklist));//给存储数据的新临时结点开辟空间
57             scanf("%d",&my_data);
58             newData->data=my_data;
59             if(head==NULL)//没有头结点，空表，头指针指向第一个填入的元素
60                 head=newData;
61             else
62                 tail->next=newData;//非空表，head不指向空，那么就讲tail后继指向新结点实现连接
63             tail=newData;//不管是空表的第一种情况，还是后续的非空表，都要有尾指针指向新临时结点
64         }
65         if(tail!=NULL)
66             tail->next=NULL;//尾插法单链表，最后尾指针后继指向空
67 
68         head=reverseLinklist(head);
69         Visit_Linklist(head);
70 
71         //可以在后面补一个释放内存的把链表内存释放了，养成好习惯
72     }
73 
74 }