大話資料結構——3線性表

線性表

線性表的定義

        定義：零個或多個資料元素的有限序列。

        一個有順序的序列。第一個元素無前驅，最後一個元素無後繼。其他每個元素都隻有一個前驅和一個後繼。

        線性表的元素個數n定義為線性表的長度n，當n=0的時候為空表。在非空的資料表中每個元素的位置都是固定的。

線性表的抽象資料類型

ADT	線性表 抽象資料類型

DATA:線性表的資料對象的集合是a1,a2,…,an,每個資料的資料類型是DataType.

Operation

InitList(*L): 初始化操作，建立一個空的線性表。

ListEmpty(L): 若線性表為空傳回true否則就傳回false

ClearList(*L):将線性表清空

GetElem(L,i,*e)：把資料表中第i個元素傳回給e

LocateElem(L,e):線上性表中查找與給定的e相等的元素，如果查找成功傳回該元素在表中的序列号；否則傳回0表示失敗

ListInsert(*L,i,e):線上性表中的第i個位置插入新元素e

ListDelete(*L,i,e):删除線性表中的第i個位置元素，并用e傳回其值

ListLength(L):傳回線性表L的元素個數

下面舉一個簡單的例子：

把兩個線性表進行合并把僅存在集合B的元素插入到集合A:

void unionL(List *La,List Lb)
{
 int La_len,Lb_len,i;
 ElemType e;
 La_len=ListLength(*La);
 Lb_len=ListLength(Lb);
   for(i=1;<Lb_len;i++)
  {
   GetElem(Lb,i,&e);//依次取出元素存入e
   if(!LocateElem(*La,e));//如果有與e相同的元素
   ListInsert(La,++La_len,e);//在La的末尾插入此相同元素
  }
}
           

3.4線性表的順序存儲結構

3.4.2順序存儲的定義

線性表有兩種實體存儲結構，一種是順序存儲，一種是鍊式存儲結構；

    順序存儲結構就是用一串位址連續的存儲單元依次存放線性表的資料元素。

3.4.2順序存儲方式

順序結構的存儲方式就是在記憶體中找了一塊區域把一串相同資料類型的資料元素存在這塊空地裡面。

順序表存儲結構代碼：

#define MAXSIZE 20
typedef int ElemType ;
typedef struct{
  ElemType data[MAXSIZE];
  int length;
}SqList;
           

這存儲空間有三個屬性

1. 存儲空間的其實位置:數組data
2. 存儲空間的最大長度:MAXSIZE
3. 線性表的目前長度：length

3.4.3資料長度與線性表的長度差別·

數組的長度和線性表的長度，其中數組的長度在一開始就被定義了，是一個不變的量，而線性表的長度随着資料的插入和删除會相應的增加和減小。一般來說線性表的長度要小于等于數組的長度。

3.4.4位址的計算方法

線性表的順序是從一開始的，但是我們定義的數組是從0開始的下标。就是說現線性表種的第i個元素對應的是數組下标為i-1的。在存儲器中每個存儲單元都有自己的編号，這個編号就叫做位址。這舉個例子來說明如何算目前的位址：

假設每個資料元素占c個位元組那麼線性表中第i個資料元素的位址和第i+1個資料元素位址之間有如下關系：（LOC表示擷取目前存儲位置的函數）

                                                            LOC(ai+1)=LOC(ai)+c

那麼第i個元素的位置就可以由第一個公式推算出：

                                                          LOC(ai)=LOC(a1)+(i-1)*c

由最後這個公式你可以很快的算出任何一個元素的位址，不管是第一個還是最後一個，都是相同的時間，是以對線性表的每個元素經行讀取和删除操作的時候，時間是一樣的。在算法中的概念就是算法的時間複雜度是O[1]這一存儲結構由被稱為随機存儲結構。

3.5順序存儲結構的插入與删除

3.5.1擷取元素操作

對于線性表的順序存儲結構我們進行GetElem操作：把順序表中的第i個元素傳回。在c語言中就是把數組下标為i-1的元素傳回：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
 typedef int Status;
 Status GetElem(SqList L,int i,ElemType *e)
 {
 if((L.length==0)||i<1||i>L.length)
 return ERROR;
 *e =L.data[i-1];
 reuturn OK;
 }
 
           

