快捷導(dǎo)航

C語言深入探索之單鏈表與typedef的用法

更新時(shí)間：2022年05月18日 09:41:38 作者：對(duì)象new不出來

typedef為C語言的關(guān)鍵字,作用是為一種數(shù)據(jù)類型定義一個(gè)新名字，單鏈表是后面要學(xué)的雙鏈表以及循環(huán)鏈表的基礎(chǔ)，要想繼續(xù)深入了解數(shù)據(jù)結(jié)構(gòu)以及C語言，我們就要奠定好這塊基石！接下來就和我一起學(xué)習(xí)吧

前言

昨天博主去本站問答貼子逛了逛，然后發(fā)現(xiàn)了好多關(guān)于數(shù)據(jù)結(jié)構(gòu)線性表，具體來說是單鏈表的問題。有的是沒有一點(diǎn)思路，無從下手；有的是看不懂代碼，不理解關(guān)鍵字以及被形參的形式氣的不行，我總結(jié)了一下常見問題來給大家?guī)砀韶?，到后面還有簡(jiǎn)單案例來鞏固知識(shí)，弄透一題勝無腦刷百題，接下來是正文內(nèi)容。

詳解typedef關(guān)鍵字

含義

C語言允許用戶使用 typedef 關(guān)鍵字來定義自己習(xí)慣的數(shù)據(jù)類型名稱，來替代系統(tǒng)默認(rèn)的基本類型名稱、數(shù)組類型名稱、指針類型名稱與用戶自定義的結(jié)構(gòu)型名稱、共用型名稱、枚舉型名稱等。一旦用戶在程序中定義了自己的數(shù)據(jù)類型名稱，就可以在該程序中用自己的數(shù)據(jù)類型名稱來定義變量的類型、數(shù)組的類型、指針變量的類型與函數(shù)的類型等。

具體使用

單鏈表結(jié)點(diǎn)示例：

typedef struct node
{
	int data;//數(shù)據(jù)域
	struct node * next;//指針域
}Lnode, * SLinkList;

這里我們創(chuàng)建了 node 結(jié)構(gòu)體，結(jié)構(gòu)體里面包含了整型數(shù)據(jù)data，指針next 指向下一個(gè)結(jié)點(diǎn)的地址?？梢钥吹较旅娲罄ㄌ?hào)外有 Lnode和*SLinkList。他的意思就是我們給node 起了一個(gè)別名叫Lnode，Lnode具有和node相同的結(jié)構(gòu)，struct node n1與Lnode n1 效果完全相同；同時(shí)C語言還允許在結(jié)構(gòu)中包含指向它自己的指針，即 SLinkList L 等價(jià)于 struct node* L 或者 Lnode *L；

詳解單鏈表參數(shù)形式

指針知識(shí)補(bǔ)充

示例：

//1、
int* getValue1(int *&L)
{
	int a = 10;
	L = &a;
	return L;
}
//2、
int* getValue2(int *L)
{
	int a = 10;
	L = &a;
	return L;
}
int main()
{
	int* ptr = (int*)malloc(sizeof(int) * 4);
	getValue1(ptr);
    getValue2(ptr);
	cout << *ptr << endl;
}

我在主函數(shù)中為指針ptr動(dòng)態(tài)分配了內(nèi)存空間，大小為4*4字節(jié)，不理解的可以參考我的這篇博文詳解數(shù)據(jù)結(jié)構(gòu)線性表里面的動(dòng)態(tài)分布內(nèi)存函數(shù)malloc；然后將地址傳遞到上面兩個(gè)函數(shù)里面去，輸出getValue1 的*ptr 結(jié)果是10，但是getValue2 中*ptr 的結(jié)果卻是亂碼。那么原因很明顯，就是參數(shù) int *&L和 int *L的區(qū)別了。這個(gè)函數(shù)的返回值是一個(gè)地址，然而在棧區(qū)開辟的數(shù)據(jù)，在函數(shù)調(diào)用結(jié)束后就會(huì)被編譯器自動(dòng)釋放掉，從而返回的地址不會(huì)是&a，因此僅僅使用地址傳遞是不行的。那么加上&為什么就可以了呢，這是因?yàn)槲覀兊哪康氖歉淖儌魅胫羔標(biāo)赶虻牡刂?，第一種只能改變?cè)摰刂穼?duì)應(yīng)的數(shù)值，第二種可以從本質(zhì)上更改地址，所以能得到 &a 從而*ptr結(jié)果為10。

單鏈表形參詳解

示例：

typedef struct node
{
	int data;//數(shù)據(jù)域
	struct node * next;//指針域
}Lnode, * SLinkList;
SLinkList Init_List(Lnode *&L)
{
	L = (SLinkList)malloc(sizeof(Lnode));
	L->next = NULL;
	return L;
}

