線(xiàn)性表(什么是線(xiàn)性表的基本理論知)

1.什么是線(xiàn)性表的基本理論知

一、線(xiàn)性表（定義） 線(xiàn)性表（Linear List）：是具有相同屬性的數據元素的一個(gè)有限序列。

它有順序、鏈接、散列等存儲結構，第一元素稱(chēng)為表頭元素，最后一個(gè)元素稱(chēng)為表尾元素。在任意一對；相鄰結點(diǎn)ai,ai+1(1 線(xiàn)性表的基本特征：若至少含有有一個(gè)結點(diǎn)，則除起始結點(diǎn)沒(méi)有直接前趨外，其他結點(diǎn)有且僅有一個(gè)直接前趨；除終端結點(diǎn)沒(méi)有直接后繼外，其他結點(diǎn)有且僅有一個(gè)直接后繼。

二、線(xiàn)性表的存儲結構及基本運算 線(xiàn)性表根據其物理存儲連續性狀態(tài)及存儲順序可劃分為順序存儲結構和鏈表存儲結構。 順序存儲結構：把線(xiàn)性表中的所有元素按照其邏輯順序依次存儲到計算機存儲器中從指定存儲位置開(kāi)始的一塊連續的存儲空間中。

因此，邏輯結構中相鄰的結點(diǎn)在存儲結構中仍相鄰。我們把順序存儲的線(xiàn)性表統稱(chēng)為順序表，它的順序存儲結構是利用數組來(lái)實(shí)現的。

順序存儲下的線(xiàn)性表的基本運算： （1）初始化線(xiàn)性表。即構造一個(gè)空表，它的長(cháng)度（length）置0。

(2)清除線(xiàn)性表中的所有元素。 （3）獲取線(xiàn)性表的長(cháng)度。

（4）檢查線(xiàn)性表是否為空。 （5）獲取線(xiàn)性表中指定序號的元素。

（6）遍歷線(xiàn)性表。 （7）從線(xiàn)性表查找具有給定值的元素。

（8）更新線(xiàn)性表中具有給定值的元素。 （9）向線(xiàn)性表的末尾添加一個(gè)元素。

（10）向線(xiàn)性表的表頭插入一個(gè)元素。 （11）向線(xiàn)性表中滿(mǎn)足條件的位置插入一個(gè)元素。

（12）從線(xiàn)性表中刪除表頭元素。 （13）從線(xiàn)性表中刪除等于給定值的元素。

（14）對線(xiàn)性表進(jìn)行排序。 鏈接存儲結構：每一個(gè)存儲單位（稱(chēng)之為存儲結點(diǎn)，簡(jiǎn)稱(chēng)結點(diǎn)），由所存元素本身的信息和元素間邏輯關(guān)系信息組成，它可以任意順序存儲任意存儲空間里。

也就是說(shuō)，鏈接存儲結構不要求元素依次存儲在一塊連續存儲空間。 采用鏈接存儲結構的線(xiàn)性表稱(chēng)之為鏈接表。

在進(jìn)行鏈接存儲時(shí)，每個(gè)結點(diǎn)除包含元素本身外，若只設置一個(gè)引用指向它后面元素（后繼），這樣構成的鏈接表稱(chēng)之為線(xiàn)性單向鏈接表，簡(jiǎn)稱(chēng)單鏈表。 若設置兩個(gè)引用分別指向它前面元素（前驅?zhuān)┖秃竺娴脑兀ê罄^），這樣構成的鏈表稱(chēng)之為線(xiàn)性雙向鏈接表，簡(jiǎn)稱(chēng)雙向鏈表。

在單鏈表中，若尾結點(diǎn)的后繼不是指向null，而是指頭結點(diǎn)，稱(chēng)之為循環(huán)鏈表。 鏈表的基本運算： （1）初始化，通過(guò)new建立一個(gè)空表。

（2）求表長(cháng)size。線(xiàn)性表的表長(cháng)等于單嘁鏈表所含表結點(diǎn)的個(gè)數。

（3）按序號查找。鏈表邏輯相鄰的結點(diǎn)并不是存貯在物理相鄰的單元中，所以不能像順序表那樣按序號i查找結點(diǎn)，在鏈表中只能從首結點(diǎn)出發(fā)，順后繼next逐個(gè)往下搜索，直到找到第i個(gè)結點(diǎn)為止。

