資料結構和算法(線性資料結構)

線性資料結構

包含n個相同性質資料元素的有限子列。

• .

  基本特征：

  1. 存在唯一的“第一個元素”
  2. 存在唯一的“最後一個元素”
  3. 除最後一個元素外，其他資料元素均有唯一的“直接後繼”
  4. 除第一個元素外，其他資料元素均有唯一的“直接前驅”
• 前後關系是“一對一關系”，即線性關系。

典型線性資料結構

• 棧 : 隻允許在末端進行操作
• 隊列 ：隻運作在兩端進行操作
• 線性表 ：允許在序列任意位置進行操作

棧

• 對于棧來說，最後一個元素所在端具有特殊意義，稱為棧頂；第一個元素稱為棧底；不含任何元素的棧稱為空棧。

  

• 棧的插入操作是将新的元素插入棧頂，稱為入棧，或壓棧。
• 棧的删除操作時删除棧頂的元素，稱為出棧，或彈棧。
• 棧的操作是按先進後出的操作原則進行的，故棧又稱為先進後出的線性資料結構。
• 棧的常用操作為：入棧、出棧、取棧頂元素。

隊列

• 通常将隊列的插入操作稱為入隊，隊列的删除操作稱為出隊，允許插入的一端稱為對尾，允許删除的一端稱為對頭。不含任何元素的隊列稱為空隊列。
• 隊列遵循先進先出的原則，是以隊列也稱為先進先出的線性資料結構。
• 隊列的常用操作：入隊，出隊，取隊頭元素等。

  

線性表

• 線性表的操作位置不受限制。線性表中所含資料元素的個數稱為線性表的長度，長度為0的表稱為空表。按元素升序或降序排列的線性表稱為有序線性表,簡稱有序表。
• 線性表中資料元素可以是數、字元、也可以是其他複雜資訊。

  

線性結構的存儲表示

• 主要形式：順序存儲和鍊式存儲
  • 順序存儲的特點是借助資料元素在存儲空間中的相對位置來表示元素之間的邏輯關系。最簡單的一種方式是用相鄰位置表示邏輯關系，即邏輯相鄰的元素在實體上也相鄰。

    

• 鍊式存儲的特點是借助訓示資料元素存儲的位址指針表示元素之間的邏輯關系。

  

  • 由于棧、隊列、線性表具有不同的操作特點，在實際組織連結清單時，會采用不同的方式；

    - 棧的操作隻允許在棧頂進行，故将其連結清單的頭指針作為棧頂指針，指向棧頂元素結點；

    - 隊列的操作隻允許在隊頭和隊尾兩端進行，故将其連結清單的指針作為隊頭指針，指向對頭元素結點，并增設隊尾指針指向隊尾元素結點；

    - 線性表的操作位置不受限制，故其具有多種連結清單組織方式。

順序存儲

順序棧

采用順序結構的棧稱為順序棧，即需要用一片位址連續的空間來存儲棧的元素。=>可用一個數組來實作，并指定棧頂元素位于序列末端，每當新元素入棧或出棧時，數組中其他元素可不改變位置，隻需改變棧頂位置即可。=>由于c語言數組的大小是預先固定的，空間存滿後，則不能繼續插入新元素；是以，可以采用動态配置設定的一段連續的存儲空間來儲存棧的元素。

順序棧的類型定義

typedef struct{
	ElemType * elem;	//存儲空間的基址
	int top;		//棧頂元素的下一個位置，簡稱棧頂位标
	int size;	//目前配置設定的存儲空間
	int increment;	//擴容時，增加的存儲容量
}SqStack;	//順序棧
           

• 初始化順序棧

  将順序棧S置為初始容量為size的空棧。算法複雜度O(1).

Status InitStack_Sq( SqStack &S, int size, int inc){
	//配置設定存儲空間
	S.elem = (ElemType * )malloc(size * sizeof(ElemType));
	if(NULL == S.elem)return OVERFLOW;	//空間配置設定失敗
	S.top = 0;	//置S為空棧
	S.size = size;	//初始容量值
	S.increment = inc;	//初始增量值
}
           

