建站
咨詢
售后
建站咨詢
新聞中心
1.線性表的本質(zhì)與相關(guān)操作
線性表的定義
線性表(List)是零個(gè)或多個(gè)數(shù)據(jù)元素的集合
線性表中的數(shù)據(jù)元素之間是有順序的
線性表中的數(shù)據(jù)元素個(gè)數(shù)是有限的
線性表中的數(shù)據(jù)元素的類型必須相同
線性表的性質(zhì)
a0為線性表的第一個(gè)元素，只有一個(gè)后繼
an為線性表的最后一個(gè)元素，只有一個(gè)前驅(qū)
除a0和an外的其它元素ai，既有前驅(qū)，又有后繼
線性表能夠逐項(xiàng)訪問和順序存取
線性表的一些常用操作
創(chuàng)建線性表
銷毀線性表
清空線性表
將元素插入線性表
將元素從線性表中刪除
獲取線性表中某個(gè)位置的元素
獲取線性表的長度
線性表操作的實(shí)現(xiàn)
線性表在程序中表現(xiàn)為一種特殊的數(shù)據(jù)類型，其操作在程序中的表現(xiàn)為一組函數(shù)
10年積累的網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站策劃后付款的網(wǎng)站建設(shè)流程，更有寶坻免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。
List* List_Create(); //創(chuàng)建線性表
void List_Destroy(List* list); //銷毀線性表
void List_Clear(List* list); //清空線性表
int List_Insert(List* list, ListNode* node, int pos); //將元素插入線性表
ListNode* List_Delete(List* list, int pos); //將元素從線性表中刪除
ListNode* List_Get(List* list, int pos); //獲取線性表中某個(gè)位置的元素
int List_Length(List* list); //獲取線性表的長度2.線性表的順序存儲(chǔ)結(jié)構(gòu)
順序存儲(chǔ)定義
線性表的順序存儲(chǔ)結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
在C語言中可以用一維數(shù)組來實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)
存儲(chǔ)空間的起始位置：數(shù)組node
線性表的最大容量：數(shù)組長度MAXSIZE
線性表的當(dāng)前長度：length
#define MAXSIZE 20
typedef struct _tag_List
{
char node[MAXSIZE];
int length;
} List;獲取元素操作
判斷線性表是否合法
判斷位置是否合法
直接通過數(shù)組下標(biāo)的方式獲取元素
char Get(List* list, int pos)
{
char ret = -1;
if((list != NULL) && (0 <= pos ) && (pos <= list->length))
{
ret = list->node[pos];
}
return ret;
}插入元素操作
判斷線性表是否合法
判斷插入位置是否合法
把最后一個(gè)元素到插入位置的元素后移一個(gè)位置
將新元素插入
線性表長度加1
int Insert(List* list, char c, int pos)
{
//判斷線性表是否合法
int ret = (list != NULL);
int i = 0;
//判斷插入位置是否合法
ret = ret && ((list->length + 1) <= MAXSIZE);
ret = ret && (0 <= pos);
if(ret)
{
if(pos >= list->length)
pos = list->length;
//從最后一個(gè)元素開始到第pos個(gè)位置，分別將他們地洞到后一個(gè)位置
for(i=list->length;i > pos; i--)
{
list->node[i] = list->node[i-1];
}
//將新元素插入
list->node[pos] = c;
//長度加1
list->length++;
}
return ret;
}刪除元素操作
判斷線性表是否合法
判斷刪除位置是否合法
將元素取出
將刪除位置后的元素分別向前移動(dòng)一個(gè)位置
線性表長度減1
char Delete(List* list, int pos)
{
char ret = -1;
int i = 0;
//判斷線性表是否合法，判斷刪除位置是否合法
if((list != NULL)&&(0 <= pos)&&(pos < list-> length))
{
ret = list->node[pos];
for(int i=pos+1; i < list->length; i++)
list->node[i-1] = list->node[i];
list->length--;
}
return ret;
}3.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
鏈?zhǔn)酱鎯?chǔ)定義
為了表示每個(gè)數(shù)據(jù)元素與其直接后繼元素之間的邏輯關(guān)系，每個(gè)元素除了存儲(chǔ)本身的信息外，還需要存儲(chǔ)指示其直接后繼的信息。
鏈?zhǔn)酱鎯?chǔ)邏輯結(jié)構(gòu)
n個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈?zhǔn)骄€性表的結(jié)構(gòu)叫做鏈表，當(dāng)每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域時(shí)，叫做單鏈表。
鏈表的基本概念
表頭結(jié)點(diǎn)
?鏈表中的第一個(gè)結(jié)點(diǎn)，包含指向第一個(gè)數(shù)據(jù)元素的指針以及鏈表自身的一些信息
數(shù)據(jù)結(jié)點(diǎn)
?鏈表中代表數(shù)據(jù)元素的結(jié)點(diǎn)，包含指向下一個(gè)數(shù)據(jù)元素的指針和數(shù)據(jù)元素的信息
尾結(jié)點(diǎn)
?鏈表中的最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)，其下一元素指針為空，表示無后繼
單鏈表示例
在C語言中可以用結(jié)構(gòu)體來定義鏈表中的指針域；鏈表中的表頭結(jié)點(diǎn)也可以用結(jié)構(gòu)體實(shí)現(xiàn)
//結(jié)點(diǎn)指針域定義
typedef struct _tag_LinkListNode{
LinkListNode* next;
} LinkListNode;
//頭結(jié)點(diǎn)定義
typedef struct _tag_LinkList
{
LinkListNode header;
int length;
} TLinkList;
//數(shù)據(jù)元素定義
struct Value
{
LinkListNode header;
int v;
};獲取第pos個(gè)元素操作
判斷線性表是否合法
判斷位置是否合法
由表頭開始通過next指針移動(dòng)pos次后，當(dāng)前元素的next指針即指向要獲取的元素
LinkListNode* current = (LinkListNode*) list;
for(i=0; inext;
}
ret = current->next; 插入元素操作
判斷線性表是否合法
判斷插入位置是否合法
由表頭開始通過next指針移動(dòng)pos次后，當(dāng)前元素的next指針即指向要插入的位置
將新元素插入
線性表長度加1
刪除元素操作
判斷線性表是否合法
判斷插入位置是否合法
獲取第pos個(gè)元素
將第pos個(gè)元素從鏈表中刪除
線性表長度減1
實(shí)現(xiàn)代碼
當(dāng)前標(biāo)題：二、線性表的概念與實(shí)現(xiàn)
URL地址：http://www.dlmjj.cn/article/jgggjd.html
