基礎資料結構-串列(List)

串列（list）是有限的有序值的集合 $(A[0], A[1], ...A[n])$ 。

串列屬性：

串列的大小. 它表明串列中有多少元素。
可以檢索特定標號(index)的元素。
可以按照標號增加的順序遍歷串列。
可以改變特定標號的元素的值，同時不影響其他元素。
可以向特定標號插入一個元素。後面的元素標號增加1。
可以在特定標號刪除一個元素。後面的元素標號減少1。
串列的「頭」「尾」、「前」「後」
串列的「頭」（head），是指指向串列的第一個元素的指標或結點；因此，串列的「尾」（tail），是指遍歷串列到達的最後一個元素。
前向串列（forward list，如C++標準模板庫的實現）是指一個單向串列，從頭部開始，每個節點有一個next指標指向緊鄰的下一個節點。

串列(List)的實作

陣列串列 (Array List)
鏈結串列 (Linked List)

串列(List)的運作(operator)

/** List ADT */
public interface List<E> {
/** Remove all contents from the list, so it is once again
empty. Client is responsible for reclaiming storage
used by the list elements. */
public void clear();
/** Insert an element at the current location. The client
must ensure that the list’s capacity is not exceeded.
@param item The element to be inserted. */
public void insert(E item);
/** Append an element at the end of the list. The client
must ensure that the list’s capacity is not exceeded.
@param item The element to be appended. */
public void append(E item);
/** Remove and return the current element.
@return The element that was removed. */
public E remove();
/** Set the current position to the start of the list */
public void moveToStart();
/** Set the current position to the end of the list */
public void moveToEnd();
/** Move the current position one step left. No change
if already at beginning. */
public void prev();
/** Move the current position one step right. No change
if already at end. */
public void next();
/** @return The number of elements in the list. */
public int length();
/** @return The position of the current element. */
public int currPos();
/** Set current position.
@param pos The position to make current. */
public void moveToPos(int pos);
/** @return The current element. */
public E getValue();
}

鏈結串列 (Linked List)

鏈結串列是由許多相同資料型態的項目，所組成的有限序列。和陣列不同之處是鏈結串列使用動態記憶體配置來存放資料，並用指標」(pointer) 連結各個項目。我們知道在資料結構的領域中，主要分成兩種主幹：靜態資料結構及動態資料結構。而鏈結串列與指標(pointer)變數，則是動態資料結構的核心組成。鏈結串列是由一個或一個以上的「節點」(node)所組成，每一個節點至少會有兩個或兩個以上的欄位，分別存放資料(Data)及指標(Pointer)

基礎資料結構-堆疊(Stack)

限制只在串列（list）的一端進行操作，而且按照『後進先出(LIFO)』

堆疊操作： 堆疊資料結構使用兩種基本操作：推入（push）和彈出（pop）： 推入：將數據放入堆疊的頂端（陣列形式或串列形式），堆疊頂端top指標加一。 彈出：將頂端數據資料輸出（回傳），堆疊頂端資料減一。

堆疊特點： 先入後出，後入先出。除頭尾節點之外，每個元素有一個前驅，一個後繼。

基礎資料結構-佇列(Queue)

佇列只允許在串列後端（稱為rear）進行插入操作，在串列前端（稱為front）進行刪除操作。，而且按照『先進先出（FIFO)』

佇列操作：__ 佇列資料結構使用兩種基本操作：插入元素EnQueue和刪除元素DeQueue： 插入元素：將數據放入佇列的後端（陣列形式或串列形式）。 刪除元素：將佇列的前端輸出。

