C++基礎語法梳理：資料結構丨順序結構

順序棧（Sequence Stack）

SqStack。cpp：

/*** @author huihut* @E-mail：huihut@outlook。com* @version 建立時間：2016年9月9日* 說明：本程式實現了一個順序棧。* 功能：有初始化、銷燬、判斷空、清空、入棧、出棧、取元素的操作。*/#include “stdio。h”#include “stdlib。h”#include “malloc。h”//5個常量定義#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1//測試程式長度定義#define LONGTH 5//型別定義typedef int Status；typedef int ElemType；//順序棧的型別typedef struct { ElemType *elem； int top； int size； int increment；} SqSrack；//初始化順序棧Status InitStack_Sq（SqSrack &S， int size， int inc） { S。elem = （ElemType *）malloc（size * sizeof（ElemType））； if （NULL == S。elem） return OVERFLOW； S。top = 0； S。size = size； S。increment = inc； return OK；}//銷燬順序棧Status DestroyStack_Sq（SqSrack &S） { free（S。elem）； S。elem = NULL； return OK；}//判斷S是否空，若空則返回TRUE，否則返回FALSEStatus StackEmpty_Sq（SqSrack S） { if （0 == S。top） return TRUE； return FALSE；}//清空棧Svoid ClearStack_Sq（SqSrack &S） { if （0 == S。top） return； S。size = 0； S。top = 0；}//元素e壓入棧SStatus Push_Sq（SqSrack &S， ElemType e） { ElemType *newbase； if （S。top >= S。size） { newbase = （ElemType *）realloc（S。elem，（S。size + S。increment） * sizeof（ElemType））； if （NULL == newbase） return OVERFLOW； S。elem = newbase； S。size += S。increment； } S。elem［S。top++］ = e； return OK；}//取棧S的棧頂元素，並用e返回Status GetTop_Sq（SqSrack S， ElemType &e） { if （0 == S。top） return ERROR； e = S。elem［S。top - 1］； return e；}//棧S的棧頂元素出棧，並用e返回Status Pop_Sq（SqSrack &S， ElemType &e） { if （0 == S。top） return ERROR； e = S。elem［S。top - 1］； S。top——； return e；}int main（） { //定義棧S SqSrack S； //定義測量值 int size， increment， i； //初始化測試值 size = LONGTH； increment = LONGTH； ElemType e， eArray［LONGTH］ = { 1， 2， 3， 4， 5 }； //顯示測試值 printf（“——-【順序棧】——-\n”）； printf（“棧S的size為：%d\n棧S的increment為：%d\n”， size， increment）； printf（“待測試元素為：\n”）； for （i = 0； i < LONGTH； i++） { printf（“%d\t”， eArray［i］）； } printf（“\n”）； //初始化順序棧 if （！InitStack_Sq（S， size， increment）） { printf（“初始化順序棧失敗\n”）； exit（0）； } printf（“已初始化順序棧\n”）； //入棧 for （i = 0； i < S。size； i++） { if （！Push_Sq（S， eArray［i］）） { printf（“%d入棧失敗\n”， eArray［i］）； exit（0）； } } printf（“已入棧\n”）； //判斷非空 if （StackEmpty_Sq（S）） printf（“S棧為空\n”）； else printf（“S棧非空\n”）； //取棧S的棧頂元素 printf（“棧S的棧頂元素為：\n”）； printf（“%d\n”， GetTop_Sq（S， e））； //棧S元素出棧 printf（“棧S元素出棧為：\n”）； for （i = 0， e = 0； i < S。size； i++） { printf（“%d\t”， Pop_Sq（S， e））； } printf（“\n”）； //清空棧S ClearStack_Sq（S）； printf（“已清空棧S\n”）； getchar（）； return 0；}

順序棧資料結構和圖片

typedef struct { ElemType *elem； int top； int size； int increment；} SqStack；

佇列（Sequence Queue）

佇列資料結構

typedef struct { ElemType * elem； int front； int rear； int maxSize；}SqQueue；

非迴圈佇列

非迴圈佇列圖片

SqQueue。rear++

迴圈佇列

迴圈佇列圖片

SqQueue。rear = （SqQueue。rear + 1） % SqQueue。maxSize

順序表（Sequence List）

SqList。cpp：

