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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

棧的基本運(yùn)算： （1）初始化棧，構(gòu)造一個(gè)空棧。 （2）清空棧 （3）檢查棧是否為空 （4）讀取棧頂元素 （5）向棧中插入元素 （6）從棧中刪除元素 （7）檢查棧是否已滿（僅適用于順序棧） 四、隊(duì)列 隊(duì)列（Queue）簡(jiǎn)稱隊(duì)，也是一種去處受限的線性表，其限制是僅允許在表的一端進(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（"請(qǐng)輸入數(shù)據(jù)長(zhǎng)度： "）； 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 求長(zhǎng)度 length()\n"); printf("select 2 取結(jié)點(diǎn) get()\n"); printf("select 3 求值查找 locate()\n"); printf("select 4 刪除結(jié)點(diǎn) delete()\n"); printf("select 5 鏈表反轉(zhuǎn) reverse()\n"); printf("input your select: "); scanf("%d",&select); switch(select) { case 1: { x1=length(&head); printf（"輸出單鏈表的長(zhǎng)度%d\n ",x1）; display(&head); }break; case 2: { printf（"請(qǐng)輸入要取得結(jié)點(diǎn)： "）； scanf("%d",&m); x2=get(&head,m); printf("%c\n",x2); display(&head); }break; case 3: { printf（"請(qǐng)輸入要查找的數(shù)據(jù)： "）； scanf("\n%c",&e); x3=locate(&head,e); printf("%d\n",x3); display(&head); }break; case 4: { printf（"請(qǐng)輸入要?jiǎng)h除的結(jié)點(diǎn)： "）； 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í)都有線性表：線性表是最基本、最簡(jiǎn)單、也是最常用的一種數(shù)據(jù)結(jié)構(gòu)。

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

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

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

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

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

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

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

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

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

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

線性表的基本特征是：

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

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

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

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

擴(kuò)展資料：

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

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

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

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