開發成長之路（3）-- C語言從入門到開發（講明白指標和參考，鏈表很難嗎？）

指標和動態記憶體分配

指標是C語言的基本概念，C語言中指標無處不在，實際上,每種資料型別,都有相應的指向T的指標型別，
指標型別變數存放的值,實際上就是記憶體地址，指標型別有兩個最基本的操作:

&：取地址操作 
*：去參考 (間接參考)操作

參考&

首先，&不是地址運算子，而是型別識別符號的一種，就像*也不是指標運算子一樣，

就像char* 意為指向char的指標一樣，int& 意為指向int 的參考，

栗子來一顆：

int a;
int &at = a;
//上述宣告允許將at和a互換，它們指向相同的值和記憶體單元，就像連體嬰一樣，

上面這個栗子其實很有內涵在里面
我為什么不寫成下面這個形式呢？

int a;
int &at;
at = a;

在指標中是可以的，但是&不允許，&必須在宣告時將其初始化，

參考經常被用作函式引數，使得函式中的變數名成為呼叫程式中變數的別名，這種呼叫方法我一直搞得暈暈的，正好這次一次性根除，這種傳遞引數的方法稱為按參考傳遞，按參考傳遞允許被呼叫函式能夠訪問呼叫函式中的變數，這是C++相比C的一個超越，
來個經典的栗子：

void swap_a(int &a,int &b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
}

//順便來個指標的
void swap_b(int *a,int *b)
{
	int temp;
	temp = *a;	//a,b是指標，*a,*b才是int
	*a = *b;
	*b = temp;
}

int main()
{
	int a = 1;
	int b = 2;
	int c = 3;
	int d = 4;
	swap_a(a,b);	//看仔細咯，這個是參考呼叫
	swap_b(&a,&b);	//看仔細咯，這個是指標呼叫
	//如果理解不了，這樣理解：引數中的*和&只是走個過場，告訴人家那個引數是什么型別的
	//呼叫函式時的引數是a,不是*a,也不是&a
	//所以&a傳的這個a是一個int型別，而*a的這個a就是指標，地址，所以要取地址傳給它
	//雖然我語文不好，但是都講到這份上了那應該是可以理解了
	return 0;
}

如果你的意圖是讓函式使用傳給它的資訊，又不想把這些資訊進行改動，那么應該使用const，
將參考引數宣告為const資料的好處有這些：

防止無意中被修改，
使用const引數可以兼容非const傳參，

將參考用于結構

C++引入參考主要就是為了和結構和類，
它還通過讓函式回傳指向結構的參考而增添了一個有趣的特點，這與回傳結構有所不同，

//代碼太長，放段偽代碼吧
struct Str	//不知道什么是結構體不急，稍后就會有
{
};

Str& test(Str &a,const Str &b)	
{
	//從b中取值，對a進行填充
	return a;//其實可以做void型別，沒必要多此一舉
}

int main()
{
	Str a,b,c;
	//b是有初值的，這是偽代碼
	c = test(a,b);
	return 0;
}

如果test函式回傳一個結構，而不是指向結構的參考，相當于把整個結構體復制到一個臨時位置，再將這個拷貝復制給c，但是現在回傳值為參考，將直接將a復制到c，效率更高，

回傳參考時最重要的一點是：應避免回傳函式終止時將不再存在的記憶體單元的參考，
下面是一個反面教材：

Str& test(const Str &d)
{
	Str &e;
	···
	return e;
}

何時使用參考引數？

程式員能夠修改呼叫函式中的資料物件，
通過傳遞參考而不是整個資料物件，可以提高程式的運行速度，

指標

指標和const

將const用于指標有一些很微妙的地方，
可以用兩種不同的方式將const關鍵字用于指標，

int age = 20; const int * pt = &age;
//該宣告指出，pt指向一個const int，因此不能使用pt來修改這個值，
//現在來看一個很微妙的問題：其實age并不是一個常量，只是對于pt來說，它是一個常量，
//就是說age可以改，只不過不能用pt來改而已，

注意點：不允許將常量資料賦值給非常量指標，個中理由就不用多解釋了吧，

const int age = 20; int * pt = &age;

int sloth = 80; int * const finger = &sloth;
// 這種宣告格式使得這個指標只能指向sloth,不過可以通過這個指標修改sloth的值，

通過指標回傳字串的函式

現在，假設需要一個回傳字串的函式，是的，函式無法回傳一個字串，但是可以回傳字串的地址，這樣效率更高，

void test(char *rc)
{
	···
	memset(rc,字串);
	···
}

相當于是使用回呼函式，我個人比較喜歡這一套模式，

