数据结构（二）:线性表包括顺序存储结构（顺序表、顺序队列和顺序栈）和链式存储结构（链表、链队列和链栈）...
還記得數據結構這個經典的分類圖吧：
今天主要關注一下線性表。
什么是線性表
線性表的劃分是從數據的邏輯結構上進行的。線性指的是在數據的邏輯結構上是線性的。即在數據元素的非空有限集中
(1)?存在唯一的一個被稱作“第一個”的數據元素，(2)?存在唯一的一個被稱作“最后一個”的數據元素，(3)?除第一個外，集合中的每個數據元素均只有一個前繼元素，(4)除最后一個外，集合中的每個數據元素均只有一個后繼元素。那么對于線性表，從存儲結構上分，可以有順序存儲結構和鏈式存儲結構。順序存儲結構包括順序表、順序隊列和順序棧；鏈式存儲結構包括鏈表、鏈隊列和鏈棧。所有這些分類數據結構的實現，后續的博文將陸續進行介紹。
順序表(數組,向量)
順序表的結構：
順序表的結構如下圖所示：從結構上可以看出，順序表實際上就是一個動態數組，在C++的標準模板庫（STL）中類似的對應著vector模板類。所以理解順序表對于使用vector進行高級應用的開發有著極為重要的作用。 存儲結構定義如下：
typedef struct
{
? DataType *m_pData;
? ? int m_nMax,m_nSize;
}SeqList;
typedef int DataType;
順序表的基本操作及其實現
有了數據的結構定義，就必須有對應的方法實現從來進行相關的操作，基本的運算函數如下：Void SetList(SeqList *L,int n);// 構造函數,建立數組長是n的空表
Void FreeList(SeqList *L); // 析構函數,釋放數組空間
int ListSize(SeqList *L) // 求表的長度
int IsEmpty(SeqList *L); // 判斷數組是否空,1:空,0滿
int IfFull(SeqList *L); // 判斷數組是否滿
DataType GetData(int pos); // 獲取數組某元素
int Locate(SeqList *L,DataTypeitem); // 判斷元素位置
Void SetData(SeqList *L,DataTypeitem,int pos); //元素位置賦值
Void Insert(SeqList *L,int pos,DataType item); //在某位置插入元素
void InsertRear(SeqList *L,DataType&item); // 在末尾插入元素
void Delete(SeqList *L,int pos);//刪除某位置元素
void ClearList(SeqList *L); // 清表,表中的元素個數是0;
Void DeleteBetween(SeqList *L,intstart, int end)
對應某些函數方法的實現如下：
voidSetList(SeqList *L,int n)
{
L->m_pData=newDataType[n];
if(L->m_pData==NULL)
{
? cout<<”overflow”<<endl;exit(1);
}
L->m_nMax=n;
L->m_nSize=0;
}
Void FreeList(SeqList *L)
{
delete [ ]L->m_pData;
L->m_nSize=0;
L->m_nMax=0;
}
void Insert(SeqList *L,DataType item,int pos)
{
//在順序表中在pos處插入item
? i=1;
? if(L->m_nSize==L->m_nMax){printf(“SeqListis FULL\n”);exit(1)}
? if(pos<=0||pos>L->m_nSize)
? {
? printf(“Pos is out of range”);exit(1);
? }
? for(i=L->m_nSize-1;i>=pos;i--)
? L->m_nData[i+1]=L->m_nData[i];
? L->m_nData[pos]=item;
? L->m_nSize++;
}
順序表的應用：動態字符串
C語言字符串
char str[13]=“Hello, world!”;
?char *pStr = str;
字符串函數?gets(char *str);
?puts(char *str);
?strcpy(char *str1, char *str2); //字符串拷貝
?strcat(char *str1, char *str2); //字符串連接,str1必須足夠大
?strcmp(char *str1, char *str2); //字符串比較
?strlen(char *str); //字符串求長,不包含’\0’的長度
動態字符串：
Typedef struct
?{
? ?int m_nSize;//不含結束符的長度
? ?char*m_pStr;
?}String;
基本運算： Concat(), SubString(), Insert(),Delete(),Clear()…順序隊列
一種特殊的線性表：只能在表的一端插入，另一端刪除，是先進先出的線性表；頭指針(刪除位置)和尾指針(插入位置) First come, first serve(FIFO) 優點：循環結構、刪除時不需移動元素順序隊列的結構：
順序隊列的結構如下圖所示：存儲結構定義如下： typedef struct
{
? DataType *m_pData;
? int m_nMax;
? int m_nFront,m_nRear, m_nSize;
}Queue;
順序隊列的基本操作及其實現
Void SetQueue(Queue *Q,int n); // 構造函數 void FreeQueue(Queun *Q); // 析構函數 int QSize(Queue *Q); // 隊列長度 int QEmpty(Queue *Q); // 判斷隊列是否空 int QFull(Queue *Q); // 判斷隊列是否滿 DataType QGetData(Queue *Q); // 獲取數據 int QInsert(Queue *Q,DataType item); // 進隊列 DataType QDelete(Queue *Q); // 出隊列 void QClear(); // 清空 隊列刪除操作：DataTypeQDelete(Queue *Q)
{
? DataType item;
? if(Q->m_nSize==0)
? {
printf(“隊列空\n”);
? ? Exit(1);
? }
? item=Q->m_pData[Q->m_nFront];
? Q->m_nFront=(Q->m_nFront+1)%Q->m_nMax;
? Q->m_nSize--;
}順序棧
一種特殊的線性表：只能在表的一端插入和刪除，是后進先出的線性表；進棧和出棧順序棧的結構：
結構如下圖所示：
Typedef struct
{
? DataType *m_pData;
? int m_nMax;
? int m_nTop;//插入數據的位置,空為-1,入棧+1,出棧-1
}Stack;
順序棧的基本操作
順序棧的基本操作如下： CStack()/CStack(int n); // 構造函數 ~CStack(); // 析構函數 int SetSize(int n); // 設置棧的大小 int Free(); // 釋放空間 int Size(); // 棧的大小 int Empty(); // 判斷是否空 int Full(); // 判斷是否滿 int Push(DataType item); // 壓棧 DataType Pop(); // 出棧 DataType GetPeek(); // 取棧頂元素 int Clear(); // 清空棧 順序棧的基本運算函數聲明如下： Void SetStack(Stack *S,int n); Void FreeStack(Stack *S); Int StackEmpty(Stack *S); Int StackFull(Stack *S); Void Push(Stack *S,DataType item); DataType Pop(Stack *S); Void ClearStack(Stack *S); DataType Peek(Stack *S);轉載于:https://www.cnblogs.com/huty/p/8519306.html
總結
以上是生活随笔為你收集整理的数据结构（二）:线性表包括顺序存储结构（顺序表、顺序队列和顺序栈）和链式存储结构（链表、链队列和链栈）...的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： jboss eap 6.2+ 版本中 加
- 下一篇： bootbox显示中文的按钮