C語言的堆疊實作(陣列)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define stack struct Stack
#define STACK_POP_ERR 42
/* 堆疊資料結構 堆棧數據結構 */
struct Stack
{
  int val[10]; // 陣列空間
  int top; // 堆疊頂端指標（棧頂）
};
/* 檢查堆疊是否為空 */
bool empty(stack *stk) { return stk->top == 0; }
/* 推入資料 */
void push(stack *stk, int x)
{
  stk->top=stk->top+1;
  stk->val[stk->top]=x;
}
/* 彈出並返回資料 */
int pop(stack *stk)
{
  if(empty(stk))
    return STACK_POP_ERR; // 不能彈出
  else
  {
    stk->top=stk->top-1;
    return stk->val[stk->top+1];
  }
}
int main()
{
  // 宣告並初始化資料結構空間
  stack stk;
  stk.top=0;
  // 推入四個
  push(&stk, 3);
  push(&stk, 4);
  push(&stk, 1);
  push(&stk, 9);
  // 彈出三個
  printf("%d ", pop(&stk));
  printf("%d ", pop(&stk));
  printf("%d ", pop(&stk));
  return 0;
}

C語言的佇列實作(陣列)

#include<stdio.h>
#include<stdlib.h>
/*佇列資料結構*/
struct Queue
{
  int Array[10];//陣列空間大小
  int head;//前端(front)
  int tail;//後端(rear)
  int length;//佇列長度 //將其視為當前资料大小，並且使用這個成員判斷滿或空    
};
/*資料加入佇列*/
void EnQueue(struct Queue *Queue1,int x)
{
  Queue1->Array[Queue1->tail]=x;
  if(Queue1->tail+1==10)//Queue1->length改為空間大小10
  {
    Queue1->tail=0;//1改為0                 
  }
  else
  {
    Queue1->tail=Queue1->tail+1;
    //Queue1->length=Queue1->length+1;//這行邏輯上有問題   //Modify By pcjackal.tw //這行放於外面
  }
  Queue1->length=Queue1->length+1;//當前個數增1
}
/*資料移出佇列*/
int DeQueue(struct Queue *Queue1)
{
  int x=Queue1->Array[Queue1->head];
  if(Queue1->head+1==10)//空間大小10
  {
    Queue1->head=0;                               
  }
  else
  {
    Queue1->head=Queue1->head+1;    
  }
  Queue1->length=Queue1->length-1;//移出后減少1
  return x;
}
/*佇列操作*/
int main()
{
  struct Queue *Queue1=malloc(sizeof(struct Queue));//建立資料結構
  Queue1->length=0;//新增長度//10改為0，初始狀態
  Queue1->head=0;//必須要先初始化
  Queue1->tail=0;//必須要先初始化
  EnQueue(Queue1,5);//將5放入佇列
  EnQueue(Queue1,8);//將8放入佇列
  EnQueue(Queue1,3);//將3放入佇列
  EnQueue(Queue1,2);//將2放入佇列
  printf("%d ",DeQueue(Queue1));//輸出佇列(5)  
  printf("%d ",DeQueue(Queue1));//輸出佇列(8)
  printf("%d ",DeQueue(Queue1));//輸出佇列(3) 
  system("pause");   
}

C語言的堆疊實作(鏈結串列)

/* 链栈的结构定义 */
typedef struct {
  SLink top; 　 　// 棧頂指針
  int length; 　 // 棧中元素個數
} Stack;

// 构造空栈 S
void InitStack (Stack &S)
{
  S.top = NULL; 　　// 設棧頂指針的初值為"空"
  S.length = 0; 　　// 空棧中元素個數為0
}
// 如果指针反过来从栈底到栈顶的话，删除栈顶元素时，为修改其前驱指针，需要从栈底一直找到栈顶。

// 在棧頂S 之上插入元素e為新的棧頂元素，並返回成功與否
bool Push (Stack &S, ElemType e) {
 p = new LNode; 　　// 建新的結點
 if(!p)
   return false;　　// 存儲分配失敗
 p -> data = e;
 p -> next = S.top;// 鏈接到原來的棧頂
 S.top = p; 　　 　// 移動棧頂指針
 ++S.length;　　 　 // 棧的長度增1
}
// 在链栈的类型定义中设立“栈中元素个数”的成员是为了便于求得栈的长度。