通過指標回傳結構

具體操作參考第二點，
當然，這里還有另外的應用場景：

void test2(const JieGouTi1 *a,JieGouTi2 *b)
{
	//將a中的某些值賦值給b
}
//這里有一個注意點，傳進去賦值的結構體指標最好用const.

函式指標

關于為什么要使用函式指標，我的理解還不是很深刻，畢竟功力不足，但是我知道那些回呼函式都是用函式指標的，所以對函式指標必須要理解好，
這叫啥，“但行好事，莫問為啥”，

函式指標完成任務的流程是這樣的：

獲取函式的地址
宣告一個函式指標
使用函式指標來呼叫函式
獲取函式地址

獲取函式地址那是比較簡單的事，如果說 void Hanshu();這是一個函式，那么它的地址就是 Hanshu，
如果函式Hanshubaba();要呼叫這個函式，是這樣的：Hanshubaba(Hanshu);
切記不能寫成：Hanshubaba(Hanshu());

宣告函式指標

假設現在有這么一個函式：int test3(void *arg); //這個arg引數，回呼函式里面用，要解釋有點長，
現在要將之改成函式指標形式：int （*test3）(void *arg);

首先，將test3更換成（*test3），因此，（*test3）也是函式，那么test3就是函式指標，
為宣告優先級，需要將 *test3 括號起來，

函式指標用武之地

如果你非要我說函式指標存在的意義，那我也真不好給你扯個所以然出來，那我就，舉幾個用得到的地方吧：

自定義排序/搜索

不同的模式（如策略，觀察者）

回呼

關于指標的一些思考

前面說到，將指標作為引數傳入，在函式內部對指標進行修改，函式結束后指標的修改將被保留，
因為指標傳參代表著地址傳參，

解惑：如何讓對指標引數的修改不被保存，

看個栗子：

class B {
	char* b;
public:
	B() {
		b = new char[5];
		strcpy(b,"aaaa");
	}
	char* get_b() { return b; }
};

class A {
private:
	char* a;
public:
	A(B* temp) { a = temp->get_b(); };

	void set_A() { 
		strcpy(a, "kkkk");	//頂替掉了
	}
};

int main() {
	B* b = new B();
	A* a = new A(b);
	a->set_A();
	cout << b->get_b() << endl;

	return 0;
}

結局列印出來的 b，就是“kkkk”，
那為什么會這樣？前面解釋過了，a、b都是對記憶體地址的映射，對a進行修改，就是對地址上的資料進行修改，而b只不過是地址的一個映射而已，讀取b，就是讀取地址上的東西，那本質已經被改了，讀出來的東西自然不一樣，

再看個例子：

void Del (POINT_T * the_head, int index)
{
	POINT_T *pFree=NULL;
	
	POINT_T *pNode=the_head;
	int flag=0;
	while (pNode->next!=NULL)
	{
		if(flag==index-1)
		{
			pFree=pNode->next;				//再指向資料域就爆了
			pNode->next=pNode->next->next;
			free(pFree->pData);
			free(pFree);
			break;
		}
		pNode=pNode->next;
		flag++;	
	}	
}

這是鏈表的一個例子，那可能會納悶兒，為什么對 pNode執行了 pNode=pNode->next;操作，而the_head卻沒有跟著變呢？
原因很簡單，pNode->next也是一個映射地址，這句話的意思就是用一個新的地址映射，頂替掉那個舊的，使得指標pNode指向一塊新的地址，和the_head失去聯系，

結構體

結構是 C 編程中一種用戶自定義的可用的資料型別，它允許我們存盤不同型別的資料項，

struct tag {	// 定義一個結構體，名字叫tag 
    member-list	// 結構體成員變數
    member-list 
    member-list  
    ...
} variable-list ;	// 結構體的簡稱

如果有簡稱時，初始化結構體物件是這樣的：

variable-list vl;
variable-list *vl2;

如果沒有簡稱時，初始化結構體物件是這樣的：

struct tag t;
struct tag *t2;

//就是要帶上‘struct’

在一般情況下，tag、variable-list 這 2 部分至少要出現 1 個，

除錯

除錯呢，是我們解決代碼運行程序中突然暴雷的一個很好的手段，如果代碼量一大的時候，憑肉眼想找到bug太難了，
但是如果我們對程式的運行流程應該是有一定的設想的吧，就是不知道實際它有沒有陽奉陰違，

除錯，就是放慢程式運行的速度，讓我們看清楚它內部是如何運行的，

1.選擇需要檢查或暫停運行的行，如下圖紅色方框前

2.點擊Windows除錯器（或者F5）

