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

1.什么是線性表的基本理論知

一、線性表（定義） 線性表（Linear List）：是具有相同屬性的數(shù)據(jù)元素的一個有限序列。

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

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

因此，邏輯結(jié)構(gòu)中相鄰的結(jié)點在存儲結(jié)構(gòu)中仍相鄰。我們把順序存儲的線性表統(tǒng)稱為順序表，它的順序存儲結(jié)構(gòu)是利用數(shù)組來實現(xiàn)的。

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

(2)清除線性表中的所有元素。 （3）獲取線性表的長度。

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

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

（8）更新線性表中具有給定值的元素。 （9）向線性表的末尾添加一個元素。

（10）向線性表的表頭插入一個元素。 （11）向線性表中滿足條件的位置插入一個元素。

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

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

也就是說，鏈接存儲結(jié)構(gòu)不要求元素依次存儲在一塊連續(xù)存儲空間。 采用鏈接存儲結(jié)構(gòu)的線性表稱之為鏈接表。

在進(jìn)行鏈接存儲時，每個結(jié)點除包含元素本身外，若只設(shè)置一個引用指向它后面元素（后繼），這樣構(gòu)成的鏈接表稱之為線性單向鏈接表，簡稱單鏈表。 若設(shè)置兩個引用分別指向它前面元素（前驅(qū)）和后面的元素（后繼），這樣構(gòu)成的鏈表稱之為線性雙向鏈接表，簡稱雙向鏈表。

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

（2）求表長size。線性表的表長等于單嘁鏈表所含表結(jié)點的個數(shù)。

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

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

(5)刪除。除了remove(Object o)方法需要先定義，其它各重載remove（)方法直接將待刪除結(jié)點的item、prev、next置為null，然后修改其前驅(qū)的后繼，后繼的前驅(qū)，必要是修改first、last。

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

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

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

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

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

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

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

棧的順序存儲結(jié)構(gòu)稱為順序棧，通常由一個一維數(shù)組（Arrays）實現(xiàn)。棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，可以通過鏈表（LinkedList）實現(xiàn)。

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

2.線性表的基本操作

#include#include#include# define null 0 typedef char ElemType； /* 字符型數(shù)據(jù)*/ 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)； /*建一鏈表并設(shè)置為空表*/ printf（"請輸入數(shù)據(jù)長度： "）； scanf("%d",&n); printf（"將數(shù)據(jù)插入到單鏈表中： "）； for(i=1;i { scanf("%c",&y); if(y=='\n') i--; else { printf（"將數(shù)據(jù)插入到單鏈表中： "）； insert(&head,y,i)； } } /*插入數(shù)據(jù)到鏈表*/ display(&head)； /*顯示鏈表所有數(shù)據(jù)*/ printf("select 1 求長度 length()\n"); printf("select 2 取結(jié)點 get()\n"); printf("select 3 求值查找 locate()\n"); printf("select 4 刪除結(jié)點 delete()\n"); printf("select 5 鏈表反轉(zhuǎn) reverse()\n"); printf("input your select: "); scanf("%d",&select); switch(select) { case 1: { x1=length(&head); printf（"輸出單鏈表的長度%d\n ",x1）; display(&head); }break; case 2: { printf（"請輸入要取得結(jié)點： "）； scanf("%d",&m); x2=get(&head,m); printf("%c\n",x2); display(&head); }break; case 3: { printf（"請輸入要查找的數(shù)據(jù)： "）； scanf("\n%c",&e); x3=locate(&head,e); printf("%d\n",x3); display(&head); }break; case 4: { printf（"請輸入要刪除的結(jié)點： "）； scanf("%d",&g); Delete(&head,g); display(&head); }break; case 5: { printf（"鏈表反轉(zhuǎn)："）； 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（"位置參數(shù)不正確！\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（"位置參數(shù)不正確！\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（"位置參數(shù)不正確！\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.線性表的定義是什么

線性表不僅是指在VF中，任何涉及到數(shù)據(jù)的知識都有線性表：線性表是最基本、最簡單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。

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

因此，線性表這種數(shù)據(jù)結(jié)構(gòu)在實際應(yīng)用中是廣泛采用的一種數(shù)據(jù)結(jié)構(gòu)。 線性表是一種常用的數(shù)據(jù)結(jié)構(gòu)，以下介紹線性表及其順序存儲，并對棧和隊列及它們的順序?qū)崿F(xiàn)給出了詳細(xì)的設(shè)計描述。

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

線性表是一個線性結(jié)構(gòu)，它是一個含有n≥0個結(jié)點的有限序列，對于其中的結(jié)點，有且僅有一個開始結(jié)點沒有前驅(qū)但有一個后繼結(jié)點，有且僅有一個終端結(jié)點沒有后繼但有一個前驅(qū)結(jié)點，其它的結(jié)點都有且僅有一個前驅(qū)和一個后繼結(jié)點。一般地，一個線性表可以表示成一個線性序列：k1,k2，…，kn，其中k1是開始結(jié)點，kn是終端結(jié)點。

是一個數(shù)據(jù)元素的有序（次序）集 線性結(jié)構(gòu)的基本特征為： 1.集合中必存在唯一的一個“第一元素”； 2.集合中必存在唯一的一個“最后元素”； 3.除最后一個元素之外，均有唯一的后繼（后件）； 4.除第一個元素之外，均有唯一的前驅(qū)（前件）。 由n(n≥0)個數(shù)據(jù)元素（結(jié)點）a1,a2，…，an組成的有限序列。

數(shù)據(jù)元素的個數(shù)n定義為表的長度。 當(dāng)n=0時稱為空表。

常常將非空的線性表（n>0）記作： （a1,a2，…an） 數(shù)據(jù)元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。 線性表的基本操作 1)Setnull(L)置空表 2)Length(L)求表長度；求表中元素個數(shù) 3)Get(L,i)取表中第i個元素（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)判別表是否為空 線性表具有如下的結(jié)構(gòu)特點： 1.均勻性：雖然不同數(shù)據(jù)表的數(shù)據(jù)元素可以是各種各樣的，但對于同一線性表的各數(shù)據(jù)元素必定具有相同的數(shù)所類長度。

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

鏈?zhǔn)酱鎯Y(jié)構(gòu)將在本網(wǎng)站線性鏈表中介紹，本章主要介紹用數(shù)組實現(xiàn)線性表數(shù)據(jù)元素的順序存儲及其應(yīng)用。另外棧.隊列和串也是線性表的特殊情況，又稱為受限的線性結(jié)構(gòu)。

4.線性表的基本特征是什么

線性表的基本特征是：

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

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

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

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

擴(kuò)展資料：

線性表主要由順序表示或鏈?zhǔn)奖硎?。在實際應(yīng)用中，常以棧、隊列、字符串等特殊形式使用。順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，稱為線性表的順序存儲結(jié)構(gòu)或順序映像。

它以物理位置相鄰來表示線性表中數(shù)據(jù)元素間的邏輯關(guān)系，可隨機存取表中任一元素。鏈?zhǔn)奖硎局傅氖怯靡唤M任意的存儲單元存儲線性表中的數(shù)據(jù)元素，稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

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

參考資料來源：百度百科—線性表