Linear_list

型別定義

一個線性表是n個資料元素的有限序列，線性表中的元素個數n定義為線性表的長度，n=0時成為空表；
抽象資料型別：

InitList(&L)                //構造空線性表L
DestroyList(&L)             //銷毀線性表L
ClearList(&L)               //將L重置為空表
ListEmpty(L)                //若L為空表回傳TRUE，否則回傳FALSE
ListLength(L)               //回傳L中資料元素個數
GetElem(L, i, &e)           //用e回傳L中第i個元素的值
//不常用
LocateElem(L, e, compare()) //回傳L中第一個與e滿足關系compare()的資料元素的位序，若不存在，則回傳0
PriorElem(L, cur_e, &pre_e) //用pre_e回傳L中資料元素cur_e的前驅
NextElem(L, cur_e, &next_e) //用next_e回傳L中資料元素cur_e的后繼
ListInsert(&L, i, e)        //在L的第i個位置前插入新資料元素e，長度更新
ListDelete(&L, i, &e)       //洗掉L的第i個資料元素，并用e回傳其值，長度更新
ListTraverse(L, visit())    //依次對L的每個資料元素呼叫函式visit()

順序表示和實作

順序表示

#define MAXSIZE 20
#define OK 1
#define ERROR 0
typedef struct{
  ElemType *elem;
  int length;
}SqList;

基本實作

InitList

Status InitList(SqList *L)
{ //構造空線性表
  L->elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
  if(!L->elem)
    return ERROR;
  L->length = 0;
  return OK;
}

ListInsert

Status ListInsert(SqList *L, int i, ElemType e)
{ //順序表插入
  int k;
  if(i < 1 || i > L->length + 1)
    return ERROR;
  for(k = L->length - 1; k >= i - 1; k--)
    L->elem[k + 1] = L->elem[k];
  L-elem[i - 1] = e;
  L->length++;
  return OK;
}

ListDelete

Status ListDelete(SqList *L, int i, ElemType *e)
{ //順序表洗掉
  int k;
  if(i < 1 || i > L->length)
    return ERROR;
  *e = L->elem[i - 1];
  if(i < L->length)
  {
    for(k = i; k < L->length; k++)
      L->elem[k - 1] = L->elem[k];
  }
  L->length--;
  return OK;
}

鏈式表示和實作

鏈式表示

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;

//節點結構體
typedef struct Node
{
  ElemType data;
  struct Node *next;
}Node;
//單鏈表
typedef struct
{
  int length;
  Node *next; //頭指標(不儲存任何值)，指向頭結點
}*LinkList;

基本實作

InitList

Status InitList(LinkList *L)
{ //創建單鏈表以及新節點
  LinkList p = (LinkList)malloc(sizeof(LinkList));
  Node *q = (Node *)malloc(sizeof(Node));   //創建頭結點
  q->next = NULL;
  p->next = q;
  p->length = 0;
  (*L) = p;
  return OK;
}

ListInsert

Status ListInsert(LinkList *L, ElemType elem. int pos)
{ //單鏈表插入
  if(pos < 1 || pos > (*L)->length + 1)
    return ERROR;     //范圍
  Node *p = (*L)->next;
  for(int i = 1; i < pos; i++)
    p = p->next;
  //創建新節點插入
  Node *q = (Node *)malloc(sizeof(Node));
  q->data = https://www.cnblogs.com/houchaoqun/p/elem;
  q->next = p->next;
  p->next = q;
  (*L)->length += 1;
  return OK;
}

ListDelete

Status ListDelete(LinkList *L, ElemType *elem, int pos)
{ //單鏈表洗掉
  if(pos < 1 || pos > (*L)->length)
    return ERROR;
  //查找
  Node *p = (*L)->next, *q;
  for(int i = 0; i < pos; i++)
    p = p->next;
  //洗掉
  q = p->next;
  p->next = q->next;
  free(q);
  (*L)->length -= 1;
  return OK;
}

回圈鏈表

表中最后一個節點的指標域指向頭結點，整個鏈表形成一個環；

考慮此時查找最后一個節點時其時間復雜度為O(n)，可對此優化在回圈鏈表中設立尾指標；同時這樣也可簡化某些操作，比如兩個線性表合并時，僅需將表的表尾與另一個表的表頭相接；

