數據結構復習總結第二章線性表

　　第二章線性表

　　線性表的邏輯結構

　　線性表是由n(n≥)個數據元素組成的有限序列當n=是稱為空表非空的線性表記為(aaa…an)

　　線性表的基本運算有

　　)InitList(L)構造空表即表的初始化;

　　)ListLength(L)求表的結點個數即表長;

　　)GetNode(Li)取表中第i個結點要求≤i≤ListLength(L);

　　)LocateNode(Lx)查找L中值為x的結點並返回結點在L中的位置有多個x則返回首個沒有則返回特殊值表示查找失敗

　　)InsertList(Lxi)在表的第i個位置插入值為x的新結點要求≤i≤ListLength(L)+;

　　)DeleteList(Li)刪除表的第i個位置的結點要求≤i≤ListLength(L);

　　線性表的順序存儲結構

　　順序表

　　順序表是把線性表的結點按邏輯次序存放在一組地址連續的存儲單元裡

　　結點的存儲地址計算公式Loc(ai)=Loc(a)+(i)*C;≤i≤n

　　順序表的定義

　　#define listsize

　　typedef int datatype;

　　typedef struct{

　　datatype data[listsize];

　　int length;

　　]seqlist;

　　順序表山的基本運算

　　 插入

　　void insertlist(seqlist *Ldatatype xint i)

　　{

　　int j;

　　if(i<||i>L>length+)

　　error(position error);

　　if(L>length>=listsize)

　　error(overflow);

　　for(j=L>length;j>=i;j)

　　L>data[j+]=L>data[j];

　　L>data[i]=x;

　　L>length++;

　　}

　　在順序表上插入要移動表的n/結點算法的平均時間復雜度為O(n)

　　刪除

　　void delete (seqlist *Lint i)

　　{

　　int j;

　　if(i<||i>L>length)

　　error(position error);

　　for(j=i;j<=L>length;j++)

　　L>data[j]=L>data[j];

　　L>length;

　　}

　　在順序表上刪除要移動表的(n+)/結點算法的平均時間復雜度為O(n)

　　線性表的鏈式存儲結構

　　用鏈接方式存儲的線性表稱鏈表

　　單鏈表

　　在結點中除了存儲結點值還存儲結點的後繼結點的地址data|nextdata是數據域next是指針域只有一個鏈域的鏈表稱單鏈表

　　單鏈表結點的定義

　　Typedef char datatype;

　　Typedef struct node{

　　Datatype data;

　　Struct node *next;

　　}listnode;

　　typedef listnode *linklist;

　　listnode *p;

　　linklist head;

　　結點的動態生成p=(listnode *)malloc(sizeof(listnode));結點的回收free(p);

　　 建立單鏈表時間復雜度為O(n)

　　) 頭插法建表

　　Link createlistF(void)

　　{

　　char ch;

　　linklist head;

　　listnode *s;

　　head=NULL;

　　ch=getchar();

　　while(ch!=\n){

　　s=(listnode *)malloc(sizeof(listnode));

　　s>data=ch;

　　s>next=head;

　　head=s;

　　ch=getchar();

　　}

　　return head;

　　}

　　)尾插法建表

　　Link createlistR(void)

　　{

　　char ch;

　　linklist head;

　　listnode *s *r;

　　s=NULL;r=NULL;

　　while((ch=getchar())!=\n){

　　s=(listnode *)malloc(sizeof(listnode));

　　s>data=ch;

　　if(head=NULL)

　　head=s;

　　else

　　r>next=s;

　　r=s;

　　}

　　if(r!=NNULL)

　　r>next=NULL;

　　return head;

　　}

　　在鏈表開始結點前附加一個頭結點的優點是)鏈表第一個位置的操作無需特殊處理;)將空表和非空表的處理統一

　　)帶頭結點的尾插法建表

　　Linklist createlisR(void)

　　{

　　char ch;

　　linklist head=(listnode *)malloc(sizeof(listnode));

　　listnode *s *r;

　　r=head;

　　while((ch=getchar())!=\n){

　　s=(listnode *)malloc(sizeof(listnode));

　　s>data=ch;

　　r>next=s;

　　r=s;

　　}

　　r>next=NULL;

　　return head;

　　}