故鏈表無(wú)法實(shí)現隨機存取。 （4）定位，即按值查找，也就是從前往后的順序，依次比較各結點(diǎn)數值域（item）與給定值X相等的結點(diǎn)的序號就是運算幽幽結果，若沒(méi)有這樣的結點(diǎn)運算結果為0。

(5)刪除。除了remove(Object o)方法需要先定義，其它各重載remove（)方法直接將待刪除結點(diǎn)的item、prev、next置為null，然后修改其前驅的后繼，后繼的前驅?zhuān)匾切薷膄irst、last。

(6)插入。刪除是unlink，插入是link，基本上刪除的反向操作。

鏈表的其他運算： （1）建表，即將一個(gè)線(xiàn)性表中的數據元素依次輸入并建立該線(xiàn)性表的單鏈表，也就是初始化運算和插入運算結合應用。 （2）消除重復結點(diǎn)，即刪除數據域（item）的值相同的多余結點(diǎn)，只保留其中序號最小的一個(gè)。

順序表和鏈表的比較： 1）順序表無(wú)需額外空間存儲各結點(diǎn)間關(guān)系系，較之鏈表占用存儲空間小； 2）順序表以位置（索引）直接存取各結點(diǎn)，存取方便；插入和刪除時(shí)需要移動(dòng)大量數據，效率低；鏈表在存取結點(diǎn)時(shí)需要從頭結點(diǎn)或尾結點(diǎn)逐一打開(kāi)后繼或前驅?zhuān)嫒⌒瘦^低，而插入和刪除時(shí)，只需要修改前驅和后繼，不需要移動(dòng)數據，效率較順序表要高。 3）順序表要求占用連續空間，只能預先分配（靜態(tài)分配），分配空間太大，易造成資源浪費，太小，易造成數據溢出；鏈表沒(méi)有這方面的要求，存儲空間可以動(dòng)態(tài)分配，任意修改空間大小。

4）順序表只能存儲線(xiàn)性表，而鏈表除此之外還可以存儲非線(xiàn)性表。 三、棧 棧（Stack）又稱(chēng)堆棧：是一種運算受限的線(xiàn)性表，其限制是僅允許在表的一端進(jìn)行插入和刪除運算。

允許進(jìn)行插入和刪除的一端稱(chēng)為棧項，另一端稱(chēng)為棧底。棧項的第一個(gè)元素稱(chēng)為棧頂元素，不含任何數據元素的棧稱(chēng)為空棧。

進(jìn)棧（也稱(chēng)入棧），即向一個(gè)棧插入新元素，它是把該元素放到棧項元素的上面，使之成為新的棧頂元素。 出棧（或退棧），即從一個(gè)棧刪除元素，它是把棧頂元素刪除掉，使其下面相鄰的元素成為新的棧頂元素。

棧的特征（棧的修改原則）：后進(jìn)先出或先進(jìn)后出（Last In First Out，簡(jiǎn)稱(chēng)LIFO）。 棧有兩種實(shí)現方法：順序實(shí)現和鏈接實(shí)現，這和線(xiàn)性表相似。

棧的順序存儲結構稱(chēng)為順序棧，通常由一個(gè)一維數組（Arrays）實(shí)現。棧的鏈式存儲結構稱(chēng)為鏈棧，可以通過(guò)鏈表（LinkedList）實(shí)現。

棧的基本運算： （1）初始化棧，構造一個(gè)空棧。 （2）清空棧 （3）檢查棧是否為空 （4）讀取棧頂元素 （5）向棧中插入元素 （6）從棧中刪除元素 （7）檢查棧是否已滿(mǎn)（僅適用于順序棧） 四、隊列 隊列（Queue）簡(jiǎn)稱(chēng)隊，也是一種去處受限的線(xiàn)性表，其限制是僅允許在表的一端進(jìn)。

2.線(xiàn)性表的基本操作

