成人app

單鏈表二

點擊打開在線編譯器,邊學邊練

(續接前文)

1.   遍歷單鏈表(打印,修改)

成人app便利的概念想必大家都不會陌生,即就是從鏈表的頭開始,逐步向后進行每一個元素的訪問,這就是遍歷,對于遍歷操作,我們可以衍生出很多常用的數據操作,比如說查詢元素,修改元素,獲取元素個數,打印整個鏈表數據等等。

成人app進行遍歷的思路極其簡單,只需要建立一個指向鏈表L的結點,然后沿著鏈表L逐個向后搜索即可。

成人app對于遍歷操作,以下是代碼實現:

//便利輸出單鏈表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d個元素的值為:%d\n",++i,p->data);
        p=p->next;
    }
}

對于元素修改操作,以下是代碼實現:

//鏈表內容的修改,再鏈表中修改值為x的元素變為為k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}

簡單的遍歷設計的函數只需要void無參即可,而當我們需要進行元素修等涉及到元素操作時,我們可以設計一個LinkedList類型的函數,使其返回一個修改后的新鏈表。

成人app以上的操作均用到了遍歷的思維,針對于遍歷還有非常多的用法供自主設計,請參考后文配套的習題進行練習。

2.   插入操作

鏈表的增加結點操作主要分為查找到第i個位置,將該位置的next指針修改為指向我們新插入的結點,而新插入的結點next指針指向我們i+1個位置的結點。其操作方式可以設置一個前驅結點,利用循環找到第i個位置,再進行插入。

成人app如圖,在DATA1和DATA2數據結點之中插入一個NEW_DATA數據結點:

從原來的鏈表狀態

31.png


到新的鏈表狀態:

32.png


以下是代碼實現:

//單鏈表的插入,在鏈表的第i個位置插入x的元素
 
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre為前驅結點
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i個位置的前驅結點
    }
    Node *p;                                //插入的結點為p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
 
    return L;
}

3.  刪除操作

刪除元素要建立一個前驅結點和一個當前結點,當找到了我們需要刪除的數據時,直接使用前驅結點跳過要刪除的結點指向要刪除結點的后一個結點,再將原有的結點通過free函數釋放掉。

參考如圖

33.png


以下是代碼實現:

//單鏈表的刪除,在鏈表中刪除值為x的元素
 
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre為前驅結點,p為查找的結點。
    p = L->next;
    
    while(p->data != x) {              //查找值為x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //刪除操作,將其前驅next指向其后繼。
    free(p);
    
    return L;
}


4.  附:完整實現代碼

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

//定義結點類型
typedef struct Node {
	int data;           //數據類型,你可以把int型的data換成任意數據類型,包括結構體struct等復合類型
	struct Node *next;          //單鏈表的指針域
} Node,*LinkedList;

//單鏈表的初始化
LinkedList LinkedListInit() {
	Node *L;
	L = (Node *)malloc(sizeof(Node));   //申請結點空間
	if(L==NULL){	//判斷申請空間是否失敗
		exit(0);	//如果失敗則退出程序
	}
	L->next = NULL;          //將next設置為NULL,初始長度為0的單鏈表
	return L;
}


//單鏈表的建立1,頭插法建立單鏈表
LinkedList LinkedListCreatH() {
	Node *L;
	L = (Node *)malloc(sizeof(Node));   //申請頭結點空間
	L->next = NULL;                      //初始化一個空鏈表

	int x;                         //x為鏈表數據域中的數據
	while(scanf("%d",&x) != EOF) {
		Node *p;
		p = (Node *)malloc(sizeof(Node));   //申請新的結點
		p->data = x;                     //結點數據域賦值
		p->next = L->next;                    //將結點插入到表頭L-->|2|-->|1|-->NULL
		L->next = p;
	}
	return L;
}


//單鏈表的建立2,尾插法建立單鏈表

LinkedList LinkedListCreatT() {
	Node *L;
	L = (Node *)malloc(sizeof(Node));   //申請頭結點空間
	L->next = NULL;                  //初始化一個空鏈表
	Node *r;
	r = L;                          //r始終指向終端結點,開始時指向頭結點
	int x;                         //x為鏈表數據域中的數據
	while(scanf("%d",&x) != EOF) {
		Node *p;
		p = (Node *)malloc(sizeof(Node));   //申請新的結點
		p->data = x;                     //結點數據域賦值
		r->next = p;                 //將結點插入到表頭L-->|1|-->|2|-->NULL
		r = p;
	}
	r->next = NULL;

	return L;
}


//單鏈表的插入,在鏈表的第i個位置插入x的元素

LinkedList LinkedListInsert(LinkedList L,int i,int x) {
	Node *pre;                      //pre為前驅結點
	pre = L;
	int tempi = 0;
	for (tempi = 1; tempi < i; tempi++) {
		pre = pre->next;                 //查找第i個位置的前驅結點
	}
	Node *p;                                //插入的結點為p
	p = (Node *)malloc(sizeof(Node));
	p->data = x;
	p->next = pre->next;
	pre->next = p;

	return L;
}


//單鏈表的刪除,在鏈表中刪除值為x的元素

LinkedList LinkedListDelete(LinkedList L,int x) {
	Node *p,*pre;                   //pre為前驅結點,p為查找的結點。
	p = L->next;
	
	while(p->data != x) {              //查找值為x的元素
		pre = p;
		p = p->next;
	}
	pre->next = p->next;          //刪除操作,將其前驅next指向其后繼。
	free(p);
	
	return L;
}

//鏈表內容的修改,再鏈表中修改值為x的元素變為為k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
	Node *p=L->next;
	int i=0;
	while(p){
		if(p->data==x){
			p->data=k;
		}
		p=p->next;
	}
	return L;
}


//便利輸出單鏈表
void printList(LinkedList L){
	Node *p=L->next;
	int i=0;
	while(p){
		printf("第%d個元素的值為:%d\n",++i,p->data);
		p=p->next;
	}
} 

int main() {
	//創建 
	LinkedList list;
	printf("請輸入單鏈表的數據:以EOF結尾\n");
	list = LinkedListCreatT();
	//list=LinkedListCreatT();
	printList(list);
	
	//插入 
	int i;
	int x;
	printf("請輸入插入數據的位置:");
	scanf("%d",&i);
	printf("請輸入插入數據的值:");
	scanf("%d",&x);
	LinkedListInsert(list,i,x);
	printList(list);
	
	//修改
	printf("請輸入修改的數據:");
	scanf("%d",&i);
	printf("請輸入修改后的值:");
	scanf("%d",&x);
	LinkedListReplace(list,i,x);
	printList(list);
	
	//刪除 
	printf("請輸入要刪除的元素的值:");
	scanf("%d",&x);
	LinkedListDelete(list,x);
	printList(list);

	return 0;
}


5.  題目練習推薦

1676題1052題

請獨自完成提交并通過


本文固定URL:http://hnsaiyang.com/course/97

上一課:單鏈表一 下一課:雙向鏈表一
第一章 數據結構入門
第二章 鏈表
第三章 棧
第四章 隊列
第五章 從C語言到C++
第六章 串,數組,矩陣,廣義表
第七章 樹
第八章 圖
第九章 算法—查找
第十章 算法—排序
第十一章 算法&競賽,思維培養
第十二章 后記
Dotcpp在線編譯      (登錄可減少運行等待時間)