3、讓程式一步步執行，點擊單步執行（F10）、進入函式（F11）、跳出函式（shift+F11）、下一個斷點（F5）
是可以在代碼中打多個斷點的，

（每個人的界面排版不一定一樣，所以建議使用快捷鍵法）

程式執行時，可以看到每個變數的狀態

簡單除錯就介紹到這里，大家可以先練習一下，

鏈表

鏈表在C語言的資料結構中的地位可不低，后面很多的資料結構，特別是樹，都是基于鏈表發展的，
所以學好鏈表，后面的結構才有看的必要，

初識鏈表

鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的，鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成，每個結點包括兩個部分：一個是存盤資料元素的資料域，另一個是存盤下一個結點地址的指標域， 相比于線性表順序結構，操作復雜，由于不必須按順序存盤，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)，

但是鏈表失去了陣列隨機讀取的優點，同時鏈表由于增加了結點的指標域，空間開銷比較大，

鏈表有很多種不同的型別：單向鏈表，雙向鏈表以及回圈鏈表，

單鏈表

單鏈表實作

話不多說啊，這里我只想直接放代碼：

#include <stdio.h>	//初學者，C語言開手
#include <conio.h>
#include <stdlib.h>
#include <memory.h>
#include <assert.h>

//節點資料結構體
typedef struct test
{	
	char name[12];		//名字
	char pwd[8];		//密碼
	int number;			//編號
	int flag;			//區分管理員和用戶	// 	0 超級管理員 1 管理員  2 普通用戶 3 屏蔽用戶
	int money;			//僅用戶有存款，初始500
} TEST_T;

//如果不多來一個資料域，怎么能體現出通用鏈表的優勢
typedef struct reported
{
	int amount;//交易金額
	int rflag; //交易方式	1、存款 2、取款 3、轉賬轉出 4、轉賬轉入
	int lastmoney;//余額
	int lastmoney2;//收款者的余額
	int number1;//付款賬戶
	int number2;//入款賬戶
	char time[12];//操作時間	
} REPORT_T;

//節點描述結構體
typedef struct point
{
	void *pData;				//指向資料域
	struct point *next;			//指向下一個節點	
} POINT_T;

POINT_T * head ;
extern POINT_T * head;

這還是個通用鏈表的頭呢！！！

//創建結點
POINT_T * creat(void *data )	//創建一個屬于結構體point的函式，
//傳入結構體test的指標便可以用以操作test變數，
{								//并回傳一個point的指標用以操作point函式
	POINT_T *p=NULL;
	
	p=(POINT_T *)malloc(sizeof(POINT_T));
	if(p==NULL)
	{
		printf("申請記憶體失敗");
		exit(-1);
	}
	memset(p,0,sizeof(POINT_T));
	
	p->pData=data;
	p->next=NULL;	//處理干凈身后事
	return p;
}

//新增節點
void add(POINT_T * the_head,void *data )				//這里的data不會和上面那個沖突嗎？
{
	POINT_T * pNode=the_head;							//把頭留下
	POINT_T *ls=creat(data);
	//后面再接上一個
	while (pNode->next != NULL)							//遍歷鏈表，找到最后一個節點
	{
		pNode=pNode->next;
	}
	pNode->next=ls;			//ls 臨時
}

//洗掉節點
void del(POINT_T * the_head, int index)
{
	POINT_T *pFree=NULL;					//用來洗掉
	
	POINT_T *pNode=the_head;
	int flag=0;
	while (pNode->next!=NULL)
	{
		if(flag==index-1)
		{
			pFree=pNode->next;				//再指向資料域就爆了
			pNode->next=pNode->next->next;	//這里要無縫銜接
			free(pFree->pData);				//先釋放資料
			free(pFree);					//釋放指標
			break;
		}
		pNode=pNode->next;
		flag++;	
	}	
}

//計算節點數
int Count(POINT_T * the_head)
{
	int count=0;
	POINT_T *pNode1=the_head;
	while (pNode1->next!=NULL)
	{
		pNode1=pNode1->next;
		count++;		
	}	
	return count;
}

//查找固定節點資料
POINT_T * find(POINT_T *the_head,int index)
{
	int f=0;
	POINT_T *pNode=NULL;
	int count=0;
	pNode=the_head;
	
	count=Count(the_head);
	
	if(count<index)	
		printf("find nothing");
	
	while(pNode->next!=NULL)
	{
		if(index==f)
			return pNode;
		pNode=pNode->next;
		f++;		
	}
}

我就挑簡單的講，先入個門，之前有專門的資料結構專欄，后面也會有專門的資料結構專欄，一步一個腳印，現在都不要太著急，