專業(yè)網(wǎng)站定制設(shè)計(jì)公司網(wǎng)絡(luò)營銷過程步驟
線性表
目錄
- 線性表
- 定義和基本操作
- 順序表
- 靜態(tài)順序表
- 動(dòng)態(tài)順序表
- 鏈表
- 單鏈表
- 不帶頭結(jié)點(diǎn):
- 帶頭結(jié)點(diǎn):
- 雙鏈表
- 循環(huán)鏈表
- 循環(huán)單鏈表:
- 循環(huán)雙鏈表:
- 靜態(tài)鏈表
- 順序表鏈表比較
- 邏輯結(jié)構(gòu):
- 存儲(chǔ)結(jié)構(gòu):
- 基本操作:
定義和基本操作
線性表的定義:線性表時(shí)具有相同數(shù)據(jù)類型的n(n>=0)個(gè)數(shù)據(jù)元素的有限序列,其中n為表長,當(dāng)n=0時(shí)線性表是一個(gè)空表。
L=(a1,a2,a3…,an) a1為表頭元素,an為表尾元素,除第一個(gè)元素外,每個(gè)元素有且僅有一個(gè)直接前驅(qū),除最后一個(gè)元素,每個(gè)元素有且僅有一個(gè)直接后繼。
特點(diǎn):
- 元素個(gè)數(shù)有限
- 元素具有邏輯上的順序性,表中元素有其先后次序
- 元素都是數(shù)據(jù)元素,每個(gè)元素都是單個(gè)元素
- 元素?cái)?shù)據(jù)類型相同,占有相同大小的存儲(chǔ)空間
- 元素具有抽象性
線性表是一種邏輯結(jié)構(gòu),表示元素之間一對(duì)一的相鄰關(guān)系,順序表和鏈表是指存儲(chǔ)結(jié)構(gòu)。
線性表基本操作:
總結(jié):
順序表
線性表的順序存儲(chǔ)稱為順序表,使用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素,從而使得邏輯上相鄰的兩個(gè)元素在物理位置上也相鄰。i為ai在線性表中的位序,元素的邏輯順序與其物理順序相同。
線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)。
順序表的特點(diǎn):
- 隨機(jī)訪問,可以在O(1)時(shí)間內(nèi)找到第i個(gè)元素 data[i-1]
- 存儲(chǔ)密度高,每個(gè)結(jié)點(diǎn)智存初數(shù)據(jù)元素
- 拓展容量不方便(即使采用動(dòng)態(tài)分配,拓展長度時(shí)間復(fù)雜度仍較高)
- 插入、刪除操作不方便,需要移動(dòng)大量元素
靜態(tài)順序表
一維數(shù)組可以靜態(tài)分配也可以動(dòng)態(tài)分配,靜態(tài)分配時(shí),數(shù)組大小和空間事先固定,不可變。而動(dòng)態(tài)順序表則不需要為線性表一次性劃分所有空間。
結(jié)構(gòu)體:
#define MaxSize 50typedef struct {int data[MaxSize];int length;
} SqList;
初始化:
//初始化
void InitList(SqList& L) {for (int i = 0; i < MaxSize; i++) {L.data[i] = 0;//將所有元素的初始值默認(rèn)設(shè)置為0//這一步其實(shí)可以省略,但是省略之后,有可能受到內(nèi)存中"臟數(shù)據(jù)"的影響}L.length = 0;
}
判空:
//判斷是否為空
bool Empty(SqList L) {return (L.length == 0);
}
插入:
//插入
bool ListInsert(SqList& L, int i, int e) {//判斷插入的位置是否合法,if (i < 1 || i > L.length + 1)return false;//判斷表是否存滿了if (L.length >= MaxSize)return false;//后面的元素后移for (int j = L.length; j >= i; j--) {L.data[j] = L.data[j - 1];}L.data[i - 1] = e;L.length++;return true;
}
刪除:
//刪除
bool ListDelete(SqList& L, int i, int& e) {//判斷i的位置是否合法if (i < 0 || i > L.length) {return false;}//取出將要被刪除的數(shù)e = L.data[i - 1];//將其后的數(shù)據(jù)前移for (int j = i; j <= L.length; j++) {L.data[j - 1] = L.data[j];}//線性表長度減一L.length--;return true;
}
查找:
//查找
//按位查找
int GetElem(SqList L, int i) {//判斷是否越界if (i < 0 || i > L.length)return -1;return L.data[i - 1];
}
//按值查找
int LocateElem(SqList L, int e) {//循環(huán)出查找for (int i = 0; i < L.length; i++) {if (L.data[i] == e)return i + 1; //返回位序}return -1;
}
改值:
//先查找后改值
//由此分為兩種方式,先按位查找后改值;或先按值查找后改值
//先按值查找后改值
bool LocateChangeElem(SqList& L, int e, int em) {//按值查找得到位序int bitOrder = LocateElem(L, e);//改值if (bitOrder != -1) {L.data[bitOrder] = em;return true;}else {return false;}
}//先按位序查找后改值
bool getChangeElem(SqList& L, int i, int em) {//給的位序,首先判斷i是否合法if (i < 0 || i >= L.length)return false;//由于是用數(shù)組實(shí)現(xiàn)的方式,可以直接利用i查找L.data[i] = em;return true;}
打印:
//打印整個(gè)順序表
void PrintSqList(SqList L) {//循環(huán)打印printf("開始打印順序表\n");for (int i = 0; i < L.length; i++) {printf("Data[%d]==%d\n", i, L.data[i]);}printf("打印結(jié)束!\n");
}
動(dòng)態(tài)順序表
一旦數(shù)據(jù)空間占滿,就另外開辟一塊更大的存儲(chǔ)空間,用以替換原來的存儲(chǔ)空間,從而達(dá)到擴(kuò)充存儲(chǔ)空間的目的。
結(jié)構(gòu)體:
#define InitSize 100
typedef struct {int* data; //指示動(dòng)態(tài)分配數(shù)組的指針int MaxSize;//順序表的最大容量int length;//順序表當(dāng)前的長度
} SeqList;
初始化:
//初始化
bool InitList(SeqList& L) {//用 malloc 函數(shù)申請(qǐng)一片連續(xù)的存儲(chǔ)空間L.data = (int*)malloc(InitSize * sizeof(int));if (L.data == NULL)return false;//(int *) 是指針的強(qiáng)制類型轉(zhuǎn)換L.length = 0;L.MaxSize = InitSize;return true;
}
判空:
//判空
bool Empty(SeqList L) {return (L.length == 0);
}
判滿:
//判滿
bool Full(SeqList L) {return (L.length >= L.MaxSize);
}
擴(kuò)展空間:
//擴(kuò)展空間
void IncreaseSize(SeqList& L, int len) {int* p = L.data;L.data = (int*)malloc((InitSize + len) * sizeof(int));for (int i = 0; i < L.length; i++) {L.data[i] = p[i];}L.MaxSize = L.MaxSize + len;free(p);//malloc 函數(shù)用于申請(qǐng)內(nèi)存空間;free 函數(shù)用于釋放內(nèi)存空間;
}
插入:
//插入
bool ListInsert(SeqList& L, int i, int e) {//判斷插入的位置是否合法,if (i < 1 || i > L.length + 1)return false;//判斷表是否存滿了
// if (L.length>=L.MaxSize)
// return fals;if (Full(L))return false;//后面的元素后移for (int j = L.length; j >= i; j--) {L.data[j] = L.data[j - 1];}L.data[i - 1] = e;L.length++;return true;
}
按位查找:
//按位查找
int GetElem(SeqList L, int i) {//判斷是否越界if (i < 0 || i > L.length)return -1;return L.data[i - 1];
}
按值查找:
//按值查找
int LocateElem(SeqList L, int e) {//循環(huán)出查找for (int i = 0; i < L.length; i++) {if (L.data[i] == e)return i + 1; //返回位序}return -1;
}
刪除:
//刪除
bool ListDelete(SeqList& L, int i, int& e) {//判斷i的位置是否合法if (i < 0 || i > L.length) {return false;}//取出將要被刪除的數(shù)e = L.data[i - 1];//將其后的數(shù)據(jù)前移for (int j = i; j <= L.length; j++) {L.data[j - 1] = L.data[j];}//線性表長度減一L.length--;return true;
}
銷毀:
//銷毀
//由于動(dòng)態(tài)分配方式使用malloc申請(qǐng)的內(nèi)存空間,故需要使用free函數(shù)手動(dòng)釋放空間!
void DestroySqList(SeqList& L) {free(L.data);L.data = NULL;L.length = 0;
}
打印:
//打印整個(gè)順序表
void PrintSqList(SeqList L) {if (L.data == NULL || L.length == 0)printf("這是一個(gè)空表!");else {//循環(huán)打印printf("開始打印順序表\n");for (int i = 0; i < L.length; i++) {printf("Data[%d]==%d\n", i, L.data[i]);}printf("打印結(jié)束!\n");}
}
總結(jié):
鏈表
單鏈表
線性表的鏈?zhǔn)酱鎯?chǔ)稱為單鏈表,它指通過一組任意的存儲(chǔ)單元來存儲(chǔ)線性表中的數(shù)據(jù)元素。每個(gè)鏈表結(jié)點(diǎn)存放元素自身的信息外,還需要存放一個(gè)指向其后繼的指針。
結(jié)構(gòu)體:
//結(jié)構(gòu)體
typedef struct LNode {int data;struct LNode* next;
} LNode, * LinkList;
//等價(jià)于
//struct LNode{
// int data;
// struct LNode *next;
//};
//
//typedef struct LNode LNode;
//typedef struct LNode *LinkList;
LinkList強(qiáng)調(diào)為單鏈表 LNode*強(qiáng)調(diào)為結(jié)點(diǎn),兩者等價(jià)
不帶頭結(jié)點(diǎn):
初始化:
//初始化
bool InitList(LinkList& L) {L = NULL;//空表暫時(shí)沒有任何數(shù)據(jù)return true;
}
判空:
//判斷是否為空
bool Empty(LinkList L) {return (L == NULL);
}
//等價(jià)于
//bool Empty1(LinkList L){
// if (L==NULL)
// return true;
// else
// return false;
//}
插入:
//在指定位置插入元素
bool ListInsert(LinkList& L, int i, int e) {if (i < 1)return false;//判斷位序i是否合法//不帶頭節(jié)點(diǎn)時(shí),插入位置正好為表頭時(shí),得單獨(dú)處理if (i = 1) {LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = L;L = s;return true;}LNode* p;//指針指向當(dāng)前掃面到的節(jié)點(diǎn)int j = 0;//記錄p指向的節(jié)點(diǎn)的位序p = L;//L指向頭節(jié)點(diǎn),從頭開始while (p != NULL && j < i - 1) {//循環(huán)掃描p = p->next;j++;}if (p == NULL) //i值超過來表長,不合法return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;//下面的順序不可交換s->next = p->next;p->next = s;return true;
}
帶頭結(jié)點(diǎn):
初始化:
//初試化(帶有頭節(jié)點(diǎn))
bool InitList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));//分配一個(gè)頭節(jié)點(diǎn)if (L == NULL)return false;//頭節(jié)點(diǎn)分配失敗,可能是內(nèi)存不足L->next = NULL;//頭節(jié)點(diǎn)之后暫時(shí)沒有節(jié)點(diǎn),頭節(jié)點(diǎn)也不存放數(shù)據(jù)return true;
}
判空:
//判空
bool Empty(LinkList L) {return (L->next == NULL);
}
打印鏈表:
void PrintList(LinkList L) {//循環(huán)打印整個(gè)鏈表LNode* p = L->next;//掃描指針int j = 0;if (p == NULL)printf("這是一個(gè)空表\n");while (p != NULL) {printf("LinkList[%d]=%d\n", j, p->data);p = p->next;j++;}
}
按位插入:
//按位插入
bool ListInsert(LinkList& L, int i, int e) {if (i < 1)return false;//判斷位序i是否合法LNode* p;//指針指向當(dāng)前掃面到的節(jié)點(diǎn)int j = 0;//記錄p指向的節(jié)點(diǎn)的位序p = L;//L指向頭節(jié)點(diǎn),從頭開始while (p != NULL && j < i - 1) {//循環(huán)掃描p = p->next;j++;}if (p == NULL) //i值超過來表長,不合法return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;//下面的順序不可交換s->next = p->next;p->next = s; //將結(jié)點(diǎn)s連到p之后return true;
}
后插操作:(包含于之前的插入操作之中)
//指定節(jié)點(diǎn)的后插操作
bool InsertNextNode(LNode* p, int e) {if (p == NULL)return false;//判斷指定節(jié)點(diǎn)是否存在LNode* s = (LNode*)malloc(sizeof(LNode));if (s == NULL)return false;//分配內(nèi)存失敗s->data = e;s->next = p->next;p->next = s;return true;
}
前插操作:由于難以獲得前一個(gè)鏈表元素信息,所以先完成后插,再交換兩者數(shù)據(jù)實(shí)現(xiàn)前插
//指定節(jié)點(diǎn)的前插操作
//先完成后插,再交換數(shù)據(jù)以實(shí)現(xiàn)前插
bool InsertPriorNode(LNode* p, int e) {if (p == NULL)return false;LNode* s = (LNode*)malloc(sizeof(LNode));if (s == NULL)return false;s->next = p->next;p->next = s;s->data = p->data;p->data = e;return true;
}
按指定位序刪除并返回值:
//按指定位序刪除節(jié)點(diǎn)并返回其值
bool ListDelete(LinkList& L, int i, int& e) {if (i < 1)return false;LNode* p;int j = 0;p = L;while (p != NULL && j < i - 1) {p = p->next;j++;}LNode* q = p->next;e = q->data;p->next = q->next;free(q);return true;
}
刪除指定節(jié)點(diǎn):若p為最后一個(gè)元素,則存在問題,只能通過從頭結(jié)點(diǎn)開始順序找到其前序節(jié)點(diǎn)的方法來進(jìn)行刪除。
//刪除指定節(jié)點(diǎn)
bool DeleteNode(LNode* p) {if (p == NULL){return false;}LNode* q = p->next;//令q指向*p的后續(xù)結(jié)點(diǎn)p->data = p->next->data;//和后續(xù)結(jié)點(diǎn)交換數(shù)據(jù)域p->next = q->next;//將*q結(jié)點(diǎn)從鏈中“斷開”free(q);//釋放后續(xù)結(jié)點(diǎn)的存儲(chǔ)空間return true;
}
按值查找:
//按值查找
LNode* LocateElem(LinkList L, int e)
{LNode* p = L->next;//從第1個(gè)結(jié)點(diǎn)開始查找數(shù)據(jù)域?yàn)閑的結(jié)點(diǎn)while (p != NULL && p->data != e){p = p->next;}return p;//找到后返回該結(jié)點(diǎn)指針,否則返回NULL;
}
按位查找:
//按位查找
LNode* GetElem(LinkList L, int i)
{if (i < 0){return NULL;}LNode* p;//指針p指向當(dāng)前掃描到的結(jié)點(diǎn)int j = 0;//當(dāng)前p指向的是第幾個(gè)結(jié)點(diǎn)p = L;//L指向頭結(jié)點(diǎn),頭結(jié)點(diǎn)是第0個(gè)結(jié)點(diǎn)(不存數(shù)據(jù))while (p != NULL && j < i){p = p->next;j++;}return p;
}
求表長:
//求表長
int Lnegth(LinkList L)
{int len = 0;//統(tǒng)計(jì)表長LNode* p = L;while (p->next != NULL){p = p->next;len++;}return len;
}
尾插法建表:設(shè)置一個(gè)表尾指針,方便直接在隊(duì)尾進(jìn)行尾插操作
//尾插法建立單鏈表(正向建立單鏈表)
LinkList List_TailInsert(LinkList& L)
{int x;L = (LinkList)malloc(sizeof(LNode));//建立頭結(jié)點(diǎn)LNode* s, * r = L;//r為表尾指針,方便尾插scanf("%d", &x);//輸入結(jié)點(diǎn)的值while (x != 9999)//輸入9999表示結(jié)束{s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;//r指向新的表尾結(jié)點(diǎn),永遠(yuǎn)保持r指向最后一個(gè)結(jié)點(diǎn),避免重復(fù)操作scanf("%d", &x);}r->next = NULL;return L;
}
頭插法建立單鏈表(不斷對(duì)頭結(jié)點(diǎn)進(jìn)行尾插操作)
//頭插法建立單鏈表(不斷對(duì)頭結(jié)點(diǎn)進(jìn)行尾插操作)
LinkList List_HeadInsert(LinkList& L)//逆向建立單鏈表
{LNode* s;int x;L = (LinkList)malloc(sizeof(LNode));//創(chuàng)建頭結(jié)點(diǎn)L->next = NULL;//初始為空鏈表scanf("%d", &x);//輸入結(jié)點(diǎn)的值while (x != 9999)//輸入9999表示結(jié)束{s = (LNode*)malloc(sizeof(LNode));//創(chuàng)建新結(jié)點(diǎn)s->data = x;s->next = L->next;L->next = s;//將新結(jié)點(diǎn)插入表中,L為頭指針scanf("%d", &x);}return L;
}
雙鏈表
在單鏈表的基礎(chǔ)上加入prior前驅(qū)指針,使得插入、刪除操作的時(shí)間復(fù)雜度變?yōu)镺(1)(可以很方便地找到前驅(qū))
結(jié)構(gòu)體:
typedef struct DNode {int data;//數(shù)據(jù)域struct DNode* prior, * next;//前指針和后指針
} DNode, * DLinkList;
初始化:
//初始化
bool InitDLinkList(DLinkList& L) {L = (DNode*)malloc(sizeof(DNode));//分配一個(gè)頭節(jié)點(diǎn)if (L == NULL)return false;L->prior == NULL;//頭節(jié)點(diǎn)前后指針都指向空L->next == NULL;return true;
}
判空:
//判空
bool Empty(DLinkList L) {return (L->next == NULL);
}
后插:
//指定節(jié)點(diǎn)的后插操作
bool InsertNextElem(DNode* p, DNode* s) {s->next = p->next;if (p->next != NULL){p->next->prior = s;//防止出現(xiàn)p后面沒有后繼結(jié)點(diǎn)的情況}s->prior = p;p->next = s;
}
刪除p后繼結(jié)點(diǎn):
//刪除P節(jié)點(diǎn)的后繼節(jié)點(diǎn)
bool DeleteNextNode(DNode* p) {if (p == NULL)return false;//p節(jié)點(diǎn)為空DNode* q = p->next;if (q == NULL)return false;//P節(jié)點(diǎn)沒有后繼p->next = q->next;if (q->next != NULL)//q不是最后一個(gè)節(jié)點(diǎn)q->next->prior = p;free(q);//手動(dòng)釋放內(nèi)存空間return true;
}
銷毀整個(gè)表:
//銷毀整個(gè)表
bool DestroyList(DLinkList& L) {//循環(huán)刪除并釋放每個(gè)節(jié)點(diǎn)while (L->next != NULL)DeleteNextNode(L);free(L);//釋放頭節(jié)點(diǎn)L = NULL;//頭指針指向NULL
}
循環(huán)鏈表
循環(huán)鏈表的最后一個(gè)指針不是NULL而是改為指向頭結(jié)點(diǎn)。
循環(huán)單鏈表:
結(jié)構(gòu)體:
typedef struct LNode {int data;struct LNode* next;
}LNode, * LinkList;
初始化:
//初始化一個(gè)循環(huán)單鏈表
bool InitRLinkList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));//分配一個(gè)頭節(jié)點(diǎn)if (L == NULL)return false;//內(nèi)存不足,分配失敗;L->next = L;//頭節(jié)點(diǎn)nex指向頭節(jié)點(diǎn),以此形成循環(huán)鏈表return true;
}
判空:
bool Empty(LinkList L)
{if (L->next == L)return true;elsereturn false;
}
判尾:
//判斷P是不是表尾指針
bool IsTail(LinkList L, LNode* p) {return (p->next == L);
}
循環(huán)雙鏈表:
結(jié)構(gòu)體:
typedef struct DNode {int data;struct DNode* prior, * next;
}DNode, * DLinkList;
初始化:
//初始化
bool InitRDLinkList(DLinkList& L) {L = (DNode*)malloc(sizeof(DNode));//分配頭節(jié)點(diǎn)if (L == NULL)return false;L->prior = L;L->next = L;//循環(huán)抱住自己return true;
}
判尾:
//判斷節(jié)點(diǎn)p是不是循環(huán)雙鏈表的表尾節(jié)點(diǎn)
bool iTail(DLinkList L, DNode* p) {return (p->next == L);
}
插入:
//在p節(jié)點(diǎn)之后插入s節(jié)點(diǎn)
bool InsertNextDNode(DNode* p, DNode* s) {s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;return true;
}
刪除:
//刪除操作
bool DeleteNextDNode(DLinkList& L, DNode* p) {DNode* q = p->next;p->next = q->next;q->next->prior = p;free(q);return true;
}
靜態(tài)鏈表
靜態(tài)鏈表借助數(shù)組來描述線性表的線性存儲(chǔ)結(jié)構(gòu),這里的指針next記錄的是結(jié)點(diǎn)的相對(duì)地址(數(shù)組下標(biāo)),又稱游標(biāo),和順序表一樣,靜態(tài)鏈表也要預(yù)先分配一塊連續(xù)的內(nèi)存空間。
靜態(tài)鏈表以next==-1作為結(jié)束標(biāo)志,插入、刪除操作與動(dòng)態(tài)鏈表的相同,只需要修改指針,而不需要移動(dòng)元素。
結(jié)構(gòu)體:
//第一種定義方法
struct Node0 {int data;//存儲(chǔ)數(shù)據(jù)元素int next;//下一個(gè)元素的數(shù)組下標(biāo)
};
typedef struct Node SLinkList[MaxSize];//第二種定義方法
typedef struct Node {int data;int next;
}SLinkList[MaxSize];
優(yōu)點(diǎn):增刪操作不需要大量移動(dòng)元素
缺點(diǎn):不能隨機(jī)存取,只能從頭結(jié)點(diǎn)開始一次往后查找:容量固定不可變
順序表鏈表比較
邏輯結(jié)構(gòu):
都屬于線性表,都是線性結(jié)構(gòu)。
采用順序存儲(chǔ)時(shí),邏輯上相鄰的元素,物理存儲(chǔ)位置也相鄰,采用鏈?zhǔn)酱鎯?chǔ)時(shí),邏輯上相鄰的元素,物理存儲(chǔ)位置不一定相鄰,邏輯關(guān)系通過指針鏈接表示。
存儲(chǔ)結(jié)構(gòu):
基本操作:
總結(jié):
主要參考:王道考研課程
后續(xù)會(huì)持續(xù)更新考研408部分的學(xué)習(xí)筆記,歡迎關(guān)注。
github倉庫(含所有相關(guān)源碼):408數(shù)據(jù)結(jié)構(gòu)筆記