第一關——鏈表

1、青銅挑戰(zhàn)——創(chuàng)建+增刪改查（c++）

1.1鏈表的內部結構

鏈表中每個結點內部的“生態(tài)環(huán)境”。

數(shù)據域存儲元素的值，指針域存放指針。
示例：

1.2鏈表的定義

struct linkNode
{
	int val;      //代表數(shù)據
	struct linkNode *next;  //代表指針
};

1.3理解C 語言里是如何構造出鏈表

c語言構造鏈表 可分為三步
1.創(chuàng)建頭指針。
2.創(chuàng)建頭結點，使頭指針指向頭結點。
3.循環(huán)創(chuàng)建結點，并使前一個結點指向當前結點。
1.）創(chuàng)建結點。
2.）使前一個結點指向當前結點。
3.）前一個結點變?yōu)楫斍肮?jié)點（為下一次循環(huán)準備）。

代碼如下：

#include <stdio.h>
#include <stdlib.h>

struct LinkNode
{
	int val;      //代表數(shù)據
	struct LinkNode *next;  //代表指針
};

struct LinkNode *initLink()
{
	//1.創(chuàng)建頭指針。
	struct LinkNode *p = NULL;
	//2.創(chuàng)建頭結點，使頭指針指向頭結點。
	struct LinkNode *temp = (struct LinkNode *)molloc(sizeof(struct LinkNode));
	p = temp;
	//3.循環(huán)創(chuàng)建結點，并使前一個結點指向當前結點。
	for(int i = 0;i < 5;i++)
	{
		 //1.)創(chuàng)建結點。
	 	struct LinkNode *a = (struct LinkNode *)malloc(struct LinkNode);
		a->val = i;
		a->next = NULL;
		//2.)使前一個結點指向當前結點。
		temp->next = a;
		//3.)前一個結點變?yōu)楫斍肮?jié)點
		temp = temp->next;
	}
	return p;
}

int main()
{
	struct LinkNode * q;
	printf("創(chuàng)建鏈表1,2,3,4");
	q = initLink();
	return 0;
}

1.4鏈表增加元素，首部、中間和尾部分別會有什么問題，該如何處理?

1.4.1 首部插入

注意：
要將新插入的結點重新設為head結點。
處理:

NewNode->next = head;
head = NewNode; 

1.4.2 中間插入

注意：
1.要在插入的前一個結點停下（這就好比一邊過河一邊拆橋，結果自己也回不去了。）
2.要先連要插入位置后面的結點（否則后面的就無法連接了）
處理:

NewNode.next = temp->next;
temp->next = NewNode; 

1.4.3 尾部插入

注意：沒什么注意的
處理:

temp->next = NewNode;

1.5鏈表刪除元素，首部、中間和尾部分別會有什么問題，該如何處理?

1.5.1 刪除首部

處理:

head = head->next; 

1.5.2 刪除中間

注意：用cur.next來比較，找到位置后，將cur->next指針的值更新為cur->next->next。
處理:

cur->next = cur->next->next;

1.5.3 刪除尾部

注意：找到要刪除位置的前一個結點并判斷 是否cur->next = 40
處理:

cur->next = NULL; 

1.6雙向鏈表是如何構造的，如何實現(xiàn)元素的插入和刪除

1.6.1 雙向鏈表的如何構造