#include#include#include# define null 0 typedef char ElemType； /* 字符型數據*/ typedef struct LNode { ElemType data; struct LNode *next; }; void setnull(struct LNode **p); int length (struct LNode **p); ElemType get(struct LNode **p,int i); void insert(struct LNode **p,ElemType x,int i); int locate(struct LNode **p,ElemType x); void Delete(struct LNode **p,int i); void display(struct LNode **p); struct LNode * reverse(struct LNode **head); main() { struct LNode *head； /*定義變量*/ int select,x1,x2,x3; int i,n; int m,g; char e,y; setnull(&head)； /*建一鏈表并設置為空表*/ printf（"請輸入數據長(cháng)度： "）； scanf("%d",&n); printf（"將數據插入到單鏈表中： "）； for(i=1;i { scanf("%c",&y); if(y=='\n') i--; else { printf（"將數據插入到單鏈表中： "）； insert(&head,y,i)； } } /*插入數據到鏈表*/ display(&head)； /*顯示鏈表所有數據*/ printf("select 1 求長(cháng)度 length()\n"); printf("select 2 取結點(diǎn) get()\n"); printf("select 3 求值查找 locate()\n"); printf("select 4 刪除結點(diǎn) delete()\n"); printf("select 5 鏈表反轉 reverse()\n"); printf("input your select: "); scanf("%d",&select); switch(select) { case 1: { x1=length(&head); printf（"輸出單鏈表的長(cháng)度%d\n ",x1）; display(&head); }break; case 2: { printf（"請輸入要取得結點(diǎn)： "）； scanf("%d",&m); x2=get(&head,m); printf("%c\n",x2); display(&head); }break; case 3: { printf（"請輸入要查找的數據： "）； scanf("\n%c",&e); x3=locate(&head,e); printf("%d\n",x3); display(&head); }break; case 4: { printf（"請輸入要刪除的結點(diǎn)： "）； scanf("%d",&g); Delete(&head,g); display(&head); }break; case 5: { printf（"鏈表反轉："）； reverse(&head); display(&head); }break; } } void setnull(struct LNode **p) { *p=null; } int length (struct LNode **p) { int n=0; struct LNode *q=*p; while (q!=null) { n++; q=q->next; } return(n); } ElemType get(struct LNode **p,int i) { int j=1; struct LNode *q=*p; while (j { q=q->next; j++; } if(q!=null) return(q->data); else printf（"位置參數不正確！\n"）; return null; } int locate(struct LNode **p,ElemType x) { int n=0; struct LNode *q=*p; while (q!=null&&q->data!=x) { q=q->next; n++; } if(q==null) return(-1); else return(n+1); } void insert(struct LNode **p,ElemType x,int i) { int j=1; struct LNode *s,*q; q=*p; s=(struct LNode *)malloc(sizeof(struct LNode)); s->data=x; if(i==1) { s->next=q; *p = s; } else { while(jnext!=null) { q=q->next; j++; } if(j==i-1) { s->next=q->next; q->next=s; } else printf（"位置參數不正確！\n"）; } } void Delete(struct LNode **p,int i) { int j=1; struct LNode *q=*p,*t=null; if(i==1) { t=q; *p=q->next; } else { while(jnext!=null) { q=q->next; j++; } if(q->next!=null&&j==i-1) { t=q->next; q->next=t->next; } else printf（"位置參數不正確！\n"）; } if(t=null) free(t); } void display(struct LNode **p) { struct LNode *q; q=*p; printf（"單鏈表顯示： "）； if(q==null) printf（"鏈表為空！"）； else if (q->next==null) printf("%c\n",q->data); else { while(q->next!=null) { printf("%c->",q->data); q=q->next; } printf("%c",q->data); } printf("\n"); } struct LNode * reverse(struct LNode **head) { struct LNode *p,*q; p=null; while((*head)->next!=null) { q=p; p=*head; (*head)=(*head)->next; p->next=q; }(*head)->next=p; return *head; }。

3.線(xiàn)性表的定義是什么

線(xiàn)性表不僅是指在VF中，任何涉及到數據的知識都有線(xiàn)性表：線(xiàn)性表是最基本、最簡(jiǎn)單、也是最常用的一種數據結構。

線(xiàn)性表中數據元素之間的關(guān)系是一對一的關(guān)系，即除了第一個(gè)和最后一個(gè)數據元素之外，其它數據元素都是首尾相接的。線(xiàn)性表的邏輯結構簡(jiǎn)單，便于實(shí)現和操作。

因此，線(xiàn)性表這種數據結構在實(shí)際應用中是廣泛采用的一種數據結構。 線(xiàn)性表是一種常用的數據結構，以下介紹線(xiàn)性表及其順序存儲，并對棧和隊列及它們的順序實(shí)現給出了詳細的設計描述。

在實(shí)際應用中，線(xiàn)性表都是以棧、隊列、字符串、數組等特殊線(xiàn)性表的形式來(lái)使用的。由于這些特殊線(xiàn)性表都具有各自的特性，因此，掌握這些特殊線(xiàn)性表的特性，對于數據運算的可靠性和提高操作效率都是至關(guān)重要的。