// 刪除S 棧頂且以e 返回其數值，返回成功與否
bool Pop (Stack &S, SElemType &e)
{
  if (!S.top)
    return false;
  else
  {
     e = S.top -> data; 　　 // 返回棧頂元素
     q = S.top;
     S.top = S.top -> next; // 修改棧頂指針
     --S.length; 　　　　　 // 棧的長度減1
     delete q;　　　　　 　// 釋放被刪除的結點空間
     return true;
   }
}

C語言的佇列實作(循環佇列)

/* 隊列的順序存儲結構(循環隊列) */
#define MAX_QSIZE 5 /* 最大隊列長度+1 */
typedef struct
{
  QElemType *base; /* 初始化的動態分配存儲空間 */
  int front; /* 頭指針，若隊列不空，指向隊列頭元素 */
  int rear; /* 尾指針，若隊列不空，指向隊列尾元素的下一個位置 */
}SqQueue;

/* 循環隊列的基本操作(9個) */
void InitQueue(SqQueue *Q)
{ /* 構造一個空隊列Q */
  Q->base=malloc(MAX_QSIZE*sizeof(QElemType));
  if(!Q->base) /* 存儲分配失敗 */
    exit(OVERFLOW);
  Q->front=Q->rear=0;
}

void DestroyQueue(SqQueue *Q)
{ /* 銷毀隊列Q，Q不再存在 */
  if(Q->base)
    free(Q->base);
  Q->base=NULL;
  Q->front=Q->rear=0;
}

void ClearQueue(SqQueue *Q)
{ /* 將Q清為空隊列 */
  Q->front=Q->rear=0;
}

Status QueueEmpty(SqQueue Q)
{ /* 若隊列Q為空隊列，則返回TRUE；否則返回FALSE */
  if(Q.front==Q.rear) /* 隊列空的標誌 */
    return TRUE;
  else
    return FALSE;
}

int QueueLength(SqQueue Q)
{ /* 返回Q的元素個數，即隊列的長度 */
  return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE;
}

Status GetHead(SqQueue Q,QElemType *e)
{ /* 若隊列不空，則用e返回Q的隊頭元素，並返回OK；否則返回ERROR */
  if(Q.front==Q.rear) /* 隊列空 */
    return ERROR;
  *e=Q.base[Q.front];
  return OK;
}

Status EnQueue(SqQueue *Q,QElemType e)
{ /* 插入元素e為Q的新的隊尾元素 */
  if((Q->rear+1)%MAX_QSIZE==Q->front) /* 隊列滿 */
    return ERROR;
  Q->base[Q->rear]=e;
  Q->rear=(Q->rear+1)%MAX_QSIZE;
  return OK;
}

Status DeQueue(SqQueue *Q,QElemType *e)
{ /* 若隊列不空，則刪除Q的隊頭元素，用e返回其值，並返回OK；否則返回ERROR */
  if(Q->front==Q->rear) /* 隊列空 */
    return ERROR;
  *e=Q->base[Q->front];
  Q->front=(Q->front+1)%MAX_QSIZE;
  return OK;
}

void QueueTraverse(SqQueue Q,void(*vi)(QElemType))
{ /* 從隊頭到隊尾依次對隊列Q中每個元素調用函數vi() */
  int i;
  i=Q.front;
  while(i!=Q.rear)
  {
    vi(Q.base[i]);
    i=(i+1)%MAX_QSIZE;
  }
  printf("\n");
}

習題

1.撰寫程式hw7a, 執行6個堆疊操作: Push(5), Push(3), Push(10), Push(2), Push(7)，Pop()後，由堆疊頂端依序列印出元素 2.設計程式hw7b, 執行6個佇列操作: EnQueue(5), EnQueue(3), EnQueue(10), EnQueue(2), EnQueue(7)，DeQueue(), 由佇列前端依序列印出元素

Chapter8 串列、堆疊和佇列