**程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法 **
數(shù)據(jù)結(jié)構(gòu)的設(shè)計對于程序的結(jié)構(gòu)和性能都至關(guān)重要。合理的數(shù)據(jù)結(jié)構(gòu)不僅可以降低算法的復(fù)雜性，使程序更易于理解和維護，并且可以極大地提升程序的性能。
數(shù)據(jù)結(jié)構(gòu)綜述.png
上圖已經(jīng)列出了常用的數(shù)據(jù)結(jié)構(gòu)和基本的操作，本文主要講述線性結(jié)構(gòu)的鏈表的創(chuàng)建和增刪改查等基本操作。
首先明確幾個名詞和其對應(yīng)的英文單詞:
list（表）、queue（隊列）、stack（棧）、tree（樹）、graph（圖）
link（鏈式）、sequence（順序）、node（節(jié)點）
- 順序表
順序表比較簡單，不是本文的重點，在這里只做簡單的介紹。比較著急的童鞋可直接跳到第二部分。
順序表和數(shù)組其實是差不多的，只不過數(shù)組是存儲在?？臻g，而表需要在堆空間申請內(nèi)存空間(請參考這篇介紹：內(nèi)存管理).
定義順序表的結(jié)構(gòu)體：
typedef struct _seqlist_
{
int *data;//可以理解為int data[tlen],指向內(nèi)存片段的首地址
int clen;//順序表當前長度
int tlen;//順序表總長度
}seqlist_st;
順序表基本操作：
- 初始化函數(shù)
seqlist_st *seqlist_init(int len)//傳入表的總長度，類似于數(shù)組的大小
{
seqlist_st *list = NULL;
list = (seqlist_st *)malloc(sizeof(seqlist_st));//向內(nèi)存申請表頭結(jié)構(gòu)體的內(nèi)存空間
list->data = (int *)malloc(sizeof(int) * len);//申請順序表的內(nèi)存大小，類似于 int data[len]
list->clen = 0;//表的當前長度
list->tlen = len;//表的總長度
return list;
}
- 銷毀函數(shù)
int seqlist_destroy(seqlist_st *list)
{
free(list->data);//先把結(jié)構(gòu)體內(nèi)部申請到的內(nèi)存釋放
free(list);//再釋放表頭結(jié)構(gòu)體的內(nèi)存地址
return 0;
}
- 增
順序表的插入操作：由于順序表的內(nèi)存地址是連續(xù)的，所以插入操作比較麻煩，需要將插入位置及之后位置的數(shù)值全部后移一位。這里只簡單地將元素插入尾部。
int seqlist_insert(seqlist_st *list,int value)
{
if(list->clen >= list->tlen)//判斷鏈表長度是否超過申請的內(nèi)存大小
return -1;
list->data[list->clen++] = value;//clen記得要執(zhí)行 +1 操作噢！
return 0;
}
- 刪
順序表的刪除操作同樣需要將之后的元素全部前移一個位置：
int seqlist_delete(seqlist_st *list, int value)
{
int i, j;
for(i=0; i < list->clen; i++)
{
if(list->data[i] == value)//刪除表中所以得value單元
{
for(j=i; j+1 < list->clen; j++)//將value元素之后的所以單元前移一個位置
list->data[j] = list->data[j+1];
list->clen--;//將當前長度 -1
i--;//請認真理解此處為何要 -1
}
}
return 0;
}
- 改
將表中的第一個old替換為new,若不存在old則返回 -1
int seqlist_modify(seqlist_st *list,int old,int new)
{
int i;
for(i = 0;i < list->clen;i++)
{
if(list->data[i]== old)//找到第一個old并將其替換為new
break;
}
if(i>=list->clen)
return -1;
list->data[i]=new;
return 0;
}```
- 查
看表中是否存在此值
int seqlist_search(seqlist_st *list,int value)
{
int i;
for(i = 0;i<list->clen;i++)
{
if(list->data[i]==value)//查找第一個vlaue值
break;
}
if(i>=list->clen)
return 0;
return 1;
}
這里給出一個show()函數(shù)和main()函數(shù)以方便測試順序表的基本操作是否正確：
int seqlist_show(seqlist_st *list)
{
int i=0;
for(i=0;i<list->clen;i++)
printf("%5d ",list->data[i]);
printf("\n");
return 0;
}```
int main(int argc, const char *argv[])
{
seqlist_st *list = NULL;
int value = 100;
list = seqlist_init(10);
while(0 == seqlist_insert(list,value))
value += 100;
seqlist_show(list);
seqlist_delete(list,600);
seqlist_show(list);
printf("search(300)= %d \n",seqlist_search(list,300));
printf("modify(200,300)= %d \n",seqlist_modify(list,200,300));
seqlist_show(list);
printf("search(200)= %d \n",seqlist_search(list,200));
seqlist_delete(list,300);
seqlist_show(list);
seqlist_destroy(list);
return 0;
}
- 鏈表
鏈表和順序表的本質(zhì)區(qū)別在于：鏈式表在堆內(nèi)存中不是順序存儲的，而是鏈式存儲的，即相鄰的兩個單元在物理位置上并不相鄰，也即地址并不連續(xù)。而是前一個節(jié)點里面存儲的后一個節(jié)點的內(nèi)存地址，通過此種方式實現(xiàn)存儲和訪問。
鏈式表的創(chuàng)建和基本的操作我們直接在下面的完整的程序中進行說明：
鏈表的內(nèi)存視圖
#include <stdio.h>
#include <stdlib.h>
typedef struct _linknode_//鏈表的節(jié)點結(jié)構(gòu)體
{
int data;//存儲節(jié)點的值
struct _linknode_ *next;//存儲后續(xù)單元的地址
}linknode_t;
typedef struct _linklist_//鏈表的結(jié)構(gòu)體
{
struct _linknode_ *head;//鏈表頭的地址
int clen;//鏈表當前的長度
int tlen;//鏈表的總長度
}linklist_t;
int linklist_destroy(linklist_t *list);
linklist_t *linklist_init(int len);
int linklist_insert(linklist_t *list,int value);
linknode_t *creat_linknode(int value);
int linklist_show(linklist_t *list);
int linklist_delete(linklist_t *list,int value);
linknode_t * linklist_search(linklist_t *list,int value);
int linklist_modify(linklist_t *list,int old,int new);
int linklist_insertend(linklist_t *list,int value);
int linklist_insertmid(linklist_t *list,int local_value,int destin_value);
int main(int argc, const char *argv[])
{
int value = 100;
linknode_t *ret=NULL;
linklist_t *list = NULL;//鏈表首地址
list = linklist_init(10);//初始化鏈表，傳入鏈表長度
while(0 == linklist_insertend(list,value))//使用尾差法將值插入表中
value +=100;
linklist_show(list);//查看表
linklist_delete(list,600);//刪除表中值為600的節(jié)點
linklist_show(list);
ret = linklist_search(list,600);//查找鏈表中值為600的節(jié)點，返回其結(jié)構(gòu)體地址
if(ret == NULL)
printf("search : NULL \n");
else
printf("%d \n",ret->data);
linklist_modify(list,500,543);//修改
ret = linklist_search(list,543);
if(ret == NULL)
printf("search : NULL \n");
else
printf("%d \n",ret->data);
linklist_insertmid(list,400,678);//將678插入在400的下一節(jié)點
linklist_show(list);
linklist_destroy(list);//一定記得要銷毀鏈表釋放內(nèi)存噢，不然會產(chǎn)生內(nèi)存泄露喔。
return 0;
}
linklist_t *linklist_init(int len)//鏈表的初始化
{
linklist_t *list = NULL;
list = (linklist_t *)malloc(sizeof(linklist_t));//鏈表的結(jié)構(gòu)體地址
list->head = creat_linknode(0);//鏈表的頭結(jié)點，
list->clen = 0;
list->tlen = len;
return list;
}
int linklist_destroy(linklist_t *list)//鏈表的銷毀
{
linknode_t *p = list->head;
linknode_t *temp = NULL;
while(NULL != p)
{
temp = p;//從頭結(jié)點開始逐個釋放申請到的內(nèi)存空間
p = p->next;
free(temp);
}
free(list);
return 0;
}
int linklist_insert(linklist_t *list,int value)//鏈表擦頭插發(fā)，即將value值插入鏈表的第一個位置(頭結(jié)點之后)
{
linknode_t *new = NULL;
if(list->clen>=list->tlen)
return -1;
new = creat_linknode(value);
new->next=list->head->next;//新建節(jié)點的next指向原頭節(jié)點的后繼節(jié)點
list->head->next=new;//頭結(jié)點的next指向新建的節(jié)點，則完成了頭插法
list->clen++;
return 0;
}
linknode_t *creat_linknode(int value)
{
linknode_t *node = NULL;
node = (linknode_t *)malloc(sizeof(linknode_t));//申請內(nèi)存空間，創(chuàng)建節(jié)點，鏈式表只在需要用時才去動態(tài)申請內(nèi)存空間，順序表和數(shù)組都是在一開始即初始化就申請了所需的全部內(nèi)存
node->data = value;
node->next = NULL;
return node;//返回申請到的節(jié)點的內(nèi)存空間地址
}
int linklist_show(linklist_t *list)//輔助函數(shù)，順序打印鏈表的值
{
int i;
linknode_t *p = list->head->next;
for(i=0;i<list->clen;i++)
{
printf("%5d ",p->data);
p=p->next;
}
putchar('\n');
return 0;
}
int linklist_delete(linklist_t *list,int value)
{
linknode_t *p = list->head;
linknode_t *tmp = NULL;
while(NULL != p->next)//找到需要刪除的節(jié)點的地址：注意，我們需要定位到其前一個節(jié)點，即 p->next->data == value 的p，請認真思考為什么
{
if(p->next->data == value)//
break;
p=p->next;
}
if(NULL == p->next)
return -1;
tmp = p->next;//將要刪除的節(jié)點的地址（p->next）先暫存
p->next = tmp->next;//將其前一個節(jié)點p的next指向其后繼節(jié)點，現(xiàn)在才可以釋放其內(nèi)存
free(tmp);
list->clen--;
return 0;
}
linknode_t * linklist_search(linklist_t *list,int value)
{
linknode_t *p = list->head->next;
while(NULL != p)
{
if(p->data == value)//搜索鏈表中值為value的節(jié)點，并將其地址返回，如不存在，則返回null
return p;
p=p->next;
}
return NULL;
}
int linklist_modify(linklist_t *list,int old,int new)
{
linknode_t *p = list->head->next;
while(NULL != p)
{
if(p->data == old)//找到old節(jié)點，將其data值替換為指定的new
{
p->data = new;
break;
}
p=p->next;
}
if(NULL == p)//若沒有找到old節(jié)點， 即鏈表中不存在值為old的結(jié)點，則返回-1
return -1;
return 0;
}
int linklist_insertend(linklist_t *list,int value)
{
linknode_t *p = list->head;
linknode_t *new = NULL;
while(NULL != p->next)//找到最后一個節(jié)點
p = p->next;
if(list->clen >= list->tlen)
return -1;
new = creat_linknode(value);//創(chuàng)建新的節(jié)點
p->next = new;//將找到的最后一個節(jié)點的next指向新創(chuàng)建的節(jié)點，這樣新創(chuàng)建的節(jié)點就添加在整個鏈表的最后了
list->clen++;
return 0;
}
int linklist_insertmid(linklist_t *list,int local_value,int destin_value)
{
linknode_t *p = list->head->next;
linknode_t *new = NULL;
linknode_t *tmp = NULL;
if(list->clen >= list->tlen)
return -1;
while(NULL != p)
{
if(p->data == local_value)//找到值為local_value的節(jié)點的地址
{
tmp = p->next;//先將其后繼節(jié)點的地址存儲起來
new = creat_linknode(destin_value);//創(chuàng)建新的節(jié)點
p->next = new;//使local節(jié)點的next指向新插入的節(jié)點
new->next = tmp;//新創(chuàng)建的節(jié)點的next指向原local的后繼節(jié)點，完成了插入操作
list->clen++;
break;
}
p = p->next;
}
return 0;
}
上述實現(xiàn)的鏈表是單向鏈表，即只能從前一個節(jié)點找到后一節(jié)點，此外還有雙向鏈表(即能從前一個節(jié)點找到后一個節(jié)點，也能從后一個節(jié)點找到前一個節(jié)點，即一個節(jié)點結(jié)構(gòu)體不僅存了前一個節(jié)點的地址還存了后繼節(jié)點的地址)、循環(huán)鏈表(即尾節(jié)點的next不為null,而是存了第一個節(jié)點的地址)等。只需在此基礎(chǔ)上稍加修改即可實現(xiàn)。我們可以根據(jù)具體的需求來選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。
