模拟链表、静态链表及PAT例题A1032 Sharing

ゝ一纸荒年。 2023-02-19 15:27 93阅读 0赞

[算法笔记总目录][Link 1]

## 一、链表 ##

1.  线性表分为顺序表和链表；链表由若干结点串联而成，结点在内存中的存储位置通常不连续；结点一般由数据域和指针域构成。
2.  使用malloc函数或new运算符为链表结点分配内存空间

typename* p = (typename*)malloc(sizeof(typename));
    int* p = (int*)malloc(100 * sizeof(int));
    free(p);
    typename* p = new typename;
    int* p = new int[100];
    delete(p);

1.  基本操作

//链表的基本操作
    #include <cstdio>
    #include <cstdlib>
    using namespace std;
    struct node{ //链表结点
    	int data;
    	node *next; 
    };
    //创建链表 
    node *create(int Array[]){ 
    	node *p,*pre,*head;//pre保存当前结点的前驱结点，head为头结点
    	head = new node;//创建头结点
    	head->next = NULL;//头结点不需要数据域，指针域初始为NULL
    	pre = head;//记录pre为head
    	for(int i=0;i<5;i++){ 
    		p = new node;//新建结点
    		//将Array[i]赋值给新建的结点作为数据域，也可以scanf输入
    		p->data = Array[i];
    		p->next = NULL;//新结点的指针域设为NULL
    		pre->next = p;//前驱结点的指针域设为当前新建结点的地址
    		pre = p;//把pre设为p，作为下个结点的前驱结点 
    	} 
    	return head;//返回头结点指针 
    }
    //查找元素
    //以head为头结点的链表上计数元素x的个数
    int search(node *head,int x){ 
    	int count = 0;//计数器
    	node *p = head->next;//从第一个结点开始
    	while(p != NULL){ //只要没有到链表末尾
    		if(p->data == x){ 
    			count++;//当前结点数据域为x,则count++ 
    		} 
    		p = p->next;//指针移动到下一结点 
    	} 
    	return count;//返回计数器count 
    } 
    //插入元素
    //将x插入以head为头结点的链表的第pos个位置上
    void insert(node *head,int pos,int x){ 
    	node *p = head;
    	for(int i = 0;i < pos - 1;i++){ 
    		p = p->next;//pos-1是为了到插入位置的前一个结点 
    	}
    	node *q = new node;//新建结点
    	q->data = x;//新结点的数据域为x
    	q->next = p->next;//新结点的下一个结点指向原先插入位置的结点
    	p->next = q;//前一个位置的结点指向新结点 
    } 
    //删除元素
    //删除以head为头结点的链表中的所有数据域为x的结点
    void del(node *head,int x){ 
    	node *p = head->next;//p从第一个结点开始枚举
    	node *pre = head;//pre始终保存p的前驱结点的指针
    	while(p != NULL){ 
    		if(p->data == x){ //数据域恰好为x，说明要删除该结点
    			pre->next = p->next;
    			delete(p);
    			p = pre->next; 
    		}
    		else{ //数据域不是x，把pre和p都后移一位 
    			pre = p;
    			p = p->next;
    		}
    	} 
    } 
    int main(){ 
    	int Array[5] = { 5,3,6,1,2};
    	node *L = create(Array);//新建链表，返回的头指针head赋值给L
    	L = L->next;//从第一个结点开始有数据域
    	while(L != NULL){ 
    		printf("%d",L->data);//输出每个结点的数据域
    		L = L->next; 
    	} 
    	return 0;
    }

## 静态链表 ##

前面讲解的都是动态链表，即需要指针来建立结点之间的连接关系。而对有些间题来说，  
结点的地址是比较小的整数(例如s位数的地址),这样就没有必要去建立动态链表,而应使  
用方便得多的静态链表。  
静态链表的实现原理是hash,即通过建立一个结构体数组，并令数组的下标直接表示结  
点的地址，来达到直接访问数组中的元素就能访问结点的效果。另外，由于结点的访问非常  
方便，因此静态链表是不需要头结点的。静态链表结点定义的方法如下:

//7.3.4静态链表
    struct Node{ 
    	typename data;//数据域
    	int next;//指针域 
    }node[size];