線(xiàn)性表是一個(gè)線(xiàn)性結構，它是一個(gè)含有n≥0個(gè)結點(diǎn)的有限序列，對于其中的結點(diǎn)，有且僅有一個(gè)開(kāi)始結點(diǎn)沒(méi)有前驅但有一個(gè)后繼結點(diǎn)，有且僅有一個(gè)終端結點(diǎn)沒(méi)有后繼但有一個(gè)前驅結點(diǎn)，其它的結點(diǎn)都有且僅有一個(gè)前驅和一個(gè)后繼結點(diǎn)。一般地，一個(gè)線(xiàn)性表可以表示成一個(gè)線(xiàn)性序列：k1,k2，…，kn，其中k1是開(kāi)始結點(diǎn)，kn是終端結點(diǎn)。

是一個(gè)數據元素的有序（次序）集 線(xiàn)性結構的基本特征為： 1.集合中必存在唯一的一個(gè)“第一元素”； 2.集合中必存在唯一的一個(gè)“最后元素”； 3.除最后一個(gè)元素之外，均有唯一的后繼（后件）； 4.除第一個(gè)元素之外，均有唯一的前驅?zhuān)ㄇ凹?由n(n≥0)個(gè)數據元素（結點(diǎn)）a1,a2，…，an組成的有限序列。

數據元素的個(gè)數n定義為表的長(cháng)度。 當n=0時(shí)稱(chēng)為空表。

常常將非空的線(xiàn)性表（n>0）記作： （a1,a2，…an） 數據元素ai(1≦i≦n)只是一個(gè)抽象的符號，其具體含義在不同的情況下可以不同。 線(xiàn)性表的基本操作 1)Setnull(L)置空表 2)Length(L)求表長(cháng)度；求表中元素個(gè)數 3)Get(L,i)取表中第i個(gè)元素（1≤i≤n） 4)Prior(L,i)取i的前趨元素 5)Next(L,i)取i的后繼元素 6)Locate(L,x)返回指定元素在表中的位置 7)Insert(L,i,x)插入元素 8)Delete(L,x)刪除元素 9)Empty(L)判別表是否為空 線(xiàn)性表具有如下的結構特點(diǎn)： 1.均勻性：雖然不同數據表的數據元素可以是各種各樣的，但對于同一線(xiàn)性表的各數據元素必定具有相同的數所類(lèi)長(cháng)度。

2.有序性：各數據元素在線(xiàn)性表中的位置只取決于它們的序與，數據元素之前的相對位置是線(xiàn)性的，即存在唯一的“第一個(gè)“和“最后一個(gè)“的數據元素，除了第一個(gè)和最后一個(gè)外，其它元素前面均只有一個(gè)數據元素直接前趨和后面均只有一個(gè)數據元素（直接后繼）。 在實(shí)現線(xiàn)性表數據元素的存儲方面，一般可用順序存儲結構和鏈式存儲結構兩種方法。

鏈式存儲結構將在本網(wǎng)站線(xiàn)性鏈表中介紹，本章主要介紹用數組實(shí)現線(xiàn)性表數據元素的順序存儲及其應用。另外棧.隊列和串也是線(xiàn)性表的特殊情況，又稱(chēng)為受限的線(xiàn)性結構。

4.線(xiàn)性表的基本特征是什么

線(xiàn)性表的基本特征是：

1、集合中必存在唯一的一個(gè)第一元素。

2、集合中必存在唯一的一個(gè)最后元素 。

3、除最后一個(gè)元素之外，均有唯一的后繼。

4、除第一個(gè)元素之外，均有唯一的前驅。

擴展資料：

線(xiàn)性表主要由順序表示或鏈式表示。在實(shí)際應用中，常以棧、隊列、字符串等特殊形式使用。順序表示指的是用一組地址連續的存儲單元依次存儲線(xiàn)性表的數據元素，稱(chēng)為線(xiàn)性表的順序存儲結構或順序映像。

它以物理位置相鄰來(lái)表示線(xiàn)性表中數據元素間的邏輯關(guān)系，可隨機存取表中任一元素。鏈式表示指的是用一組任意的存儲單元存儲線(xiàn)性表中的數據元素，稱(chēng)為線(xiàn)性表的鏈式存儲結構。

它的存儲單元可以是連續的，也可以是不連續的。在表示數據元素之間的邏輯關(guān)系時(shí)，除了存儲其本身的信息之外，還需存儲一個(gè)指示其直接后繼的信息，這兩部分信息組成數據元素的存儲映像，稱(chēng)為結點(diǎn)。

參考資料來(lái)源：百度百科—線(xiàn)性表