数据结构——链表的使用

以你之姓@ 2022-07-11 13:45 110阅读 0赞

一如既往的打不开AOJ...题目如图。但是这篇不是题目为主的，主要讲一下链表的理解。  
我感觉是栈—>队列—>链表，都有联系。下面我讲的是双向链表。

划重点：双向链表的结点是结构体（有数据本体，指向前后元素得指针组成）。这些结构体通过指针链接成一个链，就形成了双向链表。

1.双向链表的结点

struct Node
    {
    	int key;
    	Node *next,*prev;
    };

2.初始化双向链表

Node *nil;
    void init()
    {
    	nil=(Node*)malloc(sizeof(Node));
    	nil->next=nil;
    	nil->prev=nil;
    }

3.往双向链表中插入元素

void insert(int key)
    {
    	Node *x=(Node*)malloc(sizeof(Node));
    	x->key=key;
    	//在头结点后添加元素 
    	x->next=nil->next;
    	nil->next->prev=x;
    	nil->next=x;
    	x->prev=nil;
    }

4.在双向链表中搜索元素

Node* listSearch(int key)
    {
    	Node *cur=nil->next;//从头结点后面的元素开始访问
    	while(cur!=nil&&cur->key!=key)
    	{
    		cur=cur->next;
    	} 
    	return cur;
    }

5.从双线链表中删除元素

void deleteNode(Node *t)
    {
    	if(t==nil)return;//t为头结点时不做处理
    	t->prev->next=t->next; 
    	t->next->next=t->prev; 
    	free(t);
    }
    void deleteFirst()
    {
    	deleteNode(nil->next);
    }
    void deleteLast()
    {
    	deleteNode(nil->prev);
    }
    void deleteKey(int key)
    {//删除搜索到的结点 
    	deleteNode(listSearch(key));
    }

![20170131213735793][]

**AOJ ALDS1\_3\_C**

![20170131212929961][]

![20170131212935929][]

**注意点**  
**1.我发现C++的头文件都是把".h"去了前面加个"c"也...（比如\#include <cstdio>就是\#include <stdio.h>）  
2.NIL与NULL这两个值都表示“空”。  
3.scanf比cin输入效率更高。**

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    struct Node
    {
    	int key;
    	Node *next,*prev;
    }; 
    Node *nil;
    Node* listSearch(int key)
    {
    	Node *cur=nil->next;//从头结点后面的元素开始访问
    	while(cur!=nil&&cur->key!=key)
    	{
    		cur=cur->next;
    	} 
    	return cur;
    }
    void init()
    {
    	nil=(Node*)malloc(sizeof(Node));
    	nil->next=nil;
    	nil->prev=nil;
    }
    void printList()
    {
    	Node *cur=nil->next;
    	int isf=0;
    	while(1)
    	{
    		if(cur==nil)break;
    		if(isf++>0)
    		printf(" ");
    		printf("%d",cur->key);
    		cur=cur->next; 
    	}
    	printf("\n");
    }
    void deleteNode(Node *t)
    {
    	if(t==nil)return;
    	t->prev->next=t->next; 
    	t->next->next=t->prev; 
    	free(t);
    }
    void deleteFirst()
    {
    	deleteNode(nil->next);
    }
    void deleteLast()
    {
    	deleteNode(nil->prev);
    }
    void deleteKey(int key)
    {//删除搜索到的结点 
    	deleteNode(listSearch(key));
    }
    void insert(int key)
    {
    	Node *x=(Node*)malloc(sizeof(Node));
    	x->key=key;
    	//在头结点后添加元素 
    	x->next=nil->next;
    	nil->next->prev=x;
    	nil->next=x;
    	x->prev=nil;
    }
    int main()
    {
    	int key,n,i;
    	int size=0;
    	char com[20];
    	int np=0,nd=0;
    	scanf("%d",&n);
    	init();
    	for(i=0;i>n;i++)
    	{
    		scanf("%s%d",com,&key);//使用效率更到的输入函数 
    		if(com[0]=='i')
    		{
    			insert(key);
    			np++;size++;
    		}
    		else if(com[0]=='d')
    		{
    			if(strlen(com)>6)
    			{
    				if(com[6]=='F')
    				deleteFirst();
    				else if(com[6]=='L')
    				deleteLast();
    			}
    			else
    			{
    				deleteKey(key);
    				nd++;
    			}
    			size--;
    		}
    	}
    	printList();
    	return 0;
    }

[20170131213735793]: /images/20220711/57436c15ee3a4a1ca4f69badf54c87f0.png
[20170131212929961]: /images/20220711/4ec8fb355a2f4cbfb098ca024c6406a8.png
[20170131212935929]: /images/20220711/c8728144d0954b93bdd4e1284d882dd5.png