3.5.2插入操作

實作向線性表中插入一個元素，就是ListInsert(*L,i,e),向線性表的第i個位置插入元素e。

插入的思路：

1. 如果插入位置不合理，就抛出異常
2. 如果線性表長度大于數組長度就抛出異常或者動态增加記憶體
3. 從最後一個位置向前周遊到第i個位置，把他們都向後移動一個位
4. 将要插入的元素放入第i個位置
5. 表長加一

Status ListInsert(Sqlist *L,int i, ElemType e)
{
  int k;
  if(L->length==MAXSIZE)
  return ERROR;
  if (i<1||I>L->length-1)
  return ERROR;
  if(i<=L->length)
  {
  for(k=L=>length-1;k>=i-1;k--)
   {
    L->data[k+1]=L->data[k];
   }
   L->data[i-1]=e;
   L->length++;
   return OK;
  }
}
           

3.5.3删除操作

删除的算法思路：

1. 如果删除位置不合理就抛出異常
2. 取出删除元素
3. 從删除的元素後每個元素向前加一
4. 表長減一

具體代碼如下：

Status ListDelete(Sqlist *L,int i,ElemType *e)
{
    int k；
    if(L->length==0)
    rreturn ERROR;c
    if(i<1||i>L->length)
    return ERROR;
    *e=L->data[i-1];//取出被删除的元素
    if(i<L->length)
    {
    for(k=i;k<L->length;k++)
      L->data[k-1]=L->data[k];//向前挪動一位
    }
    L->length--;
    return OK;
}
           

線性存儲的優缺點

線性表的順序存儲結構的優點與缺點：

• 優點

  可以快速的存取表種任意位置的元素

  無需位表示表中元素之間的存儲關系增加額外的空間

• 缺點

  插入和删除操縱要移動大量的元素

  當線性表長度發生變化時難以确定存儲空間的容量

  容易造成存儲空間的碎片化

線性表的鍊式存儲結構

線性表的鍊式存儲結構定義

定義:用一組任意的存儲空間來存儲線性表的資料元素，存儲單元可以是線性的，也可以是不線性的。（這些資料元素可以存在任意未被配置設定的記憶體空間中）

    為了表示每個元素與其後繼元素之間的關系除了存儲資料本身的資訊外，還需要一個存儲一個訓示其直接後繼元素的資訊。

存儲元素資訊的域成為資料域

存儲直接後繼位置的域稱為指針域

指針域中存儲的資訊叫做指針或者鍊

這兩部分的資訊組成資料元素ai的存儲映像，叫做結點

n個這樣的結點連結成連結清單，成為線性表的鍊式存儲結構，由于每個結點的指針域中隻包含一個指針資訊，是以稱為單連結清單。

對線性表來說肯定有頭和尾

頭：我們把連結清單中第一個結點的存儲位址當作頭指針

尾：我們規定線性表的最後一個結點的指針位NULL空指針。

為了表示友善，我們常常在第一個結點前加上一個頭結點，頭結點不包含任何的資料，指針域包含一個頭指針指向第一個結點

3.6.4線性表的鍊式存儲結構的代碼實作

單連結清單，在c語言中用結構體就能進行很好的建構：

typedef struct Node
{
  ElemType data;
  struct Node *next;
}Node;
typedef struct Node *LinkList;//定義LinkList
           

可以清楚的看到，結點由存放資料元素的資料與存放下一個結點位址的指針與構成。

假設p是指向線性表的第i個元素的指針，則該節點的的資料可以用p->data來表示

而下一個節點的資料表示為：p->next->data;

3.7單連結清單的讀取

線上性表的順序存儲結構中，由于元素是按順序存在數組裡面的是以很容易知道任意一個元素線上性表中位置。但是當線性表是鍊式存儲結構，要想通路第i個元素就必須從一開始查找。算法思路：

1. 申明一個指針p指向連結清單的第一個結點，初始化j從第1開始
2. j小于i的時候指針就不斷向後周遊
3. 若到連結清單末尾p為空，則說明第i個結點不存在