在上面的定义中，next 是一个int型的整数，用以存放下一个结点的地址(事实上就是数  
组下标)。例如，如果初始结点的地址为11111，第二个结点的地址是22222， 第三个结点的  
地址是3333且第三个结点为链表末尾，那么整个静态链表的结点就可以通过下面的写法  
连接起来:  
node\[111111 \]=22222;  
node \[22222\]=33333;  
node\[33333\]=-1; //-1 对应上一小节动态链表中的NULL表示没有后继结点  
另外一点需要注意的是， 把结构体类型名和结构体变量名设成了不同的名字(即Node与node),事实上在- -般情况下它们是可以相同的，但是由于静态链表是由数组实现的，那么就有可能需要对其进行排序，这时如果结构体类型名和结构体变量名相同，sort 函数就会报编译出错的问题，因此，在使用静态链表时，尽量不要把结构体类型名和结构体变量名取相同的名字。

[PAT例题A1032 Sharing][PAT_A1032 Sharing]  
To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, loading and being are stored as showed in Figure 1.

![fig.jpg][]

Figure 1

You are supposed to find the starting position of the common suffix (e.g. the position of i in Figure 1).

**Input Specification:**  
Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (≤105 ), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Data Next  
where Address is the position of the node, Data is the letter contained by this node which is an English letter chosen from \{ a-z, A-Z \}, and Next is the position of the next node.

**Output Specification:**  
For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output -1 instead.

Sample Input 1:

11111 22222 9
    67890 i 00002
    00010 a 12345
    00003 g -1
    12345 D 67890
    00002 n 00003
    22222 B 23456
    11111 L 00001
    23456 e 67890
    00001 o 00010

Sample Output 1:

67890

Sample Input 2:

00001 00002 4
    00001 a 10001
    10001 s -1
    00002 a 10002
    10002 t -1

Sample Output 2:

-1

作者  
CHEN, Yue  
单位  
浙江大学  
代码长度限制  
16 KB  
时间限制  
200 ms  
内存限制  
64 MB

**代码：**

//PAT例题A1032Sharing
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    const int maxn = 100010;
    struct NODE{ //静态链表 
    	char data;//数据域
    	int next;//指针域
    	bool flag;//结点是否在第一条链表中出现 
    }node[maxn];
    
    int main() { 
    	for(int i=0;i<maxn;i++){ 
    		node[i].flag = false;
    	}
    	int s1,s2,n;//s1与s2分别代表两条链表的首地址n代表结点数 
    	scanf("%d%d%d",&s1,&s2,&n);
    	int address,next;//结点地址与后继结点地址
    	char data;//数据
    	for(int i=0;i<n;i++){ //输入结点数据 
    		scanf("%d %c %d",&address,&data,&next);
    		node[address].data = data;
    		node[address].next = next;
    	} 
    	int p;
    	for(p = s1;p != -1;p = node[p].next){ 
    		node[p].flag = true;//枚举第一条链表的所有结点，令其出现次数为1 
    	}
    	for(p = s2;p != -1;p = node[p].next){ 
    		//找到第一个已经在第一条链表中出现的结点
    		if(node[p].flag == true)	break; 
    	} 
    	if(p != -1){ //如果第二条链表还没有到达结尾，说明找到了共用结点
    		printf("%05d\n",p); 
    	}
    	else{ 
    		printf("-1\n");
    	}
    	return 0;
    }

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 100010;
    struct node{ 
    	char data;
    	int next;
    	bool flag;
    }node[maxn]; 
    int main(){ 
    	for(int i;i< maxn;i++)node[i].flag =false;
    	int s1,s2,n;
    	scanf("%d %d %d",&s1,&s2,&n);
    	int address,next;
    	char data;
    	for(int i=0;i<n;i++){ 
    		scanf("%d %c %d",&address,&data,&next);
    		node[address].data =data;
    		node[address].next =next;
    	}
    	while(s1 != -1){ 
    		node[s1].flag = 1;
    		s1=node[s1].next;
    	} 
    	while(s2 != -1){ 
    		if(node[s2].flag == 1)break;
    		s2=node[s2].next;
    	} 
    	if(s2 == -1)printf("-1\n");
    	else printf("%05d\n",s2);
        return 0;
    }

[Link 1]: https://blog.csdn.net/qq_21480607/article/details/106660085
[PAT_A1032 Sharing]: https://pintia.cn/problem-sets/994805342720868352/problems/994805460652113920
[fig.jpg]: https://img-blog.csdnimg.cn/20200621144659655.png