　　 查找運算時間復雜度為O(n)

　　) 按序號查找

　　Listnode * getnode(linklist headint i)

　　{

　　int j;

　　listnode *p;

　　p=head;j=;

　　while(p>next&&j

　　p=p->next;

　　j++;

　　}

　　if(i==j)

　　return p;

　　else

　　return NULL;

　　}

　　2) 按值查找。Tw.wINgwiT.cOm

　　Listnode * locatenode(linklist head ,datatype key)

　　{

　　listnode *p=head->next;

　　while(p&&p->data!=key)

　　p=p->next;

　　return p;

　　}

　　3. 插入運算。時間復雜度為O(n)。

　　Void insertlist(linklist head ,datatype x, int i)

　　{

　　listnode *p;

　　p=getnode(head,i-1);

　　if(p==NULL);

　　error(“position error”);

　　s=(listnode *)malloc(sizeof(listnode));

　　s->data=x;

　　s->next=p->next;

　　p->next=s;

　　}

　　4. 刪除運算。時間復雜度為O(n)。

　　Void deletelist(linklist head ,int i)

　　{

　　listnode *p ,*r;

　　p=getnode(head ,i-1);

　　if(p==NULL||p->next==NULL)

　　error(“position error”);

　　r=p->next;

　　p->next=r->next;

　　free(r);

　　}

　　2.3.2循環鏈表。

　　循環鏈表是一種首尾相連的鏈表。特點是無需增加存儲量，僅對表的鏈接方式修改使表的處理靈活方便。

　　單鏈表是將終端結點的指針域指向表頭結點或開始結點。為使空表和非空表處理一致可設置一個頭結點。

　　用頭指針表示的單循環鏈表查找開始結點的時間是O(1),查找尾結點的時間是O(n);用尾指針表示的單循環鏈表查找開始結點和尾結點的時間都是O(1)。

　　2.3.3雙鏈表

　　在結點中增加一個指針域，prior|data|next。形成的鏈表中有兩條不同方向的鏈稱為雙鏈表。

　　雙鏈表結點定義。

　　Typedef struct dlistnode{

　　Datatype data;

　　Struct dlistnode *prior,*next;

　　}dlistnode;

　　typedef dlistnode *dlinklist;

　　dlinklist head;

　　1) 雙鏈表的前插操作。時間復雜度為O(1)。

　　Void dinsertbefore(dlistnode *p ,datatype x)

　　{

　　dlistnode *s=malloc(sizeof(dlistnode));

　　s->data=x;

　　s->prior=p->prior;

　　s->next=p;

　　p->prior->next=s;

　　p->prior=s;

　　}

　　2) 雙鏈表的刪除操作。時間復雜度為O(1)。

　　Void ddeletenode(dlistnode *p)

　　{

　　p->prior->next=p->next;

　　p->next->prior=p->prior;

　　free(p);

　　}

　　2.4順序表和鏈表的比較。

　　1) 基於空間的考慮：順序表的存儲空間是靜態分配的，鏈表的存儲空間是動態分配的。順序表的存儲密度比鏈表大。因此，在線性表長度變化不大，易於事先確定時，宜采用順序表作為存儲結構。

　　2) 基於時間的考慮：順序表是隨機存取結構，若線性表的操作主要是查找，很少有插入、刪除操作時，宜用順序表結構。對頻繁進行插入、刪除操作的線性表宜采用鏈表。若操作主要發生在表的首尾時采用尾指針表示的單循環鏈表。

　　附二:

　　第二章 線性表

　　*************************************************************************************

　　線性表是由n≥0個數據元素組成的有限序列。n=0是空表;非空表，只能有一個開始結點，有且只能有一個終端結點。

　　*************************************************************************************

　　線性表上定義的基本運算：·構造空表：Initlist(L)

　　·求表長：Listlength(L)

　　·取結點：GetNode(L,i)

　　·查找：LocateNode(L,x)

　　·插入：InsertList(L,x,i)

　　·刪除：Delete(L,i)

　　*************************************************************************************

From:http://tw.wingwit.com/Article/program/sjjg/201311/23755.html