單鏈表的基本操作及C語言代碼實現(xiàn)

154535 閱讀 0 評論 1 點贊

（續(xù)接前文）

1. 遍歷單鏈表（打印，修改）

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

進行遍歷的思路極其簡單，只需要建立一個指向鏈表L的結(jié)點，然后沿著鏈表L逐個向后搜索即可。

對于遍歷操作，以下是代碼實現(xiàn)：

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

對于元素修改操作，以下是代碼實現(xiàn)：

//鏈表內(nèi)容的修改，再鏈表中修改值為x的元素變?yōu)闉閗。
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;
}

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

以上的操作均用到了遍歷的思維，針對于遍歷還有非常多的用法供自主設(shè)計，請參考后文配套的習(xí)題進行練習(xí)。

2. 鏈表插入操作

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

如圖，在DATA1和DATA2數(shù)據(jù)結(jié)點之中插入一個NEW_DATA數(shù)據(jù)結(jié)點：

從原來的鏈表狀態(tài)

鏈表結(jié)構(gòu)

到新的鏈表狀態(tài)：

鏈表插入結(jié)點

以下是代碼實現(xiàn)：

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

3. 鏈表刪除操作

刪除元素要建立一個前驅(qū)結(jié)點和一個當(dāng)前結(jié)點，當(dāng)找到了我們需要刪除的數(shù)據(jù)時，直接使用前驅(qū)結(jié)點跳過要刪除的結(jié)點指向要刪除結(jié)點的后一個結(jié)點，再將原有的結(jié)點通過free函數(shù)釋放掉。

參考如圖

鏈表刪除節(jié)點操作

以下是代碼實現(xiàn)：

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

4. 完整實現(xiàn)代碼

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

//定義結(jié)點類型
typedef struct Node {
	int data;           //數(shù)據(jù)類型，你可以把int型的data換成任意數(shù)據(jù)類型，包括結(jié)構(gòu)體struct等復(fù)合類型
	struct Node *next;          //單鏈表的指針域
} Node,*LinkedList;

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


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

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


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

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

	return L;
}


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

LinkedList LinkedListInsert(LinkedList L,int i,int x) {
	Node *pre;                      //pre為前驅(qū)結(jié)點
	pre = L;
	int tempi = 0;
	for (tempi = 1; tempi < i; tempi++) {
		pre = pre->next;                 //查找第i個位置的前驅(qū)結(jié)點
	}
	Node *p;                                //插入的結(jié)點為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為前驅(qū)結(jié)點，p為查找的結(jié)點。
	p = L->next;
	
	while(p->data != x) {              //查找值為x的元素
		pre = p;
		p = p->next;
	}
	pre->next = p->next;          //刪除操作，將其前驅(qū)next指向其后繼。
	free(p);
	
	return L;
}

//鏈表內(nèi)容的修改，再鏈表中修改值為x的元素變?yōu)闉閗。
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() {
	//創(chuàng)建 
	LinkedList list;
	printf("請輸入單鏈表的數(shù)據(jù)：以EOF結(jié)尾\n");
	list = LinkedListCreatT();
	//list=LinkedListCreatT();
	printList(list);
	
	//插入 
	int i;
	int x;
	printf("請輸入插入數(shù)據(jù)的位置：");
	scanf("%d",&i);
	printf("請輸入插入數(shù)據(jù)的值：");
	scanf("%d",&x);
	LinkedListInsert(list,i,x);
	printList(list);
	
	//修改
	printf("請輸入修改的數(shù)據(jù)：");
	scanf("%d",&i);
	printf("請輸入修改后的值：");
	scanf("%d",&x);
	LinkedListReplace(list,i,x);
	printList(list);
	
	//刪除 
	printf("請輸入要刪除的元素的值：");
	scanf("%d",&x);
	LinkedListDelete(list,x);
	printList(list);

	return 0;
}