同樣的，根據(jù)我前面講的知識(shí)，我定義了一個(gè)SLinkList 指針型的初始化鏈表函數(shù) Init_List()，傳入的是結(jié)構(gòu)體指針變量L，接下來為L(zhǎng)分配內(nèi)存空間，這里sizeof(Lnode)是計(jì)算了結(jié)構(gòu)體Lnode所占內(nèi)存大小并將此內(nèi)存分配給L，接下來讓初始化L，讓其指針域?yàn)榭?。?shí)際上L->data =NULL，L 就是單鏈表中的頭結(jié)點(diǎn)。這段代碼是沒有問題的，但是如果把形參中的Lnode *&L，改為L(zhǎng)node *L,那么編譯器必然會(huì)提示我們，取消對(duì)NULL指針的使用，這就是為什么我們要加上&的原因，不加&返回的不是我們分配的指針變量L的地址，那這樣我們的初始化毫無意義，雖然不報(bào)錯(cuò)，但是毫無作用。所以提醒你們寫數(shù)據(jù)結(jié)構(gòu)的時(shí)候記住這個(gè)小細(xì)節(jié)，很重要的！

單鏈表實(shí)戰(zhàn)案例

完整代碼實(shí)現(xiàn)

#include<iostream>
using namespace std;
#define SIZE 10
typedef struct node
{
	int data;//數(shù)據(jù)域
	struct node * next;//指針域
 
}Lnode, * SLinkList;
SLinkList Init_List(Lnode *&L)
{
	L = (SLinkList)malloc(sizeof(Lnode));
	L->next = NULL;
	return L;
}
SLinkList Creat_List(Lnode* &L,int n)//頭插建表
{
	srand((unsigned int)time(NULL));
	SLinkList p = L;
	for (int i = 0; i < n; i++)
	{
		int e = rand() % 20 + 1;
		SLinkList s = (SLinkList)malloc(sizeof(Lnode));
		s->next = p->next;
		p->next = s;
		s->data = e;
	}
	return L;
}
int count_List(Lnode *& L)
{
	int count = 0;
	SLinkList p = L->next;
	while (p)
	{
		count++;
		p = p->next;
	}
	return count;
}
int find_List(SLinkList L,int v)
{
	SLinkList p = L->next;
	int i = 1;
	while (i < v && p->next)
	{
		p = p->next;
		i++;
	}
	return p->data;
}
void display_List(SLinkList L)
{
	SLinkList p = L->next;
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
}
int main()
{
	srand((unsigned int)time(NULL));
	int n = rand()%5 + 5, count = 0, v = 0;
	SLinkList L;
	L = Init_List(L);
	cout << "隨機(jī)插入元素完成："<<endl;
	L = Creat_List(L,n);
	count = count_List(L);
	cout << "單鏈表長(zhǎng)度為：" << count << endl;
	cout << "遍歷單鏈表結(jié)果為：" << endl;
	display_List(L);
	cout << endl;
	cout << "要查找元素的位置為："; cin >> v;
	int value = find_List(L, v);
	cout << "查找結(jié)果為：" << value << endl;
}

詳解頭插建表

把頭插建表方法復(fù)制過來

SLinkList Creat_List(Lnode* &L,int n)//頭插建表
{
	srand((unsigned int)time(NULL));
	SLinkList p = L;
	for (int i = 0; i < n; i++)
	{
		int e = rand() % 20 + 1;
		SLinkList s = (SLinkList)malloc(sizeof(Lnode));
		s->next = p->next;
		p->next = s;
		s->data = e;
	}
	return L;
}

這里不用管srand((unsigned int)time(NULL));這段代碼是為了產(chǎn)生不同隨機(jī)數(shù)，和我講的內(nèi)容沒有什么聯(lián)系；往下看，創(chuàng)建建構(gòu)體指針變量p并把p設(shè)置為頭指針：L是頭結(jié)點(diǎn)，p=L，p指向鏈表第一個(gè)帶值結(jié)點(diǎn)。進(jìn)入循環(huán)語句，循環(huán)語句n我會(huì)利用隨機(jī)數(shù)產(chǎn)生；e是1~20范圍內(nèi)隨機(jī)的一個(gè)數(shù)值，結(jié)構(gòu)體指針變量s被動(dòng)態(tài)分配內(nèi)存空間s->next = p>next; p->next = s;s->data = e;這三行代碼是頭插法的核心。首先待插入原色s指針指向頭結(jié)點(diǎn)指向的結(jié)點(diǎn)，然后頭指針指向s，這樣鏈表的鏈就連好了，最后給s的數(shù)據(jù)域賦值為e，執(zhí)行循環(huán)語句，這樣新插入的結(jié)點(diǎn)都會(huì)在上一個(gè)插入結(jié)點(diǎn)的前面，這就是頭插法的全部過程。