typedef struct DoubleNode
{
	// 數(shù)據域
	int data;
	// 指向下一個結點
	struct DoubleNode *next;
	struct DoubleNode *prev;
}DoubleNode;
//創(chuàng)建新結點
DoubleNode* newNode(int data) 
{
	DoubleNode *newNode = (DoubleNode*)malloc(sizeof(DoubleNode));
	newNode->data = data;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

1.6.1 雙向鏈表的插入

頭插

與單鏈表類似。
注意：
1.讓新頭結點prev 指向 鏈表的最后Newhead->prew = head->prew。
2.新頭結點next 指向 舊的頭結點。
3. 末尾結點next 指向 新頭結點
4.舊頭結點prev 指向 新頭結點。
5.若鏈表為空，要注意額外處理。

void insertFirst(int p)
{
	DoubleNode *NewNode = (DoubleNode *)malloc(sizeof(DoubleNode));
	NewNode->data = p; 
	if(head == NULL)
		head = NewNode;
	else
	{
		NewNode->prev = head->prev;
		NewNode->next = head;
		NewNode->prev->next = NewNode;
		head->prev = NewNode;
	}
}

尾插

與頭插類似。
== 舊尾結點last = head->prew==

void insertlast(int p)
{
    DoubleNode *NewNode = (DoubleNode *)malloc(sizeof(DoubleNode));
    NewNode->data = p; 
    if(head == null){
       head = NewNode;
    }
    else
    {
 	  	NewNode->prev = head->prev;
 	  	NewNode->next = head->prev->next;
		NewNode->next->prev = NewNode;
		head->prev->next = NewNode;
	}
    return head;
}

中間插入

在某個元素之前插入元素

/*在第add位置的前面插入data節(jié)點*/
DoubleNode * InsertListHead(DoubleNode * head,int add,int data)
{
    /*新建數(shù)據域為data的結點*/
    DoubleNode * NewNode=(DoubleNode*)malloc(sizeof(DoubleNode));
    if(temp== NULL)
    {
        printf("創(chuàng)建錯誤\n");
        return NULL;
    }    
    else
    {
        NewNode->data = data;
        NewNode->prev = NULL;
        NewNode->next = NULL; 
    }
    /*插入到鏈表頭，要特殊考慮*/
    if (add==1)
    {
        NewNode->next = head;
        head->prev = NewNode;
        head = NewNode;
    }
    else
    {
        Node * body = head;
        /*找到要插入位置的前一個結點*/
        for (int i=1; i<add-1; i++)
        {
            body = body->next;
        }
        /*判斷條件為真，說明插入位置為鏈表尾*/
        if (body->next == NULL)
        {
            NewNode->prev = head->prev;
 	  		NewNode->next = head->prev->next;
			NewNode->next->prev = NewNode;
			head->prev->next = NewNode;
        }
        else
        {
            body->next->pre = NewNode;
            NewNode->next = body->next;
            body->next = NewNode;
            NewNode->pre = body;
        }
    }
    return head;
}

1.6.1 雙向鏈表的刪除

雙向鏈表的增刪改查要比單鏈表麻煩很多

頭尾刪除

頭刪

DoubleNode *deleteFirst(){
    //頭節(jié)點判空
    if(head == null){
        printf("鏈表為空，不可刪除");
        return null;
    }
    DoubleNode *temp = first;
    //第二個節(jié)點的prev指向尾節(jié)點，完成前循環(huán)
    head->next->prev = head->prev;
    //尾節(jié)點的next指向第二個節(jié)點
    head->prev->next = head->next;
    //更新頭節(jié)點
    head = head->next;
    return temp;
}

尾刪

DoubleNode *deleteLast(){
    //首先判空
    if(head == null){
        printf("鏈表為空，無法刪除");
        return null;
    }
    //快速獲取尾節(jié)點
    DoubleNode last = head->prev;
    //頭節(jié)點prev指向倒數(shù)第二個節(jié)點，完成前循環(huán)
    head->prev = last->prev;
    //倒數(shù)第二個next指向head，完成后循環(huán)
    last->prev->next = head;
    return temp;
}

刪除中間

DoubleNode * DeleteList(DoubleNode * head,int data)
{
    DoubleNode * temp = head;
    /*遍歷鏈表*/
    while (temp)
    {
        /*判斷當前結點中數(shù)據域和data是否相等，若相等，刪除該結點*/
        if (temp->data == data) 
        {
            /*判斷是否是頭結點*/
            if(temp->pre == NULL)
            {
                head = temp->next;
                temp->next = NULL;
                free(temp);
                return head;
            }
            /*判斷是否是尾節(jié)點*/
            else if(temp->next == NULL)
            {
                temp->pre->next = NULL;
                free(temp);
                return head;
            }
            else
            {
                temp->pre->next = temp->next;
                temp->next->pre = temp->pre;
                free(temp);
                return head;   
            }
        }
        //不相等就向后移動
        temp =temp->next;
    }
    printf("沒有發(fā)現(xiàn) %d!\n",data);
    return head;
}

第一次發(fā)博客，如有錯誤歡迎指正文章來源地址http://www.zghlxwxcb.cn/news/detail-609387.html

到了這里，關于《算法通關村第一關——鏈表青銅挑戰(zhàn)筆記》的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！