前言

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

詳解typedef關(guān)鍵字

含義

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

具體使用

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

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 指向下一個結(jié)點的地址。可以看到下面大括號外有 Lnode和*SLinkList。他的意思就是我們給node 起了一個別名叫Lnode，Lnode具有和node相同的結(jié)構(gòu)，struct node n1與Lnode n1 效果完全相同；同時C語言還允許在結(jié)構(gòu)中包含指向它自己的指針，即 SLinkList L 等價于 struct node* L 或者 Lnode *L；

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

指針知識補充

示例：

//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動態(tài)分配了內(nèi)存空間，大小為4*4字節(jié)，不理解的可以參考我的這篇博文詳解數(shù)據(jù)結(jié)構(gòu)線性表里面的動態(tài)分布內(nèi)存函數(shù)malloc；然后將地址傳遞到上面兩個函數(shù)里面去，輸出getValue1 的*ptr 結(jié)果是10，但是getValue2 中*ptr 的結(jié)果卻是亂碼。那么原因很明顯，就是參數(shù) int *&L和 int *L的區(qū)別了。這個函數(shù)的返回值是一個地址，然而在棧區(qū)開辟的數(shù)據(jù)，在函數(shù)調(diào)用結(jié)束后就會被編譯器自動釋放掉，從而返回的地址不會是&a，因此僅僅使用地址傳遞是不行的。那么加上&為什么就可以了呢，這是因為我們的目的是改變傳入指針所指向的地址，第一種只能改變該地址對應的數(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ù)我前面講的知識，我定義了一個SLinkList 指針型的初始化鏈表函數(shù) Init_List()，傳入的是結(jié)構(gòu)體指針變量L，接下來為L分配內(nèi)存空間，這里sizeof(Lnode)是計算了結(jié)構(gòu)體Lnode所占內(nèi)存大小并將此內(nèi)存分配給L，接下來讓初始化L，讓其指針域為空。實際上L->data =NULL，L 就是單鏈表中的頭結(jié)點。這段代碼是沒有問題的，但是如果把形參中的Lnode *&L，改為Lnode *L,那么編譯器必然會提示我們，取消對NULL指針的使用，這就是為什么我們要加上&的原因，不加&返回的不是我們分配的指針變量L的地址，那這樣我們的初始化毫無意義，雖然不報錯，但是毫無作用。所以提醒你們寫數(shù)據(jù)結(jié)構(gòu)的時候記住這個小細節(jié)，很重要的！

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

完整代碼實現(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 << "隨機插入元素完成："<<endl;
	L = Creat_List(L,n);
	count = count_List(L);
	cout << "單鏈表長度為：" << count << endl;
	cout << "遍歷單鏈表結(jié)果為：" << endl;
	display_List(L);
	cout << endl;
	cout << "要查找元素的位置為："; cin >> v;
	int value = find_List(L, v);
	cout << "查找結(jié)果為：" << value << endl;
}

詳解頭插建表

把頭插建表方法復制過來

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

int count_List(Lnode *& L)； 方法對應第一問；

int find_List(SLinkList L,int v)；方法對應第二問；

相信認真看完這篇博文的你可以很好理解上面兩種方法的含義以及整個源碼表達的意思，最后附上運行效果截圖：

運行效果