一、連續(xù)存儲【數(shù)組】
數(shù)組元素類型相同,大小相等
二、離散存儲【鏈表】
定義:
????????n個節(jié)點(diǎn)離散分配,彼此通過指針相連,每個節(jié)點(diǎn)只有一個前驅(qū)節(jié)點(diǎn),且只有一個后續(xù)節(jié)點(diǎn)
????????首節(jié)點(diǎn)前沒有前驅(qū)節(jié)點(diǎn),尾節(jié)點(diǎn)沒有后續(xù)節(jié)點(diǎn)
專業(yè)術(shù)語:
????????首節(jié)點(diǎn):第一個有效節(jié)點(diǎn)
????????尾節(jié)點(diǎn):最后一個有效節(jié)點(diǎn)
????????頭節(jié)點(diǎn):是第一個有效節(jié)點(diǎn)前的節(jié)點(diǎn),不存放有效數(shù)據(jù),方便對鏈表的操作
????????頭指針:指向頭節(jié)點(diǎn)的指針變量
????????尾指針:指向尾節(jié)點(diǎn)的指針變量
只需要頭指針就能對一個鏈表處理,指針域指向下一個節(jié)點(diǎn)的整體(并非單獨(dú)的數(shù)據(jù)域或指針域)
分類:
????????單鏈表
????????雙鏈表:每一個指針都有兩個指針域
? ? ? ? 循環(huán)鏈表:能通過任何一個節(jié)點(diǎn)找到其他所有節(jié)點(diǎn)
????????非循環(huán)鏈表
相關(guān)算法:
????????遍歷、查找、清空、銷毀、求長度、排序、刪除節(jié)點(diǎn)、插入節(jié)點(diǎn)
????????狹義的算法是與數(shù)據(jù)的存儲方式密切相關(guān)的;
????????廣義的算法是與數(shù)據(jù)的存儲方式無關(guān)的;
????????泛型:利用某種技術(shù)達(dá)到的效果就是:不同的存數(shù)方式但執(zhí)行的操作是一樣的
連續(xù)儲存數(shù)據(jù)鏈表的代碼實(shí)現(xiàn)(類似于手搓數(shù)組)
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"http://包含了exit函數(shù)
//定義了一個數(shù)據(jù)類型(類似于手搓數(shù)組)
struct Arr
{
int * pBase;
int len;//當(dāng)前有效數(shù)組長度
int cnt;//當(dāng)前有效元素個數(shù)
};
void init_arr(struct Arr * pArr,int length);//初始化
bool append_arr(struct Arr * pArr,int val);//追加
bool insert_arr(struct Arr * pArr,int pos,int val);//插入
//pos的值從1開始
bool delete_arr(struct Arr * pArr,int pos,int* pVal);//刪除
int get();
bool is_empty(struct Arr * pArr);
bool is_full(struct Arr * pArr);
void sort_arr(struct Arr * pArr);//排序
void show_arr(struct Arr * pArr);
void inversion_arr(struct Arr * pArr);//倒置
int main()
{
struct Arr arr;
int val;
init_arr(&arr,6);
show_arr(&arr);
append_arr(&arr,4);
append_arr(&arr,3);
append_arr(&arr,2);
append_arr(&arr,1);
sort_arr(&arr);
/*
if(delete_arr(&arr,3,&val))
{
printf("刪除成功!\n");
printf("您刪除的元素是:%d\n",val);
}
else printf("刪除失敗!\n");
*/
/*
if(insert_arr(&arr,3,99))
{
printf("插入成功!\n");
}
else printf("插入失敗!\n");
if(append_arr(&arr,7))
{
printf("追加成功!\n");
}
else printf("追加失敗!\n");
*/
show_arr(&arr);
return 0;
}
//結(jié)構(gòu)體變量不能加減乘除,但可以相互賦值
void init_arr(struct Arr * pArr,int length)//(arr == *pArr)
{
pArr->pBase = (int *)malloc(sizeof(int) * length);
//pArr->pBase 等價于 (*pArr).pBase
if(NULL == pArr->pBase)
{
printf("動態(tài)內(nèi)存分配失??!\n");
exit(-1);//終止整個程序
}
else
{
pArr->len = length;
pArr->cnt = 0;
}
return;
}
bool is_empty(struct Arr * pArr)
{
if(0 == pArr->cnt) return true;
else return false;
}
void show_arr(struct Arr * pArr)
{
//判斷數(shù)組是否為空
if(is_empty(pArr))//&pArr不是地址,pArr本身就是地址
{
//提示用戶數(shù)組為空
printf("數(shù)組為空!\n");
}
else
{
for(int i=0;i<pArr->cnt;i++)
{
printf("%d ",pArr->pBase[i]);
//或者是 *(pArr->pBase+i)
}
printf("\n");
}
return;
}
bool is_full(struct Arr * pArr)
{
if(pArr->cnt == pArr->len) return true;
else return false;
}
bool append_arr(struct Arr * pArr,int val)
{
if(is_full(pArr))
{
return false;
}
//數(shù)組不滿時才能追加
pArr->pBase[pArr->cnt] = val;
(pArr->cnt)++;
return true;
}
bool insert_arr(struct Arr * pArr,int pos,int val)
{
int i;
if(is_full(pArr))
{
return false;
}
if(pos<1 || pos>pArr->cnt+1)
{
return false;
}
for(i=pArr->cnt-1;i>=pos-1;i--)
{
pArr->pBase[i+1] = pArr->pBase[i];
}
pArr->pBase[pos-1] = val;
(pArr->cnt)++;
return true;
}
bool delete_arr(struct Arr * pArr,int pos,int* pVal)
{
int i;
if(is_empty(pArr))
{
return false;
}
if(pos<1 || pos>pArr->cnt)
{
return false;
}
*pVal = pArr->pBase[pos-1];
for(i=pos;i<pArr->cnt;i++)
{
pArr->pBase[i-1] = pArr->pBase[i];
}
(pArr->cnt)--;
return true;
}
void inversion_arr(struct Arr * pArr)
{
int i = 0;
int j = pArr->cnt-1;
while(i < j)//快速排序思想
{
int tmp = pArr->pBase[i];
pArr->pBase[i] = pArr->pBase[j];
pArr->pBase[j] = tmp;
i++;
j--;
}
return;
}
void sort_arr(struct Arr * pArr)
{
int i,j;
for(i=0;i<pArr->cnt-1;i++)
{
for(j=0;j<pArr->cnt-1-i;j++)
{
if(pArr->pBase[j]>pArr->pBase[j+1])//從小到大
{
int tmp = pArr->pBase[j];
pArr->pBase[j] = pArr->pBase[j+1];
pArr->pBase[j+1] = tmp;
}
}
}
return;
}
鏈表創(chuàng)建及相關(guān)算法的代碼實(shí)現(xiàn)
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"http://包含了exit函數(shù)
//鏈表的創(chuàng)建和鏈表遍歷算法的實(shí)現(xiàn)
typedef struct Node
{
int data;//數(shù)據(jù)域
struct Node * pNext;//指針域
}NODE,*PNODE;
//NODE等價于struct Node PNODE等價于struct Node*
//函數(shù)聲明
PNODE create_list(void);
void traverse_list(PNODE pHead);
bool is_empty(PNODE pHead);
int length_list(PNODE pHead);
bool insert_list(PNODE,int ,int );
bool delete_list(PNODE,int ,int *);
void sort_list(PNODE);
int main(void)
{
PNODE pHead = NULL;
int val;
pHead = create_list();
//創(chuàng)建一個非循環(huán)鏈表,并將頭節(jié)點(diǎn)地址賦給pHead
printf("當(dāng)前的鏈表為:");
traverse_list(pHead);
//遍歷輸出
//insert_list(pHead,4,33);
//traverse_list(pHead);
if(delete_list(pHead,4,&val))
{
printf("刪除成功,刪除的元素是%d\n",val);
}
else printf("刪除失敗,您刪除的元素不存在\n");
traverse_list(pHead);
//if(is_empty(pHead)) printf("鏈表為空\n");
//else printf("鏈表不空\n");
//int len = length_list(pHead);
//printf("鏈表的長度是:%d\n",len);
//sort_list(pHead);
//printf("排序后的鏈表為:");
//traverse_list(pHead);
return 0;
}
PNODE create_list(void)
{
int len;//存放有效節(jié)點(diǎn)的個數(shù)
int i;
int val;//臨時存放用戶輸入節(jié)點(diǎn)的值
//分配一個不存放有效數(shù)據(jù)的頭節(jié)點(diǎn)
PNODE pHead = (PNODE) malloc(sizeof(NODE));
if(NULL == pHead)
{
printf("分配失敗,程序終止\n");
exit(-1);
}
PNODE pTail = pHead;
//pTail指向當(dāng)前的尾節(jié)點(diǎn)
pTail->pNext = NULL;
//避免len=0,要把頭節(jié)點(diǎn)指針域清空
printf("鏈表節(jié)點(diǎn)的個數(shù):len=");
scanf("%d",&len);
for(i=0;i<len;i++)
{
printf("輸入第%d個節(jié)點(diǎn)的值:",i+1);
scanf("%d",&val);
//將pNew掛到當(dāng)前尾節(jié)點(diǎn)的后面
PNODE pNew = (PNODE) malloc(sizeof(NODE));
if(NULL == pNew)
{
printf("分配失敗,程序終止\n");
exit(-1);
}
pNew->data = val;
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
}
void traverse_list(PNODE pHead)
{
PNODE p = pHead->pNext;
while(NULL != p)
{
printf("%d ",p->data);
p = p->pNext;
}
printf("\n輸出完畢\n");
return;
}
bool is_empty(PNODE pHead)
{
if(pHead->pNext == NULL)
{
return true;
}
else return false;
}
int length_list(PNODE pHead)
{
PNODE p = pHead->pNext;
int num = 0;
while(NULL != p)
{
num++;
p = p->pNext;
}
return num;
}
void sort_list(PNODE pHead)
{
int i,j,t;
PNODE p,q;
int len = length_list(pHead);
for(i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext)
{
for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext)
{
if(p->data > q->data)//類似于數(shù)組中的:a[i]>a[j]
{
t = p->data;
p->data = q->data;
q->data = t;
}
}
}
return;
}
//在pHead所指向鏈表的第pos個節(jié)點(diǎn)的前面插入一個新的節(jié)點(diǎn),該節(jié)點(diǎn)的值是val,并且pos的值從1開始
bool insert_list(PNODE pHead,int pos,int val)
{
int i = 0;
PNODE p = pHead;
while(NULL!=p && i<pos-1)
{
p = p->pNext;
++i;
}
if(i>pos-1 || NULL==p) return false;
PNODE pNew = (PNODE)malloc(sizeof(NODE));
if(NULL == pNew)
{
printf("動態(tài)內(nèi)存分配失敗\n");
exit(-1);
}
pNew->data = val;
PNODE q = p->pNext;
p->pNext = pNew;
pNew->pNext = q;
return true;
}
bool delete_list(PNODE pHead,int pos,int *pVal)
{
int i = 0;
PNODE p = pHead;
while(NULL!=p->pNext && i<pos-1)
{
p = p->pNext;
++i;
}
if(i>pos-1 || NULL==p->pNext) return false;
PNODE q = p->pNext;
*pVal = q->data;
p->pNext = p->pNext->pNext;
free(q);
q = NULL;
return true;
}
(一)線性結(jié)構(gòu)的兩種常見應(yīng)用之一:棧
定義:
??????????一種可以實(shí)現(xiàn)“先進(jìn)后出”的存儲結(jié)構(gòu)
??????????棧類似于箱子
??????????頭部用top,尾部用bottom
????????(把鏈表的一些功能砍掉,再添加一些功能)
分類:
??????????靜態(tài)棧
??????????動態(tài)棧
算法:
??????????出棧
??????????壓棧
應(yīng)用:
??????????函數(shù)調(diào)用
??????????中斷
??????????表達(dá)式求值(計算器)
????????? 內(nèi)存分配
??????? ? 緩沖處理
??????? ? 迷宮
棧的代碼實(shí)現(xiàn)
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
typedef struct Node
{
int data;
struct Node * pNext;
}NODE, * PNODE;
typedef struct Stack
{
PNODE pTop;
PNODE pBottom;
}STACK, * PSTACK;
void init(PSTACK);
void push(PSTACK,int);
void traverse(PSTACK);
bool pop(PSTACK,int*);
void clear(PSTACK);
int main(void)
{
STACK S;
int val;
init(&S);//初始化
push(&S,1);//壓棧
push(&S,2);//壓棧
push(&S,3);//壓棧
push(&S,4);//壓棧
push(&S,5);//壓棧
push(&S,6);//壓棧
traverse(&S);//遍歷輸出
clear(&S);//棧保留,清空棧
//traverse(&S);//遍歷輸出
if(pop(&S,&val))//出棧
{
printf("出棧成功,出棧元素是%d\n",val);
}
else printf("出棧失??!\n");
traverse(&S);//遍歷輸出
return 0;
}
void init(PSTACK pS)
{
pS->pTop = (PNODE)malloc(sizeof(NODE));
if(NULL == pS->pTop)
{
printf("動態(tài)內(nèi)存分配失敗\n");
exit(-1);
}
else
{
pS->pBottom = pS->pTop;
pS->pTop->pNext = NULL;
//或?qū)憄S->pBottom->pNext = NULL;
//把創(chuàng)建空間的指針域清空
}
}
void push(PSTACK pS,int val)
{
PNODE pNew = (PNODE)malloc(sizeof(NODE));
pNew->data = val;
pNew->pNext = pS->pTop;
pS->pTop = pNew;
return;
}
void traverse(PSTACK pS)
{
PNODE p = pS->pTop;
while(p != pS->pBottom)
{
printf("%d ",p->data);
p = p->pNext;
}
printf("\n");
return ;
}
bool is_empty(PSTACK pS)
{
if(pS->pTop == pS->pBottom)
{
return true;
}
else return false;
}
//把pS所指向的棧出棧一次,把出棧的元素存入val中
bool pop(PSTACK pS,int *pVal)
{
if(is_empty(pS))//pS本身存放的就是S的地址
{
return false;
}
else
{
PNODE r = pS->pTop;
*pVal = r->data;
pS->pTop = r->pNext;
free(r);
r = NULL;
return true;
}
}
void clear(PSTACK pS)
{
if(is_empty(pS))
{
return ;
}
else
{
PNODE p = pS->pTop;
PNODE q = NULL;
while(p != pS->pBottom)
{
q = p->pNext;
free(p);
p = q;
}
pS->pTop = pS->pBottom;
return ;
}
}
(二)線性結(jié)構(gòu)的兩種常見應(yīng)用之二:隊(duì)列
定義:
??????????一種可以實(shí)現(xiàn)”先進(jìn)先出“的存儲結(jié)構(gòu)
??????????頭部用front,尾部用rear
分類:
??????????鏈?zhǔn)疥?duì)列 --- 用鏈表實(shí)現(xiàn)
??????????靜態(tài)隊(duì)列 --- 用數(shù)組實(shí)現(xiàn)(把數(shù)組的一些功能砍掉,再添加一些功能)
??????????靜態(tài)隊(duì)列通常都必須是循環(huán)隊(duì)列
? ? 附:循環(huán)隊(duì)列的講解:??????
????????1.靜態(tài)隊(duì)列為什么必須是循環(huán)隊(duì)列
????????????????front指向第一個元素,rear指向最后一個元素的下一個元素*
????????????????f和r都只能加,f和r要循環(huán)
? ? ? ?2.循環(huán)隊(duì)列需要幾個參數(shù)來確定????????需要2個參數(shù)來確定
? ? ? ? ? ? ??? Front
?????????????? ?Rear
???????3.循環(huán)隊(duì)列各個參數(shù)的含義
????????????????2個參數(shù)在不同場合有不同含義
????????????????建議初學(xué)者先記住,然后慢慢體會??????????
????????????????1)隊(duì)列初始化
????????????????????????? front和rear的值都是零
????????????????2)隊(duì)列非空
??????????????????????????front代表的是隊(duì)列的第一個元素
??????????????????????????rear代表的是隊(duì)列的最后一個有效元素的下一個元素
????????????? ?3)隊(duì)列空
????????????????????????? front和rear的值相等,但不一定是零
? ? ??4.循環(huán)隊(duì)列入隊(duì)偽算法講解
????????????????1.將值存入r所代表的位置
????????????????2.r=r+1 //錯誤寫法
? ? ? ? ? ? ??? 正確寫法為:r=(r+1)%數(shù)組長度
??????5.循環(huán)隊(duì)列出隊(duì)偽算法講解
? ? ? ? ?????????f=(f+1)%數(shù)組長度
??????6.如何判斷循環(huán)隊(duì)列是否已空偽算法
????????????????f和r相等時隊(duì)列為空
??????7.如何判斷循環(huán)隊(duì)列是否為滿偽算法
????????????????預(yù)備知識:
??????????????????????????front的值可能比rear大
??????????????????????????front的值也完全有可能比rear小
??????????????????????????當(dāng)然也可能兩者相等
????????????????兩種方法:
??????????????????????????1.多增加一個標(biāo)志參數(shù)(記錄存儲元素個數(shù))
??????????????????????????2.少用一個元素
????????????????????????????如果r和f的值緊挨著,則隊(duì)列已滿
????????????????????????????用C語言偽算法表示就是:
??????????????????????????????/*
??????????????????????????????if( (r+1)%數(shù)組長度==f ) 已滿
??????????????????????????????else 不滿
??????????????????????????????*/
隊(duì)列算法:
??????????入隊(duì)
??????????出隊(duì)
隊(duì)列的具體應(yīng)用:
??????????所有和時間有關(guān)的操作都有隊(duì)列的影子(優(yōu)先級)
循環(huán)隊(duì)列的代碼實(shí)現(xiàn)
#include "stdio.h"
#include "bits/stdc++.h"
#include "malloc.h"
#include "stdlib.h"
using namespace std;
typedef struct Queue
{
int * pBase;//Pbase是一個數(shù)組的首地址
int front;
int rear;
}QUEUE;
void init(QUEUE *);
bool en_queue(QUEUE *,int val);
void traverse_queue(QUEUE *);
bool full_queue(QUEUE *);
bool out_queue(QUEUE *,int * );
bool emput_queue(QUEUE *);
int main()
{
QUEUE Q;
int val;
init(&Q);
en_queue(&Q,1);
en_queue(&Q,2);
en_queue(&Q,3);
en_queue(&Q,4);
en_queue(&Q,5);
en_queue(&Q,6);
en_queue(&Q,7);
en_queue(&Q,8);
//只能存儲1-5的數(shù)
traverse_queue(&Q);
if(out_queue(&Q,&val))
{
printf("出隊(duì)成功,您出隊(duì)的元素是%d\n",val);
}
else printf("出隊(duì)失敗\n");
traverse_queue(&Q);
return 0;
}
void init(QUEUE *pQ)
{
pQ->pBase = (int *)malloc(sizeof(Queue) * 6);
pQ->front = 0;
pQ->rear = 0;
}
bool full_queue(QUEUE *pQ)
{
if( (pQ->rear+1)%6 == pQ->front )
{
return true;
}
else return false;
//少用一個元素判斷是否為滿(第二種方法)
}
bool en_queue(QUEUE *pQ,int val)
{
if(full_queue(pQ))
{
return false;
}
else
{
pQ->pBase[pQ->rear] = val;
pQ->rear = (pQ->rear+1)%6;
return true;
}
}
void traverse_queue(QUEUE *pQ)
{
int i = pQ->front;
while(i != pQ->rear)
{
printf("%d ",pQ->pBase[i]);
i = (i+1) % 6;
}
printf("\n");
return;
}
bool emput_queue(QUEUE *pQ)
{
if(pQ->front == pQ->rear)
{
return true;
}
else return false;
}
bool out_queue(QUEUE *pQ,int *pVal)
{
if(emput_queue(pQ))
{
return false;
}
else
{
*pVal = pQ->pBase[pQ->front];
pQ->front = (pQ->front+1)%6;
return true;
}
}
專題:遞歸
? ????????定義:
??????????????????一個函數(shù)自己直接或間接調(diào)用自己
??????????階乘滿足三個條件:
??????????????????1.遞歸必須得有一個明確的終止條件
??????????????????2.該函數(shù)所處理的數(shù)據(jù)規(guī)模必須在遞減
??????????????????3.這個轉(zhuǎn)化必須是可解的
??????????循環(huán)和遞歸
??????????????????遞歸:
????????????????????????????易于理解
????????????????????????????速度慢
????????????????????????????存儲空間浪費(fèi)多
????????????????????循環(huán):
????????????????????????????不易理解
????????????????????????????速度快
????????????????????????????存儲空間浪費(fèi)少
??舉例:????1.1+2+3+...+100的和
?????????????????2.求階乘
? ? ? ? ? ? ? ???3.漢諾塔
? ? ? ? ? ? ? ? ?4.走迷宮
??遞歸的應(yīng)用:
????????????樹和森林就是以遞歸的方式定義的
????????????數(shù)和圖的很多算法都是以遞歸來實(shí)現(xiàn)的文章來源:http://www.zghlxwxcb.cn/news/detail-817407.html
????????????很多數(shù)學(xué)公式就是以遞歸的方式定義的文章來源地址http://www.zghlxwxcb.cn/news/detail-817407.html
到了這里,關(guān)于【雨學(xué)習(xí)】數(shù)據(jù)結(jié)構(gòu)入門---線性結(jié)構(gòu)的筆記及代碼實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容,請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持TOY模板網(wǎng)!