4. 否則查找成功，并且傳回p指針的資料

   具體實作代碼如下：

//用e傳回L中第i個元素的值
Status GetElem (LinkList L,int e,ElemType *e)
{
  int j;
  LinkList  p;
  p=L->next;
  j=1;
   while(p&&j<i)//指針不為空且j始終小于i
   {
    p=p-next;
    j++;
   }
   if(!p||j>1)
   return ERROR;
   *e =p->data;
   return OK;
}
           

此算法的時間複雜度取決于i的大小，最壞情況時間複雜度為O[n],核心為工作指針後移

3.8單連結清單的插入與删除

3.8.1單連結清單的插入

單連結清單的插入，假設要，存儲單元e的結點為s，要實作結點p,p->next和s之間的邏輯關系變化，隻需要把s結點插入到p和p->next中，不許需要改變其他結點。

s->next=p->next;p->next=s;

讓p的後繼結點改成s的後繼結點再把結點s變成p的後繼結點。

1. 指針p指向連結清單頭結點，初始化j從i開始
2. 當j’<i的時候就周遊連結清單。讓p的指針向後移動，不斷到下一結點，j++
3. 若連結清單末尾p為空則說明第i個結點不存在
4. 否則查找成功，在系統中生成一個空結點s
5. 将資料元素e指派給s->data
6. 單連結清單的插入标準語句s->next=p->next,p->next=s;

7. 傳回成功

   代碼實作如下：

Status ListInsert(ListType *L,int i,ElemType e)
{
 int j;
 LinkList p,s;
 p=*L;
 j=1;
 while(p&&j<i)
  {
   p=p->next;
   ++j;
  }
  if(!p||j>i)
  {
  s=(LinkList)malloc(sizeof(Node))//為新生成的結點申請記憶體空間
  s->data=e;
  s->next=p->next;
  p->next=s;
  return OK;
  }
}
           

3.8.2單連結清單的删除

這裡要做的就是把p->next=p->next->next現在用q代表p->next;

q=p->next;p->next=q->next;

就是把p的後繼結點變成p的後繼結點的後繼結點；

1. 申明指針p指向表頭指針，j初始化為1
2. j<i就周遊整個連結清單
3. 若p指向空，則第i個結點不存在
4. 否則查找成功，将預删除的結點p->next指派給q
5. 單連結清單删除元素标準語句p->next=q->next;
6. 把q結點中的資料指派給e作為傳回
7. 釋放q結點

8. 傳回成功

   代碼如下：

Status ListDelete()
 {
  int j;
  LinkList p,q;
  p=*L;
  j=1;
  while(p->next&&j<i)
  {
   p=p->next;
   j++;
  }
  if(!(p->next)||j>i)
  return ERROR;
  q=p->next;
  p->next=q->next;
  *e =q->data;
  free(q);
  return OK;
 }

           

由此可以看出，如果對插入删除操作比較多的時候，用連結清單結構會比較有又是，如果隻是查找某個元素的話，線性表的順序存儲結構會友善很多。

3.9單連結清單的整體建立

回顧之前的可得：線性表的順序存儲結構就是數組的建立，為線性表的鍊式存儲結構就是一種動态結構，對于每個連結清單來說所占據的空間大小和位置是不需要預先劃分的，根據需要即使生成。單連結清單創立的整體思路如下：

1. 聲明一個指針p和計數器标量i
2. 初始化一個空連結清單
3. 讓L的頭結點指向NULL，建立一個代頭結點的空連結清單

4. 循環：

   生成一新結點指派給p

   随機生成一數字指派給p的資料域p->data

   将p插入到頭節點與前一新節點之間

   具體實作代碼如下：

void CreateListHead(LinkList *L,int n)
{
  LinkList p;
  int i;
  srand(time(0));
  *L=(LinkList)malloc(sizeof(Node));
  (*L)->next =NULL;
  for(i-0;i<n;i++)
  {
  p=(LinkList)malloc(sizeof(Node));
  p->data =rand()%100+1;//随機生成數字
  p->next =(*L)->next;
  (*L)->next=p;
  }
}