PAT---链表题总结

转载

对于有些问题来说，结点的地址是比较小的整数（例如5位数的地址），这样就没有必要去建立动态链表。

静态链表：实现原理是hash，通过建立一个结构体数组，并令数组的下标直接表示结点的地址，静态链表不需要头结点。

使用静态链表时，尽量不要把结构体类型名和结构体变量名取成相同的名字。（影响到了sort函数）

二叉树静态实现

• 二叉树结构定义（注意结构体类型名和结构体变量名不同哦，影响到sort（）调用了）

struct Node{
   
	int address;//结点地址 
	int data;//数据域 
	int next;//指针域 
	XXX;//结点的某个性质，不同题目会有不同的设置 
}node[10005];

• 初始化

//对静态链表进行初始化,将其定义为达不到的数字 
for(int i=0;i<maxn;i++){
   
	node[i].XXX=0;
}

• 标记不在链表上的数据

int p=begin,count=0;
while(p!=-1){
    //-1代表链表结束 
	XXX=1;
	count++;
	p=node[p].next;
}

int count = 0;
for (int p = head; p != -1; p = node[p].next){
   
    node[p].XXX = 1;
    count++;
}

• 链表排序

bool cmp(Node a,Node b){
   
	if(a.XXX==-1||b.XXX==-1)
	//至少一个结点时无效结点，就把它放到数组后面
 	return a.XXX>b.XXX;
 	else{
   
	//第二级排序 
	}
}

题目链接

1032 Sharing (25)

1052 Linked List Sorting (25)

1097 Deduplication on a Linked List (25)

1133 Splitting A Linked List (25)

动态链表

• 头结点：数据域不存放任何内容，指针域指向第一个数据域有内容的结点
• 最后一个节点的指针域指向 NULL，表示链表结尾

(1) 创建链表

node *p, *pre, *head;
head  = new node();
head->next = NULL;
pre = head;
for (int i = 0; i < n; i++){
   
    p = new node;
    p->data = data[i];
    p->next = NULL;
    pre->next = p;
    pre = p;
}

(2) 查找元素

// 查找链表中 x 并记录个数
node *p = head->next;
while (p != NULL){
   
    if (p->data == x){
   
        count++;
    }
    p = p->next;
}

(3) 插入元素

// 将 x 插入链表第 pos 个位置
node *p = head;
for (int i = 0; i < pos-1; i++){
   
    p = p->next;
}
node *q = new node;
q->data = x;
q->next = p->next;
p->next = q;

(4) 删除元素

// 删除链表中数据域为 x 的结点
node *p = head->next;
node *pre = head;
while (p != NULL){
   
    if (p->data = x){
   
        pre->next = p->next;
        delete(p);
        p = pre->next;
    }
    else{
   
        pre = p;
        p = p->next;
    }
}