雙向鏈表

存盤結構

在雙向鏈表的節點中有兩個指標域，即后繼與前驅；

typedef struct DuLNode
{
  ElemType data;
  struct DuLNode *prior;
  struct DuLNode *next;
}DuLNode, *DuLinkList;

基本實作

ListInsert

Status ListInsert(DuLinkList *L, int i, ElemType e)
{ //插入操作
  DuLNode *p, *s = (DuLNode *)malloc(sizeof(DuLNode));
  //查找位置
  if(!(p = GetElemP_DuL(L, i)))
    return ERROR;
  s->data = https://www.cnblogs.com/houchaoqun/p/e;
  //更新s前驅
  s->prior = p->prior;
  p->prior->next = s;
  //更新s后繼
  s->next = p;
  p->prior = s;
  return OK;
}

ListDelete

Status ListDelete(LinkList *L, int i, ElemType *e)
{ //洗掉操作
  DuLNode *p;
  if(!(p = GetElemP_DuL(L, i)))
    return ERROR;
  (*e) = p->data;
  p->prior->next = p->next;
  p->next->prior = p->prior;
  free(p);
  return OK;
}

靜態鏈表

存盤結構

借用一維陣列來描述線性鏈表，便于在不設“指標”型別的高級程式設計語言中使用鏈表結構；
游標指向下一個節點，在作線性表的插入和洗掉操作時無需移動元素，僅需修改指標；
其中未被使用的陣列成為備用鏈表，插入時從其中取得，洗掉時回收到備用鏈表中；同時規定下標為0的cur為備用鏈表第一個節點的下標，陣列最后一個元素的cur為第一個有數值的元素的下標，若鏈表為空，則為0；

//靜態單鏈表存盤結構
#define MAXSIZE 1000  //鏈表最大長度
typedef struct
{
  ElemType data;
  int cur;  //游標，為0時無指向
}component, SLinkList[MAXSIZE];

基本實作

InitSpace_SL

void InitSpace_SL(SLinkList *space)
{ // 將一維陣列space中各分量鏈成一個備用鏈表，space[0].cur為頭指標
  for (int i = 0; i < MAXSIZE - 1; i++)
    space[i]->cur = i + 1;
  space[MAXSIZE - 1]->cur = 0;  //無指向
}

LocateElem_SL

Status LocateElem_SL(SLinkList *S, ElemType e)
{ // 查找元素，回傳位序
  int i = S[0]->cur;
  while (i && S[i]->data != e)
    i = S[i]->cur;
  return i;
}

Malloc_SL

int Malloc_SL(SLinkList space)
{ // 若備用空間鏈表非空，回傳分配的節點下標，否則為0
  int i = space[0].cur; // 每次從頭結點開始
  if (space[0].cur)     // 可分配
    space[0].cur = space[i].cur;
  return i;
}

Free_SL

void Free_SL(SLinkList *space, int k)
{ // 將下標為k的空閑節點回收到備用鏈表
  space[k]->cur = space[0]->cur;
  space[0]->cur = k;
  // 相當于在0與其[0].cur之間插入k
}

ListInsert

Status ListInsert(component *L, int i, ElemType e)
{ //插入操作
  if(i < 1 || i > ListLength(L) + 1)
    return ERROR;
  //獲取空間
  int k = Malloc_SL(L);
  n = MAXSIZE - 1;  //從最后一個元素開始，即頭結點
  if(k)
  {
    L[k].data = https://www.cnblogs.com/houchaoqun/p/e;
    for(int l = 1; l <= i - 1; l++)
      n = L[n]->cur;        //找到第i個元素前的下標
    L[k]->cur = L[n]->cur;  
    L[n]->cur = k;          //插入
    return OK;
  }
  return ERROR;
}

ListDelete

Status ListDelete(component *L, int i)
{
  if(i < 1 || i > ListLength(L) + 1)
    return ERROR;
  int n = MAXSIZE - 1;
  for(int j = 1; j <= i - 1; j++)
    n = L[n].cur;           //查找
  j = L[n].cur;
  L[n].cur = L[j].cur;      //洗掉
}

標籤：其他

上一篇：稀疏陣列

下一篇：返回列表