• 銷毀順序棧

Status DestoryStack_Sq(SeqStack &S)
{
    S.size = 0;
    S.increment = 0;
    free(S->elem);	//釋放順序棧配置設定的空間
}
           

• 判斷順序棧是否為空

Status StackEmpty_Sq(SqStack &S){
	if(S.top == 0)return TRUE;	//若棧頂位标為0，說明此時棧為空
	else return FALSE;  
}
           

• 清空棧S

Status ClearStack_Sq(SqStack &S){
	if(S == NULL){
		printf("順序棧不存在!\n");
		return;
	}
	S.top = 0;	//将棧頂位标置為棧底，此時将棧為空棧
	printf("順序棧清空成功！\n");  
}
           

• 元素壓棧

  

Status Push_Sq(SqStack &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;
}
           

• 棧頂元素出棧

Status Pop_Sq(SqStack &S, ElemType &e)
{
	if(NULL == S){
		printf("此棧不存在！\n");
		exit(-1);
	};
 
	if (pS->top <= 0)
	{
		printf("棧為空！\n");
		exit(-1);
	}
	else
	{
		e = S.elem[S.top];
		S.top--;
		return e;
	}
}
           

• 取棧頂元素

Status GetTop_Sq(SqStack &S, ElemType &e)
{
	if(NULL == S){
		printf("此棧不存在！\n");
		exit(-1);
	};
 
	if (pS->top <= 0)
	{
		printf("棧為空！\n");
		exit(-1);
	}
	else
	{
		e = S.elem[S.top];
		return e;
	}
}
           

循環隊列

采用順序結構存儲的隊列，需要按隊列可能的最大長度配置設定存儲空間。隊列經常在對頭何隊尾分别進行出隊和入隊的操作，需要設定兩個位标分别訓示對頭元素和隊尾元素的下一位置，分别叫做對頭位标和隊尾位标。

循環隊列的定義

typedef struct{
	ElemType * elem;	//存儲空間的基址
	int front;	//對頭位标
	int rear;	//隊尾位标，訓示隊尾元素的下一位置
	int maxSize;	//存儲容量
}
           

• 初始化操作

//構造一個空隊列，最大隊列長度為size
Status InitQueue_Sq(SqQueue &Q, int size){
	//配置設定存儲空間
	Q->elem	= (ElemType * )malloc(size * sizeof(ElemType));
	if(Q->elem == NULL)return OVERFLOW;
	Q.maxSize = size;
	Q.front = Q.rear = 0;	//置空
	return OK;
}
           

• 銷毀隊列
• 置為空隊列
• 判斷是否為空
• 隊列長度
• 擷取隊頭元素
• 隊尾插入元素（入隊）

Status EnQueue_Sq(SqQueue &Q, ElemType &e){
	//若隊列未滿，則插入元素為新隊列的隊尾元素
	 if((Q.rear + 1) % maxSize == Q.front) return ERROR;//判斷是否為空隊列
	 Q->elem[rear] = e;
	 Q.rear = (Q.rear + 1) % Q.maxSize;
	 return OK;
}
           

• 出隊

Status DeQueue_Sq(SqQueue &Q, ElemType &e){
	if(Q.front == Q.rear) return ERROR; //對列為空
	e = Q.elem[Q.front];
	Q.front = (Q.front + 1) % Q.maxSize;//更新隊頭，隊列循環
	return OK;
}
           

順序表

采用順序結構表示的線性表稱為順序表。用一組位址連續的存儲單元依次存放線性表的資料元素，即以存儲位置相鄰表示位序相繼的兩個元素之間的前驅和後繼關系。

順序表的定義

typedef struct{
	ElemType * elem; //存儲空間的基址
	int length;	//目前長度
	int size;	//存儲容量
	int increment;	//順序表
}SqList;	//順序表