腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

C語言數(shù)據(jù)結(jié)構(gòu)與算法之單鏈表

更新時間：2021年12月23日 14:22:50 作者：玄澈_

單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。本文將為大家介紹C語言中單鏈表的基本概念與讀取數(shù)據(jù)元素，需要的可以參考一下

基本概念

鏈表的每一個結(jié)點中只包含一個指針域

優(yōu)點 : 儲存空間利用高效

舉例來說：

typedef struct student{
	int id;		//學(xué)生編號
	char* name; //學(xué)生名稱
 
	//指向下一結(jié)點的指針
	struct Student* pNext;
}Student;

與之相反的是多鏈表

typedef struct student{
	int id;		//學(xué)生編號
	char* name; //學(xué)生名稱
 
	//指向下一結(jié)點的指針
	struct Student* pNext;
	struct Student* qNext;
}Student;

讀取數(shù)據(jù)元素

獲取第i個結(jié)點的數(shù)據(jù)元素

聲明一個結(jié)點指針p指向鏈表的第一個結(jié)點a1，初始化j從1開始
當(dāng)j < i 時，遍歷鏈表，讓p的指針向后移動，不斷指向下一個結(jié)點，j 累加 1
當(dāng)鏈表末尾 p 為空時，則說明第 i 個元素不存在；否則查找成功，返回結(jié)點 p 的數(shù)據(jù)

?

1.定義數(shù)據(jù)元素

//定義數(shù)據(jù)元素
typedef struct student{
	int id;		
	char* name; 
}ElementType;

2.定義順序表結(jié)構(gòu)

typedef struct {
	ElementType dates[MAX_SIZE];   //當(dāng)前順序表中的數(shù)據(jù)集合
	int length;					   //當(dāng)前順序表中的元素個數(shù)
 
}SeqList;

3.定義鏈表的結(jié)點（包括數(shù)據(jù)域和指針域）

typedef struct Node {
	ElementType date;  //數(shù)據(jù)域
	struct Node* node; //指針域，指向下一個結(jié)點
}Node;

4.設(shè)置頭結(jié)點

我們在定義鏈表時，習(xí)慣性的會定義頭結(jié)點，以便統(tǒng)一鏈表結(jié)點的插入和刪除操作

typedef struct Linklist {
	Node* next;  //頭指針
	int length;
}Linklist;

如果鏈表有頭結(jié)點，next就指向頭結(jié)點，沒有就指向第一個結(jié)點

鏈表的長度初始值為0

插入數(shù)據(jù)元素?

在第i個結(jié)點后插入數(shù)據(jù)元素 ?

創(chuàng)建一個空節(jié)點，分配內(nèi)存空間，設(shè)置數(shù)據(jù)元素
獲取第i個結(jié)點，設(shè)置新結(jié)點的后繼結(jié)點為該結(jié)點的后繼結(jié)點
設(shè)置第i個結(jié)點的后繼結(jié)點為該結(jié)點

1.創(chuàng)建空節(jié)點并為數(shù)據(jù)域賦值

	//創(chuàng)建空節(jié)點并為數(shù)據(jù)賦值
	Node* node = (Node*)malloc(sizeof(Node));
    node -> date = element;
    node -> next = NULL;

2.通過循環(huán)找到要插入的結(jié)點

	for (int i = 1; currNode && i < pos - 1; i++)
	{
		currNode = currNode->next;
	}

3.將結(jié)點插入并對接前面的結(jié)點

	if (currNode) {
		node->next = currNode->next;
		currNode->next = node;
		linkList->length++;
	}

初始化鏈表

void InitLinkList(LinkList* linkList, ElementType* dateArrar, int length)
{
	for (int i = 0; i < length; i++) {
		InsertLinkList(linkList, i + 1, dateArrar[i]);
	}
}

打印鏈表

void PrintLinkList(LinkList* linklist)
{
	Node* node = linklist->next;
	if (!node)
	{
		printf("鏈表為空！\n");
		linklist->length = 0;
		return 0;
	}
	for (int i = 0; i < linklist->length; i++) {
		printf("%d\t%s\t\n", node->date.id, node->date.name);
        node = node->next;
	}
}

順序表查空

int IsLinkListEmpty(LinkList* linkList) {
 
	return linkList->length == 0 ? TRUE : FALSE;
 
}

順序表的刪除?

刪除第i個結(jié)點及其數(shù)據(jù)元素

獲取第i個結(jié)點，若該結(jié)點不是第一個結(jié)點，則獲取第i - 1個結(jié)點
將第i -1個結(jié)點的后綴結(jié)點設(shè)為第i個結(jié)點的后綴結(jié)點
刪除第i個結(jié)點，釋放內(nèi)存空間，記錄并返回刪除數(shù)據(jù)元素的值

情況1：當(dāng)刪除的是第一個元素

	if (pos == 1)
	{
		node = linkList->next;
		if (node) {
			element = node->date;
			linkList->next = node->next;
			free(node);  //釋放被刪除的結(jié)點
			linkList->length--;
		}
        return element;
	}

情況2：除第一個結(jié)點外

找到要刪除的結(jié)點和他的前綴結(jié)點
要刪除結(jié)點的next 賦值給前綴結(jié)點
釋放要刪除的結(jié)點

	Node* preNode; //前綴結(jié)點
	node = linkList->next;
	for (int i = 1; node && i < pos; i++)
	{
		preNode = node;
		node = node->next;
	}
	if (node)
	{
		element = node->date;
		preNode->next = node->next;
		free(node);
		linkList->length--;
	}
	return element;

完整代碼

ElementType DeleteLinkListElement(LinkList* linkList, int pos)
{
	ElementType element;   //被刪除的元素
	element.id = -999;     //賦一個不可能的值，來判斷刪除是否成功
	Node* node = NULL;
 
	if (pos == 1)
	{
		node = linkList->next;
		if (node) {
			element = node->date;
			linkList->next = node->next;
			free(node);  //釋放被刪除的結(jié)點
			linkList->length--;
		}
	}
 
	Node* preNode; //前綴結(jié)點
	node = linkList->next;
	for (int i = 1; node && i < pos; i++)
	{
		preNode = node;
		node = node->next;
	}
	if (node)
	{
		element = node->date;
		preNode->next = node->next;
		free(node);
		linkList->length--;
	}
	return element;
 
}

刪除單鏈表整表

聲明結(jié)點p 和 q
將第一個結(jié)點賦值給p
循環(huán)將下一個結(jié)點賦值給q，釋放p，將q賦值給p

?

void CleatLinkList(LinkList* linkList)
{
	Node* node = linkList->next;
	Node* nextNode;
	while (node) {
		nextNode = node->next;  //先記錄當(dāng)前結(jié)點的下一個結(jié)點，以便釋放當(dāng)前結(jié)點的內(nèi)存
		free(node);
		node = nextNode;
	}
	linkList->next = NULL;
	linkList->length = 0;
}