/*** @author huihut* @E-mail：huihut@outlook。com* @version 建立時間：2016年9月9日* 說明：本程式實現了一個順序表。*/#include “stdio。h”#include “stdlib。h”#include “malloc。h”//5個常量定義#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1//測試程式長度定義#define LONGTH 5//型別定義typedef int Status；typedef int ElemType；//順序棧的型別typedef struct { ElemType *elem； int length； int size； int increment；} SqList；//初始化順序表LStatus InitList_Sq（SqList &L， int size， int inc） { L。elem = （ElemType *）malloc（size * sizeof（ElemType））； if （NULL == L。elem） return OVERFLOW； L。length = 0； L。size = size； L。increment = inc； return OK；}//銷燬順序表LStatus DestroyList_Sq（SqList &L） { free（L。elem）； L。elem = NULL； return OK；}//將順序表L清空Status ClearList_Sq（SqList &L） { if （0 ！= L。length） L。length = 0； return OK；}//若順序表L為空表，則返回TRUE，否則FALSEStatus ListEmpty_Sq（SqList L） { if （0 == L。length） return TRUE； return FALSE；}//返回順序表L中元素個數int ListLength_Sq（SqList L） { return L。length；}// 用e返回順序表L中第i個元素的值Status GetElem_Sq（SqList L， int i， ElemType &e） { e = L。elem［——i］； return OK；}// 在順序表L順序查詢元素e，成功時返回該元素在表中第一次出現的位置，否則返回 - 1int Search_Sq（SqList L， ElemType e） { int i = 0； while （i < L。length && L。elem［i］！= e） i++； if （i < L。length） return i； else return -1；}//遍歷呼叫Status visit（ElemType e） { printf（“%d\t”， e）； return OK；}//遍歷順序表L，依次對每個元素呼叫函式visit（）Status ListTraverse_Sq（SqList L， Status（*visit）（ElemType e）） { if （0 == L。length） return ERROR； for （int i = 0； i < L。length； i++） { visit（L。elem［i］）； } return OK；}//將順序表L中第i個元素賦值為eStatus PutElem_Sq（SqList &L， int i， ElemType e） { if （i > L。length） return ERROR； e = L。elem［——i］； return OK；}//在順序表L表尾新增元素eStatus Append_Sq（SqList &L， ElemType e） { if （L。length >= L。size） return ERROR； L。elem［L。length］ = e； L。length++； return OK；}//刪除順序表L的表尾元素，並用引數e返回其值Status DeleteLast_Sq（SqList &L， ElemType &e） { if （0 == L。length） return ERROR； e = L。elem［L。length - 1］； L。length——； return OK；}int main（） { //定義表L SqList L； //定義測量值 int size， increment， i； //初始化測試值 size = LONGTH； increment = LONGTH； ElemType e， eArray［LONGTH］ = { 1， 2， 3， 4， 5 }； //顯示測試值 printf（“——-【順序棧】——-\n”）； printf（“表L的size為：%d\n表L的increment為：%d\n”， size， increment）； printf（“待測試元素為：\n”）； for （i = 0； i < LONGTH； i++） { printf（“%d\t”， eArray［i］）； } printf（“\n”）； //初始化順序表 if （！InitList_Sq（L， size， increment）） { printf（“初始化順序表失敗\n”）； exit（0）； } printf（“已初始化順序表\n”）； //判空 if （TRUE == ListEmpty_Sq（L）） printf（“此表為空表\n”）； else printf（“此表不是空表\n”）； //入表 printf（“將待測元素入表：\n”）； for （i = 0； i < LONGTH； i++） { if （ERROR == Append_Sq（L， eArray［i］）） printf（“入表失敗\n”）；； } printf（“入表成功\n”）； //遍歷順序表L printf（“此時表內元素為：\n”）； ListTraverse_Sq（L， visit）； //出表 printf（“\n將表尾元素入表到e：\n”）； if （ERROR == DeleteLast_Sq（L， e）） printf（“出表失敗\n”）； printf（“出表成功\n出表元素為%d\n”， e）； //遍歷順序表L printf（“此時表內元素為：\n”）； ListTraverse_Sq（L， visit）； //銷燬順序表 printf（“\n銷燬順序表\n”）； if （OK == DestroyList_Sq（L）） printf（“銷燬成功\n”）； else printf（“銷燬失敗\n”）； getchar（）； return 0；}

順序表資料結構和圖片

typedef struct { ElemType *elem； int length； int size； int increment；} SqList；