為了做筆記，以備在外面用到。
線性表定義：
零個或多個數據元素的有限序列
序列(一個元素,前只有一個,後也只能接一個。除第一個及最後外)
其中其中要具有 1.一致(指數據元素類型 ; 2. 線性(只能一個接一個) ; 3.有限(有限多個)
(如，排隊；反之公司組識則不是)
線性表(list)的抽象數據類型(ADT)：
ADT 線性表(list)
Data
線性表的數據對象集合為{a1,a2,...,aN},每個元素的類型都為DataType。其中除了第一個元素a1外
每個元素都有前一個元素，而除了最後一個元素外都有後一個元素。數據元素之間為一對一的關係.
Operation
IinitList(*L); //初始化建立一個新的list
ListIsEmpty(*L); //檢查是否為空list
ClearList(*L); //清空所傳所的list
GetElem(L,i,*e); // 將list中的第i個位置元素值給e.
LocateElem(L,e); //在list中尋找是否有等於e的元素,並傳回其位置。沒有則傳回 -1
ListInsert(*L,i,e); //在線性表L中第i位置中,插入新元素e
ListDelete(*L,i,*e); //刪除線性表L中第i的元素,並給e傳回.
ListLength(L); //傳回其長度
endADT
線性表
線性表 | ||||
順序存儲(陣列) | 鏈接式(link) | |||
單鏈式 | 靜態 | 循環 | 雙向循環 |
鏈接式中,單鏈式是指其方向(指針).靜態則是其在不具有指標下.循環則是多了rear(最後指針). 雙向循環則是在每一個node中都有二個指針.
接下來會依序介紹
A. 順序存儲的線性表(用一段連線的位址儲存數據元素)
typedef struct
{
ElemType data[MAXSIZE]; /*陣列儲存資料元素，最大值為MAXSIZE*/
int length; /*線性串列的目前長度*/
}SqList
//length ,MAXSIZE為不同。
//length為目前長度; MAXSIZE為陣列長度
A.1位址計算
| a1 | a2 | a3 | .. | .. | .. | ai-1 | ai |
0 1 2 i i+1
其儲存位置和資料索引並不相同(C語言)
其儲存位置和資料索引並不相同(C語言)
Loc(ai)= Loc(a1)+(i-1)*c //c為長度.
故其存取時間只需O(1).
/* 初始條件：順序線性串列L已存在，1<;=i<=ListLength(L) */
/* 執行結果：用e傳回L中第i個資料元素的值 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<;1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}
A.插入,刪除 (時間複複度O(N)
/* 初始條件：順序線性串列L已存在,1<=i<=ListLength(L)， */
/* 執行結果：在L中第i個位置之前插入新的資料元素e，L的長度加1 */
//1.檢查插入位址?
//2.從最後到第i的資料向後,移一個
//3.在第i的位置加入e
//4.長度+1
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length==MAXSIZE) /* 順序線性串列已經滿 */
return ERROR;
if (i<1 || i>L->length+1)/* 當i比第一位置小或比最後一位置的後一位置還要大時 */
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;
}
/* 初始條件：順序線性串列L已存在，1<=i<=ListLength(L) */
/* 執行結果：刪除L的第i個資料元素，並用e傳回其值，L的長度減1 */
//1.檢查位置
//2.取出元素
//3.從刪除位置到最後,往前一個
//4.長度--
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length==0) /* 線性串列為空 */
return ERROR;
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與後面元素ai+1之間的邏輯關,對於數據ai中,除了本身的資料還要有其指示後面元素的位置。(元素ai中,儲存本身為數據域；而儲存位置為指針域。合起來稱為Node)
… | Ai | 0x500 | .. | Ai+1(0x500) | 0x100 |
Data point
B1.而第一個Node(節點)稱為頭結點,其中頭結點的data可能無效或是其它附加資料(長度),而頭結點的point所指向的Node才是第一Node.而最後的Node的point為NULL.
B2.
( 開Node ) (第一結點 ) (最後結點)
…. | Flag | 0x0100 | … | A1(0x100) | 0x0200 | ….. | an | null |
B3.其資料data structure
typedef struct Node
{
ElemType data;
struct Node *next;
}Node; //定義了Node為struct Node
typedef struct Node *LinkList; /* 定義LinkList *
B4.linklist讀取(時間O(N))
/* 初始條件：順序線性串列L已存在，1<=i<=ListLength(L) */
/* 執行結果：用e回傳L中第i個資料元素的值 */
//1.宣告一個node P指向link list的第一個node,初始化j=1
//2.當j<i時, 經link,p向後移動,並j++
//3.若p為NULL,return false
//4.回傳p的data
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p; /* 宣告一節點p */
p = L->next; /* 讓p指向鏈結串列L的第一個節點 */
j = 1; /* j為計數器 */
while (p && j<i) /* p不為空，或計數器j還沒有等於i時，迴圈繼續 */
{
p = p->next; /* 讓p指向下一個節點 */
++j;
}
if ( !p || j>i )
return ERROR; /* 第i個元素不存 */
*e = p->data; /* 取得第i個元素的資料 */
return OK;
}
B.3 插入(時間為(O(1))
/*初始條件：順序線性表L已存在,1<=i<=ListLength(L)，*/
/*執行結果：在L中第i個位置之前插入新的資料元素e，L的長度加1*/
//1.宣告p為第一Node,j=1
//2.當j<i,p向後移,並j++
//3.若p==NULL則為不存在
//4.則可找到並新增s Node
//5.將數據e給s->data
//6.插入s->next=p->next; p->next=s; 順序**
//7.return OK
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = *L;
j = 0;
while (p && j < (i-1)) /* 尋找第i個節點 */
{
p = p->next;
++j;
}
if (!p || j > (i-1))
return ERROR; /* 第i個元素不存在 */
s = (LinkList)malloc(sizeof(Node)); /* 產生新節點(C語言標準函式) */
s->data = e;
s->next = p->next; /* 將p的後繼節點變成s的後繼 */
p->next = s; /* 將s變成p的後繼 */
return OK;
}
B.4 刪除(O(1))
/*初始條件：順序線性串列L已存在，1<=i<=ListLength(L) */
/*執行結果：刪除L的第i個資料元素，並用e傳回其值，L的長度減1*/
//1.宣告一個node p指向第一個node(頭節點),初始化j=1;
//2.當j<i時,p往後移動,j++
//3.若p為NULL,return ERROR
//4.成功找到,將若刪除的node q= p->next;
//5.刪除p->next=q->next;
//6.q node的數據給e.
//7.fre q
//8.return ok
Status ListDelete(LinkList *L,int i,ElemType *e)
{
int j;
LinkList p,q;
p = *L;
j = 1;
while (p->next && j < i) /* 走訪尋找第i個元素 */
{
p = p->next;
++j;
}
if (!(p->next) || j > i)
return ERROR; /* 第i個元素不存在 */
q = p->next;
p->next = q->next; /* 將q的後繼變成p的後繼 */
*e = q->data; /* 將q節點中的資料給e */
free(q); /* 讓系統回收此節點，釋放記憶體 */
return OK;
}
關於時間複雜度.
在陣列中,若要連續新'刪10個時,其每次都要移動n-i個且每次都是O(n).
但在link中,則除了第一個需要O(n)外其它則以此,故只需O(1)
B.5 builder link list.(特別注意,CreateListHead)
1: /* 隨機產生n個元素的值，建立一個有首節點的單向鏈結串列L（頭插法）
2: 1.宣告一個節點Node,p 和counter i
3: 2.初始化頭節點L
4: 3.讓頭節頭的next=NULL,
5: 4.循環
6: 新增節點p
7: 給其數值0xc
8: 將p插入到前一節點中.
9: */
10: 11: void CreateListHead(LinkList *L, int n)
12: { 13: LinkList p;14: int i;
15: srand(time(0)); /* 初始化亂數種子 */
16: *L = (LinkList)malloc(sizeof(Node));
17: (*L)->next = NULL; /* 先建立一個有首節點的單向鏈結串列 */
18: for (i=0; i<n; i++)
19: {20: p = (LinkList)malloc(sizeof(Node)); /* 產生新節點 */
21: p->data = rand()%100+1; /* 隨機產生100以內的數字 */
22: p->next = (*L)->next; 23: (*L)->next = p; /* 插入到串列的前端 */
24: } 25: } 26: 27: /* 隨機產生n個元素的值，建立一個有首節點的單向鏈結串列L（尾插法
28: 其L指整個link list; r為尾結點.r會改變.
29: r->next=p;r=p; //p為新增,r指向最後
30: */
31: void CreateListTail(LinkList *L, int n)
32: { 33: LinkList p,r;34: int i;
35: srand(time(0)); /* 初始化亂數種子 */
36: *L = (LinkList)malloc(sizeof(Node)); /* L為整個鏈結串列 */
37: r=*L; /* r為指向尾部的節點 */
38: for (i=0; i<n; i++)
39: {40: p = (Node *)malloc(sizeof(Node)); /* 產生新節點 */
41: p->data = rand()%100+1; /* 隨機產生100以內的數字 */
42: r->next=p; /* 將尾端節點的指標指向新節點 */
43: r = p; /* 將目前的新節點定義為尾端節點 */
44: }45: r->next = NULL; /* 表示目前鏈結串列結束 */
46: }B.6刪除整個list
1: /*初始條件：順序線性串列L已存在，1<=i<=ListLength(L) */
2: /*執行結果：刪除L的第i個資料元素，並用e傳回其值，L的長度減1
3: 1.宣告node p,q
4: 2.p=第一節點(非頭節點)
5: 3.循環
6: 將下一節點給q,
7: free p
8: p=q.
9: */
10: Status ListDelete(LinkList *L,int i,ElemType *e)
11: { 12: int j;
13: LinkList p,q; 14: p = *L; 15: j = 1;16: while (p->next && j < i) /* 走訪尋找第i個元素 */
17: { 18: p = p->next; 19: ++j; 20: }21: if (!(p->next) || j > i)
22: return ERROR; /* 第i個元素不存在 */
23: q = p->next;24: p->next = q->next; /* 將q的後繼變成p的後繼 */
25: *e = q->data; /* 將q節點中的資料給e */
26: free(q); /* 讓系統回收此節點，釋放記憶體 */
27: return OK;
28: }應用：
以其應用的特性來決定。
若需要常去尋找資料，少新增'刪時可以陣列方式。
但若不知其大小或需要常改變時,則可改用link
循環list
將單鏈表中終端node由NULL改為指向頭節點，即形成一個circular link list.
單鏈表與循環表之差在於循環的判斷條件，原為是判斷是NULL,改為check是否為頭節點。
循環list可以
1.從任一node,存取全部list.
2.用O(1)存取最後一個元素(在加入一個指向最後的尾指針)
雙向double list
(與單向的linklist相同.可以單方向的操作.ListLength,GetElem,Ehgdi .只需在新增'刪除元素時)
1: typedef struct Node
2: { 3: ElemType data;4: struct Node *next;
5: struct Node *prior;
6: }Node;7: typedef struct Node *LinkList; /* 定義LinkList *
在與單鏈表中
不變地有ListLength,GetElem,LocateElem
但對於新增及刪除需改(先搞定新增的,再去改前'後的)
1: 2: /*初始條件：順序線性表L已存在,1<=i<=ListLength(L)，*/
3: /*執行結果：在L中第i個位置之前插入新的資料元素e，L的長度加1*/
4: Status ListInsert(LinkList *L,int i,ElemType e)
5: { 6: int j;
7: LinkList p,s; 8: p = *L; 9: j = 1;10: while (p && j < i) /* 尋找第i個節點 */
11: { 12: p = p->next; 13: ++j; 14: } 15: if (!p || j > i)
16: return ERROR; /* 第i個元素不存在 */
17: s = (LinkList)malloc(sizeof(Node)); /* 產生新節點(C語言標準函式) */
18: /*
19:
20: ---------- ----------
21: | | | | | | | |
22: | | | | | | | |
23: --------|- -|-------
24: | p | | P->next
25: | |--|----- |
26: | -----|--- |
27: ---| | | |----|
28: | | | |
29: ---------
30: S
31: */
32: s->data=e; 33: s->prior=p; 34: s->next=p->next; 35: p->next->prior=s; 36: p->next=s; 37: return OK;
38: }
1: 2: /*初始條件：順序線性串列L已存在，1<=i<=ListLength(L) */
3: /*執行結果：刪除L的第i個資料元素，並用e傳回其值，L的長度減1*/
4: Status ListDelete(LinkList *L,int i,ElemType *e)
5: { 6: int j;
7: LinkList p,q;8: p = (*L);//->next;
9: j = 1;10: while ((p->next!=*L) && j < i) /* 走訪尋找第i個元素 */
11: { 12: p = p->next; 13: ++j; 14: }15: if ((p->next==*L) || j > i)
16: return ERROR; /* 第i個元素不存在 */
17: p=p->next; 18: p->prior->next=p->next; 19: p->next->prior=p->prior; 20: *e=p->data; 21: free(p); /* 讓系統回收此節點，釋放記憶體 */
22: return OK;
23: }ADT：
數學抽象特性
其數學模型及定義在該模組上的操作而其抽象數據類型的定義僅取決於它的一組logic 特性
(和它如何在機器上實現無聯)
相關程式
沒有留言:
張貼留言